Pokyny pro vypracování
Prostudujte různé typy algoritmů použitelných pro systémy reálného času.
Implementujte vybrané z nich (nejlépe v jazyce C) tak, aby byly aplikovatelné pro vestavné systémy.
Srovnejte a zhodnoťte algoritmy a jejich implementaci s ohledem na předem daná návrhová omezení (determinismus, velikost, maximální pracovní frekvence, plnění deadlinů, apod.).
Výběr přizpůsobte možnostem využití při výuce bakalářského předmětu "Systémy reálného času", používání konkrétních přípravků v laboratorní výuce a operačního systému RTOS.
Zadání bakalářské práce
Název: Implementace a srovnání plánovacích algoritmů pro systémy reálného času
Student: Josef Zápotocký
Vedoucí: doc. Ing. Hana Kubátová, CSc.
Studijní program: Informatika
Obor / specializace: Počítačové inženýrství Katedra: Katedra číslicového návrhu
Platnost zadání: do konce letního semestru 2020/2021
Bakal´ aˇrsk´ a pr´ ace
Implementace a srovn´ an´ı pl´ anovac´ıch algoritm˚ u pro syst´ emy re´ aln´ eho ˇ casu
Josef Z´ apotock´ y
Katedra ˇc´ıslicov´eho n´avrhu
Vedouc´ı pr´ace: doc. Ing. Hana Kub´atov´a, CSc.
Podˇ ekov´ an´ı
Zde bych chtˇel podˇekovat vˇsem, kdo mˇeli trpˇelivost se mnou bˇehem vypra- cov´av´an´ı bakal´aˇrsk´e pr´ace, a to vedouc´ı doc. Ing. Hanˇe Kub´atov´e, CSc., m´emu
Prohl´ aˇ sen´ı
Prohlaˇsuji, ˇze jsem pˇredloˇzenou pr´aci vypracoval samostatnˇe a ˇze jsem uvedl veˇsker´e pouˇzit´e informaˇcn´ı zdroje v souladu s Metodick´ym pokynem o dodrˇzo- v´an´ı etick´ych princip˚u pˇri pˇr´ıpravˇe vysokoˇskolsk´ych z´avˇereˇcn´ych prac´ı.
Beru na vˇedom´ı, ˇze se na moji pr´aci vztahuj´ı pr´ava a povinnosti vypl´yvaj´ıc´ı ze z´akona ˇc. 121/2000 Sb., autorsk´eho z´akona, ve znˇen´ı pozdˇejˇs´ıch pˇredpis˚u.
V souladu s ust. § 2373 odst. 2 z´akona ˇc. 89/2012 Sb., obˇcansk´y z´akon´ık, ve znˇen´ı pozdˇejˇs´ıch pˇredpis˚u, t´ımto udˇeluji nev´yhradn´ı opr´avnˇen´ı (licenci) k uˇzit´ı t´eto moj´ı pr´ace, a to vˇcetnˇe vˇsech poˇc´ıtaˇcov´ych program˚u, jeˇz jsou jej´ı souˇc´ast´ı ˇci pˇr´ılohou a veˇsker´e jejich dokumentace (d´ale souhrnnˇe jen ”D´ılo“), a to vˇsem osob´am, kter´e si pˇrej´ı D´ılo uˇz´ıt. Tyto osoby jsou opr´avnˇeny D´ılo uˇz´ıt jak´ymkoli zp˚usobem, kter´y nesniˇzuje hodnotu D´ıla a za jak´ymkoli ´uˇcelem (vˇcetnˇe uˇzit´ı k v´ydˇeleˇcn´ym ´uˇcel˚um). Toto opr´avnˇen´ı je ˇcasovˇe, teritori´alnˇe i mnoˇzstevnˇe neomezen´e. Kaˇzd´a osoba, kter´a vyuˇzije v´yˇse uvedenou licenci, se vˇsak zava- zuje udˇelit ke kaˇzd´emu d´ılu, kter´e vznikne (byt’ jen zˇc´asti) na z´akladˇe D´ıla,
´upravou D´ıla, spojen´ım D´ıla s jin´ym d´ılem, zaˇrazen´ım D´ıla do d´ıla souborn´eho ˇci zpracov´an´ım D´ıla (vˇcetnˇe pˇrekladu) licenci alespoˇn ve v´yˇse uveden´em roz- sahu a z´aroveˇn zpˇr´ıstupnit zdrojov´y k´od takov´eho d´ıla alespoˇn srovnateln´ym zp˚usobem a ve srovnateln´em rozsahu, jako je zpˇr´ıstupnˇen zdrojov´y k´od D´ıla.
ˇCesk´e vysok´e uˇcen´ı technick´e v Praze Fakulta informaˇcn´ıch technologi´ı
© 2021 Josef Z´apotock´y. Vˇsechna pr´ava vyhrazena.
Tato pr´ace vznikla jako ˇskoln´ı d´ılo na ˇCesk´em vysok´em uˇcen´ı technick´em v Praze, Fakultˇe informaˇcn´ıch technologi´ı. Pr´ace je chr´anˇena pr´avn´ımi pˇredpisy a mezin´arodn´ımi ´umluvami o pr´avu autorsk´em a pr´avech souvisej´ıc´ıch s pr´avem autorsk´ym. K jej´ımu uˇzit´ı, s v´yjimkou bez´uplatn´ych z´akonn´ych licenc´ı a nad r´amec opr´avnˇen´ı uveden´ych v Prohl´aˇsen´ı na pˇredchoz´ı stranˇe, je nezbytn´y sou- hlas autora.
Odkaz na tuto pr´aci
Z´apotock´y, Josef.Implementace a srovn´an´ı pl´anovac´ıch algoritm˚u pro syst´emy re´aln´eho ˇcasu. Bakal´aˇrsk´a pr´ace. Praha: ˇCesk´e vysok´e uˇcen´ı technick´e v Praze, Fakulta informaˇcn´ıch technologi´ı, 2021.
Abstrakt
Tato pr´ace se zab´yv´a pl´anovac´ımi algoritmy pro syst´emy re´aln´eho ˇcasu, zkoum´a a modifikuje operaˇcn´ı syst´em re´aln´eho ˇcasu FreeRTOS. FreeRTOS je speci´alnˇe vyvinut´y pro mal´e vestavˇen´e syst´emy, tak aby uspokojil jak n´aroky uˇzivatele tak pamˇet’ov´e n´aroky mal´ych vestavn´ych zaˇr´ızen´ı. Po podrobn´em popisu pri- oritn´ıho pl´anovaˇce pˇrijat´eho z FreeRTOS jsou navrˇzeny dva uˇcebn´ı pl´anovaˇce:
prvn´ı je zaloˇzen na zn´am´em algoritmu pˇrednosti s nejbliˇzˇs´ı uz´avˇerkou (EDF), druh´y je zaloˇzen na algoritmu pˇrednosti ´ukolu s nejmenˇs´ı laxitou (LLF), p˚uvodnˇe vyvinut´y pro syst´emy s v´ıce procesory. U kaˇzd´eho navrhovan´eho pl´anovaˇce je uveden popis funkˇcnosti pl´anovaˇce, uk´azka pr´ace dan´eho pl´anovac´ıho algoritmu a n´asledn´a implementace ve FreeRTOS. Pot´e je spr´avnost pl´anovac´ıch algoritm˚u implementovan´e ve FreeRTOS ovˇeˇrena testem. Pl´anvac´ı algoritmy byly vybr´any na z´akladˇe uˇziteˇcnosti v bakal´aˇrsk´em pˇredmˇetu BI-SRC na FIT
ˇCVUT v Praze.
Kl´ıˇcov´a slova FreeRTOS, EDF, LLF, Implementace, Testov´an´ı
Abstract
This work deals with scheduling algorithms for real-time systems, examines and modifies the real-time operating system FreeRTOS. FreeRTOS is spe- cially developed for small embedded systems to meet both user and memory requirements. After a detailed description of the priority scheduler adopted by FreeRTOS, two learning schedulers are proposed: the first is based on the known Earliest Deadline First Algorithm (EDF), the second is based on the Least Laxity First Algorithm (LLF), originally developed for multiprocessor systems. For each proposed scheduler, a description of the scheduler’s func- tionality, a demonstration of the work of the scheduling algorithm and sub- sequent implementation in FreeRTOS is given. Then the correctness of the planning algorithms implemented in FreeRTOS is verified by a test. Planning algorithms were selected on the basis of usefulness in the bachelor’s course BI-SRC at FIT CTU in Prague.
Keywords FreeRTOS, EDF, LLF, Implementation, Testing
viii
Obsah
Uvod´ 1
1 C´ıl pr´ace 3
2 Anal´yza a n´avrh 5
2.1 FreeRTOS . . . 6
2.1.1 Struktura j´adra . . . 6
2.1.2 Struktura ´uloh . . . 7
2.1.3 Stavy ´uloh . . . 10
2.1.4 Inicializace ´uloh . . . 12
2.1.5 Usp´an´ı ´uloh . . . 15
2.1.6 Pˇrep´ın´an´ı kontextu . . . 16
2.1.7 Syst´em tik˚u . . . 18
2.1.8 Uk´azka pl´anov´an´ı . . . 19
2.2 EDF . . . 22
2.2.1 Uk´azka pl´anov´an´ı . . . 23
2.3 LLF . . . 23
2.3.1 Uk´azka pl´anov´an´ı . . . 23
3 Implementace 25 3.1 EDF . . . 25
3.2 LLF . . . 33
4 Testov´an´ı 41 4.1 Testov´an´ı FreeRTOS pl´anovaˇce . . . 41
4.2 Testov´an´ı EDF . . . 45
4.3 Testov´an´ı LLF . . . 49
4.4 Z´avˇer testov´an´ı . . . 53
Z´avˇer 55
Literatura 57
A Seznam pouˇzit´ych zkratek 59
B Obsah pˇriloˇzen´eho CD 61
x
Seznam obr´ azk˚ u
2.1 Graf stav˚u a pˇrechod˚u ´ulohy . . . 11
2.2 xTaskCreate . . . 13
2.3 Kontext spouˇstˇen´ı ´ulohy . . . 17
2.4 Z´asobn´ık ´ulohy po uloˇzen´ı kontextu . . . 17
2.5 Pˇr´ıklad interakce pˇrep´ın´an´ı obsahu ´uloh . . . 20
2.6 Pˇr´ıklad interakce pˇrep´ın´an´ı obsahu ´uloh . . . 20
2.7 Pˇr´ıklad interakce pˇrep´ın´an´ı obsahu ´uloh . . . 21
2.8 Pˇr´ıklad interakce pˇrep´ın´an´ı obsahu ´uloh . . . 21
2.9 Pl´anov´an´ı ´uloh . . . 23
2.10 Pl´anov´an´ı ´uloh . . . 24
3.1 Nov´y list pro EDF . . . 26
3.2 Implemenetace EDF . . . 27
3.3 Implemenetace EDF . . . 28
3.4 Implemenetace EDF . . . 29
3.5 Nov´y list pro LLF . . . 35
4.1 Pr˚ubˇeh FreeRTOS pl´anovaˇce . . . 44
4.2 Testov´an´ı Pl´anov´an´ı ´uloh1 . . . 48
4.3 Pr˚ubˇeh EDF . . . 48
4.4 Pl´anov´an´ı ´uloh . . . 52
4.5 Pr˚ubˇeh LLF . . . 52
Seznam tabulek
2.1 FreeRTOS vrstvy . . . 6
Uvod ´
Pokrok v technologi´ıch za posledn´ıch 30 let a jejich uplatˇnov´an´ı ve svˇetˇe na m´ıstech, kde m˚uˇze j´ıt vyloˇzenˇe o ˇzivot, n´am pˇrivedlo n´aroky na nˇe takov´e, ˇze uˇz jednoduch´e algoritmy b´yvaj´ı nˇekdy pˇr´ıliˇs m´alo, a proto n´am tyto n´aroky daly operaˇcn´ı syst´emy re´aln´eho ˇcasu, u kter´ych je vyˇzadov´ano, aby vˇzdy byly v ˇcas splnˇeny kritick´e ´ulohy v dan´y ˇcasov´y okamˇzik bez toho aniˇz by se syst´em zasekl, ˇci dan´e ´uloze pˇrek´aˇzela jin´a ´uloha v dodˇel´an´ı. Proto do dan´ych syst´em˚u re´aln´eho ˇcasu se implementovaly r˚uzn´e algoritmy pro pl´anovan´ı ´uloh, kter´e se s dan´ym probl´emem pl´anov´an´ı ´uloh vypoˇr´ad´avaj´ı jinak, a bohuˇzel doch´az´ı i k pˇr´ıpad˚um, ˇze se pˇrerozdˇelen´ı ´uloh ned´a uspoˇr´adat tak aby je syst´em zvl´adl vˇsechny zpracovat [1]. Pokud syst´em nedok´aˇze zpracovat dan´e ´ulohy, tak selˇze, a selh´an´ı tˇechto syst´em˚u m˚uˇze m´ıt kritick´e n´asledky.
Pr´ace se proto zab´yv´a otevˇren´ym operaˇcn´ım syst´emem re´aln´eho ˇcasu FreeR- TOS [2], kter´y b´yv´a uplatnˇen v mnoha odvˇetv´ıch a zaˇr´ızen´ıch. Napˇr´ıklad je uplatnˇen v mesh s´ıt´ı ˇci v ˇzelezniˇcn´ı dopravˇe. ´Ukolem zde bude modifikovat j´adro tohoto operaˇcn´ıho syst´emu, aby pouˇz´ıval konkr´etn´ı n´ami implemento- van´e pl´anovaˇce, a to pl´anovaˇce EDF a LLF. Tyto pl´anovac´ı algoritmy byly z´amˇernˇe vybr´any, jelikoˇz jejich znalost a pochopen´ı je souˇc´ast´ı bakal´aˇrsk´eho pˇredmˇetu Syst´emy re´aln´eho ˇcasu (BI-SRC), a tato bakal´aˇrsk´a pr´ace by mˇela slouˇzit jako zp˚usob, jak porozumˇet jejich rozhodov´an´ı jin´ym zp˚usobem neˇz si to vˇse kreslit na pap´ır v praktick´e ˇc´asti v´yuky.
Pr´ace pˇredstav´ı, co je to FreeRTOS po technick´e str´ance, kter´e soubory bu- dou modifikov´any, aby v´ysledn´a aplikace pouˇz´ıvala dan´y pl´anovac´ı algoritmus.
Bude zde zm´ınˇena teorie k vybran´ym pl´anovac´ım algoritm˚um a jak´y pl´anovac´ı algoritmus FreeRTOS pouˇz´ıv´a. Po implementaci algoritm˚u budou n´aslednˇe otestov´any a porovn´any mezi sebou. N´aslednˇe si urˇc´ıme, kter´y z nich obst´al nejl´epe a nˇejakou teori´ı za t´ım proˇc.
Kapitola 1
C´ıl pr´ ace
C´ılem t´eto bakal´aˇrsk´e pr´ace je prostudovat pl´anovac´ı algoritmy pro syst´emy re´aln´eho ˇcasu a n´aslednˇe vybrat a implementovat v jazyku C nov´e pl´anovac´ıal- goritmy pro FreeRTOS. U kaˇzd´eho vybran´eho navrhovan´eho pl´anovac´ıho algo- ritmu je uveden popis implementace ve FreeRTOS a pˇr´ıklad funkˇcnosti dan´eho pl´anovac´ıho algoritmu. Ke kaˇzd´emu z tˇechto algoritm˚u budou vytvoˇreny testo- vac´ı ´ulohy, aby se provedly a aby se neprovedly. Pot´e je jejich spr´avnost ovˇeˇrena testovac´ı f´az´ı, ve kter´e budou srovn´any a zhodnoceny z hlediska rychlosti, determinismu, plnˇen´ı dealin˚u a podobnˇe. V´ybˇer pl´anovac´ıch algoritm˚u bude pˇrizp˚usoben moˇznostem vyuˇzit´ı pˇri v´yuce bakal´aˇrsk´eho pˇredmˇetu ”Syst´emy re´aln´eho ˇcasu”(BI-SRC) vyuˇcovan´em na FIT ˇCVUT v Praze.
Pro pr´aci byly vybr´any dva algoritmy dynamick´ych priorit prvn´ı z nich je zaloˇzen na zn´am´em algoritmu Earliest Deadline First (EDF), druh´y je zaloˇzen na novˇejˇs´ım algoritmu Least Laxity First (LLF)
Kapitola 2
Anal´ yza a n´ avrh
Jeden z probl´em˚u pl´anov´an´ıpro syst´emy re´aln´eho ˇcasu je urˇcit, v jak´em poˇrad´ı by se mˇely ´ukoly prov´est, aby byly uspokojeny jejich ˇcasov´e n´aroky a omezen´ı.
Abychom mohli pl´anovat v syst´emu re´aln´eho ˇcasu, potˇrebujeme m´ıt dosta- tek informac´ı, jako je deadline, ˇcas ukonˇcen´ı, pro pˇr´ıpad poruˇsen´ı deadlinu, a jak dlouho trv´a splnˇen´ı kaˇzd´eho ´ukolu. Rovnˇeˇz je dobr´e zn´at d˚uleˇzitost
´ukolu ve srovn´an´ı s ostatn´ımi ´ukoly a z´avislosti dan´e ´ulohy. Vˇetˇsina syst´em˚u pˇredpokl´ad´a, ˇze vˇetˇsina tˇechto informac´ı je k dispozici pˇredem.
Algoritmus pl´anovaˇce v re´aln´em ˇcase lze klasifikovat podle nˇekolika vlast- nost´ı:
1. preemptivn´ı / nepreemptivn´ı chov´an´ı
• Preemptivn´ı: ´Ulohy re´aln´eho ˇcasu m˚uˇzou b´yt pˇreruˇseny, pokud je potˇreba.
• Nepreemptivn´ı: ´Ulohy nem˚uˇzou b´yt pˇreruˇseny.
2. Periodick´e / sporadick´e ˇr´ızen´ı ´ukol˚u
• Periodick´e: Jsou vyd´av´any pravidelnˇe za pevn´e sazby (obdob´ı).
Vˇetˇsina senzorick´eho zpracov´an´ı m´a periodickou povahu. Napˇr´ıklad digit´aln´ı teplomˇer, kter´y mˇeˇr´ı teplotu v pr˚umyslov´e n´adrˇzi, produ- kuje data s pevnou rychlost´ı.
• Sporadick´e: ´Ulohy v re´aln´em ˇcase jsou aktivov´any nepravidelnˇe se zn´amou omezenou rychlost´ı, nen´ı u nich zn´am pˇresn´y pr˚ubˇeh
´ulohy.
3. Statick´e / dynamick´e pl´anov´an´ı priorit:Pˇri pl´anov´an´ı podle priorit je kaˇzd´emu ´ukolu pˇriˇrazena priorita.
• Statick´e: Priorita ´uloh je pˇriˇrazena na zaˇc´atku programu a je stejn´a (statick´a) bˇehem cel´eho bˇehu programu.
2. Anal´yza a n´avrh
• Dynamick´e: Priorita je urˇcov´ana za bˇehu programu v okamˇzic´ıch kde se pl´anovac´ı algoritmus rozhoduje, kterou ´ulohu vybere.
2.1 FreeRTOS
FreeRTOS je operaˇcn´ı syst´em re´aln´eho ˇcasu (RTOS), kter´y je navrˇzen tak, aby byl dostateˇcnˇe mal´y pro provoz na mikrokontrol´eru, i kdyˇz jeho pouˇzit´ı nen´ı omezeno na aplikace mikrokontrol´eru. Projekt FreeRTOS byl zah´ajen v roce 2002 a je v aktivn´ım v´yvoji. Jeho ofici´aln´ı podpora aˇz 35 integro- van´ych syst´emov´ych architektur a r˚uzn´ych v´ıce platformov´ych pˇrekladaˇc˚u, je to jednoduch´y a plnˇe dokumentovan´y API a d´ıky opensourcov´e licenci se velmi rychle rozˇs´ıˇril na voln´em trhu, d´ıky ˇcemuˇz uˇzivatelsk´a z´akladna rok od roku roste. FreeRTOS poskytuje z´akladn´ı funkce pl´anov´an´ı v re´aln´em ˇcase, komunikaci mezi ´ukoly, ˇcasov´an´ı a synchronizaci. Dalˇs´ı funkce, jako napˇr´ıklad rozhran´ı pˇr´ıkazov´e ˇr´adky nebo network stack (s´ıt’ov´y z´asobn´ık), mohou b´yt za- hrnuty jako doplˇnuj´ıc´ı funkce FreeRTOS. Pl´anovaˇc FreeRTOS je preemptivn´ı a zaloˇzen´y na pevn´e prioritˇe. Pˇri inicializaci ´ukolu je pˇriˇrazena priorita jed- notliv´ym ´uloh´am. Pokud m´a v´ıce ´ukol˚u stejnou prioritu, pak ´ulohy jsou rov- nomˇernˇe vyb´ır´any z cyklick´e fronty.
2.1.1 Struktura j´adra
Protoˇze FreeRTOS funguje v prostˇred´ıch vestavn´ych syst´em˚u, je navrˇzen tak, aby minimalizoval vyuˇzit´ıpamˇeti a je tak´e vhodn´y pro mikroprocesory s n´ızkou frekvenc´ı. Pro funkˇcnost potˇrebuje j´adro FreeRTOS pouze tˇri zdrojov´e sou- bory, kter´e dohromady maj´ı m´enˇe neˇz 9000 ˇr´adk˚u k´odu. Aby byl kompatibiln´ı se vˇsemi podporovan´ymi architekturami, tvoˇr´ı j´adro FreeRTOS 2 vrstvy:
1. hardware z´avisl´a: je pˇrizp˚usoben´a pro kaˇzdou podporovanou archi- tekturu
2. hardware nez´avisl´a: je spoleˇcn´a pro vˇsechny porty
Obr´azek 2.1 ukazuje vrstvy FreeRTOS. Poskytuj´ı 3 zdrojov´e soubory, kter´e tvoˇr´ı minim´aln´ı j´adro (spolu s nˇekolika hlaviˇckov´ymi soubory) pro tyto funkce:
Tabulka 2.1: vrstvy
FreeRTOS uˇzivatelsk´e ´ulohy a ISR k´od FreeRTOS hardwarovˇe nez´avisl´y k´od FreeRTOS hardwarovˇe z´avisl´y k´od FreeRTOS hardware
6
2.1. FreeRTOS
• task.c:zde jsou definovan´e ´ulohy, a je zde ˇr´ızen ˇzivotn´ıcyklus programu.
pl´anovac´ı funkce jsou zde tak´e definovan´e.
• queue.c: V tomto souboru jsou definovan´e struktury pouˇz´ıvan´e pro ko- munikaci a synchronizaci ´ukol˚u. ´Ukoly a pˇreruˇsen´ı spolu komunikuj´ı po- moc´ı front. Pomoc´ı front si pˇred´avaj´ı zpr´avy,semafory a z´amky(mutexy), kter´e se pouˇz´ıvaj´ı k synchronizaci kritick´ych sekc´ıch zdroje.
• list.c: je definov´ana datov´a struktura seznam˚u a jejich funkce. Seznamy se pouˇz´ıvaj´ı jak funkcemi ´uloh, tak frontami.
2.1.2 Struktura ´uloh
´Ukoly jsou implementov´any jako funkce v jazyku C. Kaˇzd´y vytvoˇren´y ´ukol je mal´y program s vlastn´ımi pr´avy v r´amci sv´ych pˇriˇrazen´ych priorit. Kaˇzd´y ´ukol se spouˇst´ı sv˚uj vlastn´ı obsah, bez z´avislost´ı na obsahu jin´eho ´ukolu. V kaˇzd´em okamˇziku FreeRTOS vybere ´ukol, kter´y bude spouˇstˇet v z´avislosti na prioritˇe.
U kaˇzd´eho ´ukolu FreeRTOS pˇridruˇz´ı spr´avnou datovou strukturu tzv. Task Control Block (TCB) [2], kter´y obsahuje n´asleduj´ıc´ı parametry:
/* The old naming convention is used to prevent breaking kernel aware debuggers. */
typedef struct tskTaskControlBlock {
/* Points to the location of the last item placed on the tasks stack. THIS MUST BE THE FIRST MEMBER OF THE TCB STRUCT. */
volatile StackType_t * pxTopOfStack;
/* The MPU settings are defined as part of the port layer.
THIS MUST BE THE SECOND MEMBER OF THE TCB STRUCT. */
#if ( portUSING_MPU_WRAPPERS == 1 ) xMPU_SETTINGS xMPUSettings;
#endif
#if ( configUSE_EDF_SCHEDULER == 1 ) TickType_t xTaskPeriod;
#endif
/* The list that the state list item of a task is reference from denotes the state of that task (Ready, Blocked, Suspended ). */
ListItem_t xStateListItem;
/* Used to reference a task from an event list. */
ListItem_t xEventListItem;
/* The priority of the task. 0 is the lowest priority. */
2. Anal´yza a n´avrh
UBaseType_t uxPriority;
/* Points to the start of the stack. */
StackType_t * pxStack;
/* Descriptive name given to the task when created.
Facilitates debugging only. */
/*lint !e971 Unqualified char types are allowed for strings and single characters only. */
char pcTaskName[ configMAX_TASK_NAME_LEN ];
#if ( ( portSTACK_GROWTH > 0 ) ||
( configRECORD_STACK_HIGH_ADDRESS == 1 ) )
/* Points to the highest valid address for the stack. */
StackType_t * pxEndOfStack;
#endif
#if ( portCRITICAL_NESTING_IN_TCB == 1 )
/* Holds the critical section nesting depth for ports that do not maintain their own count in the port layer. */
UBaseType_t uxCriticalNesting;
#endif
#if ( configUSE_TRACE_FACILITY == 1 )
/* Stores a number that increments each time a TCB is created. It allows debuggers to determine when a task has been deleted and then recreated. */
UBaseType_t uxTCBNumber;
/* Stores a number specifically for use by third party trace code. */
UBaseType_t uxTaskNumber;
#endif
#if ( configUSE_MUTEXES == 1 )
/* The priority last assigned to the task -
used by the priority inheritance mechanism. */
UBaseType_t uxBasePriority;
UBaseType_t uxMutexesHeld;
#endif
#if ( configUSE_APPLICATION_TASK_TAG == 1 ) TaskHookFunction_t pxTaskTag;
#endif 8
2.1. FreeRTOS
#if ( configNUM_THREAD_LOCAL_STORAGE_POINTERS > 0 ) void * pvThreadLocalStoragePointers[
configNUM_THREAD_LOCAL_STORAGE_POINTERS ];
#endif
#if ( configGENERATE_RUN_TIME_STATS == 1 )
/* Stores the amount of time the task has spent in the Running state. */
uint32_t ulRunTimeCounter;
#endif
#if ( configUSE_NEWLIB_REENTRANT == 1 )
/* Allocate a Newlib reent structure that is specific to
* this task. Note Newlib support has been included by
* popular demand, but is not used by the FreeRTOS
* maintainers themselves. FreeRTOS is not responsible
* for resulting newlib operation. User must be familiar
* with newlib and must provide system-wide
* implementations of the necessary stubs. Be warned
* that (at the time of writing) the current newlib
* design implements a system-wide malloc() that must
* be provided with locks.
*
* See the third party link
* http://www.nadler.com/embedded/newlibAndFreeRTOS.html
* for additional information. */
struct _reent xNewLib_reent;
#endif
#if ( configUSE_TASK_NOTIFICATIONS == 1 ) volatile uint32_t ulNotifiedValue[
configTASK_NOTIFICATION_ARRAY_ENTRIES ];
volatile uint8_t ucNotifyState[
configTASK_NOTIFICATION_ARRAY_ENTRIES ];
#endif
/* See the comments in FreeRTOS.h with the definition of
* tskSTATIC_AND_DYNAMIC_ALLOCATION_POSSIBLE. */
/*lint !e731 !e9029 Macro has been consolidated for readability reasons. */
#if ( tskSTATIC_AND_DYNAMIC_ALLOCATION_POSSIBLE != 0 )
2. Anal´yza a n´avrh
/* Set to pdTRUE if the task is a statically allocated to ensure no attempt is made to free the memory. */
uint8_t ucStaticallyAllocated;
#endif
#if ( INCLUDE_xTaskAbortDelay == 1 ) uint8_t ucDelayAborted;
#endif
#if ( configUSE_POSIX_ERRNO == 1 ) int iTaskErrno;
#endif } tskTCB;
TCB obsahuje z´akladn´ı informace charakterizuj´ıc´ı danou ´ulohu:
• ukazatele z´asobn´ık˚u*pxStackkter´y ukazuje na zaˇc´atek z´asobn´ıku ´ulohy,
*pxTopOfStackukazuje na m´ısto posledn´ıho vloˇzen´eho pˇredmˇetu z´aso- bn´ıku ´ulohy a*pxEndOfStack, tento ukazuje na m´ısto prvn´ıho vloˇzen´eho pˇredmˇetu, pˇrev´aˇznˇe pouˇz´ıv´an pro kontrolu pˇreteˇcen´ı z´asobn´ıku.
• uxPriorityje promˇenn´a obsahuj´ıc´ıprioritu ´ulohy, kdeˇztouxBasePriority obsahuje posledn´ı pˇridˇelenou prioritu (pouˇzit´y mechanismem pro dˇedˇen´ı priority).
• Objekty typu ListItem\_t xStateListItem a xEventListItem: kdyˇz je ´uloha vloˇzena do listu (napˇr´ıklad list pˇripraven´ych ´uloh, jak uvid´ıme d´ale). Listy neobsahuj´ı jednoduch´y ukazatele na TCB, ale ukazatele na dalˇs´ı objekt stejn´eho datov´eho typu. Pouˇzit´ıListItem\_tn´am zaruˇcuje, ˇze list spravuj´ıc´ı tyto poloˇzky bude mnohem chytˇrejˇs´ı a operace nad n´ım zaberou m´enˇe v´ypoˇcetn´ıho ˇcasu.
• pcTaskNameje statick´e pole obsahuj´ıc´ı jm´eno ´ulohy.
2.1.3 Stavy ´uloh
Jak n´am urˇcuje graf 2.1, ´uloha m˚uˇze existovat pouze v n´asleduj´ıc´ıch stavech
• Bˇeˇz´ı: ´Uloha, na kterou ukazuje syst´emov´a promˇenn´a *pcCurrentTCB, je, jak n´azev napov´ıd´a, v bˇehu. V dan´y okamˇzik m˚uˇze bˇeˇzet pouze jedna
´uloha.
• Pˇripravena: ´Ulohy, kter´e jsou pˇripraveny k bˇehu a ˇcekaj´ı na RTOS k napl´anov´an´ı, ale nic nedˇelaj´ı, jelikoˇz jin´a ´uloha se stejnou nebo vyˇsˇs´ı prioritou moment´alnˇe bˇeˇz´ı.
10
2.1. FreeRTOS
Obr´azek 2.1: Graf stav˚u a pˇrechod˚u ´ulohy [FreeRTOS.org]
• Blokovan´a: ´Uloha v tomto stavu nem˚uˇze b´yt pl´anov´ana, protoˇze ˇcek´a na z´asah zvenˇc´ı nebo ˇcasem z´avislou ud´alost. Napˇr´ıklad: ´uloha po za- vol´an´ı metodyvTaskDelay(TickType\_t)se sama zablokuje a ˇcek´a, aˇz od syst´emu pˇrijde ud´alost o uplynul´em ˇcase, nebo ´uloha m˚uˇze ˇcekat na semaforu, neˇz dokonˇc´ısvoj´ırutinu jin´a ´uloha a poˇsle ud´alost o dokonˇcen´ı.
• Pozastaven´a: ´Uloha se do tohoto stavu m˚uˇze dostat pouze zavol´an´ım metodvTaskSuspend()[3] avTaskResume()[3]. ´Ulohy ve stavu zadrˇzen´ı nemohou b´yt pl´anov´any.
TCB neobsahuje promˇenou, kter´a pˇr´ımo reprezentuje stav dan´e ´ulohy, m´ısto toho FreeRTOS obsluhuje list obsahuj´ıc´ı, ´ulohy pro kaˇzd´y ze stav˚u (Pˇripravena, Blokovan´a a Pozastavena), proto ´ulohy mohou b´yt implicitnˇe sledov´any tak, ˇze vloˇz´ıme danou ´ulohu do dan´eho listu.
2. Anal´yza a n´avrh
• Pˇripraven´e ´ulohy:
PRIVILEGED_DATA static List_t
pxReadyTasksLists[ configMAX_PRIORITIES ];
/*< Prioritised ready tasks. */
pxReadyTasksLists[] je pole list˚u, obsahuj´ıc´ı tolik list˚u, kolik je na- konfigurovan´ych priorit. I-t´a pozice n´am urˇcuje list ´uloh s prioritou i.
• Blokovan´e ´ulohy:
/* Delayed tasks (two lists are used - one for delays that have overflowed the current tick count. */
PRIVILEGED_DATA static List_t xDelayedTaskList2;
/* Points to the delayed task list currently being used. */
PRIVILEGED_DATA static List_t * volatile pxDelayedTaskList;
/* Points to the delayed task list currently being used to hold tasks that have overflowed the current tick count.
*/
PRIVILEGED_DATA static List_t * volatile
pxOverflowDelayedTaskList;
/* Tasks that have been readied while the scheduler was suspended. They will be moved to the ready list when the scheduler is resumed. */
PRIVILEGED_DATA static List_t xPendingReadyList;
• Pozastaven´e ´ulohy:
/*< Tasks that are currently suspended. */
PRIVILEGED_DATA static List_t xSuspendedTaskList;
jednoduch´y list obsahuj´ıc´ı pozastaven´e ´ulohy.
2.1.4 Inicializace ´uloh
´Uloha je vytv´aˇrena zavol´an´ım metodyxTaskCreate()[2.2] ze souborutask.c xTaskCreate()vytv´aˇr´ı novou ´ulohu s pˇriˇrazenou prioritou a vloˇz´ı ji do listu pˇripraven´ych ´uloh. Podrobnˇe se ´uloha vytv´aˇr´ı takto:
12
2.1. FreeRTOS Obr´azek 2.2: xTaskCreate
BaseType_t xTaskCreate( TaskFunction_t pxTaskCode,
/* lint !e971 Unqualified char types are allowed for strings and single
characters only. */
const char * const pcName,
const configSTACK_DEPTH_TYPE usStackDepth, void * const pvParameters,
UBaseType_t uxPriority,
TaskHandle_t * const pxCreatedTask )
#if ( portSTACK_GROWTH > 0 ) {
pxNewTCB = ( TCB_t * ) pvPortMalloc( sizeof( TCB_t ) );
if( pxNewTCB != NULL ) {
pxNewTCB->pxStack = ( StackType_t * ) pvPortMalloc(
( ( ( size_t ) usStackDepth )
* sizeof( StackType_t ) ) );
if( pxNewTCB->pxStack == NULL ) { vPortFree( pxNewTCB );
pxNewTCB = NULL;
} } }
#else /* portSTACK_GROWTH */
{
StackType_t * pxStack;
pxStack = pvPortMalloc( ( ( ( size_t ) usStackDepth ) * sizeof( StackType_t ) ) );
if( pxStack != NULL ) {
/* Allocate space for the TCB. */
pxNewTCB = ( TCB_t * ) pvPortMalloc( sizeof( TCB_t ) );
if( pxNewTCB != NULL ){
/* Store the stack location in the TCB. */
pxNewTCB->pxStack = pxStack;
} else {
vPortFree( pxStack );
} } else {
2. Anal´yza a n´avrh
pxNewTCB = NULL;
} }
#endif /* portSTACK_GROWTH */
pamˇet’ov´y prostor je vyhrazen pro novou TCB strukturu a jej´ı z´asobn´ık, pokud je dostateˇcnˇe voln´eho prostoru na pamˇeti. K´od vˇcetnˇe pozn´amek se nach´az´ı v souborutask.c.
/*
* Called after a Task_t structure has been allocated either
* statically or dynamically to fill in the structure’s members.
*/
static void prvInitialiseNewTask( TaskFunction_t pxTaskCode, const char * const pcName, const uint32_t ulStackDepth, void * const pvParameters, UBaseType_t uxPriority, TaskHandle_t * const pxCreatedTask, TCB_t * pxNewTCB,
const MemoryRegion_t * const xRegions ) PRIVILEGED_FUNCTION;
TCB promˇenn´e a z´asobn´ık jsou zde inicializov´any, nov´y z´asobn´ık dan´e ´ulohy je inicializov´an ve stejn´em duchu jako z´asobn´ık pro ´ulohy pozastaven´e pl´anovaˇcem.
T´ımto zp˚usobem pl´anovaˇc nepotˇrebuje ˇreˇsit inicializaci jako speci´aln´ı pˇr´ıpad pro ˇr´ızen´ı ´uloh, kdyˇz tyto dvˇe ˇreˇsen´ı vypadaj´ı stejnˇe, jako pˇri inicializaci uspan´ych ´uloh. Metoda prvInitialiseNewTask()je hardwarovˇe z´avisl´a, a proto je implementov´ana v dan´em port.c souboru pro danou architekturu.
Jak brzy uvid´ıme, kdyˇz ´uloha je pˇreruˇsena, vˇsechen obsah ´ulohy je uloˇzen na z´asobn´ık. Takˇze novˇe vytvoˇren´y z´asobn´ık je upraven, a pˇresto vypad´a, jako kdyby nov´e registry byly vloˇzeny, pˇrestoˇze z´asobn´ık nebyl jeˇstˇe pouˇzit.
prvAddTaskToReadyList( pxTCB )
je makro, kter´e po zavol´an´ı vloˇz´ı novˇe vytvoˇrenou ´ulohu do patˇriˇcn´eho prio- ritn´ıho listupxReadyTasksList[]. Jak bylo ˇreˇceno dˇr´ıve, pole
pxReadyTasksList[]obsahuje jeden list pro kaˇzdou prioritu, kterou syst´em m´a nastavenou, kde 0 je nejmenˇs´ı priorita. ´Uloha s prioritoup bude zaˇrazen´a do pˇr´ısluˇsn´eho listupxReadyTasksList[p].prvAddTaskToReadyList()je de- finov´an takto:
#define prvAddTaskToReadyList( pxTCB ) \
traceMOVED_TASK_TO_READY_STATE( pxTCB ); \
taskRECORD_READY_PRIORITY( ( pxTCB )->uxPriority ); \ vListInsertEnd( &( pxReadyTasksLists[ \
( pxTCB )->uxPriority ] ), \ 14
2.1. FreeRTOS
&( ( pxTCB )->xStateListItem ) ); \ tracePOST_MOVED_TASK_TO_READY_STATE( pxTCB )
V z´asadˇe, promˇenn´aUBaseType_t uxTopReadyPriority, reprezentuj´ıc´ıv kaˇz- d´em okamˇziku prioritu ´ulohy v bˇehu, je porovn´ana s prioritou nov´e ´ulohy, a po- kud je tato nov´a priorita vyˇsˇs´ı, takuxTopTaskReadyPriorityje aktualizov´an na novou prioritu. Pot´e,xStateListItemje vloˇzena na konec pˇr´ısluˇsn´eho pri- oritn´ıho listu v poli pxReadyTasksList[].
´Uloha je nyn´ı vytvoˇrena a pˇripravena na spuˇstˇen´ı pl´anovaˇcem ´uloh.
2.1.5 Usp´an´ı ´uloh
Jiˇz v´ıme, jak funguje vytvoˇren´ı ´uloh a jej´ı inicializace do stavu Ready. Nyn´ı se pod´ıv´ame na to, jak se ´uloha m˚uˇze dostat do stavu Blokovan´a vol´an´ım metodyxTaskDelayUntil(). Tato metoda definuje frekvenci, pˇri jak´e se ´ulohy periodicky spouˇstˇej´ı, takˇze m˚uˇze b´yt pouˇzita pro implementaci periodick´ych
´uloh. Jak uvid´ıme, FreeRTOS mˇeˇr´ıˇcas periodick´ym inkrementov´an´ım hodnotu v promˇenn´e xTickCount.xTaskDelayUntil() pˇresune ´ulohu volaj´ıc´ı metodu do pxDelayedTaskList, kde ˇcek´a, neˇz pˇrijde neˇz pˇrijde ud´alost, a n´aslednˇe je pˇresunuta do xReadyTasksList[] periodicky.
\*
* @param pxPreviousWakeTime Pointer to a variable that holds the
* time at which the task was last unblocked. The variable must
* be initialised with the current time prior to its first use
* (see the example below). Following this the variable is
* automatically updated within xTaskDelayUntil ().
*
* @param xTimeIncrement The cycle time period. The task will be
* unblocked at time *pxPreviousWakeTime + xTimeIncrement. Calling
* xTaskDelayUntil with the same xTimeIncrement parameter value
* will cause the task to execute with a fixed interface period.
*\
Metoda pracuje t´ımto zp˚usobem:
uxListRemove( &( pxCurrentTCB->xStateListItem )
pxCurrentTCBje ukazatel na ´ulohu v bˇehu, kter´a si zavolalavTaskDelayUntil(), takˇze jej´ıxStateListItem je vymaz´an z listu pˇripraven´ych ´uloh, ve kter´em byl p˚uvodnˇe uloˇzen.
2. Anal´yza a n´avrh
listSET_LIST_ITEM_VALUE( &( pxCurrentTCB->xStateListItem ), xTimeToWake );
xStateListItemnyn´ı obsahuje hodnotu kdy bude odblokov´an.
vListInsert( pxDelayedTaskList, &( pxCurrentTCB->xStateListItem ) );
xStateListItem je n´aslednˇe vloˇzen do pxDelayedTaskList, jenˇz obsahuje xStateListItem vˇsech ´uloh, kter´e jsou moment´alnˇe blokovan´e a seˇrazen´e podle ˇcasu odblokov´an´ı. Tud´ıˇz pxDelayedTaskList m´a vˇzdy na prvn´ı po- zici
xStateListItem´ulohy, kter´e budou v nejbliˇzˇs´ıdobˇe odblokov´ana.vListInsert() vkl´ad´a poloˇzky do listu tak, aby zachovala jejich ˇrazen´ı.
/* If the task entering the blocked state was placed at the
* head of the list of blocked tasks then xNextTaskUnblockTime
* needs to be updated too. */
if( xTimeToWake < xNextTaskUnblockTime ) {
xNextTaskUnblockTime = xTimeToWake;
}
nakonec syst´emov´a promˇenn´axNextTaskUnblockTimeobsahuje hodnotu ˇcasu, kdy bude zavol´ana metoda pro odblokov´an´ıprocesu, pokud je potˇreba. V tento okamˇzik je potˇreba definovat pˇrep´ın´an´ıkontextu. Hardwarovˇe specifick´a funkce portYIELD_WITHIN_API()je vol´ana, a ´uloha s nejvyˇsˇs´ıprioritou z listu pˇripraven´ych
´uloh je povol´ana do bˇehu. V dalˇs´ı sekci se zamˇeˇr´ıme na to, jak je kontext pˇrep´ın´an.
2.1.6 Pˇrep´ın´an´ı kontextu
Pˇrep´ın´an´ı kontextu mus´ı prob´ıhat transparentn´ım zp˚usobem, pokud jde o pˇr´ı- sluˇsn´e ´ukoly. Ve skuteˇcnosti ´ukol nev´ı, kdy bude pozastaven nebo znovu spuˇstˇen syst´emem, m˚uˇze klidnˇe pokraˇcovat ve sv´em bˇehu, jako kdyby nedoˇslo k ˇz´adn´emu pˇrepnut´ı kontextu. Je starost´ı operaˇcn´ıho syst´emu aby, ˇze kdyˇz bˇeˇz´ıc´ı ´uloha je pozastavena, aby jej´ı obsah by mˇel b´yt uloˇzen v jej´ım z´asobn´ıku, a bylo pˇripraveno jej´ı obnoven´ı, kdyˇz se ´uloha znovu spust´ı.
Obr´azek 2.3 ukazuje, jak ´ukol bˇeˇz´ı. Registr ukazatele z´asobn´ıku (SP) uka- zuje na z´asobn´ık bˇeˇz´ıc´ı ´uloh, registr ˇc´ıtaˇce programu (PC) ukazuje na dalˇs´ı in- strukci v k´odu ´ulohy a registry CPU jsou pouˇz´ıv´any ´ulohou. portSAVE_CONTEXT() je hardwarov´a funkce zodpovˇedn´a za ukl´ad´an´ı obsahu ´uloh. Registry PC a SP spolu s dalˇs´ımi registry jsou vloˇzeny do z´asobn´ıku ´ulohy. Obr´azek 2.4 ukazuje z´asobn´ık ´ulohy po uloˇzen´ı obsahu ´ulohy na z´asobn´ık. J´adrem si uloˇz´ı kopii SP 16
2.1. FreeRTOS
Obr´azek 2.3: Kontext spouˇstˇen´ı ´ulohy [FreeRTOS.org]
Obr´azek 2.4: Z´asobn´ık ´ulohy po uloˇzen´ı kontextu [FreeRTOS.org]
2. Anal´yza a n´avrh
a operaˇcn´ı syst´em si ukl´ad´a SP vˇsech pozastaven´ych ´uloh, aby si je mohly naˇc´ıst pˇri obnoven´ı ´ukol˚u.
Kontext ´ulohy je obnoven funkc´ıportRESTORE_CONTEXT(), j´adro pak naˇcte SP ´ulohy, kter´a mˇela v sobˇe z´aznam o probuzen´ı, n´aslednˇe je obsah uloˇzen´e
´ulohy vloˇzen zpˇet do spr´avn´ych registr˚u procesor˚u.
2.1.7 Syst´em tik˚u
Uˇz jsme vidˇeli, ˇze kdyˇz je vol´ana funkce xTaskDelayUntil(), volaj´ıc´ı ´uloha urˇc´ı ˇcas, ve kter´em vyˇzaduje sv´e probuzen´ı. FreeRTOS mˇeˇr´ı ˇcas pomoc´ı sys- t´emov´e promˇenn´e xTickCount. Pˇreruˇsen´ı tikem aktivuje Interrupt Service Routine (ISR), kter´a inkrementuje promˇenouxTickCount s pˇr´ısnou ˇcasovou pˇresnost´ı, coˇz umoˇzˇnuje syst´emu re´aln´eho ˇcasu mˇeˇrit ˇcas pˇri zvolen´e frekvenci pˇreruˇsen´ı. Pokaˇzd´e, kdyˇz se inkrementuje promˇenn´a xTickCount, operaˇcn´ı syst´em mus´ı zkontrolovat, zda je ˇcas probudit ´ukol. Je moˇzn´e, ˇze ´ukol pro- buzen´y bˇehem ISR bude m´ıt vyˇsˇs´ı prioritu neˇz priorita pˇreruˇsen´eho ´ukolu.
Pokud k tomu dojde, ISR by mˇel vr´atit novˇe probuzenou ´ulohu. Kdyˇz jsou
´ulohy vr´aceny t´ımto zp˚usobem, tam m˚uˇzeme o syst´emu ˇr´ıct, ˇze syst´em je nutnˇe preemptivn´ı. N´ıˇze bude pops´ana funkce ISR ze souboru port.c:
static void vPortSystemTickHandler( int sig ) {
Thread_t *pxThreadToSuspend;
Thread_t *pxThreadToResume;
uint64_t xExpectedTicks;
/* Signals are blocked in this signal handler. */
uxCriticalNesting++;
#if ( configUSE_PREEMPTION == 1 )
pxThreadToSuspend = prvGetThreadFromTask(
xTaskGetCurrentTaskHandle() );
#endif
/* Tick Increment, accounting for any lost signals or drift in
* the timer. */
xTaskIncrementTick();
#if ( configUSE_PREEMPTION == 1 ) /* Select Next Task. */
vTaskSwitchContext();
pxThreadToResume = prvGetThreadFromTask(
xTaskGetCurrentTaskHandle() );
prvSwitchThread(pxThreadToResume, pxThreadToSuspend);
#endif
uxCriticalNesting--;
}
18
2.1. FreeRTOS prvn´ı vˇec, kterou vPortSystemTickHandler() udˇel´a, je to, ˇze si uloˇz´ı obsah metodou pxThreadToSuspend = prvGetThreadFromTask( ), pak dvˇe hard- warovˇe nez´avisl´e funkce jsou vol´any.
• xTaskIncrementTick()inkrementuje syst´emovou promˇennouxTickCount a zkontroluje, jestli je ˇcas ´ulohu opˇet probudit ze stavu Blokovan´a do stavuPˇripraven´e. Pokud ano, pak ´uloha je odebr´ana zpxDelayedTaskList a je pˇresunuta do patˇriˇcn´ehopxReadyTasksLists[]. Funkce vr´at´ıpdTRUE, pokud stejn´e ´ulohy jsou probuzeny, aby mohly d´at ISR vˇedˇet, jestli je potˇreba pˇrep´ın´an´ı kontextu.
• vTaskSwitchContext()nastav´ı*pxCurrentTCBdo TCB ´ulohy s nejvˇetˇs´ı prioritou uloˇzenou v pxReadyTasksLists[]
Nakonec funkce:
pxThreadToResume = prvGetThreadFromTask( xTaskGetCurrentTaskHandle() );
n´am obnov´ı obsah ze z´asobn´ıku ´ulohy, na kterou ukazuje *pxCurrentTCB. 2.1.8 Uk´azka pl´anov´an´ı
V t´eto sekci je uk´az´an pˇr´ıklad preemptivn´ıho pl´anov´an´ı ve FreeRTOS. Prvn´ı obr´azek 2.5 n´am zad´av´a modelovou situaci k pˇredstavˇe. Mˇejme tedy jiˇz bˇeˇz´ıc´ı, kde jsou ˇctyˇri n´ami zadefinovan´e ´ulohy, z toho pouze tˇri jsou periodick´e a jedna (tskD) je spouˇstˇena vnˇejˇs´ı ud´alost´ı. Syst´em je moment´alnˇe v p´at´em tiku a prov´ad´ısetskD, ´ulohytskAatskBˇcekaj´ına sv˚uj ˇcas vzbuzen´ı. V okamˇzik, kdy pˇrijde syst´em k tiku 8 (obr´azek 2.6), ´ulohatskAse vloˇz´ıdo prioritn´ıfronty pxReadyTasksList[2] a z´aroveˇn je odebr´an z listu ˇcekaj´ıc´ıch ´uloh. Vloˇzen´ım
´ulohytskAdopxReadyTasksList[2]se doc´ıl´ı toho, ˇze ´ulohatskDˇcek´a, neˇz se dokonˇc´ı vˇsechny ´ulohy vpxReadyTasksList[2]. T´ımto zp˚usobem se FreeR- TOS dos´ahl toho, ˇze je preemptivn´ı. V tiku deset (obr´azek 2.7) se jiˇz zvl´adla zpracovat ´uloha tskD a tskA, ta se vˇsak, na rozd´ıl od ´ulohy tskD, kter´a nen´ı periodick´a, vr´atila do listu ˇcekaj´ıc´ıch ´uloh, kde ˇcek´a na sv˚uj nov´y ˇcas spuˇstˇen´ı. V tomto okamˇziku se zpracov´av´a ´uloha tskC. Po zpracov´an´ı vˇsech
´uloh v obr´azku 2.8 se v tiku 14 nach´az´ıme na mal´y moment situaci, kde ˇz´adn´a
´uloha nen´ı vol´ana a n´aˇs ukazatel pxCurrentTCB zpracov´av´a pouze dummy
´ulohy IDLE, jelikoˇz v listu nejniˇzˇs´ı priority je jedin´a. Zde je n´azornˇe vidˇet, ˇze o pl´anovaˇci dod´avan´e dodavatelem je drobn´a forma RMS, jelikoˇz jsou na- staveny priority staticky na zaˇc´atku pl´anov´an´ı a syst´em je preemptivn´ı, pouze syst´em nehl´ıd´a ani nedefinuje deadliny ´uloh.
2. Anal´yza a n´avrh
Obr´azek 2.5: Pˇr´ıklad interakce pˇrep´ın´an´ı obsahu ´uloh
Obr´azek 2.6: Pˇr´ıklad interakce pˇrep´ın´an´ı obsahu ´uloh
20
2.1. FreeRTOS
Obr´azek 2.7: Pˇr´ıklad interakce pˇrep´ın´an´ı obsahu ´uloh
Obr´azek 2.8: Pˇr´ıklad interakce pˇrep´ın´an´ı obsahu ´uloh
2. Anal´yza a n´avrh
2.2 EDF
Prvn´ı pl´anovaˇc, kter´y implementujeme, je zaloˇzen na algoritmu Earliest De- adline First (EDF). EDF pˇrij´ım´a z´asady preemptivn´ıho pl´anov´an´ı zaloˇzen´e na dynamick´ych priorit´ach, coˇz znamen´a, ˇze priorita ´ukolu se m˚uˇze bˇehem jeho spuˇstˇen´ı zmˇenit a zpracov´av´an´ı kter´ehokoli ´ukolu m˚uˇze b´yt pˇreruˇseno na ˇz´adost o proveden´ı ´ukolu s vyˇsˇs´ı prioritou.
Algoritmus pˇriˇrazuje priority ´ukol˚um jednoduch´ym zp˚usobem: priorita
´ukolu je inverznˇe ´umˇern´a jeho absolutn´ımu deadlinu. Jin´ymi slovy, nejvyˇsˇs´ı prioritu m´a ´uloha, kter´a m´a v aktu´aln´ı okamˇzik deadline nejdˇr´ıve. V pˇr´ıpadˇe dvou nebo v´ıce ´ukol˚u se stejn´ym deadlinem a z´aroveˇn pˇri splnˇen´ı podm´ınky pro ´uspˇeˇsn´e napl´anov´an´ı se mezi nimi vyb´ır´a n´ahodnˇe.
Algoritmus je vhodn´y pro pr´aci v prostˇred´ı, kde plat´ı tyto pˇredpoklady (jsou stejn´e jako u RMS):
1. Poˇzadavky pro ´ulohy s hard deadliny jsou periodick´e.
2. ´Ulohy jsou nez´avisl´e (ˇz´adn´e vz´ajemn´e vylouˇcen´ı nebo precedenˇcn´ı ome- zen´ı).
3. Deadline intervaly (relativn´ı deadliny) Di jsou stejn´e jako periodypi. 4. Doba v´ypoˇctuci je pˇredem zn´am´a a konstantn´ı.
5. Dobu pro pˇrepnut´ı kontextu je moˇzn´e zanedbat.
D´ıky tˇemto pˇredpoklad˚um m˚uˇzeme ´ukol charakterizovat pouze pomoc´ı2 vlast- nost´ı, a to periodou pi a dobou v´ypoˇctu ci. Pouˇzijeme T1, T2, . . . , Tn pro oznaˇcen´ın periodick´ych ´uloh (T´ask˚u), k nim pˇriˇrazen´e jejich periodyp1, p2, . . . , pn a doby v´ypoˇct˚uc1, c2, . . . , cn. Takˇze ´ulohaTije spouˇstˇena s periodoupia mˇela by zkonzumovatci ˇcasov´ych jednotek pˇred t´ım, neˇz dojde ke sv´emu deadlinu, tud´ıˇz pˇri ukonˇcen´ı ´ulohy by mˇelo platit (ci≤i).
[4]Proto si zadefinujeme postaˇcuj´ıc´ı podm´ınku pro pl´anovatelnost ´uloh takto:
Vˇeta 1 Ulohy pl´anovan´e pomoc´ı algoritmu jsou pl´anovateln´e pokud plat´ı podm´ınka:´
µ=
N
X
i=1
ci pi
≤1
Nuˇze pojd’me uvaˇzovat, ˇze m´ame n´asleduj´ıc´ı dvˇe ´ulohy: A : c1 = 2, p1 = 8 aB :c2 = 3, p1 = 5
µ= 2 8 +3
5 = 34
40 = 0.85≤1 22
2.3. LLF
Obr´azek 2.9: Pl´anov´an´ı ´uloh v EDF [BI-SRC]
2.2.1 Uk´azka pl´anov´an´ı
s odkazem na vˇetu 1, EDF pl´anovac´ı algoritmu je schopen obslouˇzit vˇsechny
´ukoly, aniˇz by byly poruˇseny deadliny nˇekter´e z ´uloh. Obr´azek 2.9 n´am popi- suje, jak ´ulohyT1 = AaT2 = Bjsou pl´anov´any. V ˇcaset= 3 ´uloha B dokonˇc´ı svoj´ı rutinu a je napl´anov´ana ´uloha A, a tak to pokraˇcuje d´al a d´al. . .V ˇcase t= 3 se rozhoduje mezi pokraˇcov´an´ım v ´uloze B, nebo jestli zah´ajit ´ulohu A, protoˇze ´uloha B m´a v dan´y ˇcas vˇetˇs´ı prioritu, tak se pokraˇcuje v bˇehu ´ulohy B. Takto se pokraˇcuje d´al aˇz do nekoneˇcna. Priorita by se zde poˇc´ıtala jako Pi=pi. To je vˇse k tomto pˇr´ıkladu z pˇredn´aˇsek BI-SRC [5]
2.3 LLF
Least Laxity First algoritmus je, stejnˇe jako algoritmu EDF, urˇcen pro jedno- procesorov´e zaˇr´ızen´ı, i kdyˇz se daj´ı pouˇz´ıt i na multiprocesorov´ych syst´emech, pˇresto nen´ı jejich pouˇzit mimo jednoprocesorov´e zaˇr´ızen´ı optim´aln´ı. V tomto algoritmu se pˇriˇrazuje priorita na z´akladˇe nejmenˇs´ı laxity. Laxitu si m˚uˇzeme pˇredstavit jako volnost v tom, na jak dlouho se m˚uˇze ´uloha odloˇzit, aniˇz bychom poruˇsili jej´ı zpracov´an´ı v r´amci periody, ˇcili [6]:
Li(t) =Di(t)−Ci(t)
, kde Li(t) je laxita procesu i v ˇcase t, Di(t) je kolik ˇcasu zb´yv´a do deadlinu procesu i v ˇcase t,Ci(t) je ˇcas, kter´y uˇz se na ´uloze jeˇstˇe potˇrebuje odpracovat v ˇcase t nebo tak´e WCET (Worst Case Execution Time).
WCET Ci(t) lze tak´e zn´azornit jako Ci(t) = ti+ci a po dosazen´ı n´am vznikne formule:
Li(t) =Di(t)−(ti+ci) .
2.3.1 Uk´azka pl´anov´an´ı
Zde si uk´aˇzeme na typicky ˇskoln´ım pˇr´ıkladu, jak algoritmus pl´anov´an´ı LLF se vypoˇr´ad´av´a s prioritami. Tud´ıˇz uvaˇzujme n´asleduj´ıc´ı pˇr´ıklad tˇr´ı ´uloh:
• ´Uloha A (T1), kde ˇcas zpracov´an´ı jecA= 2 a perioda pA= 7
• ´Uloha B (T2), kde ˇcas zpracov´an´ı jecB = 2 a perioda pA= 5
2. Anal´yza a n´avrh
Obr´azek 2.10: Pl´anov´an´ı ´uloh v LLF [BI-SRC]
• ´Uloha C (T3), kde ˇcas zpracov´an´ı jecC = 1 a perioda pA= 3
Tak v obr´azku 2.10 je zn´azornˇen´e, jak se chovaj´ı jednotliv´e ´ulohy, a pak v ˇr´adku LLF reprezentuj´ıc´ı jednoprocesorov´e vl´akno v naˇsem FreeRTOS. D´ale je spoˇc´ıtan´a laxita pro jednotliv´e ´ulohy v dan´y ˇcasov´y okamˇzik, kde p´ısmenem xzn´azorˇnuji sp´ıc´ı ´ukol, ˇcekaj´ıc´ı na zpracov´an´ı v dalˇs´ı periodˇe. Jako reprezen- tativn´ı a vysvˇetluj´ıc´ı pˇr´ıklad si zvol´ım ˇcas 16 a ten tady podrobnˇeji projdu.
V tomto okamˇziku se k n´am po sp´anku vr´atily ´ulohy B a C, zde tyto dvˇe ´ulohy maj´ı laxitu stejnou s laxitou, kterou mˇeli na zaˇc´atku programu, ˇcili laxita C jeLC = 19−(16 + 1), a toLC = 2, stejn´ym zp˚usobem se dostanem k v´ysledku ´ulohy B a ta n´am vyjdeLB= 3. Ted’ spoˇc´ıt´ame, jak vypad´a laxita
´ulohy A, ta na rozd´ıl od ostatn´ıch nezaˇcala v dan´y okamˇzik a v ˇcase 15 se nedok´azala napl´anovat, ale princip poˇc´ıt´an´ı laxity se nemˇen´ı, proto se na ni pojd’me pod´ıvat. Laxita ´ulohyLA= 22−(16+2), a tak dost´av´ame laxitu ´ulohy A. Nyn´ı porovn´ame laxity a z´ısk´ame v´ytˇeze naˇseho pl´anov´an´ı, t´ım se st´av´a
´uloha C s laxitou 2. V ˇcasov´em okamˇziku 16 se napl´anuje ´uloha C a stejn´ym zp˚usobem se z´ısk´av´a napl´anovan´a ´uloha i v n´asleduj´ıc´ıch kroc´ıch.
24
Kapitola 3
Implementace
V t´eto kapitole se zamˇeˇr´ıme na implementaci testovac´ıch soubor˚u, modi- fikac´ı jiˇz existuj´ıc´ıch metod ze souboru task.c, o kter´ych jiˇz bylo zm´ınˇeno v pˇredchoz´ıch kapitol´ach. Na rozd´ıl od tradiˇcn´ı implementace na pˇr´ıpravek, bude se implementovat vˇse nad POSIXov´ym portem dod´avan´y FreeRTOS.org z tˇret´ı strany. D´ıky POSIXov´emu portu se nemus´ıme limitovat pˇri imple- mentaci pouze na porty pˇr´ıpravk˚u a operaˇcn´ım syst´emem Windows. Apli- kace je tedy jednoduˇse spustiteln´a a kompilovateln´a na linuxov´ych operaˇcn´ıch syst´emech. Prim´arnˇe je tato pr´ace otestov´ana na operaˇcn´ım syst´emu Ubuntu 20.04 LTS a tud´ıˇz bezprobl´emov´y provoz na jin´ych operaˇcn´ıch syst´emech nen´ı zaruˇcen.
3.1 EDF
V pˇredchoz´ı kapitole bylo zm´ınˇeno, ˇze FreeRTOS pouˇz´ıv´a pl´anovaˇc zaloˇzen´y na statick´ych priorit´ach. C´ıl v t´eto sekci je jasn´y, a to popsat, jak se d´a imple- mentovat EDF pl´anovac´ı algoritmus do FreeRTOSu pouˇz´ıvaj´ıce jiˇz existuj´ıc´ı struktury, kter´e n´am FreeRTOS nab´ız´ı, ˇci pˇr´ıpadnˇe doplnit o sv´e struktury.
N´apad je takov´y, ˇze vytvoˇr´ıme nov´y listxReadyTaskListEDF(obr´azek 3.1), ve kter´em budeme spravovat priority naˇsich ´uloh. Tento nov´y list bude obsahovat
´ulohy seˇrazen´e podle naˇs´ı dynamick´e priority vzestupnˇe, kde pozice v tomto listu bude reprezentovat prioritu a na prvn´ı pozici bude naˇse moment´alnˇe spouˇstˇen´a ´uloha. Zbytek architektury FreeRTOSu je zachov´an a m´ısty se vy- skytuj´ı drobn´e ´upravy. V n´asleduj´ıc´ıch ˇc´ast´ı t´eto sekce budou uk´az´any ˇc´asti k´odu t´eto pr´ace. Pro naˇsi pr´aci si m˚uˇzeme st´ale pˇredpokl´adat platnost naˇsich pˇredpoklad˚u: Veˇsker´e zde zm´ınˇen´e zmˇeny v k´odu budou referovat na obsah souboru task.c, jelikoˇz definice a struktury pˇrenosn´eho pl´anovaˇce jsou zadefi- nov´any zde. Abychom si dodrˇzeli konzistenci s souboremtask.c, bude veˇsker´y k´od obalen v prostˇred´ı podm´ınˇen´eho pˇreklad, kde budeme kontrolovat nasta- ven´ı definiceconfigUSE_EDF_SCHEDULER. Tato definice je vloˇzena do souboru FreeRTOSConfig.h. Kdyˇz tato definice bude nastavena, pak FreeRTOS bude
3. Implementace
Obr´azek 3.1: Nov´y list obsahuje ´ulohy seˇrazen´e vzestupnˇe podle vzr˚ustaj´ıc´ıho deadlinu. Na prvn´ı pozici se nach´az´ı ´uloha s nejbliˇzˇs´ım deadlinem.
26
3.1. EDF
• Poˇzadavky pro ´ulohy s hard deadliny jsou periodick´e.
• ´Ulohy jsou nez´avisl´e (ˇz´adn´e vz´ajemn´e vylouˇcen´ı nebo precedenˇcn´ı ome- zen´ı).
• Deadline intervaly (relativn´ı deadliny) Di jsou stejn´e jako periody pi.
• Doba v´ypoˇctu ci je pˇredem zn´am´a a konstantn´ı.
• Dobu pro pˇrepnut´ı kontextu je moˇzn´e zanedbat.
Obr´azek 3.2: Zde zobrazuji bˇeˇz´ıc´ı ´ulohu C a jej´ı deadline v tiku 9
3. Implementace
Obr´azek 3.3: Zde mechanizmus vzbud´ı ´ulohu A a vloˇz´ı ji do listu pˇripraven´ych
´uloh. Z´aroveˇn ji odebereme z listu ˇcekaj´ıc´ıch ´uloh. Do listu pˇripraven´ych ´uloh ji vloˇz´ıme na m´ısto, tak aby jej´ı deadline byl seˇrazen vzestupnˇe v˚uˇci ostatn´ım
´uloh´am. Deadline byl vypoˇc´ıt´an jako Di =t+pi
pouˇz´ıvat pl´anovaˇc EDF, v opaˇcn´em pˇr´ıpadˇe bude pracovat jak v origin´aln´ım stavu.
Nejdˇr´ıve si zadefinujeme naˇs´ı novou pˇredpokl´adanou strukturu listu xReadyTasksListEDF
#if ( configUSE_EDF_SCHEDULER == 1 )
PRIVILEGED_DATA static List_t xReadyTasksListEDF;
/*< Ready tasks in order by their deadline */
#endif
Pak si pˇrid´ame do metody prvInitialiseTaskLists(), pˇrid´ame k´od pro inicializaci naˇseho nov´eho listu. Metodu modifikujeme takto:
28
3.1. EDF
Obr´azek 3.4: ´Uloha C ukonˇcila sv˚uj bˇeh a pˇresunula se do listu ˇcekaj´ıc´ıch ´uloh.
´Uloha D je nyn´ı na zaˇc´atku listu a bude spuˇstˇena.
static void prvInitialiseTaskLists( void ) {
...
// < initialise task ready list
#if ( configUSE_EDF_SCHEDULER == 1) {
vListInitialise( &xReadyTasksListEDF );
}
#endif ...
}
Dalˇs´ı zmˇenu provedeme v makruprvAddTaskToReadyList(), kter´a slouˇz´ı pro pˇrid´an´ı ´ulohy do listu pˇripraven´ych ´uloh. Zmˇenu provedeme n´asledovnˇe:
3. Implementace
/*
* There shoudl be all of the modification of how to add task
* to its list
*/
#if ( configUSE_EDF_SCHEDULER == 1 )
#define prvAddTaskToReadyList( pxTCB ) \
listSET_LIST_ITEM_VALUE( &( \
( pxTCB )->xStateListItem ), \ ( pxTCB )->xTaskPeriod + xTickCount); \ vListInsert( &( xReadyTasksListEDF ), \
&( ( pxTCB )->xStateListItem ) );
#else
/* ORIGINAL CONTENT
* Place the task represented by pxTCB into the appropriate
* ready list for the task. It is inserted at the end of
* the list.
*/
#define prvAddTaskToReadyList( pxTCB ) \ traceMOVED_TASK_TO_READY_STATE( pxTCB ); \ taskRECORD_READY_PRIORITY( ( pxTCB )->uxPriority ); \ vListInsertEnd( &( pxReadyTasksLists[ \
( pxTCB )->uxPriority ] ), \
&( ( pxTCB )->xStateListItem ) ); \ tracePOST_MOVED_TASK_TO_READY_STATE( pxTCB )
#endif
MetodavListInsert()je vol´ana pro vloˇzen´ı ukazatele TCB do
xReadyTasksListEDF. Tato metoda vkl´ad´a pˇredmˇety do list tak, aby list byl seˇrazen podle hodnoty pˇredan´e druh´ym parametrem, v naˇsem pˇr´ıpadˇe ( pxTCB )->xStateListItem. Tud´ıˇz zde m˚uˇzeme s jistotou pˇredpokl´adat, ˇze do t´eto promˇenn´e budeme ukl´adat deadline ´ulohy. ˇCasov´a sloˇzitost vkl´ad´an´ı
´uloh do listu je line´arn´ı a jednoduch´y, proto je vhodn´y pro zaˇr´ızen´ı s malou pamˇet´ı.
Jak jsme si zobrazili v obr´azc´ıch 3.2, 3.3 a 3.4, kdyˇz pˇresouv´ame ´ulohy, tak potˇrebujeme vˇedˇet ˇcas deadlinu, abychom ji zvl´adli vloˇzit na spr´avnou pozici.
Naˇstˇest´ı deadline se d´a jednoduˇse spoˇc´ıtat jako Di = t+pi, tud´ıˇz budeme potˇrebovat, aby ´ulohy si ukl´adali ´udaj o sv´e periodˇe. To doc´ıl´ıme tak, ˇze do TBC vloˇz´ıme n´asleduj´ıc´ı k´od:
/* The old naming convention is used to
prevent breaking kernel aware debuggers. */
typedef struct tskTaskControlBlock 30
3.1. EDF
{
...
#if ( configUSE_EDF_SCHEDULER == 1 ) TickType_t xTaskPeriod;
#endif ...
} tskTCB;
Pochopitelnˇe abychom tento ´udaj mohli vyuˇz´ıt, budeme potˇrebovat vytvoˇrit novou metodu xTaskPeriodicCreate(). Toto je vˇsak zkop´ırovan´a a trochu modifikovan´a metodaxTaskCreate(), kter´a nav´ıc sb´ır´a informaci o periodˇe.
#if ( configUSE_EDF_SCHEDULER == 1 )
BaseType_t xTaskPeriodicCreate( TaskFunction_t pxTaskCode, const char * const pcName,
const configSTACK_DEPTH_TYPE usStackDepth, void * const pvParameters,
UBaseType_t uxPriority,
TaskHandle_t * const pxCreatedTask, TickType_t period ){
...
if( pxNewTCB != NULL ) {
pxNewTCB->xTaskPeriod = period;
listSET_LIST_ITEM_VALUE( &( ( pxNewTCB )->xStateListItem ), ( pxNewTCB )->xTaskPeriod + xTickCount);
prvInitialiseNewTask( pxTaskCode, pcName, ( uint32_t ) usStackDepth, pvParameters, uxPriority,
pxCreatedTask, pxNewTCB, NULL );
prvAddNewTaskToReadyList( pxNewTCB );
xReturn = pdPASS;
} else {
xReturn = errCOULD_NOT_ALLOCATE_REQUIRED_MEMORY;
}
return xReturn;
}
#endif
3. Implementace
ˇR´ızen´ı speci´aln´ı sp´ıc´ı ´ulohy tak´e neunikne modifikaci. Inicializace sp´ıc´ı ´ulohy je prov´adˇena v metodˇe vTaskStartScheduler(), kter´a zahajuje cel´y proces ˇr´ızen´ı re´aln´eho ˇcasu a inicializuje veˇsker´e nutn´e struktury. Protoˇze FreeRTOS je velmi specifick´y v tom, jak se maj´ı ´ulohy spouˇstˇet, tak spr´avn´e oˇsetˇren´ı sp´ıc´ı ´ulohy je nezbytn´e. V klasick´em pˇr´ıpadˇe je oˇsetˇren´ısp´ıc´ı ´ulohy jednoduch´e, prostˇe se j´ı pˇriˇrad´ı nejniˇzˇs´ı priorita. T´ım se zajiˇst’uje, ˇze ´uloha je vol´ana, pouze kdyˇz nen´ıˇz´adn´a jin´a ´uloha, kter´a by chtˇela pracovat. S naˇs´ım EDF pl´anovaˇcem m˚uˇzeme nasimulovat n´ızkou prioritu t´ım, ˇze d´ame deadline t´emˇeˇr nekoneˇcn´y.
Metoda vTaskStartScheduler() inicializuje naˇsi sp´ıc´ı ´ulohu a vloˇz´ı ji do xReadyTasksListEDF.
Metoda je definov´ana takto:
#if ( configUSE_EDF_SCHEDULER == 1 ) {
TickType_t initIDLEPeriod = 0xfffffff;
xReturn = xTaskPeriodicCreate( prvIdleTask, configIDLE_TASK_NAME, configMINIMAL_STACK_SIZE, ( void* ) NULL,
( tskIDLE_PRIORITY | portPRIVILEGE_BIT ),
&xIdleTaskHandle, initIDLEPeriod );
}
#else {
xReturn = xTaskCreate( prvIdleTask, configIDLE_TASK_NAME, configMINIMAL_STACK_SIZE, ( void * ) NULL,
( tskIDLE_PRIORITY | portPRIVILEGE_BIT ),
/* In effect ( tskIDLE_PRIORITY | portPRIVILEGE_BIT ), but tskIDLE_PRIORITY is zero. */
&xIdleTaskHandle ); /*lint !e961 MISRA exception, justified as it is not a redundant explicit cast to all supported compilers. */
}
#endif
Sp´ıc´ı ´ulohu inicializujeme s periodouTickType_t initIDLEPeriod = 0xfffffff;. Pˇredpokl´ad´am, ˇze pro ´uˇcely v´yuky nikdo nebude ˇcekat 0xfffffff sekund, aby pˇretekly ostatn´ı ´ulohy danou sp´ıc´ı ´ulohu, a syst´em tak z˚ustal na nˇejakou chv´ıli ve stavu sp´anku. Takto zaruˇc´ıme, ˇze sp´ıc´ı ´uloha bude vˇzdy posledn´ı.
Posledn´ı ´upravy se budou t´ykat mechanismu pˇrep´ınan´ı kontext˚u ´uloh.
Pokaˇzd´e, kdyˇz ´uloha je pozastavena nebo pozastaven´a ´uloha, s vyˇsˇs´ı prio- 32
3.2. LLF ritou neˇz moment´alnˇe bˇeˇz´ıc´ı, se vzbud´ı, doch´az´ı k pˇrepnut´ı kontextu. Metoda vTaskSwitchContext() je tu od toho, aby patˇriˇcnˇe aktualizovala ukazatel
*pxCurrentTCBna novˇe spuˇstˇenou ´ulohu:
void vTaskSwitchContext( void ) {
...
#if ( configUSE_EDF_SCHEDULER == 1 ) {
pxCurrentTCB = ( TCB_t * )
listGET_OWNER_OF_HEAD_ENTRY( &(
xReadyTasksListEDF ) );
} {
/*lint !e9079 void * is used as this macro is used with timers and co-routines too. Alignment is known to be fine as the type of the pointer stored and retrieved is the same. */
taskSELECT_HIGHEST_PRIORITY_TASK();
}
...
}
MetodataskSELECT_HIGHEST_PRIORITY_TASK()je nahrazena abychom doc´ılili toho, ˇze se vˇzdy vybere ´uloha na prvn´ım m´ıstˇe v listu xReadyTasksListEDF.
Nyn´ı m´ame vˇsechny potˇrebn´e ˇc´asti k provozuschopnosti pl´anovaˇce.
3.2 LLF
Po implementaci pl´anovac´ıho algoritmu EDF, je na ˇcase zaˇc´ıt implemen- taci algoritmu Least laxity first. I tento algoritmus jako EDF vyuˇz´ıv´a dy- namick´e priority. C´ıl t´eto sekce je opˇet jasn´y, a to popsat, jak se d´a imple- mentovat LLF pl´anovac´ı algoritmus do FreeRTOSu pouˇz´ıvaj´ıc´ı jiˇz existuj´ıc´ı struktury, kter´e n´am FreeRTOS nab´ız´ı, ˇci pˇr´ıpadnˇe doplnit o sv´e struktury.
N´apad je takov´y, ˇze vytvoˇr´ıme tentokr´at dva nov´e listy xReadyTaskListLLF
3. Implementace
a xTemporaryTaskListLLF (obr´azek 3.5). V listu xReadyTaskListLLF bu- deme podobnˇe jako u EDF spravovat priority naˇsich ´uloh. Tento nov´y list bude obsahovat ´ulohy seˇrazen´e podle naˇs´ı dynamick´e priority vzestupnˇe, kde pozice v tomto listu bude reprezentovat prioritu podle nejmenˇs´ı laxity, a opˇet bude v prvn´ı pozici naˇse moment´alnˇe spouˇstˇen´a ´uloha. Druh´y list n´am bude slouˇzit jako zp˚usob, jak rychle a bez velk´e reˇzie budeme listy ˇradit. Zbytek architek- tury FreeRTOSu je zachov´an a m´ısty se vyskytuj´ı drobn´e ´upravy. Pro nasta- ven´ıLLF se zadefinuje vFreeRTOSConfig.hdefiniceconfigUSE_LLF_SCHEDULER. Ta n´am bude urˇcovat, jestli bude pouˇzit pl´anovaˇc LLF. Chov´an´ı programu nen´ı definov´ano pokud bude LLF i EDF pl´anovaˇc zapnut najednou. Zaˇcneme podobnˇe jako u EDF a to t´ım, ˇze si zadefinujem naˇse nov´e pˇredpokl´adan´e struktury list˚uxReadyTasksListLLFaxTemporaryTasksListLLFa k nim je- jich pˇr´ısluˇsn´e ukazatelepxReadyTasksListLLFapxTemporaryTasksListLLF.
#if ( configUSE_LLF_SCHEDULER == 1 )
/*< Ready tasks in order by their deadline */
PRIVILEGED_DATA static List_t xReadyTasksListLLF;
PRIVILEGED_DATA static List_t xTemporaryTasksListLLF;
/* Necessary for easy swapping */
PRIVILEGED_DATA static List_t * volatile pxReadyTasksListLLF;
PRIVILEGED_DATA static List_t * volatile pxTemporaryTasksListLLF;
#endif
D´ale v metodˇe prvInitialiseTaskLists() si inicializujeme naˇse nov´e listy n´asleduj´ıc´ım zp˚usobem:
#if ( configUSE_LLF_SCHEDULER == 1) // < initialise task ready list {
vListInitialise( &xReadyTasksListLLF );
vListInitialise( &xTemporaryTasksListLLF );
pxReadyTasksListLLF = &xReadyTasksListLLF;
pxTemporaryTasksListLLF = &xTemporaryTasksListLLF;
}
#endif
Tentokr´at ´uprava metodyprvAddTaskToReadyList()bude vypadat dosti po- dobnˇe ´upravˇe v EDF pl´anovaˇci. Zde jako hlavn´ı list je xReadyTasksListLLF ve kter´em jsou uloˇzeny ´ulohy ˇrazeny vzestupnˇe podle laxity. Tato funkce m´a line´arn´ı sloˇzitost.
34
3.2. LLF
Obr´azek 3.5: Nov´y list xReadyTasksListsEDF obsahuje ´ulohy seˇrazen´e vze- stupnˇe podle vzr˚ustaj´ıc´ı laxity. Na prvn´ı pozici se nach´az´ı ´uloha s nejniˇzˇs´ım laxitou. Druh´y list m´a slouˇzit pouze ˇrazen´ı ´uloh. Kaˇzd´y list m´a pˇridruˇzen´y ukazatel pro swapov´an´ı obsahu.
3. Implementace
#if ( configUSE_LLF_SCHEDULER == 1)
#define prvAddTaskToReadyList( pxTCB ) \ vListInsert( pxReadyTasksListLLF , &( \
( pxTCB )->xStateListItem ) )
#else
/* ORIGINAL CONTENT
* Place the task represented by pxTCB into the appropriate
* ready list for the task. It is inserted at the end of
* the list.
*/
#define prvAddTaskToReadyList( pxTCB ) \
traceMOVED_TASK_TO_READY_STATE( pxTCB ); \ taskRECORD_READY_PRIORITY( ( pxTCB )->uxPriority ); \ vListInsertEnd( &( pxReadyTasksLists[ \ ( pxTCB )->uxPriority ] ), &( \
( pxTCB )->xStateListItem ) ); \
tracePOST_MOVED_TASK_TO_READY_STATE( pxTCB )
#endif
N´asleduje deklarov´an´ı nov´ych promˇenn´ych do prvTaskControlBlock, kter´e jsou potˇreba novˇe vˇedˇet.
#if ( configUSE_LLF_SCHEDULER == 1 ) TickType_t xTaskCapacity;
volatile TickType_t xTaskExecTime;
#endif
TickType_t xTaskCapacityn´am novˇe bude urˇcovat dobu nutnou pro v´ypoˇcet
´ulohy avolatile TickType_t xTaskExecTimepromˇenn´a ukl´ad´a stav o tom, kolik je potˇreba jeˇstˇe prov´est v´ypoˇct˚u v dan´e periodˇe. Nyn´ı kdyˇz m´ame tyto dvˇe nov´e promˇenn´e deklarovan´e, je nutno upravit xTaskPeriodicCreate(), aby s nimi bylo moˇzn´e pracovat.
BaseType_t xTaskPeriodicCreate( TaskFunction_t pxTaskCode, const char * const pcName,
const configSTACK_DEPTH_TYPE usStackDepth, void * const pvParameters,
UBaseType_t uxPriority,
TaskHandle_t * const pxCreatedTask, TickType_t period,
TickType_t capacity){
36
3.2. LLF
...
pxNewTCB->xTaskExecTime = 0;
pxNewTCB->xTaskPeriod = period;
pxNewTCB->xTaskCapacity = capacity;
listSET_LIST_ITEM_VALUE( &( ( pxNewTCB )->xStateListItem ), ( pxNewTCB )->xTaskPeriod - (
xTickCount + ( pxNewTCB )->xTaskCapacity ) ; rvInitialiseNewTask( pxTaskCode, pcName, ( uint32_t )
usStackDepth, pvParameters, xPriority, pxCreatedTask, pxNewTCB, NULL );
prvAddNewTaskToReadyList( pxNewTCB );
xReturn = pdPASS;
} else {
xReturn = errCOULD_NOT_ALLOCATE_REQUIRED_MEMORY;
}
return xReturn;
}
D´ale uprav´ıme probouzen´ı ´uloh v metodˇexTaskIncrementTick()a pˇriprav´ıme prostor na um´ıstˇen´ı k´odu ˇrazen´ı ´uloh. Vˇse dˇel´ame v souladu s definic´ı laxity Li =Di−(t+c0i).
BaseType_t xTaskIncrementTick( void ) {
...
#if ( configUSE_LLF_SCHEDULER == 1 ) vResortTasksLLF();
const TickType_t xTemp = (pxCurrentTCB->xTaskExecTime + 1) % (pxCurrentTCB->xTaskCapacity + 1);
if( listGET_LIST_ITEM_VALUE( &(
( pxCurrentTCB )->xStateListItem ) ) ) pxCurrentTCB->xTaskExecTime = xTemp;
if(pxCurrentTCB !=
(TCB_t *)listGET_OWNER_OF_HEAD_ENTRY(
pxReadyTasksListLLF )){
xSwitchRequired = pdTRUE;
}
#endif
3. Implementace
...
#if ( configUSE_LLF_SCHEDULER == 1 )
printf("Here: %ld\n",pxTCB->xTaskExecTime);
pxTCB->xTaskExecTime = 0;
printf("Here: %ld\n",pxTCB->xTaskExecTime);
listSET_LIST_ITEM_VALUE( &(
( pxTCB )->xStateListItem ), ( pxTCB )->xTaskPeriod - (
( xTickCount % ( pxTCB )->xTaskPeriod ) + ( pxTCB )->xTaskCapacity ) );
#endif ...
}
V n´asleduj´ıc´ım kusu k´odu je novˇe zadefinov´ana funkcevoid vResortTasksLLF(). Tato funkce obsluhuje logiku v´ypoˇctu laxity v kaˇzd´em okamˇziku, jelikoˇz jsme limitov´ani FreeRTOSem v tom, jakou maxim´aln´ıdobu m˚uˇzeme str´avit v´ybˇerem
´ukolu, st´av´a se tato funkce delik´atn´ım ´ukolem, jelikoˇz i kdyˇz to vypad´a, ˇze funkce by se dala napsat i ´uspornˇeji, jej´ı podoba v tomto tvaru je nezbytn´a.
Nad d˚uvodem proˇc se vˇsak v t´eto pr´aci nebudeme zab´yvat. Tato funkce m´a kvadratickou sloˇzitost.
void vResortTasksLLF(){
List_t * listSwap;
configASSERT( ( listLIST_IS_EMPTY( pxTemporaryTasksListLLF )
== pdTRUE ) );
while( listLIST_IS_EMPTY( pxReadyTasksListLLF ) == pdFALSE ){
TCB_t * pxTCB =
listGET_OWNER_OF_HEAD_ENTRY( pxReadyTasksListLLF );
uxListRemove( &( ( pxTCB )->xStateListItem ) );
const TickType_t xRuned = ( pxTCB )->xTaskCapacity - ( pxTCB )->xTaskExecTime;
const TickType_t xTimed =
(xTickCount - 1) % ( pxTCB )->xTaskPeriod;
listSET_LIST_ITEM_VALUE( &( ( pxTCB )->xStateListItem ), ( pxTCB )->xTaskPeriod - ( xRuned + xTimed ) );
vListInsert( pxTemporaryTasksListLLF, &(
( pxTCB )->xStateListItem ) );
} 38
3.2. LLF
listSwap = pxReadyTasksListLLF;
pxReadyTasksListLLF = pxTemporaryTasksListLLF;
pxTemporaryTasksListLLF = listSwap;
}
Jelikoˇz toto byl n´aˇs posledn´ınezbytn´y ´ukol k funkˇcnosti pl´anovaˇce LLF vr´at´ıme se se k nˇemu znovu aˇz v sekci LLF kapitoly Testov´an´ı.
Kapitola 4
Testov´ an´ı
V t´eto kapitole se zamˇeˇr´ıme na testov´an´ı, porovn´an´ı jednotliv´ych algoritm˚u.
Na n´asleduj´ıc´ıch pˇr´ıkladech se budeme snaˇzit porozumˇet praktick´emu pouˇzit´ı pl´anovaˇc˚u re´aln´eho ˇcasu v re´aln´em svˇetˇe. Zkus´ıme porovnat pouˇzit´ı algoritm˚u dynamick´ych priorit s algoritmem statick´e priority. V t´eto ˇc´asti se nebudeme zab´yvat niˇc´ım jin´ym neˇz praktick´ymi pˇr´ıklady, kter´e byly pouˇzity na syst´emu re´aln´eho ˇcasu. Syst´em, na kter´em pracujeme, je preemptivn´ı, jinak by nemˇelo cenu ˇreˇsit pl´anov´an´ı, pokud chceme, aby ´ulohy opravdu splnili deadline.
4.1 Testov´ an´ı FreeRTOS pl´ anovaˇ ce
V t´eto sekci si spust´ıme ´ulohu, kde oba configUSE_EDF_SCHEDULER a configUSE_LLF_SCHEDULERjsou nastaveny na nulu.
/* Standard includes. */
#include <stdlib.h>
#include <stdio.h>
#include <unistd.h>
#include <stdarg.h>
#include <assert.h>
/* FreeRTOS kernel includes. */
#include "FreeRTOS.h"
#include "task.h"
/* Local includes. */
//#include "console.h"
#define mainSELECTED_APPLICATION 2
#define projCOVERAGE_TEST 1
