Les modèles de coopération entre processus
De très nombreux problèmes de coopération entre processus se ramènent à quelques modèles de base bien connus, dont nous présentons ici succinctement les deux plus courants.
Il s'agit des modèles dits "lecteurs/rédacteurs" et "producteurs/consommateurs".
Leur résolution formelle, quoique passionnante, n'entre pas dans le cadre de ce cours.
De nombreux ouvrages généraux sur les fondements des systèmes d'exploitation abordent ces problèmes, et le livre de Ben-Ari
[BenAri86]
leur est entièrement consacré.
Le partage de ressources critiques, sera lui aussi abordé ici.
Problèmes liés à la coopération entre processus
Tous ces problèmes peuvent être mis sous la forme suivante :
EntreeEnSectionCritique ();
ActivitéEnSectionCritique ();
SortieDeSectionCritique (); |
Des problèmes peuvent survenir dans chacune de ces phases, entraînant un dysfonctionnement du système pouvant aller jusqu'à son blocage complet :
Interblocage
On dit qu'il y a interblocage (ou étreinte fatale, deadlock) lorsque les EntreeEnSectionCritique() de deux processus interagissent et qu'aucune des deux ne peut être réalisée à cause de l'autre.
Un
exemple
est montré en utilisant des sémaphores.
Attente indéfinie en section critique
Si un processus est bloqué entre l'entrée et la sortie de sa section critique; s'il est dans une boucle infinie, ou, pire, s'il est détruit à l'intérieur, les conséquences peuvent être catastrophiques pour les autres processus en attente.
Ce problème est pris en compte par Unix, par exemple dans le
déverrouillage
des fichiers.
Privation (ou famine)
Par un concours de circonstances, et bien que l'algorithme soit juste et bien codé, il peut arriver que certains processus ne puissent jamais entrer dans leur section critique, ou avec un délai trop long pour être acceptable.
Si par exemple un processus a besoin de 2 Koctets de mémoire pour fonctionner alors que tous les autres processus n'en ont besoin que de 1 Ko, alors il suffit qu'ils se relaient de telle façon que chacun ne se termine que lorsqu'un autre a démarré pour que le processus le plus "gourmand" ne puisse jamais avoir satisfaction : c'est une situation de privation ou de famine.
Parfois la situation peut paraître suffisamment rare et peu probable au concepteur pour qu'il en prenne le risque.
Malheureusement, avec une augmentation significative de la charge, le phénomène peut devenir fréquent et même systématique.
Pour cette raison, les situations de famine doivent être systématiquement détectées et évitées.
Une telle situation est étudiée ci-dessous.
Partage de ressources critiques
Rappelons tout d'abord qu'une ressource (matérielle : processeur, mémoire, imprimante, ligne téléphonique, etc. ou logicielle : séquence de code, variables ou objets, etc.) est dite critique si elle ne peut être utilisée simultanément que par un seul processus, ou un nombre maximal fixé de processus (ascenseur, sas, etc.) ou un ensemble limité ou non de processus, mais partageant des caractéristiques communes.
Du fait de ces restrictions, une politique d'attribution de cette ressource doit être établie.
Il faut aussi noter que la section critique du
schéma général ci-dessus
est une ressource critique !
Ce schéma peut être reformulé de façon plus explicite :
AcquerirRessourceCritique ();
UtiliserRessourceCritique ();
LibererRessourceCritique (); |
Lorsque la ressource requise n'est pas disponible, AcquerirRessourceCritique() peut soit bloquer le processus qui l'appelle, soit lui signaler qu'elle n'est pas disponible pour lui permettre d'envisager une alternative.
Si la ressource peut être acquise en une seule opération (réserver une imprimante par exemple), les techniques les plus rudimentaires (verrous, sémaphores) ou les plus élaborées (moniteurs, objets protégés) sont utilisables sans problème.
Au contraire, si la ressource critique est complexe et nécessite plusieurs opérations, les techniques les plus simples peuvent engendrer des situations d'erreurs, en particulier d'
interblocage.
Considérons par exemple qu'un processus ait besoin de deux ressources, un crayon et une gomme, pour pouvoir effectuer un traitement, et que ces objets soient disponibles en un seul exemplaire.
L'algorithme peut être écrit :
AcquerirGommeEtCrayon ();
Dessiner
();
RendreGommeEtCrayon (); |
Si le mécanisme d'acquisition ne peut acquérir qu'un élément à la fois, l'algorithme doit être écrit :
AcquerirGomme ();
AcquerirCrayon ();
Dessiner ();
RendreCrayon ();
RendreGomme (); |
Considérons deux processus ayant les séquences de code suivantes :
AcquerirGomme (); {1}
AcquerirCrayon (); {2}
Dessiner ();
RendreCrayon ();
RendreGomme (); |
AcquerirCrayon (); {1'}
AcquerirGomme (); {2'}
Dessiner ();
RendreCrayon ();
RendreGomme (); |
Une situation d'interblocage est prévisible si les instructions se déroulent dans l'ordre
{1} {1'} {2}, ou {1} {1'} {2'}.
Il est donc nécessaire que les deux acquisitions soient effectuées de façon atomique.
Même dans ce cas, il importe que le mécanisme d'acquisition ne réserve aucune des ressources s'il ne peut les réserver toutes simultanément.
Mais même dans ce cas, des problème subsistent.
Considérons en effet qu'un processus ait besoin d'un crayon pour effectuer une partie de son activité, puis aussi d'une gomme pour continuer.
Une analyse superficielle conduirait à l'algorithme :
AcquerirCrayon ();
Dessiner
();
AcquerirGomme ();
DessinerEtEffacer ();
RendreCrayonEtGomme (); |
On voit bien qu'il ne s'agit que d'une variante de la
solution précédente
avec les mêmes risques d'interblocage.
Cependant, AcquerirCrayonEtGomme() dès le début alors qu'on n'en a pas l'utilité immédiatement peut diminuer grandement l'efficacité de l'ensemble.
Une solution, très altruiste, pourrait être :
AcquerirCrayon
();
Dessiner
();
RendreCrayon
(); {3}
AcquerirCrayonEtGomme (); {4}
DessinerEtEffacer ();
RendreCrayonEtGomme (); |
Elle a pour inconvénient majeur de permettre que l'activité puisse être interrompue, éventuellement pendant longtemps, entre {3} et {4}.
L'interblocage peut être totalement fortuit si les acquisitions de ressources sont effectuées à l'insu de l'utilisateur.
Considérons par exemple qu'une bibliothèque comporte les fonctions , en style C++ :
void Redessiner ()
{
AcquerirGomme ();
DessinerEnEffacant();
RendreGomme
();
} // Redessiner() |
void Remodeler ()
{
AcquerirCrayon ();
EffacerEnDessinant();
RendreCrayon ();
} // Redessiner() |
Si les sources ne sont pas disponibles et si la documentation fournie n'est pas explicite, les deux processus suivants pourront de bonne fois se retrouver dans une situation d'interblocage :
AcquerirCrayon ();
Redessiner ();
RendreCrayon (); |
AcquerirGomme();
Remodeler ();
RendreGomme (); |
Afin d'éviter de telles situations, il importe de rendre visible ou de documenter les réservations de ressources critiques.
Lecteurs/Rédacteurs
Le principe des lecteurs/rédacteurs
Le principe de ce problème est le suivant : il existe une information (il faut imaginer ici une information volumineuse, ne se limitant pas à une variable élémentaire) que certains processus consultent (les lecteurs) et que d'autres mettent à jour (les rédacteurs) : c'est la ressource critique.
L'activité des lecteurs ne modifie pas l'information.
Il s'ensuit que plusieurs lecteurs peuvent être autorisés à lire simultanément.
En revanche, les rédacteurs modifient l'information (ils "écrivent") dont la cohérence ne peut être assurée que s'ils y accèdent seuls (aucun autre rédacteur et aucun lecteur).
Que se passerait-il en effet si deux processus modifiaient chacun de leur coté des parties de l'information ! Un mécanisme d'exclusion mutuelle doit donc être mis en place.
A ce modèle correspondent de nombreuses situations, tant dans des applications classiques (maintenance de bases de données, par exemple) qu'au sein de nombreuses activités d'un système d'exploitation : pensons par exemple à la gestion des tampons des fichiers d'Unix ou à la table des i-noeuds, accédés simultanément par de nombreux processus.
Appelons Lire() et Ecrire() les activités respectives des lecteurs et des rédacteurs.
On peut les considérer comme des primitives, dans le sens qu'elles sont ininterruptibles (atomiques) par les différents acteurs : un lecteur en cours de lecture ne peut être interrompu par un rédacteur qui modifierait l'information, avant que le lecteur ne reprenne là où il en était.
De même il est impensable qu'un rédacteur soit interrompu, par exemple par un autre rédacteur, puis qu'il reprenne la main pour terminer sa modification.
Bien entendu, au niveau du processeur, et du système d'exploitation, ces activités peuvent parfaitement être interruptibles, par exemple dans le cadre d'un système multi-tâches, mais cela ne doit pas altérer le comportement de l'ensemble des acteurs.
Schéma général de résolution
Il est supposé que le nombre de lecteurs et/ou de rédacteurs peut être quelconque et n'est pas limité par l'algorithme.
La résolution de ce problème s'exprime sous la forme des algorithmes suivants :
Lecteur
si (Nombre de rédacteurs actifs == 0)
alors
Lire();
finsi; |
Rédacteur
Si (Nombre de lecteurs actifs == 0 et
Nombre de rédacteurs actifs == 0)
alors
Ecrire();
finsi; |
Ces algorithmes ne peuvent être trancrits simplement dans les langages de programmation habituels.
En effet, plusieurs difficultés doivent être résolues :
-
que fait le lecteur si la condition n'est pas satisfaite ?
Exceptionnellement, il doit pouvoir sauter jusqu'au "finsi".
En général cependant, il attend jusqu'à ce que la condition soit satisfaite.
L'
attente active
étant exclue, le processus passe dans l'état bloqué.
Il faut un mécanisme qui le réveille, qui ne peut être activé que par un autre processus;
-
le nombre de lecteurs doit être incrémenté, le test et l'incrémentation devant être effectués de façon atomique.
En effet, si une interruption est possible entre l'évaluation du test et l'incrémentation du compteur, un rédacteur peut se glisser dans l'intervalle, tester le nombre de lecteurs actifs, le trouver nul et donc commencer à écrire.
Le problème est cependant plus délicat, puisque, si le test est bloquant, l'atomicité avec l'incrémentation n'est plus possible.
Il faut donc un dispositif permettant, si le test est vrai, d'enchaîner de façon atomique l'incrémentation.
Si le test est faux, le processus est bloqué.
Lorsqu'il est réveillé, le test est évalué à nouveau, et, s'il est vrai, l'incrémentation est enchaînée.
Dans le cas contraire, le processus se bloque de nouveau et ainsi de suite.
On pourrait penser que, si le lecteur a été réveillé, c'est que la condition est vraie.
Cependant, certaines implémentations de ce mécanisme peuvent réveiller plusieurs processus, dont un seul sera satisfait;
-
comme le lecteur, le rédacteur est en général bloqué si la condition n'est pas satisfaite.
Dans ce cas ce sont les deux évaluations et l'incrémentation qui doivent être atomiques;
-
le "finsi" du rédacteur n'est pas trivial, puisqu'il doit réveiller un lecteur ou un rédacteur qui serait bloqué.
Qui réveiller d'abord si des lecteurs et des rédacteurs sont bloqués ? C'est au développeur de fixer la politique de choix qui résout ce problème;
-
le "finsi" du lecteur est encore plus complexe.
En principe, il ne devrait pas réveiller de lecteur puisque, la lecture pouvant être simultanée par plusieurs lecteurs, ils n'ont aucune raison d'être bloqués.
En revanche, un lecteur ne peut réveiller un rédacteur que s'il était le dernier.
Politiques d'élection de processus
Il faut tout d'abord remarquer que l'algorithme ci-dessus présente un risque de famine : s'il y a toujours un lecteur qui commence à lire avant que les autres terminent, un rédacteur ne pourra jamais accéder à l'information.
La seule solution, dite solution équitable, consiste à ce que les processus soient servis dans leur ordre d'arrivée.
Cela revient à exprimer de nouvelles conditions d'entrée en section critique :
Lecteur
si (Nombre de rédacteurs actifs ==
0
et
Nombre de rédacteurs en attente == 0)
alors
Lire();
finsi; |
Rédacteur
Si (Nombre de lecteurs actifs
== 0
et
Nombre de rédacteurs actifs
== 0
et
Nombre de lecteurs en attente ==
0
et
Nombre de rédacteurs en attente == 0)
alors
Ecrire();
finsi; |
Dans cette solution, on remarque qu'un lecteur ne peut pas toujours commencer à lire même si d'autres lecteurs sont actifs.
Comme précédemment, le finsi du lecteur ne pourra pas réveiller de lecteur, puisque s'il y a des lecteurs bloqués, c'est qu'ils attendent le passage d'un rédacteur arrivé avant eux.
En revanche, il devra chercher à réveiller le rédacteur arrivé le premier.
Le finsi du rédacteur réveillera le processus bloqué le plus ancien, lecteur ou rédacteur.
Si c'est un lecteur, cela ne coûte rien de déveiller tous les autres lecteurs en attente, puisqu'ils peuvent se dérouler en parallèle, donc sans pénaliser les autres rédacteurs.
L'équité, si elle part d'un "bon sentiment", n'est peut-etre pas toujours souhaitable :
-
si des rédacteurs sont en attente, il est peut-être inutile de laisser des lecteurs commencer à lire, sachant que les informations qu'ils lisent sont peut-être obsolètes.
Il est alors préférable de donner la priorité aux rédacteurs.
Dans certains cas, on peut même imaginer que, si tous les rédacteurs mettent à jour la même information, il est inutile de les faire passer dans l'ordre chronologique, il suffit de donner la priorité au dernier et de "renvoyer" tous les autres;
-
si "l'indice de satisfaction" se mesure au nombre de processus servis et à la rapidité de service, il faut donner la priorité aux lecteurs;
-
les priorités peuvent évoluer dans le temps : il est commercialement plus important de favoriser l'entrée de clients dans un magasin que de faciliter leur sortie.
Cependant, en cas de saturation, il faut inverser la priorité.
De même dans une banque ayant un seul sas d'entrée/sortie, permettant une entrée à la fois et N sorties simultanées, il n'est pas souhaitable de laisser le client attendre à l'extérieur, mais il faut bien que les clients sortent de temps en temps !
Producteurs/Consommateurs
Dans ce modèle, il existe des entités (processus, tâches, threads) qui "produisent" de l'information et la déposent sur un support, ce sont les producteurs, et d'autres qui la retirent de ce support, ce sont les consommateurs.
A l'opposé du modèle des Lecteurs/Rédacteurs étudié ci-dessus, lorsque l'information est lue, elle est consommée, ce qui signifie qu'elle n'est plus disponible.
De ce fait, il doit toujours y avoir une opération de production qui précède une opération de consommation, ce qui implique une synchronisation entre les producteurs et les consommateurs.
Habituellement, les deux primitives qui représentent ces actions sont appelées Deposer() et Retirer().
Rendez-vous d'Ada
Le mécanisme des Rendez-vous d'Ada permet une implémentation un peu particulière du modèle des Producteurs/Consommateurs.
Considérons le schéma suivant :
-- Tâche Client
Message : T_Message;
Creer (Message);
Serveur.Deposer (Message) |
-- Tâche Serveur
MessageLocal : T_Message;
accept Deposer (Missive : in T_Message)
begin
MessageLocal := Missive;
end Deposer; |
Le serveur joue le rôle de consommateur : il est susceptible de consommer tous les messages en provenance de n'importe quels clients (les producteurs).
On a déjà noté la forte dissymétrie entre les protagonistes : les producteurs connaissent le consommateur, celui-ci les ignore.
S'il y a plusieurs consommateurs possibles (plusieurs serveurs), le producteur doit choisir a priori quel est celui qui va consommer le message.
Le premier inconvénient de cette solution est donc l'impossibilité qu'a le Rendez-vous d'Ada de faire rencontrer n'importe quel producteur avec n'importe quel consommateur.
Le second inconvénient est que l'échange d'information est tout à fait synchrone : elle nécessite la présence physique des deux protagonistes (d'où le nom de Rendez-vous !)
Le mécanisme est full-duplex : deux protagonistes peuvent être à la fois producteur et consommateur, et s'échanger de l'information d'un seul point de Rendez-vous, sans que les informations se mélangent.
Boîte aux lettres
La boîte aux lettres (BAL) est un média qui peut contenir un seul message.
Elle est soit pleine, soit vide.
N'importe quel producteur peut y déposer un message, n'importe quel consommateur peut le retirer.
Le mécanisme est half-duplex : une seule BAL ne permet pas l'échange de correspondance : si une des entités est à la fois producteur et consommateur, elle peut retirer le message qu'elle a déposé elle-même.
Le dépot et le retrait sont chacun soumis à une condition :
Si BAL.Vide()
alors
BAL.Deposer (Message); |
Si non BAL.Vide()
alors
Message = BAL.Retirer (); |
Ce mécanisme a l'intérêt de découpler partiellement les producteurs et les consommateurs : l'échange se fait de façon asynchrone.
Cependant, la souplesse du mécanisme est faible et il devient fréquemment bloquant.
Tampons finis
C'est l'extension logique de la BAL : une succession de BAL.
Ce tampon peut être géré de multiples façons.
La plus naturelle est la file FIFO (First In First Out), mais on peut aussi envisager une pile, ou une
file de priorité
: à chaque message déposé est attribué une "priorité", et la file les restitue dans l'ordre des priortiés décroissantes
Le dépot et le retrait sont chacun soumis
à une condition :
Si non Tampon.Plein()
alors
Tampon.Deposer (Message); |
Si non Tampon.Vide()
alors
Message = Tampon.Retirer (); |
De nombreux mécanismes permettent d'implémenter les tampons finis : objets protégés en Ada, piles, files et files prioritaires en C++ et Java, pipes,
sockets,
files de message
et bien d'autres dispositifs offerts par les systèmes d'exploitation.
Dernière mise à jour : 15/10/2001