Plánovanie úloh v distribuovaných systémoch

Každý procesor má svoje vlastné lokálne plánovanie. Obvykle tento prístup funguje. Avšak, keď skupina procesov beží na rôznych procesoroch, nezávislé plánovanie nie je vždy najefektívnejší spôsob.

Obrázok 1: Úlohy bežiace na fázy.


Základný problém môže byť ukázaný na príklade (obr. 1), kde sú procesy A a B spustené na jednom procesore a procesy C a D na inom. Každý procesor má časovú jednotku 100 milisekúnd, kde A a C bežia v párnych riadkoch, a B a D bežia v nepárnych. Predpokladajme, že A urobí viacero vzdialených volaní procedúr alebo pošle veľa správ procesu D. Počas časového intervalu 0 začne proces A a hneď zavolá proces D, ktorý nie je spustený pretože je na rade proces C. Po 100 milisekúnd, sa prepnú procesy a D dostane správy od procesu A, vykoná úlohy a rýchlo odpovie. Pretože teraz beží proces B, bude trvať ďalších 100 milisekúnd kým A dostane odpovede a môže pokračovať. Výsledkom je jedna výmena správ každých 200 milisekúnd. Je potrebné zabezpečiť, aby procesy, ktoré spolu často komunikujú bežali zároveň.
Riešeným tohto problému je gangové plánovanie (angl. gang scheduling). Gangové plánovanie má tri časti:
  1. Skupiny súvisiacich procesov sú naplánované ako celok, gang.
  2. Všetci členovia gangu bežia naraz, na rôznych CPU.
  3. Všetci členovia gangu sa spustia a skončia v rovnakom čase.
Príklad toho ako gangové plánovanie funguje je na obrázku 2. Nachádza sa tam multiprocesor so štyrmi procesormi, ktoré sú využívané skupinami (gangmi), A až D Počas časovej jednotky 0, je naplánovaná a skupina A. Počas časovej jednotky 1, je naplánovaná skupina B. Počas časovej jednotky 2, je naplánovaná skupina C. Posledná skupina D beží v časovej jednotke 3. Potom sa cyklus opakuje, údaje v časovej jednotke 4 sú rovnaké ako tie v časovej jednotke 0 a tak ďalej.

Obrázok 2: Gangové plánovanie.


Myšlienkou gangového plánovania je, aby všetky procesy, ktoré spolu komunikujú bežali naraz. Keď jeden pošle požiadavku inému, správu dostane takmer hneď, a bude schopný rýchlo odpovedať.

1Aké plánovacie algoritmy sa používajú pri DS?