CKTIS / C
Scheduling round-robin
Lo scheduling round-robin assegna a turno tempo di CPU ai job pronti, per non più di un quanto ciascuno. L’esempio in C simula questa politica e calcola il tempo di attesa e il tempo di turnaround secondo una regola esplicita per l’ordine di arrivo.
Versione: C23; repository compiler flag, production runtime not attested
Sintassi
slice = min(remaining, quantum); turnaround = completion - arrival; waiting = turnaround - burstLo scheduling round-robin (RR) serve una coda di job pronti. Il job in testa viene eseguito per un massimo di un quantum, cioè un intervallo di tempo positivo. Se è ancora pronto e non ha terminato, passa in fondo alla coda; i job completati escono, mentre quelli bloccati attendono fuori dalla coda dei pronti. Un quantum più breve favorisce la reattività, ma aumenta il costo dei cambi di contesto; in generale RR non minimizza il tempo medio di turnaround.
L’ordine di arrivo richiede una regola esplicita: aggiungere i nuovi job in fondo alla coda e risolvere gli eventuali pareggi in modo deterministico. Un arrivo durante un quantum non interrompe di per sé l’intervallo. Ai confini del quantum occorre specificare se elaborare prima i nuovi arrivi o il reinserimento del job corrente. Qui tutti i job arrivano al tempo 0, nell’ordine P1, P2, P3; scorrere ciclicamente l’array è sufficiente solo per questa semplificazione.
Il tempo di turnaround è completion - arrival. Il tempo di attesa somma il tempo trascorso nella coda dei pronti, non solo l’attesa prima della prima esecuzione. Nel modello ipotizzato, senza I/O né overhead, equivale a turnaround - burst. L’esempio usa quantum = 2 e fabbisogni CPU 5, 3, 1; i tempi di completamento sono rispettivamente 9, 8, 5.
Questa è una simulazione deterministica di una singola CPU in unità di tempo astratte, non una configurazione dello scheduler di un sistema operativo né una prova del comportamento dei thread C. Ambito della versione: C23; repository compiler flag, production runtime not attested. L’esecuzione in ambiente di produzione non è attestata.
Esempi
#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;
}
Risultato
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
Il codice mostrato e il risultato dichiarato sono stati verificati in un ambiente isolato con il metodo registrato nella prova di verifica di questa versione esatta.