Trois caisses, trois façons de servir
Un algorithme d’ordonnancement est une règle qui décide quel processus passe en premier sur le processeur. Changer la règle change le temps que chaque processus attend.
Prenez trois clients à une caisse : un achat de trois minutes, un de six, un de trois. L’ordre de passage change l’attente moyenne.
À la fin de cette leçon
Remarque
Je peux comparer trois algorithmes d’ordonnancement par leur temps d’attente moyen.
Mots-clés
| Mot | Ce que ça veut dire | Exemple |
|---|---|---|
| Durée d’exécution | le temps de calcul dont le processus a besoin | 6 |
| Temps d’attente | le temps passé dans la file des prêts | |
| Temps de rotation | le temps entre l’arrivée et la fin | |
| Premier arrivé, premier servi | on exécute dans l’ordre d’arrivée | |
| Plus court d’abord | on exécute en premier la plus petite durée | |
| Famine | un processus qui n’obtient jamais le cœur |
Les cellules que les étudiants remplissent restent vides dans cet aperçu.
Deux mesures jugent un algorithme
Le temps d’attente d’un processus est le temps qu’il passe prêt, sans cœur. Le temps de rotation va de son arrivée à sa fin. Il vaut l’attente plus la durée d’exécution.
Ici, tous les processus arrivent à l’instant 0 et on calcule la moyenne. Plus la moyenne est basse, plus le système paraît vif.
Deux règles : l’ordre d’arrivée ou le plus court
Avec premier arrivé, premier servi, on exécute chaque processus jusqu’au bout, dans l’ordre de la liste. C’est simple, mais un long processus fait attendre tous les autres.
Avec plus court d’abord, on exécute en premier la plus petite durée. L’attente moyenne est la plus basse possible, mais il faut connaître les durées à l’avance.
Exemple travaillé : durées 3, 6 et 3
| Règle | Ordre | Attentes | Moyenne |
|---|---|---|---|
| Premier arrivé, premier servi | P1, P2, P3 | 0, 3, 9 | 4 |
| Plus court d’abord | P1, P3, P2 | 0, 3, 6 (P1, P3, P2) | 3 |
| Tourniquet, quantum 2 | P1, P2, P3, P1, P2, P3, P2 | 4, 6, 7 | 17 sur 3 |
Les cellules que les étudiants remplissent restent vides dans cet aperçu.
Attente moyenne dans l’ordre d’arrivée
python3 -c "print(sum([0, 3, 9]) / 3)"Affichée ici, non exécutée. Créez un compte gratuit pour appuyer sur Exécuter et la saisir dans le terminal de votre propre labo.
Attente moyenne en plus court d’abord
python3 -c "print(sum([0, 3, 6]) / 3)"Affichée ici, non exécutée. Créez un compte gratuit pour appuyer sur Exécuter et la saisir dans le terminal de votre propre labo.
D’où viennent les nombres dans ces commandes
Les listes viennent de la table. Les attentes 0, 3 et 9 sont celles de l’ordre 3, 6, 3. Les attentes 0, 3 et 6 sont celles de l’ordre 3, 3, 6.
La division par 3 donne la moyenne : Python affiche 4.0, puis 3.0. Le même travail de la machine coûte un tiers de moins en attente.
Calculer une attente moyenne
durees = [3, 6, 3]
# Remplacez par [3, 3, 6] pour voir l’autre ordre
attente = 0
total = 0
for duree in durees:
total = total + attente
attente = attente + duree
print(total / len(durees))
Le tourniquet est plus juste, plus lent
Le tourniquet donne un peu de temps à chacun. Aucun processus ne reste longtemps sans cœur, donc la famine est impossible.
Dans l’exemple, la somme des attentes monte à 17 contre 9. Vous payez l’équité par une moyenne plus haute et des commutations.
Erreur fréquente
Attention
Beaucoup de gens pensent que « plus court d’abord » est toujours le meilleur choix, puisque sa moyenne est la plus basse. Les longs processus peuvent attendre sans fin si des courts arrivent sans cesse. Un système réel ne connaît pas non plus les durées à l’avance.