Synchronisation de Processus

1
Problématique 2
 Dans un système multiprogrammée les processus/Les threads
peuvent interagir (coopérer) avec d’autres processus/threads
pour progresser.
 L’exécution d’un processus/thread peut être affecté par
l’exécution des autres processus/threads et inversement.
 Pour interagir (coopérer) il y a besoin de communication
assurée généralement par des données partagées (MC, fichiers)
 Les accès concurrents (simultanés) à des données partagées
peuvent conduire à des incohérences dans les résultats obtenus.
 Quand plusieurs Processus/threads s’exécutent en parallèle,
nous ne pouvons pas faire d’hypothèses sur leurs vitesses
d’exécution, ni leur entrelacements.
Exemple illustratif 3

 Soient deux processus/threads qui exécutent

simultanément le même code suivant: b=a;
b++;
a=b;
 Notons que a est une variable partagée entre les deux
entités communicantes initialisée à 0 et b une variable
locale à chacune d’elles. Quel pourrait être le résultat
dans a?
 Sachant que aucune hypothèse n’est connu sur les
vitesses d’exécution des processus et que ces derniers
peuvent être interrompus à n’importe quel moment.
Exemple illustratif (suite)
Deux scénarios possibles:
 (1) les processus s’exécutent itérativement et dans ce cas
le résultat dans b est égal à 2.
P1
 (2) b=a interruption P2
b=a
b++
b++ a=b
a=b

P1 est interrompu après la lecture de a, P2 s’exécute après,

quand P1 reprend l’exécution il ne tiendra pas compte de la
modification effectuée par P1.
4
 Notion de ressource
 Une ressource désigne toute entité nécessaire à
l’exécution d’un processus.
 Ressource matérielle (processeur, périphérique,…)
 Ressource logicielle (variable,…)

 Une ressource est caractérisée :

1. par un état : libre /occupée
2. par son nombre de points d'accès : nombre de
processus pouvant l'utiliser en même temps.
5
Notion de ressource
 Utilisation d'une ressource par un processus passe
par trois étapes :
1. Allocation
2. Utilisation
3. Restitution

 Contrainte : Les phases d'allocation et de restitution

doivent assurer que la ressource soit utilisée
conformément à son nombre de points d'accès

6
 Ressource et Section Critique
 Une ressource est à un seul point d'accès
est dite critique

 La partie de programme dans laquelle se font

les accès à une ressource critique s'appelle une
section critique. Lorsqu’un processus
manipule une donnée (ou ressource) partagée
avec d’autres, il se trouve dans une section
critique (associée à cette ressource critique)
7
 Le problème de la section critique
Le problème posé est l’accès simultané à une ressource
critique
Exemple : Accès à une base de données.
 Plusieurs processus peuvent lire simultanément,
 mais quand un processus fait une mise à jour, tous les
autres accès doivent être interdits.
 l'accès à cette section critique doit se faire en exclusion
mutuelle, ce qui consiste à rendre atomique
(indivisible) la séquence d'instructions de la section
8 critique.
 Le problème de la section critique
 Le problème de la section critique est de trouver un
algorithme d’exclusion mutuelle de threads dans
l’exécution de leur SC afin que le résultat de leurs
actions ne dépendent pas de l’ordre
d’entrelacement de leur exécution
(avec un ou plusieurs processeurs).

 L’exécution des SCs doit être mutuellement

exclusive et atomique: à tout instant, un seul
processus peut exécuter une SC pour une donnée
(même lorsqu’il y a plusieurs UCT)
9
 Structure d’un programme type
 Le programme est présenté comme boucle infinie: while(true)
 Chaque processus doit donc demander une permission avant
d’entrer dans une SC
 La section de code qui effectue cette requête est la section
d’entrée
 La section critique est normalement suivie d’une section de sortie
 Le code qui reste est la section non-critique

while (true) {
Section d’entrée
Section critique atomique
Section de sortie
Section non critique
10 }
 4 Conditions d'accès à une SC
 Exclusion Mutuelle :Deux processus ne peuvent être
ensemble en section critique,
 Progression Un processus bloqué en dehors de sa section
critique ne doit pas empêcher un autre d'entrer dans la sienne
(pas d’Interblocage)
 Attente bornée Si deux processus attendent l'entrée dans
leurs sections critiques respectives, le choix doit se faire en un
temps fini, (pas de famine).
 Aucune hypothèse Pas d'hypothèses sur les vitesses
relatives des processus (indépendance vis à vis du matériel).
Tous les processus doivent avoir la même chance d'entrer en
11
section critique,
 Trois types de solutions
 Solutions fournies par le matériel : s’appuient sur
l’existence de certaines instructions spéciales (du
processeur)

 Solutions par logiciel : des algorithmes qui n’utilisent

pas d’instructions spéciales.

 Solutions fournies pas le SE : procurent certains appels

du système au programmeur

12
 Solutions d’exclusion mutuelles
avec attente active.
Dans ce contexte on trouve les solutions
suivantes:

1. Le masquage des interruptions

2. Les variables de verrouillage
3. L’alternance stricte
4. La solution de Peterson

13
 Masquage des interruptions
 Avant d’entrer dans une section critique, le processus masque les
interruptions.
 Il les restaure à la fin de la section critique.
 Il ne peut être alors suspendu durant l’exécution de la section
critique.
Process Pi:
Répéter
Protocole d’entrée en SC = désarmer les Interruptions
Section critique ( SC In-interruptible, donc
indivisible car pas de commutation de contexte)
Protocole de sortie de SC = armer les Interruptions
Section restante
Fin Répéter

14
Masquage des interruptions
Problèmes
 Solution dangereuse : si le processus, ne restaure pas les
interruptions à la sortie de la section critique, ce serait la fin
du système.
 Elle n’assure pas l’exclusion mutuelle, si la machine est
multiprocesseurs (le masquage des interruptions concerne
uniquement le processeur qui a demandé l’interdiction). Les
autres processus exécutés par un autre processeur pourront
donc accéder aux objets partagés.
 Cette technique parfois utilisée et, est réservée aux
systèmes d’exploitation
15
 Attente active et verrouillage
 Utiliser une variable partagée verrou, unique, initialisée à 0.
 Pour rentrer en section critique, un processus doit tester la valeur
du verrou.
 Si verrou = 0, le processus met le verrou à 1 puis exécute
sa section critique.
 A la fin de la section critique , il remet le verrou à 0.
 Sinon, il attend (attente active ) que le verrou devienne égal à
0 : while(verrou !=0) ;

16
 Attente active et verrouillage

17
 Attente active et verrouillage
Problèmes
 Elle n’assure pas l’exclusion mutuelle :
 Supposons qu’un processus est suspendu juste après avoir lu la valeur du
verrou qui est égal à 0.
 Ensuite, un autre processus est élu. Ce dernier teste le verrou qui est
toujours égal à 0, met le verrou à 1 et entre dans sa section
critique.
 Ce processus est suspendu avant de quitter la section critique. Le
premier processus est alors réactivé, il entre dans sa section critique et
met le verrou à 1.
 Les deux processus sont en même temps en section critique

 L’attente active surcharge le CPU

18
 Instruction indivisible:
Test-And-Set (TAS)
 Instruction disponible sur presque toutes les machines
(mais on n'a pas toujours le droit de l'utiliser). Quand
X vaut 1, cela veut dire que la ressource est prise.

 Utilisation (X est une variable partagée par plusieurs

processus, initialisée à zéro) :

 Inconvénient: Attente active

19
 Instruction indivisible: Test-and-Set
(TAS)

20
 Attente active avec alternance
 Utiliser une variable tour qui mémorise le tour
du processus qui doit entrer en section
critique. La variable tour est initialisée à 0.

21
 Attente active avec alternance
Processus P0 Processus P1
while (1) while (1)
{ /*attente active*/ { /*attente active*/
while (tour !=0) ; while (tour !=1) ;
section_critique_P0(); section_critique_P1();
tour = 1 ; tour = 0 ;
…. ….
} }

 Un processus peut être bloqué par un

processus qui n’est pas en section
critique.
22
 Attente active consomme du temps CPU.
 Solution de Peterson
 Cette solution se base sur deux fonctions entrer_region et
quitter_region.
 Chaque processus doit, avant d’entrer dans sa section critique
appeler la fonction entrer_region en lui fournissant en
paramètre son numéro de processus.
 Cet appel le fera attendre si nécessaire jusqu’à ce qu’il n’y ait
plus de risque.
 A la fin de la section critique, il doit appeler quitter_region
pour indiquer qu’il quitte sa section critique et pour autoriser
l’accès aux autres processus.
23
 Solution de Peterson

24
 Solutions d’exclusion mutuelle
sans attente active.

Dans ce contexte on considère les méthodes

suivantes
1. Les primitives systèmes sleep et wakeup
2. Les sémaphores
3. Les moniteurs

25
 Les primitives SLEEP et WAKEUP

 SLEEP est un appel système qui suspend l’appelant en

attendant qu’un autre le réveille.
 WAKEUP(process) : est un appel système qui réveille le
processus process.
 Un processus H qui veut entrer dans sa section critique
est suspendu si un autre processus B est déjà dans sa
section critique.
 Le processus H sera réveillé par le processus B, lorsqu’il
quitte la section critique.

26
 Les primitives SLEEP et WAKEUP

27
 Les primitives SLEEP et WAKEUP

28
 Mise en oueuvre (Signaux Unix)
 Dans le système Unix, les appels système qui assurent à peu
près, les mêmes fonctions que les primitives SLEEP et
WAKEUP sont :
 pause( ) : suspend le processus appelant jusqu’à réception d’un
signal.
 kill(pid, SIGCONT): envoie le signal SIGCONT au processus
pid. L’émission d’un signal est possible si l’une des deux
conditions est vérifiée :
1. L’émetteur et le destinataire du signal appartiennent au même
propriétaire
2. L’émetteur du signal est le super-utilisateur.
29
 Sémaphores
 Introduit par Dijkstra en 1965 pour résoudre le problème
d’exclusion mutuelle.
 Permettent l’utilisation de m ressources identiques (exemple
imprimantes) par n processus.
 Un sémaphore est une structure contenant deux champs :
Struct
{
valeur : entier ;
en_attente :
file de processus
}

30
 Sémaphores: Définition(1)
Un sémaphore est une variable globale protégée, c’est
à dire on peut y accéder qu’au moyen des trois
procédures :
 I(S, x) : initialiser le sémaphore S à une certaine
valeur x;
 P(S) ; Peut -on passer ?/peut-on continuer?
 V(S) ; libérer?/vas y?
P et V sont des primitives plutôt que des procédures
car elles sont non interruptibles possible sur
31
monoprocesseur par masquage d'Interruption.
 Sémaphores: définition (2)
 Un sémaphore binaire est un sémaphore dont la
valeur peut prendre que deux valeurs positives
possibles : en générale 1 et 0.

 Un sémaphore de comptage : la valeur peut

prendre plus de deux valeurs positives possibles.
Il est utile pour allouer une ressource parmi
plusieurs exemplaires identiques : la valeur est
initialisée avec le nombre de ressources.
32
 Sémaphores: Réalisations
logicielles
 I(S, x) {[Link] =x ; }

 P(S) // [Link] est tjs modifié par P(S)

{ S. valeur =[Link] -1 ;
Si S. valeur < 0 alors bloquer le
processus en fin den S. valeur _attente ;
}

 V(S) /*[Link] est tjs modifié par V(S)*/

{ S. valeur :=S. valeur + 1 ;
Si S. valeur <= 0 alors débloquer le
processus en tête de S.en_attente ; }
33
 Sémaphores: une deuxième
implantation logicielle
 Traduction directe de la spécification fonctionnelle:
 P(S) {
Si [Link] > 0 alors [Link] =[Link]-1 ;
Sinon bloquer le processus en fin de
S.en_attente ;
}
 V(S) {
Si S.en_attente non-vide alors débloquer le
processus en tête de S.en_attente ;
sinon [Link] :=[Link] +1 ;}

34
 Problème de l’exclusion mutuelle
Initialiser S à 1, et la procédure d’entrée est P(S), et la
procédure de sortie estV(S)
Var mutex : sémaphore init à 1
Processus Pi
Début
...
P(mutex)
SC
V(mutex)
...
35 Fin
 Problème de l’exclusion mutuelle
 L’initialisation dépend du nombre de processus
pouvant effectuer en même temps une même "
section critique " :
 Exemple: m, si on a m imprimantes identiques;
 Cette implémentation donne à chaque fois dans
[Link] le nombre de ressources libres :
 lorsque [Link] est négative, sa valeur absolue
donne le nombre de processus dans la file.

36
 Problème du
producteur/consommateur
 La solution du problème au moyen des sémaphores nécessite
deux sémaphores.
 Le premier, nommé Plein, compte le nombre
d’emplacements occupés. Il est initialisé à 0.
 Il sert à bloquer/débloquer le consommateur (P(Plein) et
V(Plein)).
 Le second, nommé Vide, compte le nombre d’emplacements
Vide. Il est initialisé à N (N est la taille du tampon).
 Il sert à bloquer/débloquer le producteur (P(Vide) et
V(Vide)).
37
 Problème du
producteur/consommateur
 tampon [N];
Consommateur :
Producteur :
{ int ic =0;
{ int ip =0;
Répéter
Répeter
{ P(Plein);
{ P(Vide) ;
consommer(tampon,ic);
produire(tampon, ip);
ic= Mod(ic+1, N);
ip = Mod(ip +1,N);
V(Vide);
V(Plein);
} tantque vrai
} tantque vrai
}
}38