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 - burstPlá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.