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

Plánování úloh v systémech RT – IV: víceprocesorové prostředí

V předcházejícím článku [7] bylo ukázáno, že přesahují-li výpočetní požadavky kladené na procesor jeho výpočetní možnosti, lze východisko z přetížení nalézt, jestliže se použijí speciální, pro tento účel navržené mechanismy přiřazování priorit a plánovače. Avšak i tyto jsou nuceny dočasně pozastavit běh instancí či modifikovat parametry některých úloh proto, aby se přetížení předcházelo či bylo zemezeno důsledkům z něj plynoucích, zejména tzv. dominovému efektu, vedoucímu k neřízenému a často také náhlému kolapsu systému. Při použití těchto mechanismů je tedy chování systému předvídatelné v tom smyslu, že již v době návrhu systému je pro případ přetížení známo, které z úloh budou vždy dokončeny včas a které včas dokončeny být nemusí. 

Plánováním úloh ve víceprocesorovém prostředí

Může se zdát, že tento důsledek, z pohledu podílu včasně dokončených instancí úloh nepříjemný, lze jednoduše odstranit např. zvětšením počtu procesorů schopných provádět úlohy. Je nutné si ale uvědomit, že použitím m > 1 procesorů sice vzroste výpočetní výkon systému, což obecně může přispět k včasnému dokončování úloh (nutná podmínka U =ui ≤ 1 plánovatelnosti množin úloh na jednom procesoru je totiž modifikována, a tedy i zobecněna na m; symbolika použitá v článku je zavedena ve [4]), ale problém plánování úloh se rozšiřuje o další rozměry. Zaprvé je třeba rozhodnout, které úlohy poběží na kterém z procesorů. Dále je třeba rozhodnout, zda úlohy budou procesorům přiděleny pevně a neměnně za běhu systému, či zda a jak budou moci mezi procesory za běhu migrovat, zda daná úloha může být současně rozpracována několika identickými, nebo odlišnými procesory či jaké mechanismy přiřazování priorit budou na jednotlivých procesorech použity, jak budou procesory propojeny, jak budou komunikovat atd. Protože úplný popis souvisejících problémů by výrazně přesáhl rámec tohoto článku, omezme se pouze na představení typických problémů a způsobů jejich řešení prostřednictvím vybraných zástupců související třídy plánovacích mechanismů.

Nejprve bude nastíněno, jaké, na první pohled neočekávané, situace mohou při plánování úloh ve víceprocesorovém prostředí nastávat [3]. Předně, z plánovatelnosti množiny Γ (tj. z garance včasného dokončení všech úloh z Γ) v jednoprocesorovém prostředí neplyne plánovatelnost Γ ve víceprocesorovém prostředí. Tuto situaci ilustruje obr. 1 s využitím množiny Γ = {τ1, τ2, τ3, τ4} úloh tvaru τi(ri, Ci, Di, Ti): τ1(0, 1, 2, 10), τ2(0, 3, 3, 10), τ3(1, 2, 3, 10) a τ4(2, 3, 3, 10) určených k běhu na dvou procesorech (tj. m = 2) s možností migrace úloh mezi procesory za běhu systému a přiřazováním priorit mechanismem EDF (Earlier Deadline First). Jsou-li úlohy přidělovány procesorům nevhodně, některá z nich nemusí být dokončena včas (v obr. 1a je to τ4 – viz červeně zbarvené pozadí) přesto, že množina Γ pro dané m plánovatelná je (obr. 1b).

Na rozdíl od jednoprocesorového může ve víceprocesorovém prostředí dále nastat situace, kdy rostoucí m, zkrácení nejhorších dob provádění úloh C, zmírnění či odstranění závislostí mezi úlohami a jiné změny běžně vedoucí ke snížení výpočetní zátěže mohou být příčinou neplánovatelnosti dané množiny úloh – viz obr. 2 s množinou Γ = {τ1, τ2, τ3, τ4, τ5, τ6} úloh tvaru τi(ri, Ci, Di, Ti): τ1(0, 5, 10, 30), τ2(0, [2, 6], 10, 30), τ3(4, 8, 11, 30), τ4(0, 10, 20, 30), τ5(5, 100, 195, 200), τ6(7, 2, 15, 30), pro jejichž priority platí P1 >… > P6. Na obr. 2 (plán je zobrazen pouze v rozmezí t = 0 až t = 26) si např. povšimněme, že v obou mezních hodnotách intervalu <2;6> je Γ plánovatelná (obr. 2a, b), zatímco např. v případě na obr. 2c, kdy se C2 nachází blíže středu daného intervalu, Γ plánovatelná není. Na obr. 2d (C2 = 5) je ilustrováno, že úlohy na jednom z procesorů (zde CPU2) mohou být dokonce dokončeny dříve než v případě na obr. 2a pro C2 = 2.

Podmínky plánovatelnosti pro vybrané případy

Jelikož problematika plánování úloh ve víceprocesorovém prostředí je velmi komplikovaná, nelze nalézt mechanismus, který by byl pro obecnou množinu úloh Γ, obecné víceprocesorové prostředí a způsob přiřazování priorit schopen rozhodnout, zda Γ je či není plánovatelná, nebo byl schopen zaručit plánovatelnost. Takový mechanismus lze nalézt pouze pro úzce vymezené případy, z nichž některé jsou představeny v následujícím textu.

Vybraný případ A

Následující mechanismus garantuje plánovatelnost pro Γ = {τ1, …,τn} periodických nezávislých úloh určených k běhu na m identických procesorech s migrací úloh mezi procesory povolenou výhradně při preempci, s nepřípustným současným rozpracováním jedné úlohy na více procesorech a se statickými prioritami přiřazenými úlohám τi takto:

  • je-li ui > m/(3m – 2), je z nejvýznamnějších priorit úloze τi přiřazena libovolná, ale poté neměnná priorita,
  • jinak je úloze τi přiřazena priorita podle mechanismu RM (Rate Monotonic).

Množina úloh Γ je plánovatelná na m procesorech, platí-li postačující podmínka U ≤ m2/(3m – 2). Jelikož však tato podmínka není zároveň nutná, mohou existovat plánovatelné množiny, které ji nesplňují. Tento mechanismus si ilustrujeme na následujícím příkladě uvažujícím m = 3 a množinu Γ = {τ1, τ2, τ3, τ4, τ5} úloh tvaru τi(ri, Ci, Di = Ti): τ1(0, 1, 7), τ2(0, 2, 15), τ3(0, 9, 20), τ4(0, 11, 24), τ5(0, 2, 25). Pro tuto množinu jsou hodnoty ui= Ci/Tinásledující: u1 = 1/7 = 0,143, u2 = 2/15 = 0,133, u3 = 9/20 = 0,450, u4 = 11/24  = 0,458, u5 = 2/25 = 0,08. Výraz m/(3m – 2) má po dosazení m= 3 hodnotu 3/(3·3 – 2) = 3/7 ≈ 0,428 6. Priority tedy budou přiřazeny takto:

  • jelikož ui> 0,428 6 platí pouze pro i = 3 a i = 4, jsou nejvýznamnější priority přiřazeny pouze úlohám τ3, τ4,
  • ostatním úlohám jsou priority přiřazeny podle mechanismu RM.

Ve výsledku tedy budou úlohám přiřazeny priority s významností klesající ve směru zleva doprava s pořadím úloh, které může být buď τ3,τ4, τ1, τ2, τ5, nebo τ4,τ3, τ1, τ2, τ5.

Nutná podmínka plánovatelnosti (tj. U = 1,265 ≤m = 3) je splněna – není tedy vyloučeno, že Γ je plánovatelná. Po dosazení m = 3 do U ≤ m2/(3m – 2) se dostane 1,265 ≤ 1,286; nerovnost platí, Γ je tedy plánovatelná. Výsledný plán je zobrazen na obr. 3.

Vybraný případ B (metoda dekompozice hyperperiody)

Nutnou i postačující podmínku plánovatelnosti pro množiny periodických, nezávislých úloh s Di = Ti lze např. nalézt, jsou-li procesory přiřazovány úlohám při použití dekompozice hyperperiody (nejmenšího společného násobku period Ti všech úloh) na úseky ohraničené časy příchodů ri úloh. Princip je následující. Úlohy jsou nejprve uspořádány podle nerostoucích hodnot jejich ui (tedy platí uiui+1); poté jsou po jednotlivých úsecích procesory postupně přidělovány úlohám vždy na díl úseku přímo úměrný velikosti jejich ui. Tento mechanismus vede na postačující a nutnou podmínku plánovatelnosti tvaru

vzorec (1)

Mechanismus si pro m = 2 ilustrujeme při použití množiny Γ = {τ1, τ2, τ3} úloh tvaru τi(ri, Ci, Di = Ti) uspořádaných podle hodnot jejich ui = Ci/Ti: τ1(0, 2, 3) s u1 = 2/3, τ2(0, 2, 4) s u2 = 2/4 a τ3(0, 3, 6) s u3 = 3/6. Nutná podmínka plánovatelnosti (tj. U = 5/3 ≤m = 2) je splněna – není tedy vyloučeno, že Γ je plánovatelná. Nutná i postačující podmínka (1) bude po dosazení tvaru max[max(2/3), 5/6] = 5/6 ≤ 1, a bude tedy splněna. Daná Γ je tudíž na dvou procesorech plánovatelná. Hyperperioda má délku dvanáct časových jednotek (nejmenší společný násobek period T1 = 3, T2 = 4 a T3 = 6) a při sestavování plánu bude rozčleněna celkem na šest úseků vymezených časy volání úloh během hyperperiody – tyto úseky budou tedy ohraničeny časy 0, 3, 4, 6, 8, 9 a 12 časových jednotek. Úsek po úseku jsou poté procesory postupně přidělovány úlohám na díl úseku přímo úměrný velikosti jejich ui. Například v úseku mezi t = 0 a t = 3 o délce tří časových jednotek budou procesory – označme si je CPU1, CPU2 – přiřazeny úlohám takto:

  • τ1 poběží na CPU1 po dobu u1 = 2/3 délky úseku, tj. 3·2/3 = 2 časových jednotek,
  • τ2 poběží celkem po dobu 1/2 délky úseku, tj. 3·1/2 = 1,5 jednotky: dílem na procesoru CPU1, na němž již zbývá pouze jedna časová jednotka, a dílem na CPU2,
  • τ3 poběží po dobu 1/2 délky úseku, tj. 3·1/2 =1,5 časové jednotky na CPU2.

Oba procesory jsou v tomto úseku nečinné po dobu 1/2 časové jednotky. Poté jsou úlohy přiřazeny procesorům pro interval t = 3 až t = 4 o délce jedné časové jednotky atd. Plán v délce hyperperiody je znázorněn na obr. 4.

Přidělování úloh mechanismem RM s minimalizací počtu procesorů

V poslední části tohoto článku je představeno několik metod přiřazujících procesorům úlohy s prioritami podle mechanismu RM [4] pevně a za běhu systému neměnně, přičemž cílem je zajistit plánovatelnost n-prvkové množiny úloh Γ při použití co nejmenšího počtu m procesorů [1]. Vstupem těchto metod tedy je Γ, výstupem přiřazení úloh procesorům tak, aby Γ byla plánovatelná a hodnota m byla minimální. Budou představeny principy a základní vlastnosti mechanismů Rate Monotonic Next Fit (RMNF), Rate Monotonic First Fit (RMFF) a Rate Monotonic Best Fit (RMBF).

Uvedené tři mechanismy jsou založeny na využití postačující podmínky plánovatelnosti n úloh označované WC (Worst-Case) tvaru

vzorec (2) 

popř. (mírnější) podmínky plánovatelnosti (n – 1) úloh označované IP (Increasing Period), která je z podmínky WC odvozena. Nechť

vzorec (3)

pak podmínka IP má tvar

 vzorec (4)

Je-li splněna podmínka WC (2) nebo alespoň podmínka IP (4), je Γ plánovatelná při přiřazení priorit podle RM – existují totiž plánovatelné množiny úloh nesplňující (přísnější) podmínku WC, ale splňující (mírnější) podmínku IP. 

Mechanismus RMNF

Postup při použití mechanismu RMNF (Rate Monotonic Next Fit) je takovýto:

  • v kroku 1 jsou úlohy uspořádány podle neklesajících hodnot jejich period, tj. v pořadí τ1, …, τn pro T1 ≤ … ≤ Tn,
  • v kroku 2 je stav i počitadla úloh, stejně jako stav j počitadla alokovaných procesorů, nastaven na hodnotu 1,
  • v kroku 3 je úloha τi přidělena k běhu na procesoru CPUj, ovšem pouze za podmínky, že množina úloh obsahující τi a úlohy již dříve přidělené procesoru CPUj splňuje podmínku IP (4); jinak je alokován nový procesor (tj. stav počitadla j je zvětšen o 1) a τi je přidělena k běhu na procesoru CPUj,
  • platí-li i < n, pak dojde ke zvětšení stavu počitadla úloh o 1 a návratu na krok 3; jinak mechanismus RMNF končí
  • počet alokovaných procesorů je roven stavu počitadla j.

Princip mechanismu RMNF je ilustrován na obr. 5a při použití množiny Γ = {τ1, τ2, τ3, τ4, τ5} úloh tvaru τi(ri, Ci, Di = Ti): τ1(0, 1, 10), τ2(0, 3, 10),τ3(0, 8, 10),τ4(0, 1, 11),τ5(0, 4, 11). Úlohy budou přiděleny třem procesorům, a to následovně: na procesoru CPU1 poběží úlohy τ1, τ2, na CPU2 úlohy τ3, τ4 a na CPU3 úloha τ5. Pro činitele využití procesorů platí UCPU1 = 0,4, UCPU2 = 0,890 91 a UCPU3 = 0,363 64. Všechny úlohy budou dokončeny včas.

Mechanismus RMFF

Princip mechanismu RMFF (Rate Monotonic First Fit) je založen na myšlence zkoušet přidělovat po řadě každou z úloh τ1τn postupně již rezervovaným procesorům CPU1 až CPUk, a to dokud nebude nalezen procesor schopný zajistit včasné provedení úlohy, tj. procesor splňující alespoň podmínku IP (4). Není-li takový nalezen, je přidán nový procesor CPU(k + 1).

Přidělení úloh z příkladu k RMNF (opět třem) procesorům bude podle RMFF následující: na procesoru CPU1 poběží úlohy τ1,τ2,τ4, na CPU2 úloha τ3 a na CPU3 úloha τ5 (část plánu je zobrazena na obr. 5b). Pro činitele využití procesorů platí UCPU1 = 0,490 91, UCPU2 = 0,8 a UCPU3 = 0,363 64. Oproti RMNF byla tedy při použití mechanismu RMFF přesunuta část zátěže CPU2 (dané prováděním τ4) na CPU1. Oproti RMNF je mechanismus RMFF díky této své vlastnosti schopen naplánovat obecnou množinu úloh při použití menšího počtu procesorů.

Mechanismus RMBF

Mechanismus RMBF (Rate Monotonic Best Fit) přiřazuje úlohu procesoru, který má na množině procesorů splňujících podmínku IP (4) největší hodnotu činitele využití. Cílem tohoto způsobu přidělování je maximalizovat využití již přidělených procesorů, a v důsledku tak minimalizovat jejich celkový počet. Množinu úloh z příkladů k RMNF a RMFF je mechanismus RMBF schopen naplánovat při použití pouze dvou procesorů, přičemž na procesoru CPU1 poběží úlohy τ1,τ2,τ3 a na CPU2 úlohy τ4, τ5 (část plánu je zobrazena na obr. 5c). Pro činitele využití procesorů platí UCPU1 = 0,763 64, UCPU2 = 0,890 91. Oproti RMNF a RMFF bylo zmenšení počtu procesorů ze tří na dva umožněno zvětšením zátěže CPU1 zejména o zátěž z původního CPU3. Překvapivě však mechanismus RMBF není schopen naplánovat obecnou množinu úloh při použití menšího počtu procesorů než mechanismus RMFF.

Ostatní mechanismy

Vedle zmíněných metod vycházejících z mechanismu RM, modelovatelných např. volně dostupným nástrojem Cheddar [2], existují mnohé další – např. RMST (Rate Monotonic Small Tasks) či RMGT (Rate Monotonic General Tasks), schopné naplánovat množiny úloh při použití ještě menšího počtu procesorů než mechanismy RMNF, RMFF a RMBF. Obdobné mechanismy přidělování procesorů úlohám lze nalézt také pro přiřazování priorit např. podle EDF – zmiňme alespoň názvy mechanismů EDZL (Earliest Dead­line Zero Laxity) či EDF-UM (Earliest Deadline First – Utilization Monotonic).

Závěrem

Následujícím, posledním článkem bude seriál celkem pěti článků na téma plánování úloh v časově kritických systémech uzavřen. Závěrečný článek bude věnován přehledu pojmů a problémů souvisejících se zvýšením spolehlivosti programového vybavení používaného při realizaci systémů reálného času (systémy RT) a představení možných způsobů řešení těchto problémů na úrovni programového vybavení a jádra operačního systému reálného času (RTOS).

Poděkování

Tento článek byl vypracován v rámci projektu Centrum excelence IT4Innovations, reg. č. CZ.1.05/1.1.00/02.0070, podporovaného Operačním programem Výzkum a vývoj pro inovace, financovaného ze strukturálních fondů EU a ze státního rozpočtu ČR, projektu Výzkum informačních technologií z hlediska bezpečnosti (CEZ MSM 0021630528) a grantu BUT FIT-S-11-1.

Literatura:

[1] BURCHARD, A. – LIEBEHERR, J. – OH, Y. – SON, S. H.: Assigning Real-Time Tasks to Homogeneous Multiprocessor Systems. Technical Report CS-94-01, University of Virginia, 1994.

[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ů II: úlohy reálného času. Automa, 2010, roč. 16, č. 12, s. 18–19, ISSN 1210-9592.

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

[6] STRNADEL, J.: Plánování úloh v systémech RT – I: závislé úlohy. Automa, 2012, roč. 18,
č. 10, s. 42–45, ISSN 1210-9592.

[7] STRNADEL, J.: Plánování úloh v systémech RT – II: neperiodické úlohy. Automa, 2012, roč. 18, č. 11, s. 44–46, ISSN 1210-9592.

[8] STRNADEL, J.: Plánování úloh v systémech RT – III: přetížení systému. Automa, 2012, roč. 18, č. 12, s. 44–47, ISSN 1210-9592 

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

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

Obr. 1. Ilustrace k přechodu od plánování v jednoprocesorovém na víceprocesorové prostředí (CPU – procesorová jednotka)

Obr. 2. Ilustrace k anomáliím při plánování úloh ve víceprocesorovém prostředí

Obr. 3. Ilustrace k rozložení úloh mezi procesory

Obr. 4. Ilustrace k přidělení úloh procesorům na základě dekompozice hyperperiody

Obr. 5. Ilustrace k přidělení úloh procesorům mechanismy RMNF (a), RMFF (b) a RMBF (c)