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í
.
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:
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 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 .
Literatura
- HANZÁLEK, Zdeněk. Kombinatorická optimalice - slides k přednáškám.