Operating system II

Chapitre II: Process Synchronization

[Link]

Université des sciences et de technologie Med Boudiaf Oran

Faculté MI Département Informatique
06 Janvier 2025

20 mars 2025

1 / 54
Belarbi SI2 V1.0 Janvier 2025 (2024-2025)
 2 / 54
Belarbi SI2 V1.0 Janvier 2025 (2024-2025)
 Introduction
The Critical-section problem
Sémaphore Dénitions
Problème classique de synchronisation
Les Moniteurs

Process Synchronization
Objectifs du chapitre

Présenter le problème de critical section, dont les solutions peuvent

être utilisées pour assurer la cohérence des données partagées.
Présenter les solutions logicielles et matérielles du problème de critical
section.
Examiner plusieurs problèmes classiques du process synchronization
Explorer plusieurs outils utilisés pour résoudre process synchronization.

3 / 54
Belarbi SI2 V1.0 Janvier 2025 (2024-2025)
 Introduction
The Critical-section problem
Sémaphore Dénitions
Problème classique de synchronisation
Les Moniteurs

Process Synchronization
Dénitions

La mémoire est partagée entre plusieurs process, il y a donc des risques

de comportements bizarres.
Situation de compétition ou de coopération entre process
Compétition : plusieurs process veulent accéder à la même ressource
(par exemple, modier le même chier ou la même variable)
Coopération : plusieurs process interagissent pour mener à bien une
tâche  ils doivent communiquer régulièrement pour échanger des
informations et déterminer l'avancement global
Les deux situations nécessitent de synchroniser les process

4 / 54
Belarbi SI2 V1.0 Janvier 2025 (2024-2025)
 Introduction
The Critical-section problem
Sémaphore Dénitions
Problème classique de synchronisation
Les Moniteurs

Process Synchronization
Exemple - Compte Bancaire-

Deux opérations sur le même compte exécutées en concurrence :

Concurrence sans problème

5 / 54
Belarbi SI2 V1.0 Janvier 2025 (2024-2025)
 Introduction
The Critical-section problem
Sémaphore Dénitions
Problème classique de synchronisation
Les Moniteurs

Process Synchronization
Exemple - Compte Bancaire-

Deux opérations sur le même compte exécutées en concurrence : Concurrence avec problème

- Le résultat dépend de l'entrelacement des actions, donc de l'ordonnancement des process. Il y

a donc un besoin de contrôler le déroulement d'un process.

- Il faut empêcher l'utilisation simultanée en lecture et écriture de la variable commune

Compte .
6 / 54
Belarbi SI2 V1.0 Janvier 2025 (2024-2025)
 Introduction
The Critical-section problem Dénitions
Sémaphore Caractéristique
Problème classique de synchronisation Solutions Critical-section
Les Moniteurs

The Critical-section problem

Concepts fondamentaux

Ressource critique
Une ressource est dite ressource critique lorsque des accès concurrents
à cette ressources peuvent résulter dans un état incohérent.

7 / 54
Belarbi SI2 V1.0 Janvier 2025 (2024-2025)
 Introduction
The Critical-section problem Dénitions
Sémaphore Caractéristique
Problème classique de synchronisation Solutions Critical-section
Les Moniteurs

The Critical-section problem

Concepts fondamentaux

Ressource critique
Une ressource est dite ressource critique lorsque des accès concurrents
à cette ressources peuvent résulter dans un état incohérent.

Race condition
On parle aussi de situation de compétition(race condition) pour décrire
une situation dont l'issue dépend de l'ordre dans lequel les opérations
sont eectuées.

7 / 54
Belarbi SI2 V1.0 Janvier 2025 (2024-2025)
 Introduction
The Critical-section problem Dénitions
Sémaphore Caractéristique
Problème classique de synchronisation Solutions Critical-section
Les Moniteurs

The Critical-section problem

Concepts fondamentaux

Ressource critique
Une ressource est dite ressource critique lorsque des accès concurrents
à cette ressources peuvent résulter dans un état incohérent.

Race condition
On parle aussi de situation de compétition(race condition) pour décrire
une situation dont l'issue dépend de l'ordre dans lequel les opérations
sont eectuées.

Section atomique
Une section de programme est dite atomique lorsqu'elle ne peut pas être
interrompue par un autre process manipulant les mêmes ressources
critiques. C'est donc une atomicité relative à la ressource.
7 / 54
Belarbi SI2 V1.0 Janvier 2025 (2024-2025)
 Introduction
The Critical-section problem Dénitions
Sémaphore Caractéristique
Problème classique de synchronisation Solutions Critical-section
Les Moniteurs

The Critical-section problem

Concepts fondamentaux

Critical-section
Critical-section est une section de programme manipulant une ressource
critique.

8 / 54
Belarbi SI2 V1.0 Janvier 2025 (2024-2025)
 Introduction
The Critical-section problem Dénitions
Sémaphore Caractéristique
Problème classique de synchronisation Solutions Critical-section
Les Moniteurs

The Critical-section problem

Concepts fondamentaux

Critical-section
Critical-section est une section de programme manipulant une ressource
critique.

Mutual exclusion
Un mécanisme d'exclusion mutuelle sert à assurer l'atomicité des sections
critiques relatives à une ressource critique.
Une ressource est en exclusion mutuelle si seul un processus peut utiliser
la ressource à un instant donné.

8 / 54
Belarbi SI2 V1.0 Janvier 2025 (2024-2025)
 Introduction
The Critical-section problem Dénitions
Sémaphore Caractéristique
Problème classique de synchronisation Solutions Critical-section
Les Moniteurs

The Critical-section problem

Caractéristique

Chaque process possède un segment de code, appelé critical-section

Un process modie des variables communes, actualiser une table,

écrire un chier, etc
Quand un process exécute sa critical-section, aucun autre process n'est
autorisé à exécuter sa critical-section (Un seul process dans critical-section) ;
L'exécution des criticals-sections est mutuellement exclusive dans le
temps ;
Le problème de criticals sections est de concevoir un protocole que les
process puissent utiliser pour coopérer.

9 / 54
Belarbi SI2 V1.0 Janvier 2025 (2024-2025)
 Introduction
The Critical-section problem Dénitions
Sémaphore Caractéristique
Problème classique de synchronisation Solutions Critical-section
Les Moniteurs

Critical Section Problem

Caractéristique

La tolérance aux défaillances : si le processus en SC est détruit ou

se termine anormalement, il ne faut pas qu'il bloque tout le système ;
La symétrie : Les protocoles d'E/S en SC doivent être identiques
pour tous les processus et indépendants de leur nombre.
Aucune hypothèse ne doit être posée sur les vitesses relatives des
processus ni sur le nombre de processeurs.
L'exclusion Mutuelle n'est pas garantie si :
1 un processus peut entrer en SC alors qu'un autre s'y trouve déjà ;
2 un processus désirant entrer en SC ne peut pas y entrer alors qu'il
n'y a aucun processus en SC ;
3 un processus désirant entrer en SC n'y entrera jamais car il sera
jamais sélectionné lorsqu'il est en concurrence avec d'autres
processus.

10 / 54
Belarbi SI2 V1.0 Janvier 2025 (2024-2025)
 Introduction
The Critical-section problem Dénitions
Sémaphore Caractéristique
Problème classique de synchronisation Solutions Critical-section
Les Moniteurs

Critical Section Problem

Caractéristique
chaque process doit demandé la permission d'entrer à sa Critical
Section.
Entry section est la section code qui implémente cette requête ;
Critical Section doit être suivie par Exit section ;
Le code restant est remainder section ;

Figure  General structure of a typical process Pi

11 / 54
Belarbi SI2 V1.0 Janvier 2025 (2024-2025)
 Introduction
The Critical-section problem Dénitions
Sémaphore Caractéristique
Problème classique de synchronisation Solutions Critical-section
Les Moniteurs

Critical Section Problem

Exemple Banque

P1 P2
entry_Critical_section(. . ..) ; entry_Critical_section( . . ...) ;
/* début la section critique */ /* début la section critique */
int tmp = compte ; int tmp = compte ;
tmp = tmp + 1000 ; tmp = tmp -500 ;
compte = tmp ; compte = tmp ;
/* n de la section critique */ /* n de la section critique */
Exit_Critical_section(. . ...) Exit_Critical_section(. . ..) ;

??
Les codes de fonctions entry_Critical_section(. . ..) ; et
Exit_Critical_section(. . ...) ;

12 / 54
Belarbi SI2 V1.0 Janvier 2025 (2024-2025)
 Introduction
The Critical-section problem Dénitions
Sémaphore Caractéristique
Problème classique de synchronisation Solutions Critical-section
Les Moniteurs

Critical-section problem
Solutions

Une solution au critical-section problem, doit satisfaire aux trois besoins

suivants :
Mutual Exclusion : si le process Pi exécute sa critical-section, aucun
autre process ne peut exécuter sa critical-section ;
Idée : verrouiller l'accès à une section critique déjà occupée

13 / 54
Belarbi SI2 V1.0 Janvier 2025 (2024-2025)
 Introduction
The Critical-section problem Dénitions
Sémaphore Caractéristique
Problème classique de synchronisation Solutions Critical-section
Les Moniteurs

Critical-section problem
Solutions

Une solution au critical-section problem, doit satisfaire aux trois besoins

suivants :
Mutual Exclusion : si le process Pi exécute sa critical-section, aucun
autre process ne peut exécuter sa critical-section ;
Idée : verrouiller l'accès à une section critique déjà occupée
Progress : si aucun process n'exécute sa critical section et si certains
process désirent entrer dans les leurs, alors seulement les process qui
ne se trouvent pas dans leurs remainder section peuvent décider qui
rentrera dans critical-section (la sélection ne peut pas être reportée
indéniment).

13 / 54
Belarbi SI2 V1.0 Janvier 2025 (2024-2025)
 Introduction
The Critical-section problem Dénitions
Sémaphore Caractéristique
Problème classique de synchronisation Solutions Critical-section
Les Moniteurs

Critical-section problem
Solutions

Une solution au critical-section problem, doit satisfaire aux trois besoins

suivants :
Mutual Exclusion : si le process Pi exécute sa critical-section, aucun
autre process ne peut exécuter sa critical-section ;
Idée : verrouiller l'accès à une section critique déjà occupée
Progress : si aucun process n'exécute sa critical section et si certains
process désirent entrer dans les leurs, alors seulement les process qui
ne se trouvent pas dans leurs remainder section peuvent décider qui
rentrera dans critical-section (la sélection ne peut pas être reportée
indéniment).
bounded waiting : limiter le nombre de permissions à d'autres process
a accédé à critical section ;

13 / 54
Belarbi SI2 V1.0 Janvier 2025 (2024-2025)
 Introduction
The Critical-section problem Dénitions
Sémaphore Caractéristique
Problème classique de synchronisation Solutions Critical-section
Les Moniteurs

Critical section problem

Solutions Critical-section

Solutions logicielles pour le problème de critical-section

Solutions algorithmiques
 Exemples : Solution de Peterson, Solution de Dekker (Fiche TD2 )
 Limitées à deux processus
 Pas de garantie de bonne fonctionnements sur toutes les
architectures

14 / 54
Belarbi SI2 V1.0 Janvier 2025 (2024-2025)
 Introduction
The Critical-section problem Dénitions
Sémaphore Caractéristique
Problème classique de synchronisation Solutions Critical-section
Les Moniteurs

Critical section problem

Solutions Critical-section

Solutions logicielles pour le problème de critical-section

Solutions algorithmiques
 Exemples : Solution de Peterson, Solution de Dekker (Fiche TD2 )
 Limitées à deux processus
 Pas de garantie de bonne fonctionnements sur toutes les
architectures
Solutions matérielles
Masquage des interruptions
Pas faisable sur des architectures multiprocesseurs
Peut perturber le bon fonctionnement du système (mise à jour de
l'horloge)
Instructions spéciales (supportées par le matériel)
Test and set (dicile dans un multiprocesseur)
Permutation (swap) atomique
Complexes à utiliser par les programmeurs

14 / 54
Belarbi SI2 V1.0 Janvier 2025 (2024-2025)
 Introduction
The Critical-section problem Dénitions
Sémaphore Caractéristique
Problème classique de synchronisation Solutions Critical-section
Les Moniteurs

Critical-section solution
Le verrou -attente active-

Verrou
Un mécanisme proposé pour permettre de résoudre les concurrences
d'accès à une ressource est le mécanisme de verrou.
On utilise un booléen partagé comme Verrou
Un verrou est un objet système à deux états
(libre(unlocked)/occupé(locked)) sur lequel deux opérations sont dénies.

Lock(v) permet au process d'acquérir le verrou v s'il est libre. S'il n'est
pas disponible, le process est bloqué en attente de la ressource.
Unlock (v) permet au process de libérer le verrou v qu'il possédait.
Si un ou plusieurs process étaient en attente de ce verrou, un seul de ces
process est réactivé et reçoit le verrou.
invoquer unlock() réveille un process suspendu (s'il y en a) attention :
ordre de réveil non spécié 15 / 54
Belarbi SI2 V1.0 Janvier 2025 (2024-2025)
 Introduction
The Critical-section problem Dénitions
Sémaphore Caractéristique
Problème classique de synchronisation Solutions Critical-section
Les Moniteurs

Critical-section solution
Verrou -attente active-

16 / 54
Belarbi SI2 V1.0 Janvier 2025 (2024-2025)
 Introduction
The Critical-section problem Dénitions
Sémaphore Caractéristique
Problème classique de synchronisation Solutions Critical-section
Les Moniteurs

Critical-section solution
API POSIX (Threads)
API POSIX : Mutex locks (Threads)

17 / 54
Belarbi SI2 V1.0 Janvier 2025 (2024-2025)
 Introduction
The Critical-section problem Dénitions
Sémaphore Caractéristique
Problème classique de synchronisation Solutions Critical-section
Les Moniteurs

Critical-section solution
attente active

Défauts de l'attente active Le processus qui attend consomme du

temps processeur (d'où le nom d'attente active).
NB : on peut améliorer cela en mettant un sleep ou un yield dans la
boucle.
Cette approche n'assure par l'exclusion !
verrou est lui même une ressource critique.
- Bonne solution
On associe à la ressource un jeton, que les process peuvent prendre et
reposer Seul le process possédant le jeton devrait manipuler la ressource
Donc, si un process souhaite manipuler la ressource et que le jeton est
pris, il doit d'abord attendre que le jeton redevienne disponible
Utilisation d'un sémaphore initialisé à 1

18 / 54
Belarbi SI2 V1.0 Janvier 2025 (2024-2025)
 Introduction
The Critical-section problem Dénitions
Sémaphore Caractéristique
Problème classique de synchronisation Solutions Critical-section
Les Moniteurs

Process Synchronization
Résumé
Exclusion mutuelle
Notion de "race condition" :
- plusieurs accès concurrents à une même variable
- accès non atomique données incohérentes
Critical section
- morceau de code qu'on veut rendre atomique
- exécution nécessairement en exclusion mutuelle
Solution : utiliser un mutex lock
lock(V) ;
/* section critique */
unlock(V) ;
Résumé des problèmes
- Attentes actives à consommation du temps CPU.
ˆ Masquage des interruptions à dangereuse pour le système
innie. ˆ SLEEP et WAKEUP à mauvaise synchronisation des signaux
(rendez-vous manqués) à blocage.
19 / 54
Belarbi SI2 V1.0 Janvier 2025 (2024-2025)
 Introduction
The Critical-section problem
Sémaphore Dénition
Problème classique de synchronisation
Les Moniteurs

Process Synchronization
Sémaphore

Les solutions matérielles et logicielles présentées dans les sections pré-

cédentes sont diciles à mettre en ÷uvre pour des problèmes de syn-
chronisation complexes.

20 / 54
Belarbi SI2 V1.0 Janvier 2025 (2024-2025)
 Introduction
The Critical-section problem
Sémaphore Dénition
Problème classique de synchronisation
Les Moniteurs

Process Synchronization
Sémaphore

Les solutions matérielles et logicielles présentées dans les sections pré-

cédentes sont diciles à mettre en ÷uvre pour des problèmes de syn-
chronisation complexes.
Le système d'exploitation ore un outil de synchronisation appelé sé-
maphore,

20 / 54
Belarbi SI2 V1.0 Janvier 2025 (2024-2025)
 Introduction
The Critical-section problem
Sémaphore Dénition
Problème classique de synchronisation
Les Moniteurs

Process Synchronization
Sémaphore

Les solutions matérielles et logicielles présentées dans les sections pré-

cédentes sont diciles à mettre en ÷uvre pour des problèmes de syn-
chronisation complexes.
Le système d'exploitation ore un outil de synchronisation appelé sé-
maphore,
Les sémaphores ont été introduits par Edsger Dijkstra , informaticien
hollandais , en 1965.

20 / 54
Belarbi SI2 V1.0 Janvier 2025 (2024-2025)
 Introduction
The Critical-section problem
Sémaphore Dénition
Problème classique de synchronisation
Les Moniteurs

Process Synchronization
Sémaphore

Les solutions matérielles et logicielles présentées dans les sections pré-

cédentes sont diciles à mettre en ÷uvre pour des problèmes de syn-
chronisation complexes.
Le système d'exploitation ore un outil de synchronisation appelé sé-
maphore,
Les sémaphores ont été introduits par Edsger Dijkstra , informaticien
hollandais , en 1965.
Un sémaphore S est constitué de deux champs : d'un compteur (une
variable)protéger et d'une le d'attente F (Process bloqués)

20 / 54
Belarbi SI2 V1.0 Janvier 2025 (2024-2025)
 Introduction
The Critical-section problem
Sémaphore Dénition
Problème classique de synchronisation
Les Moniteurs

Sémaphore
Implémentation

On peut accéder au sémaphores à l'aide des Primitives suivants :

Initialisation I(S,x) : qui permet de créer le sémaphore et de lui
attribuer une valeur initiale (x) positive ou null ;
Manipulation : par deux opérations standards atomiques wait et si-
gnal ;
Une fonction permettant de détruire un sémaphore et de libérer les
ressources qui lui sont associées.

21 / 54
Belarbi SI2 V1.0 Janvier 2025 (2024-2025)
 Introduction
The Critical-section problem
Sémaphore Dénition
Problème classique de synchronisation
Les Moniteurs

Sémaphore
Implémentation WAIT
wait, P(Dijkstra(Proberen, tester))(down(algol68), sleep)
wait(S) : demande d'autorisation, qui est utilisée pour modier la
valeur du sémaphore.
Si S>0, S- - (décrémenter) (en utilisant un wakeup stockée) et poursuit
son activité
Si S==0 ,le process est placé en sommeil(le d'attente) sans que down
ne se termine
Si F(S) vide, S++, Sinon, un des process en attente (choix aléatoire)
est libéré et passe à l'état Ready.

22 / 54
Belarbi SI2 V1.0 Janvier 2025 (2024-2025)
 Introduction
The Critical-section problem
Sémaphore Dénition
Problème classique de synchronisation
Les Moniteurs

Sémaphore
Implémentation SIGNAL
Signal, V(Dijkstra(Verhogen,incrémenter),(up(algol68), wakeup)
signal(S) : n d'utilisation (Libérer)
Si F(S) non vide Sinon, un des process en attente (choix aléatoire) est
libéré et passe à l'état Ready et S==0 sinon S++
Si S>0, S d'une unité et la fonction réussit.
Si s==0, le process est bloqué jusqu'à ce qu'un autre process le dé-
bloque en appelant la fonction post.
Quant un process doit attendre un sémaphore, il est ajouté à la le
de process. Une opération Signal supprime un process de la le des
process en attente et réveille ce process.
L'exécution d'une opération wait(s) ou signal(s) se fait sans interac-
tion possible (de façon atomique).

23 / 54
Belarbi SI2 V1.0 Janvier 2025 (2024-2025)
 Introduction
The Critical-section problem
Sémaphore Dénition
Problème classique de synchronisation
Les Moniteurs

Type de sémaphore
Sémaphore binaires

Un sémaphore binaire est un sémaphore ayant une valeur entière entre

0 et 1 ;
Un sémaphore binaire est un sémaphore qui est initialisé avec la
valeur 1. Ceci a pour eet de contrôler l'accès une ressource unique.
Le sémaphore binaire permet l'exclusion mutuelle (mutex) : Une res-
source est en exclusion mutuelle si seul un processus peut utiliser la
ressource à un instant donné.
Un sémaphore qui est initialisé avec la valeur 0 est un sémaphore
bloquant.
Plus simple à implémenter qu'un sémaphore de comptage

24 / 54
Belarbi SI2 V1.0 Janvier 2025 (2024-2025)
 Introduction
The Critical-section problem
Sémaphore Dénition
Problème classique de synchronisation
Les Moniteurs

Type de sémaphore
Sémaphore de comptage

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.

25 / 54
Belarbi SI2 V1.0 Janvier 2025 (2024-2025)
 Introduction
The Critical-section problem
Sémaphore Dénition
Problème classique de synchronisation
Les Moniteurs

Sémaphore
Sémaphore (Utilisation)
Problème de la section critique
n processus partagent un sémaphore,
Les sémaphores binaires permettent d'assurer l'exclusion mutuelle :
Semaphore mutex = 1 ;
Principe :
Sémaphore mutex (à cause de mutual exclusion)initialisé a 1 ;
Primitive wait en début de la section critique ;
Primitive signal en n de la section critique ;
Implémentation de Mutual exclusion avec des semaphores.
repeat
wait(mutex) ;
critical section
signal mutex()
section restante
until false ; 26 / 54
Belarbi SI2 V1.0 Janvier 2025 (2024-2025)
Sémaphore
Exemple

Deux Process P1 et P2 exécutent respectivement deux instructions S1 et S2

Process P1 | Process P2
Debut | Debut
S1 | S2
Fin | Fin

S2 s'execute après S1

Process P1 | Process P2
Debut | Debut
S1 ; | Wait(S) ;
Signal(S) | S2
Fin | Fin
Comme S est initialisé à 0, Process P2 executera S2 seulement une fois
que Process P1 aura appelé signal(S), qui est après S1.
Remarque : Un sémaphore peut être initialisé à n'importe quelle valeur entière, mais

généralement cette valeur est positive ou null .

Sémaphore
Exemple

28 / 54
 Introduction
The Critical-section problem
Sémaphore Dénition
Problème classique de synchronisation
Les Moniteurs

Sémaphores
Sémaphores POSIX

Les sémaphores POSIX sont implantés dans la librairie <semaphore.h>

Le type sémaphore est désigné par le mot : sem_t.

29 / 54
Belarbi SI2 V1.0 Janvier 2025 (2024-2025)
 Introduction
The Critical-section problem
Sémaphore Dénition
Problème classique de synchronisation
Les Moniteurs

Sémaphores
Sémaphores POSIX

Initialisation :
#include <semaphore.h>
int sem_init(sem_t *sem, int pshared, unsigned int value) ;
Une fois l'objet créé, on peut l'initialiser :
sem 7→ pointeur vers le sémaphore à initialiser ;
pshared 7→ drapeau qui précise si le sémaphore est utilisé par des threads
(valeur 0pour local et non null pour partagé) ;
value 7→ valeur de départ(initiale) du sémaphore.
le code retour varie entre :
'0' si tout s'est bien passé
'1' si une erreur survient et errno est positionné

30 / 54
Belarbi SI2 V1.0 Janvier 2025 (2024-2025)
 Introduction
The Critical-section problem
Sémaphore Dénition
Problème classique de synchronisation
Les Moniteurs

Sémaphores
Sémaphores POSIX
Blocage
Une fois le sémaphore initialisé, on peut demander son blocage avec
#include <semaphore.h>
int sem_wait(sem_t *sem) ;
sem 7→ pointeur vers le sémaphore à bloquer ;
le code retour varie entre :
'0' si tout s'est bien passé
'-1' si une erreur survient et errno est positionné
int sem_wait(semaphore *s)
{
s−→val = s−→val-1 ;
if(s−→val<0)
{
// Place this thread in s−→queue ;
// This thread is blocked ;
}
31 / 54
} Belarbi SI2 V1.0 Janvier 2025 (2024-2025)
 Introduction
The Critical-section problem
Sémaphore Dénition
Problème classique de synchronisation
Les Moniteurs

Sémaphores
Sémaphores POSIX
Relachement d'un sémaphore
Une fois la section critique passée, on peut relâcher le sémaphore :
#include <semaphore.h>
int sem_post(sem_t *semaphore) ;
semaphore−→ pointeur vers le sémaphore bloqué ;
le code retour varie entre :
'0' si tout s'est bien passé
'-1' si une erreur survient et errno est positionné
int sem_post(semaphore *s)
{
s−→val = s−→val+1 ;
if(s−→val<=0)
{
// Remove one thread(T) from s−→queue ;
// Mark Thread(T) as ready to run ;
}
32 / 54
} Belarbi SI2 V1.0 Janvier 2025 (2024-2025)
Sémaphores
Sémaphores POSIX

Destruction
int sem_destroy(sem_t *sem) ;
sem −→ pointeur vers le sémaphore à détruire ;
le code retour varie entre :
'0' si tout s'est bien passé
'-1' si une erreur survient et errno est positionné
Sémaphores
Sémaphores POSIX

int sem_trywait( sem_t *sem) : décrémente la valeur du sémaphore, si

sa valeur est supérieure à 0 et retourne 0 ; sinon elle retourne une erreur
(une valeur diérente de 0) => sem_wait non bloquant.

int sem_getvalue(sem_t *sem, int * sval) : retourne dans sval la valeur

courante du sémaphore.

34 / 54
Process Synchronization
Sémaphore avec le d'attente

Surmonter le besoin de l'attente active :

Modier la dénition des opérations de sémaphores Wait et signal.
Qd un processus exécute wait(), au lieu de l'attente, le processus
peut se bloqué lui même
Opération block place le un process dans une le d'attente associés
au sémaphore.
Le contrôle est transféré au sheduler de l'UC qui sélectionne un
autre process (pour l'exécuter)
un process bloqué devrait être redémarré qd un autre process
exécute signal.
process est redémarré avec une opération wakeup (changement
d'état de attente à prêt)

35 / 54
Process Synchronization
Sémaphore (avec le d'attente)

Dénition 2
Un sémaphore S est un ensemble de deux variables :
une valeur entière value
une le d'attente F de process

Implémentation
décrire un sémaphore comme un enregistrement
type semaphore =record
value : integer ;
L :list of process ;
end ;

Les opérations des sémaphores peuvent être déni comme suit :

36 / 54
Process Synchronization
Sémaphore (avec le d'attente)

wait(s) : [Link] :=[Link]-1 ;

if [Link]<0
then begin
ajouter ce process à S.L ;
block ;
end ;

signal(S) : [Link] :=[Link]+1 ;

if [Link]≤0
then begin
enlever le process P à S.L ;
wakeup (P) ;
end ;
La le d'attente d'un sémaphore est gérée :
 FIFO : sémaphore fort (par défaut) ou
 LIFO : sémaphore faible (famine possible).
Interblocage et famine

Deux process ou plus peuvent attendre indéniment un événement qui ne

peut être produit que par un process en attente (l'exécution de signal).

Ces process se trouvent dans une situation d'interblocage

Si nous ajoutons ou supprimons des process de la le dans un ordre LIFO,

il peut de produire un blocage indéni ou la famine. Une situation où les
process attendent indéniment dans le sémaphore.

38 / 54
 Problème classique de synchronisation
Le problème des lecteurs et rédacteurs
Ce problème traite de l'accès concurrent en lecture et en écriture à
une ressource : une base de donnée. exple :réservation de billets d'avion

39 / 54
 Problème classique de synchronisation
Le problème des lecteurs et rédacteurs
Ce problème traite de l'accès concurrent en lecture et en écriture à
une ressource : une base de donnée. exple :réservation de billets d'avion
Plusieurs processus légers (thread) peuvent lire en même temps la
ressource (lecteurs), aucun eet défavorable (puisqu'une lecture ne
modie pas le contenu d'une ressource) ;
 Problème classique de synchronisation
Le problème des lecteurs et rédacteurs
Ce problème traite de l'accès concurrent en lecture et en écriture à
une ressource : une base de donnée. exple :réservation de billets d'avion
Plusieurs processus légers (thread) peuvent lire en même temps la
ressource (lecteurs), aucun eet défavorable (puisqu'une lecture ne
modie pas le contenu d'une ressource) ;
Si on veut actualiser (lire et écrire)-rédacteur- : si un rédacteur et
d'autres process( lecteurs où rédacteurs) accèdent simultanément à
la ressource, le chaos peut s'ensuivre. les lecteurs ne doivent pas lire
une information en cours de modication ;
 Problème classique de synchronisation
Le problème des lecteurs et rédacteurs
Ce problème traite de l'accès concurrent en lecture et en écriture à
une ressource : une base de donnée. exple :réservation de billets d'avion
Plusieurs processus légers (thread) peuvent lire en même temps la
ressource (lecteurs), aucun eet défavorable (puisqu'une lecture ne
modie pas le contenu d'une ressource) ;
Si on veut actualiser (lire et écrire)-rédacteur- : si un rédacteur et
d'autres process( lecteurs où rédacteurs) accèdent simultanément à
la ressource, le chaos peut s'ensuivre. les lecteurs ne doivent pas lire
une information en cours de modication ;
Les rédacteurs demandent des accès en écriture à la ressource ;

39 / 54
 Problème classique de synchronisation
Le problème des lecteurs et rédacteurs
Ce problème traite de l'accès concurrent en lecture et en écriture à
une ressource : une base de donnée. exple :réservation de billets d'avion
Plusieurs processus légers (thread) peuvent lire en même temps la
ressource (lecteurs), aucun eet défavorable (puisqu'une lecture ne
modie pas le contenu d'une ressource) ;
Si on veut actualiser (lire et écrire)-rédacteur- : si un rédacteur et
d'autres process( lecteurs où rédacteurs) accèdent simultanément à
la ressource, le chaos peut s'ensuivre. les lecteurs ne doivent pas lire
une information en cours de modication ;
Les rédacteurs demandent des accès en écriture à la ressource ;
Les lecteurs demandent des accès en lecture à la ressource.
 Introduction
The Critical-section problem
Sémaphore Conclusion
Problème classique de synchronisation
Les Moniteurs

Problème classique de synchronisation

Le problème des lecteurs et rédacteurs

Le rédacteur (écrivain)
Un écrivain exclut les autres écrivains et les lecteurs : un écrivain
accède donc toujours seul à la ressource, autrement dit il eectue des
accès en mutual exclusion des autres écrivains et des lecteurs (un accès
exclusif).
- Le schéma du mutual exclusion (rédacteur) se fait à l'aide d'un
sémaphore redact initialisé à 1.

40 / 54
Belarbi SI2 V1.0 Janvier 2025 (2024-2025)
 Introduction
The Critical-section problem
Sémaphore Conclusion
Problème classique de synchronisation
Les Moniteurs

Problème classique de synchronisation

Le problème des lecteurs et rédacteurs

Le lecteur Un lecteur exclut les écrivains mais pas les autres lecteurs. Il
faut donc :
Le premier lecteur doit s'assurer qu'il n'y a pas d'accès en écriture
en cours ;
Le dernier lecteur doit réveiller un éventuel écrivain ;
On doit compter le nombre de lecteurs qui accèdent à la ressource.
On utilise pour cela une variable NbL, initialisée à 0. Cette variable
NbL va être accédée en concurrence par tous les lecteurs qui vont
soit incrémenter cette variable (un lecteur de plus), soit la
décrémenter (un lecteur de moins). Pour que le contenu de la
variable reste cohérent, il faut que NbL soit accédée en exclusion
mutuelle. L'accès à la variable sera donc gardé par un sémaphore
MUTEX initialisé à 1.

41 / 54
Belarbi SI2 V1.0 Janvier 2025 (2024-2025)
 Problème classique de synchronisation
Le problème des lecteurs et rédacteurs

42 / 54
 Introduction
The Critical-section problem
Sémaphore Conclusion
Problème classique de synchronisation
Les Moniteurs

Problème classique de synchronisation

Le problème des lecteurs et rédacteurs

Il existe plusieurs variations du problème des lecteurs et rédacteurs

prenant en compte les priorités.
le 1er problème : Aucun lecteur ne devrait attendre parce qu'un
rédacteur attend ⇒ état de famine : manque de ressource et un
rédacteur pourra ne jamais entrer ;
le second problème : un rédacteur est prêt, il eectue son écriture le
plus vite possible, aucun nouveau lecteur ne peut commencer à lire
⇒ état de famine
Exercice : Modiez le code de manière à empêcher les lecteurs d'accéder
à la base si un au moins des rédacteurs est en attente.
Si la ressource est utilisée par un lecteur :
- Tout écrivain est mis en attente.
- Tout lecteur est accepté s'il n'y a pas d'écrivain en attente.

- Tout lecteur est mis en attente s'il y a un écrivain en attente.

43 / 54
Belarbi SI2 V1.0 Janvier 2025 (2024-2025)
 Introduction
The Critical-section problem
Sémaphore Conclusion
Problème classique de synchronisation
Les Moniteurs

Problème classique de synchronisation

Le problème du diner des philosophes

Le diner des philosophes

Il s'agit d'un problème classique de synchronisation posé et résolu par
Dijkstra [1965] qui modélise des processus qui entre en concurrence pour
un accès exclusif à un nombre limité de ressources.
C'est une représentation simple du besoin d'allouer plusieurs ressources
parmi plusieurs process sans rencontrer le problème de l'inter-blocage ou
de la famine.

TD_Sémaphores_Fiche3

44 / 54
Belarbi SI2 V1.0 Janvier 2025 (2024-2025)
 Problème classique de synchronisation
Le problème Producteur/consommateur

De nombreuses applications sont construites sur le modèle client ser-

veur : Interaction entre un client qui fait une demande et un serveur
qui fournit une réponse. Il est largement utilisé dans les architectures
réseau.

45 / 54
 Problème classique de synchronisation
Le problème Producteur/consommateur

De nombreuses applications sont construites sur le modèle client ser-

veur : Interaction entre un client qui fait une demande et un serveur
qui fournit une réponse. Il est largement utilisé dans les architectures
réseau.
Producteur-consommateur : Modèle où un producteur génère des don-
nées que le consommateur utilise. Il est souvent utilisé pour gérer les
ux de données et la synchronisation entre processus dans des sys-
tèmes concurrents.

45 / 54
 Problème classique de synchronisation
Le problème Producteur/consommateur

De nombreuses applications sont construites sur le modèle client ser-

veur : Interaction entre un client qui fait une demande et un serveur
qui fournit une réponse. Il est largement utilisé dans les architectures
réseau.
Producteur-consommateur : Modèle où un producteur génère des don-
nées que le consommateur utilise. Il est souvent utilisé pour gérer les
ux de données et la synchronisation entre processus dans des sys-
tèmes concurrents.
Les cadences de production et de consommation peuvent varier au
cours du temps
 Problème classique de synchronisation
Le problème Producteur/consommateur

De nombreuses applications sont construites sur le modèle client ser-

veur : Interaction entre un client qui fait une demande et un serveur
qui fournit une réponse. Il est largement utilisé dans les architectures
réseau.
Producteur-consommateur : Modèle où un producteur génère des don-
nées que le consommateur utilise. Il est souvent utilisé pour gérer les
ux de données et la synchronisation entre processus dans des sys-
tèmes concurrents.
Les cadences de production et de consommation peuvent varier au
cours du temps
augmenter la probabilité d'exécution parallèle du producteur et du
consommateur, ceux-ci communiquent par l'intermédiaire d'un tam-
pon de N cases
 Problème classique de synchronisation
Le problème Producteur/consommateur

De nombreuses applications sont construites sur le modèle client ser-

veur : Interaction entre un client qui fait une demande et un serveur
qui fournit une réponse. Il est largement utilisé dans les architectures
réseau.
Producteur-consommateur : Modèle où un producteur génère des don-
nées que le consommateur utilise. Il est souvent utilisé pour gérer les
ux de données et la synchronisation entre processus dans des sys-
tèmes concurrents.
Les cadences de production et de consommation peuvent varier au
cours du temps
augmenter la probabilité d'exécution parallèle du producteur et du
consommateur, ceux-ci communiquent par l'intermédiaire d'un tam-
pon de N cases
Le principal dé dans le modèle producteur-consommateur est la ges-
tion des ressources partagées (par exemple, une mémoire tampon)
 Problème classique de synchronisation
Le problème Producteur/consommateur

De nombreuses applications sont construites sur le modèle client ser-

veur : Interaction entre un client qui fait une demande et un serveur
qui fournit une réponse. Il est largement utilisé dans les architectures
réseau.
Producteur-consommateur : Modèle où un producteur génère des don-
nées que le consommateur utilise. Il est souvent utilisé pour gérer les
ux de données et la synchronisation entre processus dans des sys-
tèmes concurrents.
Les cadences de production et de consommation peuvent varier au
cours du temps
augmenter la probabilité d'exécution parallèle du producteur et du
consommateur, ceux-ci communiquent par l'intermédiaire d'un tam-
pon de N cases
Le principal dé dans le modèle producteur-consommateur est la ges-
tion des ressources partagées (par exemple, une mémoire tampon)
Un producteur peut produire des données plus rapidement que le
consommateur ne peut les traiter, et inversement.
 Introduction
The Critical-section problem
Sémaphore Conclusion
Problème classique de synchronisation
Les Moniteurs

Problème classique de synchronisation

Le problème Producteur/consommateur

Buer Overow (dépassement de tampon) : Si le consommateur ne

consomme pas les données assez vite, le tampon dans lequel les don-
nées sont stockées pourrait déborder.
Underow (pénurie de données) : Si le producteur ne produit pas
susamment de données pour satisfaire le consommateur, ce dernier
pourrait se retrouver à attendre sans rien à traiter.

46 / 54
Belarbi SI2 V1.0 Janvier 2025 (2024-2025)
 Problème classique de synchronisation
Le problème Producteur/consommateur

TD_Sémaphores_Fiche3
47 / 54
 Introduction
The Critical-section problem
Sémaphore Conclusion
Problème classique de synchronisation
Les Moniteurs

Conclusion sur les sémaphores

Les sémaphores sont un excellent mécanisme pour gérer la mise en

attente de processus.
Lorsqu'il faut gérer la mise en attente en combinaison avec la mani-
pulation d'un compteur, les sémaphores sont très bien adaptés.
L'utilisation des sémaphores binaires indique quelles dicultés appa-
raissent lorsque l'on combine l'attente implémentée par un sémaphore
avec la manipulation d'une autre structure de donnée.
Il serait intéressant d'avoir une solution systématique pour gérer ce
type de problème.

48 / 54
Belarbi SI2 V1.0 Janvier 2025 (2024-2025)
 Introduction
The Critical-section problem
Sémaphore
Problème classique de synchronisation
Les Moniteurs

Les Moniteurs

Quel est le problème avec les sémaphores ? ? ?

Les sémaphores représentent un énorme progrès par rapport à

l'implémentation load/store équivalente, mais ils présentent les
inconvénients suivants :
- Il s'agit essentiellement de variables globales partagées.
- il n'y a pas de lien linguistique entre le sémaphore et les données
auxquelles le sémaphore contrôle l'accès.
- L'accès aux sémaphores peut provenir de n'importe quel endroit du
programme.
- Ils ont deux fonctions : l'exclusion mutuelle et les contraintes
d'ordonnancement.
- Il n'y a pas de contrôle ou de garantie d'utilisation correcte.

Solution : utiliser une primitive de niveau supérieur appelée

moniteur.
49 / 54
Belarbi SI2 V1.0 Janvier 2025 (2024-2025)
 Les Moniteurs
Les moniteurs d'Hoare

- Les moniteurs sont des primitives de synchronisation, introduit par

Hoare en 1973, initialement proposées dans les langages objet. Il est
utilisé actuellement dans des langages tel que ADA ou Java et
implémenté au sein de systèmes d'exploitation.
- Le moniteur se positionne sur une classe et les mutexes sur ses
méthodes et sont basés sur des variables condition. elle sont forcement
privée et inaccessible à l'extérieur de la classe.
Moniteur = variables globales + sections critiques d'un même problème
 Les Moniteurs
Les moniteurs d'Hoare

Pour assurer l'exclusion mutuelle, à tout moment un processus au plus

est actif dans le moniteur.
Si un processus est actif dans le moniteur et un autre demande à y
accéder (appelle une procédure du moniteur), ce dernier est mis en
attente.
C'est le compilateur qui se charge de cette gestion. Pour ce faire, il
rajoute au moniteur le code nécessaire pour assurer l'exclusion mu-
tuelle.
Cette solution est plus simple que les sémaphores et les compteurs
d'événements, puisque le programmeur n'a pas à se préoccuper de
contrôler les accès aux sections critiques.
La majorité des compilateurs utilisés actuellement ne supportent pas
les moniteurs (à l'exception de JAVA, C#).

51 / 54
 Les Moniteurs
Dénition formelle

Un moniteur dénit un verrou et zéro ou plusieurs variables de

condition pour gérer l'accès concurrent aux données partagées.
Le moniteur utilise le verrou pour s'assurer qu'un seul thread est
actif dans le moniteur à tout moment.
Le verrou permet également l'exclusion mutuelle des données
partagées.
Les variables de condition permettent aux threads de s'endormir à
l'intérieur des sections critiques, en libérant leur verrou en même
temps que la mise en veille du thread.
Opérations de contrôle :
Encapsule les données partagées que vous souhaitez protéger.
Acquiert le mutex au début.
Opère sur les données partagées.
Libère temporairement le mutex si l'opération ne peut pas se
terminer.
Réacquiert le mutex lorsqu'elle peut continuer.
Libère le mutex à la n.

52 / 54
 Les Moniteurs
Mise en oeuvre en Java

- Il est simple de transformer une classe Java en moniteur :

- Rendre toutes les données privées
- Rendre toutes les méthodes synchronisées (ou au moins celles qui ne
sont pas privées)

class Queue{
private ... ; // queue data

public void synchronized Add( Object item ) {

put item on queue ;
}

public Object synchronized Remove() {

if queue not empty {
remove item ;
return item ;
}
}
53 / 54
 Les Moniteurs
Exemple Banque

Moniteur Compte
{ int solde = 0 ;
void Deposer (int montant) // section critique pour le dépôt
{ solde = solde + montant ;
}
void retirer (int montant) //section critique pour le retrait
{ if (solde >= montant)
solde = solde  montant ;
}
}