CHAPITRE3:

Synchronisation et
communication entre
processus
Enseignante de Cours: Siwar Mejri
E-mail: [Link]@[Link]

Année universitaire: 2024-2025

Plan

I- Introduction IV- Solutions Logicielles

II- Section critique V- Les sémaphores

III- Solution Matérielle VI- Problèmes classiques de synchronisation

I. Introduction
 I. Introduction

• Les processus ne sont pas toujours indépendants, ils peuvent coopérer et

nécessitent donc un moyen de communication et synchronisation.

• Parfois, ils se trouvent dans un état de compétition pour les ressources du

système (fichiers ou mémoire commune). Les opérations sur ces ressources
peuvent provoquer des incohérences ou des interblocages si l’accès à ces
ressources n’est pas contrôlé.

4
 I. Introduction

Un interblocage se produit lorsque deux processus concurrents s’attendent

mutuellement.
Exemple :

Tout se passe bien si Processus B s’exécute après la terminaison du processus A. Mais,

considérons maintenant la séquence d'opérations suivante :
- Le processus A obtient R1.
- Le processus B obtient R2.
- Le processus A attend pour obtenir R2.
- Le processus B attend pour obtenir R1.
Dans cette situation, les deux processus sont indéfiniment bloqués : Interblocage. 5
 I. Introduction

Illustration du problème:
Exemple 1 : Imaginons 2 processus voulant imprimer en même temps sur une
seule imprimante disponible.

Print(<<Premier Print(<<Deuxième
PreDeumxièr me pr,,
processus>>) processus>>)

P1 commence à imprimer puis perd le processeur, P2 obtient le processeur et

commence à imprimer➔ Les caractères vont se mélanger.

6
 I. Introduction

→On est devant une situation d’utilisation d’une ressource critique pour laquelle l’accès
doit être exprimé en prenant en compte l’exclusion mutuelle des processus demandeurs.

• L'exclusion mutuelle permet de garantir qu'à tout moment, une ressource critique ne
peut être utilisée que par un seul processus ou thread à la fois. Cela signifie qu'un
processus ou thread qui utilise actuellement la ressource critique empêche tous les
autres processus ou threads d'y accéder jusqu'à ce qu'il ait terminé son utilisation.

→La partie du code des processus utilisant cette ressource critique est dite section
critique. Ici, « print » est une section critique.

7
 I. Introduction

Prenons un autre exemple de section critique ;

Exemple 2 : Mise à jour d’un compte bancaire via 2 processus créditeur et débiteur.

✓Les instructions (1), (2), (3), (4) et (5) sont indivisibles.

✓L’exécution parallèle de plusieurs processus créditeur ou débiteur est possible et
provoque l’entrelacement des instructions.
✓L’exécution parallèle n’est cohérente que si et seulement si le résultat de leur
exécution donne le même résultat qu’une exécution séquentielle. 8
 I. Introduction

C'est-à-dire, si initialement Solde=10.

• Créditeur(5) + débiteur(10) = solde = 5

• puis Débiteur(10) + Créditeur(5) = solde = 5

[Link] le premier scénario, le créditeur ajoute 5 à ce solde (Créditeur(5)), puis le

débiteur retire 10 (Débiteur(10)). Cela donne un solde final de 5.

[Link] le deuxième scénario, le débiteur retire d'abord 10 du solde

(Débiteur(10)), puis le créditeur ajoute 5 (Créditeur(5)). Encore une fois, cela
donne un solde final de 5.

3.➔Dans les 2 cas ; Solde=5.

9
 I. Introduction

A. Considérons l’exécution parallèle de 2 débits : débiteur(9); Initialement

Solde=10.

→ Exécution séquentielle :
1. détection du découvert lors du 2ème débit.
2. Impression du découvert
3. Solde = -8.
→Exécution parallèle possible : (3)1, (4)1, (3)2, (4)2, (5)1, (5)2.
Solde = 1 et pas de détection du découvert : une chance pour le client !
 Les 2 processus débiteurs entrent en conflit d’accès à la variable partagée
Solde.

10
 I. Introduction

B. Considérons l’exécution de 2 crédits : créditeur(5 )et créditeur(7) , avec un Solde

initial =10 ➔ Solde =22.

Or, une exécution parallèle possible : (1)1, (1)2, (2)1, (2)2 ; créditeur(7) ➔ Solde =17 !! 
→Problème d’accès concurrent à une variable partagée.
Donc, la section de code créditeur (débiteur) est une section critique ; au plus, un
seul processus peut l’exécuter à la fois.

Pour éviter le conflit, il faut assurer que l’ensemble des opérations sur cette variable
(consultation + mise à jour) soit exécuté de manière indivisible (= atomique = non
interruptible).
Comment éviter le conflit ?
→Contrôler l’entrée à la SC.
→Garantir l’exclusion mutuelle dans la SC. 11
 I. Introduction

Exemple3 : Spoule d’impression

Supposons que plusieurs utilisateurs envoient des travaux d'impression

simultanément au spouleur d'impression. Chaque travail d'impression est traité
comme une tâche à exécuter.

1. Lorsqu'un utilisateur envoie un travail d'impression, le spouleur d'impression ajoute

cette tâche à une file d'attente de travaux d'impression à traiter.

2. Avant de commencer à traiter un travail d'impression, le spouleur d'impression

vérifie s'il peut accéder à la ressource partagée, c'est-à-dire l'imprimante. C'est la
section critique.

3. Si la ressource est disponible, le spouleur d'impression verrouille l'accès à

l'imprimante, ce qui garantit qu'un seul travail d'impression est exécuté à la fois. C'est
l'exclusion mutuelle. 12
 I. Introduction

Exemple3 : Spoule d’impression

4. Une fois l'accès à l'imprimante verrouillé, le spouleur d'impression commence à

traiter le travail d'impression en cours.

5. Pendant ce temps, les autres travaux d'impression restent dans la file d'attente et
attendent leur tour.

6. Une fois le travail d'impression terminé, le spouleur d'impression déverrouille

l'accès à l'imprimante, ce qui permet au prochain travail d'impression dans la file
d'attente de commencer à être traité.

→ Ce processus garantit que les travaux d'impression sont exécutés de manière

séquentielle, un à la fois, évitant ainsi les conflits d'accès à l'imprimante et assurant un
traitement efficace des travaux d'impression dans le respect de l'exclusion mutuelle.

13
II. Section Critique
 II. Section Critique

1. Définition :

une section critique est une partie d’un programme dont l’exécution ne doit pas
entrelacer avec d’autres programmes. Une fois qu’une tâche y entre, il faut lui
permettre de terminer cette section sans permettre à d’autres tâches d’utiliser les
mêmes données.

L’exécution d’une section critique implique l’exclusion de l’exécution de processus

coopérants de leur section critique correspondante : principe d’exclusion
mutuelle.

15
II. Section Critique

16
 II. Section Critique

Pour mettre en œuvre correctement une SC, il faut s’assurer que les 4 propriétés suivantes sont
vérifiées :

✓ L’accès exclusif ou l’unicité : un et un seul processus est en section critique (exclusion mutuelle).

✓ Avancement et absence d’interblocage: un processus en dehors de sa section critique ne doit pas

empêcher (=bloquer) un autre processus à entrer en section critique.
Donc si un processus veut entrer dans la SC à répétition, et les autres ne sont pas intéressés, il doit
pouvoir le faire.

✓ Pas de famine : aucun processus ne doit attendre indéfiniment pour pouvoir entrer dans sa SC (les
demandes doivent être traitées d’une façon équitable).

Si plusieurs processus sont en attente d’exécuter leurs SC alors qu’aucun processus n’est dans sa SC,
l’un d’eux doit pouvoir y entrer au bout d’un temps fini.

✓ Aucune hypothèse ne doit être faite sur les vitesses relatives des processus.
17
 II. Section Critique

Il est nécessaire de définir un protocole d’entrée en SC et un protocole de sortie de

SC.

Algorithme Exclusion_mutuelle (SC)

….
Entrée_SC ; // {inst} qui permet de vérifier si 1 processus n’est pas déjà en SC.
SC ;
Sortie_SC ; // {inst} qui permet à 1 processus ayant terminé sa SC d’avertir d’autres
processus en attente de la libération de la voie.
….SNC
Fin

Il existe plusieurs méthodes de mise en œuvre de l’exclusion mutuelle dont chacune

a ses avantages et inconvénients
18
III. Solution Matérielle
 III. Solution matérielle

La commutation de processus se fait par des interruptions : interruption de l’horloge

ou de n’importe quel autre périphérique. Ainsi, il est intéressant de masquer
(désactiver) les interruptions quand un processus est en train d’exécuter sa section
critique : plus d’interruption, donc plus de commutation de processus, donc garantir
l’exclusion mutuelle. Le processus peut alors examiner et actualiser la mémoire
partagée.
Algorithme Exclusion_mutuelle (SC)
….
Masquer_interruptions ; in

SC ;
Autoriser_interruptions ;
….
Fin

Cette solution n’est valable que sur un système monoprocesseur. 20

 III. Solution matérielle

En effet, la désactivation des interruptions n’affecte que le processeur en question.

Les autres continuent d’exécuter des processus. Donc, il se peut qu’un processus
accède à la mémoire partagée !

 Il n’est pas judicieux de donner aux processus utilisateur le pouvoir de désactiver

les interruptions. Que se passera t-il s’il oublie de les réactiver ?! ➔ Fin du
système 
Cependant, il est pratique pour le noyau qu’il désactive les Its pendant qu’il
in

actualise des variables ou des listes.

La solution matérielle proposée peut être utilisée si la section critique est courte.

21
IV. Solutions Logicielles
 VI. Solutions Logicielles

On peut envisager des solutions qui utilisent des variables globales. Les 3 premières
solutions qui seront présentées ci-dessous sont fausses.

Solution 1 : un verrou
Un verrou : une variable unique partagée de valeur initiale 0, par exemple : verrou du
disque.
Principe de la méthode : Le processus avant d’entrer en SC teste si un autre est déjà
en train d’exécuter sa SC (SC est verrouillée). Si aucun processus ne se trouve en SC, il
pose un verrou et entre en SC.
Si la porte est fermée, le processus reste dehors. Si elle est ouverte, il entre et ferme
la porte

Verrou = 0 : aucun processus ne se trouve en SC : (initialement)

1 : processus exécute sa SC.
23
 VI. Solutions Logicielles

Soient 2 processus A et B :

Soit la séquence d’exécution suivante: A1, A2, B1, B2, A3, A4, B3, B4 !
→ 2 processus en SC en même temps !
➔L’exclusion mutuelle n’est pas satisfaite !

24
 VI. Solutions Logicielles

Solution 2 : Variable <<tour>>

Le processus ne teste plus si la SC est verrouillée ou non, mais si c’est bien son tour
pour exécuter la SC : P0 entre en SC si tour = 0 et P1 entre en SC si tour = 1

Avec une telle solution, si P0 est en SC, P1 teste d’une façon continue la valeur de la
variable tour jusqu’à ce qu’elle passe à 1. ➔Exclusion mutuelle satisfaite.
Avec cette méthode, on garantit l’exclusion mutuelle mais pas l’avancement des
travaux. Prenons le cas suivant :
25
 VI. Solutions Logicielles

Solution 2 : Variable <<tour>>

➔P1 n’est pas autorisé à exécuter sa SC (car tour = 0), alors que P0 n’est pas
dans sa SC.
➔P1 est plus rapide que P0 : P1 est bloqué dans P1_1, jusqu’à ce que P0
définisse tour à 1.
C’est une alternance stricte !
26
 VI. Solutions Logicielles

Solution 3 : 2 drapeaux (qui est intéressé)

Un processus Pi signale qu’il veut exécuter sa SC par intéressé[i]=vrai. Mais, il
n’entre pas si l’autre processus est aussi intéressé.

→ Exclusion mutuelle est garantie : si P0 est en SC, P1 attend et teste d’une façon continue la
valeur de intéressé[0].
27
 VI. Solutions Logicielles

Solution 3 : 2 drapeaux (qui est intéressé)

→ Le critère « avancement des travaux » n’est pas satisfait.

En effet, considérons la séquence suivante : P0_1, P1_1
→ intéressé[0]=vrai et intéressé[1]=vrai
→ Les processus attendent indéfiniment pour exécuter leur SC !
→ On a un interblocage ! (chaque processus dit : « après vous » : excès de courtoisie ! ) 28
 VI. Solutions Logicielles

Solution 4 : Algorithme de Peterson

Il combine les principes des 2 derniers algorithmes précédents (tour et intéressé).
L’idée est : le processus se dit « je ne vais plus attendre que l’autre processus me
donne mon tour, j’indique moi-même mon tour. Toutefois, je teste si l’autre n’est pas
intéressé ». Là, ça devient question de rapidité ; qui a été le plus rapide à positionner
le tour va passer. Le processus se dit : c’est mon tour, mais je vérifie si l’autre est
intéressé, j’attends.

29
 VI. Solutions Logicielles

Solution 4 : Algorithme de Peterson

Preuve que cette solution est valide :

- Exclusion mutuelle : P0 et P1 peuvent être intéressés en même temps :
o intéressé[0]=vrai et intéressé[1]=vrai
o mais le plus rapide, entre le premier. Exemple : P0 entre bien que tour=1 puisque il a
modifié tour avant P1.
- Avancement : P0 a terminé, P1 est dans sa SNC, P0 peut-il continuer ? intéressé[1]=faux,
intéressé[0]=vrai, tour=0 → Oui, P0 peut exécuter SC puisque la condition est non
vérifiée. → Pas de famine : P0 et P1 veulent exécuter Sc, le plus rapide à poser le tour va
passer. Les 2 vont exécuter leur SC. L’algorithme est équitable si l’ordonnanceur est
équitable.
- On n’a pas posé des hypothèses sur les vitesses (ni sur les caractéristiques) des processus.
30
 VI. Solutions Logicielles

Solution 4 : Algorithme de Peterson

Remarque :
ce test utilise l’attente active qui consomme beaucoup du temps processeur, puisque le
processeur est immobilisé simplement pour attendre → on a un gaspillage de la puissance
CPU disponible.

31
 VI. Solutions Logicielles

Solution 5 : Solution valide par verrou

Pour que la solution utilisant le verrou soit valide, il faut que les opérations de
manipulation du verrou soient atomiques.

32
 VI. Solutions Logicielles

Solution 5 : Solution valide par verrou

avec : type verrou = enregistrement

val : entier
FA : LC //File d'attente de type Liste chaînée

33
 VI. Solutions Logicielles

Les différentes solutions présentées ne permettent de gérer qu’une section

critique, exemple : utilisation d’une seule ressource non partageable (1 seul
exemplaire).
A l’exception du « verrou », les autres solutions présentaient l’inconvénient de
l’attente active.
➔Le verrou = sémaphore binaire
= sémaphore d’exclusion mutuelle

Le sémaphore peut être généralisé afin de pouvoir gérer une ressource

critique en N exemplaires.

34
V- Les sémaphores
 V. Les sémaphores

1. Syntaxe et sémantique d’un sémaphore

Un sémaphore est une structure de données composée d’ :
- un compteur
- une file d’attente

Le sémaphore est initialisé comme suit :

36
 V. Les sémaphores

1. Syntaxe et sémantique d’un sémaphore

Initialement :
-le compteur est égal à une valeur entière positive (=degré d’accès à la
ressource critique),
- la FA est vide : aucun processus n’est en attente.

Nb : Si le sémaphore est initialisé à une valeur n>1, on obtient une solution qui
permet à n processus d’être simultanément dans leur section critique.
Un sémaphore est manipulé par les deux actions atomiques suivantes :
- P(s) décrémente le compteur associé au sémaphore. Si sa valeur est négative,
le processus appelant se bloque dans la file d'attente.
- V(s) incrémente le compteur. Si le compteur est négatif ou nul, un processus
37
est choisi de la file d'attente et est réactivé.
 V. Les sémaphores

1. Syntaxe et sémantique d’un sémaphore

38
 V. Les sémaphores

1. Syntaxe et sémantique d’un sémaphore

Lorsqu’un processus effectue l’opération P(S) :

✓ si la valeur de S est supérieure à 0, il y a alors des ressources disponibles ➔ P(S)
décrémente [Link] et le processus poursuit son exécution,
✓ sinon ce processus sera mis dans une file d’attente jusqu’à la libération d’une
ressource.

Lorsqu’un processus effectue l’opération V(S) :

✓ s’il n’y a pas de processus dans la file d’attente, V(S) incrémente la valeur de S,
sinon un processus en attente est débloqué.

39
 V. Les sémaphores

2. Utilisation des sémaphores

On peut utiliser les sémaphores pour protéger les sections critiques et ainsi garantir
l’exclusion mutuelle et pour assurer la synchronisation conditionnelle des processus,

A. Exclusion mutuelle:
Si on veut par exemple protéger l’accès à une ressource partagée (une variable, une
imprimante...), on utilise un sémaphore d'exclusion mutuelle ;

40
 V. Les sémaphores

2. Utilisation des sémaphores

Question : Un des processus provoque un déroutement durant la section critique et s'arrête.
Quelle anomalie provoque-t-il ainsi sur la suite de l'exécution des autres processus ?
Réponse : Puisque le processus dérouté n'a pas exécuté la sortie de la section critique par
l'appel V(mutex), la section critique est considérée comme toujours occupée par un
processus et par conséquent plus aucun autre processus ne pourra entrer en section
critique.

Si m processus partagent n exemplaires d’une même ressource (m > n)

41
 V. Les sémaphores

2. Utilisation des sémaphores

On peut assimiler la valeur positive du compteur au nombre de processus pouvant acquérir
librement la ressource et assimiler la valeur négative du compteur au nombre de processus
bloqués en attente d'utilisation de la ressource.
Un sémaphore est toujours initialisé à une valeur non-négative mais peut devenir négative
après un certain nombre d'opérations P(S) ➔ nombre des processus en attente.

B. Synchronisation des processus

Il se peut qu’un processus doive attendre un autre pour pouvoir continuer son exécution,
exemple : P0 doit attendre P1 (P1 puis P0)

42
 V. Les sémaphores

B. Synchronisation des processus ( Suite)

- Le sémaphore syn est initialisé avec une valeur de 0. Lorsque sa valeur est 0, cela signifie
qu'il est utilisé comme un mécanisme de blocage pour empêcher P0 de continuer son
exécution avant que P1 ne libère le sémaphore en augmentant sa valeur (V(syn)).
- P0 arrive à un point où il doit attendre que P1 ait terminé certaines tâches avant de
pouvoir continuer.
- P0 tente de prendre le sémaphore syn en exécutant P(syn). Comme la valeur de syn est 0,
cela bloque le processus P0, le faisant attendre.
- P1 exécute ses tâches comme d'habitude.
- À un certain moment, P1 atteint le point où il est prêt à permettre à P0 de continuer.
- P1 libère le sémaphore syn en exécutant V(syn), ce qui incrémente la valeur du
sémaphore à 1.
- Après que P1 ait libéré le sémaphore, la valeur de syn devient 1.
- P0 peut alors continuer son exécution après avoir réussi à prendre le sémaphore syn
(P(syn)). 43
 V. Les sémaphores

2. Utilisation des sémaphores (Suite)

Un sémaphore est un mécanisme de synchronisation qui fonctionne comme une barrière
bloquante dans certaines conditions.

Conclusion : les sémaphores sont des mécanismes de bas niveau, généralement utilisés à
l’intérieur des noyaux de systèmes. Pour des séquences brèves d’exclusion mutuelle, les
multiprocesseurs peuvent en outre utiliser l’attente active.
En général, toutes les solutions se basent sur l’existence d’instructions atomiques, qui
fonctionnent comme SCs de base
.

44
VI- Problèmes classiques de
synchronisation
 VI. Problèmes classiques de synchronisation

1. Rendez-vous
On considère 2 processus, chacun étant constitué de deux phases de calcul AVANT et APRES.
Le problème consiste à garantir qu'aucun des processus ne commence sa phase de calcul
APRES avant que l’autre processus ait terminé leur phase de calcul AVANT. Les 2 processus
ont donc un rendez-vous à la fin de leur phase de calcul AVANT.

46
 VI. Problèmes classiques de synchronisation

1. Rendez-vous
Sémaphores arrivée1, arrivée2 ; arrivé[Link]=0, arrivé[Link]=0 ;

47
 VI. Problèmes classiques de synchronisation

1. Rendez-vous
Soient N processus parallèles ayant un point de rendez-vous. Un processus arrivant au point
de rendez-vous se met en attente s'il existe au moins un autre processus qui n'y est pas
arrivé. Le dernier arrivé réveillera les processus bloqués. La solution suivante résout ce
problème en utilisant des sémaphores.

48
 VI. Problèmes classiques de synchronisation

1. Rendez-vous

49
 VI. Problèmes classiques de synchronisation

2. Producteur/ consommateur (tampon borné)

Buffer:
- Le buffer est un espace de mémoire partagé entre le producteur et le consommateur.
- Il agit comme une zone intermédiaire où le producteur place des données et d'où le
consommateur récupère ces données pour les traiter.
- Il assure la communication et la synchronisation entre le producteur et le consommateur
en leur permettant de travailler à des vitesses différentes
→ Il assure la communication et la synchronisation entre le producteur et le consommateur
50
en leur permettant de travailler à des vitesses différentes.
 VI. Problèmes classiques de synchronisation

2. Producteur/ consommateur (tampon borné)

Producteur :
- Le producteur est responsable de la génération ou de la création des données à stocker
dans le buffer.
- Après la création des données, le producteur les place dans le buffer pour les rendre
disponibles au consommateur.
-Le producteur fonctionne de manière asynchrone par rapport au consommateur, ce qui
signifie qu'il peut continuer à produire des données même si le consommateur n'est pas prêt
à les traiter. 51
 VI. Problèmes classiques de synchronisation

2. Producteur/ consommateur (tampon borné)

Consommateur :

-Le consommateur récupère les données du buffer et les traite ou les utilise selon ses
besoins.
-Il fonctionne de manière asynchrone par rapport au producteur, ce qui signifie qu'il peut
traiter les données à son propre rythme, en les récupérant lorsque nécessaire.
-Le consommateur assure la libération de l'espace dans le buffer après avoir utilisé les
52
données, permettant au producteur de continuer à ajouter de nouvelles données.
 VI. Problèmes classiques de synchronisation

2. Producteur/ consommateur (tampon borné)

Contraintes de synchronisation :
- Relation de précédence : Producteur < Consommateur
- Section critique (tampon)
o tampon plein → Producteur se bloque
o tampon vide Consommateur se bloque → Exclusion mutuelle au tampon 53
 VI. Problèmes classiques de synchronisation

2. Producteur/ consommateur (tampon borné)

Variables partagées :
#define N 100
Semaphore mutex; [Link]=1; /* protège l'accès au tampon */
Semaphore nb_plein; nb_plein.val=0; /*compte le nb d ’informations produites dans le
tampon */
Semaphore nb_vide ; nb_vide.val= N; /*Nb d ’emplacements libres dans le tampon */

54
 VI. Problèmes classiques de synchronisation

2. Producteur/ consommateur (tampon borné)

55
 VI. Problèmes classiques de synchronisation

3. Lecteurs/ rédacteurs
Considérons ce problème comme étant un système de réservation de billets d’avions où
plusieurs processus tentent de lire et d'écrire des informations:
- On accepte que plusieurs lecteurs utilisent le système➔ degré d’accès>=1

- On n’autorise qu’un seul rédacteur à la fois ➔on exclut les lecteurs et les rédacteurs :
degré d’accès=1➔ exclusion mutuelle → Sémaphore : nb_accès.

- Un rédacteur bloqué doit attendre le dernier des lecteurs pour qu’il puisse entrer en
section critique.

56
 VI. Problèmes classiques de synchronisation

3. Lecteurs/ rédacteurs
Variables partagées:

Sémaphore mutex ; [Link]=1; /* protège le compteur des lecteurs */

Sémaphore nb_accès; nb_accès=1; /* exclusion mutuelle pour les rédacteurs */
int nb_lect=0; /* Nombre de lecteurs actifs */

57
 VI. Problèmes classiques de synchronisation

3. Lecteurs/ rédacteurs

58