실시간 시스템의 DMA I / O 요구를 위한 최악 시간 분석

한주선(Joosun Hahn),하란(Rhan Ha),민상렬(Sang Lyul Min) 한국정보과학회 2005 정보과학회논문지 : 시스템 및 이론 Vol.32 No.3·4

CPU의 수행과 병행하여 I/O가 수행되도록 DMA 방식을 채택한 실시간 시스템의 스케줄 가능성을 보장하기 위해서는 CPU 태스크 뿐만 아니라 I/O 요구의 스케줄 가능성도 반드시 검증되어야 한다. 본 논문에서는 CPU에게 최상위 우선순위가 할당된 고정우선순위 버스 프로토콜을 기반으로 CPU와 다수의 DMA 컨트롤러가 시스템 버스를 공유하는 환경에서 DMA I/O 요구의 최악 응답시간을 분석하는 기법을 제안한다. 제안하는 분석 기법의 첫 번째 단계에서는 CPU 상에서 수행 중인 각 CPU 태스크별로 최악 버스 요구 패턴을 구한다. 두 번째 단계에서는 이들 CPU 태스크의 최악 버스 요구 패턴을 모두 통합해 CPU 전체의 최악 버스 요구 패턴을 구한다. 최종 세 번째 단계에서는 CPU의 최악 버스 요구 패턴으로부터 DMA 컨트롤러의 버스 가용량을 구하고 DMA I/O 요구의 최악 응답시간을 산출한다. 모의 실험을 통해 제안하는 분석 기법이 일반적인 DMA 전송량에 대해 20% 오차 범위 이내에서 안전한 응답시간을 산출하며, DMA 전송량이 증가할수록 오차가 점차 감소함을 보였다. We propose a technique for finding the worst case response time (WCRT) of a DMA request that is needed in the schedulability analysis of a whole real-time system. The technique consists of three steps. In the first step, we find the worst case bus usage pattern of each CPU task. Then in the second step, we combine the worst case bus usage patterns of CPU tasks to construct the worst case bus usage pattern of the CPU. This second step considers not only the bus requests made by CPU tasks individually but also those due to preemptions among the CPU tasks. Finally, in the third step, we use the worst case bus usage pattern of the CPU to derive the WCRT of DMA requests assuming the fixed-priority bus arbitration protocol. Experimental results show that overestimation of the DMA response time by the proposed technique is within 20% for most DMA request sizes and that the percentage overestimation decreases as the DMA request size increases.

무선 센서 네트워크에서의 감지범위 보존을 위한 백업 노드 기반 결함 허용 기법

한주선(Joosun Hahn),하란(Rhan Ha) 한국정보과학회 2009 정보과학회논문지 : 정보통신 Vol.36 No.4

무선 센서 네트워크에서 센서 노드의 한정된 배터리 자원은 네트워크 수명에 직접적인 영향을 끼친다. 따라서 불필요한 전력 소모를 줄이기 위해, 많은 경우 최소한의 센서 노드만을 활성 모드로 유지하고 나머지는 휴면 모드로 유지한다. 그러나 이러한 경우, 예상하지 못한 결함으로 인해 센서 노드가 감지 및 전송 기능을 수행하지 못하게 되면 네트워크 서비스를 안정적으로 제공할 수가 없다. 따라서 센서 노드의 결함에도 불구하고 감지수준을 일정하게 유지하는 것은 신뢰성 있는 감지환경을 제공하는 데 있어 매우 중요하다. 본 논문에서는 센서 노드의 결함으로 인한 감지수준 저하의 문제를 효과적으로 극복하기 위해 FCP(Fault-tolerant Coverage Preserving) 기법을 제안한다. FCP 기법에서는 각 활성 노드에 대해 백업 노드 집합을 미리 선정하여, 활성 노드의 결함 시 결함 노드를 대신하도록 한다. 성능 평가 결과, FCP 기법이 기존 결함 허용 기법들에 비해 평균 87.2% 향상된 감지범위 보존 성능을 보일 뿐 아니라, 추가 백업 노드 수와 추가 제어 메시지 전송량 측면에서도 각각 평균 57.6%, 평균 99.5% 향상된 효율성을 제공함을 보였다. In wireless sensor networks, the limited battery resources of sensor nodes have a direct impact on network lifetime. To reduce unnecessary power consumption, it is often the case that only a minimum number of sensor nodes operate in active mode while the others are kept in sleep mode. In such a case, however, the network service can be easily unreliable if any active node is unable to perform its sensing or communication function because of an unexpected failure. Thus, for achieving reliable sensing, it is important to maintain the sensing level even when some sensor nodes fail. In this paper, we propose a new fault-tolerance scheme, called FCP(Fault-tolerant Coverage Preserving), that gives an efficient way to handle the degradation of the sensing level caused by sensor node failures. In the proposed FCP scheme, a set of backup nodes are pre-designated for each active node to be used to replace the active node in case of its failure. Experimental results show that the FCP scheme provides enhanced performance with reduced overhead in terms of sensing coverage preserving, the number of backup nodes and the amount of control messages. On the average, the percentage of coverage preserving is improved by 87.2% while the additional number of backup nodes and the additional amount of control messages are reduced by 57.6% and 99.5%, respectively, compared with previous fault-tolerance schemes.

고정우선순위 버스 프로토콜 환경에서 DMA I / O 요구의 최악 응답시간 분석

한주선(Joosun Hahn),하란(Rhan Ha),민상렬(Sang Lyul Min) 한국정보과학회 1999 한국정보과학회 학술발표논문집 Vol.26 No.2Ⅲ

CPU에게 최상위 우선순위가 할당된 고정우선순위 버스 프로토콜에서는 CPU와 DMA 컨트롤러의 버스 요구가 충돌할 경우 DMA 전송이 지연된다. 본 논문에서는 CPU와 다수의 DMA 컨트롤러가 시스템 버스를 공유하는 환경에서 DMA I/O 요구의 최악 응답시간을 분석하는 기법을 제안한다. 제안하는 최악 응답시간 분석 기법은 다음의 세단계로 구성되어 있다. 첫번째 단계에서는 CPU 상에서 수행중인 각 CPU 태스크별로 최악 버스 요구 패턴을 구한다. 두번째 단계에서는 이들 CPU 태스크의 최악 버스 요구 페턴을 모두 통합해 CPU 전체의 최악 버스 요구 패턴을 구한다. 최종 세번째 단계에서는 CPU의 최악 버스 요구 패턴으로부터 DMA 컨트롤러의 버스 가용량을 구하고 DMA I/O 요구의 촤악 응답시간을 산출한다. 모의 실험을 통한 제안하는 분석 기법이 일반적인 DMA 전송량에 대해 20% 오차 범위 이내에서 안전한 응답시간을 산출함을 보였다.

고정우선순위 선점가능 스케쥴링 환경에서의 캐쉬에 의한 선점지연시간 분석 (pp.243-256)

이창건(Chang-Gun Lee),한주선(Joosun Hahn),서양민(Yang-Min Seo),민상렬(Sang Lyul Min),하란(Rhan Ha),홍성수(Seongsoo Hong),박창윤(Chang Yun Park),이민석(Minsuk Lee),김종상(Chong Sang Kim) 한국정보과학회 1998 정보과학회논문지 : 시스템 및 이론 Vol.25 No.3

프로세서와 메모리사이의 속도차가 증가함에 따라, 범용 컴퓨터 시스템에서 뿐만 아니라 실시간 컴퓨터 시스템에서도 캐쉬 메모리의 필요성이 증대되었다. 캐쉬 메모리의 사용은 태스크의 평균 수행시간을 감소시키는 긍정적인 측면을 가지고 있는 반면, 태스크간의 선점이 허용되는 멀티태스킹 환경에서는 태스크의 수행시간에 예측하기 힘든 추가비용(캐쉬에 의한 선점지연시간)을 초래한다는 부정적 측면도 가지고 있다. 이러한 부정적 측면은 주어진 시간안에 태스크의 수행 완료를 보장해야 하는 실시간 컴퓨터 시스템이 캐쉬 메모리를 사용하는 것을 어렵게 만드는 요소로 작용한다. 본 논문에서는 고정우선순위 선점가능 스케쥴링 환경에서 보다 정확하게 케쉬에 의한 선점지연시간을 예측하기 위한 분석기법을 제안한다. 캐쉬에 의한 선점지연시간을 예측하기 위한 현재까지의 연구는 “선점하는 태스크는 현재 캐쉬에 올라와 있는 선점되는 태스크의 메모리블럭을 캐쉬로부터 모두 쫓아내며, 이렇게 쫓겨난 메모리블럭들은 선점된 태스크가 이후에 수행을 재개했을 때 모두 다시 캐쉬로 올라와야 한다”는 비관적인 가정을 바탕으로한다. 그러나 본 논문에서 제안하는 기법은 각 태스크가 선점시 지불해야하는 캐쉬에 의한 선점비용으로 유용한 - 이후에 다시 사용되는 - 캐쉬블럭만을 고려하므로써 보다 정확하게 캐쉬에 의한 선점지연시간을 예측할 수 있다. 제안되는 기법은 두 단계로 이루어진다. 첫번째 단계에서는 각각의 태스크를 독립적으로 분석하여, 주어진 태스크의 각 수행지점에서의 유용한 캐쉬블럭의 수를 계산하고 이를 이용하여 해당 수행 지점에서의 캐쉬에 의한 선점비용을 구한다. 이렇게 구해진 선점비용들은 각 태스크가 특정 횟수만큼 선점될 때 부가적으로 지불하게 되는 캐쉬에 의한 최악 선점비용을 나타내도록 표의 형태로 정리된다. 두번째 단계에서는 첫번째 단계의 결과를 본 논문에서 정의한 선형계획법의 입력으로 이용하여 주어진 시간동안 발생할 수 있는 캐쉬에 의한 최악 선점지연시간을 계산하고, 이를 최악 반응시간식에 적용하여 각 태스크의 최악 반응시간을 구한다. 이렇게 구해진 최악 반응시간은 기존의 기법에 의해 구해진 값에 비해 보다 정확한 최악 반응시간 예측값이며, 따라서 이를 이용하면 보다 정확하게, 주어진 태스크가 마감시간 이내에 수행을 완료할 수 있는가 여부( 스케쥴 가능성 - schedulability)를 판단할 수 있다. 본 논문에서 행한 실험에 따르면, 제안된 기법은 기존의 기법에 비해 최고 60%까지 더 정확하게 캐쉬에 의한 선점지연시간을 예측해낸다. Cache memory is increasingly being used in real-time computer systems as well as general purpose computer systems due to the ever increasing speed gap between processors and main memory. However, the use of cache memory in real-time systems introduces variation to task execution time when preemptions are allowed among tasks. This paper proposes a technique for analyzing the cache-related preemption delays of tasks that cause such unpredictable variation in task execution time in the context of fixed-priority preemptive scheduling. Unlike previous approaches that make a pessimistic assumption that each memory block of a preempting task replaces from cache memory a memory block needed by a lower priority task, the proposed technique considers the usefulness of cache blocks in computing cache-related preemption delay to improve prediction accuracy. The proposed technique consists of two steps The first step performs a per-task analysis to estimate cache-related preemption cost for each execution paint in a given task from the number of useful cache blocks at the execution point. The results of this first step are given in a table that specifies the (worst case) preemption cost for a given number of preemptions. The second step computes the worst case response time of each task using a response time equation and a linear programming technique which takes as its input the preemption cost information of tasks obtained in the first step. Our experimental results show that the proposed technique gives a prediction of the worst case cache-related preemption delay that is up to 60% tighter than that obtained from previous approaches.

무선 센서 네트워크에서 전송 레벨을 이용한 RF 위치 측정 기법

채상윤(Chae Sang Yun),한주선(Joosun Hahn),하란(Rhan Ha) 한국정보과학회 2007 한국정보과학회 학술발표논문집 Vol.34 No.2D

무선 센서 네트워크는 경제적, 환경적 목적으로 다양한 방면에서 활용되고 있다. 이 때, 배치된 각 센서의 위치를 파악하는 것은 센서 네트워크에서 가장 기본적이며 가장 중요한 문제 중의 하나이다. 기존 논문에서 제안된 센서 위치 측정 방법은 특별한 장비를 장착하거나 특정한 환경의 지역에 한정시킨 방법으로 제한하고 있는 경우가 대부분이다. 하지만 어떠한 관심 지역의 환경은 언제라도 바뀔 수 있다. 또한, 센서가 위치할 환경의 기온, 풍속 등을 미리 안다는 것은 비현실적인 가정이다. 더구나 각각의 센서에 특별한 장비를 장착한다는 것은 비용 절감을 이유로 센서 네트워크를 운영하는 경우 오히려 그것을 이용하지 않는 경우보다 비용이 더 들 수도 있다. 이에 본 논문에서는 센서 노드의 기본적인 통신 기능을 이용하여, 환경에 순응적으로 센서의 위치를 측정할 수 있는 방법을 제안하고자 한다. 센서 노드에서 기본적으로 제공하는 통신 기능은 RF 전파를 보낼 때 전송 레벨을 달리하여 보낼 수 있다. 이러한 기본적인 기능을 이용하여 위치를 측정하게 되면, 전체적인 센서 네트워크의 비용이 절감될 뿐만 아니라 환경에 순응적인 위치 측정이 가능하게 된다. 또한, 각 노드의 위치가 정해진 후 다른 노드와 통신할 때 전파의 세기를 조정함으로써 RF 통신에서 소모되는 전력량을 줄일 수 있다. 따라서 본 논문에서 제안하는 전송 레벨을 이용한 위치 측정 방법은 단순히 위치를 측정한다는 의미뿐 아니라 환경에 순응적으로 작동한다는 장점이 있다. 향후 네트워크 내에서 통신에 소비되는 전력을 줄일 수 있다는 점에서도 중요한 의미를 지닌다.

무선 센서 네트워크에서의 연속적인 물체의 추적을 위한 에너지 효율적인 경계 선정 기법

장상욱(Sangwook Jang),한주선(Joosun Hahn),하란(Rhan Ha) 한국정보과학회 2009 정보과학회논문지 : 정보통신 Vol.36 No.6

Wireless sensor networks (WSNs) can be used in various applications for military or environmental purpose. Recently, there are lots of on-going researches for detecting and tracking the spread of continuous objects or phenomena such as poisonous gas, wildfires, earthquakes, and so on. Some previous work has proposed techniques to detect edge nodes of such a continuous object based on the information of all the 1-hop neighbor nodes. In those techniques, however, a number of nodes are redundantly selected as edge nodes, and thus, the boundary of the continuous object cannot be presented accurately. In this paper, we propose a new edge detection method in which edge nodes of the continuous object are detected based on the information of the neighbor nodes obtained via the Localized Delaunay Triangulation so that a minimum number of nodes are selected as edge nodes. We also define the sensor behavior rule for tracking continuous objects energy-efficiently. Our simulation results show that the proposed edge detection method provides enhanced performance compared with previous 1-hop neighbor node based methods. On the average, the accuracy is improved by 29.95% while the number of edge nodes, the amount of communication messages and energy consumption are reduced by 54.43%, 79.36% and 72.34%, respectively. Moreover, the number of edge nodes decreases by 48.38% on the average in our field test with MICAz motes. 무선 센서 네트워크는 군사적, 환경적 목적으로 다방면에서 활용될 수 있는데, 최근 유독가스, 산불, 지진과 같은 연속적인 성격을 가진 물체의 확산 경로를 추적하는 연구가 새롭게 진행되고 있다. 기존 연구에서는 연속적인 물체의 경계를 지역적으로 측정하기 위해 1-홉 이웃 노드들과의 통신을 통한 방식을 제시하였으나, 이러한 방식은 불필요하게 많은 노드들이 경계 노드로 선택되어 물체의 경계를 정확히 측정할 수 없는 문제를 안고 있다. 본 논문에서는 최소한의 경계 노드를 선별하기 위해 지역적인 드로네 삼각기법을 이용한 방법을 제안하고, 연속적인 물체를 에너지 효율적으로 추적하기 위한 센서의 동작 규칙을 규정한다. 모의실험 결과, 본 논문에서 제안한 방법이 기존의 1-홉 경계 설정과 비교해 경계 노드의 선택 정확도는 평균 29.95% 개선되면서도 경계 노드의 수는 평균 54.43% 감소하며, 통신 메시지 수와 에너지 소모량은 각각 평균 79.36%, 72.34% 향상됨을 보였다. 또한, MICAz mote를 이용한 현장실험을 통해 평균 48.38% 경계 노드 수가 감소함을 보였다.