Ú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.

{ zpětná vazba }

Tweet		Delicious
Sdílet

Hodnocení (1): 5

Přečtěte si také

McNaughtonův algoritmus

Diskuse

Pavel Mička24.1.2012

Ahoj,

já osobně jsem tohle měl v rámci předmětu "Kombinatorická optimalizace" na FEL ČVUT. Na tento předmět bohužel nejsou skripta, jsou na něj jenom slajdy + ty jsou samotné bez výkladu nepříliš použitelné (u rozvrhování je to imho hodně o stylu myšlení).

Pokud potřebuješ přesný rozvrhy (tj. ne aproximace), tak je asi nejjednodušší cestou celočíselné lineární programování, které je ale NP-Complete (ale to je i většina rozvrhovacích úloh). Jinak je třeba hledat aproximační algoritmy pro daný typ úlohy, jako je tento, McNaughtonův algoritmus, List scheduling nebo pseudopolynomiální algoritmy jako Rothkopfův algoritmus...

Haunter24.1.2012

Zdravím, jak se dá dál postupovat v rozvrhování? Je na to nějaký předmět na VŠ, že bych si našel skripta? Budeme vyvíjet ve firmě SW pro tohle, tak se to musím našrotit;-)

Pavel Mička15.6.2011

> Zis

Opraveno.

Pavel Mička14.6.2011

> Zis

Mám :-)...Tam měla být taky 1...opravím to.

Díky za upozornění.

Zis13.6.2011

Zdarec, hele nemas chybu u Přiřazení úrovní Obr. 1 u T1? T1/3/4 nemelo by to bejt T1/3/6? Pac pricitas level T2 (ten je 3) a processing time T1 (ten je taky 3).

Pavel Mička23.5.2011

asch: díky, opraveno.

asch23.5.2011

Errata: Čas = 17, T10 <- 1/4 a ne 1/5 jak je uvedeno