23 - Ordonnancement des processus
Evaluation ✎ : -
1 - Ordonnanceur du système d'exploitation
Maintenant que nous avons vu comment nous pouvions faire patienter les processus, nous allons voir comment le système d'exploitation parvient à choisir le prochain processus à qui il va permettre d'accéder aux services du processeur.
Ordonnanceur
1 - Vocabulaire
L'ordonnanceur est la partie du noyau du système d'exploitation responsable du choix du processus élu qui va pouvoir bénéficier du service du processeur (et globalement toutes les tâches annexes qui en découlent). Cette tâche se nomme l'ordonnancement.
L'ordonnanceur est chargé notamment
- de réaliser les élections parmi les processus dont l'état est PRET,
- de réaliser d'éventuels préemptions du processus ELU (arrêt du travail pour l'élu sans que l'élu ne l'ai demandé lui-même)
- et globalement tout ce qui traite de la gestion de l'alternance des processus.
A chaque fois qu'un processus passe de ELU à PRET, il faut sauvegarder en RAM l'état des registres du processeur à ce moment (numéro PC de la prochaine instruction, valeurs dans les autres registres...).
A chaque fois qu'un processus passe de PRET à ELU, il faut remplir les registres du processeur avec les états sauvegardés en RAM.
2 - Politiques d'ordonnancement possibles
Il existe un très grand nombre de politiques possibles pour gérer l'accès au service du processeur. Certaines sont simples et solides, d'autres de vraies systèmes d'horlogerie, certaines sont généralistes et d'autres spécifiques à certains usages.
Le but de ce cours n'est pas de faire un inventaire complet des différentes politiques. Nous allons en voir 4 spécifiquement lors des activités débranchées.
Si nous devions classer ces politiques, voici quelques caractéristiques clivantes :
- Sans préemption (on ne peut pas faire sortir l'élu de son état si il ne le demande pas lui-même) ou avec préemption (on peut imposer à l'élu de quitter son état)
- Temps partagé (on tente de partager plus ou moins équitablement le CPU entre les processus) ou temps réel (il y a un mécanisme qui permet à certains processus d'être extrêmement prioritaires s'il le faut)
- Choix de la propriété maximisant la chance d'être élu :
- Durée d'attente du processus dans l'état PRET ?
- Importance de la tâche réalisée par ce processus ?
- Durée estimée du travail à réaliser avant de rendre la main ?
- ...
3 - Types de préemption
Le système d'exploitation dispose d'un mécanisme de signal permettant de détecter certains événements (réception de données depuis le clavier, le disque dur, la carte réseau...
En fonction de la politique d'ordonnancement sélectionnée, l'ordonnateur peut alors préempter le processus élu lorsqu'un événement particulier intervient et réaliser une nouvelle élection. Par exemple :
- Une interruption d'horloge : le processeur travaille depuis la bonne durée prédéfinie avec un même processus, il est temps de passer la main.
- Une interruption liée à un événement : l'utilisateur a réalisé une action, une ressource réponds à une sollicitation
- ...
Dans le cadre de cette activité, nous allons voir :
- Deux politiques temps partagé (dont une réellement implémentée dans Linux)
- une politique FIFO sans préemption ni priorité qu'on nomme ordonnancement coopératif FIFO.
- une politique FIFO avec priorité dynamique et préemption temporelle qu'on nomme OTHER dans Linux.
- Deux politiques temps réel (toutes les deux implémentées dans Linux)
- une politique FIFO sans préemption temporelle mais avec priorité qu'on nomme FIFO dans Linux.
- une politique FIFO avec préemption et priorité qu'on nomme tourniquet / round-robin dans Linux.
REMARQUE : l'ordonnanceur se dit scheduler en anglais.
2 - Temps partagé : premier arrivé, premier servi, coopératif
La première politique que nous allons voir est simple, solide mais possède bien entendu des désavantages qui ne lui permettent pas d'appartenir aux politiques validées pour Linux.
Description général d'un ordonnateur basé sur la coopération des processus : Premier Arrivé, Premier Servi
- La politique est sans préemption.
- La demande de service processeur du processus dans une file : on sélectionne celui qui est revenu à l'état PRET depuis le plus longtemps.
- Puisque cette politique est non-préemptive, le processus ELU ne change d'état que dans trois cas dépendants intégralement de ses propres instructions. Les cas possibles sont :
- ELU vers BLOQUE ; il vient de lancer un appel-système (une demande d'entrée/sortie...)
- ELU vers FIN ; il a fini ses instructions.
- ELU vers PRET volontairement ; il décide de laisser la main (appel à sched_yield()).
Nous allons voir que cela fonctionne bien si tous les processus coopèrent mais que cette stratégie est totalement incapable de gérer les processus égoïstes.
Symboles des états du processus
- le tiret - indique que le processus n'est pas encore créé ou est totalement FINI,
- un carré évidé ◻ qu'il est dans l'état PRET,
- un carré plein ■ indique que le processus est ELU et accède au processus,
- une croix x indique que le processus est BLOQUE,
Symboles sur le descriptif des actions à faire par le processus
- Le drapeau coloré ⚑ caractérise un ensemble de calculs qui prend l'intégralité d'un "temps-machine".
- ⚑ provoque donc ■
- Le drapeau blanc ⚐ signifie que le processus est gentil et va rendre la main volontairement à la fin de ce temps-machine en effectuant une transition ELU vers PRET.
- ⚐ provoque donc aussi ■ sur le temps actuel et le suivant sera
- soit ◻ s'il ne gagne pas l'élection,
- soit ■ s'il gagne à nouveau l'élection
- L'engrenage ⚙ signifie que le processus travaille sur ce temps à lancer un appel-système et passe ensuite à l'état BLOQUE le temps d'obtenir la réponse. Le temps de blocage est fourni derrière le symbole. Avec 2, il y aura donc 2 temps-machines passés à l'état BLOQUE avant de pouvoir revenir à l'état PRET.
- ⚙4 provoque donc ■xxxx.
- la tête de mort ☠ indique que le processus a totalement terminé son exécution et n'existera bientôt plus (passe à l'état FINI sans occupé le moindre temps machine ici),
- ☠ provoque donc -----------...
- le sablier ⧗ indique que le processus passe juste à l'état BLOQUE pour temps indéfini ici (il rentre en sommeil car son travail consiste maintenant à attendre un signal qui lui sera destiné lorsqu'il aura de nouveau quelque chose à faire),
- ⧗ provoque donc xxxxxxxxx...
01° Etudier les accès au processeur par les trois processus suivants. Il faut que vous puissiez retrouver les processus sélectionnés en utilisant les demandes des 3 processus de façon à obtenir la même séquence sur le processeur.
Processus R : ⚑⚑⚙6 ⚑⚑⚐ ⚑⚑⚑⚑⚐ ⚑⚑⚑⚑⚐ ⚑⚑⧗ qui commence dès le temps 1.
Processus B : ⚑⚑⚑⚙4 ⚑⚑⚙3 ⚑⚑⚑☠ qui commence dès le temps 3.
Processus V : ⚑⚑⚑⚑⚑ ⚑⚑⚑⚑⚑ ⚑⚑⧗ qui commence dès le temps 6.
Voici le déroulé qu'on obtient alors :
| t | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 0 | 1 | 2 |
| R | ■ | ■ | ■ | x | x | x | x | x | x | ◻ | ◻ | ◻ | ◻ | ◻ | ◻ | ◻ | ◻ | ◻ | ◻ | ■ | ■ | ■ | ◻ | ◻ | ◻ | ■ | ■ | ■ | ■ | ■ | ◻ | ◻ | ◻ | ■ | ■ | ■ | ■ | ■ | ■ | ■ | x | x |
| B | - | - | ◻ | ■ | ■ | ■ | ■ | x | x | x | x | ◻ | ◻ | ◻ | ◻ | ◻ | ◻ | ◻ | ◻ | ◻ | ◻ | ◻ | ■ | ■ | ■ | x | x | x | ◻ | ◻ | ■ | ■ | ■ | - | - | - | - | - | - | - | - | - |
| V | - | - | - | - | - | ◻ | ◻ | ■ | ■ | ■ | ■ | ■ | ■ | ■ | ■ | ■ | ■ | ■ | ■ | x | x | x | x | x | x | x | x | x | x | x | x | x | x | x | x | x | x | x | x | x | x | x |
| t | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 0 | 1 | 2 |
| P | ■ | ■ | ■ | ■ | ■ | ■ | ■ | ■ | ■ | ■ | ■ | ■ | ■ | ■ | ■ | ■ | ■ | ■ | ■ | ■ | ■ | ■ | ■ | ■ | ■ | ■ | ■ | ■ | ■ | ■ | ■ | ■ | ■ | ■ | ■ | ■ | ■ | ■ | ■ | ■ | ◻ | ◻ |
02° Avec ce type d'ordonnancement, que se passe-t-il si un processus (comme le vert ici) ne rend pas la main facilement ?
...CORRECTION...
Le processus garde la main. Il empêche donc les autres de travailler. Il va falloir attendre qu'il ai fini son déroulé.
03° Sur notre exemple, quel est le pourcentage d'occupation du CPU avant que le rouge ne finisse par se mettre lui aussi en sommeil à l'état BLOQUE ?
Ce type de comportement est-il courant ?
...CORRECTION...
100 %.
Non, ce n'est pas courant en utilisation classique. Mais cela évitera ici d'avoir trop de cases vides à remplir.
04° Cet ordonnancement peut-il néanmoins fonctionner correctement si tous les processus formulent régulièrement
- soit un appel système d'entrée/sortie ou
- soit une demande pour repartir d'eux-même en PRET ?
...CORRECTION...
Oui, cela en fait un Ordonnanceur facile et solide, si les processus sont sous conditions que les processus soit "civiques" ou "gentils".
05° Cet algorithme ordonnanceur est-il adapté à un environnement non-restreint où on peut importer un grand nombre de processus d'origine non contrôlée ?
...CORRECTION...
Non, il suffit d'avoir un processus très calculatoire ne demandant jamais à accéder à une ressource ou incorporant une boucle infinie et c'est fini : il gardera la main jusqu'au bout.
06° Nous avons totalement passé sous silence le temps que met le processeur pour transporter entre les données temporaires du processus entre les registres et la RAM à chaque fois que le processus quitte ou revient à l'état ELU. Cette action s'appelle la commutation de contexte.
Imaginons que cela représente un bloc de temps-machine pour sortir un processus du CPU ou pour faire entrer un processus du CPU. Le déroulement de la question 1 donnerait alors ceci :
P ■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■◻◻
Quel va être le problème si les rotations des processus sont très rapides ?
...CORRECTION...
Le CPU va perdre du temps de travail à faire des chargements de données plutôt que de vraiment travailler.
Conclusion
Une politique d'ordonnancement "Premier Arrivé - Premier Servi" (FIFO) sans préemption a donc tendance à favoriser les processus peu gentils qui gardent la main.
On trouve également d'autres stratégies d'élection comme la stratégie "Plus court travail d'abord" qui va cette fois favorisé les processus demandant le moins d'opérations d'un coup. La difficulté est alors d'estimer le temps d'utilisation du prochain accès au CPU... On agit souvent en réalisant des moyennes sur les derniers accès de ce processus. Il n'en reste pas moins que cette stratégie ne règle pas le problème du processus qui prend la main à un moment et ne la rend pas.
3 - Temps partagé : OTHER, politique à crédits
Nous allons voir comment Linux réalise son ordonnancement temps partagé pour éviter de voir un trop grand accaparement du processus par un ou plusieurs processus.
Il s'agit juste de voir le principe. Le but de cette activité n'est pas de présenter dans les détails le vrai fonctionnement. Si cela vous intéresse, il suffit d'aller voir le code source de votre version Linux.
N'utiliser donc pas cette activité autrement que comme une façon d'aborder l'ordonnancement en première approche. Pour information, les lignes d'instructions implémentant cette fonction dépasse les 5000 lignes. Il est donc hors de question de comprendre son fonctionnement en détail...
OTHER est le nom de la politique d'ordonnancement temps partagé générique présente sur les systèmes Linux. Pourquoi lui donner un nom pareil ? Simplement car aucune technique précise n'est imposée.
Principe général de la politique à crédits OTHER de Linux
Voici son principe :
- C'est une politique préemptive : l'ordonnanceur donne un temps de travail limite à chaque processus et provoque la transition ELU vers PRET lorsque le processus a utilisé tous ses crédits d'accès au CPU. Le processus peut donc se faire exclure du CPU sans l'avoir demandé lui-même. Il devra attendre qu'on lui redonne de nouveaux crédits pour agir.
- Lors de la création du processus, on lui attribue une priorité statique allant
- de 1 (pour les processus les moins prioritaires)
- à 40 (pour les processus les plus prioritaires).
- En réalité, l'ordonnanceur utilisant OTHER va travailler avec une priorité dynamique basée sur la priorité statique et un modificateur que l'ordonnanceur gère lui-même :
- Il donne un bonus dynamique aux processus qui sont passés régulièrement à BLOQUE à cause d'un appel-système. On favorise donc les processus E/S demandant peu de ressources CPU. On ne gérera pas cela en activité débranchée.
- Il donne un malus dynamique aux processus qu'il doit mettre dehors une fois que le temps alloué est atteint. On pénalise donc les processus très calculatoires. On ne gérera pas cela en activité débranchée.
- L'ordonnanceur va alors accorder à chaque processus dont l'état est PRET ou BLOQUE un certain crédit de temps-machine valable sur une période de temps qu'on nomme une époque. Sur notre activité papier, on prendra un système simple :
- Priorité dynamique de 31-40 : crédit de 8 temps-machines.
- Priorité dynamique de 21-30 : crédit de 6 temps-machines.
- Priorité dynamique de 11-20 : crédit de 4 temps-machines.
- Priorité dynamique de 01-10 : crédit de 2 temps-machines.
- Une époque se termine lorsqu'il n'y a plus de processus PRET pouvant encore agir.
- On fait le choix qu'un processus arrivant au milieu d'une époque doit attendre le début d'une nouvelle époque pour bénéficier de crédit. On pourrait faire autrement.
- Une époque se termine lorsque tous les processus à l'état PRET ont utilisé leurs crédits. Il peut donc rester des crédits non utilisés parmi les processus BLOQUE.
- Une fois qu'une époque est terminée, l'ordonnanceur recommence son attribution de temps-machine en donnant la moitié éventuellement des crédits non utilisés si le processus ne les as pas utilisé entièrement (s'il est bloqué par exemple).
- L'ordonnanceur choisit le processus de plus grande priorité ayant encore du crédit
- Il crée un mécanisme de files par niveau de priorité en cas d'égalité de priorité.
Préemption
Priorité dynamique
Epoque et temps alloué
Election
Variantes multiples : je rappelle qu'on peut gérer ceci de plein de manières différentes puisqu'il n'existe pas de OTHER "officiel".
Un processus n"obtient de crédit qu'au début d'une époque. Si il arrive après la distribution, il devra attendre la fin de l'époque actuelle pour en obtenir.
07° Etudier les accès au processeur par les trois processus suivants. Il faut que vous puissiez retrouver les processus sélectionnés en utilisant les demandes des 3 processus de façon à obtenir la même séquence sur le processeur.
Processus R : ⚑⚑⚙6 ⚑⚑⚙2 ⚑⚑⚑⚑⚙2 ⚑⚑⚑⚑⚙2 ⚑⚑⧗ qui commence dès le temps 1 avec une priorité de 20 (4 crédits au début de chaque cycle).
Processus B : ⚑⚑⚑⚙4 ⚑⚑⚙3 ⚑⚑⚑⚑⚑⚑⚑⚑⚑⚑☠ qui commence dès le temps 3 avec une priorité de 40 (8 crédits au début de chaque cycle).
Processus V : ⚑⚑⚑⚑⚑ ⚑⚑⚑⚑⚑ ⚑⚑⧗ qui commence dès le temps 6 avec une priorité de 35 (4 crédits au début de chaque cycle).
Les o indiquent que le processus n'a pas/plus de crédit dans cette époque.
| t | | | 1 | 2 | 3 | | | 4 | 5 | 6 | 7 | | | 8 | 9 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 0 | 1 | | | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | | | 0 | 1 | 2 | 3 | 4 | | | 5 |
| R | |4 | ■ | ■ | ■ | |4 | x | x | x | x | |6 | x | x | ◻ | ◻ | ◻ | ◻ | ◻ | ◻ | ◻ | ◻ | ◻ | ■ | ■ | ■ | |5 | x | x | ◻ | ◻ | ◻ | ◻ | ◻ | ◻ | ◻ | ◻ | ◻ | ◻ | ◻ | ◻ | ■ | ■ | ■ | ■ | |4 | ■ | x | x | ■ | ■ | |4 | x |
| B | |0 | - | - | o | |8 | ■ | ■ | ■ | ■ | |10 | x | x | x | x | ◻ | ◻ | ◻ | ◻ | ■ | ■ | ■ | x | x | x | |13 | ■ | ■ | ■ | ■ | ■ | ■ | ■ | ■ | ■ | ■ | - | - | - | - | - | - | - | - | | | - | - | - | - | - | | | - |
| V | |0 | - | - | - | |0 | - | - | o | o | |8 | ■ | ■ | ■ | ■ | ■ | ■ | ■ | ■ | o | o | o | o | o | o | |8 | ◻ | ◻ | ◻ | ◻ | ◻ | ◻ | ◻ | ◻ | ◻ | ◻ | ■ | ■ | ■ | ■ | x | x | x | x | |10 | x | x | x | x | x | |13 | x |
| t | | | 1 | 2 | 3 | | | 4 | 5 | 6 | 7 | | | 8 | 9 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 0 | 1 | | | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | | | 0 | 1 | 2 | 3 | 4 | | | 5 |
| P | | | ■ | ■ | ■ | | | ■ | ■ | ■ | ■ | | | ■ | ■ | ■ | ■ | ■ | ■ | ■ | ■ | ■ | ■ | ■ | ■ | ■ | ■ | | | ■ | ■ | ■ | ■ | ■ | ■ | ■ | ■ | ■ | ■ | ■ | ■ | ■ | ■ | ■ | ■ | ■ | ■ | | | ■ | ◻ | ◻ | ■ | ■ | | | ◻ |
08° Pourquoi un processus possédant une boucle infinie ne peut plus parvenir à trop perturber le système avec la politique d'ordonnancement OTHER ?
...CORRECTION...
Le processus va utiliser régulièrement tout son crédit puis va subir une préemption.
09° Dans la "vraie" politique OTHER, les processus utilisant l'intégralité de leur crédit machine subissent une pénalité comme nous l'avions précisé dans le principe de OTHER. Que va-t-il se passer pour un processus très gourmand en ressource CPU ?
...CORRECTION...
La priorité du processus va baisser progressivement jusqu'à atteindre un très bas niveau. Il pourra donc continuer à travailler mais après les autres processus présents dans l'époque.
10° Expliquer alors pourquoi OTHER ne permet pas de réaliser un ordonnancement temps réel. Dans un tel ordonnancement temps réel, un processus très prioritaire (comme le déclencheur d'AirBag par exemple) doit accéder très rapidement au CPU dès qu'il reçoit un signal d'action à réaliser.
...CORRECTION...
Montrer que quelque chose est vraie est compliqué. Pour montrer qu'une chose est fausse, il suffit de trouver un exemple. Et nous en avons deux :
- prenons un processus très important mais très calculatoire. Nous avons vu sur la question précédente que sa priorité allait chuter. Il passera donc après les autres. Son temps de réaction ne peut donc pas être garantit puisqu'il devra attendre systématiquement que les autres processus aient épuisé leurs crédits CPU.
- deuxième exemple : sur l'exercice 7 au temps 8, on voit que le processus Vert prend la main alors que le processus Bleu est bloqué. Le Bleu ne pourra reprendre la main qu'après un temps assez long puisque le processus Vert possède pas mal de crédit à cause de sa propre priorité, moins forte que celle de Bleu mais forte néanmoins.
Dans les deux cas, le processus prioritaire devant reprendre rapidement la main va devoir attendre...
11° Partir sur une console Linux (par exemple celui des postes Linux de votre lycée, ou celui de l'ENT si vous êtes dans les HdF).
Les en-têtes PRI NI POL caractérisent la priorité du processus, sa valeur de NIce (sa gentillesse) et sa politique d'ordonnancement (voir le manuel Linux pour la signification du terme TS).
Question
Visiblement, quelle est la priorité par défaut, la gentillesse par défaut et la politique d'ordonnancement par défaut ?
rv@rv-HP2:~$ man ps
policy POL Classe d’ordonnancement du processus (alias
class, cls). Les valeurs possibles sont :
- non signalé
TS SCHED_OTHER
FF SCHED_FIFO
RR SCHED_RR
B SCHED_BATCH
ISO SCHED_ISO
IDL SCHED_IDLE
DLN SCHED_DEADLINE
? valeur inconnue
~$ ps -ef -o "user pid ppid stat priority nice policy"
USER PID PPID STAT PRI NI POL
rv 78971 18170 Ss 20 0 TS
rv 79009 78971 R+ 20 0 TS
rv 78888 18170 Ss 20 0 TS
rv 78900 78888 S+ 20 0 TS
rv 78913 78900 S+ 20 0 TS
rv 18188 18170 Ss 20 0 TS
rv 18201 18188 S+ 20 0 TS
rv 18203 18201 Sl+ 20 0 TS
rv 1604 1228 Ssl+ 20 0 TS
rv 1613 1604 Sl+ 20 0 TS
Remarque : SCHED car en anglais ordonnanceur se dit scheduler.
Il y a encore beaucoup de choses à dire si on le veut sur la politique OTHER de Linux mais nous venons de voir ses limites : impossibilité de garantir une politique "temps réel" pour un processus prioritaire.
Hors-programme
Pour gérer un peu plus finement la gestion des processus, sachez qu'on peut modifier la gentillesse des processus via leur programme.
- Dans un programme, on peut rajouter des instructions permettant au processus engendré par ce programme de modifier sa priorité en utilisant l'appel-système nommé nice() en lui fournissant un modificateur de "gentillesse".
- Avec des droits normaux, on ne peut que rendre le processus plus gentil en diminuant sa priorité (on peut faire des appels de nice(0) à nice(20)). Avec une priorité basique de 20 et un usage de nice(5), la priorité du processus passerait donc à 15.
- Avec des droits super-user, on ne peut que rendre le processus plus égoïste en augmentant sa priorité (on peut faire des appels de nice(0) à nice(-20)). Avec une priorité basique de 20 et un usage de nice(-5), la priorité du processus passerait donc à 25.
- Ces modifications permettent au développeur de pouvoir augmenter la priorité de son programme lorsqu'il sait qu'il est en train de réaliser des tâches importantes ou au contraire des tâches qui peuvent attendre. Un même programme peut ainsi obtenir des priorités différentes en fonction de ses différentes phases de fonctionnement. Notez bien que c'est le développeur qui décide ici de l'importance de son programme. Pas le système lui-même.
- Dans un programme, on peut rajouter des instructions permettant au processus engendré par ce programme de modifier la priorité de ses descendants en utilisant l'appel-système nommé renice().
Globalement, OTHER fonctionne bien pour la gestion des processus "normaux". En effet, OTHER favorise les processus ayant une forte priorité et utilisant beaucoup d'appels-système sans pour autant bloquer totalement les processus de basse priorité même si les processus-prioritaires veulent travailler intensément.
Nous venons de voir
- en partie 2 que la politique simple FIFO temps partagé ne permet pas de gérer correctement les processus égoïstes
- en partie 3 que la politique OTHER de Linux était la politique principale mais qu'elle ne permet pas de gérer correctement le temps réel.
Voyons maintenant comment gérer le cas du "temps-réel". Cette fois, on veut laisser toute latitude d'actions aux processus très prioritaires car ils doivent faire leur travail sans délai sous peine de voir apparaître de très gros problèmes sur le système.
4 - Temps réel : FIFO
Politique FIFO de Linux : "temps réel" avec préemption de priorité
Priorité
On utilise également des priorités mais attention, elles n'ont pas le même statut que les priorités statiques et dynamiques de OTHER.
On les nomme les priorités temps réel entre 1 et 99 la plupart du temps.
Attention, la priorité temps réel de n'importe quel processus dont la politique est OTHER vaut...0. N'importe quel processus OTHER passe après un processus dont la politique est FIFO même si sa priorité temps réel n'est que de 1.
Principe
- Election : on prend le processus de plus grande priorité temps réel à l'état PRET. En cas d'égalité, on utilise une FILE et c'est donc le premier arrivé dans la file qui en sort.
- Aucune préemption temporelle : le processus ELU ne sera jamais exclu du CPU car il travaille depuis trop longtemps.
- Préemption de priorité : le processus ELU repasse à l'état PRET dès qu'un processus de plus grande priorité passe à l'état PRET. On donne donc clairement la main au processus qui a été jugé le plus critique.
C'est tout.
12° Etudier les accès au processeur par les trois processus suivants. Il faut que vous puissiez retrouver les processus sélectionnés en utilisant les demandes des 3 processus de façon à obtenir la même séquence sur le processeur.
Processus R : ⚑⚑⚙7 ⚑⚑⚙2 ⚑⚑⚑⚑⚙2 ⚑⚑⚑⚑⚙2 ⚑⚑⧗ qui commence dès le temps 1 avec une priorité temps réel de 50.
Processus B : ⚑⚑⚑⚙4 ⚑⚑⚙3 ⚑⚑⚑⚑⚑⚑⚑⚑⚑⚑☠ qui commence dès le temps 3 avec une priorité temps réel de 70.
Processus V : ⚑⚑⚑⚑⚑ ⚑⚑⚑⚑⚑ ⚑⚙20 ⚑⚑⧗ qui commence dès le temps 6 avec une priorité de 90.
| t | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 0 | 1 | 2 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 0 |
| R | ■ | ■ | ◻ | ◻ | ◻ | ◻ | ◻ | ◻ | ◻ | ◻ | ◻ | ◻ | ◻ | ◻ | ◻ | ◻ | ◻ | ◻ | ■ | x | x | x | x | x | x | x | ■ | ■ | ◻ | ◻ | ◻ | ◻ | ◻ | ◻ | ◻ | ◻ | ◻ | ◻ | ◻ | ◻ | ■ | x | x | ■ | ■ | ■ | ■ | ■ | x | x | ■ | ■ | ■ | ■ | ■ | x | x | ■ | ■ | x | x |
| B | - | - | ■ | ■ | ■ | ◻ | ◻ | ◻ | ◻ | ◻ | ◻ | ◻ | ◻ | ◻ | ◻ | ◻ | ◻ | ■ | x | x | x | x | ■ | ■ | ■ | x | x | x | ■ | ■ | ■ | ■ | ■ | ■ | ■ | ■ | ■ | ◻ | ◻ | ■ | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - |
| V | - | - | - | - | - | ■ | ■ | ■ | ■ | ■ | ■ | ■ | ■ | ■ | ■ | ■ | ■ | x | x | x | x | x | x | x | x | x | x | x | x | x | x | x | x | x | x | x | x | ■ | ■ | x | x | x | x | x | x | x | x | x | x | x | x | x | x | x | x | x | x | x | x | x | x |
| t | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 0 | 1 | 2 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 0 |
| P | ■ | ■ | ■ | ■ | ■ | ■ | ■ | ■ | ■ | ■ | ■ | ■ | ■ | ■ | ■ | ■ | ■ | ■ | ■ | ◻ | ◻ | ◻ | ■ | ■ | ■ | ◻ | ■ | ■ | ■ | ■ | ■ | ■ | ■ | ■ | ■ | ■ | ■ | ■ | ■ | ■ | ■ | ◻ | ◻ | ■ | ■ | ■ | ■ | ■ | ◻ | ◻ | ■ | ■ | ■ | ■ | ■ | ◻ | ◻ | ■ | ■ | ◻ | ◻ |
13° Sur l'exemple précédent :
- Que se passe-t-il dès que le vert veut prendre la main ?
- Quels sont les seuls instants où les processus travaillant avec la politique OTHER peuvent faire exécuter leurs propres instructions ?
- Les processus temps réel FIFO sont-ils censés être très nombreux sur un système informatique ?
- Que se passe-t-il si un processus temps réel boucle à l'infini ?
...CORRECTION...
- Dès qu'il veut la main, il l'obtient car il est le plus prioritaire.
- Les processus sous OTHER ne pourront travailler que lorsqu'aucun processus temps réel ne voudra la main. Ca peut être long s'ils la demandent souvent.
- Heureusement, les processus temps réel ne sont normalement pas nombreux à vouloir agir en même temps. Et si c'est le cas, c'est bien qu'il vaut mieux leur donner la main de toutes manières. C'est qu'il y a une chose urgente à faire pour la sécurité du système.
- C'est le gros défaut de FIFO : si un processus temps réel boucle à l'infini, on ne pourra jamais plus faire tourner les processus normaux car il va monopoliser le CPU...
FIFO et OTHER sont sur un bateau
Pour permettre aux processus OTHER de continuer à travailler un peu (par exemple pour répondre à une demande de fermeture d'un processus temps réel qui tourne en boucle !) ce choix a été fait sous Linux :
- Si les processus temps réels ont la main depuis 950 ms,
- On donne temporairement la main aux processus temps partagé sous OTHER pendant 50 ms.
C'est un moyen de limiter la casse en cas de processus prioritaire mal programmé et tournant en boucle ou travaillant de façon continue à cause d'un très gros calcul.
14° Etudier les accès au processeur par les trois processus suivants. Il faut que vous puissiez retrouver les processus sélectionnés en utilisant les demandes des 3 processus.
Processus R : ⚑⚑⚑⚙7 ⚑⚑⚑⚑⚙2 ⚑⚑⚑⚑⚙2 ⚑⚑⧗ qui commence dès le temps 1 avec une priorité temps réel de 70.
Processus B : ⚑⚑⚑⚑⚑ ⚑⚑⚑⚑⚑ ☠ qui commence dès le temps 3 avec une priorité temps réel de 50.
Processus V : ⚑⚑⚑⚑⚑ ⚙20 ⚑⚑⧗ qui commence dès le temps 6 avec une priorité de 65.
15° Quel est le problème pour le processus bleu, alors qu'il est aussi prioritaire que le processus rouge ?
Processus R : ⚑⚑⚑⚑⚑ ⚑⚑⚑⚑⚑ ⚑⚑⚙7⧗ qui commence dès le temps 1 avec une priorité temps réel de 50.
Processus B : ⚑⚑⚑⚑⚑ ⚙7⧗ qui commence dès le temps 2 avec une priorité temps réel de 50.
...CORRECTION...
Puisqu'il est arrivé après le processus rouge, il va devoir attendre que celui-ci finisse son travail avant de pouvoir agir...
Processus R : ⚑⚑⚑⚑⚑ ⚑⚑⚑⚑⚑ ⚑⚑⚙7⧗ qui commence dès le temps 1 avec une priorité temps réel de 50.
Processus B : ⚑⚑⚑⚑⚑ ⚙7⧗ qui commence dès le temps 2 avec une priorité temps réel de 50.
t 1234567890123456789012345678901
R ■■■■■■■■■■■■■xxxxxxxxxxxxxxxxxxxxxxxx
B --◻◻◻◻◻◻◻◻◻◻◻■■■■■■xxxxxxxxxxxxxxxxxx
t 1234567890123456789012345678901
P ■■■■■■■■■■■■■■■■■■■
Pour pallier à ce défaut lorsque deux processus ont la même priorité temps réel, on peut prévoir des alternances programmées dans les processus, en utilisant des appels systèmes qui permettent au processus de rendre la main volontairement. Dans ce cas, on obtient une alternance si plusieurs processus de même priorité attendent. Mais encore faut-il que les développeurs y pensent et que leurs programmes ne se fassent pas alors doublés par des processus plus agressifs qui ne rendent pas la main...
Pour résoudre le problème des processus prioritaires et n'intégrant pas de tentatives volontaires de rendre la main, nous allons découvrir une dernière politique d'ordonnancement.
5 - Temps réel : Tourniquet / Round-Robin RR
Ce dernière politique d'ordonnancement est en réalité une variante de la stratégie FIFO temps réel.
Il s'agit de rajouter une préemption au bout d'un temps fixe en plus de la préemption en cas d'arrivée
Politique Tourniquet-Round-Robin-RR - "temps réel" avec préemption temporelle et de priorité
Priorité
On utilise les priorités temps réel entre 1 et 99 la plupart du temps, comme celles de FIFO temps réel.
Principe
- Election : on prend le processus de plus grande priorité temps réel à l'état PRET. En cas d'égalité, on utilise une FILE et c'est donc le premier arrivé dans la file qui en sort Comme FIFO temps réel.
- Préemption de priorité : le processus ELU repasse à l'état PRET dès qu'un processus de plus grande priorité passe à l'état PRET. On donne donc clairement la main au processus qui a été jugé le plus critique. Comme FIFO temps réel.
- Préemption temporelle : au bout d'un certain temps-machine, le processus repasse à l'état PRET s'il y a d'autres processus de même priorité que lui. Revenant dans la File à l'arrière, il laisse la main à un autre processus. C'est la nouveauté par rapport à FIFO.
C'est tout.
C'est pour cela que cette politique d'ordonnancement se nomme Tourniquet.
Comme sur un tourniquet, on va voir passer les processus de même priorité tour à tour dans le CPU sans que l'un d'entre eux ne garde la main trop longtemps.
16° Reprenons les deux processus de la question 15. On fixe le quantum d'utilisation à 4 temps-machine. Quelle différence avec FIFO temps réel ?
Processus R : ⚑⚑⚑⚑⚑ ⚑⚑⚑⚑⚑ ⚑⚑⚙7⧗ qui commence dès le temps 1 avec une priorité temps réel de 50.
Processus B : ⚑⚑⚑⚑⚑ ⚙7⧗ qui commence dès le temps 2 avec une priorité temps réel de 50.
...CORRECTION...
Processus R : ⚑⚑⚑⚑⚑⚑⚑⚑⚑⚑⚙7⧗ qui commence dès le temps 1 avec une priorité temps réel de 50.
Processus B : ⚑⚑⚑⚑⚑⚙7⧗ qui commence dès le temps 2 avec une priorité temps réel de 50.
t 1234567890123456789012345678901
R ■■■■◻◻◻◻■■■■◻◻■■■■■xxxxx
B --◻◻■■■■◻◻◻◻■■xxxxxxxxxx
t 1234567890123456789012345
P ■■■■■■■■■■■■■■■■■■■
17° Imaginons trois processus.
On fixe le quantum d'utilisation à 4 temps-machine.
Processus R : ⚑⚑⚑⚑⚑ ⚑⚑⚑⚑⚙7 ⚑⚑⚑⚑⚙7 ⚑⚑⚑⚑⚙7⧗ qui commence dès le temps 1 avec une priorité temps réel de 50.
Processus B : ⚑⚑⚑⚙3 ⚑⚑⚑⚙2 ⚑⚑⚑⚙6 ⚑⚑⚑⚙2⧗ qui commence dès le temps 3 avec une priorité temps réel de 50.
Processus V : ⚑⚑⚑⚑⚑ ⚑⚑⚙10 ⚑⚑⧗ qui commence dès le temps 10 avec une priorité temps réel de 50.
Fournir la liste successive des instructions accomplies en considérant un quantum de temps-machine de 5.
18° Pourquoi ne pas prendre des quantums de temps trop petits ? Quel phénomène ne prend-t-on pas en compte actuellement sur cet exercice papier ?.
...CORRECTION...
On ne gère pas les changements de contexte.
Si on sauvegarde et charge trop souvent le contexte, une partie non négligeable du temps-processeur va servir à ...changer de processus plutôt qu'à servir à faire avancer les instructions des processus.
"Temps réel"
Pour les applications Temps réel, on voit bien que cela peut poser problème : rien ne peut garantir qu'on redonne immédiatement la main au bon processus si plusieurs processus on la même priorité.
Il faut alors se tourner vers des OS plus orientés temps réel, notamment des noyaux basés sur un noyau Linux mais possédant une gestion temps réel encore plus précise que celles que nous venons de présenter.
6 - FAQ
tty, pty et pts, c'est quoi ça ?
Le sigle tty désigne un vrai terminal de commande, en texte et implémenté directement dans le système.
Le sigle pty désigne un pseudo-terminal de commande, une émulation à travers un autre programme comme ssh pour une connexion à distance ou bash pour un "terminal" à l'intérieur d'une application graphque.
Le sigle pts désigne un pseudo-terminal slave, une partie d'un pty.
Processus et Thread, c'est pareil ?
Non, un processus est bien une instance d'un programme qui sa propre zone mémoire virtuelle.
Par contre, un processus peut faire tourner à tour de rôle plusieurs petits processus qui partagent sa propre zone mémoire virtuelle. On nomme ces "processus légers" des Threads. Les Threads ne sont donc pas des processus autonomes mais font partie d'un processus.
Activité publiée le 06 03 2022
Dernière modification : 06 03 2022
Auteur : ows. h.