Aktuální vydání

celé číslo

03

2021

Digitální transformace, chytrá výroba, digitální dvojčata

Komunikační sítě, IIoT, kybernetická bezpečnost

celé číslo

Návrh časově kritických systémů III: priorita úloh

Způsob, jakým jsou jednotlivým úlohám v časově kritických systémech (systémy RT, popř. úlohy RT) přiřazeny priority, má podstatný vliv na pořadí provádění těchto úloh, a tedy i na pořadí a doby poskytnutí odezev systému RT. Třetí ze série člán­ků na téma návrhu systémů RT je proto věnován mechanismům přiřazování prio­rit úlohám RT.
 
V závěru článku [7], druhého ze série čtyř článků uvádějících do problematiky návrhu časově kritických systémů (systémy reálné­ho času, systémy RT, Real-Time Systems), je konstatováno, že většina plánovačů používa­ných v moderních operačních systémech re­álného času (Real-Time Operating System – RTOS) je prioritních a preemptivních, z če­hož plynou zejména tyto důsledky:
  • díky systému priorit je zaručeno, že ze všech připravených úloh RT (dále jen úloh) je procesor přiřazen právě té z nich, jejíž priorita je v čase, kdy plánovač rozhodu­je, nejvýznamnější,
  • preemptivita garantuje, že obsluha poža­davku s velkou prioritou bude zahájena s minimálním zpožděním, tj. jestliže se momentálně běžící úloha nachází na méně významné prioritní úrovni, při příchodu prioritně významnějšího požadavku bude její provádění přerušeno a procesor bude předán obsluze nově příchozího požadav­ku; nestane-li se během provádění této ob­sluhy připravenou úloha s ještě větší pri­oritou, po ukončení obsluhy je procesor navrácen úloze, jejíž provádění bylo touto obsluhou přerušeno.
Jelikož způsob, jakým jsou úlohám při­řazeny priority, má podstatný vliv na pořa­dí provádění úloh, a tedy i na pořadí a doby poskytnutí odezev systému RT, je tento třetí článek série věnován obšírnějšímu popisu tzv. mechanismů přiřazování priorit.
 

Kategorie mechanismů přiřazování priorit

 
Podle toho, zda plány produkované me­chanismy přiřazování priorit jsou generová­ny před dobou běhu systému či až během ní, se tyto mechanismy dělí na historicky starší off-line (garantující optimálnost plánů – ty je však nutné generovat před spuštěním systé­mu) a mladší on-line (schopné adaptace na změny v okolí systému – plán je tvořen až za běhu systému). Umožňují-li změnu pri­ority za běhu systému RT či nikoliv, hovoří se o (jednodušších) mechanismech statické­ho přiřazování priorit či o (složitějších) me­chanismech dynamického přiřazování prio­rit (podle použitého mechanismu se potom rozlišují priority statické a dynamické). Nej­jednodušší z mechanismů jsou konstruová­ny pro nezávislé periodické úlohy, složitější mechanismy dokážou vhodně přiřadit prio­rity i úlohám sporadickým či aperiodickým, závislým úlohám, úlohám plánovaným při přetížení systému či v systému snažícím se zotavit z poruchy apod. Velká většina me­chanismů plánování existuje jak v preemp­tivní, tak nepreemptivní podobě. Pro základ­ní orientaci v této oblasti bude postačující, omezí-li se následující výklad pouze na pre­emptivní verze mechanismů on-line pláno­vání množin nezávislých periodických úloh v jednoprocesorovém prostředí.
 

Mechanismy statického přiřazování priorit

 
Z mechanismů statického přiřazování pri­orit zde budou představeny mechanismy zná­mé zejména jako RM a DM.
 

Mechanismus RM (RMA)

Mechanismus statického přiřazování prio­rit označovaný v literatuře jako RM (Rate Mo­notonic), popř. RMA (Rate Monotonic Assign­ment), vychází z předpokladu, že úlohy volané častěji mají významnější prioritu. Významnost priority úlohy je tedy nepřímo úměrná velikos­ti periody mezi příchody (přímo úměrná kmi­točtu odpovídajícímu periodě) jejích instan­cí, tj. hodnotě statického parametru T úlohy.
 
Uvažujeme-li úlohy τ1(r1, C1, D1, T1) = τ 1(0, 3, 5, 20), τ 2(r2, C2, D2, T2) = τ 2(0, 3, 7, 12), τ 3(r3, C3, D3, T3) = τ 3(0, 4, 10, 10) a τ 4(r4, C4, D4, T4) = τ 4(0, 3, 20, 20), podle RM budou těmto úlohám přiřazeny priori­ty od nejvýznamnější po nejméně významnou v pořadí τ 3, τ 2, τ 1, τ 4nebo τ 3, τ 2, τ 4, τ 1.
 
Plán generovaný na základě přiřazová­ní priorit podle mechanismu RM je vyobra­zen na obr. 1, kde v čase t = 0 vzniknou požadavky na současné vyvolání všech úloh. Jelikož úloze t3 je přiřazena nejvýznamněj­ší priorita, poběží jako první právě tato úlo­ha; zbylé úlohy přejdou do čekajícího sta­vu. Až po dokončení úlohy τ 3(tj. v čase t = 0 + C3= 4) může začít běžet úloha, kte­rá má z dosud neprováděných úloh (τ 2, τ 1, τ 4) nejvyšší prioritu, tj. úloha τ 2. Poté (tj. v čase t = 4 + C2= 7) může začít běžet úlo­ha τ 1nebo τ 4. Avšak bez ohledu na pořadí provádění úloh t1t4úloha t1překročí svou časovou mez, protože ta vypršela již v t = 5, zatímco spuštění úlohy t1 je podle priorit přiřazených mechanismem RM plánováno nejdříve v čase t = 7.
 
Jestliže mechanismus RM není schopen zajistit plánovatelnost množiny úloh RT, jak je tomu právě v již uvedeném případě, vzni­ká problém, který je řešitelný dvěma základ­ními způsoby. První způsob spočívá ve změ­ně parametrů úloh RT s cílem zajistit pláno­vatelnost dané množiny úloh RT (ovšem již obsahující úlohy s modifikovanými parametry). Tento způsob je však obecně nepřijatel­ný a nelze ho doporučit, protože modifika­cí parametrů úloh RT je možné způsobit od­klon od již verifikované specifikace systému RT, a tím i jeho neočekávané chování. Druhý způsob spočívá v použití jiného mechanismu přiřazování priorit. Příčinou selhání mecha­nismu RM může v případě uvedené množiny úloh RT být skutečnost, že mechanismus RM je optimální pouze na množině úloh RT, mezi jejichž parametry platí vztah D = T a jejichž priorita se nemění v čase. Jinými slovy: exis­tuje-li pro množinu splňující podmínky pří­pustný plán, je možné jej generovat i pomo­cí mechanismu RM.
 

Mechanismus DM (DMA, ID, IDA)

Mechanismus statického přiřazování pri­orit nepřímo úměrně hodnotě časové meze označovaný zkratkou DM (Deadline Monotonic), popř. DMA (Deadline Monotonic Assignment), ID (Inverse Deadline) nebo IDA (Inverse Deadline Assignment), vychá­zí z předpokladu, že úlohy s menší hodnotou časové meze jsou významnější. Význam­nost priority úlohy je tedy v tomto případě nepřímo úměrná hodnotě statického para­metru D úlohy. Pro množinu úloh RT, uva­žovanou v odstavci týkajícím se mechanis­mu RM, budou při použití mechanismu DM těmto úlohám přiřazeny priority od nejvý­znamnější po nejméně významnou v po­řadí τ1, τ2, τ3, τ4. Odpovídající plán je vyobrazen na obr. 2.
 
V porovnání s mechanismem RM je me­chanismus DM optimální také na množině úloh s D < T, tj. celkově na množině úloh, mezi jejichž parametry platí vztah D ≤ T. To znamená, že při použití mechanismu DM lze plánovat i ty množiny úloh, které nejsou plánovatelné pomocí mechanismu RM. Tuto vlastnost lze vysledovat i porovnáním plánů na obr. 1 obr. 2 (zatímco pro danou mno­žinu úloh RT není pomocí mechanismu RM možné vytvořit přípustný plán, při použití mechanismu DM to již možné je).
 
Z pohledu návrháře systému RT je zde klíčová existence tzv. testů plánovatelnosti, které jsou již v etapě reprezentace systému RT množinou úloh RT (tj. dávno před tím, než je systém RT v reálném prostředí spuš­těn) schopny pro danou množinu úloh RT a daný mechanismus přiřazování priorit roz­hodnout, zda daná množina je, či není při po­užití daného mechanismu plánovatelná. Celá problematika spojená s těmito testy je však natolik složitá, že značně přesahuje rámec tohoto seriálu. Zmiňme alespoň, že rozho­dovací schopnost těchto testů klesá s počtem parametrů obsažených v modelu úloh RT a se složitostí mechanismu přiřazování priorit úlo­hám. U některých množin úloh a některých mechanismů přiřazování priorit je tedy nutné počítat s tím, že o plánovatelnosti tímto způ­sobem rozhodnout nelze.
 

Mechanismy dynamického přiřazování priorit

 
Vedle uvedených nejjednodušších mecha­nismů (statického) přiřazování priorit existu­je mnoho dalších, složitějších mechanismů. Z jejich velmi početné množiny zde budou představeny pouze dva mechanismy umožňu­jící změnu priority v čase, známé jako EDF a LLF. Tyto základní mechanismy tzv. dyna­mického přiřazování priorit dokážou lépe vy­hodnotit aktuální stav systému, zejména roz­poznat blížící se překročení časových mezí. Podstatný rozdíl oproti mechanismům RM a DM je ten, že priority všech úloh nachá­zejících se v systému jsou proměnné v čase, přičemž priority jsou obvykle přehodnocová­ny v časech příchodů úloh, dokončení úloh či přepnutí kontextu úloh.
 

Mechanismus EDF

Mechanismus dynamického přiřazování priorit nepřímo úměrně době zbývající v čase t do uplynutí časové meze má označení EDF (Earliest Deadline First). Garantuje, že vý­znamnější priorita je v čase přiřazena těm úlohám, kterým v t zbývá do uplynutí časo­vé meze méně času na provedení, což je hod­nota reprezentovaná dynamickým parame­trem D(t) úlohy. Předpokládejme množinu tvořenou úlohami τ1(r1, C1, D1, T1) = τ 1(0, 2, 5, 5) a τ2(r2, C2, D2, T2) = τ2(0, 4, 7, 7). Tato mno­žina není plánovatelná s použitím ani jednoho z mechanismů RM a DM (v čase t = 7 totiž úloha t2 v obou případech překročí svoji časovou mez). Bu­de-li se však priorita měnit v čase, k tomuto překro­čení nemusí dojít. V čase t = 0 je podle mechanis­mu EDF přiřazena nejvý­znamnější priorita úloze t1, jelikož do uplynutí její časové meze zbývá méně času. Úloha t1 tedy běží po svou dobu C1 = 2 jednot­ky času. Protože v systému není žádná jiná úloha, je poté (tj. v čase t = 2) spuš­těna úloha τ2, která poběží až do okamžiku příchodu nové periody T1, tj. do t = 5.V tomto čase budou priority přehodnoceny. Jelikož úloze τ2 zbývají do uplynutí časové meze jen dvě jednotky času, zatímco úloze τ1 pět jednotek, je vyšší priorita přiřazena úloze τ2, která na základě tohoto rozhodnutí dokon­čí svůj běh (v délce jedné jednotky času) a do­drží svoji časovou mez již v čase t = 6. Poté je procesor přidělen úloze τ1 atd. Celý plán v délce jedné hyperperiody (hlavního cyklu) je ukázán na obr. 3.
 

Mechanismus LLF (LL, MLF, LSF)

Vedle mechanismu EDF existují i další mechanismy dynamického přiřazování pri­orit s ještě lepšími vlastnostmi. Například mechanismus označovaný LLF (Least Laxity First), popř. LL (Least Laxity), LSF (Least Slack Time First) nebo MLF (Minimum Laxi­ty First), je schopen zamezit překročení časo­vých mezí dříve než mechanismus EDF tím, že úlohám přiřazuje priority nepřímo úměrně době volnosti úlohy v čase t, tj. hodnotě para­metru L(t) úlohy (udávajícího, na jak dlouho může být provádění úlohy odloženo, aniž by překročila svou časovou mez). Cenou za tuto lepší vlastnost je větší počet přepnutí kontex­tu a preempcí – zatímco v případě plánu EDF na obr. 3 je počet přepnutí kontextu třináct a počet preempcí dvě, v případě plánu odpo­vídajícího plánu LLF na obr. 4 již jde o hod­noty jednadvacet a deset. Mechanismus LLF tedy na stejně velkém časovém intervalu pře­hodnocuje priority častěji (v daném případě každou časovou jednotku) než EDF, díky če­muž dokáže dříve reagovat na blížící se pře­kročení časové meze.
 
Princip konstrukce plánu LLF zob­razeného na obr. 4 je následující: v čase = 0 jsou doby volnosti úloh τ1τ2, vy­hodnoceny jako L1(0) = D1(0) – C1(0) = 5 – 2 = 3 a L2(0) = D2(0) – C2(0) = 7 – 4 = 3. Jelikož L1(0) = L2(0), tj. obě úlo­hy si mohou dovolit prodlévat stejně dlou­hou dobu, jsou oběma úlohám přiřazeny stej­né priority. To umožňuje přiřadit procesor libovolné z obou úloh (na obr. 4 je nede­terministicky přiřazen úloze s indexem 1).V čase t = 1 jsou pak hodnoty přehodno­ceny následovně: L1(1) = D1(1) – C1(1) = 4 – 1 = 3 a L2(1) = D2(1) – C2(1) = 6 – 4 = 2. Platí L1(1) = 3 > 2 = L2(1) a proto je významnější priorita přiřazena úloze t2, která může odložit své provádění na kratší dobu než úloha t1. V čase = 2 platí L1(2) = 3 – 1 = 2 a L2(1) = 5 – 3 = 2, běžet tedy může libovolná z úloh. V čase t = 3 je L1(3) = 2 – 0 = 2 a L2(3) = 4 – 3 = 1, v čase t = 4 je L1(4) = 1 – 0 = 1 a L2(4) = 3 – 2 = 1, v čase = 5 je L1(5) = 0 – 0 = 0 a L2(5) = 2 – 1 = 1 atd.
 
Plán LLF zobrazený na obr. 4 tedy, na roz­díl od plánu EDF na obr. 3, není pro danou množinu úloh RT jediný možný, ale pouze jeden z možných. Obecně platí, že množina plánů generovaných mechanismem EDF je podmnožinou množiny plánů generovaných mechanismem LLF. Použitelnost mechanis­mu LLF však významně závisí mj. na tom, s jak velkou přesností je plánovač schopen vyhodnotit parametr C(t), tj. čas, který úlo­hám zbývá k dokončení jejich běhu. Toto vy­hodnotit může být obtížné, jelikož hodnotit nelze bez detailní znalosti cílové platformy a příslušného RTOS.
 

Závěr

 
Chování mechanismů přiřazování prio­rit představených v tomto článku lze detail­něji studovat např. s použitím volně dostupných nástrojů [4], [5]. V závěrečném článku z této série bude na jednoduchém příkladu ukázáno, jaký vztah existuje mezi formál­ní specifikací systému RT, množinou úloh RT a realizací systému RT s použitím pro­středků RTOS.
 
Poděkování:
Článek vznikl za podpory výzkumného zámě­ru MSM0021630528 – Výzkum informačních technologií z hlediska bezpečnosti (agentura CEZ MŠMT) a projektu specifického výzku­mu FIT-S-10-1 (VUT v Brně).
 
Literatura:
[1] CHENG, A. M. K.: Real-Time Systems: Sche­duling, Analysis, and Verification. Wiley, 2002, 552 s., ISBN 0-471-18406-3.
[2] COTTET, F. – DELACROIX, J. – KAISER, C. – MAMMERI, Z.: Scheduling in Real-Time Systems. John Wiley & Sons, 2002, 266 s., ISBN 0-470-84766-2.
[3] JOSEPH, M.: Real-Time Systems Specificati­on, Verification and Analysis. Prentice Hall, 1996, 278 s., ISBN 0-13-455297-0.
[4] Cheddar project: a free real time scheduling analyzer [online]. 2008 [cit. 2010-03-25]. Dokument dostupný z <http://beru.univ-brest.fr/~singhoff/cheddar/>.
[5] TimesTool [online]. 2007 [cit. 2010-03-25]. Dokument dostupný z <http://www.timestool.com/>.
[6] STRNADEL, J.: Návrh časově kritických systémů I: specifikace a verifikace. Automa, 2010, roč. 16, č. 10, s. 42–44, ISSN 1210-9592.
[7] STRNADEL, J.: Návrh časově kritických systémů II: úlohy reálného času. Automa, 2010, roč. 16, č. 12, s. 18–19, ISSN 1210-9592.
 
Ing. Josef Strnadel, Ph.D.,
Fakulta informačních technologií,
Vysoké učení technické v Brně
 
Obr. 1. Ilustrace k mechanismu přiřazování priorit přímo úměrně kmitočtům příchodů (Rate Monotonic – RM)
Obr. 2. Ilustrace k mechanismu přiřazování priorit nepřímo úměrně velikosti časové meze (Deadline Monotonic – DM)
Obr. 3. Ilustrace k mechanismu přiřazování priorit nepřímo úměrně době zbývající v čase t do uplynutí časové meze (Earliest Deadline First – EDF)
Obr. 4. Ilustrace k mechanismu přiřazování priorit nepřímo úměr­ně době volnosti úlohy v čase t (Least Laxity First – LLF)