工學碩士學位請求論文 실시간프로세스의최악응답시간예측 Predicting RT Process s Worst Case Response Time 2008 年 2 月 仁荷大學校大學院 情報通信工學科 李東植
工學碩士學位請求論文 실시간프로세스의최악응답시간 Predicting RT Process s Worst Case Response Time 2008 年 2 月 指導敎授崔源益 이論文을碩士學位請求論文으로提出함 仁荷大學校大學院 情報通信工學科 李東植
이論文을李東植의碩士學位論文으로認定함. 2008 年 2 月日 主審 副審 委員 印 印 印
요 약 범용운영체제로개발된리눅스는전세계의많은개발자들에의해발전해왔다. 그리고리눅스를실시간시스템에서도사용할수있도록스케줄러의수정, 선점형커널의지원등각종지연시간을줄이기위한연구가활발히진행되고있다. 리눅스는선점형커널의지원으로커널모드에서우선순위가높은프로세스에의한선점이가능해졌지만여전히커널과디바이스드라이버의일부분에서는선점을금지시킨다. 리눅스를경성실시간시스템에서활용하기위해서는스케줄링가능성분석을위해실행시간에대한정보가필수적으로요구된다. 그러나프로세스의실행시간은실행시점과실행환경에따라가변적이기때문에정확한실행시간을알아내기어렵다. 게다가리눅스에서는실시간성을요구하지않는프로세스도커널모드에서선점을금지시킬수있다. 보다정확한실행시간을분석하기위해서는해당시스템에서작동될모든프로세스에의해서발생되어질수있는커널모드에서의선점금지시간에대한자세한분석을통해실시간프로세스의최악응답시간을예측하는것이매우중요하다. 본논문에서는커널모드에서선점이금지되는시간을측정해주는모듈을구현하였고실험을통해프로세스별로커널모드에서선점금지시간을측정하였다. 그리고이를바탕으로실시간프로세스의최악응답시간을보다정확히예측할수있음을보였다. i
Abstract Linux, a general-purpose operating systems, has been developed by many developers. For Real time Linux system, various improvements on scheduler correction and research on, preemptive kernel to reduce the time delay are actively underway. By supporting preemption in kernel mode, high priority process can be preempted by the kernel and device drivers, but Linux still has many part of the preemption disabling region. In order to analyze scheduling possibilities for hard real-time Linux systems, execution time information is essential. However, because of execution environment and time of execution, it is difficult to determine the exact process s execution time. Moreover, non real-time process also can disable preemption in kernel mode. In order to analyze the execution time accurately, therefore, it is very important to analyze in detail preemption disabling time of all processes which will be operated from corresponding system. This analysis will help to predict the worst case response time of real-time process. In this paper, we present the kernel module for the preemption disabling time analysis in kernel mode and show experimental results for worst case response time analysis. The results shows that real-time process s worst case response time can be predicted more accurately. ii
목 차 제 1 장서론... 1 제 2 장관련연구... 3 2.1 실시간시스템...3 2.1.1 태스크의특성...4 2.1.2 실시간스케줄링알고리즘...4 2.2 리눅스...7 2.2.1 리눅스스케줄러...8 2.2.2 Preemptive Kernel...12 2.2.3 realtime-preempt Patch...14 2.3 최악응답시간예측...15 2.3.1 최악응답시간예측도구들...16 제 3 장실시간프로세스의최악응답시간예측... 18 3.1 리눅스와기존예측도구들의제한...18 3.2 선점금지시간분석모듈구조...19 3.2.1 수정된커널코드...19 3.2.2 선점금지시간분석모듈구현...23 제 4 장실험및분석... 27 4.1 실험환경...27 4.2 실험및분석...27 제 5 장결론및향후연구... 30 참고문헌... 32 iii
제 1 장서론 리누스토발즈에의해서범용운영체제로개발된리눅스는소스가공개되어있고무료로누구나사용이가능하며재배포가가능하다는장점으로전세계의많은사람들에게환영을받고있다. 이러한리눅스는임베디드뿐만아니라엔터프라이즈분야에도다양하게사용되고발전해왔다. 그리고최근들어리눅스를실시간시스템에서도활용하기위한연구도활발히진행되어선점형커널의지원및커널을자세하게분석하고수정해지연시간을줄임으로써실시간성능을매우높혔다. 그러나아직까지리눅스는연성실시간성만지원한다.[1][2] 경성실시간운영체제로의활용하기에현재의리눅스에서가장문제가되는부분은커널과디바이스드라이버에서선점을금지하는영역이다. 리눅스커널 2.4에서는커널모드에서는완전히선점이금지되었었지만리눅스커널 2.6에서부터는선점형커널을지원함으로써프로세스가커널모드에서작동될때우선순위가높은프로세스에의한선점이가능하게하였다. 그러나여전히일부영역에서는선점을금지시킨다.[2] 이러한리눅스를경성실시간시스템에서활용하기위해서는스케줄링가능성분석을위해실행될모든프로세스의실행시간에대한정보가필수적으로요구된다. 그러나프로세스의실행시간은실행시점과실행환경에따라가변적이기때문에정확한실행시간을알아내기어렵다.[7] 게다가리눅스에서는실시간성을요구하지않는프로세스도커널모드에서선점을금지시킬수있으므로보다정확한실행시간을알아내기위해서는실행흐름에따른실행시간분석도필요하지만해당시스템에서작동될모든 1
프로세스에의해서발생되어질수있는커널모드에서의선점금지시간에 대한자세한분석을통해실시간프로세스의최악응답시간을예측하는것이 더욱중요하다. 이에본논문은리눅스를실시간시스템으로활용하고자할때리눅스상에서프로세스가커널모드에서작동될때선점을금지시키는지연시간들을측정을도와주기위한모듈의구조를제안하고구현한후실험을통해리눅스를실시간시스템으로활용할때실시간프로세스의최악응답시간을예측할수있도록하고자한다. 본논문의구성은다음과같다. 제2장에서는관련연구들을소개한다. 우선실시간시스템에대해서알아보고, 그다음으로실시간운영체제로의리눅스커널에대해서알아보며, 마지막으로리눅스에서실시간프로세스의응답시간을분석하기위한도구들에대해알아본다. 제 3장에서는리눅스와기존도구들의문제점을알아보고커널모드에서선점금지시간분석모듈의구조를제시하고구현한다. 제 4장에서는실험을통해서결과를측정하고분석함으로써리눅스에서실시간프로세스의최악응답시간을예측함을보인다. 마지막제 5장에서는결론및향후연구방향에대해설명하고끝을맺는다. 2
제 2 장관련연구 2.1 실시간시스템 실시간운영체제는마감시간이라는제약을허용하는정도에따라서경성실시간운영체제와연성실시간시스템으로구분된다. 경성실시간시스템은정해진마감시간안에반드시수행결과를도출해야하며, 그렇지못한경우는심각한결함으로간주한다. 예를들면, 핵발전소제어, 공정제어, 항공기제어, 무기체계등을관리하기위한시스템을사용된다. 한편연성실시간시스템은마감시간을최대한맞추려고하지만시간을어겼을때경성실시간시스템에서처럼치명적이지않고마감시간을넘겨서수행을마쳤더라도계산의결과가어느정도의미를가지는시스템을말한다. 예를들면, 온라인트랜잭션시스템, 멀티미디어스트리밍시스템등은연성실시간시스템의응용분야라고할수있다. [6] 이와같은실시간시스템은마감시간을만족시키기위해서고속의계산이필요하기는하지만, 고속의계산이실시간시스템의요구조건을만족시키는것은아니다. 고속의계산은시스템의평균응답시간을줄여줄수있지만실시간시스템에서요구되는예측성을보장해주지는못한다. 현재대부분의실시간시스템은점점복잡해지고있기때문에경성과연성이혼합되어구성하는추세이다. 실시간시스템에서는주어진태스크들이모두마감시간을만족할수있는지의여부를판단하는것이매우중요하다. 이것을스케줄링가능성검사라고하며해당시스템에서모든태스크들이마감시간을만족시키면서수행이가능한가를간단한수식을이용하여판단가능한분석적방법을많이사용한 3
다.[6] 2.1.1 태스크의특성 실시간시스템에서는일반적으로크게 3가지형태로태스크를구분한다. 먼저주기적 (periodic) 태스크와우발적 (sporadic) 태스크그리고비주기적 (aperiodic) 태스크이다.[6] 실시간태스크는주기적으로수행되는특성을갖는경우가많다. 주기적태스크는특정한시간주기를가지고있으며, 각주기마다마감시간을가지고있는태스크이다. 예를들면핵발전소에서온도센서로부터주기적으로온도를입력받아서입력받은정보를주기적으로모니터로출력하는일을하는태스크를말한다. 우발적태스크는특정한외부이벤트에의해서비주기적으로실행되지만주어진마감시간을반드시만족시켜야하는태스크이며, 비주기적태스크는우발적태스크와같이비주기적으로실행되지만마감시간을가지지않는태스크를말한다. 또한태스크들은마감시간을어겼을때결과의심각성에따라 critical 태스크와 non-critical 태스크로나눌수도있으며, 수행중에우선순위가높은태스크가도착했을때 CPU를양보하는지의여부에따라선점 (Preemptive) 태스크와비선점 (Non-Preemptive) 태스크로나눌수도있다. 2.1.2 실시간스케줄링알고리즘 일반적으로범용운영체제의스케줄러는가장기본적인운영체제의기능중 의하나로써 CPU 활용도의극대화, 평균대기시간의최소화그리고 throughput 의극대화를목표로한다. 그러나실시간시스템에서의스케줄러는 4
CPU 활용도의극대화나 throughput의극대화를목표로하는것이아니라어떤이벤트에대한처리시간을위한예측성과실시간성을요구하는태스크에대한마감시간의보장을목표로한다. 이러한실시간시스템을위한실시간스케줄링알고리즘은정적우선순위스케줄링 (Static Priority Scheduling) 알고리즘과동적우선순위스케줄링 (Dynamic Priority Scheduling) 알고리즘으로분류된다. 정적우선순위스케줄링알고리즘은태스크의우선순위가한번정해지면수행되는동안우선순위가변하지않는스케줄링알고리즘을의미하며, 동적우선순위스케줄링알고리즘은실행되는동안태스크의우선순위가변할수있음을의미한다. 먼저정적우선순위스케줄링알고리즘은보통태스크생성시우선순위를지정하며생성되며태스크의수행중에우선순위는바뀌지않는다. 정적우선순위방식을사용하는스케줄링알고리즘은 RM(Rate Monotonic) 방식과 DM(Deadline Monotonic) 방식이있다. RM방식은태스크의주기가짧을수록높은우선순위를할당하여우선순위가높은순서대로태스크를선택해서수행하는방식으로 ucos-ii와 RTLinux등에사용되며, DM방식은태스크의마감시간이짧을수록높은우선순위를할당하며우선순위가높은태스크를선택하는방식이다. 그리고동적우선순위스케줄링알고리즘은정적우선순위스케줄링알고리즘과달리태스크가수행되는동안에언제든지태스크의우선순위가바뀌는것이가능한스케줄링알고리즘이다. 동적우선순위방식을사용하는스케줄링알고리즘은 EDF(Earliest Deadline First) 방식과 TDS(Time Driven Scheduler) 방식, LLF(Least Laxity First) 방식, SRT(Shortest Remainin Time) 방식이있다. EDF방식은가장짧은마감시간을가진태스크에가장높은우선 5
순위를부여하고새로운태스크가도착할때마다우선순위를조정함으로써태스크들이마감시간을지킬수있도록하며, TDS방식은 EDF와같이마감시간을기준으로스케줄링하는것은같으나과부하발생시비중이낮은태스크를제거함으로써과부하상태에대한처리를한다. LLF방식은마감시간까지남아있는 processing time이가장여유가없는태스크의우선순위를높여주는방식으로마감시간을지킬수있도록한다. SRT방식은비선점방식인 SJF(Shortest Job First) 방식을선점형태로바꾸어높은것이며새로운태스크가들어오면현재수행중인태스크와남은 CPU 요구시간을비교하여더짧은 CPU 시간을가진태스크를수행하는방식이다.[6] 2.1.3 실시간운영체제의특성 최근의운영체제들은여러가지효율적인알고리즘을적용하여 CPU 활용의극대화, 평균대기시간의최소화, throughput의극대화등을통해서컴퓨터의성능을향상시켰다. 그러나실시간운영체제에서의성능은단지평균실행시간성능이나 throughput 성능으로측정되지않는다. 범용운영체제의전체적인성능을향상시키는데많은도움이될지라도실시간운영체제에서는많은문제점을나타낼수도있다. 실시간운영체제에서는결정성, 응답성, 사용자제어, 신뢰성이요구된다. 결정성이란명확하게정의된시간안에특정동작을수행하는것을의미한다. 경성실시간시스템에서는내적, 외적요인에관계없이항상일정한시간내에수행이완료되어야하므로결정성은실시간시스템에서매우중요한요소이다. 그리고응답성은어떠한이벤트에대해서가능한한빨리응답하는능력을말한다. 예를들어입출력인터럽트와같은비동기적인이벤트에대해서즉각 6
적인응답은실시간운영체제의중요한요소이다. 사용자제어는사용자에의해서운영체제의제어가가능함을의미한다. 범용운영체제는시간을분할해서모든태스크들에게공평한 CPU할당을통해서 throughput의극대화를목적으로하기때문에실시간서비스를제공하기에는제한적이다. 실시간운영체제에서는사용자가태스크들의우선순위를정하는것뿐만아니라시스템의스케줄링방식, 페이징의사용, 프로세스간의스와핑등모든영역에서시스템을제어하는것이가능해야함을의미한다. 마지막으로신뢰성은장시간동안시스템이오류없이계속동작할수있는것을의미한다. 실시간운영체제는가상의환경에서작동되는것이아니라실세계의환경에서작동되므로실시간시스템의오류는막대한금전적손실이나인간의생명을위협할수도있으므로실행에대한신뢰성역시매우중요한요소이다. 2.2 리눅스 1991년핀란드헬싱키대학의학생인리누스토발즈 (Linus Benedict Torvalds) 는자신의 IBM호환 386 PC를제대로활용하는운영체제를찾고있었다. 그당시사용할수있었던미닉스는교육용으로만들어진것이였기때문에기능이매우제한되었으며, 하드웨어의성능을제대로이용하지못했다. 이에리누스는 IBM호환 PC에서사용할수있는유닉스호환운영체제를만들기로하고개발을시작했다. 리누스토발즈는자신인작업한최초의 0.01 커널을인터넷을통해공개하였고자신의이름을본따 Linux라고이름을붙였다. 리눅스는모든사람이자유롭게복사하고사용할수있으며, 마음대로소스를수정하여재배포할수있는 GPL(Gnu Public License) 의라이센스를따랐다. 소스가공개되어있었기때문에관심이있는사람들은누구나잘못된부분은수정할수있었으며, 부족한기능들을직접구현할수있었다. 그리고전 7
세계의많은개발자들은 IBM 호환 386 PC 에서만이아니라알파 (Alpha) 나스 팍 (SPARC), 모토롤라 (Motorola), 암 (ARM), 밉스 (MIPS) 등다양한아키텍처에 서도리눅스를사용할수있도록작업해오고있다.[1] 이렇게빠르게발전해온리눅스는많은개발자들에의해서기존의커널을일부수정하는작업을통해임베디드시스템에적용되어사용되고있을뿐만아니라실시간시스템에적용하기위해서스케줄러의수정및선점형커널의지원등각종지연시간을줄임으로써실시간운영체제로활용하기위해많은노력을기울이고있다.[2] 2.2.1 리눅스스케줄러 실시간운영체제의스케줄러는항상상수시간안에스케줄링을보장해주어야한다. 리눅스커널 2.4에서의스케줄링알고리즘은시기 (epoch) 단위로 CPU 시간을나누어동작한다. 모든프로세스는시기가시작할때우선순위에기반해서타임퀀텀을할당받아실행한다. 우선순위는 1에서 140까지부여되며 1 에서 99까지는실시간프로세스를위한우선순위에해당하며 100부터 140까지는우선순위는일반프로세스에해당한다. 기본타임퀀텀은 task_struct 자료구조의멤버중의하나인 counter 필드에기록된다. 프로세스의디폴트타임슬라이스는 10tick으로써약 100ms정도이다. 스케줄러로부터 CPU를할당받은프로세스는 10ms마다 1tick씩자신이소유한타임슬라이스를소비하면서실행된다. 타임슬라이스를모두소비한프로세스는다른프로세스에의해선점되며, 실행가능한다른프로세스로대체된다. 시기는실행가능한모든프로세스가타임슬라이스를모두소비했을때스케줄러는모든프로세스의타임슬라이스를다시계산하고새로운시기를시작한다.[1] 이때모든프로세 8
스에대한타임슬라이스의재계산은실시간운영체제에적합하지않다. 그리고리눅스커널 2.4의스케줄러에해당하는 schedule() 함수는 current 프로세스를당장블록시켜야할경우에직접적으로호출되는되기도하며, current의 need_resched 필드값을 1로설정하여커널모드에서유저모드로되돌아가기전에 need_resched 필드값에대한검사를통해서우회적으로호출되기도한다. schedule() 함수가호출되면 [ 그림.2-1] 에서와같이실행큐리스트에있는모든프로세스에대한 goodness를평가함으로써수행할프로세스를선택하게된다. 그러나이러한스케줄러구현은프로세스의갯수가늘어나면스케줄링을위해서필요한시간도늘어난다. 즉, O(n) 의시간이필요하다는말이며, n은프로세스의갯수를뜻한다. 이러한스케줄러구현상의문제점역시프로세스의개수에상관없이항상상수 (constant) 시간안에스케줄링을보장해주지못하며실시간운영체제에는적합하지않았다. [ 그림. 2-1] 리눅스커널 2.4 스케줄러 9
리눅스커널 2.6에서는 Ingo Molnar가개발한일명 O(1) 스케줄러를사용한다. 이새로운스케줄러는글로벌동기화와재계산루프를제거하여 SMP 효율성뿐만아니라항상상수시간안에스케줄링을보장해준다. 이스케줄러는타임슬라이스재계산으로인한문제를해결하기위해서 [ 그림.2-2] 의구조를가지는두개의우선순위배열을사용한다. 이두배열은포인터를통해서액세스되며 active array와 expired array로구분된다. active array는타임슬라이스가남아있고실행가능프로세스리스트을가지고있으며, expired array는 [ 그림.2-3] 과같이타임슬라이스가모두소비된프로세스가 active array에서제거되면서타임슬라이스재계산된프로세스리스트를가지고있다. 모든 active array의프로세스들이타임슬라이스를소비해 active array의 nr_active값이 0이되면, [ 그림.2-4] 과같이두배열을액세스하기위한포인터값은서로바뀌어 expired array는 active array, active array는 expired array가된다. 리눅스커널 2.6의스케줄러는이러한과정을수행함으로써리눅스커널 2.4의스케줄러가모든프로세스의타임슬라이스를계산하는일을 active array와 expired array를스위칭하는일로대체했다. [ 그림. 2-2] 리눅스커널 2.6 의 prio_array 구조체 10
nr_active : 3 => 2 active P1 timeslice 100ms P2 timeslice 100ms P3 timeslice 0ms expired P4 timeslice 150ms P3 timeslice 200ms Recalculate timeslice [ 그림. 2-3] 타임슬라이스재계산과정 [ 그림. 2-4] active array 와 expired array 의스위칭과정 그리고리눅스커널 2.4의스케줄러처럼루프를돌면서모든프로세스에대해서 goodness를평가해다음에실행할프로세스를선택하는것이아니라 [ 그림.2.5] 에서처럼 sched_find_first_bit() 함수를이용해서 active array의 bitmap의첫번째로설정된 bit값을검색해서설정되어있는 bit값의위치를인덱스로 queue 배열에서해당위치의값이가리키는프로세스를선택한다. Bitmap의크기 140bit로고정되어있으므로리눅스커널 2.4에서처럼프로세 11
스갯수에실행시간이영향을받지않고예측가능한시간안에스케줄링이처 리될수있다. [ 그림. 2-5] 리눅스커널 2.6 스케줄러 2.2.2 Preemptive Kernel 리눅스커널 2.4에서는프로세스가시스템콜을요청하거나인터럽트예외가발생하여커널모드에진입한경우프로세스가자발적으로 CPU를반납하거나커널모드에서빠져나오지않는이상커널모드에있는프로세스는선점되지않는다. 따라서커널모드에있는동안인터럽트가발생하여이를처리한결 12
과실시간프로세스또는현재프로세스보다더높은우선순위를가진프로세스가실행이가능해진경우라도스케줄링은커널모드에서유저모드로돌아가는시점에만일어나므로현재프로세스가커널모드에서작업을마칠때까지기다려야만한다. 이러한특징은실시간성을요구하는프로세스가마감시간을보장하지못하게할수도있으므로리눅스를실시간운영체제가되기위해서는커널모드에서선점이가능해야만한다. [ 그림. 2-6] 비선점형커널과선점형커널의비교 오픈커뮤니티에서시작된리눅스커널의선점지원노력은리눅스커널 2.5.4에서공식으로채택되었고커널 2.6부터는컴파일시옵션으로선택할수있게되었다. 이로인해리눅스는어느시점에서든지커널모드에서실행되고있는프로세스가선점으로부터보호되어야하는부분을 locking을하지않고 13
스케줄링이안전하기만하다면커널모드에서선점이가능해졌다. 이러한커널영역의보호는선점카운터를이용해서보호하는데 preempt_disable() 함수는선점카운터를증가시키고 preempt_enable() 은선점카운터를감소시킨다. preempt_disable() 함수는여러번호출될수도있으며, n번 preempt_enable() 함수가호출돼선점카운터가다시 0이되면커널모드에서의선점은가능해진다. 그러면우선순위가높은프로세스가실행이필요하게된경우커널모드에서 preempt_schedule() 함수를호출하여우선순위가높은프로세스가커널모드에서선점하도록해준다.[2] 2.2.3 realtime-preempt Patch 리눅스의 O(1) 스케줄러와 Preemptive Kernel 지원은기존리눅스의실시간성능을높였다. 그러나여전히리눅스커널의많은부분에서잠금이발생하므로실시간운영체제로활용되기에는부족한점을가지고있다. Ingo Molnar에의해관리되고있는 realtime_preempt 패치는부족한점을보완하기위해서기존의커널을분석하여긴 locking latency를가지는구간을찾아내수정하고새로운선점포인트를추가해우선순위가높은프로세스를위한선점타이밍을앞당김으로써우선순위가높은프로세스가실행될수있는시간을앞당겼다. 그리고 [ 표.2-1] 과같이커널의스핀락코드를 mutex로대체함으로써 lock을사용지지않는프로세스가실행할기회를빼앗는것을없애고 spinlock 요청영역의전역적 locking을지역화시켰다. 게다가추가적으로인터럽트처리에서도 [ 그림.2-7] 에서처럼기존의인터럽트처리와달리타이머인터럽트를제외한다른인터럽트처리들을커널쓰레드화시키고각각의인터럽트쓰레드에우선순위와 SCHED_FIFO 스케줄링정책을할당함으로써인터 14
럽트처리가끝날때까지선점을금지시키지않음으로써리눅스의예측가능성 을높였다. [ 표. 2-1] CONFIG_PREEMPT 와 CONFIG_PREEMPT_RT 비교 [ 그림. 2-7] 기존인터럽트처리과정과인터럽트쓰레드화의비교 2.3 최악응답시간예측 리눅스를실시간시스템으로활용하기위해많은수정을거쳐서실시간성 능을높였지만완벽한경성실시간성을가지지는못하고있다. 그러므로리눅 15
스를실시간운영체제로활용하기위해서는해당시스템에서작동하는리눅스커널의성능에대한분석뿐만아니라유저레벨에서실행되는모든프로세스에서의실행시간에대한철저한분석을통해스케줄링이가능한가를알아보기위해서는보다정확한응답시간에대한분석이요구된다. 2.3.1 최악응답시간예측도구들 리눅스를실시간시스템에서활용하기위해서유저레벨에서리눅스의실시간성능을평가하는도구들은주로해당프로세스에대한응답에대한지연시간을측정에목적을둔다. 실시간성을요구하는프로세스를수행하여응답에대한지연시간을분석함으로써실시간시스템으로활용이가능한가를판단한다. Realfeel은 mlockall() 시스템콜을이용해서프로세스의페이징을금지시키고스케줄링정책과우선순위를지정한후 /dev/rtc를이용해서주기적인인터럽트를발생시키고 /dev/rtc에대해서 read() 시스템콜에대한처리시간을측정함으로써실시간프로세스의응답시간을평가한다.[3] 그리고 cyclictest의경우는우선순위가다른여러개의쓰레드를생성해서소프트웨어타이머를이용해서주기적으로시그널을발생시켜시그널에대한응답속도를측정하거나 nanosleep() 을이용해서해당쓰레드가깨어나는데걸리는시간을측정하여리눅스커널에서의서비스처리속도와응답시간을바탕으로해당실시간프로세스의최악응답시간을예측한다. [4] 16
User Process read() User Level Analyzer read() sys_read() Virtual File System(VFS) vfs_read() Ext2 ext2_read() Device Driver DISK [ 그림. 2-8] 일반적인응답시간분석도구작동방식의예 17
제 3 장실시간프로세스의최악응답시간예측 3.1 리눅스와기존예측도구들의제한제 2장에서분석한최악응답시간예측도구들은해당시스템의실시간프로세스의응답시간측정을위해서실행되면해당프로세스가실행하는도중에리눅스의페이징폴트로발생할수있는지연시간을해결하기위해서 mlock() 또는 mlockall() 시스템콜을이용해서시스템콜을호출한프로세스에대해서페이징을금지시켜항상물리메모리상에상주시키고 sched_setscheduler() 함수를이용해서프로세스에실시간프로세스를위한우선순위를할당하고실시간프로세스를위해서스케줄링방식을바꾼다음커널과유저프로세스사이에서프로세스가응답하는데걸리는지연시간들을계속해서메모리에기록해둠으로써실시간프로세스의응답시간측정을수행한다. 그러나이러한방법은커널내부에서지연되는시간까지자세히분석하는것이아니라유저레벨에서프로세스의응답시간을분석하는것일뿐이다. 그러므로이러한분석도구들은하나의실시간프로세스에대해서만응답시간분석이가능하며여러개의프로세스가동작하는경우에대해서는다른프로세스가해당프로세스에게미치는영향들은분석이어렵다. 그리고 realtime-preempt 패치가적용되고선점형커널로컴파일된리눅스가동작하고있는시스템에서는사용자프로세스가어떤커널의서비스를요청하는경우해당프로세스가커널모드에서완전히선점을금지하는것이아닌커널코드의일부분에서만금지된다. 그러므로우선순위가낮은프로세스인경우, 우선순위가높은프로세스에게미치는영향은커널모드에서의선점금지시간이므로이러한다른프로세스에게미치는영향을분석할수가없다. 게다가시스템에서실행될모든프로세스들을동시에 18
실행되는환경을만들어서수행되어야하지만이러한실행상황을만드는것은매우어렵다. 그러므로보다체계적인방법을통해서실시간프로세스의최악응답시간을예측하기위해서는커널모드에서선점이금지되는시간을정확하게측정해줄도구가필요하다. 3.2 선점금지시간분석모듈구조실시간프로세스의최악응답시간을보다정확하게예측하기위해서는커널모드에서선점금지시간을측정하고저장하는오버헤드를가능한한최대한줄일수있는구조를가져야한다. 3.2.1 수정된커널코드리눅스커널 2.4에서는프로세스가 CPU를스스로포기하지않는이상커널모드에서는현재실행되고있는프로세스보다우선순위가높은프로세스가선점하는것이불가능했다. 그러나리눅스커널 2.5에서부터커널모드에서의선점지원에대한연구가진행되어리눅스커널 2.6에서는커널선점패치가포함되어커널모드에서우선순위가높은프로세스를위해선점이가능하게되었다. 그리고커널선점패치와더불어 Robert Love의 Low-Latency 패치등실시간성능향상을위해서여러패치가합쳐진 Ingo Molnar의 realtime-preempt 패치는기본리눅스커널 2.6의부족한실시간성능을좀더보완해실시간운영체제로의리눅스실시간성능을상당히높혔다.[2] 물론앞에서도언급했듯이현재에도커널코드의모든부분이선점이가능하다는것은아니다. 여전히 realtime-preempt 패치가적용된커널코드의특정중요한섹션은선점에대비해서잠긴다. 이러한잠금은 CPU당 19
데이터구조와상태가선점으로부터항상언제나보호되어야하는것을확실히해두고있다. 리눅스커널 2.6에서는커널모드에서우선순위가낮은프로세스가수행할때우선순위가높은프로세스에의해서선점으로부터보호되어야영역은선점카운터를이용해보호하며선점카운터는 [ 그림. 3-1] 에있는 preempt_disable(), preempt_enable() 그리고 preempt_enable_no_resched() 함수들에의해서증가하거나감소한다. #define preempt_disable() \ do { \ inc_preempt_count(); \ barrier(); \ } while (0) #define preempt_enable() \ do { \ preempt_enable_no_resched(); \ barrier(); \ preempt_check_resched(); \ } while (0) #define preempt_enable_no_resched() \ do { \ barrier(); \ dec_preempt_count(); \ } while (0) [ 그림. 3-1] 커널모드에서선점금지를위한함수들 preempt_disable() 함수는여러번호출이가능하며호출될때마다 preempt_count를증가시켜낮은우선순위의프로세스가커널모드에서우선순위가높은다른프로세스에의해서선점되는것을금지시킨다. preempt_enable() 은호출될때마다 preempt_count를감소시키며 20
preempt_count가 0이되면비로소커널영역에서높은우선순위의프로세스가낮은우선순위의프로세스를중지시키고 CPU를선점하는것이가능해진다.[2] 그러므로 preempt_disable() 함수와호출될때 preempt_count값이 0이아닌경우현재시간을저장하고나중에 preempt_enable_no_resched() 함수가호출되기전에 preempt_count값을확인해서다시 0이되었을때현재시간을측정한다면이두시간의차이를이용해서커널내부에서선점이금지된시간을알수가있다. 그래서커널모드에서선점을금지시키는시작부분과선점이가능하게하는부분인 preempt_disable() 함수와 preempt_enable_no_resched() 함수를 [ 그림.3-2] 와같이커널코드를수정함으로써선점금지시간을분석할수있도록하였다. [ 그림. 3-2] 수정된선점금지를위한함수들 추가된두개의함수는모듈의로깅함수를호출함으로써해당프로세스에 의한선점금지시간에대한정보를저장한다. 그러나리눅스에서커널은 21
모듈이로드되었을때지정된 open(), read(), write() 와같은시스템콜을통한몇개의함수만호출이가능할뿐그이외의함수들은모듈내부에서만참조가가능하다.[5] 그러므로커널에의해서모듈의함수가호출될수가없으므로선점금지시간을측정하고저장하는오버헤드를줄이기위해서이러한함수들을통하지않고커널에서직접한번에모듈의특정함수를호출할수있도록하기위해서 [ 그림.3-3] 와같이 NULL 값을가진함수포인터를선언하고 EXPORT_SYMBOL() 을이용해모듈에서이함수포인터를참조할수있도록하고함수포인터를이용해서함수포인터값이 NULL인지아닌지만을검사함으로써커널에서모듈이로드되었는지를판단하게하여모듈의함수를호출하도록커널을일부수정하였다. [ 그림. 3-3] 커널에서모듈함수를참조하기위해추가된함수들 22
3.2.2 선점금지시간분석모듈구현 선점금지시간분석모듈에서는로깅여부판단을위해서두가지의 검사를수행해야한다. 먼저최대한빠르게로깅을프로세스가맞는지 아닌지검사를수행하고 preempt_count값이 0인지아닌지검사한다. 이두가지검사를모두만족하는경우만로깅을수행한다. 모듈에서이러한두가지검사를최대한오버헤드를줄이면서수행한후두개의조건을만족한다면 preempt_disable_logging_fn() 함수에서호출된모듈의함수는현재시간을측정해서저장하고 preempt_enable_logging_fn() 함수에서호출된모듈의함수는현재시간을측정후선점이금지되었던시간과두시간의차이를저장해둠으로써커널모드에서해당프로세스에의해서선점이금지된시간정보들을응답시간분석에이용할수있도록한다. 이러한작동흐름을알고리즘으로표현하면 [ 그림.3-4] 와 [ 그림.3-5] 와같다. [ 그림. 3-4] 선점금지시전반적인수행과정 23
[ 그림. 3-5] 선점가능시전반적인수행과정 커널내부에서프로세스별로선점이금지되는시간을보다정확하게측정하기위해서는실행에따른오버헤드가최대한적어야한다. 커널모듈에서현재시간을측정하는오버헤드를제외하고최대한오버헤드를줄이기위한방법중첫번째로모듈은 [ 그림.3-6] 에서처럼프로세스의선점이금지되는시간을기록해둘 log_task 구조체에대한포인터배열을미리리눅스에서실행가능한프로세스개수사이즈만큼미리선언해놓고모듈이로드될때 NULL값으로초기화시켜놓고이배열을이용해서로깅할프로세스인지아닌지판별한다. 판별방법은 [ 그림.3-7] 과같이유저프로세스의 pid에해당하는위치의배열의값이 NULL이면선점금지시간정보를저장할 log_task 구조체가할당되지않았으므로로깅할프로세스가아님을나타내고 NULL값이아니면선점금지시간정보를저장할 log_task 구조체가있다는것을의미하므로로깅할프로세스로판단하고로깅을수행한다. 24
[ 그림. 3-6] 프로세스별로깅정보를저장할 log_task 구조체 struct log_task *logging_task[] n log_task 3 2 1 0 last... 1... 1 0 0 0 XXX log_task n 3 2 1 0 last... 0... 0 0 0 0 0 [ 그림. 3-7] 로깅할프로세스판단과정 커널은사용자프로세스에의해서로깅에대한요청이있으면커널내부에선점금지된시간을저장하기위해서동적으로메모리를할당하고동적으로할당된메모리의주소를배열의해당위치에저장함으로써곧바로로깅을수행할수있도록한다. 그리고두번째로선점이금지된시간에대한정보를저장할때도유저프로세스에대한로깅요청이들어오면모듈은 log_task 구조체를동적으로할당하고정수배열을먼저모든값을 0으로초기화후 preempt_disable() 함수가호출되어 preempt_count값이 0일때시간정보를저장할 last 멤버값을초기화한다. 그리고다시 preempt_enable_no_resched() 함수가호출되었을때 preempt_count값이 25
0이되면다시현재시간을측정하고선점이금지된시간을저장할때는 log_task 구조체의 last값과현재시간의차를 delay 배열의인덱스로사용해서해당위치의값을 1 증가시킴으로써시간에대한정보를단한번에찾아서저장함으로써실행에대한오버헤드를줄인다. log_task 0 n idx = current_time - last... 1... 0 0 0 0 X X X update 3 2 1 0 last log_task[idx] + 1 calculate idx [ 그림. 3-9] 해당프로세스로인한선점금지시간기록과정 26
제 4 장실험및실험결과 4.1 실험환경본논문에서제안한프로세스별선점금지시간분석모듈은리눅스커널 2.6.18버전에 Ingo Molnar의 realtime-preempt 패치를적용된시스템에서 gcc 4.1.2 버전을이용하여구현되었다. 실험에사용된컴퓨터의시스템사양은 Intel x86기반의 Pentium IV 1.5GHz, 256MB PC를사용하였고, 커널에영향을주지않고보다정확한시간측정을위해커널의 do_gettimeofday() 함수를이용하지않고타임스탬프값을읽어직접계산하도록구현하였다. 본실험에서는사용자프로세스에서실험데이터를직접읽어들여서출력하도록고려하였으나커널내에존재하는데이터를사용자프로세스로옮기는과정에발생하는선점금지로발생하는재귀적인로깅으로인한문제와사용자프로세스로옮길때발생하는지연시간데이터를없애기위해서로깅중지요청시에커널메시지로출력되도록하였다. 이메시지는리눅스명령어 dmesg로확인이가능하며해당프로세스이름과 pid로써구분이가능하도록하였다. 4.2 실험및실험결과실시간시스템에서는실시간프로세스만수행되는것이아니라실시간성을요구하지않는프로세스도수행된다. 이러한상황에서실시간프로세스는다른모든프로세스에의해서지연될수있다. 그리고실시간프로세스는우선순위가낮은다른모든프로세스들중에커널모드에서의선점금지시간이가장긴시간만큼지연된다. 그러므로자세한분석을위해실험은총 2가지과정으로구분해실험을수행했다. 첫번째는과정은 4개의 Non-RT 프로세스 27
가수행될때발생하는커널에서의선점금지시간을측정하는실험이며, 두번째과정은실시간프로세스와일반프로세스가동시에수행될때여러가지상황에서일반프로세스에의한선점금지로인해서발생하는실시간프로세스의응답지연시간을측정하고첫번째실험결과와비교분석하였다. 모의실험에서사용된실시간프로세스는 realfeel과같이 /dev/rtc를이용해주기적으로인터럽트를발생시키고이에대한처리를수행하는응답시간을측정하는프로세스이며, Non-RT 프로세스는실시간성을요구하지는않지만시스템콜을호출하여커널모드에서선점을금지시키는서로다른종류의프로세스들이다. < 과정 1> [ 표.4-1] 는 4 개의 Non-RT 프로세스들을단독으로실행시키고해당프로세 스에의해커널모드에서선점이금지되는시간을측정한결과이다. [ 표.4-1 ] 4 개의 Non-RT 프로세스의선점금지시간 < 과정 2> [ 표.4-2] 은실시간프로세스와일반프로세스를동시에실행시키고, 여러가 28
지상황에서실시간프로세스의응답지연시간의변화를예측해보았고실제 로실시간프로세스의최대응답지연시간을측정한결과이다. [ 그림. 4-2]RT 프로세스의최악응답지연시간의변화 결과에서보면실시간프로세스와일반프로세스가동시에실행되는경우실시간프로세스의응답지연시간은예측변화량보다조금크다는것을알수있다. 이것은태스크스케줄링시간이추가되었기때문이며태스크스케줄링으로인한지연시간역시조금씩다른이유는리눅스의 O(1) 스케줄러가항상고정된시간에스케줄링을보장해주는것이아니라최대스케줄링시간을보장을해주기때문이다. 그러나스케줄링시간을제외한다면본논문에서구현한모듈을이용해일반프로세스에의해서선점이금지되는시간분석함으로써상당히정확히실시간프로세스의응답지연을예측할수있음을볼수있다. 29
제 5 장결론및향후연구 리눅스를임베디드환경에서뿐만아니라엔터프라이즈급환경에서도실시간운영체제로활용하기위한실시간운영체제로써의예측성과정확성을높이기위한연구가활발히진행되었고많은부분에있어서엄청난개선을이뤘다. 그러나여전히리눅스의커널모드일부분에서는우선순위가높은프로세스에의한선점이이루어지지않으므로완벽한예측을할수가없다. 게다가여러개의프로세스가동시에작동하는경우에는더더욱예측이어렵다. 이러한리눅스를실시간시스템으로활용하기위해서는스케줄링가능성을알아보기위해모든프로세스의실행시간에대한정확한분석이필요하다. 그러나프로세스의실행시간에대한정확한분석또한매우어려우며실시간성을요구하지않는프로세스에의해서도실시간프로세스가지연될수있으므로모든프로세스에의해발생하는커널모드에서선점금지시간에대한정확한분석을통해실시간프로세스의최악응답시간예측이필요하다. 본논문에서는리눅스를실시간시스템으로활용하고자할때이러한문제점을해결하고자유저레벨에서프로세스별로수행도중에해당프로세스에의해서커널모드에서선점이금지되는시간을분석해주는모듈을구현하였다. 또한, 실험을통하여프로세스별커널모드에서의선점금지시간측정을통하여리눅스를실시간시스템으로활용하기위한실시간프로세스의최악응답지연시간을예측할수있음을보였다. 그러나본논문에서제안한프로세스별선점금지시간분석모듈은보완해야할점을가지고있다. 제안한모듈은해당프로세스에대해서커널모드에서선점금지시간을분석해주지만해당프로세스가 fork() 또는 exec() 와같은시스템콜을사용해서새로운프로세스를생성하는경우새롭게생성된프 30
로세스에대해서는분석을해주지못하므로응답시간에대한예측하는데제약이된다. 이를보완하기위해서는향후 fork() 와 exec() 와같은시스템콜을수정하여부모프로세스가생성한자식프로세스들에대한분석도해주도록수정하거나부모프로세스의로깅여부를판단하여로깅을수행하는방식의구현도고려되어야한다. 31
참고문헌 [1] Linus Tovalds, www.kernel.org [2] Ingo Molnar, RT Patch, http://people.redhat.com/mingo/realtimeprempt [3] Mark Hahn. http://brain.mcmaster.ca/hahn/realfeel [4] Thomas Gleixner. http://rt.wiki.kernel.org/index.php/cyclictest [5] 유영창저, 리눅스디바이스드라이버. 한빛미디어 [6] Qing Li Caroline Yao 저, 전동환성원호역. RTOS 를이용한실시간 임베디드시스템디자인 [7] 박현희, 최명수, 양승민, 최용훈, 임형택, XScale 프로세서기반의임베디드소프트웨어를위한최악실행시간분석도구의구현 한국정보처리학회정보처리학회논문지 A, Vol 12, No. 5, 365-374 32