工學碩士學位請求論文 인터럽트지연시간의감소를통한 BrickOS 의실시간성강화에관한연구 A Study on Enhancement of BrickOS s Real ealtime Cha hara racteristic by Reducing Interrupt Latency 2007 年 2 月 仁荷大學校大學院 情報通信工學科 河正大
工學碩士學位論文 인터럽트지연시간의감소를통한 BrickOS 의실시간성강화에관한연구 A Study on Enhancement of BrickOS s Realtime Characteristic by Reducing Interrupt Latency 2007 年 2 月 指導敎授吳範渙 이論文을碩士學位論文으로提出함 仁荷大學校大學院 情報通信工學科 河正大
이論文을河正大의碩士學位論文으로認定함. 2007 年 2 月日 主審 副審 委員 印 印 印
요 약 임베디드시스템인 RCX에탑재된 BrickOS(Brick Operating System) 는실시간태스크수행중두가지의지연요소를가진다. 첫번째지연은실시간태스크가생성되어실제수행에들어가는과정중에발생한다. 이는실시간태스크는실행할준비가되어있지만라운드로빈방식에의해다음타임퀀텀까지기다려야하는지연이다. 두번째지연은스케줄링알고리즘에의해발생한다. 실시간태스크가수행중일때호출되는스케줄러는특별한경우를제외하고는의미가없다. 때문에실시간태스크의수행중호출되는스케줄러는그자체로지연시간이된다. 이에본논문에서는위의두지연을해소하기위해스케줄러의호출방식에변화를주었다. 매일정한타임간격마다스케줄러를호출하는대신타이머인터럽트가발생할때마다스케줄러의호출여부를결정한다. 이를통해첫번째지연을감소시킬수있다. 그리고두번째지연을해결하기위해매순간마다실시간태스크의생성여부와실행여부를체크하도록하였다. 이는스케줄러의필요성을판별하기위한방법으로이를통해스케줄러의호출을제한함으로서두번째지연을감소시킬수있다. 본논문에서는위에서제안하는알고리즘을 BrickOS의커널분석과수정, 추가등을통해구현하는과정을보인다. 그리고비교실험을통해제안된알고리즘에서동작하는실시간태스크의수행에약 8% 의성능향상이있음을보인다. i
Abstract BrickOS(Brick Operating System) on top of RCX system has two latency factors against real-time characteristic. The first one happens between the real-time task s creating and beginning. When the operating system tries to start real-time job it couldn t start instantly. Because it has to wait until next time tick is over. So the latency can happen. Next lantency happens by BrickOS s scheduling algorithm. BrickOS tries to call the scheduler every time tick. But it is useless to call the scheduler while the real-time task is running. The reason is that it is impossible for any normal task to take CPU when the real-time task is running. Therefore, in that case calling the scheduler can be latency. To solve this latency problem, this paper suggests new scheduler calling method. Timer interrupt handler checks if new real-time task is made or not. If it is, they call the scheduler. This method calls the scheduler faster than original calling way. Timer handler also checks if there is a running real-time task. And it has any actions if there is. This means that there is no scheduler calling if any real-time task is running. So we can save more time to process the realtime task. This paper shows the process of implementation this algorithm in BrickOS through the kernel analysis and modification. And it also shows that the real-time task in the implemented system is 8% faster than the origin one by experiments. ii
목 차 제 1 장서론...1 제 2 장관련연구...3 2.1 MindStorm 및 RCX의소개... 3 2.2 BrickOS kernel... 4 2.2.1 Kernel의시작... 4 2.2.2 kernel의동작구조... 5 2.2.2 메모리관리... 5 2.2.3 Networking... 7 2.3 실시간스케줄링... 7 2.3.1 실시간스케줄링알고리즘의개념... 7 2.3.2 정적우선순위스케줄링... 8 2.3.3 동적우선순위스케줄링... 10 제 3 장 BrickOS 스케줄링의문제점과개선방안... 12 3.1 BrickOS의스케줄링기법... 12 3.1.1 라운드로빈스케줄링기법... 12 3.1.2 우선순위기반의선점형스케쥴링... 14 3.2 기존스케줄링의문제점... 19 3.2.1 태스크생성부터선점사이의지연... 19 3.2.2 불필요한스케줄러의호출에따른지연... 20 3.3 개선된실시간스케줄링... 22 3.3.1 개선된실시간스케줄링알고리즘... 22 3.3.2 개선된실시간스케줄러의구현... 25 제 4 장실험및결과... 29 4.1 실험환경... 29 4.2 실험및결과... 30 제 5 장결론... 34 iii
제 1 장서론 오늘날다양한임베디드시스템에서실시간처리기능에대한요구가날로높아지고있다. 임베디드시스템인 RCX의기본펌웨어를대체하는 BrickOS(Brick Operating System) 역시실시간서비스를제공하기위해우선순위기반의라운드로빈방식의스케줄링방식을채택하고있다 [1,2]. 라운드로빈스케줄링방식은태스크의기아상태 (starvation) 을해소해주지만완료시간에대한고려를전혀하지않기때문에태스크의작업완료에있어최선의노력을해야하는실시간시스템에는적합하지않은알고리즘이다. 실시간태스크를수행하는데있어 BrickOS의스케줄링방식에는두가지의지연요소가생긴다. 첫번째지연은실시간태스크의생성에서실제수행에들어가는과정중에발생한다. 실시간태스크가생성되어실행할준비를끝마친상황에서태스크선점을하기위해다음스케줄러의호출까지기다려야한다. 이는최대타임간격만큼실시간태스크의수행이지연될수있다는것을의미한다. 매일정한간격으로호출되는스케줄러역시그자체로지연이될수있다. 실시간태스크는항상최우선순위를가지고수행이된다. 따라서수행중인실시간태스크가다른일반태스크에의해선점이되거나스위칭이되는경우는실제스케줄러의호출횟수만큼빈번하게일어나지않는다. 따라서기존알고리즘에의해호출되는스케줄러는특별한경우를제외하고는의미가없기때문에주기적으로호출되는스케줄러자체가태스크수행의지연을의미한다. 이에본논문에서는위의두지연을해소하기위해스케줄러의호출방식에 변화를주었다. 매일정한타임간격마다스케줄러를호출하는대신타이머 1
인터럽트가발생할때마다스케줄러의호출여부를결정하도록하였다. 이는태스크의시작시간을앞당길수있기때문에첫번째지연을감소시킬수있다. 두번째지연을해소하기위해서매타이머인터럽트마다실시간태스크의생성여부와실행여부를체크하도록하였다. 이는스케줄러의필요성을판별하기위한방법으로이를통해스케줄러의호출을제한함으로써두번째지연을감소시킬수가있다. 본논문은위에서제안하는알고리즘이 BrickOS의커널분석과수정, 추가등을통해구현되는과정을보이고실험결과를통해본논문에서제안한실시간시스템이기존의시스템에비해향상된실시간태스크수행능력을가지고있다는것을보여준다. 본논문의구성은다음과같다. 제2장에서는관련연구들을소개한다. 우선 BrickOS의커널에대해소개하고, 그다음으로현재연구되고있는실시간스케줄링에대해알아본다. 제3장에서는 BrickOS의스케줄링에서발생하는지연과그에따른문제점을알아보고이를해결하는대안을제시, 구현한다. 제4장에서는실험을통해제안된알고리즘의성능향상결과를보이며, 마지막제5장에서는결론및향후연구방향에대해설명하고끝을맺는다. 2
제 2 장관련연구 BrickOS의커널에대해알아보기전에실제구현에사용되었던통합개발킷인 MindStorm과그중 BrickOS를탑재할수있는임베디드시스템인 RCX 에대해간략하게알아본다. 2.1 MindStorm 및 RCX 의소개 Lego MindStorm Kit은여러가지레고 (Lego) 블록들과바퀴, 기어, 모터, 터치 (Touch) 센서, 빛센서, 적외선통신이가능한컴퓨터블록 (RCX) 을포함하고있는통합개발킷이다. RCX에는프로그래밍이가능하여, 사고 ( 思考 ) 가가능하다. 즉, 여러가지레고블럭들을컴퓨터블록 (RCX) 과연결하고적당한프로그래밍만해준다면, 로봇이된다 [1,2]. MindStorm은기본적으로 window 환경에서동작하는로봇개발환경을제공하며이는 GUI형식의프로그래밍으로, 아주쉽고, 간단하며, 신속하게 RCX를제어할수있는프로그래밍을할수있도록되어있다 [3]. 그렇지만 MindStorm에서제공하는프로그래밍환경에선가장기본적인제어만제공하기때문에 RCX를보다세밀하고자유롭게활용할수없다. 모터의세밀한조정및빛센서의세밀한감지도불가능하며, RCX의적외선통신도제어가불가능하다. 따라서, RCX를좀더완벽하게활용할수있도록, 많은사람들이 RCX 개발환경을개발하기시작했다. 현재까지개발된 RCX 개발툴로는프리소프트웨어 (Free Software) 인 NQC(Not Quite C) 나 C언어를통해 RCX를개발할수있는 RCXCC와 legos, 그리고 brickos가있다.[3] NQC나 RCXCC는 RCX에들어있는순정펌웨어 (Firmware) 를바탕으로동작하기때문에, 순정펌웨어의능력을넘는제어는불가능하다. 이에비해 legos와그차기버전인 brickos는운영체제로, RCX 펌웨어를교체한다. 따라서운영시스템자체가변경되고, 개발환경 (gcc) 이나 3
동작환경이모두바뀌어, RCX 는개선된성능을보인다 [4]. 또한, 자체통신 프로토콜을사용하여적외선통신을자유롭게구현할수있어, RCX 간의통신 도가능해진다. 본연구에사용된하드웨어인 RCX는 Hitachi H8/3292 마이크로컨트롤러칩이 RCX제어의대부분을담당하는데, 이칩에내장되어있는구성요소는크게 H8/300 CPU와 MEMORY, Input/Output으로나눌수있다. H8/300 CPU 는 10Mhz의 system clock으로동작하며 8bit와 16bit 연산을지원한다. RCX 에는총 8개의 16bit레지스터 (R0,R1, R7) 와 16bit 프로그램카운트레지스터 (PC), 8 bit condition code 레지스터 (CCR) 를가지고있다.[2] RCX에사용되는메모리는마이크로컨트롤러칩에내장되어있는 16Kbyte mask programmable ROM과 512byte RAM 그리고 128byte의온칩레지스터필드가있으며이와별도로 32Kbyte의외부 RAM이있다. 그외로 16bit 타이머와 2개의 8bit 타이머채널, A/D 컨버터와 I/O 포트들이있다. 2.2 BrickOS kernel 2.2.1 Kernel 의시작 Kernel은 ROM에의해 kmain 함수가호출되면서시작한다. 이함수는싱글태스킹이나멀티태스킹모드로들어가기전 kernel의초기화를진행한다. 만약 task manager가 kernel에포함되어있지않다면오직싱글태스크모드로만작동하며동적프로그램로딩은불가능하게된다. 이논문에서는 task manager가동작하며멀티태스킹모드와동적프로그램로딩을지원하도록하였다. kernel이초기화되는동안시작되는태스크는 3개이다. 첫번째는아 4
무런동작도하지않는 idle 태스크이며나머지두개는동적프로그램로딩을위한 packet_consumer 태스크와 key_handler 태스크이다. packet_consumer 태스크는 IR-port의움직임을제어하는태스크로서패킷의송수신에관한일을한다. 그리고 key_handler 태스크는 RCX brick의버튼에대한제어권을가진태스크로버튼의움직임에대한행동을결정한다. 이세가지태스크가생성된후 task manager가실행되며태스크스위칭을시작한다. 2.2.2 kernel 의동작구조 kernel은가장먼저메모리를초기화하며, 그외의필요한장치들을초기화한다. 시스템타임을초기화힐때는 16비트타이머에 1ms 마다 timer interrupt이발생하도록하고, ROM 은 timer interrupt가발생했을경우 ocia_vector가가리키는 systime_handler 함수를호출한다. systime_handler 함수는다양한서브시스템들의핸들러를차례로폴링하면서실제적으로 BrickOS를조종한다. 그리고이러한시스템은 BrickOS가각각의장치환경들과의통신수단으로인터럽트를쓰지않고폴링방식을사용한다는것을말한다. systime_handler는각각의핸들러를호출하는일이외에도일정한타임퀀텀이지나면 tm_switcher라는스케줄러를호출하는일을통해멀티태스킹을가능하게한다. 2.2.2 메모리관리 BrickOS 는메모리관리에있어순차적인메모리할당방식을사용하고있다. 페이징이나세그멘테이션과같은고급메모리관리기법은하드웨어에서제공 5
해주지않고있다. 만약제공된다고해도매우부족한메모리공간때문에고 급메모리관리방식은오히려더많은오버헤드를발생시킨다 [5]. 메모리는커널부분과유저부분으로나누어저있으며커널코드와 static 커널데이터는 0x8000부터 mm_start 주소사이에위치한다. 메모리관리자는 mm_start 부터 0xFFFF까지의모든메모리를관리한다. 기본적인메모리구조는 [ 그림 2-1] 과같다. [ 그림 2-1] 메모리구조 6
2.2.3 Networking BrickOS는 usb IR tower를이용하여외부와통신을한다. 통신프로토콜로 LNP(LegOS Networking Protocol)[4] 를사용하며 Broadcast 성격의 Integrity 패킷과특정주소에만전달하는 Addressing 패킷으로나눌수있다. 패킷을수신하게되면, Receive Shift Register로수신데이터가도착하게되고, 수신된데이터가이상없다면, Receive Data Register로수신데이터가옮겨진다. Receive Data Register로수신데이터가옮겨지면, RDR-FULL Flag의 Flip으로인하여인터럽트처리기 (ISR) 가발생해, Receive-end interrupt(rxi) vector인 rx_handler를호출하게된다. rx_handler는 collision, checksum등을계산하고, 패킷의종류에따라, Integrity 또는 Addressing Handler를호출하여, User에게수신된데이터를전달한다. 패킷의송신은버퍼로송신할패킷을복사한후, Serial Control Register를변경하여, Send interrupt vector인 tx_handler를호출하여, 버퍼의내용을전송하게된다. BrickOS는자신의패킷이아닐경우에는버리도록되어있으므로, 다른 RCX로부터의패킷중계 (Routing) 가불가능하다. 2.3 실시간스케줄링 2.3.1 실시간스케줄링알고리즘의개념 실시간스케줄링알고리즘의정의는어떠한자극에대해처리할수있는시간이예측가능하고또한완료시간이지켜져야하는일에대해서완료시간에대한보장을해줄수있는스케줄링알고리즘을의미한다. 여기서중요한사항은 예측가능 해야된다는것과 완료시간에대한보장 이가능해야된 7
다는것인데일반적인리눅스나윈도우즈같은범용 OS 는이러한예측가능 성과완료시간에대한보장을해주지못하기때문에실시간 OS 로써적합하 지않다 [6]. 여기에는 soft real-time과 hard real-time으로다시분류될수있는여지가있므며, 대부분의 real-time class process들은상용시스템에서완벽히 hard real-time을지원해주고있지는못하다 [7]. 완전한 hard real-time보다는 soft real-time을지원한다는말은반드시어떤주어진시간안에는마치지못하더라도그연산의결과가받아들일만하다고여긴다는말이다. 이논문에서제안하는알고리즘은지연시간의감소를통한 best effort service를제공한다. 즉 hard real-time 보다는 soft real-time의요구를만족시킨다. 또다른실시간스케줄링알고리즘의분류방법으로정적우선순위스케줄링 (Static Priority Scheduling) 알고리즘과동적우선순위스케줄링 (Dynamic Priority Scheduling) 알고리즘으로나누는방법이있다 [8]. 정적우선순위스케줄링알고리즘은우선순위가한번정해지면변하지않는방식이며, 동적우선순위스케줄링알고리즘은상황에따라서우선순위가변할수가있다. 동적우선순위스케줄링알고리즘은스케줄링당시의상황에따라매번우선순위를계산하여야하기때문에구현이복잡하고정적스케줄링알고리즘에비해많은시간을요구한다는단점이있으나실제모든태스크의실시간제약을만족시키는데에있어서는정적스케줄링알고리즘보다보다효율적이다. 2.3.2 정적우선순위스케줄링 정적우선순위 (Static Priority) 는태스크가생성될때, 최초로정해지게되고, 8
태스크수행중에는바뀌는경우가생기지않는다. 보통은컴파일시에고정 된값으로주게된다. 정적우선순위방식을사용하는스케줄링에는 Rate Monotonic (RM) 과 DeadLine Monotonic (DM) 이있다. Rate Monotonic (RM) Rate Monotonic 방식은각각의태스크중생성주기가가장짧은태스크가가장높은우선순위를가지는스케줄링방식이다. [ 그림 2-1] 은 RM 스케줄링방식에대하여설명한것으로그림의세개의태스크는모두일정한간격으로생성되고있다. 그리고가장빠른생성주기를가지고있는태스크 1은스케줄링알고리즘에따라선점의최우선권을가지며태스크 2와태스크 3은그뒤를따르고있다. [ 그림 2-1] 의마지막라인은이세개의태스크들이서로선점되는과정을보여주며 violation of deadline 지점에서태스크 3의수행시간이데드라인을넘어가는것을알수있다. [ 그림 2-1] RM 으로스케줄링한예 9
Deadline Monotonic (DM) Deadline Monotonic 스케줄링은말그대로데드라인이가장짧은태스크에게가장높은우선순위를준다. [ 그림 2-3] 을보면태스크 2가가장짧은데드라인을가지고있다는것을알수있다. 그리고정적스케줄링방식이기때문에태스크의종료까지이순위는변하지않는다. 따라서태스크 2는다른태스크보다우선해서실행된다. [ 그림 2-3] DM 으로스케줄링한예 2.3.3 동적우선순위스케줄링 동적우선순위 (Dynamic Priority) 는수행중에언제든지태스크의우선순위 를바꾸는것이가능한경우를말한다. 동적우선순위방식을사용하는스케 10
줄링에는 Earliest DeadLine First (EDF) 와 Time Driven Scheduler (TDS), Least Laxity First (LLF), Shortest Remaining Time (SRT) 등이있다. Earlist Deadline First (EDF) DM(Deadline monotonic) 스케줄링방식과마찬가지로가장짧은데드라인을가지고있는태스크에가장높은우선순위를준다. 그러나동적으로할당되기때문에이우선순위는시간의경과에따라바뀔수있다. [ 그림 2-4] 에서보면처음에는가장짧은데드라인을가지고있는태스크 2가가장높은우선순위를가지고선점이되는것을볼수있으나태스크 3의데드라인에가까워질수록태스크 3에게우선권을뺏기고있는것을알수있다. 따라서모든태스크의실시간요구를만족시키는데적합한스케줄링방식이라는것을알수있다. [ 그림 2-4] 에서도지금까지와는다르게태스크 3의데드라인역시지켜짐을볼수있다. [ 그림 2-4] EDF 로스케줄링한예 11
제 3 장 BrickOS 스케줄링의문제점과개선방안 3.1 BrickOS 의스케줄링기법 brickos는표면적으로실시간오퍼레이팅시스템임을표방한다. 그이유로 brickos가라운드로빈스케줄링방식과우선순위기반의선점형스케줄링방식을혼합하여사용한다는것을들수있다. 3.1.1 라운드로빈스케줄링기법 라운드로빈스케줄링은각태스크에게 CPU 실행시간을골고루나눠준다. 각태스크는라운드로빈이라는이름이뜻하는것처럼지정된시분할시간만큼번갈아가면서수행된다 [9]. 런타임카운터는클럭틱 (clock tick) 마다각태스크의남아있는수행시간을점검한다. 태스크가지정된시분할을모두소모하면카운터를지운뒤태스크를라운드로빈사이클의마지막에둔다. 새로추가된같은우선순위의태스크역시라운드로빈사이클의마지막에놓여진다. 이때태스크의런타임카운터는 0으로초기화된다. 아래의 [ 그림3-1] 은라운드로빈스케줄링방식을그림으로표현하였다. [ 그림 3-1] 라운드로빈스케줄링기법 12
BrickOS 에서의라운드로빈스케쥴링 [ 그림 3-2] 는 task_switch_handler 함수의일부분으로라운드로빈 스케줄링에직접적인영향을미치는부분이다. [ 그림 3-2] task_switch_handler 함수 task_switch_handler 함수는타이머인터럽트가발생할때마다호출되는함수이다. RCX에서타이머인터럽트는매 1ms마다발생하기때문에빠른수행을위해어셈블리어로작성되었으며매수행시마다각각의외부장치들의핸들러를호출하여동작여부를결정한다. 이러한것으로미루어볼때 BrickOS는외부장치와의통신수단으로인터럽트방식대신폴링 13
방식을사용한다는것을알수있다. [ 그림 3-2] 는그중라운드로빈스케줄링을하는부분으로매호출시마다 tm_current_slice값을감소시킨후 0이되었을때 tm_switcher_vector가가리키는곳으로 jump하는것을볼수있다. tm_switcher_vector에는현재동작하고있는스케줄러의주소가담겨있으므로즉일정한시간이지나면스케줄러를호출시킨다. 현재 brickos의 default tick값은 20으로되어있기때문에매 20msec마다스케줄러의호출이일어난다. 3.1.2 우선순위기반의선점형스케쥴링 [ 그림 3-3] 과같이우선순위기반의선점형스케줄링알고리즘을사용할경우, 임의의시점에수행중인태스크는항상시스템에서실행가능상태에있는태스크중우선순위가가장높은태스크이다 [9,10]. 우선순위기반의선점형스케줄러는각태스크별로우선순위를매긴후가장높은우선순위를가진태스크를수행시킨다. 현재실행중인태스크보다우선순위가높은태스크가실행가능상태가되면커널은즉시현재태스크의문맥을 TCB에저장하고우선순위가더높은태스크로실행권을넘긴다. [ 그림 3-3] 우선순위기반의선점형스케줄링 14
BrickOS 에서의우선순위기반의선점형스케줄링 BrickOS 에서는 [ 그림 3-4] 에서보듯이 3 가지의서로다른우선순위를제공 하고있다. [ 그림 3-4] brickos 에서제공하는우선순위 그리고각태스크의상태를아래와같이 4 가지 [10] 로분리해놓고있다. task Running task 가실행되고있는상태를의미한다. 해당태스크는 Round Robin 스케줄링이아닌이상언제든지자신보다우선순위가높은태스크가없다면 수행될수있다. 라운드로빈스케줄링에서는차례대로수행된다. task Wating 해당태스크가어떠한이벤트를기다리면서대기하는상태이다. 이러한 이벤트에는 signal, irq, io request, semaphore 자원등이있을수있다. task Sleeping 해당태스크는 IDLE 상태이나언제든지실행할준비가되어있다. task Zombie 해당태스크는수행이종료되어있는상태이다. 그러나메모리스택이아직 반환되지않았기때문에태스크정보가메모리에남아있다. 15
BrickOS 는 [ 그림 3-4] 의우선순위정보와해당태스크들의상태에대한 정보를바탕으로선점이가능한스케줄링서비스를제공해주고있다 [ 그림 3-5] 는 brickos 의스케줄링알고리즘을보여준다. [ 그림 3-5] brickos 의스케줄링알고리즘 16
스케줄러가호출될때현재수행중인태스크의스택포인터 (old_sp) 를인자로가지고온다 [5]. 이는태스크의스택에실제태스크의수행코드의시작위치가저장되어있기때문이다. [ 그림 3-6] 을보면태스크의종료위치와시작위치가태스크스택의맨상단에위치해있음을알수있다. 스케줄러실행중현재태스크를수행시킬필요가있을때인자로가져온스택포인터를활용한다. Address of interrupted task s next instruction ROM callee saved data &rom_ocia_return &systime_tm_return saved context of current task, R1...R5 [ 그림 3-6] SLEEPING 태스크의스택구조 BrickOS는우선순위기반의선점형서비스를지향하고있기때문에스케줄링시가장높은우선순위를찾아야한다. BrickOS는이를위해두개의리스트를이용하여스케줄링을하고있다. 그림 [3-7] 을보면각각의우선순위노드에태스크노드들이달려있는것을볼수있다. 그리고가장높은우선순위노드는항상 P_HEAD로지정되어있다. 스케줄러가호출되면가장먼저 P_HEAD 를찾는다. 이는다음수행할태스크를찾을때항상가장높은우선순위를가지는노드에서부터시작한다는것을의미한다. 또한그우선순위노드의태스크들이모두종료되지않으면다음우선순위의태스크는실행될수없다. 예를들어그림 [3-7] 에서가장높은우선순위인 20에달려있 17
는 3개의태스크들의상태가모두 task_waiting 이거나 task_jombie가아니면다음우선순위인 10과 1의태스크들은실행되지않는다. 더불어매 20mec마다스케줄러의호출이일어나는라운드로빈방식이기때문에새로운상위우선순위의태스크가생성되면스케줄러호출시태스크스위칭, 즉태스크선점이일어나게된다. 이를종합해볼때 BrickOS는우선순위기반의선점형서비스를지원한다. [ 그림 3-8] 은이를그림으로나타내고있다. [ 그림 3-7] 우선순위리스트와태스크리스트의관계 [ 그림 3-8] 선점형스케줄링과라운드로빈스케줄링의사용 18
3.2 기존스케줄링의문제점 3.2.1 태스크생성부터선점사이의지연 실시간서비스가필요한태스크는수행중의불필요한시간의지연을최소화해야한다 [11,12]. BrickOS는태스크간에우선순위에의거하여선점을허용하지만즉각적인태스크의교환을지원하지는않는다. 따라서라운드로빈스케쥴링방식을사용하고있는 BrickOS는선점을유도할다음스케쥴러의호출까지지연을생성시킬수있다. [ 그림 3-9] 에서보듯이태스크1의수행중실시간태스크인태스크2가실행큐에들어왔을때실제수행까지지연이생긴다. 즉실시간서비스를원하는태스크가실행큐에들어왔을때다음스케쥴러호출까지최대시분할간격만큼의불필요한시간을소모하게된다. [ 그림 3-9] 태스크생성시발생하는지연시간 19
3.2.2 불필요한스케줄러의호출에따른지연 BrickOS의스케쥴러에서발생시키는또다른지연으로스케줄러호출자체를들수있다. 우선순위기반의선점형알고리즘은해당우선순위목록에수행될태스크가존재하면더높은우선순위를가지는태스크가우선순위리스트에새로이추가되는경우와해당우선순위리스트에수행중인태스크가모두제거되거나 WAITING상태에빠지지않는한하위우선순위목록에있는태스크를수행시키지않는다 [5]. 이는만약가장높은우선순위리스트에태스크가하나만존재하면이후반복되는스케줄러가그태스크가종료할때까지계속하여현재수행중인태스크를선택한다는말이된다. 따라서하나의실시간태스크가가장최상위우선순위를가질경우에스케줄러는다른태스크를실행시키지않는다. 결과적으로최우선순위를가진실시간태스크가있을때스케줄러는호출할때마다실시간태스크를선택한다. 그러므로실시간태스크가수행중에는호출되는스케쥴러의필요성은상실되게된다. 따라서불필요한스케줄러의호출을제한할경우 [ 그림 3-10] 에서보듯이전체태스크수행시간에서태스크교환에따른부가적인동작시간과스케줄러자체의수행시간만큼을줄일수가있다. [ 그림 3-11] 의윗그림은일반적인태스크수행시중간중간수행되는스케줄러를보여주고있다. [ 그림 3-11] 의아래그림은태스크수행시스케줄러의호출을제한한모습이다. 그림에서보듯이지속적인태스크수행시스케줄러의호출을제한하면태스크수행시간의지속적인감소효과를낼수가있다. 그러나이처럼스케줄러의호출을제한하면여러가지문제점을야기시키게된다 [13,14]. 따라서이러한문제점을보완하면서수행속도를향상시키는방법이필요하다. 이는다음장에서다루도록한다 20
[ 그림 3-10] 스케쥴러호출시소요시간 [ 그림 3-11] 태스크수행시간비교 21
3.3 개선된실시간스케줄링 3.3.1 개선된실시간스케줄링알고리즘 전장에서언급한문제점들은일정한타이머틱을두고스케줄러를호출하는라운드로빈스케줄러이기에발생되는문제이다. 라운드로빈방식은모든프로세스에게고른 CPU 시간을주기때문에프로세스의기아현상을해결하고동시에여러일을처리하기에는효율적이나일의중요도에따라작업이할당되야하는실시간시스템에는부적합하다. BrickOS는이를보완하기위해우선순위에따른선점형서비스를제공하였으나 3.2절에서언급했던것과같이몇가지미흡한점이있다. 따라서이를해결하기위해서는라운드로빈방식을포기하여야하나실시간태스크를제외한일반태스크의스케줄링을위해서는라운드로빈방식이필요하다. 그러므로기존의스케줄러와새로설계될실시간스케줄러는서로공존하면서필요에따라번갈아호출되어야한다. 이는이전에연구가되었던이중실시간스케줄링방식 [12] 과기본적인컨셉은같지만스케줄링호출에있어 BrickOS의 kernel에맞게변형이되었다. [ 그림 3-12] 는새로제안하는알고리즘을위해커널상에서수정되어야하는타이머인터럽트핸들러와새로운실시간스케줄러의동작과정을보여주고있다. 매 20sec마다스케줄러를호출하는기존의방식과는달리매 1ms마다호출되는타이머인터럽트핸들러에서스케줄러의호출여부를매번판단한다. 이때호출여부의판단시간을최대한으로줄이기위해단순히플래그의세팅여부에따라이를판단하도록하였다. 새로운실시간태스크가생성되면다음타임틱까지기다리지않고즉시스케줄러를호출한다. [ 그림 3-12] 에서보듯이새로이생성된실시간태스크가있으면기존의스케줄러호출 22
시스템을정지시킨다. 실시간태스크가수행중일때는일반태스크의수행이필요가없기때문이다. 그런다음실시간스케줄러를호출한뒤태스크가종료할때까지실시간스케줄러를호출하지않는다. 이를통해새로운실시간태스크가생성시생기는지연과불필요한스케줄러의호출에의해야기되는지연을줄일수있다. [ 그림 3-12] 타이머인터럽트핸들러와실시간스케줄러의동작과정 개선된실시간스케줄링알고리즘에는실시간태스크를정지시키고스케줄링을해야할예외상황이있는데 [ 그림 3-12] 에나와있듯이크게 3가지로나눌수가있다. 첫번째는실시간태스크의수행중또다른실시간태스크가들어왔을때두실시간태스크간의중요성여부를판단하기위해서다. 그러나이논문에서는실시간태스크수행중발생하는지연시간을줄이는것에중점을두고있으며실시간태스크간에우선순위에는차이를주지않기때문에실시간태스크간의스케줄링은고려하지않았다. 따라서새로운실시간태스크는단순히실시간태스크의실행큐에가장뒤에위치하도록하였다. 두번째예외사항은실시간태스크를생성하는데 23
필요한일반태스크의수행이요구될때이다. 현재 BrickOS에서는실시간태스크수행중패킷송수신작업은불가능하다. 그러나어떤실시간서비스를요구하는패킷이전송되었거나전송될필요가있을때이를처리해주는작업이필요하다. 마지막은실시간태스크가어떠한이벤트를기다리고있을상황이다. 이때는이벤트의발생까지자원의효율성을위해일반태스크를실행하는것이바람직하다. 따라서이벤트가일어나기전까지기존의스케줄링방식으로복귀한다. [ 그림 3-13] 은이러한모든상황을고려한최종스케줄링알고리즘을순서도로보여준다. [ 그림 3-13] 개선된실시간스케줄링알고리즘에대한순서도 24
3.3.2 개선된실시간스케줄러의구현 위에서제시한알고리즘을구현하기위해서는크게타이머인터럽트핸들러 와태스크생성함수의수정그리고실시간스케줄러함수가필요하다. 타이머인터럽트핸들러 [ 그림 3-14] 는수정된타이머인터럽트핸들러의코드의일부로서타이머인터럽트가발생할때스케줄러의호출을담당하는부분이다. 실시간태스크의생성여부와현재수행중인실시간태스크의존재여부를알기위해 f_new_rtask, f_run_rtask 두개의플래그가사용되었다. 새로운실시간태스크가생성되면크리티컬섹션을체크한뒤실시간스케줄러를호출한다. 만약새로운실시간태스크가생성되지않았지만현재수행중인실시간태스크가존재하면스케줄러를호출하지않는다. 만약위의조건에모두만족되지않으면기존의스케줄링알고리즘에따라태스크의동작여부가결정된다. [ 그림 3-14] 의코드에대한설명은다음과같다. A : 새로운실시간태스크의생성여부를판별, 만약새로이생성된실시간태스크가있으면실시간스케줄러의호출을위해크리티컬섹션을체크한다. 크리티컬섹션체크에실패하면다음인터럽트발생때다시시도한다. 크리티컬섹션체크에성공하면실시간스케줄러의호출을위해 rt_switch로분기한다. B : rt_switcher_vector 값으로분기, 즉실시간스케줄러함수로분기한다. C : 현재수행중인실시간태스크가있는지를확인한다. 있을경우스케줄러의 호출을제한한다. D : 기존의스케줄링알고리즘에따라동작한다. 25
[ 그림 3-14] 수정된타이머인터럽트핸들러함수 26
수정된태스크생성함수 ( new_execi() execi() ) 기존의 BrickOS에서 execi() 함수는메모리할당과태스크구조체생성등태스크생성에필요한일반적인작업을한뒤새로생성한태스크를할당받은우선순위에따라실행리스트 (RUN QUEUE) 에삽입해주는작업을했다. 수정된생성함수는실행리스트에삽입하기전까지는전과동일한작업을한다. 그러나기존에있는실행리스트와는별도로있는실시간실행리스트에새로생성된태스크를삽입한뒤 f_new_rtask를세팅하여타이머인터럽트핸들러에이를알린다. 만일실행리스트에다른실시간태스크가존재하면새로운태스크는기존의태스크리스트의가장뒤에붙는다. [ 그림 3-15] 는 new_execi() 의코드중이에관련된부분을보여준다. [ 그림 3-15] 수정된 execi() 함수 27
실시간스케줄러함수 (realtime realtime_tm_scheduler) 현재실행중인실시간태스크의상태를확인한후다음실행할태스크를찾는역할을한다. 실시간태스크의스케줄링만을관할하기때문에실시간태스크가없을시에는호출되지않는다. 실시간태스크간의우선순위를두지않았기때문에단순히다음실시간태스크로의전환만이주된임무이다. 전환이일어나는상황은새로운실시간태스크의생성에관련한일반태스크의작업이필요할때와현재수행중이실시간태스크가새로운이벤트를위해대기하고있을때이다. 실시간태스크간에도우선순위를두어작업의경중을조절할수있지만본논문에서지향하는지연시간감소와큰관련이없기때문에차후에구현하도록한다. [ 그림 3-16] 은실시간스케줄러함수의코드중중요부분을보여준다. [ 그림 3-16] 실시간스케줄러함수 28
제 4 장실험및결과 4장에서는본논문에서구현한실시간시스템을대상으로, 실시간태스크를생성하고이를처리하는과정에대한실험및결과를보여준다. 또한기존의스케줄링방식과비교하여본논문에서제안한실시간스케줄링방식의성능을평가한다. 4.1 실험환경 본논문에서제안한실시간시스템은리눅스커널 2.6.8버전의데비안 리눅스 시스템에서 h8300-hitachi-hms-gcc 2.95.2 버전의 크로스 컴파일러를이용하여구현하였다. host 컴퓨터의시스템사양은 Pentium III 800MHz의 PC를 사용하였고, firmdl3와 dll 프로그램을 업로드용으로 사용하였다. 실험데이터를판별하기위해 RCX의외부출력장치중하나인 lcd를고려하였으나표현가능한숫자가 4자리를넘지못하기때문에정상적인결과데이터출력이불가능하였다. 이에호스트컴퓨터와의통신을통해결과데이터를 host 컴퓨터에서확인하는방법을채택하였다. 이를위해 lnphost 프로그램을사용하였으며 lnphost[15] 는 host 컴퓨터가받은패킷중 lnp 프로토콜을사용하는모든데이터를화면에출력하는프로그램이다. 본논문에서제한하는실시간시스템의성능향상정도를측정하기위해태스크의수행속도를측정하여야했다. 그리고이를위해시스템에서제공하는 get_system_up_time 함수를사용하였다. get_system_up_time 함수는현재의시스템타임값인 sys_time값을반환하는함수이다. 29
4.2 실험및결과 실험은총 3가지로분류하여시행되었다. 첫번째는단일실시간태스크의생성부터시행까지의과정중발생하는지연을줄이는알고리즘의성능을평가하기위한실험이며, 두번째는실시간태스크수행시불필요한스케줄러의호출을막아태스크수행속도의향상을도모하는알고리즘을평가하는실험이다. 3번째실험은위의두가지알고리즘을모두적용시켰을시즉, 본논문에서제안한실시간시스템을사용했을시단일실시간태스크의수행속도향상정도를측정하였다. 모든실험은하나의단일실시간태스크를사용하였다. 이단일실시간태스크는하나의 LOOP만을가지고있는더미태스크다. 그리고각각의실험은 LOOP의횟수를변경하면서수행된다. 이는실시간태스크의작업량에따른수행시간의변화를보기위해서이다. 그외에수행중인태스크는 BrickOS가서비스하는 3개의일반태스크가있다. 이태스크들은가장높은우선순위를가지고실행중이며모두외부장치의이벤트를기다리고있다. 본실험에서는실시간태스크의실행중야기되는지연을해소함으로서얻을수있는시간의이익을아는것이목적이기때문에일반태스크의이벤트가일어나지않도록하였다. 따라서실험태스크는필요한자원이나이벤트를요구하지않으며태스크수행중이벤트상태에빠지지않도록하였다. 모든실험에서의데이터값은태스크의생성에서부터종료까지걸린총시간이며그사이에수행속도에영향을줄수있는타이머인터럽트를제외한외부인터럽트를발생시키지않았다. 또한새로운일반태스크의생성및종료와같은이벤트역시수행되지않으며외부와의통신역시실험태스크의수행중이아닐때만가능하다. 30
< 실험 1> [ 표 4-1] 은실시간태스크생성부터수행까지의지연을없애는알고리즘을적용한후실험한결과이다. 결과에서보듯이개선된스케줄링을사용할경우태스크수행시간의감소를보이고있다. 그렇지만전체태스크속도에있어크게영향을미치는수준은아니며태스크의작업량에따라감소되는양의변화는미미하기때문에작업량이많아질수록줄어드는시간의비율은점점감소한다. [ 표 4-1] 태스크생성시발생하는지연감소 loop 횟수기존스케줄링개선된스케줄링수행시간의차이 10000 9560 ms 9394 ms -166 ms (1.73%) 20000 14720 ms 14552 ms -168 ms (1.14%) 30000 19243 ms 19077 ms -166 ms (0.86%) 40000 23874 ms 23706 ms -168 ms (0.70%) 50000 28359 ms 28190 ms -169 ms (0.59%) < 실험 2> 두번째실험은실시간태스크의수행시불필요한스케줄러의호출을 제한하는알고리즘을적용하였다. [ 표 4-2] 에서보듯이이알고리즘을 적용하면전체실시간태스크의수행시간이감소한다는것을알수있다. 31
게다가기존스케줄링방식에서의태스크수행시간과개선된스케줄링방식에서의태스크수행시간의차이는선형적으로증가한다. 이는태스크의작업량이많아지는것에비례하여줄어드는시간역시증가한다는것을의미한다. 따라서일정한비율만큼의수행시간감소효과를낼수있다. [ 표 4-2] 스케줄러호출제한에따른태스크수행시간의변화 loop 횟수기존스케줄링개선된스케줄링수행시간의차이 10000 9570 ms 8796 ms -774 ms (8.09%) 20000 14350 ms 13426 ms -924 ms (6.43%) 30000 19128 ms 17882 ms -1246 ms (6.52%) 40000 23898 ms 22475 ms -1423 ms (5.95%) 50000 28378 ms 26563 ms -1815 ms (6.39%) < 실험 3> 이번실험에서는위의두알고리즘을복합하여구현한실시간시스템에서태스크의수행시간을측정하였다. 측정결과기존스케줄링방식을사용했을때보다개선된실시간스케줄링알고리즘을적용했을시확실한수행시간의감소가나타남을알수있었다. 감소의폭또한위의두알고리즘을적용했을때보다컸으며차이또한지속적으로증가하였다. 이를통해본논문에서제안한시스템에서의실시간태스크수행이기존의시스템에서보다빠르게완료됨을확인할수있었다. [ 표 4-3] 은실험결과를표로, [ 그림 32
4-1] 은결과값을그래프로나타내고있다. [ 표 4-3] 기존시스템과실시간시스템사이의태스크수행시간비교 loop 횟수기존시스템실시간시스템수행시간의차이 10000 9551 ms 8793 ms -758 ms (7.93%) 20000 14343 ms 13183 ms -1160 ms (8.08%) 30000 19234 ms 17641 ms -1593 ms (8.28%) 40000 23890 ms 21955 ms -1935 ms (8.09%) 50000 28382 ms 26167 ms -2215 ms (7.80%) 작업량이늘어나도일정한비율을유지하며수행시간의감소가일어남을알 수있다. 이는작업량이증가하면지연시간의감소역시늘어난다는것을 의미한다. 밑의그래프는이러한선형적인차이를그래프로보여준다. 2500 수행시간의차이 2000 1500 1000 500 0 10000 20000 30000 40000 50000 loop 횟수 [ 그림 4-1] 기존시스템과실시간시스템간의태스크수행시간차이 33
제 5 장결론 BrickOS는기존의 RCX 펌웨어를능가하는임베디드오퍼레이팅시스템이다. 이오퍼레이팅시스템은기존펌웨어보다보다더많은서비스를 RCX에제공하기위해다양한기능을구현하였다. 우선순위기반의선점형스케줄링방식은그중에하나로써 BrickOS는이스케줄링방식을통해실시간서비스의지원을도모하였다. 그러나실제실시간서비스를제공하기에는몇가지문제점이있다. 실제 BrickOS는실시간태스크의수행을위한어떠한자료구조도지원하고있지않다. 뿐만아니라실시간서비스인점을고려해서기존의스케줄링방식은몇가지의지연시간을가지고있기때문에 Best Effort Service를지원해야하는실시간오퍼레이팅시스템에서이러한스케줄링방식은적합하지않다. 이에본논문에서는 BrickOS가실시간태스크를처리할수있도록기본자료구조를추가하였다. 그리고기존시스템에서실시간태스크를처리할때일어나는지연시간을보완할수있는새로운실시간스케줄링알고리즘을제안하였다. 또한제안한알고리즘을실제로구현하기위해 BrickOS의커널을분석하였으며, 커널중태스크의생성과스케줄링에관련된부분들을수정, 추가하였다. 그리고제안된알고리즘의성능향상을평가하기위한실험은본논문에서제안한알고리즘에서의실시간태스크수행이기존의스케줄링방식보다약 8% 정도빠르게진행되었다는것을보여주었다. 이는제안한실시간시스템이지연시간의감소를통해기존의시스템보다향상된 best effort service를해준다는것을의미하며더불어보다향상된실시간성을가지고있다는것을말한다. 하지만본논문에서제안한실시간태스크에는보완해야할점이있다. 서로 34
다른실시간태스크간에스케줄링알고리즘이정의되어있지않다는점이다. 단일의실시간태스크만이동작할때는문제가없지만동시에여러개의실시간태스크가작업을요구할때는단순히 FIFO의법칙에의해태스크가동작하므로나중에들어온태스크의실시간성을지켜주는데문제가생길수있다. 이를위해서는향후에따로분리된실시간스케줄러에 EDF 나 LLF 방식을적용하여서로다른실시간태스크들간의스케줄링도고려해야주어야한다. 35
참고문헌 [1] Ole Caprani, "RCX Manual", http://legolab.daimi.au.dk/csaea/rcx/ Manual.dir/RCXManual.html, Last updated 6.2.06. [2] Kekoa Proudfoot, RCX Internals, stanford CA-LAB, http:// graphics.stanford.edu/~kekoa/rcx, 1998,1999 stig. [3] Stephen M Moraco, Installing legos on Debian GNU/Linux Systems, http://brickos.sourceforge.net/doc/install-debian.html, 8 October, 2002. [4] 이호익, 이대성, 김기창, legos(lego Operating Systme) 의커널분석 및수정을통한 RCX 간의 Routing 구현, 제 29 회한국정보과학회추계학술 발표회논문집 (I), pp. 424-247, 2002. [5] stig Nielsson, Introduction to the legos kernel, http://legos. sourceforge.net/docs/kerneldoc.ps, September 27, 2000. [6] 김성민, 김윤수, 신동준, 송재각, 김주용, 고건 FreeBSD 상에서의 실시간스케줄러의설계및구현, 한국정보과학회학술발표논문집 Vol.21, No.2, 1994. [7] William Wong, Embedded/systems/Software Editor, BASICS of Design REAL-TIME OPERATING SYSTEMS, A Supplement to Element to Electronic Design, September 1. [8] 최영호, 백창우, 조경민, Real Time OS for Ubiquitous Computing, 10.21.2004. 36
[9] Qung Li Caroline Yao, RTOS 를이용한실시간임베디드시스템디자인, CMPBOOKS, 2004, 2, 6. [10] 김남윤, 신혁식, 김일석, 김연철, 내장형시스템을위한실시간커널의 설계및구현, 한국정보과학회가을학술발표논문집 Vol, 20, No. 2, 1993 [11] 한대만, 최만억, 구용완, 주기태스크의종료시간을보장하기위한 확장된혼합실시간스케줄링알고리즘, 한국정보과학회가을 학술발표논문집 Vol.26.No.2, 1999. [12] 인치호, 실시간제약커널환경하에서의이중실시간스케줄링설계, 전력전자학회논문지제 6 권제 4 호 2001.8.Toby Miller, "Detecting Loadable Kernel Modules", http://www.s0ftpj. org/docs/lkm.htm, 2001. [13] 최정훈, 김경화, 김두상, " 실시간리눅스에서선택알고리즘을이용한 스케줄링성능평가, 한국정보과학회가을학술발표논문집 Vol. 29. No. 2, 2002. [14] Andreas Gerstlauer, Haobo Yu, Daniel D.Gajski, RTOS Modeling for System Level Design, Proceedings of the Design, Automation and Test in Europe Conference and Exhibition, IEEE, 2003 [15] Stephan Hohrmann, sourceforge.net, Lnphost project, http:// lnphost.sourceforge.net, 2006. 37