센서 네트워크는 빛, 소리, 온도, 움직임 같은 물리적 데이터를 센서 노드에서 감지하고 측정하여 중앙으로 전달하고 처리하는 구조를 가진 네트워크이다. 센서 네트워크는 여러 분야에서 활용할 수 있는 기술이다. 센서 노드가 외부에서 채취한 데이터를 실시간으로 사용자에게 전달하는 것은 매우 중요하다. 센서 네트워크의 핵심은 센서 노드인 하드웨어 플랫폼과 노드에 들어가는 초소형 운영체제라고 할 수 있다. UC 버클리에서 개발된 TinyOS는 센서 노드에서 동작하는 운영체제 중 가장 많이 사용되고 있다. TinyOS는 Event-driven 방식이며 Component 기반의 센서 네트워크 운영체제이다. 기본적으로 비선점 방식의 스케줄러를 사용한다. 만약 급한 작업이 수행되어야 하는 시점에서 다른 태스크가 수행 중에 있다면 수행 중인 태스크가 완료할 때까지 기다려야 한다. 이러한 특성으로 인해 TinyOS에서 정해진 시간안에 자신의 작업을 끝낸다고 보장하기 어렵다. 최근 연구에서 TinyOS의 빠른 반응성을 위해 Priority Level Scheduler라는 선점 기능이 제안되었다. 이것은 제한적으로 5개의 우선순위를 만들어 높은 우선순위가 낮은 우선순위를 선점할 수 있게 한다. 여기서 본 논문은 TinyOS의 실시간성을 보장함과 더불어 사용자 태스크의 평균 응답시간을 줄이고자 Priority Level Scheduler에 실시간 스케줄러인 EDF(Earliest Deadline First)를 적용한 선점형 EDF 스케줄링 방식을 제안하고자 한다.
센서 네트워크는 빛, 소리, 온도, 움직임 같은 물리적 데이터를 센서 노드에서 감지하고 측정하여 중앙으로 전달하고 처리하는 구조를 가진 네트워크이다. 센서 네트워크는 여러 분야에서 활용할 수 있는 기술이다. 센서 노드가 외부에서 채취한 데이터를 실시간으로 사용자에게 전달하는 것은 매우 중요하다. 센서 네트워크의 핵심은 센서 노드인 하드웨어 플랫폼과 노드에 들어가는 초소형 운영체제라고 할 수 있다. UC 버클리에서 개발된 TinyOS는 센서 노드에서 동작하는 운영체제 중 가장 많이 사용되고 있다. TinyOS는 Event-driven 방식이며 Component 기반의 센서 네트워크 운영체제이다. 기본적으로 비선점 방식의 스케줄러를 사용한다. 만약 급한 작업이 수행되어야 하는 시점에서 다른 태스크가 수행 중에 있다면 수행 중인 태스크가 완료할 때까지 기다려야 한다. 이러한 특성으로 인해 TinyOS에서 정해진 시간안에 자신의 작업을 끝낸다고 보장하기 어렵다. 최근 연구에서 TinyOS의 빠른 반응성을 위해 Priority Level Scheduler라는 선점 기능이 제안되었다. 이것은 제한적으로 5개의 우선순위를 만들어 높은 우선순위가 낮은 우선순위를 선점할 수 있게 한다. 여기서 본 논문은 TinyOS의 실시간성을 보장함과 더불어 사용자 태스크의 평균 응답시간을 줄이고자 Priority Level Scheduler에 실시간 스케줄러인 EDF(Earliest Deadline First)를 적용한 선점형 EDF 스케줄링 방식을 제안하고자 한다.
A sensor network is a special network that makes physical data sensed by sensor nodes and manages the data. The sensor network is a technology that can apply to many parts of field. It is very important to transmit the data to a user at real-time. The core of the sensor network is a sensor node and ...
A sensor network is a special network that makes physical data sensed by sensor nodes and manages the data. The sensor network is a technology that can apply to many parts of field. It is very important to transmit the data to a user at real-time. The core of the sensor network is a sensor node and small operating system that works in the node. TinyOS developed by UC Berkeley is a sensor network operating system that used many parts of field. It is event-driven and component-based operating system. Basically, it uses non-preemptive scheduler. If an urgent task needs to be executed right away while another task is running, the urgent one must wait until another one is finished. Because of that property, it is hard to guarantee real-time requirement in TinyOS. According to recent study, Priority Level Scheduler, which can let one task preempt another task, was proposed in order to have fast response in TinyOS. It has restrictively 5 priorities, so a higher priority task can preempt a lower priority task. Therefore, this paper suggests Preemptive EDF(Earliest Deadline First) Scheduler that guarantees a real-time requirement and reduces average respond time of user tasks in TinyOS.
A sensor network is a special network that makes physical data sensed by sensor nodes and manages the data. The sensor network is a technology that can apply to many parts of field. It is very important to transmit the data to a user at real-time. The core of the sensor network is a sensor node and small operating system that works in the node. TinyOS developed by UC Berkeley is a sensor network operating system that used many parts of field. It is event-driven and component-based operating system. Basically, it uses non-preemptive scheduler. If an urgent task needs to be executed right away while another task is running, the urgent one must wait until another one is finished. Because of that property, it is hard to guarantee real-time requirement in TinyOS. According to recent study, Priority Level Scheduler, which can let one task preempt another task, was proposed in order to have fast response in TinyOS. It has restrictively 5 priorities, so a higher priority task can preempt a lower priority task. Therefore, this paper suggests Preemptive EDF(Earliest Deadline First) Scheduler that guarantees a real-time requirement and reduces average respond time of user tasks in TinyOS.
* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.
문제 정의
그러나 Priority Level Scheduler의 단점으로 우선순위를 컴파일 하기 전에 주어야 하는데 선점형 EDF 스케줄러는 매 순간의 deadline에 따라 우선순위를 판단해야 하기 때문에 Priority Level Scheduler를 바로 적용하기 어렵다. 그래서 본 논문은 Priority Level Scheduler에 실시간 스케줄러의 기능을 적용한 선점형 EDF 스케줄러를 제안하고자 한다.
2 절에서 언급한 비선점일 경우의 문제가 발생하는 경우를 바탕으로 하였다. 또한, 동일한 상황 하에 비선점형 EDF 스케줄러와 비교 실험하여 선점형 EDF 스케줄러가 더 우수하다는 것을 검증하고자 한다.
본 논문에서는 TinyOS상에서 실시간성을 개선하기 위해서 Priority Level Scheduler상에 대표적인 실시간 스케줄링 알고리즘인 EDF(Earliest Deadline First)[5]를 사용하여 실시간성을 보장하는 선점형 EDF 스케줄링 기법을 제시한다.
본 실험은 구현된 선점형 EDF 스케줄러가 정상적으로 동작하는 것을 확인하는 실험이다. Kmote에 프로그램을 업로드 하여 콘솔 화면에서 확인을 하였다.
본 실험은 선점형 EDF 스케줄러의 동작을 확인하고, TinyOS에서 제공하는 비선점형 EDF 스케줄러와 성능을 비교함으로써 선점형 EDF 스케줄러가 좀 더 많은 태스크의 deadline을 만족함을 보이는데 목적이 있다.
여기서 우리가 원하는 결과는 (c)와 같이 t3이 t0을 선점하여 t3의 deadline을 충족시키고, t0의 수행을 늦추므로써 실시간성 및 응답성을 만족시키고자 한다. 이에 본 논문은 (c)와 같이 선점할 수 있는 EDF 스케줄링을 제시하고자 한다.
그러나 T3의 데드라인을 보면 다른 태스크보다 더 빠르다는 것을 알 수 있다. 이 상황은 3.1.2절의 예와 비슷한 경우라고 생각할 수 있는데, 이런 경우 비선점형 EDF 스케줄러와 선점형 EDF 스케줄러가 각각 어떻게 동작되는지 실험을 통해 알아보자.
의 deadline을 충족시키고, t0의 수행을 늦추므로써 실시간성 및 응답성을 만족시키고자 한다. 이에 본 논문은 (c)와 같이 선점할 수 있는 EDF 스케줄링을 제시하고자 한다.
이에 본 논문은 TinyOS의 실시간성 및 응답성을 강화하기 위하여 Priority Level Scheduler를 기반으로 선점형 EDF 스케줄러를 제안하였고 수행 중에도 우선순위를 할당할 수 있도록 개선하였다.
그러나 센서 운영체제인 TinyOS는 실시간성을 보장할 수 없다는 문제가 있다. 이에 본 논문은 선점이 가능한 EDF 스케줄러를 제안했다. 기존 TinyOS는 실시간성을 보장하지 못하기 때문에 본 논문이 제안하는 것과 비교하는 것은 무리가 있다.
가설 설정
① Tn의 deadline이 Tc의 deadline 보다 같거나 늦다.
② Tn의 deadline이 Tc의 deadline 보다 빠르다.
제안 방법
본 실험은 구현된 선점형 EDF 스케줄러가 정상적으로 동작하는 것을 확인하는 실험이다. Kmote에 프로그램을 업로드 하여 콘솔 화면에서 확인을 하였다. 또한 호스트의 콘솔 화면에 출력하기 위해 TinyOS에서 제공한 printf 라이브러리를 응용프로그램에 추가시켰으며, 데드라인이 서로 다른 4개의 태스크를 같은 시간에 포스트하여 수행시켜 동작 여부를 실험하였다.
Kmote에 프로그램을 업로드 하여 콘솔 화면에서 확인을 하였다. 또한 호스트의 콘솔 화면에 출력하기 위해 TinyOS에서 제공한 printf 라이브러리를 응용프로그램에 추가시켰으며, 데드라인이 서로 다른 4개의 태스크를 같은 시간에 포스트하여 수행시켜 동작 여부를 실험하였다. 4개의 태스크 정보는 <표 1> 과 같다.
왜냐하면 데드라인 순서대로 수행되긴 하였지만 선점이 수행되지 않는 상황이기 때문에 선점 기능에 대한 검증이 부족한 실험이었다. 이번 절의 실험은 선점 기능을 사용하는 실험으로, 선점이 발생 하는 상황은 흔하게 되지 않기 때문에, 본 실험에서는 특수한 상황을 만들어 수행한다. 특수한 상황은 3.
스케줄러는 태스크 큐에 있는 태스크들의 deadline과 현재 들어온 태스크 deadline과 비교하여 deadline이 빠른 순서로 정렬 상태가 되도록 현재 들어온 태스크를 적절한 위치에 넣는다. 즉, 스케줄러가 관리하는 FIFO큐의 태스크를 deadline이 빠른 순서로 정렬시킴으로써 EDF 스케줄링을 구현하였다. 이렇게 되면 태스크 수행순서가 FIFO 이므로 deadline이 빠른 태스크가 먼저 큐에서 나와 수행된다.
이것은 log찍는 시간과 태스크 종료 후 처리작업으로 인한 오차범위이다. 태스크의 완료된 순서는 데드라인이 빠른 순서인 T3, T1, T2, T4로 EDF 알고리즘을 충분히 수행했다. 이 과정을 도식화 하면 (그림 15)와 같다.
이번 절의 실험은 선점 기능을 사용하는 실험으로, 선점이 발생 하는 상황은 흔하게 되지 않기 때문에, 본 실험에서는 특수한 상황을 만들어 수행한다. 특수한 상황은 3.1.2 절에서 언급한 비선점일 경우의 문제가 발생하는 경우를 바탕으로 하였다. 또한, 동일한 상황 하에 비선점형 EDF 스케줄러와 비교 실험하여 선점형 EDF 스케줄러가 더 우수하다는 것을 검증하고자 한다.
대상 데이터
이것은 일반 운영체제에서 사용되는 선점 기능하고 비교하여 다소 독특한 구조를 가진다. 일단 TinyOS의 기본 스케줄러를 기반으로 하여 총 5개의 FIFO큐를 사용한다. VERYHIGH, HIGH, BASIC, LOW, VERYLOW로 총 5개의 우선순위가 있고, 각 우선순위마다 큐가 하나씩 존재한다.
데이터처리
이외에 상황에 따라 우선순위를 정적또는 동적으로 줄 수 있는 two-layer priority[9] 방식이 있다. two-layer priority는 선점형 EDF에 대한 언급을 하였지만 자세한 구현에 대한 내용은 생략되었고, TinyOS에서 기본적으로 제공하는 FIFO와 비선점형 EDF 방식을 사용하여 시뮬레이션을 통해 결과를 비교하였다. 참고 논문 [10]은 TinyOS에서 응답성을 높이기 위한 방법으로 선점적인 EDF 방식을 이용하였다.
성능/효과
4.2절의 실험만 가지고는 선점형 EDF 스케줄러가 완벽하게 동작한다는 것을 보장할 수 없다. 왜냐하면 데드라인 순서대로 수행되긴 하였지만 선점이 수행되지 않는 상황이기 때문에 선점 기능에 대한 검증이 부족한 실험이었다.
그러고 나서 중단되었던 T1을 중단 시점부터 다시 시작한다. 그 결과 4개의 태스크 중에서 모든 태스크의 데드라인을 만족함을 이 실험을 통해서 알 수 있다.
기본적으로 비선점 방식의 스케줄러를 사용함으로써 TinyOS에서는 모든 태스크들이 정해진 시간 안에 끝낼 수 있다고 보장하기 힘들다. 또한, 비선점 기반의 EDF 스케줄링은 매우 급한 태스크가 들어와도 현재 수행되는 태스크가 완료될 때까지 기다려야하기 때문에 자신의 데드라인을 넘기는 문제가 있다는 것을 예제 및 실험을 통해 확인하였다.
비선점 방식은 모든 태스크의 데드라인을 만족 시키지 못했지만, 선점 방식은 모든 태스크에서 데드라인을 만족함을 보였다. 이는 본 논문인 제안하고 있는 선점형 EDF 스케줄러가 올바르게 동작함을 보였을 뿐만 아니라 비선점형 EDF 스케줄러보다 우수함을 실험을 통해 알 수 있다.
비선점 방식은 모든 태스크의 데드라인을 만족 시키지 못했지만, 선점 방식은 모든 태스크에서 데드라인을 만족함을 보였다. 이는 본 논문인 제안하고 있는 선점형 EDF 스케줄러가 올바르게 동작함을 보였을 뿐만 아니라 비선점형 EDF 스케줄러보다 우수함을 실험을 통해 알 수 있다.
이것은 TinyOS의 기본 성질인 비선점방식을 그대로 적용하였기 때문에 실시간성을 보장하지 못할 수 있을 뿐만 아니라 평균 응답성도 커질 수 있다. 이에 본 논문은 선점방식하에 EDF 스케줄링 알고리즘을 적용하였고, 비선점방식보다 우수하다는 것을 실험을 통해서 확인하였다.
후속연구
본 논문에서 고려할 부분은 Priority Level Scheduler는 일반 OS에서 동작하는 선점과는 다르게 매우 제약적으로 동작하기 때문에 선점형 EDF 스케줄러 역시 제약적으로 선점기능을 사용하고 있다. 따라서 향후에는 제약적인 선점기능을 향상시키면서 TinyOS의 실시간성 보장을 위한 연구가 필요하다.
질의응답
핵심어
질문
논문에서 추출한 답변
센서 네트워크의 핵심은 무엇인가?
센서 노드가 외부에서 채취한 데이터를 실시간으로 사용자에게 전달하는 것은 매우 중요하다. 센서 네트워크의 핵심은 센서 노드인 하드웨어 플랫폼과 노드에 들어가는 초소형 운영체제라고 할 수 있다. UC 버클리에서 개발된 TinyOS는 센서 노드에서 동작하는 운영체제 중 가장 많이 사용되고 있다.
TinyOS는 기본적으로 어떤 방식의 스케줄러를 사용하나?
TinyOS는 Event-driven 방식이며 Component 기반의 센서 네트워크 운영체제이다. 기본적으로 비선점 방식의 스케줄러를 사용한다. 만약 급한 작업이 수행되어야 하는 시점에서 다른 태스크가 수행 중에 있다면 수행 중인 태스크가 완료할 때까지 기다려야 한다.
센서 네트워크는 무엇인가?
센서 네트워크는 빛, 소리, 온도, 움직임 같은 물리적 데이터를 센서 노드에서 감지하고 측정하여 중앙으로 전달하고 처리하는 구조를 가진 네트워크이다. 센서 네트워크는 여러 분야에서 활용할 수 있는 기술이다.
참고문헌 (11)
Ian F. Akyildiz, Weilian Su, Yogesh Sankarasub- ramaniam, Erdal Cayirci, "A Survey on Sensor Networks," IEEE Communications Magazine, pp.102-114, August, 2002.
J. Hill, R. Szewczyk, A. Woo, S. Hollar, D. Culler, and K. Pister. "System architecture directions for networked sensors," In Proc. of the 9th Intl. Conf. on Architectural Support for Programming Languages and Operating Systems (ASPLOS), pp.93-104, Cambridge, MA, Nov., 2000.
D. Gay, P. Levis, R. von Behren, M. Welsh, E. Brewer, and D. Culler. "The nesC language: A holistic approach to networked embedded systems," In proc. ACM SIGPLAN Conference on Programming Language Design and Implementation, pp.1-11, June, 2003.
Cormac Duffy, Utz Roedig, John Herbert and Cormac J. Sreenan. "Adding preemption to tinyos," In To appear in the Fourth Workshop on Embedded Networked Sensors (EmNets 2007), University College Cork, Ireland. ACM Digital Library, June, 2007.
C.L. Liu and James W. LayLand. "Scheduling Real-Time Environment," J.ACM, 20, pp.40-61, 1973.
V.Subramonian, H-M. Huang, S. Data, and C. Lu, "Priority scheduling in TinyOS - A case study," Technical Report WUCSE-2003-74, Washington University, 2002.
Tao Lei, Xiang-mo Zhao and Fei hui. "A TinyOS scheduling strategy and its implementation," Communication Software and Networks (ICCSN), 2011 IEEE 3rd International Conference on, pp.216-219, May, 2011.
P.Levis and C.Sharp. "Schedulers and Tasks," TinyOS 2.x Extension Proposal 106.
Zhi-bin Zhao, Fuxiang Gao, "Study on Preemptive Real-Time Scheduling Strategy for Wireless Sensor Networks," Journal of information processing systems 5(3), pp.135-144, September, 2009.
Liu Jianhui, "Research on TinyOS Scheduling Strategy Based on SJP," Computational Intelligence and Design (ISCID), 2010 International Symposium on, pp.144-146, Oct., 2010.
P. Levis, D. Gay, V. Handziski, J.-H. Hauer, B. Greenstein, M. Turon, J. Hui, K. Klues, C. Sharp, R. Szewczyk, J. Polastre, P. Buonadonna, L. Nachman, G. Tolle, D. Culler, and A. Wolisz. "T2: A second generation os for embedded sensor networks." Technical Report TKN-05-007, Telecommunication Networks Group, Technische Universitat Berlin, 2005.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.