Les modèles de coopération entre processus

Problèmes liés à la coopération entre processus

    Des problèmes peuvent survenir dans chacune de ces phases, entraînant un dysfonctionnement du système pouvant aller jusqu'à son blocage complet :

Interblocage

Attente indéfinie en section critique

Privation (ou famine)

Partage de ressources critiques

    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

    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

    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

    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

Rendez-vous d'Ada

    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

    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

    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.