CKTIS / C
Ordonnancement round-robin
L’ordonnancement round-robin attribue à tour de rôle du temps processeur aux tâches prêtes, pendant au plus un quantum chacune. L’exemple en C simule cette stratégie et calcule les temps d’attente et de séjour selon une règle explicite d’ordre d’arrivée.
Version : C23; repository compiler flag, production runtime not attested
Syntaxe
slice = min(remaining, quantum); turnaround = completion - arrival; waiting = turnaround - burstL’ordonnancement round-robin (RR) dessert une file de tâches prêtes. La tâche en tête s’exécute pendant au plus un quantum, c’est-à-dire une tranche de temps positive. Si elle est toujours prête et inachevée, elle passe en fin de file ; les tâches terminées en sortent, tandis que les tâches bloquées attendent hors de la file des tâches prêtes. Un quantum plus court favorise la réactivité, mais augmente le coût des changements de contexte ; RR ne minimise généralement pas le temps de séjour moyen.
L’ordre d’arrivée doit suivre une règle explicite : ajouter les nouvelles tâches en fin de file et départager les égalités de façon déterministe. Une arrivée pendant un quantum ne l’interrompt pas à elle seule. Aux limites d’un quantum, il faut préciser si les nouvelles arrivées ou la réinsertion de la tâche en cours sont traitées en premier. Ici, toutes les tâches arrivent à l’instant 0, dans l’ordre P1, P2, P3 ; parcourir le tableau en boucle ne suffit que pour cette simplification.
Le temps de séjour est completion - arrival. Le temps d’attente totalise le temps passé dans la file des tâches prêtes, et pas seulement le délai avant la première exécution. Dans le modèle supposé, sans E/S ni surcoût, il vaut turnaround - burst. L’exemple utilise quantum = 2 et des besoins CPU de 5, 3, 1 ; les temps d’achèvement sont respectivement 9, 8, 5.
Il s’agit d’une simulation déterministe d’un processeur unique en unités de temps abstraites, et non d’une configuration d’ordonnanceur de système d’exploitation ni d’une preuve du comportement des threads C. Périmètre de version : C23; repository compiler flag, production runtime not attested. L’exécution en environnement de production n’est pas attestée.
Exemples
#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;
}
Résultat
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
Le code affiché et le résultat déclaré ont été vérifiés dans un environnement isolé selon la méthode consignée dans la preuve de vérification de cette version exacte.