Un cap pour ce chapitre
Ce que vous saurez faire
- Distinguer exécution, attente de ressource et état prêt.
- Lire un diagramme d’ordonnancement.
- Comparer des politiques sous des hypothèses explicites.
Les bases utiles pour commencer
Partir d’un modèle précis
Un processus prêt possède tout ce qui lui manque pour avancer sauf le processeur. Un processus bloqué attend un événement, par exemple la fin d’une lecture. L’ordonnanceur choisit parmi les processus prêts. Accorder du temps de processeur à un processus bloqué ne fait pas apparaître la donnée qu’il attend. Cette distinction explique pourquoi un téléchargement peut attendre alors que d’autres applications calculent.
Pour étudier une politique, on précise les arrivées, les durées de calcul, les éventuelles entrées-sorties et le nombre de cœurs. Ici, trois processus A, B et C arrivent à l’instant zéro, dans cet ordre. Ils demandent respectivement 5, 2 et 1 unités de processeur, sans entrée-sortie. Les changements de contexte sont d’abord supposés gratuits.
Dessinez trois cases « prêt », « en exécution » et « bloqué ». Une préemption ramène le processus exécuté vers les prêts ; une demande de lecture non satisfaite le bloque ; la fin de la lecture le rend prêt. Cette représentation explique pourquoi le processeur peut traiter B pendant que A attend le disque.
Premier arrivé, premier servi
Une politique non préemptive laisse le processus choisi poursuivre jusqu’à sa fin ou jusqu’à son blocage. Avec le premier arrivé, premier servi, A occupe les instants 0 à 5, B les instants 5 à 7 et C les instants 7 à 8. C attend donc sept unités pour un calcul qui n’en exige qu’une. Le processeur reste occupé, mais la réactivité est mauvaise pour ce petit travail.
Le temps de séjour va de l’arrivée à la terminaison. Le temps d’attente dans la file des prêts correspond aux périodes pendant lesquelles le processus pourrait calculer mais ne dispose pas du cœur. Dans notre modèle sans blocage, attente = séjour moins durée de calcul. Cette égalité doit être adaptée si des périodes d’entrée-sortie apparaissent.
Tourniquet et quantum
Le tourniquet, aussi appelé round robin, donne au plus un quantum de temps à chaque processus prêt. Si le processus n’a pas terminé, il rejoint la fin de la file. Avec un quantum de deux, la séquence est A pendant deux unités, B pendant deux, C pendant une, A pendant deux, puis A pendant une. C termine à cinq au lieu de huit.
Une politique préemptive peut interrompre un processus qui pourrait continuer. Le système sauvegarde suffisamment de contexte pour le reprendre. Un quantum court favorise la réactivité mais peut multiplier ces changements ; un quantum très long rapproche le comportement du premier arrivé, premier servi. Les politiques présentées sont des modèles pédagogiques, pas une description exhaustive d’un système actuel.
Comparer sans déclarer un vainqueur universel
Servir d’abord les travaux courts réduit parfois l’attente moyenne, mais nécessite une estimation de leur durée. Dans un flux continu, certains travaux longs peuvent être longtemps repoussés. Le tourniquet donne régulièrement accès au processeur, sans garantir le meilleur temps moyen de terminaison. La bonne question est donc : quelle propriété veut-on favoriser ?
Pour justifier une trace, écrivez les bornes de chaque intervalle et l’état de la file après celui-ci. Vérifiez que chaque processus a reçu exactement sa durée demandée. Dans notre exemple, la somme des intervalles vaut huit, indépendamment de la politique, puisque nous ignorons les coûts de commutation et toute période d’inactivité.
Exemple suivi : des arrivées décalées
Prenons A, arrivé à 0 pour 4 unités de calcul, B, arrivé à 1 pour 2 unités, et C, arrivé à 3 pour 1 unité. En premier arrivé, premier servi, A occupe [0 ; 4[, B [4 ; 6[ puis C [6 ; 7[. L’écriture avec une borne droite exclue évite de compter deux fois l’instant du changement. Les attentes valent 0 pour A, 4 - 1 = 3 pour B et 6 - 3 = 3 pour C. Leur moyenne est 2, alors que les dates de première exécution sont 0, 4 et 6. Il faut donc soustraire chaque arrivée, et non commencer tous les compteurs à zéro.
Pour le tourniquet avec des arrivées, indiquez aussi une convention lorsque arrivée et fin de quantum coïncident : les nouveaux processus sont-ils insérés avant ou après celui qui est interrompu ? Deux traces différentes peuvent être correctes si elles suivent des conventions différentes. Avant de simuler, écrivez ces hypothèses. Sans processus prêt, on dessine un intervalle d’inactivité et on avance jusqu’à la prochaine arrivée.
| Processus | Arrivée | Calcul utile | Exécution FIFO | Attente |
|---|---|---|---|---|
| A | 0 | 4 | 0 à 4 | 0 |
| B | 1 | 2 | 4 à 6 | 3 |
| C | 3 | 1 | 6 à 7 | 3 |
Exemple suivi : comprendre le compromis du quantum
Reprenons A=5, B=2, C=1, tous arrivés à zéro. Avec un quantum de 1, les six premiers intervalles exécutent A, B, C, A, B, A ; A travaille encore entre 6 et 8. B termine à 5 et C à 3. Les attentes sont donc 3 pour A, 3 pour B et 2 pour C. Avec un quantum de 2, les terminaisons sont 8, 4 et 5 : B bénéficie de sa tranche complète, tandis que C commence plus tard. Un petit quantum ne diminue donc pas l’attente de chaque processus.
La première réponse est l’instant où le processus commence à travailler, alors que la terminaison arrive après tout son calcul. Une application interactive peut privilégier la première réponse. Le coût dépend également de ce qu’on appelle une commutation : deux tranches consécutives de A n’impliquent pas nécessairement un changement de processus. Dans un exercice chiffré, comptez exactement les événements auxquels l’énoncé attribue un coût.
À vous de faire varier les choses
Pilotez le partage du processeur
Modifiez la durée de A et la politique. B dure 2 unités, C dure 1 ; tous arrivent à zéro. Comparez les attentes et les tranches.
Lire le résultat de l’expérience initiale
8 unités de calcul, 5 tranches.
Attentes : A 3, B 2, C 4. Les arrivées sont simultanées, sans entrées-sorties ni coût de commutation.
| Début | Fin | Processus |
|---|---|---|
| 0 | 2 | A |
| 2 | 4 | B |
| 4 | 5 | C |
| 5 | 7 | A |
| 7 | 8 | A |
Le travail total est identique dans ce modèle ; l’ordre change surtout le moment où chacun obtient une réponse.
De la compréhension à l’autonomie
À vous de résoudre
Cherchez d’abord par vous-même. Vérifiez les résultats demandés, utilisez les indices si nécessaire, puis comparez votre méthode à la correction.
Lire un planning
A dure 4 unités, B dure 1, C dure 3. Tous arrivent à zéro dans cet ordre. Donnez les intervalles et les attentes avec le premier arrivé, premier servi.
Indice 1
La durée d’un intervalle est sa borne finale moins sa borne initiale.
Indice 2
Le premier processus n’attend pas ; les suivants attendent la fin de leurs prédécesseurs.
Comprendre la correction
A s’exécute de 0 à 4, B de 4 à 5 et C de 5 à 8. Les attentes sont donc 0, 4 et 5, soit une moyenne de 3 unités. La terminaison de C à 8 inclut cinq unités d’attente et trois unités de travail.
Construire le tourniquet
Reprenez A=4, B=1, C=3 avec un quantum de 2. Indiquez l’ordre des tranches et la terminaison de B.
Indice 1
Un processus terminé sort de la file.
Indice 2
Une tranche peut être plus courte que le quantum.
Comprendre la correction
Les tranches sont A de 0 à 2, B de 2 à 3, C de 3 à 5, A de 5 à 7 et C de 7 à 8. B termine à 3. Il n’occupe qu’une unité, car un quantum est une durée maximale, pas une durée minimale à consommer.
Corriger une confusion
Un élève affirme : « Un processus qui attend le disque doit recevoir un plus grand quantum pour terminer plus vite. » Expliquez le défaut du raisonnement.
Indice 1
Quelle ressource manque réellement ?
Indice 2
Le processus appartient-il à la file des prêts pendant cette attente ?
Comprendre la correction
Le processus est bloqué sur une entrée-sortie. Du temps de processeur ne remplace pas la réponse du disque. Il redeviendra prêt après l’événement attendu, puis pourra être choisi. Il faut distinguer ce blocage de l’attente dans la file des processus prêts.
Réintroduire le coût du système
Huit unités de calcul sont réparties sur cinq tranches. Chacun des quatre passages entre tranches coûte 0,1 unité. Quelle durée totale obtient-on, sans coût initial ni final ?
Indice 1
Les changements entre cinq tranches sont au nombre de quatre.
Indice 2
Séparez calcul utile et coût des transitions.
Comprendre la correction
Le coût ajouté est 4 × 0,1 = 0,4. La durée totale devient 8,4 unités. Le partage n’a pas augmenté la quantité de calcul utile ; il a ajouté du travail de gestion. Ce modèle montre pourquoi réduire le quantum indéfiniment ne constitue pas une solution universelle.
Problème : comparer deux services
A=6, B=2 et C=2 arrivent à zéro dans cet ordre. Construisez FIFO puis le tourniquet de quantum 2. Calculez les attentes individuelles et leur moyenne. Donnez un critère qui favorise chaque politique. Saisissez l’attente moyenne du tourniquet.
Indice 1
Pour le tourniquet, A revient après B et C.
Indice 2
Soustrayez les durées aux dates de terminaison.
Comprendre la correction
FIFO donne [0;6[ pour A, [6;8[ pour B, [8;10[ pour C : attentes 0, 6, 8. Le tourniquet donne A [0;2[, B [2;4[, C [4;6[, A [6;8[, A [8;10[ : attentes 4, 2, 4, soit 10/3. FIFO favorise ici la fin de A et limite les passages entre processus ; le tourniquet fait répondre B et C plus tôt. La charge totale reste dix unités.
Problème : intégrer une attente du disque
A et B arrivent à zéro. A calcule de 0 à 2, attend le disque de 2 à 5 puis doit calculer encore une unité. B demande quatre unités, sans interruption. Le choix est non préemptif ; A est choisi en premier. Tracez le processeur et les états de A. Calculez son séjour et son attente dans les prêts.
Indice 1
Pendant le blocage de A, B peut utiliser le cœur.
Indice 2
À 5, A est prêt mais B ne sera pas interrompu.
Comprendre la correction
A calcule [0;2[, B [2;6[, puis A [6;7[. A est bloqué pendant trois unités, puis prêt sans processeur pendant une unité. Son séjour est sept unités : trois de calcul, trois de blocage et une d’attente. Soustraire seulement sa durée de calcul donnerait quatre, ce qui mélange blocage et attente des prêts.
Problème : choisir pour un usage
Un service traite une longue conversion de vingt unités et, au même instant, deux requêtes d’une unité chacune. La conversion est première dans la file. Comparez FIFO et un tourniquet de quantum 1 pour les deux requêtes. Expliquez pourquoi on ne peut pas conclure sur la durée réelle sans coût de commutation.
Indice 1
Les requêtes passent après une seule unité de conversion avec le tourniquet.
Indice 2
Séparez date de réponse, durée utile et gestion du système.
Comprendre la correction
FIFO termine les requêtes à 21 et 22 ; le tourniquet les termine à 2 et 3. Les clients obtiennent donc rapidement leur résultat avec le tourniquet, tandis que la conversion termine plus tard qu’en FIFO. Les vingt-deux unités utiles sont conservées dans les deux cas. Pour estimer un temps réel, il manque le coût des commutations et d’éventuelles entrées-sorties ; la seule frise idéale ne permet pas de le mesurer.
Les erreurs qui méritent un détour
- Confondre bloqué et prêt.
- Un processus prêt attend le processeur ; un processus bloqué attend un autre événement.
- Attribuer systématiquement tout le quantum.
- Un processus qui termine avant la fin de sa tranche libère le cœur immédiatement.
La fiche à garder
L’essentiel à retenir
- Un ordonnancement dépend des arrivées, durées et hypothèses de ressources.
- La préemption permet d’interrompre puis reprendre un processus.
- Réactivité, attente moyenne et coût des changements sont des critères différents.
Cette notion au bac
Retrouvez ces idées dans un sujet complet, avec des indices, une correction expliquée et des ateliers.
Le prochain pas
Retrouver le catalogue de Terminale
Ce chapitre s’appuie sur le programme officiel de Terminale (PDF, nouvel onglet). Les explications et exercices sont proposés pour l’apprentissage.