Aktuální vydání

celé číslo

02

2021

Systémy pro řízení vodárenských sítí a ČOV

Hladinoměry

celé číslo

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í – časovouprostorovou. Č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 GP = (V, E), jehož uzly z množiny V představují úlohy a jehož orientované hrany z množiny E Í × 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 τ1 zajišťující periodické vzorkování určené veličiny (např. teploty) a úloha τ2 periodicky produkující průměr ze čtyř posledních vzorků poskytnutých úlohou τ1. Tuto závislost reprezentuje precedenční graf na obr. 1a.

Obecně pro zajištění τi ® τj musí platit: rjri (tj. τj nesmí být vyvolána dříve než τi) a PiPj (tj. τj nesmí mít významnější prioritu než τi). Pro příklad z obr. 1a to znamená nastavit r2 na hodnotu z intervalu (r1 + 3T1, r1 + 4T1) priority P tak, aby platilo P1 P2.

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 ri, rj úloh τi, *τj změněny na ri*, rj* tak, aby platilo rj* ≥ max(ri, ri*) a Pi  ≥ Pj (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 (ri), 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 Di*, Dj* parametrů Di, Dj úloh τi, τj: Dj* ≥ max(Dj, Di*). 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: rj* ≥ max(ri* + Ci, rj), tj. τj nesmí být vyvolána dříve, než by končila τi, a di* ≥ min(dj*Cj, di), 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 τ1. Její parametr r1 se změní na hodnotu r1* = max(0, r1) = 0. Poté se zpracovávají následovníci. Těmi jsou τ2, τ4 – mění se tedy r2, r4 následovně: r2* = max(r1* + C1, r2) = 3, r4* = max(r1* + C1, r4) = 3. Další změna se provede u úlohy τ3, následovníka τ2: r3* = max(r2* + C2, r3) = 5. Jako poslední se změní r5; jelikož τ5 je následovníkem τ2τ4, hodnota bude změněna na r5* = max(max(r2* + C2, r4* + C4), r5) = 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 τ3, τ5. Hodnoty d3, d5 se změní na d3* = min(¥, d3) = 12, d5* = min(¥, d5) = 9. Poté se zpracují předchůdci úloh τ3, τ5, tj. úlohy τ2τ4. Protože τ4 má jediného následovníka (τ5), bude d4 změněna na d4* = min(d5*C5, d4) = 7. Úloha τ2 má však následovníky dva (τ3τ5), a proto bude d2 změněna na d2* = min(min(d3*C3, d5*C5), d2) = 7. Poslední úloha (τ1) má předchůdce τ2, τ4d1, tedy bude změněna na d1* =  min(min(d2*C2, d4*C4), d1) = 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 t1 je spuštěna úloha τ1 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 t2 však τ1 požaduje přístup k (dosud neuvolněnému) R. Tento přístup není umožněn, procesor je τ1 odebrán a předán úloze τn, aby tato doužívala R, uvolnila jej a τ1 poté mohla pokračovat v běhu (čas t4). Popsaná situace představuje tzv. přímé (direct) blokování úlohy τ1 úlohou τn, způsobené nedostupností prostředku (v obr. 4 vyznačené jako BD). Mimoto existují i další typy blokování, např. nepřímé (indirect, v obr. 4 vyznačené jako BI), obvykle zapříčiněné dočasným propůjčením vysoké priority úloze s nízkou prioritou pro minimalizaci doby BD, č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 (KSR). Je-li v KSR úloha, je KSR 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 τ1, …, τ4 P1 (nejvyšší) > … > P4 (nejnižší), přičemž τ2, τ4 sdílejí prostředek R. Zaměřme se na dobu odezvy úlohy τ2 – ta je delší o dobu potřebnou k provedení úlohy τ1 s prioritou P1 > P2 (doba mezi t3t4) a dobu přímého blokování úlohy τ2 úlohou τ4 s prioritou P4 < P2 (doba mezi t1t5). Avšak doba přístupu τ2 k R (tj. přítomnosti τ2 v KSR) je také prodloužena o dobu běhu úlohy τ3, která ani nesdílí prostředek s τ2, ani pro ni neplatí P3 > P2. V t2 se totiž τ2 stává nepřipravenou k běhu z důvodu nedostupnosti R a τ3 je v t2 jediná připravená úloha s prioritou větší než P4. Úloha τ3 tedy začíná běžet, čímž však odsouvá čas uvolnění R úlohou τ4 až na t4. Inverze priorit tedy nastává v intervalu mezi t2, t3t4, t5. Doba blokování prostředku R úlohou τ4 – a tedy i doba odezvy úlohy τ2 – je tudíž „zbytečně“ prodloužena o (t3t2) + (t5 – t4) č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 τ1, τ2 sdílejících prostředky R1, R2 a přistupující k nim způsobem podle obr. 6. V čase t1 vstoupí τ2 do KSR1 (obsazenost KSR1 je zvýrazněna žlutou barvou). V t2 přichází τ1, přerušuje provádění τ2; v t3 vstupuje do KSR2 (její obsazenost je zvýrazněna červenou barvou) a v t4 požaduje vstup do KSR1, která je však stále obsazena úlohou τ2 – ta ji pro přerušení úlohou τ1 nestihla uvolnit. Úloha τ1 se tedy stane nepřipravenou k běhu, procesor je jí odebrán a předán úloze τ2. V t5 požaduje τ2 vstup do KSR2, která je však obsazena úlohou τ1. Je zřejmé, že každá z úloh τ1, τ2 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 (τ1, …, τ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 KSRi a čeká na uvolnění KSRj obsazené úlohou τj, kde j = (i + 1) mod (n + 1), tj. τ1 na τ2, …, τn na τ1 – č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 KSR). 

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 τ1 s prioritou P1 vstoupit úloha τ2P2 > P1, je P1 změněna na P2, 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 τ1, …, τm, je přiřazena tzv. stropová, popř. mezní priorita (PR) rovná největší z hodnot P1, …, Pm. 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 KSR pouze tehdy, je-li KSR volná a Pτ > Pmax, kde Pmax = max(PR1, …, PRk), je největší ze stropových priorit zdrojů R1, …, Rk 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 (τ1) může být blokována nejvýše jednou úlohou s nízkou prioritou (τ2) přistupující k témuž R,

c)  po uvolnění KSR úlohou τ2 již úloha τ1 nemůže být při přístupu k žádným prostředkům blokována (avšak τ1 může být stále blokována úlohou τ3P3 > P1; taková úloha však jistě žádný prostředek s τ1 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 τ2 nacházející se v KS není zvýšena až v čase blokování úlohy τ1 s vysokou prioritou při jejím přístupu do KS, ale už v době přístupu τ2 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 *)

Úloha

(Di = Ti)

Původní parametry

Parametry pro RM

Parametry pro EDF

ri

Ci

di

ri*

Pi

Pi*

ri*

di*

Pi

Pi*

τ1

0

3

12

0

5

10

0

5

5

10

τ2

0

2

11

1

8

8

3

7

8

8

τ3

0

3

12

2

5

5

5

12

5

2

τ4

0

1

11

1

8

8

3

7

8

8

τ5

0

2

9

2

10

5

5

9

10

5

 

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

Vlastnost

Protokol

NPP

PIP

PCP

Zamezuje nežádoucímu blokování?

ne

ano

ano

Počet blokování při sdílení prostředků

1

k

1

Zamezuje inverzi priorit?

ano

ano

ano

Zamezuje uváznutí?

ano

ne

ano

Realizační požadavky

malé

malé

velké