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ánků na téma návrhu systémů RT je proto věnován mechanismům přiřazování priorit ú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žívaný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 čehož 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č rozhoduje, nejvýznamnější,
-
preemptivita garantuje, že obsluha požadavku 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žadavku; nestane-li se během provádění této obsluhy připravenou úloha s ještě větší prioritou, 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řadí 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é mechanismy 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 priority 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) mechanismech dynamického přiřazování priorit (podle použitého mechanismu se potom rozlišují priority statické a dynamické). Nejjednodušší z mechanismů jsou konstruovány pro nezávislé periodické úlohy, složitější mechanismy dokážou vhodně přiřadit priority 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 mechanismů plánování existuje jak v preemptivní, tak nepreemptivní podobě. Pro základní orientaci v této oblasti bude postačující, omezí-li se následující výklad pouze na preemptivní verze mechanismů on-line plánová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í priorit zde budou představeny mechanismy známé zejména jako RM a DM.
Mechanismus RM (RMA)
Mechanismus statického přiřazování priorit označovaný v literatuře jako RM (Rate Monotonic), popř. RMA (Rate Monotonic Assignment), 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á velikosti periody mezi příchody (přímo úměrná kmitočtu odpovídajícímu periodě) jejích instancí, 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 priority 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 vyobrazen 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 úloha; zbylé úlohy přejdou do čekajícího stavu. Až po dokončení úlohy τ 3(tj. v čase t = 0 + C3= 4) může začít běžet úloha, která 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 úloha τ 1nebo τ 4. Avšak bez ohledu na pořadí provádění úloh t1a t4ú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ě, vzniká problém, který je řešitelný dvěma základními způsoby. První způsob spočívá ve změně parametrů úloh RT s cílem zajistit plánovatelnost dané množiny úloh RT (ovšem již obsahující úlohy s modifikovanými parametry). Tento způsob je však obecně nepřijatelný a nelze ho doporučit, protože modifikací parametrů úloh RT je možné způsobit odklon 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í mechanismu 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: existuje-li pro množinu splňující podmínky přípustný plán, je možné jej generovat i pomocí mechanismu RM.
Mechanismus DM (DMA, ID, IDA)
Mechanismus statického přiřazování priorit 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ýznamnost priority úlohy je tedy v tomto případě nepřímo úměrná hodnotě statického parametru D úlohy. Pro množinu úloh RT, uvažovanou v odstavci týkajícím se mechanismu 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 mechanismus 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 a 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 rozhodnout, zda daná množina je, či není při použ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 rozhodovací 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 úlohá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 mechanismů (statického) přiřazování priorit existuje mnoho dalších, složitějších mechanismů. Z jejich velmi početné množiny zde budou představeny pouze dva mechanismy umožňující změnu priority v čase, známé jako EDF a LLF. Tyto základní mechanismy tzv. dynamického přiřazování priorit dokážou lépe vyhodnotit aktuální stav systému, zejména rozpoznat 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 t přiřazena těm úlohám, kterým v t zbývá do uplynutí časové meze méně času na provedení, což je hodnota reprezentovaná dynamickým parametrem 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). Bude-li se však priorita měnit v čase, k tomuto překročení nemusí dojít. V čase t = 0 je podle mechanismu 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 jednotky č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 dodrží 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í priorit 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 Laxity First), je schopen zamezit překročení časový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ě parametru 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í kontextu 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 odpovídajícího plánu LLF na obr. 4 již jde o hodnoty jednadvacet a deset. Mechanismus LLF tedy na stejně velkém časovém intervalu přehodnocuje priority častěji (v daném případě každou časovou jednotku) než EDF, díky čemuž dokáže dříve reagovat na blížící se překročení časové meze.
Princip konstrukce plánu LLF zobrazeného na obr. 4 je následující: v čase t = 0 jsou doby volnosti úloh τ1 a τ2, vyhodnoceny 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ě úlohy si mohou dovolit prodlévat stejně dlouhou dobu, jsou oběma úlohám přiřazeny stejné priority. To umožňuje přiřadit procesor libovolné z obou úloh (na obr. 4 je nedeterministicky přiřazen úloze s indexem 1).V čase t = 1 jsou pak hodnoty přehodnoceny 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 t = 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 t = 5 je L1(5) = 0 – 0 = 0 a L2(5) = 2 – 1 = 1 atd.
Plán LLF zobrazený na obr. 4 tedy, na rozdí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 mechanismu 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ý úlohám zbývá k dokončení jejich běhu. Toto vyhodnotit 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í priorit představených v tomto článku lze detailně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ální specifikací systému RT, množinou úloh RT a realizací systému RT s použitím prostř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ýzkumu FIT-S-10-1 (VUT v Brně).
Literatura:
[1] CHENG, A. M. K.: Real-Time Systems: Scheduling, 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 Specification, Verification and Analysis. Prentice Hall, 1996, 278 s., ISBN 0-13-455297-0.
[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ěrně době volnosti úlohy v čase t (Least Laxity First – LLF)
Článek ve formátu PDF je možné stáhnout zde.