CKTIS / C
Raspoređivanje round-robin
Raspoređivanje round-robin dodjeljuje procesorsko vrijeme spremnim poslovima naizmjence, svakome najviše jedan vremenski kvant. Primjer u C-u simulira tu politiku i računa vrijeme čekanja i vrijeme obrta prema izričito utvrđenom redoslijedu dolazaka.
Verzija: C23; repository compiler flag, production runtime not attested
Sintaksa
slice = min(remaining, quantum); turnaround = completion - arrival; waiting = turnaround - burstRaspoređivanje round-robin (RR) obrađuje red spremnih poslova. Posao na početku reda izvršava se najviše jedan quantum, odnosno pozitivno vremensko razdoblje. Ako je i dalje spreman i nije dovršen, premješta se na kraj reda; dovršeni poslovi izlaze, a blokirani čekaju izvan reda spremnih. Kraći quantum poboljšava odziv, ali povećava trošak promjena konteksta; RR općenito ne minimizira prosječno vrijeme obrta.
Redoslijed dolazaka zahtijeva izričito pravilo: nove poslove dodati na kraj reda, a izjednačenja razriješiti deterministički. Dolazak tijekom quantuma sam po sebi ne prekida taj interval. Na granicama quantuma treba odrediti obrađuju li se prvo novi dolasci ili ponovno umetanje trenutačnog posla. Ovdje svi poslovi dolaze u trenutku 0, redom P1, P2, P3; kružni prolazak kroz polje dovoljan je samo za ovo pojednostavljenje.
Vrijeme obrta je completion - arrival. Vrijeme čekanja obuhvaća ukupno vrijeme provedeno u redu spremnih poslova, a ne samo čekanje prije prvog izvršavanja. U pretpostavljenom modelu bez I/O-a i dodatnih troškova jednako je turnaround - burst. Primjer koristi quantum = 2 i CPU zahtjeve 5, 3, 1; vremena dovršetka su redom 9, 8, 5.
Ovo je deterministička simulacija jednog procesora u apstraktnim vremenskim jedinicama, a ne konfiguracija raspoređivača operacijskog sustava niti dokaz ponašanja C niti. Opseg verzije: C23; repository compiler flag, production runtime not attested. Izvršavanje u produkcijskom okruženju nije potvrđeno.
Primjeri
#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;
}
Rezultat
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
Prikazani kôd i navedeni rezultat provjereni su u izoliranom okruženju metodom zabilježenom u dokazu provjere za ovu točnu verziju.