Synchronisation de
Processus
Communication inter-processus
• Besoin de communication entre processus
Exemple :
• Ps1 | Ps2
Sortie Entrée
• Cat [Link] | grep mot
• Problèmes rencontrés :
Comment un processus fait pour passer des informations à un autre processus
Nécessité de s’assurer que deux processus ou plus ne rentre pas en conflit
Séquençage en présence de dépendance
A produit des données
B les imprime
B doit attendre que A terminela production
Chaque problématique étudié à part
Conditions de concurrence
• Processus coopérant pouvant partager parfois un espace de
stockage commun servant à la lecture / ecriture pour chacun
d’entre eux
• On parle donc de tâches coopératives
• Espace partagé
fichiers
ou mémoire commune
et ressources
Un exemple
• Deux processus exécutent M. X demande une
cette même procédure et réservation
partagent la même base de d’avion
données
Base de données
• Ils peuvent être interrompus dit que fauteuil
n’importe où A est disponible
• Le résultat de l ’exécution
concurrente de P1 et P2 Fauteuil A est
dépend de l`ordre de leur assigné à X et
entrelacement marqué occupé
Vue globale d’une exécution possible
P1 P2
Interruption
M. Leblanc demande une
réservation d’avion
M. Guy demande une
réservation d’avion
Base de données dit
que fauteuil 30A est
disponible Base de données dit
que fauteuil 30A est
disponible
Fauteuil 30A est Fauteuil 30A est
assigné à Leblanc et assigné à Guy et
marqué occupé marqué occupé
Deux opérations en parallèle sur une var a partagée
(b est privé à chaque processus)
P1 interruption P2
b=a
b=a
b++
a=b
b++
a=b
Supposons que a soit 0 au début
P1 travaille sur le vieux a donc le résultat final sera a=1.
Sera a=2 si les deux tâches sont exécutées l’une après l’autre
Autres exemples
Répertoire
de spoule
• Processus A lit in et en Processus B lit in et
stocke 7 dans sa variable ….. en stocke 7 dans sa
next-free-slot variable next-free-slot
• Interruption abc Out=4 B stocke son nom de
• A s’execute à nouveau fichier dans l’entrée 7
progc
examine next-free-slot et et actualise in à 8
met son fichier dans progn Interruption
l’entrée 7 écrasant le In=7
fichier du processus B
met à jour next-free-slot
et l’affecte à in
Démon d’impression ne s’appercevant de
rien
= B attendra indéfiniment une
impression qui ne se produira jamais
Section Critique
• Comment éviter les conditions concurrentes impliquant la mémoire, les
fichiers partagés ou tout autre élément partageable
• Trouver des solutions pour interdire à plusieurs processus de lire et
écrire simultanément des données partagées
• L’exclusion Mutuelle : une des méthodes permettant de s’assurer que si
un processus utilise un objet partagé . Les autres processus seront
exclus de cette activité.
• Région critique ou section critique : partie du programme où il y a
accès partagé
• Empêcher deux processus d’être dans leur sections critiques
Le problème de la section critique
• Lorsqu’un processus manipule une donnée (ou ressource) partagée,
nous disons qu’il se trouve dans une section critique (SC) (associée
à cette donnée)
• Le problème de la section critique est de trouver un algorithme
d`exclusion mutuelle de processus dans l`exécution de leur SCs
afin que le résultat de leurs actions ne dépendent pas de l’ordre
d’entrelacement de leur exécution
• L’exécution des sections critiques doit être mutuellement exclusive:
à tout instant, un seul processus peut exécuter une SC pour une var
donnée (même lorsqu’il y a plusieurs processeurs)
• Ceci peut être obtenu en plaçant des instructions spéciales dans les
sections d`entrée et sortie
• Pour simplifier, dorénavant nous faisons l’hypothèse qu’il n’y a
q’une seule SC dans un programme.
Structure du programme
• Chaque processus doit donc demander une permission avant d’entrer dans une
section critique (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 restante (SR): non-critique
repeat
section d’entrée
section critique
section de sortie
section restante
forever
Application
M. X demande une
réservation d’avion
Section d’entrée
Base de données dit que
fauteuil A est disponible
Section
critique Fauteuil A est assigné à X et
marqué occupé
Section de sortie
Critères nécessaires pour solutions
valides
• Exclusion Mutuelle
À tout instant, au plus un processus peut être dans une section
critique (SC) pour une variable donnée
• Non interférence:
Si un processus s’arrête dans sa section restante, ceci ne devrait
pas affecter les autres processus
• Mais on fait l ’hypothèse qu’un processus qui entre dans
une section critique, en sortira.
Critères nécessaires pour solutions
valides
• Progrès:
absence d`interblocage
si un processus demande d`entrer dans une section
critique à un moment où aucun autre processus en fait
requête, il devrait être en mesure d’y entrer
• Aussi nécessaire
Absence de famine: aucun processus éternellement
empêché d’atteindre sa SC
Difficile à obtenir, nous verrons…
Types de solutions
• Solutions par logiciel
• des algorithmes dont la validité ne s’appuie pas sur l’existence
d`instruction spéciales
• Solutions fournies par le matériel
• s’appuient sur l’existence de certaines instructions (du processeur)
spéciales
• Solutions fournies pas le SE
• procure certains appels du système au programmeur
• Toutes les solutions se basent sur l’atomicité de l’accès à la mémoire
centrale: une adresse de mémoire ne peut être affectée que par une
instruction à la fois, donc par un processus à la fois.
• Plus en général, toutes les solutions se basent sur l ’existence
d’instructions atomiques
Atomicité = indivisibilité
Solutions par logiciel
(pas pratiques, mais intéressantes pour comprendre le pb)
• Nous considérons d’abord 2 processus
Algorithmes 1 et 2 ne sont pas valides
• Montrent la difficulté du problème
Algorithme 3 est valide (algorithme de Peterson)
• Notation
Débutons avec 2 processus : P0 et P1
Lorsque nous discutons de la tâche Ti, Tj dénotera toujours
l’autre tâche (i != j)
Algorithme 1: processus se donnent mutuellement le tour
• La variable partagée turn est
initialisée à 0 ou 1
• La SC de Ti est exécutée ssi turn = i
• Ti est occupé à attendre si Tj est processus Ti:
dans SC.
repeat
• Fonctionne pour l’exclusion while(turn!=i);
mutuelle!
SC
• Mais critère du progrès n’est pas
satisfait car l’exécution des SCs turn = j;
doit strictement alterner SR Rien
forever faire
Ex 1: T0 possède une longue SR et T1 possède une courte SR. Si turn==0, T0 entre
dans sa SC et puis sa SR (turn==1). T1 entre dans sa SC et puis sa SR (turn==0), et
tente d’entrer dans sa SC: refusée! il doit attendre que T0 lui donne le tour.
initialisation de turn à 0 ou 1
processus T0: processus T1:
repeat repeat
while(turn!=0); while(turn!=1);
SC SC
turn = 1; turn = 0;
SR SR
Rien
forever forever
faire
Algorithme 1 vue globale
Ex 2: Généralisation à n processus: chaque fois, avant qu’un processus puisse rentrer
dans sa section critique, il lui faut attendre que tous les autres aient eu cette chance!
Algorithme 2 ou l’excès de
courtoisie...
• Une variable Booléenne par
processus: flag[0] et flag[1]
• Ti signale qu’il désire exécuter sa SC Thread Ti:
par: flag[i] =vrai
repeat
• Mais il n’entre pas si l’autre est aussi flag[i] = vrai;
intéressé!
while(flag[j]);
• Exclusion mutuelle ok
SC
• Progrès pas satisfait:
flag[i] = faux;
• Considérez la séquence: SR
T0: flag[0] = vrai
T1: flag[1] = vrai
forever rien faire
• Chaque processus attendra
indéfiniment pour exécuter sa
SC: on a un interblocage
Après vous, monsieur
Après vous, monsieur
Thread T0: Thread T1:
repeat repeat
flag[0] = vrai; flag[1] = vrai;
while(flag[1]); while(flag[0]);
SC SC
flag[0] = faux; flag[1] = faux;
SR SR
forever forever
Algorithme 2 vue globale
T0: flag[0] = vrai
T1: flag[1] = vrai
interblocage!
Algorithme 3 (dit de Peterson): bon!
combine les deux idées: flag[i]=intention d’entrer; turn=à qui le tour
• Initialisation: processus Ti:
• flag[0] = flag[1] = faux repeat
• turn = i ou j flag[i] = vrai;
// je veux entrer
• Désire d’exécuter SC est indiqué
par flag[i] = vrai turn = j;
// je donne une chance à l’autre
• flag[i] = faux à la section de sortie do while
(flag[j] && turn==j);
SC
flag[i] = faux;
SR
forever
Entrer ou attendre?
• processus Ti attend si:
• Tj veut entrer et c’est la chance à Tj
• flag[j]==vrai et turn==j
• Un processus Ti entre si:
• Tj ne veut pas entrer ou c’est la chance à Ti
• flag[j]==faux ou turn==i
• Pour entrer, un thread dépend de l’autre qu’il lui donne la
chance!
Thread T0: Thread T1:
repeat repeat
flag[0] = vrai; flag[1] = vrai;
// T0 veut entrer // T1 veut entrer
turn = 1; turn = 0;
// T0 donne une chance à T1 // T1 donne une chance à 0
while while
(flag[1]&&turn=1); (flag[0]&&turn=0);
SC SC
flag[0] = faux; flag[1] = faux;
// T0 ne veut plus entrer // T1 ne veut plus entrer
SR SR
forever forever
Algorithme de Peterson vue globale
Scénario pour le changement de
contrôle
Thread T0: Thread T1:
… …
SC flag[1] = vrai;
flag[0] = faux; // T1 veut entrer
// T0 ne veut plus entrer turn = 0;
SR // T1 donne une chance à T0
while
… (flag[0]&&turn=0) ;
//test faux, entre
…
T1 prend la relève, donne une chance à T0 mais T0 a dit
qu’il ne veut pas entrer.
T1 entre donc dans la SC
Autre scénario de changem. de
contrôle
Thread T0: Thread T1:
SC
flag[0] = faux;
// T0 ne veut plus entrer flag[1] = vrai;
SR // T1 veut entrer
flag[0] = vrai; turn = 0;
// T0 veut entrer // T1 donne une chance à T0
turn = 1; // mais T0 annule cette action
// T0 donne une chance à T1
while while
(flag[1]==vrai&&turn=1) ; (flag[0]&&turn=0) ;
// test vrai, n’entre pas //test faux, entre
T0 veut rentrer mais est obligé de donner une chance à T1, qui entre
Mais avec un petit décalage, c’est
encore T0!
Thread T0:
Thread T1:
SC
flag[0] = faux;
// 0 ne veut plus entrer
RS
flag[0] = vrai;
// 0 veut entrer
flag[1] = vrai;
turn = 1;
// 1 veut entrer
// 0 donne une chance à 1
// mais T1 annule cette action
turn = 0;
// 1 donne une chance à 0
while while
(flag[1] && turn=1) ; (flag[0]&&turn=0);
// test faux, entre // test vrai, n’entre pas
Si T0 et T1 tentent simultanément d’entrer dans SC, seule une valeur pour turn
survivra:
non-déterminisme (on ne sait pas qui gagnera), mais l’exclusion fonctionne
d’attendre pour d’autres qui
pourraient ne pas avoir besoin de la
SC
Supposons que T0 soit le seul à avoir besoin de la SC, ou que T1 soit
lent à agir: T0 peut rentrer de suite (flag[1]==faux la dernière fois que T1
est sorti)
flag[0] = vrai // prend l’initiative
turn = 1 // donne une chance à l’autre
while flag[1] && turn=1 //test faux, entre
SC
flag[0] = faux // donne une chance à l’autre
Cette propriété est désirable, mais peut causer famine pour T1
Une leçon à retenir…
• À fin que des processus avec des variables partagées
puissent réussir, il est nécessaire que tous les processus
impliqués utilisent le même algorithme de coordination
• Un protocole commun
Critique des solutions par logiciel
• Difficiles à programmer! Et à comprendre!
• Les solutions que nous verrons dorénavant sont toutes
basées sur l’existence d’instructions spécialisées, qui facilitent
le travail.
• Les processus qui requièrent l’entrée dans leur SC sont
occupés à attendre (busy waiting); consommant ainsi du
temps de processeur
• Pour de longues sections critiques, il serait préférable de
bloquer les processus qui doivent attendre...
Solutions matérielles: désactivation
des interruptions
• Chaque processus désactive
toutes les interruptions avant
d’entrer dans la section critique
• Une fois la section critique Process Pi:
terminée, il réactive les repeat
interruptions inhiber interrupt
• Interruptions désactivées => section critique
horloge ne pouvant pas rétablir interrupt
envoyer d’interruptions section restante
forever
Solutions matérielles: désactivation
des interruptions
• Solution très simple
• Interruptions désactivées : processus pouvant travailler
sans crainte sur l’objet partagée.
• Non judicieux de donner aux processus utilisateur le
pouvoir de désactiver les interruptions
• Problème sérieux posé si interruptions non activées
Solutions matérielles: instructions
machine spécialisées
• Normal: pendant qu’un processus fait accès à une adresse de
mémoire, aucun autre ne peut faire accès à la même adresse
en même temps
• Extension: instructions machine exécutant plusieurs actions
(ex: lecture et écriture) sur la même case de mémoire de
manière atomique (indivisible)
• Une instruction atomique ne peut être exécutée que par un
processus à la fois
Solutions matérielles: instruction Test
and Set
• Lire et écrire le contenu d’un mot de manière indivisible : Test and
Set, TS ou TAS
• Opération ayant deux opérandes :
Un registre a
Et un mot b de la mémoire
Elle copie le mot dans le registre et place la valeur 1 dans b
Procedure TS (var a, b:entier)
Debut
a:=b;
b:=1
Fin
Solutions matérielles: instruction Test
and Set
• Fondamental : cette procédure est toujours utilisée de manière
indivisible
• Permet de résoudre facilement le problème des sections critiques:
Les processus partagent une variable « verrou »
Chaque processus possède une variable locale notée testi
La section d’entrée de chaque processus consiste à exécuter
l’instruction TS (testi,verrou) et à consulter la valeur de cette variable
(testi).
Si sa valeur est 1 (verrou mis) le processus doit recommencer
Sinon, il peut entrer dans la section critique
Le verrou est initialisé à 0
Solutions matérielles: instruction Test
and Set
• Chaque processus Pi est de la forme :
Répéter
<Section Restante>
TS (testi,verrou)
tant que testi=1 faire TS (testi,verrou)
<Section Critique>
verrou:=0
Jusqu’à faux
Solutions matérielles: instruction Test
and Set
• Satisfait l’exclusion mutuelle
• Ne garantit pas l’attente bornée
• L’attente active(sans grande utilité) mobilise l’UC
• Un processus P2 avec forte priorité demande l’UC.
P1 qui dispose de la section critique va être mis en attente.
Si P2 veut aussi entrer en section critique, il ne pourra pas
• blocage
Solutions basées sur des instructions
fournies par le SE (appels du
système)
• Les solutions vues jusqu’à présent sont difficiles à
programmer et conduisent à du mauvais code.
• On voudrait aussi qu’il soit plus facile d’éviter des erreurs
communes, comme interblocages, famine, etc.
• Besoin d’instruction à plus haut niveau
• Les méthodes que nous verrons dorénavant utilisent des
instructions puissantes, qui sont implantées par des
appels au SE (system calls)
Sémaphores
• Un sémaphore S est un entier qui, sauf pour l'Initialisation, est
accessible seulement par ces 2 opérations atomiques et
mutuellement exclusives:
wait(S) (appelé aussi procédure P)
signal(S) (appelé aussi procédure V)
• Il est partagé entre tous les procs qui s’intéressent à la même
section critique
• Les sémaphores seront présentés en deux étapes:
• sémaphores qui sont occupés à attendre (busy waiting)
• sémaphores qui utilisent des files d ’attente
Sémaphores occupés à attendre
(busy waiting)
wait(S):
while S=0 ;
S--;
signal(S):
S++;
Sémaphores occupés à attendre
(busy waiting)
• Wait et Signal sont exécutées de manière indivisible
Quand un processus modifie la valeur du sémaphore S vie Wait
et Signal, aucun autre processus ne peut modifier cette valeur ou
la tester.
• Pour leur implémentation, on peut désarmer les interruptions
pendant l’exécution de Wait et Signal
• Condition d’exclusion mutuelle pour n processus
Sémaphore ex_mut initialisé à 1
Sémaphores occupés à attendre
(busy waiting)
• Chaque processus Pi est de la forme :
Répéter
<Section Restante>
Wait(ex_mut)
<Section Critique>
Signal(ex_mut)
Jusqu’à faux
Utilisation des sémaphores pour
synchronisation de tâches
• On a 2 tâches: T1 et T2 • Synchronisation correcte
• Énoncé S1 dans T1 doit être lorsque T1 contient:
exécuté avant énoncé S2 S1;
dans T2 signal(S);
• Définissons un sémaphore
S • et que T2 contient:
• Initialiser S à 0 wait(S);
S2;
Interblocage et famine avec les
sémaphores
• Famine: un processus peut n’arriver jamais à
exécuter car il ne teste jamais le sémaphore au bon
moment
• Inter blocage: Supposons S et Q initialisés à 1
T0 T1
wait(S)
wait(Q)
wait(Q) wait(S)
Comment éviter l’attente occupée et
le choix aléatoire dans les
sémaphores
• Quand un processus doit attendre qu’un sémaphore
devienne plus grand que 0, il est mis dans une file d’attente
de processus qui attendent sur le même sémaphore.
• Les files peuvent être PAPS (FIFO), avec priorités, etc. Le SE
contrôle l`ordre dans lequel les processus entrent dans leur
SC.
• wait et signal sont des appels au SE comme les appels à des
opérations d’E/S.
• Il y a une file d ’attente pour chaque sémaphore comme il y
a une file d’attente pour chaque unité d’E/S.
Sémaphores sans attente occupée
• Un sémaphore S devient une structure de données:
• Une valeur
• Une liste d’attente L
• Un processus devant attendre un sémaphore S, est bloqué et ajouté la file d’attente S.L du sémaphore (v. état bloqué = attente chap 3).
• signal(S) enlève (selon une politique juste, ex: PAPS/FIFO) un thread de S.L et le place sur la liste des processus prêts/ready.
Implementation
wait(S): [Link] --;
if [Link] < 0 { // SC occupée
add this process to S.L;
block // thread mis en état attente (wait)
signal(S): [Link] ++;
if [Link] 0 { // des threads attendent
remove a process P from S.L;
wakeup(P) // processus choisi devient prêt
}
[Link] doit être initialisé à une valeur non-négative (dépendant de l’application,
v. exemples)
