CKTIS / C
Razvrščanje round-robin
Razvrščanje round-robin pripravljenim opravilom po vrsti dodeljuje procesorski čas, vsakemu največ en časovni kvant. Primer v C simulira to politiko ter izračuna čas čakanja in čas obrata ob izrecno določenem vrstnem redu prihodov.
Različica: C23; repository compiler flag, production runtime not attested
Sintaksa
slice = min(remaining, quantum); turnaround = completion - arrival; waiting = turnaround - burstRazvrščanje round-robin (RR) obravnava vrsto pripravljenih opravil. Opravilo na začetku se izvaja največ en quantum, to je pozitivno časovno obdobje. Če je še vedno pripravljeno in nedokončano, se premakne na konec vrste; dokončana opravila jo zapustijo, blokirana pa čakajo zunaj vrste pripravljenih. Krajši quantum izboljša odzivnost, vendar poveča režijo preklapljanja; RR na splošno ne minimizira povprečnega časa obrata.
Vrstni red prihodov zahteva izrecno pravilo: nova opravila se dodajo na konec vrste, izenačenja pa se razrešijo deterministično. Prihod med quantumom sam po sebi ne prekine tega obdobja. Na mejah quantumov je treba določiti, ali se najprej obravnavajo novi prihodi ali ponovno vstavljanje trenutnega opravila. Tukaj vsa opravila prispejo ob času 0 v vrstnem redu P1, P2, P3; kroženje po polju zadošča samo za to poenostavitev.
Čas obrata je completion - arrival. Čas čakanja zajema ves čas v vrsti pripravljenih opravil, ne le čakanja pred prvim izvajanjem. V predpostavljenem modelu brez V/I in režije je enak turnaround - burst. Primer uporablja quantum = 2 in potrebe po procesorju 5, 3, 1; časi dokončanja so po vrsti 9, 8, 5.
To je deterministična simulacija enega procesorja v abstraktnih časovnih enotah, ne konfiguracija razvrščevalnika operacijskega sistema in ne dokaz vedenja niti C. Obseg različice: C23; repository compiler flag, production runtime not attested. Izvajanje v produkcijskem okolju ni potrjeno.
Primeri
#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
Prikazana koda in navedeni rezultat sta bila preverjena v izoliranem okolju z metodo, zapisano v dokazilu o preverjanju te natančne različice.