Znalostná bázaCentrum skúšok
SKSlovenčina
Vybrať jazyk13

CKTIS / C

Plánovanie round-robin

Plánovanie round-robin prideľuje pripraveným úlohám procesorový čas postupne, každej najviac na jeden časový kvant. Príklad v C túto stratégiu simuluje a počíta čas čakania a čas obratu podľa výslovne určeného poradia príchodov.

Verzia: C23; repository compiler flag, production runtime not attested

Syntax

slice = min(remaining, quantum); turnaround = completion - arrival; waiting = turnaround - burst

Plánovanie round-robin (RR) obsluhuje front pripravených úloh. Úloha na začiatku beží najviac jedno quantum, teda kladný časový úsek. Ak je stále pripravená a nie je dokončená, presunie sa na koniec frontu; dokončené úlohy front opustia a blokované čakajú mimo frontu pripravených. Kratšie quantum zlepšuje odozvu, ale zvyšuje réžiu prepínania; RR vo všeobecnosti neminimalizuje priemerný čas obratu.

Poradie príchodov vyžaduje výslovné pravidlo: nové úlohy sa pridávajú na koniec frontu a zhody sa riešia deterministicky. Príchod počas quanta sám osebe tento úsek nepreruší. Na hraniciach quanta treba určiť, či sa najprv spracujú nové príchody alebo opätovné zaradenie práve bežiacej úlohy. Tu všetky úlohy prichádzajú v čase 0 v poradí P1, P2, P3; cyklické prechádzanie poľa stačí iba pre toto zjednodušenie.

Čas obratu je completion - arrival. Čas čakania zahŕňa celkový čas strávený vo fronte pripravených úloh, nielen čakanie pred prvým spustením. V predpokladanom modeli bez I/O a réžie sa rovná turnaround - burst. Príklad používa quantum = 2 a požiadavky na CPU 5, 3, 1; časy dokončenia sú postupne 9, 8, 5.

Ide o deterministickú simuláciu jedného procesora v abstraktných časových jednotkách, nie o konfiguráciu plánovača operačného systému ani dôkaz správania vlákien C. Rozsah verzie: C23; repository compiler flag, production runtime not attested. Spustenie v produkčnom prostredí nie je potvrdené.

Príklady

#include <stdio.h>

int main(void)
{
    const int quantum = 2;
    const int burst[3] = {5, 3, 1};
    int remaining[3] = {5, 3, 1};
    int completion[3] = {0};
    int time = 0;
    int unfinished = 3;

    while (unfinished > 0) {
        for (int i = 0; i < 3; ++i) {
            if (remaining[i] == 0) {
                continue;
            }
            int slice = remaining[i] < quantum
                      ? remaining[i] : quantum;
            printf("P%d [%d,%d)\n", i + 1, time, time + slice);
            time += slice;
            remaining[i] -= slice;
            if (remaining[i] == 0) {
                completion[i] = time;
                --unfinished;
            }
        }
    }

    puts("job waiting turnaround");
    for (int i = 0; i < 3; ++i) {
        int turnaround = completion[i]; /* arrival = 0 */
        int waiting = turnaround - burst[i];
        printf("P%d %d %d\n", i + 1, waiting, turnaround);
    }
    return 0;
}

Výsledok

P1 [0,2)
P2 [2,4)
P3 [4,5)
P1 [5,7)
P2 [7,8)
P1 [8,9)
job waiting turnaround
P1 4 9
P2 5 8
P3 4 5

Zobrazený kód a uvedený výsledok boli overené v izolovanom prostredí metódou zaznamenanou v dôkaze o overení tejto presnej verzie.

Zdroje