McNaughtonův algoritmus

McNaughtonův algoritmus slouží k rozvržení preemptivních úkolů na identických zdrojů při minimalizaci délky rozvrhu. Algoritmus pracuje s lineární asymptotickou složitostí O(n) .

Princip

Algoritmus nejprve vytvoří obdélníkovou matici, v níž je počet řádků roven počtu zdrojů a počet sloupců odpovídá délce rozvrhu. Délku rozvrhu můžeme vyjádřit jako:

$C^{*}_{max} = \max \{{{1} \over {R}}\; \sum^{n}_{i = 1}\; p_{i},\; \max_{i = 1, \;2, \cdots, \; n} \; p_{i} \}$

Suma v maximu značí situaci, kdy je obdélníková matice rozvrhu ideálně zarovnána (tj. každý ze zdrojů je vždy obsazen). Druhý argument pak vyjadřuje délku nejdelšího úkolu – jednotlivé úkoly jsou vnitřně sekvenční, nelze proto jeden úkol vykonávat zároveň na více zdrojích (procesorech).

Nyní, když je již známá délka rozvrhu, může algoritmus přistoupit k samotnému plánování. Algoritmus iteruje postupně přes všechny úkoly a vyplňuje matici od levého horního rohu po řádcích. První úkol umístí do levého horního rohu, druhý úkol těsně za něj a tak dále. V okamžiku, kdy se některý z úkolů již nevejde celý na jeden řádek (zdroj), tak jej algoritmus přeruší (nechá na k-tém zdroji vykonat pouze koncovou část úkolu), a jeho první část rovrhne na zdroj následující. Díky výše zmíněnému výpočtu délky rozvrhu se nikdy nemůže stát, že by byl jeden úkol zpracováván v jeden okamžik více zdrojích.

Po rozvržení posledního úkolu algoritmus terminuje. Matice odpovídá optimálnímu rozvrhu.

Příklad

Rozvrhněte následující úkoly $T = [1,\; 4,\; 4,\; 2,\; 1]$ na 3 identické zdroje s využitím preempce.

Řešení

Celková délka rozvrhu bude 4, protože suma délek úkolů je 12 a rozvrhujeme na 3 zdroje, a navíc je délka nejdelšího úkolu taktéž 4. Matice rozvrhu proto bude mít rozměr $3 \times 4$ .