Page préc.
Exemple de coopération entre processus
Fin de page Page suiv.
Attente active

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 fataledeadlock) 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 :

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 :

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.


Page préc.
Exemple de coopération entre processus
Début de page Page suiv.
Attente active
Dernière mise à jour : 15/10/2001