Plánování úloh v systémech RT – I: závislé úlohy

V seriálu článků Návrh časově kritických systémů I až IV [4] až [7] byl představen model úloh tzv. reálného času (real-time, RT, úlohy RT) [5] a základní preemptivní mechanismy (RM, DM, EDF, LLF) přiřazování priorit a plánování množin úloh RT [6]. Bylo předpokládáno, že úlohy jsou periodické a nezávislé a jsou bezchybně prováděny v rámci jednoprocesorového systému, který je vždy provozuschopný a má dostatečný výkon ke včasnému provedení všech úloh zahrnutých v systému. Nyní začínající seriál Plánování úloh v systémech RT navazuje na uvedená publikovaná témata a je věnován mechanismům, které jsou použitelné v situacích, kdy již zmíněné předpoklady splněny nejsou. I nadále však bude pojednáváno o preemptivních variantách mechanismů. 

Tento první článek nového seriálu je věnován principům přiřazování priorit závislým úlohám RT, tj. úlohám, mezi kterými existují závislosti plynoucí ze specifikace systému [4]. Oproti nezávislým úlohám je tudíž za běhu systému třeba dodržet nejen časová omezení kladená na odezvy úloh, ale navíc při snahách o jejich dodržování i reflektovat dané závislosti a řešit problémy z toho vyplývající.

Mezi úlohami lze rozlišit dva typy závislostí – časovou a prostorovou. Časová závislost (někdy také označovaná jako precedenční) mezi úlohami existuje tehdy, plyne-li ze specifikace požadavek přednostního provedení jedné z úloh před jinými. Prostorová závislost mezi úlohami plyne z požadavku úloh přistupovat ke stejnému (tj. těmito úlohami sdílenému) prostředku (typicky zdroji/poskytovateli určité služby), mnohdy vyžadujícímu vzájemně výlučný přístup v tom smyslu, že daný prostředek může v daném čase využívat nejvýše jedna úloha. Tyto závislosti mohou být kombinovány, čímž se situace dále komplikuje. V dalším textu budou nastíněny principy přiřazování priorit pro každý ze zmíněných typů závislostí.

Časová závislost mezi úlohami

Časové závislosti (angl. precedence constraints) mezi úlohami jsou typicky vyjadřovány a zadávány ve formě tzv. precedenčního grafu (precedence graph), což je orientovaný graf G_P = (V, E), jehož uzly z množiny V představují úlohy a jehož orientované hrany z množiny E Í V × V svou orientací vyjadřují časové závislosti mezi úlohami [3]. Každá časová závislost tvaru „úloha τ_i předchází úlohu τ_j“, obvykle značenou τ_i ® τ_j, a je v precedenčním grafu reprezentována pomocí uzlů τ_i, τ_j a orientované hrany (τ_i, τ_j) Î E vedoucí z τ_i do τ_j. Tento typ závislosti lze považovat za základní prostředek zajištění synchronizace akcí prováděných různými úlohami. Příkladem může být úloha τ₁ zajišťující periodické vzorkování určené veličiny (např. teploty) a úloha τ₂ periodicky produkující průměr ze čtyř posledních vzorků poskytnutých úlohou τ₁. Tuto závislost reprezentuje precedenční graf na obr. 1a.

Obecně pro zajištění τ_i ® τ_j musí platit: r_j ≥ r_i (tj. τ_j nesmí být vyvolána dříve než τ_i) a P_i ≥ P_j (tj. τ_j nesmí mít významnější prioritu než τ_i). Pro příklad z obr. 1a to znamená nastavit r₂ na hodnotu z intervalu (r₁ + 3T₁, r₁ + 4T₁) priority P tak, aby platilo P₁ ≥ P₂.

Důležité je si uvědomit, že zavedením časových závislostí již plánovač nerozhoduje o přidělení procesoru jen na základě mechanismu přiřazování priorit aplikovaném na parametry úloh, ale také na základě vztahů zaznamenaných v precedenčním grafu. V následujícím textu bude ukázáno, jak informace zaznamenaná v precedenčním grafu změní parametry úloh, a tím zajistí příslušnou časovou závislost pro daný mechanismus přiřazování priorit. Základní myšlenka již byla naznačena dříve – spočívá v zamezení spuštění úlohy před jejími předchůdci a v zamezení přerušení následovníků úlohy některým z jejích předchůdců.

V případě mechanismu RM musí být pro zajištění τ_i ® τ_j parametry r_i, r_j úloh τ_i, ^*τ_j změněny na r_i^*, r_j^* tak, aby platilo r_j^* ≥ max(r_i, r_i^*) a P_i  ≥ P_j (tab. 1). Zde je vhodné poznamenat, že pro úlohy se stejnou periodou tedy plyne poměrně značná volnost při volbě nejen dob vyvolání úloh (r_i), ale i priorit, které mají zajistit respektování precedenčních omezení.

Obdobným způsobem jsou priority přiřazeny i v případě mechanismu DM – zde musí, vedle podmínek pro mechanismus RM, navíc platit podmínka pro modifikace D_i^*, D_j^* parametrů D_i, D_j úloh τ_i, τ_j: D_j^* ≥ max(D_j, D_i^*). Mechanismus DM totiž přiřazuje významnější prioritu úloze s menší hodnotou parametru D, tj. kratší časovou mezí odezvy.

Jelikož mechanismy RM a DM jsou statické v tom smyslu, že přiřazují priority úlohám pevně a neměnně za běhu systému pracujícího v reálném čase (systém RT), je vliv precedenčního grafu na priority omezen pouze na stanovení priorit v návrhové etapě, tj. před zahájením běhu systému RT. Situace se však komplikuje, jsou-li časové závislosti kombinovány s mechanismem dynamického přiřazování priorit, jako je např. EDF (Earliest Deadline First). Podle tohoto mechanismu jsou totiž úlohám přiřazovány priority nepřímo úměrně hodnotě parametru d určeného vztahem d = D – t, kde t je aktuální čas [5]. Hodnota d je zřejmě obecně proměnná v čase, a tedy i graf omezení musí být analyzován, a to i za běhu systému, kdykoliv je volán plánovač.

Přiřazování priorit EDF s ohledem na precedenční graf musí pro každou závislost τ_i ® τ_j splňovat následující podmínky: r_j^* ≥ max(r_i^* + C_i, r_j), tj. τ_j nesmí být vyvolána dříve, než by končila τ_i, a d_i^* ≥ min(d_j^* – C_j, d_i), tj. časová mez τ_i nesmí být předsunuta před čas včasného zahájení τ_j. Při modifikaci parametrů se postupuje nejprve v protisměru orientace hran precedenčního grafu, a to od úloh nemajících žádné následovníky (modifikace parametru d), a poté po směru orientace hran precedenčního grafu, a to od úloh nemajících žádné předchůdce (modifikace parametru r), popř. naopak – viz obr. 3.

Princip zmíněné modifikace lze ilustrovat jednoduchým příkladem při použití množiny úloh z tab. 1 a precedenčního grafu z obr. 1b. Změna původních parametrů začne od úloh nemajících předchůdce – v popisovaném případě od úlohy τ₁. Její parametr r₁ se změní na hodnotu r₁^* = max(0, r₁) = 0. Poté se zpracovávají následovníci. Těmi jsou τ₂, τ₄ – mění se tedy r₂, r₄ následovně: r₂^* = max(r₁^* + C₁, r₂) = 3, r₄^* = max(r₁^* + C₁, r₄) = 3. Další změna se provede u úlohy τ₃, následovníka τ₂: r₃^* = max(r₂^* + C₂, r₃) = 5. Jako poslední se změní r₅; jelikož τ₅ je následovníkem τ₂ i τ₄, hodnota bude změněna na r₅^* = max(max(r₂^* + C₂, r₄^* + C₄), r₅) = 5.

Po vyčerpání všech následovníků se začne druhá fáze změn, tj. změny parametru d úloh. V tomto případě se začne od úloh bez následovníků, což jsou úlohy τ₃, τ₅. Hodnoty d₃, d₅ se změní na d₃^* = min(¥, d₃) = 12, d₅^* = min(¥, d₅) = 9. Poté se zpracují předchůdci úloh τ₃, τ₅, tj. úlohy τ₂ a τ₄. Protože τ₄ má jediného následovníka (τ₅), bude d₄ změněna na d₄^* = min(d₅^* – C₅, d₄) = 7. Úloha τ₂ má však následovníky dva (τ₃ a τ₅), a proto bude d₂ změněna na d₂^* = min(min(d₃^* – C₃, d₅^* – C₅), d₂) = 7. Poslední úloha (τ₁) má předchůdce τ₂, τ₄ a d₁, tedy bude změněna na d₁^* =  min(min(d₂^* – C₂, d₄^* – C₄), d₁) = 5.

Kromě časové závislosti může mezi úlohami existovat i závislost prostorová; zbylá část článku bude tedy věnována právě jí.

Prostorová závislost mezi úlohami

Prostorová závislost mezi úlohami vzniká, požadují-li úlohy přístup ke stejnému prostředku (resource). S tímto typem závislosti je spojeno množství obecně známých problémů, které je třeba řešit, nicméně na jejich detailní popis není v tomto článku prostor, a proto zde bude uveden pouze přehled nejvýznamnějších z nich: hladovění (starvation), blokování (blocking), inverze priorit (priority inversion) a uváznutí (deadlock). V článku budou vynechány typické metody řešení těchto problémů (jakými jsou např. bankéřův algoritmus) v konvenčních operačních systémech a místo toho bude pozornost zaměřena na mechanismy typicky implementované v operačních systémech reálného času (RTOS) [1]. Pro jednoduchost bude opět předpokládáno jednoprocesorové prostředí. 

Hladovění

Hladovění úloh nepředstavuje na třídě systémů RT závažný problém – naopak, lze říci, že patří k základní vlastnosti systémů RT v tom smyslu, že s klesající významností prio­rity doba čekání úloh na přidělení procesoru roste. Toto čekání je zcela přirozené a plyne ze samotné podstaty systémů RT, pro něž je klíčové dodržet časová omezení, byť za cenu hladovění některých úloh.

Jelikož zbylé ze zmíněných problémů již mohou vést ke zpoždění odezev úloh a následně k nedodržení časových omezení, musí být jejich řešení při vypracovávání návrhu a realizaci systémů RT věnována patřičná pozornost. V následujícím textu bude ukázána podstata těchto problémů, jaké prostředky prevence těchto problémů existují a jaké jsou jejich vlastnosti. Pozornost bude zaměřena pouze na přehled tzv. protokolů přístupu k prostředkům (resource access protocols). Ty je možné rozčlenit na protokoly pro jedno- či víceprocesorové prostředí, na protokoly pracující se statickými či dynamickými prioritami atd. Přehled bude omezen na jednoprocesorové prostředí a statické priority. 

Blokování

Jako první z problémů s dopadem na dodržování časových omezení zmiňme blokování. To lze neformálně definovat jako čekání úlohy s vysokou prioritou na uvolnění prostředku momentálně užívaného úlohou s nízkou prioritou. Toto čekání je jistě nežádoucí – prioritní úloha se totiž chystala (přednostně) provést další část svého kódu, ale vlivem vnějších okolností (tj. nedostupnosti zdroje) musela být pozastavena až do času uvolnění tohoto zdroje, což prodlužuje dobu provádění i odezvy prioritní úlohy. Blokování je ilustrováno na obr. 4, kde úloha τ_n s nejméně významnou prioritou začne jako první z úloh využívat prostředek (nazvěme jej např. R). Čas žádosti úlohy o přístup k R je v obrázku vyznačen symbolem ¯_R, čas uvolnění R symbolem ­_R a doba přístupu k R červeným obdélníkem. V čase t₁ je spuštěna úloha τ₁ s nejvýznamnější prioritou. Ta vyvolá, před zahájením svého běhu, přerušení provádění (preempci) úlohy τ_n. V čase t₂ však τ₁ požaduje přístup k (dosud neuvolněnému) R. Tento přístup není umožněn, procesor je τ₁ odebrán a předán úloze τ_n, aby tato doužívala R, uvolnila jej a τ₁ poté mohla pokračovat v běhu (čas t₄). Popsaná situace představuje tzv. přímé (direct) blokování úlohy τ₁ úlohou τ_n, způsobené nedostupností prostředku (v obr. 4 vyznačené jako B_D). Mimoto existují i další typy blokování, např. nepřímé (indirect, v obr. 4 vyznačené jako B_I), obvykle zapříčiněné dočasným propůjčením vysoké priority úloze s nízkou prioritou pro minimalizaci doby B_D, či řetězené (chained) blokování, jež může nastat, existuje-li několik úloh sdílejících několik prostředků – úloha přistupující k n prostředkům pak může být blokována až n-krát.

Poznamenejme, že k prostředkům se vzájemně výlučným přístupem se obvykle přistupuje v rámci tzv. kritických sekcí (KS), jejichž provádění je atomické v tom smyslu, že v KS se může nacházet nejvýše jedna úloha. Slouží-li KS k zajištění výlučného přístupu k prostředku R, lze také hovořit o KS prostředku R (KS_R). Je-li v KS_R úloha, je KS_R označena jako obsazená; jinak je volná.

Inverze priorit

Další významný problém představuje pro systémy RT tzv. inverze priorit, ilustrovaná na obr. 5 na příkladu úloh τ₁, …, τ₄ s P₁ (nejvyšší) > … > P₄ (nejnižší), přičemž τ₂, τ₄ sdílejí prostředek R. Zaměřme se na dobu odezvy úlohy τ₂ – ta je delší o dobu potřebnou k provedení úlohy τ₁ s prioritou P₁ > P₂ (doba mezi t₃ a t₄) a dobu přímého blokování úlohy τ₂ úlohou τ₄ s prioritou P₄ < P₂ (doba mezi t₁ a t₅). Avšak doba přístupu τ₂ k R (tj. přítomnosti τ₂ v KS_R) je také prodloužena o dobu běhu úlohy τ₃, která ani nesdílí prostředek s τ₂, ani pro ni neplatí P₃ > P₂. V t₂ se totiž τ₂ stává nepřipravenou k běhu z důvodu nedostupnosti R a τ₃ je v t₂ jediná připravená úloha s prioritou větší než P₄. Úloha τ₃ tedy začíná běžet, čímž však odsouvá čas uvolnění R úlohou τ₄ až na t₄. Inverze priorit tedy nastává v intervalu mezi t₂, t₃ a t₄, t₅. Doba blokování prostředku R úlohou τ₄ – a tedy i doba odezvy úlohy τ₂ – je tudíž „zbytečně“ prodloužena o (t₃ – t₂) + (t₅ – t₄) časových jednotek.

Uváznutí

Jako poslední z problémů souvisejících se sdílením prostředků zmiňme uváznutí (deadlock). Jelikož, na rozdíl od předchozích problémů, může uváznutí vést k zastavení činnosti systému jako celku, je nutné mu předcházet zvlášť pečlivě. Uváznutí bude ilustrováno pomocí úloh τ₁, τ₂ sdílejících prostředky R₁, R₂ a přistupující k nim způsobem podle obr. 6. V čase t₁ vstoupí τ₂ do KS_R1 (obsazenost KS_R1 je zvýrazněna žlutou barvou). V t₂ přichází τ₁, přerušuje provádění τ₂; v t₃ vstupuje do KS_R2 (její obsazenost je zvýrazněna červenou barvou) a v t₄ požaduje vstup do KS_R1, která je však stále obsazena úlohou τ₂ – ta ji pro přerušení úlohou τ₁ nestihla uvolnit. Úloha τ₁ se tedy stane nepřipravenou k běhu, procesor je jí odebrán a předán úloze τ₂. V t₅ požaduje τ₂ vstup do KS_R2, která je však obsazena úlohou τ₁. Je zřejmé, že každá z úloh τ₁, τ₂ by mohla pokračovat v běhu za předpokladu, že by druhá z nich uvolnila jí obsazenou KS. Nicméně to možné není, a dojde tedy k uváznutí (v obr. 6 vyobrazeno modrou barvou). Obecně může uváznutí nastat i na množině n úloh (τ₁, …, τ_n), a to za předpokladu, že jsou současně splněny následující podmínky: pro i = 1, …, n platí: τ_i je v KS_Ri a čeká na uvolnění KS_Rj obsazené úlohou τ_j, kde j = (i + 1) mod (n + 1), tj. τ₁ na τ₂, …, τ_n na τ₁ – čekání je cyklické, a k prostředkům se přistupuje výhradně v rámci příslušných KS (tj. zdroj R může uvolnit pouze úloha, která je v KS_R). 

Protokoly přístupu k prostředkům

Zde bude představen přehled typických způsobů řešení již zmíněných problémů prostředky RTOS označovanými jako protokoly přístupu k prostředkům. Stručně budou zmíněny principy a vlastnosti protokolů NPP, PIP a PCP. U každého z nich bude pozornost soustředěna na popis následujících skutečností: princip činnosti, požadavku kladeného na realizaci v RTOS, dopad na dobu blokování a schopnost zamezit již popsaným problémům.

Protokol NPP (nepreemptivní protokol, Non Preemptive Protocol) zamezuje preempci během provádění KS. Realizace NPP prostředky RTOS je jednoduchá – úloze τ vstupující do KS je, až do dokončení KS, zvýšena priorita na nejvyšší možnou. Výhoda tohoto přístupu je zřejmá: obsazená KS je vždy dokončena bez přerušení, tj. atomicky. Protokol NPP zamezuje inverzi priorit i uváznutí a ohraničuje shora dobu blokování. Jeho velkým nedostatkem je, že během provádění KS mohou být blokovány i úlohy, které mají prioritu významnější než P_τ (mimo KS by jistě vedly k přerušení provádění τ) a k žádnému prostředku nepřistupují.

Protokol PIP (protokol dědění priorit, Priority Inheritance Protocol) se snaží odstranit již uvedený nedostatek a omezit dopad protokolu pouze na úlohy přistupující k prostředkům. Princip PIP je následující: chce-li v čase t do KS obsazené úlohou τ₁ s prioritou P₁ vstoupit úloha τ₂ s P₂ > P₁, je P₁ změněna na P₂, a to od času t do času uvolnění KS. Předností protokolu PIP je, že odstraňuje nedokonalost protokolu NPP a ohraničuje shora dobu inverze priorit. Jeho nedostatkem je, že nezamezuje řetězenému blokování (tj. úloha s velkou prioritou přistupující k n prostředkům může být blokována n-krát) ani uváznutí.

Z hlavních nedostatků protokolu PIP vyplynuly snahy rozšířit PIP o schopnost zamezit uváznutí a řetězenému blokování. Princip tohoto rozšíření, známého pod označením PCP (protokol stropování/mezních priorit, Priority Ceiling Protocol), je následující: každému prostředku R, potencionálně používanému úlohami τ₁, …, τ_m, je přiřazena tzv. stropová, popř. mezní priorita (P_R) rovná největší z hodnot P₁, …, P_m. Při snaze o přístup do obsazené KS dědí úloha v KS prioritu podle PIP. Řetězenému blokování a uváznutí zamezuje následující pravidlo: úloha τ může vstoupit do KS_R pouze tehdy, je-li KS_R volná a P_τ > P_max, kde P_max = max(P_R1, …, P_Rk), je největší ze stropových priorit zdrojů R₁, …, R_k momentálně používaných ostatními úlohami. Důsledky PCP pro praxi mohou být shrnuty do těchto bodů:

a) úloha může být zablokována i před přístupem k neobsazenému zdroji (prevence řetězeného blokování),

b) úloha s velkou prioritou (τ₁) může být blokována nejvýše jednou úlohou s nízkou prioritou (τ₂) přistupující k témuž R,

c)  po uvolnění KS_R úlohou τ₂ již úloha τ₁ nemůže být při přístupu k žádným prostředkům blokována (avšak τ₁ může být stále blokována úlohou τ₃ s P₃ > P₁; taková úloha však jistě žádný prostředek s τ₁ nesdílí).

Oproti protokolu PIP zamezuje PCP řetězenému blokování i uváznutí. Základní vlastnosti protokolů NPP, PIP a PCP jsou uvedeny v tab. 2.

Jednoduchou modifikací PCP je možné získat protokol IPCP (okamžité PCP, Immediate PCP), jehož princip je následující: nízká priorita úlohy τ₂ nacházející se v KS není zvýšena až v čase blokování úlohy τ₁ s vysokou prioritou při jejím přístupu do KS, ale už v době přístupu τ₂ do KS. V porovnání s PCP je realizace IPCP jednodušší, vede k menšímu počtu přepnutí kontextu, avšak z pohledu jedné úlohy je zapotřebí větší počet změn priority.

Shrnutí

Závislosti představené v tomto článku lze jednak modelovat ve volně dostupných nástrojích – např. TimesTool [8], Cheddar [2] – či zkoumat v souvislosti s realizacemi konkrétních RTOS. I ty nejjednodušší z existujících RTOS totiž zpravidla obsahují alespoň některé ze zmíněných protokolů ve svých jádrech – např. v rámci prostředku mutex, zajišťujícího vzájemně výlučný přístup v jádrech FreeRTOS, či μC/OS-II je zaveden protokol PIP. Mimoto lze rozhraní protokolů PIP nebo PCP také nalézt např. v rámci rozšířené normy POSIX 1003.1c a využít dříve popsané mechanismy ke zkvalitnění návrhu nejen úloh RT, ale i úloh řízených operačními systémy kompatibilními s touto normou.

Další díl seriálu bude zaměřen na přehled mechanismů společného plánování periodických a neperiodických úloh, přičemž cílem bude probrat a představit různé přístupy k dosažení co nejlepšího kompromisu mezi procentem obsloužených neperiodických podnětů a včasným dokončením periodických úloh.

Poděkování

Práce byla podpořena Evropským fondem regionálního rozvoje (ERDF) v rámci projektu Centra excelence IT4Innovations (CZ.1.05/1.1.00/02.0070), projektem Výzkum informačních technologií z hlediska bezpečnosti (CEZ MSM 0021630528) a grantem BUT FIT-S-11-1.

Literatura:

[1] BUTAZZO, G. C.: Hard Real-Time Computing Systems, Predictable Scheduling Algorithms And Applications. Kluwer, 1997, pp. 181–221, ISBN 0-7923-9994-3.

[2] The Cheddar Project: A Free Real Time Scheduling Analyzer [on-line]. Dostupné z http://beru.univ-brest.fr/~singhoff/cheddar/.

[3] COTTET, F. – DELACROIX, J. – KAISER, C. – MAMMERI, Z.: Scheduling in Real-Time Systems. John Wiley & Sons, 2002, ISBN 0-470-84766-2.

[4] STRNADEL, J.: Návrh časově kritických systémů I: specifikace a verifikace. Automa, 2010, roč. 16, č. 10, s. 42–44, ISSN 1210-9592.

[5] 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.

[6] STRNADEL, J.: Návrh časově kritických systémů III: priorita úloh. Automa, 2011, roč. 17, č. 2, s. 50–52, ISSN 1210-9592.

[7] STRNADEL, J.: Návrh časově kritických systémů IV: realizace prostředky RTOS. Automa, 2011, roč. 17, č. 4, s. 58–60, ISSN 1210-9592.

[8] The Times Tool [on-line]. Dostupné z <www.timestool.com>.  

Ing. Josef Strnadel, Ph. D., Fakulta informačních technologií,

Vysoké učení technické v Brně (strnadel@fit.vutbr.cz)

Obr. 1. Ilustrace k precedenčnimu grafu

Obr. 2. Plány RM a EDF pro množinu úloh s původními parametry (a, b) a s parametry modifikovanými (c, d) podle precedenčního grafu z obr. 1b (pozn.: vyobrazené plány jsou výstupem z nástroje Times Tool [8])

Obr. 3. Ilustrace k principu vlivu precedenčního grafu (a) na změny parametrů úloh plánovaných pomocí EDF (b)

Obr. 4. Ilustrace k blokování

Obr. 5. Ilustrace k inverzi priorit

Obr. 6. Ilustrace k uváznutí

Tab. 1. Ilustrace vlivu precedenčního grafu z obr. 1b na parametry úloh (změněné parametry jsou v pravém horním indexu označeny symbolem ^*)

Tab. 2. Shrnutí vlastností protokolů NPP, PIP a PCP