next up previous index
Next: Gestion de la mémoire Up: Gestion des Processus. Previous: L'ordonnancement de processus.   Index

Subsections

La synchronisation (communication) de processus.

La mémoire est partagée entre plusieurs processus (exemple BD), il y a donc des risques de comportements bizarres.

Soient les deux processus suivant et la variable globale compte initialisée à 10.

Processus A
var aux : integer

begin
aux := compte;
aux := aux + 10;
compte := aux;
end.
Processus B
var aux : integer

begin
aux := compte;
aux := aux - 5;
compte := aux;
end.

La figure 2.3 représente le graphe des comportements du ``programme'' constitué des deux processus. Chaque n\oe ud contient les valeurs des trois variables, et les arcs représentent les instructions.


\begin{automate}[ct]{800}{450}{Les trois variables.
}{0.6}(45,5)
\etat[i]{400}{4...
...\trans[acw]{quinze}{vingtun}{B3}
\trans{dixhuit}{vingtun}{A3}
\par\end{automate}

Le résultat dépend de l'entrelacement des actions, donc de l'ordonnancement des processus. Il y a donc un besoin de contrôler le déroulement d'un processus.


Le problème de la section critique.

$N$ processus exécutent le programme suivant :


debut
tant que vrai faire debut
        "entrer en section critique"
        Section Critique
        "sortir de section critique"
        Section Non Critique
        fin
fin

Les objectifs :

Les solutions logicielles.

Première idée pour 2 processus: un feu vert/rouge.
le feu est initialisé à vert.

debut
tant que vrai faire debut
        tant que feu = rouge faire rien;
        feu := rouge;
        Section Critique;
        feu := vert;
        Section Non Critique
        fin
fin
Les 2 processus peuvent être ensemble en S.C

Deuxième idée : Deux drapeaux
Flag[i] signifie que Pi veut entrer et les drapeaux sont initialisés à faux.

debut
tant que vrai faire debut
        Flag[i] := true;
        tant que Flag[j] faire rien;
        Section Critique;
        Flag[i] := false;
        Section Non Critique
        fin
fin

Les 2 processus ne peuvent pas être ensemble en S.C

Il n'y a pas d'attente s'il n'y a pas de compétition.

Il y a possibilité d'attente infinie (famine).

la preuve est faite par la construction du graphe du comportement des deux processus.

Troisième idée : une variable qui indique "A qui le tour".

debut
tant que vrai faire debut
        tant que tour = j faire rien;
        Section Critique;
        tour := j ;
        Section Non Critique
        fin
fin

2 processus ne peuvent pas être ensemble en S.C

Il n'y a pas d'attente infinie.

Il peut y avoir attente s'il n'y a pas de compétition. C'est un algorithme d'alternance (jeton).

Algorithme de Peterson pour 2 processus.
Combiner les deuxième et troisième idées.

debut
tant que vrai faire debut
        Flag[i] := true;
        tour := i ;
        tant que (Flag[j] et tour = i) faire rien;
        Section Critique;
        Flag[i] := false;
        Section Non Critique
        fin
fin
La preuve sera faite en TD

Section critique pour N processus.
Solutions complexes et difficiles à prouver.

Le SE doit fournir des primitives pour synchroniser des processus.

Les primitives matérielles de synchronisation.

Les solutions logicielles font les hypothèses suivantes :

Le problème devient plus simple si on les change.

Le défaut commun à ces solutions est l'attente active (gaspillage de l'UC).

Le SE doit fournir des appels systèmes pour endormir et réveiller des processus.

Les appels systèmes de synchronisation.

On suppose l'existence de deux appels systèmes: d'une part block qui permet à un processus de se mettre en état d'attente; d'autre part wakeup(P) qui permet de mettre l'état du processus P à prêt.

Avec ces hypothèses, il est assez facile d'éliminer l'attente active. Il suffit de remplacer faire rien par block, puis ajouter en fin de la phase de sortie une boucle pour réveiller tous les processus "en attente" grâce à un wakeup(P)

Cette solution est moyennement satisfaisante, car en fait un seul processus doit être réveillé, les autres feront en effet un nouveau block.

Les sémaphores : Dijkstra - 1965

L'idée est de combiner les appels block et wakeup avec les procédures wait et signal.

Définition

Une structure de données

type semaphore = (n : entier; l : liste de processus);
manipulée uniquement par les actions atomiques wait et signal.

procedure wait(var S : semaphore)       procedure signal(var S : semaphore)
debut                                   debut
S.n := S.n - 1;                         S.n := S.n + 1;
si (S.n < 0) alors debut                si (S.n <= 0) alors debut
        ajouter(moi,S.l);                       enlever(P,S.l);
        block;                                  wakeup(P);
        fin                                     fin
fin                                     fin

Une solution au problème de la section critique

Une solution équitable pour N processus au problème de la section critique avec un sémaphore mutex initialisé à (1,vide).

debut
tant que vrai faire debut
        wait(mutex);
        Section Critique;
        signal(mutex);
        Section Non Critique
        fin
fin
La solution est équitable si la liste de processus est une FIFO.

Implémentation

Les sémaphores peuvent être implémentés de la façon suivante :

Utilisation

Autres solutions

Il existe des solutions équivalentes (en terme de puissance de synchronisation) pour la synchronisation de processus.

Les messages

Le SE propose les primitives

Les S.E. conçus autour d'un micro-noyau utilise principalement cette technique.

Les messages permettent de synchroniser des processus distants.

Il existe des variantes en fonction des sémantiques :

Une solution au problème de la section critique.

utilise un processus contrôleur qui délivre les autorisations d'entrée en SC.


processus Pi
debut
tant que vrai faire debut
        emettre(demande,controleur);
        recevoir(aquittement,controleur);
        Section Critique;
        emettre(fin,controleur);
        Section Non Critique
        fin
fin

processus Controleur
debut
tant que vrai faire
        cas de 
        recevoir(demande,P1); emettre(aquittement,P1); recevoir(fin,P1);
        ou 
        recevoir(demande,P2); emettre(aquittement,P2); recevoir(fin,P2);
        ou 
        ...
        ou 
        recevoir(demande,Pn); emettre(aquittement,Pn); recevoir(fin,Pn);
        sac
fin

Les structures précédentes (sémaphores et messages) sont puissantes, mais encore difficiles d'utilisation. Les suivantes sont plus simples d'emploi.

Les régions critiques conditionnelles

Une variable partagée est déclarée par :


var v : shared T;

et ne peut être utilisée que de la façon suivante :


region v when B do S;

Une solution au problème de la section critique

Les variables manipulées dans la section critique sont rassemblées dans une structure v déclarée partagée.


debut
tant que vrai faire debut
        region v when true do
               Section Critique;
        Section Non Critique
        fin
fin

Le risque, pour l'utilisateur, d'erreur d'entrelacement est nettement diminué.

Les moniteurs

Définition : Un moniteur comprend des variables, des conditions, des procédures et un code d'initialisation. Seules les procédures peuvent être manipulées par les processus, et le mécanisme du moniteur garantit l'exécution de chaque procédure en exclusion mutuelle.


Syntaxe d'un moniteur


type nom du moniteur = monitor
déclarations de variables
déclarations de conditions
procedure entry P1(...)
begin ...end;

procedure entry Pn(...)
begin ...end;
begin
code d'initialisation
end.

La synchronisation des processus est obtenu à l'aide des procédures wait et signal appliquées sur les variables de type condition. L'action X.signal provoque le réveil de tous les processus qui ont auparavant effectué X.wait.

Une solution au problème de la section critique

type SectionCritique = monitor
token : booleen;
sc : condition
procedure entry EntreeSC
begin
while not token do sc.wait;
token := false;
end;
procedure entry SortieSC
begin
token := true;
sc.signal;
end;
begin
token := true
end.


shared var SC = SectionCritique

Code des processus

begin
while true do begin
code de la section non critique
SC.EntreeSC;
code de la section critique
SC.SortieSC
end
end.

Équivalences

En fait, tous ces mécanismes sont équivalents au sens ou n'importe lequel permet d'implémenter tous les autres.

Par exemple, il est possible d'implémenter une région critique conditionnelle à l'aide des sémaphores mutex(1,vide), delai1(0,vide) et delai2(0,vide), et des entiers compteur1 et compteur2 initialisés à 0.


debut
wait(mutex);
tant que non B faire debut
        compteur1 := compteur1 + 1;
        si compteur2 > 0 alors
                signal(delai2);
        sinon
                signal(mutex);
        wait(delai1);
        compteur1 := compteur1 - 1;
        compteur2 := compteur2 + 1;
        si compteur1 > 0 alors
                signal(delai1);
        sinon
                signal(delai2);
        wait(delai2);
        compteur2 := compteur2 - 1;
        fin;
S;
si compteur1 > 0 alors
        signal(delai1);
sinon
        si compteur2 > 0 alors
                signal(delai2);
        sinon
                signal(mutex);
fin

Autres problèmes classiques de synchronisation

Il existe plusieurs problèmes de synchronisation de processus qui permettent de valider, et de comparer les facilités d'utilisation des différents mécanismes.

Le Producteur/Consommateur avec buffer limité

Un producteur dépose des messages dans un buffer, duquel un consommateur les retire. La synchronisation doit satisfaire les points suivants :

Les lecteurs/rédacteurs

Un objet est partagé par des lecteurs qui veulent connaître sa valeur, et des rédacteurs qui peuvent modifier sa valeur.

Les philosophes mangeurs de spaghettis

N philosophes alternativement pensent et mangent. Pour manger, ils disposent d'une table circulaire ayant N assiettes et N fourchettes.

Il n'existe pas de contrôle possible pour ce problème sans faire d'hypothèses supplémentaires. (priorité, accès limité à N-1 à la table).

Remarque

Le cours détaille le problème de la section critique et les sémaphores. N'importe quel autre problème, et n'importe quel autre mécanisme auraient permis la présentation de ce chapitre.


next up previous index
Next: Gestion de la mémoire Up: Gestion des Processus. Previous: L'ordonnancement de processus.   Index
Alain GRIFFAULT
2000-12-22