TinyOS에 선점형 EDF 스케줄링 알고리즘 적용

Abstract

센서 네트워크는 빛, 소리, 온도, 움직임 같은 물리적 데이터를 센서 노드에서 감지하고 측정하여 중앙으로 전달하고 처리하는 구조를 가진 네트워크이다. 센서 네트워크는 여러 분야에서 활용할 수 있는 기술이다. 센서 노드가 외부에서 채취한 데이터를 실시간으로 사용자에게 전달하는 것은 매우 중요하다. 센서 네트워크의 핵심은 센서 노드인 하드웨어 플랫폼과 노드에 들어가는 초소형 운영체제라고 할 수 있다. UC 버클리에서 개발된 TinyOS는 센서 노드에서 동작하는 운영체제 중 가장 많이 사용되고 있다. TinyOS는 Event-driven 방식이며 Component 기반의 센서 네트워크 운영체제이다. 기본적으로 비선점 방식의 스케줄러를 사용한다. 만약 급한 작업이 수행되어야 하는 시점에서 다른 태스크가 수행 중에 있다면 수행 중인 태스크가 완료할 때까지 기다려야 한다. 이러한 특성으로 인해 TinyOS에서 실시간성을 보장하기 어렵다. 최근 연구에서 TinyOS의 빠른 반응성을 위해 Priority Level Scheduler라는 선점 기능이 제안되었다. 이것은 제한적으로 5개의 우선순위를 만들어 높은 우선순위가 낮은 우선순위를 선점할 수 있게 한다. 여기서 본 논문은 Priority Level Scheduler를 이용하여 TinyOS의 실시간성을 보장하고자 한다. Priority Level Scheduler에 실시간 스케줄러인 EDF(Earliest Deadline First)를 적용한 선점형 EDF 스케줄링 방식을 제안하고자 한다.; A sensor network is a special network architecture that makes physical data sensed by sensor nodes transmit to a host PC and manages the data at the host PC. The sensor network is a technology that can apply to many parts of fields. It is very important to transmit the data sensed by sensor nodes to a user at a real time. The core of the sensor network is a sensor node and a mini operating system that works in the node. TinyOS developed by UC Berkeley is a sensor network operating system that used many parts of fields. It is an event-driven and a component-based operating system. Basically, it uses a 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 a real-time requirement in TinyOS. According to a 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 a method using Priority Level Scheduler to guarantee a real-time requirement in TinyOS. This paper proposes Preemptive EDF Scheduler that applies EDF(Earliest Deadline First) algorithm using Priority Level Scheduler.