Znalostní bázeCentrum zkoušek
CSČeština
Vybrat jazyk13

CKTIS / C

Plánování round-robin

Plánování round-robin přiděluje připraveným úlohám procesorový čas postupně, každé nejvýše na jeden časový kvant. Příklad v C tuto strategii simuluje a počítá dobu čekání a dobu obratu podle výslovně určeného pořadí příchodů.

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

Syntaxe

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

Plánování round-robin (RR) obsluhuje frontu připravených úloh. Úloha na začátku běží nejvýše jedno quantum, tedy kladný časový úsek. Pokud je stále připravená a není dokončená, přesune se na konec fronty; dokončené úlohy frontu opustí a blokované čekají mimo frontu připravených. Kratší quantum zlepšuje odezvu, ale zvyšuje režii přepínání; RR obecně neminimalizuje průměrnou dobu obratu.

Pořadí příchodů vyžaduje výslovné pravidlo: nové úlohy se přidávají na konec fronty a shody se řeší deterministicky. Příchod během quantu sám o sobě tento úsek nepřeruší. Na hranicích quantu je třeba určit, zda se nejprve zpracují nové příchody, nebo opětovné zařazení právě běžící úlohy. Zde všechny úlohy přicházejí v čase 0 v pořadí P1, P2, P3; cyklické procházení pole stačí pouze pro toto zjednodušení.

Doba obratu je completion - arrival. Doba čekání zahrnuje celkový čas strávený ve frontě připravených, nejen čekání před prvním spuštěním. V předpokládaném modelu bez I/O a režie se rovná turnaround - burst. Příklad používá quantum = 2 a požadavky na CPU 5, 3, 1; časy dokončení jsou postupně 9, 8, 5.

Jde o deterministickou simulaci jednoho procesoru v abstraktních časových jednotkách, nikoli o konfiguraci plánovače operačního systému ani o důkaz chování vláken C. Rozsah verze: C23; repository compiler flag, production runtime not attested. Provozní spuštění není doloženo.

Pří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ýsledek

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ýsledek byly ověřeny v izolovaném prostředí metodou zaznamenanou v dokladu o ověření této přesné verze.

Zdroje