Úrovňový algoritmus

Úrovňový algoritmus slouží k sestavení rozvrhu pro n preemptivních úkolů na k \\geq 2 identických zdrojích při zohlednění relace následnosti (precedence). Algoritmus je 2 - 2/k aproximační – tj. je optimální pro dva zdroje (procesory). Úrovňový algoritmus byl popsán v roce 1970 R.R. Muntzem a E.G. Coffmanem.

Princip

Sestavení grafu

Algoritmus nejprve zkonstruuje graf závislostí, v němž jsou úkoly vyjádřené pomocí uzlů a relace následností pomocí orientovaných hran (hrana vede vždy z předka do následníka). Dále algoritmus ohodnotí všechny uzly dle následujícího schématu (\\Gamma(x) značí všechny následníky uzlu x):


level(task) = \\max_{a \\in \\Gamma(task)}\\{level(a)\\} + processing\\_time(task)

Úroveň uzlu je rovna součtu úrovně nejdražšího následníka (0, pokud uzel nemá žádné následníky) a výpočetní době příslušného úkolu. Tímto způsobem dojde k postupnému ocenění úkolů od nejvíce závislých až po iniciální.

Pokud se nyní podíváme na jednotlivé úkoly, tak si všimneme, že jejich úroveň odpovídá délce nejdelší cesty skrz rozvrh – značí množství práce, které musí zdroje vykonat, než bude rozvrh splněn. Algoritmus proto při rozvrhování preferuje ty úkoly, které mají splněné všechny předky a mají nejvyšší úroveň – délka rozvrhu na nich nejvíce závisí.

Přiřazení úrovní
Přiřazení úrovní

Rozvrhování

Samotné rozvrhování probíhá v časových kvantech. Na každý zdroj je umístěn úkol s nejvyšší úrovní. Po obsazení všech zdrojů je spuštěno zpracování úkolů na zdrojích na časové kvantum T, které odpovídá času do zpracování nejkratšího z úkolů. Po vykonání tohoto kvanta je zpracovaný úkol odstraněn a u částečně zpracovaných úkolů je snížena jejich úroveň o T (úroveň se skládá také z délky úkolu a ta je nyní kratší). Na zdroje jsou znovu umístěny úkoly s nejvyšší úrovní (jejichž všichni předci již byli zpracováni), což ale nemusí být nutně ty, které byly částečně zpracovány v minulé iteraci. Algoritmus terminuje v okamžiku zpracování všech úkolů.

Speciální případy

Při přiřazování úkolů na zdroje může dojít k několika dosud nepopsaným situacím. Pokud existuje méně volných úkolů, než je zdrojů, tak tyto zdroje poběží naprázdno.

Pokud naopak existuje více úkolů se stejnou úrovní, než je počet zdrojů, tak jsou na daný zdroj přiřazeny všechny tyto úkoly a jsou vykonávány paralelně – pokud přiřadíme m úkolů na n zdrojů, tak se časy nutné pro vykonání jednotlivých úkolů znásobí koeficientem m. Po terminaci úrovňového algoritmu je nutné tyto části rozvrhu přerozvrhnout pomocí McNaughtonova algoritmu.


Příklad

Rozvrhněte za použití preempce následujích 13 úkolů T_{1}, \\cdots, T_{13} na 2 identické procesory. Doby zpracování úkolů jsou stanoveny jako P = [3,\\; 2,\\; 4,\\; 1,\\; 5,\\; 6,\\; 2,\\; 4,\\; 3,\\; 5,\\; 4,\\; 3,\\; 3], relace následnosti: Pre(T_{4}) = \\{T_{1},\\; T_{2}\\}, Pre(T_{5}) = \\{T_{2},\\; T_{3}\\}, Pre(T_{6}) = {T_{3}}, Pre(T_{7}) = \\{T_{4}\\}, Pre(T_{8}) = \\{T_{4},\\; T_{9}\\}, Pre(T_{9}) = \\{T_{5},\\; T_{6}\\}, Pre(T_{10}) = \\{T_{6}\\}, Pre(T_{11}) = \\{T_{7},\\; T_{8}\\}, Pre(T_{12}) = \\{T_{8}\\}, Pre(T_{13}) = \\{T_{9},\\; T_{10}\\}.

Řešení

Nejprve zkonstruujeme graf a přiřadíme úkolům úrovně.

Graf s přiřazenými úrovněmi
Graf s přiřazenými úrovněmi

Nyní provedeme samotné rozvrhování.

ČasZdroj 1Zdroj 2T1T2T3T4T5T6T7T8T9T10T11T12T13
0T3T23/122/184/211/95/166/172/64/83/115/84/43/33/3
2T3T13/122/191/95/166/172/64/83/115/84/43/33/3
4T6T51/101/95/166/172/64/83/115/84/43/33/3
9T6T11/101/91/122/64/83/115/84/43/33/3
10T9T41/92/64/83/115/84/43/33/3
11T9T102/64/82/105/84/43/33/3
13T8T7, T102/64/83/64/43/33/3
17T10T111/44/43/33/3
18T11, T12, T133/33/33/3
22,5

Nakonec přerozvrhneme pomocí McNaughtonova algoritmu ty části rozvrhu, ve kterých je více úkolů než zdrojů. Na druhém zdroji proto v čase \\langle 13,\\; 15) necháme vykonat úkol T_{7}, v čase \\langle 15,\\; 17) pak úkol T_{10}. Úkol T_{11} bude vykonáván na prvním zdroji v čase \\langle 18,\\; 21), úkol T_{12} bude vykonáván na prvním zdroji v čase \\langle 21,\\; 22.5) a na druhém zdroji v čase \\langle 18,\\; 19.5) a konečně úkol T_{13} bude vykonáván na druhém zdroji v čase \\langle 19.5,\\; 22.5).

Literatura

  • HANZÁLEK, Zdeněk. Kombinatorická optimalice - slides k přednáškám.







Doporučujeme