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 - burstRound-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.