CKTIS / C
Round-robinscheduling
Round-robinscheduling geeft gereedstaande taken om beurten processortijd, maximaal één tijdquantum per taak. Het C-voorbeeld simuleert dit beleid en berekent de wachttijd en doorlooptijd volgens een expliciete regel voor de aankomstvolgorde.
Versie: C23; repository compiler flag, production runtime not attested
Syntax
slice = min(remaining, quantum); turnaround = completion - arrival; waiting = turnaround - burstRound-robinscheduling (RR) bedient een wachtrij met gereedstaande taken. De taak vooraan draait maximaal één quantum, een positief tijdsinterval. Is de taak daarna nog gereed en niet klaar, dan gaat deze naar het einde van de wachtrij; voltooide taken verlaten de wachtrij en geblokkeerde taken wachten erbuiten. Een korter quantum bevordert de responsiviteit, maar verhoogt de kosten van contextwisselingen; RR minimaliseert doorgaans niet de gemiddelde doorlooptijd.
Voor de aankomstvolgorde is een expliciete regel nodig: voeg nieuwe taken achteraan toe en behandel gelijke gevallen deterministisch. Een aankomst tijdens een quantum onderbreekt dat interval niet vanzelf. Leg bij quantumgrenzen vast of nieuwe aankomsten of het opnieuw invoegen van de huidige taak als eerste worden verwerkt. Hier komen alle taken aan op tijdstip 0, in de volgorde P1, P2, P3; cyclisch door de array lopen volstaat alleen voor deze vereenvoudiging.
De doorlooptijd is completion - arrival. De wachttijd omvat de totale tijd in de wachtrij voor gereedstaande taken, niet alleen de vertraging vóór de eerste uitvoering. In het aangenomen model zonder I/O of overhead is deze gelijk aan turnaround - burst. Het voorbeeld gebruikt quantum = 2 en CPU-behoeften 5, 3, 1; de voltooiingstijden zijn respectievelijk 9, 8, 5.
Dit is een deterministische simulatie van één processor in abstracte tijdseenheden, geen configuratie van een besturingssysteemplanner en geen bewijs van het gedrag van C-threads. Versieomvang: C23; repository compiler flag, production runtime not attested. Uitvoering in een productieomgeving is niet bevestigd.
Voorbeelden
#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;
}
Resultaat
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
De getoonde code en het opgegeven resultaat zijn in een geïsoleerde omgeving geverifieerd met de methode die in het verificatiebewijs voor exact deze versie is vastgelegd.