Aktuální vydání

celé číslo

08

2020

Mozaika novinek a informací

Restart ekonomiky

celé číslo

Plánování úloh v systémech RT – II: neperiodické úlohy

Druhý díl seriálu nepřímo navazuje na [6], kde byly představeny základní mechanismy přiřazování statických (pevných) priorit periodickým úlohám tzv. reálného času (real-time, RT, úlohy RT), a na [5], kde bylo zmíněno, že vedle periodických úloh RT mohou existovat i úlohy neperiodické. Mezi neperiodickými úlohami RT jsou obvykle rozlišovány úlohy aperiodické (intervaly příchodů úloh tohoto typu jsou předem neznámé) a úlohy sporadické (je u nich známa nejkratší doba mezi příchody). V tomto článku jsou představeny základní mechanismy společného (tzv. hybridního) plánování množin periodických a neperiodických úloh (hybrid/joint scheduling) [1], [2]. Výklad předpokládá u čtenáře znalost modelu úlohy RT a jeho symboliky podle [5].

Vliv aperiodických úloh na chod systému

Ještě před započetím popisu mechanismů je nutné zdůraznit, že zejména aperiodické úlohy a s velkou prioritou představují problém z pohledu nekontrolovatelného zvýšení zátěže procesoru, na kterém, vedle aperiodických úloh  τ1, …, τk (obvykle s odezvami typu soft), mohou běžet periodické či sporadické úlohy τk + 1, …,  τk + m s odezvami typu firm či hard. Celkové využití procesoru U společnou množinou úloh Γ = {τ1, …, τk, τk + 1, …, τk + m} je dáno součtem ui využití procesoru dílčími úlohami z Γ [5], tedy

           vzorec (1)

Pro = 1 je součet výpočetních požadavků kladených na procesor roven výpočetním možnostem procesoru (tj. procesor je zcela vytížen), a jakýkoliv další nárůst U tudíž povede k přetížení procesoru, následnému nedodržení časových omezení některých úloh, či dokonce k náhlému kolapsu systému. Z podstaty aperiodických úloh plyne, že podněty vedoucí k jejich spuštění mohou přicházet v nekonečně krátkých intervalech, tj. Ti0, což vede na U ¥. Každý dobře navržený systém RT tedy musí být připraven vhodně reagovat na situaci, kdy počet podnětů v čase t nebude ohraničen shora; přitom musí zajistit, aby hodnota U klesla nejen pod 1, ale i pod hodnotu U*(M), garantující plánovatelnost úloh při použití daného mechanismu přiřazování priorit (M).

Následující text bude zaměřen na popis vybraných mechanismů společného plánování periodických a aperiodických úloh. Důvody, proč nebudou představeny mechanismy zaměřené čistě na plánování aperiodických či sporadických úloh, jsou tyto:

a) sporadické úlohy vykazují, vzhledem k omezenosti dob jejich příchodů v rámci daného intervalu, podobné vlastnosti jako periodické úlohy,

b) je-li mechanismus schopen společně plánovat množiny periodických a aperiodických úloh, je schopen plánovat tyto množiny i tehdy, je-li podmnožina periodických úloh prázdná.

Pro jednotný popis mechanismů si označme množinu periodických (aperiodických) úloh symbolem ΓP (ΓA) a činitel využití procesoru úlohami z ΓP symbolem UP.

Plánování v pozadí (BS)

Jako první z mechanismů společného plánování bude představen mechanismus plánování v pozadí (Background Scheduling – BS). Tento mechanismus je založen na následujícím principu. Úlohám z ΓA je přidělen procesor pouze v intervalech, kdy jej nevyžadují úlohy z ΓP. Úlohy z ΓP (ΓA) pak běží v tzv. popředí (pozadí). K realizaci BS jsou obvykle třeba dvě fronty úloh připravených k běhu (jedna pro úlohy z ΓP, druhá pro ty z ΓA), úlohy každé z front mohou být plánovány různými mechanismy. Pro správnou činnost BS je nutné přidělit úlohám priority tak, aby priority úloh z ΓP byly významnější než priority úloh z ΓA, tj. aby pro všechny úlohy τiΓPτjΓA platilo Pi > kde Pi, Pj jsou priority úloh i, j.

Pj. Z jednoduchosti realizace BS plyne jeho hlavní nedostatek: doba odezvy aperiodických úloh RA roste s hodnotou UP blížící se k 1 do nekonečna (RA ¥ pro UP 1). Ale k přetížení procesoru v důsledku nadměrného počtu aperiodických úloh jistě nedojde.

Ilustrace k BS je na obr. 1 – je zřejmé, že od doby vzniku aperiodických požadavků, tj. požadavku č. 1 (2) příchozího v t1 (t4) a vyžadujícího 1 (2) výpočetní jednotku(y) na procesoru, jsou prováděny až v době, kdy procesor není využíván úlohami τ1, τ2 ΠΓP.

Servery úloh

V dalším textu se z existujících mechanismů společného plánování zaměřme na tzv. servery úloh. Serverem úloh bude chápána periodická úloha τS (s periodou TS) zařazená do systému speciálně za účelem obsluhy aperiodických podnětů. Dobu, kterou má server vyhrazenu pro obsluhu aperiodických podnětů, nazvěme kapacita serveru; bude označována symbolem CS. Server bude značen symbolem τS(TS, CS), využití procesoru serverem US = CS/TS.

Vyzývací server (PS)

Jako první ze serverů si představme tzv. vyzývací server (Polling Server – PS). Jeho princip spočívá v tom, že aperiodické úlohy jsou plánovány stejným mechanismem jako periodické. Je-li serveru přidělen procesor v čase tS a existují-li neobsloužené aperiodické požadavky, server obslouží požadavky až do počtu souhrnně nevyžadujícího k obsluze více než CS jednotek času na procesoru; obsluhy nad tento limit jsou odsouvány do další TS. Jestliže v tS neexistují neobsloužené aperiodické požadavky, server se dobrovolně vzdává přidělení procesoru i nedočerpané kapacity, a to až do následující TS. Realizace PS spočívá v přidání úlohy τS(TS, CS) do existující množiny ΓP, přičemž je nutné pečlivě zvážit volbu hodnot TSCS a stanovit postup, na jehož základě bude procesor přidělen aperiodickým úlohám v případě, že v čase tS existuje několik neobsloužených aperiodických požadavků. Předností PS (oproti BS) je nastavitelnost TSCS spolu se skutečností, že s příchodem nové TS je CS zcela obnovena (tj. bez ohledu na to, zda a popř. jak byla v minulosti konzumována). Nedostatkem je, že přijde-li aperiodický požadavek krátce poté, co se τS vzdá procesoru, nebude obsluha takového požadavku zahájena dříve než v následující TS. Z toho plyne pro stanovování hodnot Di pro τi ΠΓA plánovaných pomocí PS podmínka DiTS(1+ Ci/TS). Množina úloh Γ je plánovatelná s využitím PS a mechanismu M přiřazování priorit, platí-li UP + US £ U(M).

Princip PS je ilustrován na obr. 2. Kratší doby odezvy aperiodických požadavků je dosaženo díky prodloužení doby odezvy úlohy τ2 ΠΓP. Změna CS v čase je vyobrazena v rámci části plánu pro τS. Klesající hodnota CS signalizuje, že procesorem zpracovává aperiodické úlohy.

Odkládací server (DS)

Ve snaze zmenšit zpoždění začátků provádění, a tím i průměrnou dobu odezvy aperiodických úloh více, než umožňuje PS, lze PS modifikovat na tzv. odkládací server (Deferrable Server – DS), pracující následovně. S příchodem TS je (jako u PS) zcela obnovena CS. Není-li na začátku TS detekován neobsloužený aperiodický požadavek, DS se sice vzdává procesoru, ale ne své nevyčerpané kapacity – tu si až do příchodu další TS ponechává pro obsluhu případných nově vzniklých aperiodických požadavků. Aperiodické požadavky tedy mohou být pomocí DS obslouženy (za předpokladu, že kapacita DS nebyla vyčerpána) i mezi časem, kdy se DS vzdal procesoru, a časem příchodu nové TS. Oproti PS se tedy zkrátila doba odezvy aperiodických požadavků, avšak na úkor odezvy periodických úloh s prioritou nižší než priorita DS – pro zajímavost je možné porovnat plány z obr. 2 (plán pro PS) a obr. 3 (plán pro DS).

Server s výměnou priorit (PE)

Bude-li DS navíc spravovat informaci o tom, kterým úlohám byl přidělen (z pohledu serveru zapůjčen) procesor poté, co se jej DS z důvodu absence aperiodických požadavků vzdal, získá se server s výměnou (směnou, záměnou) priorit (Priority Exchange Server – PE). Kapacita serveru se po jeho vzdání se procesoru „neztrácí“, ale zapůjčuje úlohám běžícím v době, kdy je CS nenulová. Informaci o těchto zápůjčkách udržuje PE pro každou z úloh tak, že za běhu úlohy se její zápůjčka s každou jednotkou času zvyšuje o 1, nejvýše však do celkové výše zápůjček CS. S příchodem nové periody úlohy se její zápůjčka nuluje. Vznikne-li aperiodický požadavek, PE zjistí úlohu τ s nejvyšší prioritou na množině úloh s nenulovými zápůjčkami. Tuto úlohu přeruší a začne, na její prioritní úrovni, běžet do dokončení obsluhy požadavku, nejdéle však po dobu rovnou výši její zápůjčky. Nebyla-li obsluha požadavku dokončena (tj. zápůjčka byla nedostatečná k dokončení obsluhy), proces hledání zápůjček se opakuje. Jestliže již zápůjčky neexistují, musí PE čekat na doplnění CS až do příchodu nové TS. Oproti DS tedy aperio­dické úlohy mohou v rámci TS využít procesor i na dobu delší než CS jednotek (tj. běžely-li předtím periodické úlohy ze zápůjček od PE), avšak po dobu omezenou součtem zápůjček úloh, které si čas procesoru dříve od PE zapůjčily a dosud jej PE „nevrátily“. Spolu s procesorem jsou mezi úlohami předávány (děděny) i zápůjčky.

Princip PE je ilustrován na obr. 4, kde zápůjčky úloh τ1, τ2 jsou značeny modrou, popř. zelenou barvou na pozadí části plánu těchto úloh. V čase t1 neexistuje aperiodický požadavek, a τ1 tedy začíná (do t2) běžet. Její zápůjčka (zdůrazněna modrým pozadím) je přitom zvýšena na hodnotu 1. V t3 je procesor předán, spolu se zápůjčkou o hodnotě 1, úloze τ2 (zápůjčka pro τ2 je zvýrazněna zeleným pozadím), která s touto zápůjčkou běží až do t4, kdy si půjčuje od PE další jednotku času, a výše její zápůjčky tak vzrůstá na hodnotu 2. V t5 přichází τ1; díky absenci aperiodického požadavku si tedy τ1 od PE zapůjčuje 1 jednotku času na procesoru. V t6 však přichází aperiodický požadavek a PE si od τ1 vybírá zápůjčku o velikosti 1, v rámci níž je (na úkor τ1) obsloužena, na prioritní úrovni τ1, první polovina aperio­dického požadavku. Na provedení jeho druhé části si PE v t7, na prioritní úrovni τ2, vybírá zápůjčku od τ2. Jelikož však P2 < P1, je nejprve v době od t7 do t8 dokončena τ1 a až poté, v době od t8 do t9, i aperiodická úloha. Následně může být dokončena i τ2, a to s další zápůjčkou od PE, kterou si PE vybírá v t10. V t11 jsou zápůjčky τ2 nulovány.

Sporadický server (SS)

Z principu DS a PE vychází i tzv. sporadický server (Sporadic Server – SS). Na rozdíl od DS a PE však SS svoji kapacitu neobnovuje na začátku TS vždy, ale pouze tehdy, byla-li předtím konzumována aperio­dickými úlohami. K popisu činnosti SS je třeba zavést tyto symboly, a pojmy:

  • Pexe pro prioritu běžící úlohy,
  • PS pro prioritu SS,
  • aktivní SS, označující predikát pravdivý, platí-li PS > Pexe (tj. SS přerušil úlohu s nižší prioritou),
  • tA pro čas, ve kterém se SS stane aktivním,
  • nečinný SS, označující predikát pravdivý, platí-li PS £ Pexe (tj. procesor je vrácen úloze s nižší prioritou),
  • tI pro čas, ve kterém se SS stane neaktivním,
  • RT pro čas, ve kterém má být doplněna (replenishment) kapacita SS,
  • RA pro hodnotu, o kterou se má navýšit kapacita SS.
Pravidla pro doplňování kapacity SS jsou takováto:
  • je-li CS > 0, je v tA nastavena hodnota RT na tA+TS,
  • byla-li od tA konzumována kapacita o velikosti K, je v tI nastavena hodnota RA na K.

Ilustrační příklad k SS je na obr. 5, kde v signálu aktivní SS jsou zeleně vyznačeny oblasti aktivity SS. Poprvé je SS aktivní při konzumaci CS v intervalu mezi t1t2, během něhož jsou spotřebovány dvě jednotky CS (tedy poprvé se CS doplňuje v čase RT= t1 + TS = t5 a je navýšena o hodnotu RA = 2 na cílovou hodnotu 3). Podruhé je SS aktivní při konzumaci CS v intervalu mezi t3t4, během něhož jsou spotřebovány dvě jednotky CS (tedy podruhé se CS doplňuje v čase RT = t3 + TS = t6 a je navýšena o hodnotu RA = 2 na cílovou hodnotu 5, tj. maximální hodnotu CS). Při použití SS lze zřejmě dosáhnout přijatelné reaktivity aperiodických úloh a zamezit přitom přetížení procesoru v důsledku jejich nadměrného počtu. Dále také rozložení časů RT a hodnot RA přímo závisí na tom, jak aperiodické podněty přicházely v minulosti.

Shrnutí

V článku byly představeny základní mechanismy plánování aperiodických úloh spolu s mechanismy společného plánování aperiodických a periodických úloh RT. Při jejich popisu však nebyla probírána např. problematika použití kombinace různých typů serverů či po­užití více než jednoho serveru daného typu. Je třeba také zmínit, že vedle mechanismů popsaných v článku – jejichž výčet jistě nebyl vyčerpávající a úplný – existuje ještě mnoho dalších, např. (v původním jazyce) Total Bandwidth Server, Constant Bandwidth Server či Slack Stealing [2].

Nicméně lze konstatovat, že neexistuje mechanismus, který by byl schopen garantovat dodržení časových mezí všech periodických i aperiodických úloh. Aby byl, musel by mít dopřednou (a priori) informaci o časech příchodů aperiodických podnětů, což je však v přímém rozporu s definicí aperiodických podnětů i úloh [1].

Dokladem důležitosti mechanismů popsaných v článku je, že některé z nich (např. sporadický server) jsou standardní součástí rozhraní služeb operačního systému (jmenujme např. sporadické plánování v QNX Neutrino) či rozšíření obecně používaných norem, mezi které patří např. POSIX 1003.1d pro oblast RT.

Následující díl seriálu bude zaměřen na přehled mechanismů plánování konstruovaných pro situace přetížení systému, tj. schopných zajistit předvídatelné chování systému i tehdy, není-li k dispozici dostatek výpočetního výkonu.

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] BUTAZZO, G. C.: Hard Real-Time Computing Systems, Predictable Scheduling Algorithms And Applications. Kluwer, 1997, pp. 109–178, ISBN 0-7923-9994-3.

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

[3] ČIŽINSKÝ, V.: Implementace pokročilých mechanismů plánování množin RT úloh běžících pod uC/OS-II. Diplomová práce, FIT VUT v Brně, 2010.

[4] QNX Realtime Operating System [on-line]. Dostupné z <www.qnx.com>.

[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.: Plánování úloh v systémech RT – I: závislé úlohy. Automa, 2012, roč. 18, č. 10, s. 42–45, 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 plánování v pozadí (BS)

Obr. 2. Ilustrace k vyzývacímu serveru (PS)

Obr. 3. Ilustrace k odkládacímu serveru (DS)

Obr. 4. Ilustrace k serveru s výměnou priorit (PE)

Obr. 5. Ilustrace ke sporadickému serveru (SS)