Úrovňový algoritmus

Úrovňový algoritmus slouží k sestavení rozvrhu pro 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 ):

$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í

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 , 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 (ú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 úkolů na zdrojů, tak se časy nutné pro vykonání jednotlivých úkolů znásobí koeficientem . 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

Nyní provedeme samotné rozvrhování.

Čas	Zdroj 1	Zdroj 2	T₁	T₂	T₃	T₄	T₅	T₆	T₇	T₈	T₉	T₁₀	T₁₁	T₁₂	T₁₃
0	T₃	T₂	3/12	2/18	4/21	1/9	5/16	6/17	2/6	4/8	3/11	5/8	4/4	3/3	3/3
2	T₃	T₁	3/12		2/19	1/9	5/16	6/17	2/6	4/8	3/11	5/8	4/4	3/3	3/3
4	T₆	T₅	1/10			1/9	5/16	6/17	2/6	4/8	3/11	5/8	4/4	3/3	3/3
9	T₆	T₁	1/10			1/9		1/12	2/6	4/8	3/11	5/8	4/4	3/3	3/3
10	T₉	T₄				1/9			2/6	4/8	3/11	5/8	4/4	3/3	3/3
11	T₉	T₁₀							2/6	4/8	2/10	5/8	4/4	3/3	3/3
13	T₈	T₇, T₁₀							2/6	4/8		3/6	4/4	3/3	3/3
17	T₁₀	T₁₁										1/4	4/4	3/3	3/3
18	T₁₁, T₁₂, T₁₃												3/3	3/3	3/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.