4. Quatre politiques et leurs exemples complets

4.1. FCFS : premier arrivé, premier servi

First-Come, First-Served utilise une file unique et son ordre d’arrivée. Il est non préemptif : une arrivée courte ne chasse pas la tâche exécutée. La tâche continue jusqu’à sa fin ou son blocage; lorsqu’elle se débloque, elle revient à la fin de la file.

Les besoins sont P1=24, P2=3, P3=3. Le premier scénario fait arriver P1 à 0, P2 à 0,0001 et P3 à 0,0002 pour établir cet ordre. Les valeurs du tableau pédagogique négligent ensuite les epsilon :

0                         24    27    30
|           P1             | P2  | P3  |

P1 occupe le CPU jusqu’à 24. P2 et P3 restent en file; P2 finit à 27, P3 à 30. Aucun ne préempte P1.

Si les epsilon sont conservés, W2=23,9999 et W3=26,9998; les moyennes deviennent 26,9999 pour T et 16,9999 pour W. Le cours arrondit ces écarts, mais la méthode générale reste F−A puis T−B.

Pour les mêmes besoins, si l’ordre d’arrivée devient P2, P3, P1 avec des arrivées prises au début du scénario :

0    3    6                              30
| P2 | P3 |              P1               |

Le travail CPU total reste 30, mais davantage de tâches finissent rapidement. Les moyennes passent 27→13 et 17→3 : la qualité de service dépend fortement de l’ordre sans dépendre d’un changement du volume de calcul.

FCFS est simple, limite les commutations pendant une rafale et évite les dépassements indéfinis dans une file FIFO si les tâches précédentes finissent ou se bloquent. Une tâche qui ne libère jamais le CPU invalide cette progression. Une longue tâche en tête retarde les courtes et pénalise l’interactivité; une tâche E/S peut être défavorisée à chaque retour en queue, ce qui retarde aussi ses opérations périphériques. Le traitement de texte du support illustre cette réponse lente.

4.2. SJF : plus court travail disponible, sans préemption

Shortest Job First choisit la durée CPU la plus courte parmi les candidats prêts. Certaines diapositives écrivent SJB; le mécanisme est SJF. Ici, la politique est non préemptive : une tâche lancée garde le CPU jusqu’à la fin ou au blocage, même si un travail plus court arrive.

La méthode suppose une durée connue. Une application nouvelle ne fournit pas nécessairement ce renseignement; une durée peut parfois être estimée à partir d’un comportement récurrent. Estimer n’est pas connaître exactement B.

Premier scénario : A=0 pour P1/P2/P3/P4 et B=(6,8, 7,3). À 0, choisir P4; à 3, P1; à 9, P3; à 16, P2 :

0    3          9             16                24
| P4 |    P1    |     P3       |       P2        |

L’optimalité de l’attente moyenne concerne ces hypothèses : durées connues, arrivées simultanées, demandes CPU du modèle. Pour comprendre la règle, considérer deux tâches de durées x>y adjacentes. Avec x avant y, la courte attend x; les inverser remplace cette contribution par y, tandis que les suivantes commencent au même instant puisque x+y ne change pas. Répéter ces échanges conduit à l’ordre croissant et réduit l’attente totale. Cette bonne moyenne ne garantit pas une bonne attente à chacun : P2 attend 16.

Deuxième scénario : mêmes B, mais P4 arrive à 3. À 0, P1/P2/P3 sont prêts, donc P1 est choisi. L’arrivée de P4 ne l’interrompt pas. À 6 seulement, choisir P4, puis P3 et P2 :

0          6    9             16                24
|    P1    | P4 |     P3       |       P2        |
     P4 arrive à3; P1 continue

Les moyennes restent ici 13 et 7 malgré la chronologie différente. Pour P4, finir à 9 signifie un traitement 9−3=6 et une attente 6−3=3. Dans le premier scénario, P1 reçoit six unités de 3 à 9; finir à 9 ne lui donne pas neuf unités CPU, et P3 commence bien à 9, pas à 12. Ces questions du cours rappellent de distinguer durée et instant.

Les longues tâches sont défavorisées. Dans une charge dynamique où de courtes tâches continuent d’arriver avant les décisions, une longue tâche peut subir la famine. La règle optimale d’un ensemble simultané ne se transforme donc pas en garantie universelle.

4.3. SRT : comparer les restes et préempter

Shortest Remaining Time, ou SRTF, est la variante préemptive du travail le plus court. À une arrivée, comparer la durée de la nouvelle tâche au reste actuel du courant. Si elle est strictement plus courte, elle préempte; après une fin, choisir le plus petit reste parmi les prêts. Pour des égalités absentes de cet exemple, suivre l’énoncé.

Les décisions successives sont :

1. 0–1 : P1 est seul et utilise 1; il lui reste 7.
2. À 1 : P2 arrive avec 4<7 et préempte P1.
3. À 2 : P3 arrive avec 9, mais P2 n’a plus que 3; poursuivre P2.
4. À 3 : P4 arrive avec 5, mais P2 n’a plus que 2; poursuivre P2.
5. À 5 : P2 finit. Restes : P1=7, P3=9, P4=5; sélectionner P4.
6. 5–10 : P4 termine; P1 est ensuite le plus court.
7. 10–17 : P1 termine ses 7 unités restantes.
8. 17–26 : P3 reçoit ses 9 unités et termine.

0  1       5          10             17                  26
|P1|   P2  |    P4    |      P1      |         P3         |

P1 répond initialement à 0, mais attend de 1 à 10 : R1=0 ne signifie pas W1=0. P2 commence à son arrivée et n’attend pas. P3 attend 2→17, soit 15; P4 attend 3→5, soit 2. Le total CPU est 26 et la fin globale aussi, conformément au modèle sans coûts ni temps mort.

Le reste de P2 à 2 est 3, non son B initial 4. La reprise de P1 finit à 17; une ancienne graduation 20 dans une figure intermédiaire ne doit pas remplacer cette fin. P3 nécessite 9, même si la reconnaissance automatique déforme un chiffre en 3. Comme SJF, SRT peut affamer une longue tâche si de courtes tâches continuent d’être préférées.

4.4. Round Robin : faire tourner une file avec un quantum

RR prend la tête de file pour au plus q unités CPU. Si elle reste prête et inachevée à l’expiration, elle est préemptée puis replacée à la fin. Si elle termine ou se bloque avant q, le CPU passe immédiatement à un autre candidat. Une tâche terminée ne retourne pas en file.

P1=20, P2=3, P3=7, toutes arrivéesà 0 dans cet ordre, avec q=4 :

0    4   7    11   15  18   22   26   30
| P1 |P2 | P3 | P1 |P3 | P1 | P1 | P1 |

P2 ne gaspille pas une quatrième unité : P3 commence à 7, pas à 8. P3 reçoit 4+3=7. P1 reçoit cinq passages de 4=20. Ses trois derniers passages sont adjacents parce qu’il n’y a plus de concurrent prêt; la frontière de quantum ne force pas à choisir une tâche inexistante.

Les attentes se retrouvent directement : P1 attend 4→11 puis 15→18, soit 7+3=10; P2 attend 0→4; P3 attend 0→7 puis 11→15, soit 7+4=11. La question du cours sur P2 est ainsi résolue : CPU3, traitement 7, attente 4. P1 obtient une première réponse à 0 malgré son achèvementà 30 et son attente cumulée 10.

4.5. Quantum, comparaison et contrôles

Un petit quantum donne fréquemment leur tour aux autres tâches et améliore la réponse et l’impression de simultanéité. Il augmente la gestion et les commutations, donc réduit potentiellement le travail utile. Un grand quantum favorise le débit, mais laisse les autres attendre. Pour de simples demandes CPU dont chaque B<q, RR produit l’ordre FCFS. Le support illustre petit/intermédiaire/grand avec 1 ms, 20–50 ms et 500 ms, sans fixer un optimum indépendant de la charge.

Ne comparer les moyennes de deux politiques que pour une même charge et les mêmes hypothèses. Les exemples SJF, SRT et RR ci-dessus ont des données différentes : leurs chiffres illustrent chacun un calcul, sans établir un classement général entre algorithmes. Les contrôles CPU/fin globale donnent 30 pour FCFS, 24 pour SJF, 26 pour SRT et 30 pour RR. Pour un autre scénario, intégrer les temps morts et les coûts explicitement demandés.