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 étant courant et un ensemble de ressources système.

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

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

• un identifiant
• des adresses mémoires
• program counter
• é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 des fils, peut l'attendre et savoir si il a réussi. Un processus peut être orphelin (et donc adopté par le processus init pid=1)

Exécution des processus

Les procesuss sont ordonnancés par cycle (par pipeline), la durée du cycle est fixe et est reliée à la fréquence. L'horloge interrompt régulièrement pour redonner la main au système régulièrement (environ 1 fois par milliseconde sous linux). 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 processus (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 un jeu d'instructions. Le noyau peut tout faire sauf en cas de virtualisation matérielle. Seul l'hyperviseur peut tout faire.

Quant à lui l'utilisateur est 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.

Un exception est une interruption par le processeur lui-même en cas d'erreur et ne sait pas comment continuer, il demande alors à l'OS de l'aider puis reprend ensuite l'exécution au même endroit. Au final l'application ne se rend compte de rien.

Cependant les exceptions ne sont possible que quand le processeur travaille. Les reprise de l'exécution sont possible uniquement si le traitant a réparé l'erreur avec succès.

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 ont l'avantage d'être possible n'importe quand, même si le processeur ne fait rien de plus il n'y a 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 exception forcée par une application pour effectuer une opération privilégie. Elle se produit 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, l'adresse du traitant défine par le noyau au boot, le processeur y saute immédiatement lors de l'appel système. En suit une exécution temporaire en mode privilégie (le processus n'est pas encore, son exécution est déroutée).

L'appel de l'appel système se fait en passant les paramètres au traitant. Convention de passage des paramètres : numéro dans %eax et arguments dans %ebx %ecx %edx %esi et %edi.

Une fois terminé, il y a une restauration des registres utilisateurs et retour concret en espace utilisateur par instruction spéciale (iret, sysexit).

Les appels système virtuels sont des appels système chers et parfois inutiles (le retour de getpid() varie peu) on cherche donc à optimiser certains appels en espace utilisateur.

Processus et threads

Vie et mort des processus

Sous Unix la création de processus se fait via 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, de créer une nouvelle file d'exécution dans cet espace. Le fils créé est identique au père, sauf pour son PID.

La création d'un threads est équivalent à rajouter une file d'exécution dans l'espace d'adressage courant via les commandes pthread_create() ou clone(). Pour lancer une tâche le noyau créé un contexte utilisateur. Ce contexte pointe vers une fonction à exécuter, possède une nouvelle pile. Lors de la terminaison d'une tâche il faut passer en mode noyaux. Pour cela il faut un moyen d'entrer (appel système exit ou 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 ou n'importe quel fils (wait() et waitpid()). C'est une tâche zombie tant que le père ne s'en occupe pas.

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 pret, 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 attente active sont des boucle infinie qui attendent un événement, elles monopolisent le processeur jusqu'à l'événement. Ils possèdent une très bonne réactivité mais gaspillent des cycles processus. L'attente semi-active est une attente active en renadant 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 une mécanisme de réveil lors d'un événement. La tâches 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ûte assez cher puisqu'il est nécessaire d'effectuer un changements de contexte. Il est donc rentable de mettre en sommeil si processus uniquement 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 transition entre les états

• 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'exécution de l'ordonnanceur nécessite l'existence du noyau, si le noyau n'existe pas il n'y a pas d'homme en noir pour ordonnancer les tâches en arrière plan. L'ordonnancement nécessite l'exécution du code de l'ordonnanceur. L'ordonnancement peut être activé explicitement par les applications (processus qui rend la main _yield ou processus qui attend sleep()) ou implicitement par des appel système bloquant (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 donc qu'une tâche s'exécutant en mode noyau, sur le bon processeur qui doit appeler 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 engrange 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 en espace utilisateur sur le code utilisateur (le code du noyau peut être long et nuire à la réactivité du système). 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'ordonnancement), les processus sont préemptés dans le noyau de la même façon (par exemple juste avant leur retour en espace utilisateur). Les interruptions peuvent préempter n'importe quand.

Processus et threads

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

Un thread est une file 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 (piles registres) alors que d'autre le peuvent (espace d'adressage mémoire, fichiers ouverts, signaux, identifiant des processus ...)

Modèle 1 on 1

Un thread noyau est actif pour chaque thread, la création / destruction / changement de contexte sont aussi coûteux que les processus, les processus multi-threads sont avantagés.

Threads en espace utilisateur

Un seul thread noyau propulse plusieurs threads utilisateurs, le coût d'ordonnancement est très réduit (on reste en espace utilisateur), le multithreads est ignoré par le système

Modèle M on N

Dans ce modèle il y a plusieurs threads utilisateurs sur plusieurs threads noyau. Si un thread bloque une tâche, les autres tâches peuvent continuer à travailler, l'ajout de threads noyau se fait à la volée.

Algorithmes d'ordonnancement

Actuellement nous devons résoudre le problème suivant, nous avons besoin d'une équité et de l'interactivité de 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'ordonnancement (choix de la durée des Timesclices). Il nous faut un temps pas 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'holorge (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é, deadlines ...), d'équité et de prédictabilité
2. Pour le système : performance (quantité de travail, utilisation du processus), équité et respect des priorités

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

• FIFO
• Round-Robin
• Short First ou Short Remaining Next
• Feedback

Liste triée par priorités

Trier par priorité la liste des tâches s'effectue 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 effectuer plusieurs listes de tâches possédant toutes les mêmes priorités, 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.

Le multicoeurs et multiprocesseur

Nous rappelons que la préemption est la concurrence entre tâches sur un seul processeur. Le multiprocesseur implique une concurrence réelle entre les tâches. La question se pose sur quel processeur / coeur exécuter quelles tâches.

Il y a donc deux modes de fonctionnement

1. Une seule runqueue (load sharing) où tous les processeurs piochent
2. Une runqueue par processeur, qu'il faudra équilibre (load balancing)

Ordonnancement dans Linux

L'ordonnanceur dans Linux est assez classique possédant une bonne interactivité et équité. Il possède une priorité effective avec un bonus ou pénalité.

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 éventuellement des démons dédiés à des tâches périodiques.

Le noyau s'exécute à travers des hooks un peu partout dans le code qui n'a rien à voir (pendant les appels systèmes, dans le cas d'interruptions / 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 micro-noyaux on réalise les appels systèmes minimaux, la gestion effective du système d'exploitation est réalisé en dehors du noyau (dans les processus serveurs dédiés).

Nous pouvons noter que les noyaux monolithiques ont besoin de traitement annexes (appels systèmes imprévisibles, traitants d'interruption dans contexte trop limité). Nous mettons donc en place l'utilisation de threads dédiés, qui tournent toujours en mode noyau (pas d'espace d'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.