23 juillet 2020
On appelle processus, ou tâche, un programme qui est en cours d’exécution sous le contrôle du système d’exploitation.
Ce cours s’intéresse aux systèmes multi-tâches qui font tourner plusieurs processus présents en mémoire en même temps. De nos jours, ces systèmes multi-tâches sont présents dans tous les ordinateurs grands et petits (smartphones).1.
On parlera indifféremment de multi-tâches ou de “temps partagé” (time sharing), même si les puristes réservent ce dernier terme aux systèmes multi-utilisateurs.
Un système multi-tâches “fait tourner” plusieurs processus à la fois, même sur une machine qui n’a qu’un seul processeur, grâce la technique de “temps partagé” (time slicing).
En réalité, le processeur fait avancer chaque tâche pendant pendant un petit laps de temps (de l’ordre de 10-100ms), puis passe à la suivante, etc. Ce laps de temps étant très court, ceci donne, à notre échelle, une illusion d’avancement simultané, tout comme la projection rapide d’images fixes successive donne une illusion de continuité.
Comme plusieurs processus sont présents, il se pose plusieurs problèmes :
Pour pouvoir faire tourner des programmes écrits dans des langages de haut niveau, il faut que les compilateurs convertissent les appels aux “fonctions système” en appels à une bibliothèque “runtime” d’exécution, qui fera les appels systèmes en se conformant à l’ABI (Application Binary Interface) du système, c’est-à-dire aux conventions fixées pour les numéros de service, les registres utilisés etc.
La notion d’interruption permet de voir l’ordinateur comme un “système réactif”, dont l’état évolue par exécution des instructions, mais qui répond aussi à l’arrivée d’évènements extérieurs.
La table des processus est une structure de données centrale d’un système d’exploitation.
Elle contient la description des divers processus présents en mémoire, avec pour chacun :
Situation banale : vous avez plusieurs fenêtre ouvertes à l’écran. Dans un navigateur web, vous cliquez sur un lien, qui tarde à répondre. Vous en profitez pour continuer à faire autre chose dans une autre fenêtre.
Que s’est-il passé ?
Maintenant, le système peut activer une des autres tâches présentes.
Que se passe-t-il ensuite ?
On voit donc 3 états possibles pour les processus
Des changements d’état ont lieu, sous le contrôle du système d’exploitation :
ACTIF
^ _\
/ \
activation / \ envoi
/ \ requête
/ v
PRÊT <--------- BLOQUÉ
requête
terminéeCeci entraîne des commutations de contexte
Quand un processus est activé, les informations du bloc de contexte sont placées dans les registres, et l’exécution reprend là où elle en était arrêtée.
TODO.
Reprendre quelques classiques, pour montrer
Par exemple tâches qui font quelques cycles calcul/entrée sortie.
Voir aussi cohabitation de tâches “IO-bound” et “CPU-bound”.
Avec le système expliqué ci-dessus, si un processus ne fait que du calcul et aucun appel système (par exemple parce que le programmeur a fait une boucle sans fin), il reste actif et donc monopolise la machine indéfiniment.
On souhaite évidemment éviter cette situation, que l’on retrouvait dans les systèmes d’exploitation à “ordonnancement coopératif” (MacOs jusqu’à la version 9, Windows jusqu’à 3.11),, dans lesquels on compte sur la bonne volonté et la compétence des programmeurs d’application pour que tout se passe bien.
La solution est d’utiliser un timer (circuit d’horloge) qui émet une interruption au bout d’un certain temps (typiquement 20-100 ms).
Ce timer
Le processus actif est alors mis à l’état prêt, et un autre processus prêt est choisi pour être activé.
ACTIF
^ _\
// \
activation // \ envoi
// timeout \ requête
/v v
PRÊT <--------- BLOQUÉ
requête
terminéeAinsi, on évite que le “temps de processeur” soit monopolisé par un programme qui boucle (ou qui calcule très longtemps).
On appelle “quantum” la durée accordée à un processus actif avant qu’il soit interrompu par le timer. Compromis à trouver :
Dans la mesure où c’est très dépend de ce qu’on donne à faire à la machine, solution pragmatique : essayer, mesurer, ajuster.
Il reste un petit détail à régler concernant l’ordonnancement, c’est-à-dire la manière de choisir un processus prêt pour l’activer, sachant qu’il peut y en avoir plusieurs.
On peut imaginer plusieurs façons de faire. On les compare sur des critères
qui dans la réalité sont évidemment contradictoires.
Sûr et équitable, mais ne permet pas d’avoir des processus plus prioritaires que d’autres.
Efficace, mais risque : si les processus du niveau le plus élevé bouclent, situation de monopole ou de coalition qui empêche les autres processus de s’exécuter.
Les tâches courtes sont favorisées, ce qui est agréable pour l’utilisation interactive. Quand un calcul se met à durer, il devient moins prioritaires.
Problème : deux processus qui bouclent en communiquant par un pipe conservent une priorité élevée.
(Multi-level feedback queues)
En pondérant (par exemple files choisies à 70%, 20% et 10%) on favorise certains processus, sans risque de monopole.
Les systèmes multi-tâches, inventés à la fin des années 50, ont été rendus possibles pratiquement par l’introduction dans les processeurs de divers dispositifs matériels : interruptions, modes, protection mémoire, etc.
Dans la machine, un seul programme peut être actif à la fois, par processeur. Dans le système d’exploitation, les programmes présents en mémoire sont répertoriés dans une table des processus, qui contient leur état (actif, prêt, bloqué), et les informations nécessaires pour pouvoir les “activer”.
L’état des processus change par le biais des interruptions :
Lorsqu’un processeur se libère, l’ordonnanceur (scheduler) choisit, parmi les processus qui sont prêts, celui qui sera activé.
Ce choix se fait selon une politique d’ordonnancement où rentrent en compte divers facteurs, parmi lesquels l’équitabilité, des priorités voulues, l’impossibilité de monopoliser les processeurs, etc.
Dans la mémoire de l’ordinateur vont se retrouver le code et les données des processus, ainsi que du système d’exploitation.
Comment se répartir cet espace, et surtout le protéger contre les erreurs des programmes ?
Dans un système mono-tâche, le système d’exploitation est chargé au démarrage (typiquement au fond de la mémoire), et y reste jusqu’à l’arrêt de la machine. Et les programmes d’applications sont ensuite chargés au début de l’espace restant.
En passant à un système multi-tâches, on peut imaginer placer les programmes d’applications les uns après les autres. Chaque programme occupera une plage d’adresses (adresse de début / adresse de fin)
Comme les programmes apparaissent et disparaissent au gré des chargements et fin d’exécution, le système tient une comptabilité des espaces disponibles.
Le chargement d’un programme sera possible uniquement si on peut lui allouer un espace suffisamment grand pour le loger. Mais il ne suffit pas que le total des espaces libre excède la taille du programme, il faut aussi que cet espace soit contigu (en un seul morceau),
Exemple : on a chargé successivement des programmes A, B, C, D de tailles respectives 20, 10, 20, 30 KiB dans une mémoire de 64 KiB. Les programmes A et C se terminent, ce qui laisse 40 KiB octets disponibles. Mais on ne pourra pas lancer un programme de 25KiB, parce que le plus grand bloc libre est de 20 KiB seulement. La mémoire est trop fragmentée.
Le mécanisme d’allocation consiste à chercher un bloc assez grand pour y loger le programme. Diverses stratégies sont possibles :
Dans tous les cas, lors de la libération, le bloc qui se libère est fusionné si possible avec les blocs libres voisins pour en former un plus gros.
Exercice : La stratégie best-fit est une heuristique2 qui ne résout pas complètement le problème. Trouvez des scénarios (suite d’allocations et de libérations) pour lesquels
Lorsqu’un programme d’application s’exécute, le matériel doit l’empêcher d’accéder à autre chose que son propre espace mémoire.
Une solution simple est d’équiper le processeur de “registres limite” dans lesquels le système mettra les adresses de début et de fin de cet espace. Des comparateurs3 connectés aux registres et au bus d’adresse détecteront toute tentative d’accéder en dehors de cette plage, et déclencheront une interruption “accès mémoire illégal”.
Ces registres ne sont manipulables qu’en mode privilégié.
En pratique, cette idée a été peu utilisée. En effet, a priori les programmes d’applications peuvent être chargés n’importe où, en fonction de ce qui a été chargé avant. Or les programmes contiennent des instructions de branchements, avec des adresses calculées à la compilation. Il devient compliqué de charger des programmes qui contiennent des adresses absolues. De même si on veut les déplacer pour “dé-fragmenter” la mémoire.
Une idée plus intéressante est de considérer que chaque processus dispose d’un espace mémoire, qu’il voit à travers des “adresses logiques” qui - pour lui- commencent à 0.
Cet espace logique correspond à une plage d’adresses physiques. En additionnant une adresse logique et l’adresse de début de la plage, on obtient l’adresse physique correspondante.
Dans le processeur on intègre quelques circuits pour effectuer la génération d’adresses physiques :
et pour la protection :
Ceci introduit une distinction conceptuelle entre deux espaces d’adressage :
Cette indépendance permet au système d’exploitation de déplacer un programme, en copiant ailleurs son “image mémoire” et en faisant pointer le registre de base vers le nouvel emplacement. C’est une stratégie curative pour le problème de fragmentation.
Malheureusement, c’est une opération qui prend du temps.
Et on doit aussi le faire quand un programme demande à disposer de plus d’espace mémoire pendant son exécution4, alors que son espace mémoire est suivi par un autre espace occupé.
Une approche radicalement différente apporte une solution à ces problèmes, et conduira à la notion de “mémoire virtuelle” (voir plus loin).
Découpage de l’espace logique : L’espace logique d’un processus est maintenant considéré comme une succession de “pages” de même taille (une puissance de 2, dépendant de l’architecture de la machine).
Par exemple, sur une machines à pages de 4Kib (212 = 4094), un processus de 10354 octets occupe 3 pages. La page 0 correspond aux adresses logiques 0 à 4095, la page 1 aux adresses de 4096 à 8191, et la page 2, qui n’est pas complètement occupée, de 8192 à 12287.
Calculer le calcul du numéro de page correspondant à une adresse logique n’est pas compliqué : c’est le quotient de l’adresse logique (par exemple 9876) par la taille de page (4096), soit 2. Et le reste donne l’offset (position dans la page).
Aucun circuit de calcul n’est nécessaire : l’offset est dans les 12 bits de droite de l’adresse, le numéro de page dans les bits de gauche.
binaire décimal
--------------------- ------------------ ----------
adresse 0010 0110 1001 0100 = 9876
numéro de page 0010 = 2
position dans la page 0110 1001 0100 = 1688L’espace d’adressage physique est, de la même façon, découpé en “cadres” (de page) la même taille5.
Bien évidemment, les pages logiques correspondront à des cadres.
La correspondance est assurée par un groupe de registres appelé table des pages, qui fait partie de la MMU (memory management unit), un composant du processeur.
Ces registres établissent une correspondance entre
Exemple, avec une table des pages qui contient
| page | cadre |
|---|---|
| 0 | 4 |
| 1 | 10 |
| 2 | 3 |
l’adresse logique 5100, qui est à la position 1006 de la page 1, (parce que 5100 = 1 × 4096 + 1006) se trouve en mémoire à la position 1006 du cadre 10 (qui correspond à la page 1), soit l’adresse physique 10 × 4096 + 1006 = 41966.
La table est consultée à chaque accès à la mémoire pour générer l’adresse physique. Pour un accès rapide (en temps élémentaire), elle utilise un indexage matériel (multiplexage, registres associatifs…).
La table est chargée par le système d’exploitation quand un processus est activé. Dans la table des processus, on trouve donc une copie de la table des pages du processus.
Les tables de page permettent d’avoir des espaces mémoires communs à plusieurs processus. Exemple, avec les tables de pages ci-dessous, les processus P1 et P2 ont tous deux accès aux octets du cadre n°6,
P1 P2
--- ---
0 4 0 1
1 2 1 0
2 6 2 3
3 6mais ils ne le voient pas avec les mêmes adresses logiques.
Note : les droits d’accès à des pages communes peuvent être différents. Pour faire respecter ces droits d’accès, la MMU contiendra aussi des indicateurs de permissions (lire, modifier, faire exécuter).
Si on observe ce qui se passe dans la machine, on constate qu’en fait la plupart des pages qui ont été chargées ne sont pas “actives”. Par exemple, le début d’un programme a été chargé et exécuté, et on ne revient pas dessus ensuite.
Qui plus est, les adresses utilisées par un processus sur une courte période de temps sont souvent voisines les unes des autres (principe de localité).
Ce qu’on appelle l’ensemble de travail, c’est-à-dire les pages dont se sert effectivement un processus à un moment donné, est nettement plus petit que l’espace d’adressage du processus.
On peut donc envisager de retirer les pages inactives de la mémoire, pour faire de la place à d’autres programmes.
Mais a priori, on ne sait pas si une page inactive va resservir dans le futur ou pas. Une idée naturelle est donc de les sauvegarder sur disque6, pour pouvoir les récupérer au besoin.
Ceci conduit à la notion de mémoire virtuelle, qui contient à la fois les pages présentes en mémoire centrale (mémoire réelle), et celles qui ont été sauvegardées sur disque.
Nous allons voir maintenant comment la conjonction du matériel et du système d’exploitation permet de donner aux programmes l’illusion qu’ils fonctionnent comme en mémoire, mais dans un espace qui est beaucoup plus grand.
Matériel
Le système d’exploitation
Quand cette page finit par arriver (le disque est un périphérique relativement lent) :
Le principe est donc relativement simple. La difficulté est de trouver un cadre de page disponible. Quand toute la mémoire est occupée, il faut “sortir” une page présente (paging out) pour pouvoir ramener (paging in) celle dont le processus a besoin.
Les performances de la machine dépendront de la qualité de l’algorithme d’éviction utilisé pour choisir la page présente que l’on va remplacer.
Les facteurs qui rentrent en compte
Et donc : les pages qui n’ont pas servi depuis longtemps et/ou qui n’ont pas été modifiées depuis longtemps sont de “bons candidats” pour l’éviction.
Une petite modification de la MMU permet de connaître les pages qui n’ont pas été utilisées depuis longtemps.
Un indicateur R est ajouté pour chaque page, il indique si la page a été accédée (R = referenced).
Et dans les tables du système, un entier est aussi ajouté pour coder l’“âge” de chaque page :
Ceci permet de mettre en place la stratégie dite “LRU” (least recently used) où on choisit d’évincer une des pages les plus âgées, qui n’a pas servi depuis longtemps.
Dans la MMU, on ajoute un bit M (M = modified) pour chaque page.
Il indique donc si la page a été modifiée depuis son chargement.
Le système interrogera la MMU pour récupérer la liste des pages modifiées.
En prenant en compte cette information, on obtient une stratégie du type :
choisir une des pages les plus âgées, non modifiée de préférence
Exercice: Dans la littérature, on trouve une version de cette stratégie sous le nom “NRU” (not recently used). Elle n’utilise que les bits R et M, et pas l’âge. Ces bits définissent 4 classes de pages. Dans quel ordre sont-elles choisies ?
La mémoire virtuelle permet une meilleure utilisation de la mémoire primaire, en libérant la place occupée par les pages inactives.
Les pages inactives sont transférées (évincées) en mémoire secondaire, d’où elles peuvent être récupérées en cas de besoin (défaut de page détecté par la MMU lors de la génération d’adresses).
Les échanges entre mémoires primaire et secondaire étant lents, la qualité de l’algorithme d’éviction (choix d’une page à sauvegarder pour la remplacer par une autre qui est nécessaire) est primordiale. Ces algorithmes se basent essentiellement sur deux considérations
Il est donc préférable de choisir d’évincer une page qui n’a été référencée depuis longtemps, et qui n’a pas été modifiée.
Note: lorsqu’une machine est “chargée” avec des processus qui n’ont pas ce comportement “local”, les défauts de page devient trop nombreux, et les transferts entre mémoire primaire et secondaire deviennent un goulot d’étranglement qui cause un écroulement des performances (thrashing).
Les systèmes mono-tâches existent dans les petits dispositifs d’informatique embarquée qui ne font qu’une chose à la fois. Par exemple une centrale météo qui relève la température, la pression, etc. et transmet les données périodiquement à un serveur.↩
technique susceptible de fournir une solution approchée à un problème (mais pas toujours).↩
Un comparateur est un soustracteur, dont on utilise le signe du résultat.↩
par exemple parce qu’ils font de l’allocation dynamique (instruction new en C++, Java, etc).↩
pour éviter les confusions, on parle de “page” pour les adresses logiques, et de “cadre” pour les adresses physiques.↩
Une ressource plus abondante, moins chère, mais aussi d’accès plus lent que la mémoire centrale (on ne peut pas tout avoir).↩
dans le sens de “faire défaut”, c’est-a-dire manquer.↩