Baza wiedzyCentrum egzaminacyjne
PLPolski
Wybierz język13

CKTIS / C

Planowanie rotacyjne (round-robin)

Planowanie rotacyjne przydziela gotowym zadaniom procesor kolejno, najwyżej na jeden kwant czasu. Przykład w C symuluje tę politykę i oblicza czas oczekiwania oraz czas realizacji przy jawnie określonej kolejności przybycia.

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

Składnia

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

Round-robin scheduling (RR) obsługuje kolejkę gotowych zadań. Zadanie z jej początku działa najwyżej przez quantum, czyli dodatni kwant czasu. Jeśli nadal jest gotowe i nie zakończyło pracy, trafia na koniec kolejki; zadanie zakończone wypada, a zablokowane czeka poza kolejką gotowych. Krótszy kwant sprzyja szybkiej reakcji, lecz zwiększa narzut przełączeń; RR nie minimalizuje ogólnie średniego czasu realizacji.

Arrival ordering, czyli kolejność przybycia, wymaga jawnej reguły: nowe zadania dodaje się na koniec kolejki, a remisy rozstrzyga deterministycznie. Przybycie podczas kwantu samo w sobie go nie przerywa. Dla zdarzeń na granicy kwantu trzeba ustalić kolejność dodawania nowych zadań i ponownego wstawiania bieżącego. W przykładzie wszystkie zadania przybywają w chwili 0, w kolejności P1, P2, P3; cykliczne przejście po tablicy wystarcza tylko dla tego uproszczenia.

Turnaround time (czas realizacji) to completion - arrival. Waiting time (czas oczekiwania) sumuje pobyt w kolejce gotowych, nie tylko oczekiwanie na pierwsze uruchomienie. Dla przyjętego modelu bez I/O i narzutu wynosi turnaround - burst. Przykład używa quantum = 2 i zapotrzebowania na CPU 5, 3, 1; czasy zakończenia to odpowiednio 9, 8, 5.

To deterministyczna symulacja jednego procesora w umownych jednostkach czasu, nie konfiguracja planisty systemowego ani dowód zachowania wątków C. Zakres wersji: C23; repository compiler flag, production runtime not attested. Nie potwierdzono wykonania w środowisku produkcyjnym.

Przykłady

#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;
}

Wynik

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

Wyświetlony kod i zadeklarowany wynik zweryfikowano w odizolowanym środowisku metodą zapisaną w dowodzie weryfikacji tej dokładnej wersji.

Źródła