Processus et exécution

Description des processus

Les processus permettent à toutes les applications de progresser simultanément, les processeurs physiques les exécutent en alternance et chaque application a l'illusion d'être seule sur la machine. Les processus ont pour objectif de partager les ressources disponibles entre de multiples applications pour utiliser les ressources efficacement.

Définition : Un processus est un programme en exécution, une instance d'un programme s'exécutant sur un ordinateur, une entité pouvant être assignée et exécutée sur un processeur ou une unité d'activité caractérisée par l'exécution d'une suite d'instructions, un état courant et un ensemble de ressources système.

Les processus sont caractérisés par leur initialisation (code du programme, ensemble de données en entrée), leur état durant l'exécution (bloc de contrôle) et un identifiant (PID).

Le bloc de contrôle d'un processus est composé de :

• un identifiant
• des adresses mémoire
• le compteur ordinal (program counter) et les registres sauvegardés
• état d'ordonnancement
• état des entrées / sorties
• privilèges
• statistiques

Chaque processus a une généalogie, c'est-à-dire un processus père et potentiellement des processus fils. Le père de chaque processus est notifié de la mort de ses fils, peut l'attendre et savoir s'il a réussi. Un processus peut devenir orphelin (il est alors adopté par le processus init, de PID 1).

Exécution des processus

Le processeur exécute les instructions au rythme de son horloge (cycles de durée fixe, liée à la fréquence, avec un pipeline). Une horloge matérielle (timer) interrompt régulièrement le processeur pour redonner la main au système (entre 100 et 1000 fois par seconde sous Linux selon la configuration). Chaque processus possède un mode d'exécution avec différents privilèges.

Modes d'exécution

Il existe plusieurs niveaux de privilèges qui sont mis en place matériellement par le processeur (accès aux registres de contrôle, instructions d'entrées / sorties de bas niveau, gestion mémoire). Les différents niveaux de privilèges définissent les instructions autorisées. Le noyau peut tout faire, sauf en cas de virtualisation matérielle, où seul l'hyperviseur peut tout faire.

Le mode utilisateur est quant à lui très limité (protection ring 3 sur x86) et n'a pas accès à la mémoire du noyau.

Exceptions et interruptions

Ce sont des événements inattendus qui interrompent temporairement l'exécution en cours. Le processeur saute automatiquement et immédiatement à un traitant (fonction dont l'adresse a été définie par le système d'exploitation au démarrage). Le traitant dépend du type d'exception ou d'interruption.

Une exception est déclenchée par le processeur lui-même lorsqu'une instruction provoque une erreur et qu'il ne sait pas comment continuer (défaut de page, division par zéro, etc.) : il demande alors à l'OS de l'aider. Si le traitant a pu corriger la situation (par exemple en chargeant la page manquante), l'exécution reprend au même endroit et l'application ne se rend compte de rien ; sinon, l'OS signale l'erreur au processus (par un signal, qui le termine souvent).

Les exceptions sont synchrones : elles ne se produisent que lorsque le processeur exécute une instruction.

Les interruptions sont des messages d'un périphérique (signal électrique sur une broche dédiée du processeur ou écriture à une adresse mémoire spéciale). C'est un événement asynchrone, le processeur pourrait continuer à tourner en l'ignorant pendant un certain temps.

Les interruptions peuvent survenir n'importe quand, même si le processeur ne fait rien ; elles n'ont pas d'influence directe sur la tâche qui s'exécutait (l'application ne se rend compte de rien).

Les appels système sont des exceptions provoquées volontairement par une application (instruction spéciale) pour effectuer une opération privilégiée. Ils se produisent uniquement depuis l'espace utilisateur, à la demande des applications.

Appels système

Le traitement de l'appel système est effectué dans le traitant de l'instruction spéciale, dont l'adresse est définie par le noyau au démarrage ; le processeur y saute immédiatement lors de l'appel système. S'ensuit une exécution temporaire en mode privilégié (le processus n'est pas interrompu : son exécution est déroutée).

L'appel système se fait en passant les paramètres au traitant. Convention de passage des paramètres sous Linux x86 32 bits (int $0x80) : numéro dans %eax et arguments dans %ebx, %ecx, %edx, %esi et %edi.

Une fois le traitement terminé, les registres utilisateur sont restaurés et le retour en espace utilisateur se fait par une instruction spéciale (iret, sysexit).

Les appels système sont coûteux, et certains sont parfois inutiles (le résultat de gettimeofday() peut être calculé sans privilège particulier) : les appels système virtuels (vsyscall, puis vDSO sous Linux) permettent d'exécuter ces appels directement en espace utilisateur.

Processus et threads

Vie et mort des processus

Sous Unix, le lancement d'un programme se fait par la création d'un nouveau processus puis l'exécution d'une commande (fork() + exec()). Le fork() permet de dupliquer l'espace d'adressage et de créer un nouveau fil d'exécution dans cet espace. Le fils créé est identique au père, sauf pour son PID (et la valeur renvoyée par fork()).

La création d'un thread revient à ajouter un fil d'exécution dans l'espace d'adressage courant, via pthread_create() ou l'appel système clone(). Pour lancer une tâche, le noyau crée un contexte utilisateur. Ce contexte pointe vers une fonction à exécuter et possède une nouvelle pile. Lors de la terminaison d'une tâche, il faut passer en mode noyau, par un appel système (exit) ou une exception. La file d'exécution est alors détruite et relâche les ressources qu'elle utilisait. Lorsqu'une tâche se termine elle renvoie un code de retour destiné au père. Le père peut attendre la terminaison d'un fils précis ou de n'importe quel fils (waitpid() et wait()). La tâche terminée reste zombie tant que le père n'a pas récupéré son code de retour.

Les processus prêts à s'exécuter sont dans une file d'attente spéciale appelée runqueue. Cette liste est utilisée uniquement pour les processus prêts ; les processus non prêts sont dans des files spéciales avec un moyen de les retrouver. Il ne sert à rien de parcourir une liste de 1000 processus pour trouver le seul prêt à s'exécuter.

Les attentes actives sont des boucles infinies qui attendent un événement : elles monopolisent le processeur jusqu'à l'événement. Elles offrent une très bonne réactivité mais gaspillent des cycles processeur. L'attente semi-active est une attente active en rendant la main. L'opération yield() à chaque itération d'une boucle while est effectuée et la réactivité est imprévisible (pas de garantie de reprise de main rapide). Cela peut gaspiller autant de temps CPU (dépend de l'activité des autres tâches). L'attente semi active n'est à utiliser que quand une attente passive est totalement impossible.

L'attente passive d'un événement est un mécanisme de réveil lors de l'événement. La tâche est placée sur une file d'attente et elle n'est plus dans la runqueue (ignorée par l'ordonnanceur). Lors de l'événement, celui qui produit l'événement déplace la tâche de la file d'attente vers la runqueue. En revanche l'endormissement et le réveil d'un processus coûtent assez cher, puisqu'il est nécessaire d'effectuer des changements de contexte. Il n'est donc rentable de mettre un processus en sommeil que si le délai d'attente n'est pas très court.

Ordonnancement

Les états des processus sont représentés par un automate de transitions entre les états suivants :

• Running
• Ready (prêt mais pas en train de s'exécuter)
• Blocked (non-prêt, en attente d'un événement)
• New (en cours de création)
• Exit (en cours de destruction, zombie)
• Suspend (suspendu par l'utilisateur)

L'ordonnanceur fait partie du noyau, mais il n'y a pas d'« homme en noir » qui ordonnance les tâches en arrière-plan : l'ordonnancement nécessite que le code de l'ordonnanceur soit effectivement exécuté. L'ordonnancement peut être activé explicitement par les applications (processus qui rend la main avec yield() ou processus qui attend sleep()) ou implicitement par des appels système bloquants (read(), poll()). Cependant, nous n'avons aucune garantie d'un ordonnancement régulier, cela dépend du bon vouloir des applications. Il y a aussi un problème d'équité et de réactivité, un processus peut conserver le processeur indéfiniment. Les tâches doivent donc coopérer.

Il faut qu'une tâche s'exécutant en mode noyau, sur le bon processeur, appelle le code de l'ordonnanceur. Il faut donc trouver un moyen d'appeler l'ordonnanceur même si l'application ne fait pas d'ordonnancement explicite ou implicite. Il faut donc utiliser le mécanisme de préemption.

La préemption est le mécanisme qui permet de désordonnancer une tâche de force si une tâche s'exécute depuis trop longtemps ou si une autre tâche est prioritaire. La préemption engendre un léger surcoût puisque l'on doit vérifier de temps en temps s'il faut désordonnancer de force mais c'est un gain énorme en équité et réactivité. Il n'y a plus besoin de coopération des processus.

Sous Linux, l'ordonnanceur vérifie s'il faut passer la main à une autre tâche lors du retour vers le code utilisateur (après un appel système ou une interruption, notamment celle du timer). Il n'y a pas de préemption directe en espace utilisateur (il faut être dans le noyau pour exécuter le code de l'ordonnanceur) : les processus sont préemptés depuis le noyau (par exemple juste avant leur retour en espace utilisateur). Le code du noyau pouvant être long et nuire à la réactivité du système, un noyau préemptible peut aussi être préempté en dehors des sections critiques. Les interruptions peuvent survenir n'importe quand.

Threads

L'intérêt des threads est le partage de ressources entre les tâches, permettant une meilleure exploitation des processeurs : un seul programme peut tourner sur plusieurs processeurs (critique depuis l'avènement des multicœurs).

Un thread est un fil d'exécution interne à un processus. Le processus devient un conteneur (au moins un thread et des ressources partagées). Certaines données ne peuvent pas être partagées (pile, registres), alors que d'autres le peuvent (espace d'adressage mémoire, fichiers ouverts, gestionnaires de signaux, identifiant du processus, etc.).

Modèle 1:1

Un thread noyau est associé à chaque thread utilisateur : la création, la destruction et le changement de contexte sont presque aussi coûteux que pour des processus, mais les threads d'un même processus peuvent s'exécuter en parallèle sur plusieurs cœurs, et un thread bloqué ne bloque pas les autres (modèle de Linux avec NPTL).

Threads en espace utilisateur

Un seul thread noyau propulse plusieurs threads utilisateur (modèle N:1) : le coût d'ordonnancement est très réduit (on reste en espace utilisateur), mais le multithreading est ignoré par le système : pas de parallélisme réel, et un appel système bloquant bloque tous les threads.

Modèle M:N

Dans ce modèle, plusieurs threads utilisateur s'exécutent sur plusieurs threads noyau. Si un thread se bloque, les autres peuvent continuer à travailler ; l'ajout de threads noyau se fait à la volée.

Algorithmes d'ordonnancement

Nous devons résoudre le problème suivant : nous avons besoin d'équité et d'interactivité dans la progression de toutes les tâches, sans que cela ne dépende de la bonne volonté des tâches (préemption). Il est donc nécessaire de déterminer la durée d'exécution allouée à chaque tâche (choix de la durée des timeslices). Il nous faut un temps ni trop court, sinon le coût d'ordonnancement devient prohibitif, ni trop long, sinon les processus n'avancent pas assez régulièrement.

En revanche il faut noter qu'il est difficile de savoir précisément si un processus est gourmand en temps processeur, l'ordonnancement est essentiellement basé sur les ticks d'horloge (peu précis).

Critères d'ordonnancement

1. Pour l'utilisateur : il est nécessaire d'avoir des performances (rapidité d'exécution ou de terminaison, réactivité, échéances, etc.), de l'équité et de la prédictibilité ;
2. Pour le système : performance (quantité de travail, utilisation du processeur), équité et respect des priorités.

Nous avons donc quelques idées pour l'ordonnancement :

• FIFO
• Round-Robin
• Shortest Job First (SJF) ou Shortest Remaining Time Next (SRTN)
• Files multiniveaux avec rétroaction (feedback)

Liste triée par priorités

Maintenir la liste des tâches triée par priorité impose une insertion en complexité linéaire en fonction du nombre de tâches. Chaque opération d'ordonnancement coûtera cher. Il faut aussi faire attention aux famines, les processus non-prioritaires ne doivent pas rester indéfiniment en fin de liste.

Listes par priorités

Nous pouvons aussi utiliser une liste par niveau de priorité (chaque liste regroupant des tâches de même priorité) : la manipulation se fait alors en temps constant. Les listes sont alors parcourues plus ou moins souvent selon la priorité.

Ajuster la timeslice aux priorités

Cela implique de définir un quantum de temps d'exécution variable (Timeslice) selon la priorité. Cela est éventuellement dynamique et calculable en temps constant.

Multicœur et multiprocesseur

Rappelons que, sur un seul processeur, la préemption permet une concurrence entre tâches par entrelacement. Le multiprocesseur implique une concurrence réelle (parallélisme) entre les tâches. La question se pose alors de savoir sur quel processeur ou cœur exécuter quelles tâches.

Il y a deux modes de fonctionnement :

1. une seule runqueue (load sharing), où tous les processeurs piochent ;
2. une runqueue par processeur, qu'il faut équilibrer (load balancing).

Ordonnancement dans Linux

L'ordonnanceur présenté en cours (ordonnanceur O(1) de Linux 2.6) est assez classique, avec une bonne interactivité et une bonne équité : chaque tâche possède une priorité effective, calculée à partir de sa priorité statique avec un bonus ou une pénalité. Depuis Linux 2.6.23, l'ordonnanceur par défaut est CFS (Completely Fair Scheduler), qui répartit le temps processeur au prorata du poids des tâches (valeur nice), remplacé par EEVDF à partir de Linux 6.6.

Exécution du système

En réalité il n'y a pas de processus noyau qui surveille tout le monde, le système s'exécute essentiellement dans le contexte des processus lorsqu'ils sont en mode noyau. Il peut seulement exister des démons (threads noyau) dédiés à des tâches périodiques.

Le noyau s'exécute à travers des points d'entrée répartis dans l'exécution des processus (pendant les appels système, lors des interruptions et des exceptions).

L'exécution en mode noyau est possible grâce à un changement de contexte (qui implique un changement des privilèges) et l'utilisation d'une pile spéciale (éviter de stocker des informations critiques en espace utilisateur). Le contexte utilisateur est sauvegardé puis restauré.

Dans le cas des micronoyaux, le noyau ne réalise que les appels système minimaux ; la gestion effective du système d'exploitation est réalisée en dehors du noyau (dans les processus serveurs dédiés).

Nous pouvons noter que les noyaux monolithiques ont besoin de traitements annexes (tâches différées, travail impossible dans un traitant d'interruption au contexte trop limité). Nous mettons donc en place l'utilisation de threads dédiés, qui tournent toujours en mode noyau (pas d'espace utilisateur). Les threads noyau sont partout, tout processus est propulsé par un thread noyau, il passe en mode utilisateur juste après sa création. Il revient en mode noyau de temps en temps.