Université de Médéa

Faculté des Sciences,

Département de Mathématiques et Informatique

Note de cours

Système d’Exploitation 2

Dr. KHELDOUN Ahmed

Maitre de Conférence, Université de Médéa.

Filière Informatique (Licence)

Spécialité Systèmes Informatiques (SI)
Niveau L3

Année Universitaire 2023‐2024

 Objectifs :
- Inculquer à l’étudiant les concepts et les outils de base des systèmes d’exploitation.
- Introduire la problématique du parallélisme dans les systèmes d’exploitation et étudier
la mise en œuvre des mécanismes de synchronisation, de communication dans
l’environnement centralisé.

Recommandations :
- Il est conseillé d’utiliser un système d’exploitation (UNIX par exemple) comme exemple
en termes d’outils pour chaque concept étudié.
- Prévoir des TPs pour la mise en application des concepts étudiés.

Faculté des Sciences vi Département de Mathématiques et Informatique

 Table de Matières

Chapitre 1 : NOTION DE PARALLELISME, DE COOPERATION ET DE COMPETITION

1. Introduction aux S.E ........................................................................................................................ 1

2. Processus ......................................................................................................................................... 1

A. Définition ..................................................................................................................................... 1

B. États d’un processus .................................................................................................................... 1

Les processus passent par des états discrets différents. On dit qu’un processus est : ..................... 1

C. Processus dans Unix .................................................................................................................... 1

D. Relation entre processus ............................................................................................................. 2

3. Système de tâches et notion de parallélisme ................................................................................. 3

A. Modèle de représentation de processus (décomposition en tâches)......................................... 3

B. Parallèlisation de tâches dans un système de tâches ................................................................. 4

4. Appel fork et threads ...................................................................................................................... 7

Chapitre 2 : SYNCHRONISATION
1. Notion de ressources..................................................................................................................... 11

2. Problème de l’exclusion mutuelle ................................................................................................. 11

A. Propriétés de l’exclusion Mutuelle (E.W. Dijkstra).................................................................... 13

B. Solutions Matérielles ................................................................................................................. 13

C. Solutions Logicielles................................................................................................................... 14

3. Application des sémaphores pour quelques problèmes de synchronisation ............................... 15

4. Moniteurs ...................................................................................................................................... 18

5. Régions critiques ........................................................................................................................... 26

Chapitre 3 : COMMUNICATION ENTRE PROCESSUS

1. Introduction ................................................................................................................................... 30

2. Communication par variables partagées (modèles : producteur/ consommateur) : ................... 30

Faculté des Sciences vi Département de Mathématiques et Informatique

3. Communication par échange de messages : ................................................................................. 30

4. Communication interprocessus sous UNIX : ................................................................................. 31

Chapitre 4 : INTERBLOCAGE
1. Introduction ................................................................................................................................... 41

2. Interblocage................................................................................................................................... 41

A. Définition de l’interblocage (deadlock) ..................................................................................... 41

B. Conditions d’interblocage ......................................................................................................... 42

C. Modèles d’interblocage............................................................................................................. 42

3. Formalisation de l’état d’un système ............................................................................................ 42

4. Traitements des interblocages ...................................................................................................... 46

5. Conclusion : Approche combinée de traitement de l’interblocage .............................................. 52

Faculté des Sciences vi Département de Mathématiques et Informatique

Liste de Figures

Figure 1. États d’un processus ............................................................................................................... 1

Figure 2. État zombie ............................................................................................................................. 1

Figure 3. Solution à base de l’attente active.......................................................................................... 3

Figure 4. Blocage d'un processus ........................................................................................................... 3

Figure 5.Exemple d'un graphe de précédence ...................................................................................... 4

Figure 6. Composition parallèle de graphes de précédence ................................................................. 5

Figure 7. Spécification dans un langage évolué ..................................................................................... 5

Figure 8. Appel fork ................................................................................................................................ 7

Figure 9. Graphe de tâches correspond à l'appel fork ........................................................................... 7

Figure 10. Exemple de code avec appel fork ......................................................................................... 7

Figure 11. Utilisation de concept des threads ....................................................................................... 8

Figure 12. Schéma générale de l'utilisation du thread .......................................................................... 9

Figure 13. Exemple de code avec utilisation des threads ...................................................................... 9

Figure 14. Résultat d'exécution de code de la Figure 13 ..................................................................... 10

Figure 15. Exemple introductif – réservation de vols .......................................................................... 11

Figure 16. Problème d'exclusion mutuelle (Ordonnancement en temps partagé) ............................. 12

Figure 17. Protocole d'utilisation d'une section critique ..................................................................... 12

Figure 18. Solution de problème de réservation par les sémaphores ................................................. 15

Figure 19. Exemple de solution du problème Producteur/Consommateur avec sémaphores ........... 16

Figure 20. Exemple de solution du problème Lecteur/Rédacteur avec sémaphores.......................... 17

Figure 21. Exemple de solution du problème de Rendez‐vous ........................................................... 18

Figure 22. Schéma globale de moniteur .............................................................................................. 19

Figure 23. Exemple de solution du problème Producteur/Consommateur avec moniteur ................ 20

Faculté des Sciences vi Département de Mathématiques et Informatique

Figure 24. Exemple de solution du problème Lecteur/Rédacteur avec moniteur .............................. 21

Figure 25. Exemple de solution du problème de Rendez‐vous avec moniteur ................................... 21

Figure 26. Allocation de ressources avec moniteur ............................................................................. 22

Figure 27. Rendez‐vous à N processus avec moniteur ........................................................................ 22

Figure 28. Allocation des ressources avec moniteur de KESSELS ........................................................ 24

Figure 29. Problème de Rendez‐vous de N processus avec moniteur de KESSELS.............................. 25

Figure 30. Allocation de ressources avec moniteur de priorité ........................................................... 26

Figure 31. Utilisation d'une variable partagéé dans deux régions critiques ........................................ 27

Figure 32. Région critiques imbriquées ............................................................................................... 27

Figure 33. Exemple de solution de Problème de Producteur/Consommateur avec région ................ 28

Figure 34. Exemple de solution de problème Lecteur/Rédacteur avec région ................................... 29

Figure 35. Exemple de communication directe entre un producteur et un consommateur .............. 30

Figure 36. Tune ordinaire..................................................................................................................... 31

Figure 37. Code d'utilisation de tube ordinaire ................................................................................... 32

Figure 38. Envoi d'un message via le tube nommé ............................................................................. 33

Figure 39. Réception d'un message via le tube nommé ...................................................................... 33

Figure 40. Situation d'interblocage avec les tubes nommés ............................................................... 34

Figure 41. La commande ipcs ............................................................................................................... 34

Figure 42. Segment partagé entre deux processus ............................................................................. 35

Figure 43. Code d'utilisation d'un segment partagé ............................................................................ 36

Figure 44. Code d'utilisation une file de messages .............................................................................. 37

Figure 45. Code d'utilisation de sémaphore ........................................................................................ 39

Figure 46. Utilisation croisée de 2 ressources critiques ...................................................................... 41

Figure 47. Allocation partielle d’une ressource ................................................................................... 41

Figure 48. Graphe d’allocation de ressources ..................................................................................... 45

Faculté des Sciences vi Département de Mathématiques et Informatique

Figure 49. Graphe d'allocation de ressources avec une situation d'interblocage ............................... 45

Figure 50.Algorithme du Banquier....................................................................................................... 48

Figure 51. Algorithme TestSain ............................................................................................................ 50

Faculté des Sciences vi Département de Mathématiques et Informatique

 Chapitre 1
NOTION DE PARALLELISME, DE COOPERATION ET DE COMPETITION

1. Introduction aux S.E

Un S.E est un ensemble de programmes qui coopèrent à la gestion des ressources de la machine
(ordinateur) [4].
Les principaux objectifs d’un S.E sont :
 Gestionnaire de ressource : Le S.E permet l’ordonnancement et le contrôle de
l’allocation des processeurs, des mémoires et des périphériques d’E/S entre les
différents programmes qui y font appel.
 Présenter une machine virtuelle à l’utilisateur : Son rôle est de masquer des
éléments fastidieux liés aux matériel comme les interruptions, les horloges, la
gestion de la mémoire, la gestion de processus, …

2. Processus

La notion de processus [5] constitue un modèle simple et efficace pour représenter l‘exécution
concurrente de tâches au sein d’un système d’exploitation multitâches.

A. Définition

Un processus représente l’exécution d’un programme comportant des instructions et

des séquences. C’est une entité dynamique (active) créée à un instant donné, qui
disparaît en général au bout d’un temps fini.

NB : différence entre processus et programme : le programme est une description

statique ; le processus est une activité dynamique (il y a un début, un déroulement et
une fin, il a un état qui évolue au cours du temps).
 Exemple de processus :
- Copier un fichier sur disque
- Impression la fiche de paie

B. États d’un processus

Les processus passent par des états discrets différents. On dit qu’un processus est :

- Élu (en Exécution) : si le processus est en cours d’exécution.

- Prêt : si le processus dispose de toutes les ressources nécessaires à son
exécution à l’exception du processeur.
- Bloqué : si le processus attend qu’un événement se produit pour progresser.

Faculté des Sciences Département de Mathématiques et Informatique

1
 Chapitre 1 : NOTION DE PARALLELISME, DE COOPERATION ET DE COMPETITION

Les transitions entre ces trois états sont matérialisées par l’automate
suivant (Figure 1) :

Nouveau
Terminé
création
2 fin
Prêt Élu

1
4 3
Bloqué

Figure 1. États d’un processus

La signification des quatre transitions est la suivante.

1. Le processus a épuisé le quantum de temps qui lui a été attribué.
L’ordonnanceur élit un autre processus parmi les processus prêts,
2. L’ordonnanceur élit ce processus parmi les processus prêts,
3. Blocage du processus élu dans l’attente d’un évènement (E/S ou autre)
4. Réveil du processus bloqué après disponibilité de l’événement bloquant
(Fin E/S, etc…)
NB : Sous UNIX, il y’a un autre état du processus appelé état « zombie » (Figure 2). En effet,
un processus zombie est un processus qui s’est terminé mais dont les ressources n’ont
pas encore été libérées. Il est de la responsabilité du processus père de libérer les
ressources ocupées par ses fils zombies mais il faut que le fils l’avertisse qu’il a terminé.
Un processus zombie est signalé par la mention <defunct>.

Père

Fils
Fork()

Exit(1)

État zombie
du fils

Figure 2. État zombie

C. Processus dans Unix

- Un processus est identifié par un numéro PID,

- La commande ps donne la liste des processus en cours d’exécution,
- La commande fork() crée un nouveau processus,

Faculté des Sciences Département de Mathématiques et Informatique

1
 Chapitre 1 : NOTION DE PARALLELISME, DE COOPERATION ET DE COMPETITION

- getpid() : obtenir le numéro du processus courant.

- getuid() : obtenir le numéro d’usager auquel appartient le processus,
- kill(PID) : tuer un processus spécifié par PID.
- sleep(n) : se bloquer pendant n secondes.
- exit() : terminaison d’un processus.
- wait() : mise en sommeil sur la terminaison d’un fils.

NB : Lors du démarrage de système Unix, deux processus sont crées :

- Swapper(PID = 0) qui gère la mémoire,
- Init(PID = 1) qui crée tous les autres processus.

D. Relation entre processus

Dans un système, plusieurs processus peuvent se dérouler simultanément. Ces

processus résultent de l’exécution de programmes. Durant leur évolution, les
processus d’un système interagissent les uns avec les autres. Selon que les processus
se connaissent mutuellement ou pas, ces interactions en deux types qui sont :
Coopération / Compétition.
1. Compétition : C’est la situation dans laquelle plusieurs processus doivent
utiliser simultanément une ressource à accès exclusif (ressource ne pouvant
être utilisée que par un seul processus à la fois (ressources critiques)).
Exemples :
- Processeur (cas du pseudo‐parallélisme)
- Imprimante
 Une solution possible (mais non la seule) : faire attendre les processus demandeurs
jusqu’à ce que l’occupant actuel ait fini (premier arriver, premier servi).
2. Coopération : C’est la situation dans laquelle plusieurs processus collaborent
à une tâche commune et doivent synchroniser pour réaliser cette tâche.
Un processus est dit coopératif s’il peut affecter les autres processus en cours
d’exécution dans le système ou être affecté par eux.
Exemples :
- P1 produit un fichier, p2 imprime le fichier,
- P1 met à jour un fichier, p2 consulte le fichier,
NB : La synchronisation se ramène au cas suivant : un processus doit attendre
qu’un autre processus ait franchi un certain point de son exécution.
Remarque : Notons que, pour les deux types de relations (compétition ou
coopération), on doit faire attendre un processus. Comment réaliser cette
attente ?

Faculté des Sciences Département de Mathématiques et Informatique

2
 Chapitre 1 : NOTION DE PARALLELISME, DE COOPERATION ET DE COMPETITION

- Solution 1 : attente active (Figure 3)

P1 P2
while (resource occupée) ressource occupée = true;
{} utiliser resource;
ressource occupée = true; ressource occupée = false ;

Figure 3. Solution à base de l’attente active

Inconvénient : l’attente active monopolise le processeur et donc dégrade la

performance globale de la machine.
- Solution 2 : blocage du processus
On définit un nouvel état pour les processus, l’état bloqué. L’exécution d’un
processus bloqué est arrêtée, jusqu’à son réveil explicite par un autre processus ou
par le système (Figure 4).

blocage

actif bloqué
réveil
…
sleep(5);/* se bloquer pendant 5 secondes */
…

Figure 4. Blocage d'un processus

3. Système de tâches et notion de parallélisme

A. Modèle de représentation de processus (décomposition en tâches)

On appelle tâche une unité élémentaire de traitement ayant une cohérence logique.
Si l’exécution du processus P est constituée de l’exécution séquentielle des tâches
T1, T2, …, Tn, on écrit :
P = T1T2…Tn
A chaque tâche Ti est associé une date de début ou d’initialisation di et une date
de terminaison ou de fin fi.
Remarque1 : On parle alors de l’initialisation (lecture des paramètres d’entrée,
chargement d’information) et de la terminaison (écriture des résultats, libération des
ressources, sauvegarde d’information) d’une tâche.
Remarque2 : A toute suite de tâches T1T2…Tn élémentaires est associée une suite
d1f1d2f2…dnfn d’initialisations et de terminaisons de tâches. On appelle une telle
suite un mot de l’alphabet A = {d1, f1, d2, f2,… , dn, fn }.
Reamrque3 : L’ensemble de ces mots décrivent tous les comportements possibles du
système de tâches S, on l’appelle le langage L(S) de S.

Faculté des Sciences Département de Mathématiques et Informatique

3
 Chapitre 1 : NOTION DE PARALLELISME, DE COOPERATION ET DE COMPETITION

Exemple :
Soit la tâche T correspondant à l’instruction N := N + 1 ;
En utilisant des instructions du langage machine opérant sur un registre R, il est
possible de décomposer la tâche T en trois tâches plus élémentaires :
P = T1T2T3 et A = d1f1d2f2d3f3 Où :
- T1 correspond à l’instruction LOAD R, N qui charge la valeur de N dans le
registre R.
- T2 correspond à l’instruction ADD R, 1 qui incrémente le registre R.
- T3 correspond à l’instruction STORE R, N qui transfert la valeur de R dans N.

B. Parallèlisation de tâches dans un système de tâches

Pour augmenter le degré de multiprogrammation, donc le taux d’utilisation de l’UC,

on peut exécuter en parallèle certaines tâches d’un processus séquentiel. Pour cela,
on introduit la relation de précédence "<" sur un ensemble E de tâches élémentaires.

 Définition : Une relation de précédence sur un ensemble E est une relation vérifiant :
- ∀ T ∈ E, on n'a pas T < T
- ∀ T ∈ E et ∀ T' ∈ E, on n'a pas simultanément T < T' et T' < T
- la relation < est transitive, i.e. si T, T’ et T’’ ∈ E tels que T < T’ et T’ < T’’,
alors T < T’’.
Où Ti < Tj signifie que la terminaison de Ti doit nécessairement intervenir avant
l’initialisation de Tj (en terme de date : fi < dj ).
NB : Si on a ni Ti < Tj, ni Tj < Ti, alors on dit que Ti et Tj sont exécutable en parallèle.
 Définition : On appelle système de tâches S = (E, <), un couple constitué d’un
ensemble E de tâches et d’une relation de précédence "<" sur cet ensemble.
Une relation de précédence peut être représentée par un graphe orienté. Par
exemple, le système de tâches S = ((T1, T2, T3), (Ti<Tj pour i
inférieur à j)) à pour graphe (graphe de précédence (Figure 5)) :

T1 T2 T3

Figure 5.Exemple d'un graphe de précédence

On pourra faire des opérations de produit et de composition parallèle (l’union) des

graphes G1 et G2 de systèmes de tâches.
 Définition : Le produit G1*G2 est le graphe de précédence obtenu à partir des
graphes G1 et G2, en ajoutant des arêtes joignant chaque sommet terminal de G1 à
chaque sommet initial de G2. En effet, cela signifie que G1*G2 reprend les
contraintes de G1 et de G2, avec en plus la contrainte qu’aucune tâche de G2 ne peut
être initialisée avant que toutes les tâches de G1 ne soient terminées.

Faculté des Sciences Département de Mathématiques et Informatique

4
 Chapitre 1 : NOTION DE PARALLELISME, DE COOPERATION ET DE COMPETITION

Exemple :
Prenons les deux graphes de précédences suivants. La Figure 6 montre la
composition parallèle de ces deux graphes de précédences.

T1 T1

T2 T3 T6 T7 T2 T3
* =
T4 T5
T8
T4 T5

G1 G2 T6 T7

T8
G1*G2

Figure 6. Composition parallèle de graphes de précédence

Question : Définir l’opération de composition parallèle (Union) sur les graphes de

précédences (G1 // G2). Montrer la par un exemple.
 Spécification dans les langages évolués :
Certains langages permettent d’exprimer la mise en séquence et en parallèle de
système de tâches.
- La mise en séquence : P1 ; P2 ; pour des programmes associés à des systèmes de
tâches S1 et S2.
- La mise en parallèle : parbegin P1 ; P2 ; parend ;

Exemple : soit le programme suivant (Figure 7) :

debut
parbegin
lire a ; lire b ;
parend
parbegin
c  a * a ; d  b * b;
parend
ec+d;
fin

Figure 7. Spécification dans un langage évolué

Faculté des Sciences Département de Mathématiques et Informatique

5
 Chapitre 1 : NOTION DE PARALLELISME, DE COOPERATION ET DE COMPETITION

 Conditions de Bernstein :
Soit I une instruction d’un programme, on dénote par :
- R(I) : l’ensemble des variables de l’instruction I qui ne changent pas par
l’exécution de l’instruction I.
- W(I): l’ensemble des variables de l’instruction I qui sont mises à jour par
l’instruction I.
On dira que deux instructions I1 et I2 peuvent s’exécuter en parallèle si les
conditions suivantes sont satisfaites :
 R(I1)∩ W(I2) = Ø
 W(I1)∩ R(I2) = Ø
 W(I1)∩ W(I2) = Ø
Exemple : soit le programme suivant :
Début lire(a) ; lire(b) ; ca+b ; écrire(c) ; Fin.
L’instruction lire(b)ne peut s’exécuter en parallèle avec ca+b car :
W(lire(b))∩ R(ca+b) = {b}
A. Parallélisme maximal :
Définition 1: Soit S = (E, <) un système de tâches. T1 et T2 sont dites non
interférentes vis‐à‐vis de S si :
- Ou bien T1 est un prédécesseur ou successeur de T2,
- Ou bien R(T1)∩ W(T2)= W(T1)∩ R(T2)= W(T1)∩ W(T2)= Ø
(conditions de Bernstein)
Définition 2 : Soit S = (E, <) un système de tâches. Si les tâches sont 2 à 2 non
interférentes alors il est déterminé.
Définition 3 : Un système de tâches de parallélisme maximal est un système
déterminé dont le graphe de précédence vérifie la propriété : la suppression de
tout arc (T1,T2) du graphe G entraîne l’interférence des tâches T1 et T2.
Théorème : Soit S = (E, <) un système déterminé. Il existe un unique système S’ de
parallélisme maximal équivalent à S. S’ = (E, <’) avec <’ fermeture transitive1 de la
relation : R = {(T1, T2)| T1< T2 et (R(T1)∩ W(T2)≠Ø ou W(T1)∩ R(T2)≠Ø
ou W(T1)∩ W(T2)≠Ø) et (W(T1)≠Ø et W(T2)≠Ø)}
En résumé, si on n’a pas les conditions de Bernstein satisfaites, on crée un arc
(relation R).
L’algorithme de construction de système S’ découle du théorème :
- Construire le graphe de R,
- Éliminer tous les arcs (T1, T2) redondants, i.e. tels qu’il existe un chemin de
T1 à T2 contenant plus d’un arc.

1
Déf : La fermeture transitive d'un graphe G= (X, A) est la relation transitive contenant la relation (X, A).
Il s’agit d’un graphe G*= (X, *) tel que : (x,y)* ssi il existe un chemin f dans G d’origine x et
d’extrémité y.

Faculté des Sciences Département de Mathématiques et Informatique

6
 Chapitre 1 : NOTION DE PARALLELISME, DE COOPERATION ET DE COMPETITION

4. Appel fork et threads

Il existe deux façons dans le système UNIX d’exprimer le parallélisme :

- Création de processus par l’appel "fork()",
- Utilisation des "Threads".
 Solution des processus : Regardons comment l’utilisation d’un appel à la fonction
"fork()" peut être exprimée sous la forme d’un graphe de tâches (Figure 8) :
Père Fils

debut
T0
T1

debut

pid= fork(); pid= fork();

T2

fin

Figure 8. Appel fork

Cela s’écrit en pseudo‐code (Figure 9) :

D’où le graphe de tâches correspondant :

début
T0 ;
T1 ;
parbegin T2 ; T2 parend ;
fin ;

Figure 9. Graphe de tâches correspond à l'appel fork

La Figure 10 montre un code avec appel fork.

pid=fork(); code correspondant à

if (pid==0) l’exécution du processus fils
{
printf(“je suis le fils, mon PID =
%d”, getpid());
}
else code correspondant à
{ l’exécution du processus père
printf(“je suis le père, mon PID =
%d”, getpid());
}

Figure 10. Exemple de code avec appel fork

Faculté des Sciences Département de Mathématiques et Informatique

7
 Chapitre 1 : NOTION DE PARALLELISME, DE COOPERATION ET DE COMPETITION

 Solution des Threads :

Idée : Un processus est défini par les ressources qu’il utilise et par l’emplacement
mémoire sur lequel il s’exécute. Il serait intéressant que les ressources soient
partagées et que l’on puisse y accéder d’une manière concurrentielle.
Solution : Création de plusieurs threads à l’intérieur du même processus.
Définition : Un thread est un processus léger. En effet, le concept de thread a pour
objectif de permettre à plusieurs threads d’exécution de partager un jeu de
ressources pour travailler ensemble afin d’accomplir une tâche donnée (Figure 11).

Figure 11. Utilisation de concept des threads

Remarque :
 Le terme multithreading est employé pour décrire la situation dans laquelle
plusieurs threads sont présents dans le même processus.
 L’utilisation de fork génère la poursuite de l’exécution au même emplacement
avec un code de retour différent, tandis qu’un nouveau thread commence son
exécution avec la fonction passée en paramètre.
a. Manipulation des threads (utilisation de la norme POSIX) :
- Création de threads
int pthread_create(
pthread_t *tid, // sert à récupérer le TID du thread créé
const pthread_attr_t *attr,
// sert à préciser les attributs du thread `(taille de la pile, priorité….)
//attr = NULL pour les attributs par défaut
void * (*func) (void*), // est la fonction à exécuter par le thread
void *arg); //le paramètre de la fonction.
Cette fonction permet de créer un nouveau thread, elle renvoie 0 s'elle réussit, sinon
elle renvoie une valeur non nulle identifiant l'erreur qui s'est produite.
- Attente la fin d’un thread
void pthread_join( pthread_t tid,
void *status);// sert à récupérer la valeur de retour et l’état de
terminaison.

Faculté des Sciences Département de Mathématiques et Informatique

8
 Chapitre 1 : NOTION DE PARALLELISME, DE COOPERATION ET DE COMPETITION

Cette fonction faire un attente d’un thread. L’équivalent de waitpid des processus
sauf qu’on doit spécifier le tid du thread à attendre.
- Terminaison de thread
void pthread_exit( void * status);
Termine l’exécution d’un thread.
- void pthread_self(void); retourne l’identifiant du Thread.
Exemple : Ce programme crée un autre thread qui va montrer qu’il partage des
variables avec le thread original, et permettre au "petit nouveau" de renvoyer un
résultat à l’original.

Thread principal pthread_create un_thread

pthread_join pthread_exit

Figure 12. Schéma générale de l'utilisation du thread

thread.c
#include <stdio.h>
#include <pthread.h>
void *fonction_de_thread(void *arg);
int val = 0;
int main (void *arg)
{ fonction exécutée par le
pthread_t un_thread; adresse de l’identifiant
thread créé
void *resultat_de_thread; du thread créé
printf("Père %d: Début (val = %d)\n", pthread_self, val);
pthread_create(&un_thread, NULL, fonction_de_thread, (void*)val);
printf("Père %d: création du thread %d\n", pthread_self, un_thread);

pthread_join(un_thread, &resultat_de_thread);
paramètre passé
printf("Père %d: Début (val = %d)\n", pthread_self, val);
return 0; à la fonction
}//fin main
identifiant du thread
void *fonction_de_thread(void *arg)
attendu
{
sleep(1);
printf(Fils %d: Début \n", pthread_self());
sleep(3);
val = 10;
printf("Fils %d: Modification (val = %d)\n", pthread_self, val);
sleep(1);
printf(Fils %d: Fin \n", pthread_self());
pthread_exit(NULL); adresse de l’objet renvoyé au
} thread appelant (ici NULL)

Figure 13. Exemple de code avec utilisation des threads

Faculté des Sciences Département de Mathématiques et Informatique

9
 Chapitre 1 : NOTION DE PARALLELISME, DE COOPERATION ET DE COMPETITION

NB : compilation : gcc −D_REENTRANT thread.c −o thread −lpthread

permet l’utilisation établir un lien avec la
de code réentrant bibliothèque de threads

Résultat

Père -1208662336 : Début (val = 0)

Père -1208662336 : création du thread -1208665200
Fils -1208665200 : Début
Fils -1208665200 : Modification (val = 10)
Fils -1208665200 : Fin
Père -1208662336 : Fin (val = 10)

Figure 14. Résultat d'exécution de code de la Figure 13

Remarque: Une fonction est dite réentrante si elle peut être appelée « simultanément » par
plusieurs threads et renvoyer pour chacun le résultat identique à celui en contexte mono‐thread.

Exercice : donnez un exemple de fonction non réentrante. long random (void).

Faculté des Sciences Département de Mathématiques et Informatique

10
 Chapitre 2
SYNCHRONISATION

1. Notion de ressources

 Définition : Une ressource désigne toute entité dont a besoin un processus pour
s’exécuter. Elle est soit une :
- Ressource matérielle (Processeur, Périphérique)
- Ressource logicielle (variable, fichier).
En plus, la ressource est caractérisée par :
- Un état : libre/ occupée.
- Son nombre de points d’accès (nombre de processus pouvant l’utiliser en
même temps).
 Utilisation d’une ressource par un processus : L’utilisation d’une ressource par un
processus se fait de la manière suivante (trois étapes):
- Allocation
- Utilisation
- Restitution
Les phases d’allocation et de restitution doivent assurer que la ressource est
utilisée conformément à son nombre de points d’accès.
NB : Une ressource avec un seul point d’accès appelée une ressource critique.
Exemple : (ressource matérielle : imprimante)
Allocation : Occupée (1 point d’accès) impression Restitution : Libre (1 point d’accès)

2. Problème de l’exclusion mutuelle

On considère un système permettant à des clients de réserver une place dans un avion
donné « numéro_vol » (Figure 15).

Client1 RESERVATION
Réserver(1666)
N° vol, nb_place
1623, 10
Réserver(1666)
Client2 1644, 5
1666, 1

Client1 Client2

Réservation :
Accéser à (entrée, n°vol) dans la table des vols
Si entrée.nb_place > 0
Alors
Réserver une place
Entrée.nb_place = entrée .nb_place – 1
Fsi

Figure 15. Exemple introductif – réservation de vols

Faculté des Sciences Département de Mathématiques et Informatique
11
 Chapitre 2 SYNCHRONISATION

On considère la situation où deux clients demandent simultanément la réservation d’une

place sur le vol 1666 pour lequel reste une seule place disponible.
NB : les deux processus Réservation s’exécutent en concurrence ; le S.E ordonnance les
deux processus via un algorithme en temps partagé (Figure 16).

Réservation Client 1 Réservation Client 2

Ordonnancement / commutation
Si Nb_place > 0 alors
Si Nb_place > 0 alors
Nb_place = Nb_place – 1
Ordonnancement / commutation //Nb_place= 0
Nb_place = Nb_place – 1
//Nb_place = ‐1 !!!

Figure 16. Problème d'exclusion mutuelle (Ordonnancement en temps partagé)

 Que faut‐il faire ? Intedire au processus Réservation_Client_2 de modifier la

variable nb_place pendant que Réervation_Client_1 manipule cette variable.
 Un seul processus à la fois accède à nb_place (nb_place est une ressource
critique).
 Solution : Exclusion mutuelle
 Définition : Une section critique (SC) est un ensemble de suites d’instructions qui
peuvent produire des résultats imprévisibles lorsqu’elles sont exécutées
simultanément par des processus différents.
Les SC doivent être exécutés en Exclusion Mutuelle. i.e. Avant d’exécuter une SC, un
processus doit s’assurer qu’aucun autre processus n’est en train d’exécuter cette SC.
L’exécution en Exclusion Mutuelle nécessite de définir un protocole d’entré en SC et
un protocole de sortie de SC.
- Protocole d’entré en SC: ensemble d’instructions qui permet cette
vérification et la non progression éventuelle;
- Protocole de sortie de SC: ensemble d’instructions qui permet à un
processus ayant terminé sa SC d’avertir d’autres processus en attente que la
voie est libre.
En fin, la structure des processus devient (Figure 17) :

Début
Section non Critique
Protocole d’entré
SC
Protocole de sortie
Section non critique
Fin.

Figure 17. Protocole d'utilisation d'une section critique

Faculté des Sciences Département de Mathématiques et Informatique

12
 Chapitre 2 SYNCHRONISATION

A. Propriétés de l’exclusion Mutuelle (E.W. Dijkstra)

Il existe quatre conditions nécessaires pour réaliser correctement une exclusion

mutuelle :
- Deux processus ne peuvent être en même temps en dans leurs SC ;
- Pas d’hypothèses sur la vitesse des processus
- Aucun processus suspendu en dehors de sa SC ne doit bloquer les autres
processus.
- Aucun processus ne doit attendre trop longtemps avant d’entrer en SC (attente
borné).
Il existe deux catégories de solution pour l’exclusion mutuelle à savoir : la solution
matérielle et la solution logicielle.

B. Solutions Matérielles

Dans cette catégorie on distingue :

a. Masquage des IT (Monoprocesseurs): Il permet au processeur d’exécuter le
code de la section critique jusqu’à sa fin sans être 'interrompu par un autre
processus.
<Entré en SC> : Masquer les IT.
<Sortie de SC> : Démasquer les IT.
Inconvénients :
- Cette solution ne peut être utilisée dans les systèmes
multiprocesseurs car le faite de masquer les interruptions d'un
processeur n'entraîne pas le masquage des autres processeurs.
- Temps passé en SC est non contrôlable.
b. Test and Set (TS ou TAS) (Multiprocesseurs): c’est une instruction exécutée
par le matériel qui permet de lire et d’écrire le contenu d’un mot de la
mémoire de manière indivisible.
int TAS (int *a, int *b)
{
a = b ;
b=1 ;
}
Cette instruction a deux opérandes, un registre a et un mot b (partageable
entre différents processus) de la mémoire centrale. Elle copie le mot dans le
registre et place la valeur 1 dans le mot.
Exemple d’utilisation : Deux processus partagent une variable occupé. testi
est une variable locale au processus.
<Entré en SC> : TAS (testi, occupé) ;
Tantque testi = 1 faire TAS (testi, occupé) ;
<Sortie de SC> : occupé = 0 ;
Inconvénient:
- Attente active.
Faculté des Sciences Département de Mathématiques et Informatique
13
 Chapitre 2 SYNCHRONISATION

C. Solutions Logicielles2

On distingue :
1. Les verrous : un verrou (en anglais Lock) est un objet système à deux états
(libre/occupé) sur lequel deux opération sont définies :
• verrouiller (v) : Elle permet au processus d’acquérir le verrou v s’il est
libre. S’il n’est pas disponible, le processus est bloqué en aatente de la
ressource.
• déverrouiller (v) : Elle permet au processus de libérer le verrou v qu'il
possédait. Si un ou plusieurs processus étaient en attente de ce verrou,
un seul de ces processus est réactivé et reçoit le verrou.
En tant qu’opérations systèmes, ces opérations sont indivisibles.
Exemple d’utilisation : soit V_Nb_Place une variable de type verrou :
<Entré en SC> : verrouiller(V_Nb_Place);
<Sortie de SC> : déverrouiller(V_Nb_Place);
2. Les sémaphores : Il est introduit par Dijkstra en 1965 pour résoudre le
problème d’exclusion mutuelle.
Définition : Un sémaphore est une variable globale protégé i.e. on peut y
accéder qu’au moyen des trois procédures :
- Init(S, x) : initialiser le sémaphore S à une certaine valeur X ;
- P(S) ou down(S) : Peut‐on passer ? Peut‐on continuer ?
- V(S) ou up(S): Libérer ? vas y ?

Un sémaphore est une structure à deux champs :

- Une variable entière, ou valeur du sémaphore.
- Une file d’attente de processus ou de tâches.

NB : Un sémaphore est dit binaire si sa valeur ne peut être que 0 ou 1,

générale (de comptage) sinon.

1ère Réalisations logicielles :

- Init(S, x) {S.n = x ;}
- P(S) { S.n = S.n - 1 ;
Si S.n <0 alors bloquer le processus en fin de
S.en_attente ;}
- V(S){ S.n = S.n +1 ;
Si S.n <= 0 alors débloquer le processus en tête
de S.en_attente ;}

2
Algorithme de Dekker, Peterson  TDs

Faculté des Sciences Département de Mathématiques et Informatique

14
 Chapitre 2 SYNCHRONISATION

NB : L’initialisation dépend du nombre de processus pouvant effectuer en

même temps « section critique ».
- Exemple : m, si on a m imprimantes identiques.
- Cette implémentation donne à chaque fois dans S.n le nombre de
ressources libres ;
- Lorsque S.n est négative, sa valeur absolue donne le nombre de
processus dans la file d’attente S.en_attente.

2ème Réalisations logicielles :

- P(S){ Si S.n > 0 alors S.n = S.n ‐ 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 S.n :=S.n +1 ;}
Exemple d’utilisation du sémaphore d’exclusion mutuelle :
Init(Mutex, 1) : initialiser le sémaphore Mutex à 1
<Entré en SC> : P(Mutex);
<Sortie de SC> : V(Mutex);
Solution de problème de réservation par les sémaphores :

Mutex : sémaphore
Init(Mutex, 1)
Réservation :
P(Mutex)
Si nb_place > 0 alors // réserver une place
Nb_place = nb_place - 1
Finsi
V(Mutex)

Figure 18. Solution de problème de réservation par les sémaphores

3. Application des sémaphores pour quelques problèmes de synchronisation

• Producteur / consommateur : Un modèle de communication entre

processus avec partage de zone commune (tampon/buffer) est le modèle
producteur / consommateur. En effet, Le producteur doit pouvoir ranger
en zone commune des données qu'il produit en attendant que le
consommateur soit prêt à les consommer. Le consommateur ne doit pas
essayer de consommer des données inexistantes.
Hypothèses :
- les données sont de taille constante

Faculté des Sciences Département de Mathématiques et Informatique

15
 Chapitre 2 SYNCHRONISATION

- les vitesses respectives des deux processus (producteur

consommateur) sont quelconques.

Règles :
- Le producteur ne peut pas ranger un objet si le tampon est plein.
- Le consommateur ne peut pas prendre un objet si le tampon est
vide.
- Le consommateur ne peut prélever un objet que le producteur est
en train de le ranger.
- Si le producteur (resp. consommateur) est en attente parce que
le tampon est plein (resp. vide), il doit être averti dès que cette
condition cesse d'être vraie.
Le tampon peut être représenté par une liste circulaire. On introduit
donc deux variables caractérisant l’état du tampon :
NPLEIN : nombre d'objets dans le tampon (début : 0)
NVIDE : nombre d'emplacements disponibles dans le tampon (N au
début).

initialisation

NPLEIN, NVIDE : sémaphore ;

Init(NPLEIN , 0);
Init(NVIDE , N);

Producteur Consommateur
Répéter
produire un objet Répéter
P(NVIDE) P(NPLEIN)
prélever un objet
déposer un objet
V(NVIDE)
V(NPLEIN) consommer l’objet
Jusqu’à faux Jusqu’à faux

Figure 19. Exemple de solution du problème Producteur/Consommateur avec sémaphores

• Lecteurs/ rédacteurs: Ce problème modélise bien les accès d'un processus

à une base de données. On peut accepter que plusieurs processus lisent la
base en même temps (lecteurs); mais dès qu'un processus écrit dans la
base (rédacteur), aucun autre processus ne doit être autorisé à y
accéder, en lecture ou en écriture.
Solution :
- Pour contrôler les accès à la base, on a besoin de connaître le
nombre de lecteurs qui sont en train de lire de la base (NbLect).

Faculté des Sciences Département de Mathématiques et Informatique

16
 Chapitre 2 SYNCHRONISATION

En effet, ce compteur NbL est un objet partagé par tous les

lecteurs. L’accès à ce compteur doit être exclusif (sémaphore mutex).
- Pour assurer l’accès exclusif à la base par les rédacteurs, on utilise
un autre sémaphore (Redact)
Règles :
- Un lecteur peut accéder à la base, s’il y a déjà un lecteur qui
accède à la base (NbLect >0) ou aucun rédacteur n’est en train
d’utiliser la base.
- Un rédacteur peut accéder à la base, si elle n’est pas utilisée par
les autres.

initialisation
int NbLect = 0;
sémaphore mutex, Redact;
init (mutex, 1) ; Init (Redact, 1) ;
Lecteur Redacteur
P(mutex) ;
NbLect = NbLect + 1 ; P(Redact) ;
Si NbLect=1 alors P(Redact) FinSi Ecritures() ;
V(mutex) ; V(Redact) ;
Lecteurs()
P(mutex) ;
NbLect = NbLect ‐ 1 ;
Si NbLect = 0 alors V(Redact) FinSi
V(mutex) ;

Figure 20. Exemple de solution du problème Lecteur/Rédacteur avec sémaphores

• Synchronisation :
Définition : On dit qu'un processus P est synchronisé avec un
processus Q lorsque l'activité de P (resp. Q) dépend d'un événement
modifié par Q (resp. P).
La synchronisation exige la mise en place d'un mécanisme permettant
à un processus actif de bloquer un autre processus ou de se bloquer
lui‐même ou d'activer un autre processus. L’un des mécanismes utilisé
pour la synchronisation est les sémaphores.
Définition (Rendez‐vous) : Établir un point de rendez‐vous dans le
déroulement de N processus (N est une donnée supposée connue).
Ex : calcul de (a+ b) * (c + d) ‐ (e/f) par trois processus. P2 calcule c + d,
P3 calcule e/f et P1 le résultat.

Faculté des Sciences Département de Mathématiques et Informatique

17
 Chapitre 2 SYNCHRONISATION

Attente

T1 = a+b T4 = T1*T2 res = T4‐T3

P1
T2 = c+d
P2
T3 = e/f
P3

Points de rendez‐vous
initialisation
sémaphore mutex1, mutex2;
init (mutex1, 0) ; Init (mutex2, 0) ;
P1 P2 P3
T1 = a+b ; T2 = c+d ; T3 = e/f ;
P(mutex1) ; V(mutex1) ; V(mutex2) ;
T4 = T1*T2 ;
P(mutex2) ;
res = T4‐T3 ;

Figure 21. Exemple de solution du problème de Rendez‐vous

4. Moniteurs

Définition : Un moniteur est un outil évolué de synchronisation introduits par Brinch &
Hansen en 1972‐73 et Hoare en 1974. Un moniteur comprend : des variables d'état, des
procédures internes, des procédures externes (points d'entrées), des conditions et des
primitives de synchronisation.
Remarques : ‐ La seule manière pour un processus d'accéder à une variable moniteur
est d'appeler une procédure moniteur (procédure externe) qui sont exécutées en EM.
- Au maximum, un seul processus actif dans le moniteur.
- Au lieu d’être dispersées dans les différents processus, les sections critiques
sont transformées en opérations (procédures) d’un moniteur.
Le moniteur utilise des variables de type condition (i.e. définies explicitement par l’attribut
Condition). A chaque variable de ce type est associée une file d’attente de processus. Sur
ces variables on peut appliquer 3 opérateurs indivisibles :
 Wait(c) : bloque le processus courant et le place en attente dans la file d’attente
associée au variable c.

Faculté des Sciences Département de Mathématiques et Informatique

18
 Chapitre 2 SYNCHRONISATION

 Signal(c) : réveille un processus bloqué (en attente de c). Si la file d’attente

associée au variable c est vide, le signal n’est pas mémorisé et son
action sera sans effet. En général, les conditions sont gérées de
manière FIFO.
 non_vide(c) : vrai si aucun processus n'est en attente de c, faux sinon
Remarque (sémantique de la primitive signal):
La primitive Signal telle qu’elle est a été définie risque de provoquer une violation de l’EM
dans le moniteur car deux processus vont se retrouver simultanément actifs à l’intérieur du
moniteur :
- Le processus qui exécute Signal est toujours dans le moniteur
- Le processus réveillé par Signal risque de continuer son exécution dans le
moniteur.
Solutions :
- 1ère solution (Brinch Hansen) : Imposer au programmeur de
n’utiliser Signal que comme la dernière instruction avant de sortir
du moniteur (fin de service). L’inconvénient de cette solution est
qu’elle restreint énormément les possibilités de programmation des
moniteurs.
- 2ème solution (Hoare) : Elle donne la priorité absolue au processus
réveillé et consiste à imposer le blocage momentané du processus
qui exécute Signal jusqu’à ce que le processus réveillé :
 Soit quitté le moniteur
 Soit c’est bloqué à nouveau dans le moniteur.
- 3ème solution : C’est l’inverse de la deuxième :
En plus, le moniteur possède une file d'attente globale. En effet, Si le
moniteur appelé par un processus pour manipuler une donnée partagée,
est occupé, le processus est placé dans cette file d’attente du moniteur. Dès
qu’il est libéré (i.e. lorsque la procédure en cours est terminée ou lors d’un
wait), l’un des processus de la file est choisi et la procédure invoquée est
exécutée.
La Figure 22montre la structure générale d’un moniteur.

Variables partagées
Files d’attentes X
associées aux Y
conditions X et Y File d’attente du moniteur
Procédures (Opérations)

Initialisations des variables

Figure 22. Schéma globale de moniteur

Faculté des Sciences Département de Mathématiques et Informatique

19
 Chapitre 2 SYNCHRONISATION

 Producteur / consommateur :
- Les sections critiques sont les opérations de dépôt et de retrait du
tampon partagé.
- Un dépôt est possible uniquement si le tampon n’est pas plein. Pour
bloquer le producteur, il suffit d’utiliser une variable de condition nplein
et de précéder chaque opération de dépôt par l’action wait(nplein), si le
tampon est plein.
- L’action signal(nplein) sera appelée suite à un retrait d’un buffer plein.
- Un retrait est possible uniquement si le tampon n’est pas vide. Pour
bloquer le consommateur, il suffit d’utiliser une variable de condition
nvide et de précéder chaque opération de retrait par l’action wait(nvide),
si le tampon est vide.
- L’action signal(nvide) sera appelée par l’opération de dépôt dans le cas
d’un dépôt dans un buffer vide.

Moniteur ProdCons procédure entry retirer ()

Debut - Debut
Condition nplein, nvide; Si compteur = 0 alors Wait (nvide)
int compteur ; < retirer un objet>
procédure entry ajouter () // Dépôt compteur = compteur‐1;
Debut Si compteur = N‐1 alors Signal (nplein)
Si compteur = N alors Wait (nplein) Fin
< déposer un objet>
Producteur Consommateur
compteur = compteur+1;
Répéter Répéter
Si compteur = 1 alors Signal (vide)
Produire (objet) ProdCons.retirer ()
Fin
ProdCons . ajouter () Consommer(objet)
Jusqu’à faux Jusqu’à faux
/* début du corps du moniteur*/
compteur = 0 ;
/* fin du corps du moniteur*/
Fin.

Figure 23. Exemple de solution du problème Producteur/Consommateur avec moniteur

 Lecteurs/ rédacteurs (priorité aux lecteurs):

- Les sections critiques sont les opérations debut_lecteur,
fin_lecteur, debut‐ecriture, fin_ecriture.
- Le nombre de lecteurs qui sont en train de lire la BDD est
représenté par NbLect (initialement 0). En plus, l’existence d’une
écriture est repérée par le booléen ecriture (initialement faux).
- Les files d’attente de lecteurs et de rédacteurs sont deux
variables de type condition, désignées par accord_lecture et
accord_écriture.

Faculté des Sciences Département de Mathématiques et Informatique

20
 Chapitre 2 SYNCHRONISATION

Moniteur LectRedact procédure entry debut_ecriture ()

Début Debut
Conditions accord_lecture, accord_écriture; Si (ecriture ou NbLect>0) alors Wait(accord_écriture) ; FinSi
int NbLect ; boolean ecriture; ecriture = vrai ;
procédure entry debut_lecteur () Fin
Debut procédure entry fin_ecriture ()
NbLect++ ; Si ecriture alors Debut
Wait(accord_lecture) ; Signal(accord_lecture) ; FinSi ecriture = faux ;
Fin Si NbLect>0 alors Signal(accord_lecture) ;
Procédure entry fin_lecteur () Sinon Signal(accord_écriture);
Debut FinSi
Nblect‐‐ ; Si Nblect= 0 alors Signal(accord_écriture);FinSi Fin
Fin

/* début du corps du moniteur*/ Lecteur Rédacteur

NbLect = 0 ; ecriture= faux ; LectRedact.debut_lecteur LectRedact.debut_ecriture
/* fin du corps du moniteur*/ Lecteur () Écriture ()
Fin. LectRedact.debut_lecteur LectRedact.debut_ecriture

Figure 24. Exemple de solution du problème Lecteur/Rédacteur avec moniteur

 Synchronisation (Rendez‐vous) : Reprendre le même exemple présenté pour la

partie sémaphore. Il s’agit de calculer l’expression : (a+ b) * (c + d) ‐ (e/f) par
trois processus. P2 calcule c + d, P3 calcule e/f et P1 le résultat.

Moniteur RDV Procédure entry P2_arrive () P1

Début Debut T1 = a+b ;
Boolean arrive2, arrive3 ; arrive2=vrai ; RDV.attendre_P2 ;
Conditions arrive_P2, arrive_P3; Signal(arrive_P2) ; T4 = T1*T2 ;
Procédure entry attendre_P2 () Fin RDV.attendre_P3 ;
Debut Procédure entry P3_arrive () res = T4‐T3 ;
Si non arriv2 alors Wait(arrive_P2) ; FinSi Debut
Fin arrive3=vrai ;
Procédure entry attendre_P3 () Signal(arrive_P3) ;
Debut Fin
Wait(arrive_P3) ;
Fin
/* début du corps du moniteur*/
arrive2= faux ; arrive3=faux ; P2 P3
/* fin du corps du moniteur*/ T2 = c+d ; T3 = e/f ;
Fin. RDV. arrive _P2 ; RDV. arrive _P3 ;

Figure 25. Exemple de solution du problème de Rendez‐vous avec moniteur

Faculté des Sciences Département de Mathématiques et Informatique

21
 Chapitre 2 SYNCHRONISATION

 Exercices :
a) Allocation de ressources : proposer une solution a base des moniteurs pour le
problème d’allocation de ressources à k points d’accès par n (n>k) processus.
Le protocole d’exécution d’un processus est le suivant :
Moniteur AllocRess Pi i=1..n
Début Debut
int NbRes; //nombre de ressources libre …..
Conditions Cond; AllocRess.Allocation;
Procédure entry Allocation () //utilisation
Debut AllocRess.Restitution;
Si NbRes = 0 alors Wait(Cond) ; FinSi ….
NbRes‐‐ ; Fin
Fin
Procédure entry Restitution ()
Debut
NbRes++ ;
Si non non_vide(Cond) alors Signal(Cond) ; FinSi
Fin
/* début du corps du moniteur*/
NbRes = N ;
/* fin du corps du moniteur*/
Fin.

Figure 26. Allocation de ressources avec moniteur

b) Rendez‐vous à N processus : Soient N processus parallèles ayant un point

de rendez‐vous. Un processus arrivant au point de rendez‐vous se met en
attente. Le dernier arrivé réveillera les processus bloqués.

Moniteur Rendez_vous Pi i=1..n

Début Debut
int cpt; …..
Conditions tous_la; Rendez_vous.Arriver ;
Procédure entry Arriver () ….
Debut Fin
cpt++ ;
Si cpt < N alors Wait(tous_la) ; FinSi
Signal(tous_la) ;
cpt=0 ;
Fin
/* début du corps du moniteur*/
cpt = 0 ;
/* fin du corps du moniteur*/
Fin.

Figure 27. Rendez‐vous à N processus avec moniteur

Faculté des Sciences Département de Mathématiques et Informatique

22
 Chapitre 2 SYNCHRONISATION

 Implémentation des moniteurs par les sémaphores :

1. Du moment que l’accès au moniteur est exclusif, un sémaphore binaire
mutex_nom_moniteur, initialisé à 1.
- P(mutex_nom_moniteur) : est exécuté au début de chaque entrée
- V(mutex_nom_moniteur) : est exécuté à la fin.
File d’attente associée au mutex_nom_moniteur = File d’attente du moniteur
2. Pour chaque variable de condition (C) du moniteur :
- Un sémaphore binaire C_mutex initialisé à 0.
File de C_mutex = File d’attente de C
- Sachant que Signal n’a d’effet que s’il y’a au moins un processus bloqué
sur C alors, un compteur C_count du nombre de processus en attente
de C est nécessaire.
3. Quand un processus exécute Signal(C), il attend momentanément, on aura
besoin d’un sémaphore de synchronisation S, initialisé à 0.
File de S = File d’attente des processus en attente momentanément
- L’attente se fait jusqu’à ce que le processus réveillé quitte le moniteur
ou se bloque une autre fois. Donc, en ce moment, ce dernier doit
vérifier si un processus est en attente momentanée pour le réveiller
par V(S). Sachant qu’un processus réveillé par Signal peut réveiller un
autre à son tour. Alors, un compteur S_Count du nombre de processus
bloqués momentanément sur S est nécessaire.
a. À l’entrée du moniteur, on exécute : P(mutex_nom_moniteur)
b. À la sortie du moniteur :
Si S_Count > 0 alors V(S) Sinon V(mutex_nom_moniteur) ; FSi.
c. Wait(C): C_count ++ ; Si (S_count>0) alors V(S) Sinon V(mutex_nom_moniteur) ;
FSi P(C_mutex) ; C_count ‐‐ ;
d. Signal(C):Si (C_count>0) alors S_count ++ ;V(C_mutex); P(S) ; S_count‐‐;FSi
 Critiques et amélioration des moniteurs
 Principal inconvénient : le mode de fonctionnement vu jusqu’ici, vise à assurer
que la condition attendue ne peut être modifiée entre l’exécution du signal et
le réveil du processus. Ce mode de fonctionnement à l’inconvénient de faire
apparaître la condition de franchissement en deux points du programme :
• Avant l’attente
• Avant le réveil
Et de ne pas traiter simplement le cas où plusieurs processus attendent la même
condition (un signal non attendu est perdu, contrairement aux sémaphores).
 Améliorations proposées :
 Amélioration de KESSELS(77) : KESSELS a proposé de changer la
sémantique de la primitive wait(Condition C) : dans cette nouvelle
formulation, C est une expression booléenne faisant intervenir les

Faculté des Sciences Département de Mathématiques et Informatique

23
 Chapitre 2 SYNCHRONISATION

variables globales du moniteur (et éventuellement des paramètres

d’appel).
Wait(C): provoque le blocage du processus qui l’exécute tant que
l’expression C est fausse ; dès que C devient vraie un processus bloqué sur
C est alors réveillé.
Conséquences :
- La primitive Signal devient inutile et par conséquent disparaît.
- Il faut provoquer la réévaluation automatique des conditions C dès
qu’un processus quitte le moniteur ou se bloque à nouveau.

Exemple1 (Gestion d’une ressource critique):

Moniteur AllocRess Pi i=1..n

Début Debut
Boolean Libre ; …..
Condition (Libre); AllocRess.Allocation;
Procédure entry Allocation () //utilisation
Debut AllocRess.Restitution;
Wait(Libre) ; ….
Libre = faux ; Fin
Fin
Procédure entry Restitution ()
Debut
Libre = true ;
Fin
/* début du corps du moniteur*/
Libre = vrai ;
/* fin du corps du moniteur*/
Fin.

Figure 28. Allocation des ressources avec moniteur de KESSELS

Faculté des Sciences Département de Mathématiques et Informatique

24
 Chapitre 2 SYNCHRONISATION

Exemple2 (Rendez‐vous de N processus):

Moniteur Rendez_vous Pi i=1..n

Début Debut
int cpt; …..
Conditions (cpt=N); Rendez_vous.Arriver ;
Procédure entry Arriver () ….
Debut Fin
cpt++ ;
Wait(cpt=N) ;
Si(non_vide(cpt=N)) cpt=0 ;
Fin
/* début du corps du moniteur*/
cpt = 0 ;
/* fin du corps du moniteur*/
Fin.

Figure 29. Problème de Rendez‐vous de N processus avec moniteur de KESSELS

 Avantage : Programmation plus simple : les conditions de franchissement sont

explicitement représentées.
 Inconvénients : Il y a perte d’efficacité par réévaluation automatique de
plusieurs conditions.
 Amélioration de la gestion des files d’attente associée aux conditions :
Cette extension permet de gérer la file d’attente associée à une variable de
type condition par priorités. A cet effet, un paramètre entier relatif P est
spécifié dans la primitive :
Wait(Cond(P)) : l’insertion du PCB du processus qui l’exécute se fera dans la file
associée à Cond mais selon la valeur de la priorité P. Généralement, les PCB
sont ordonnés dans la file par valeurs croissantes de P.
Cette technique permet de faciliter l’écriture de moniteurs gérant des
applications où l’attente des processus se fait par priorités.

Faculté des Sciences Département de Mathématiques et Informatique

25
 Chapitre 2 SYNCHRONISATION

Exemple (Allocateur de ressources avec priorité aux plus petites demandes):

Moniteur AllocRess Pi i=1..n

Début Debut
int NbRes; //nombre de ressources libre …..
Conditions Cond; AllocRess.Allocation(x);
Procédure entry Allocation (int x) //utilisation
Debut AllocRess.Restitution(x);
Si NbRes <x alors Wait(Cond(x)) ; FinSi ….
NbRes = NbRes‐x ; Fin
Fin
Procédure entry Restitution (int x)
Debut
NbRes = NbRes+x;
Si non non_vide(Cond) alors Signal(Cond) ; FinSi
Fin
/* début du corps du moniteur*/
NbRes = N ;
/* fin du corps du moniteur*/
Fin.

Figure 30. Allocation de ressources avec moniteur de priorité

5. Régions critiques

Cet outil a été introduit par Brinch Hansen en 72 et Hoare en 72. L’objectif des régions critiques
est de remédier les problèmes dues à la mal utilisation des sémaphores.
Définition : Une région critique définit une suite d’instructions exécutées en EM et relative à
l’utilisation d’une variable déclarée explicitement comme partagée. En prenant pour exemple de
langage de programmation parallèle le concurrent PASCAL (extension du PASCAL traditionnel
intégrant la gestion des processus). Une variable partagée sera déclarée par l’attribut SHARED :
Var V :Shared t ; où V : nom de la variable, et t : type de la variable.
1) Régions critiques inconditionnelles : Il s’agit de déclarer une variable V partagée ; celle‐
ci ne peut être accessible qu’a l’intérieur d’une région contenant l’instruction de la
forme :
Region V do
Begin
S;
End;
Où : S représente la section critique (i.e. ensemble d’instructions peut être vide).
Lorsque plusieurs processus tentent d’exécuter simultanément des régions associées à
une même variable partagée, un seul est autorisé à poursuivre son exécution. Les autres
resteront bloqués jusqu’à la sortie du processus courant de la région critique (i.e. après

Faculté des Sciences Département de Mathématiques et Informatique

26
 Chapitre 2 SYNCHRONISATION

la dernière instruction de la séquence S). À ce moment là, un seul processus parmi ceux
en attente sera autorisé à entrer en région critique.
Remarques :
- La variable V peut être utilisée dans deux Régions comme suit :
Var V : shared ;

………… …………
Region V do S1 ; Region V do S2 ;
………… …………

Figure 31. Utilisation d'une variable partagéé dans deux régions critiques

- Les Régions peuvent être imbriquées sans inconvénient sauf qu’il

faut éviter le cas d’interblocage.
Exemple :
Processus P1 Processus P2
Region A do Begin Region B do Begin
Region B do S1; Region A do S2;
End ; End ;

Figure 32. Région critiques imbriquées

- Son implémentation est simple. Il s’agit de déclarer un sémaphore

d’EM V_mutex (initialisé à 1) et d’encadrer S par P(V_mutex) et
V(V_mutex).

2) Régions critiques conditionnelles : La structure précédente ne permet pas de résoudre

les problèmes généraux de synchronisation. Pour cela, une condition booléenne
exprimée à l’aide des variables de la région V et éventuellement des variables locales à
une procédure. On distingue différentes formes selon la disposition de la condition.

 Forme1 : Region V When B do S ;

Où B est une condition (expression booléenne).
Fonctionnement : La suite d’instructions S n’est exécutée que si
l’expression B est vraie.
L’exécution par un processus P est la suivante :
P entre ne région critique (première porte) et évalue l’expression B
(deuxième porte), deux cas sont alors possible :
1. Soit B est vraie, alors P exécute S et sort de la région critique.
2. Soit B et fausse, alors P libère la région critique (première porte)
et se bloque sur la condition B attendue (deuxième porte). P
sera réactivé à chaque fois qu’un processus sort (a terminé

Faculté des Sciences Département de Mathématiques et Informatique

27
 Chapitre 2 SYNCHRONISATION

complètement) d’une région critique associée à V pour

réévaluer B à nouveau.
Pour chaque variable partagée V, on aura ainsi 2 classes de
processus :
- Processus demandant l’entrée en région critique associée
(bloqués sur la première porte).
- Processus ayant passé la première porte mais ayant trouvé une
condition attendue B fausse (bloqués sur la deuxième porte).
 Producteur/Consommateur :
1ère Solution : Producteur Consommateur
Répéter Répéter
Var V :Shared record Produire (objet) Region V when (compteur>0) do
int compteur = 0; Region V when (compteur<N) do Begin
Object Tampon[0..N‐1]; Begin objet = Tampon[out];
int in=0; Tampon[in] = objet ; out = (out+1) mod N;
int out = 0; in = (in+1) mod N; compteur‐‐;
End; compteur++; End ;
End ; Consommer(objet)
Jusqu’à faux Jusqu’à faux

2ème Solution :
Producteur Consommateur
Var V :Shared record Répéter Répéter
int compteur = 0; Produire (objet) Region V when (compteur>0) do ;
End; Region V when (compteur<N) do ; <Prélever un objet>
<Déposer un objet> Region V do compteur ‐‐ ;
Region V do compteur ++ ; Consommer(objet)
Jusqu’à faux Jusqu’à faux

Figure 33. Exemple de solution de Problème de Producteur/Consommateur avec région

 Form2: Dans cette deuxième forme, après entrée en Région critique, Region V do
la séquence S1 est exécutée sans condition, ensuite B est évaluée : Begin
1. Soit B est vraie, alors P exécute S2 et sort de la région critique S1;
Await(B);
2. Soit B est fausse, alors P libère la région critique (première porte) et
S2;
se bloque sur la condition B attendue (deuxième porte). P sera réactivé à End;
chaque fois qu’un processus sort (a terminé complètement) d’une région
critique associée à V pour réévaluer B à nouveau.

Faculté des Sciences Département de Mathématiques et Informatique

28
 Chapitre 2 SYNCHRONISATION

 Lecteurs/rédacteurs (priorité aux lecteurs) :

Lecteur Rédacteur
Var V :Shared record
Region V do Region V do
int NbLect = 0;
Begin Begin
Boolean écriture = faux;
NbLectA ++ ; Await (NbLect = 0 et  écriture et NbLectA = 0);
int NbLectA=0;
Await ( écriture); Écriture = vrai ;
End;
NbLectA ‐‐ ; NbLect ++ ; End ;
end ; <Écriture>
<Lecture> Region V do Écriture = faux ;
Region V do NbLect ‐‐;

Figure 34. Exemple de solution de problème Lecteur/Rédacteur avec région

Exercices (en TD) :

- Traduction des Régions critiques
- Lecteurs/Rédacteurs (priorités aux rédacteurs)

Faculté des Sciences Département de Mathématiques et Informatique

29
 Chapitre 3
COMMUNICATION ENTRE PROCESSUS

1. Introduction

La communication est un outil important qui permet de faire évoluer l’ensemble des processus
dans un système.
Il existe plusieurs stratégies pour réaliser cette communication, nous citons :
- Variables partagées (modèles : producteur/ consommateur)
- Échange de messages (modèles : producteur/consommateur, client/serveur, Boite aux lettres)

2. Communication par variables partagées (modèles : producteur/ consommateur) :

Un modèle de communication entre processus avec partage de zone commune (tampon) est
le modèle producteur‐consommateur. Ce modèle a été décrit en détail dans le chapitre 2
sur la synchronisation.

3. Communication par échange de messages :

La fonction du sous‐système de messages est de permettre aux processus de communiquer
sans avoir besoin de variables partagées. Il doit offrir deux opérations de base :
- Send(destination, &message)
- Receive (source , &message)
La liaison de communication peut être directe ou indirecte, unidirectionnelle ou
bidirectionnelle.
a. Communication directe : Tout processus qui désire communiquer avec ce mode, doit
nommer explicitement le receveur ou l’expéditeur. Les primitives Send et Receive
sont définis comme suit :
- Send(P, &message) : envoyer le « message » au processus P.
- Receive (Q , &message) : recevoir le « message » du processus Q.
Soit le problème producteur/ consommateur qui peut être décrit par le code de Figure 35 :
Producteur
Répéter
produire_objet (&objet) /* produire un nouvel objet */
receive (consommateur , &m) /* attendre un message vide */
faire_message (&m , objet) /* construire un message à envoyer */
send (consommateur , &m) /* envoyer le message */
Jusqu’à faux
consommateur
send (producteur , &m) /* envoyer un messages vides */
Répéter
receive (producteur , &m) /* attendre un message */
retirer_objet (&m , &objet) /* retirer l'objet du message */
consommer_objet (objet)
send (producteur , &m) /* renvoyer une réponse vide */
Jusqu’à faux
Figure 35. Exemple de communication directe entre un producteur et un consommateur

Faculté des Sciences Département de Mathématiques et Informatique

30
 Chapitre 3 COMMUNICATION ENTRE PROCESSUS

b. Communication indirecte :
Les messages sont envoyés et reçus à travers des boites aux lettres (BAL). Ces dernières
peuvent être vues comme des objets où l’on peut déposer et retirer des messages.
Chaque boite aux lettres dispose d’un identificateur unique. Les processus peuvent alors
communiquer à travers plusieurs boites aux lettres.
Les primitives Send et Receive sont définies comme suit :
- Send(A, &message) : envoyer le « message » à la BAL A avec ou sans blocage si pleine.
- Receive (A , &message) : recevoir le « message » de la BAL A avec ou sans blocage si vide.
Deux autres primitives sont nécessaires :
- BAL = CreationBAL(nom) : retourne le descripteur de la BAL crée.
- BAL = RelierBAL(nom) : recherche la BAL et retourne son descripteur.

On peut imaginer, pour le modèle producteur/ consommateur, une solution de type

boîte aux lettres de capacité N messages, avec un producteur se bloquant si la boîte est
pleine et un consommateur se bloquant si la boîte est vide.
4. Communication interprocessus sous UNIX :

Les moyens de communication interprocessus UNIX sont : Pipes (tubes), Signaux, Sockets,
IPCs (Sémaphores, files de messages, mémoires partagées).
a. Communication par Pipes (Tubes) :
Les tubes (pipes) peuvent être considérés comme des fichiers temporaires. Ils
permettent d’établir des liaisons unidirectionnelles de communication entre processus
dépendants. En effet, Un tube de communication permet de mémoriser des informations
et se comporte comme une file FIFO.
Un tube est caractérisé par :
- Deux descripteurs de fichiers (lecture et écriture).
- Sa taille limitée (d’où la notion de tube plein).
- L’opération de lecture dans un tube est destructrice : une information ne peut
être lue qu’une seule fois dans un tube.
Il existe deux sortes de tube : les tubes ordinaires (anonymes) et les tubes nommés.
 Tubes ordinaires :
Les tubes anonymes sont, en général, utilisés pour la communication entre un
processus père et ses processus fils, avec un processus qui écrit sur le tube, appelé
processus écrivain, et un autre qui lit à partir du tube, appelé processus lecteur.
Remarque :
Un tube anonyme n’a pas de référence dans le système de fichiers.
La primitive de création d’un tube ordinaire est : pipe(p) ; avec int p[2] ;
P[0] : correspond au descripteur en mode lecture
P[1] : correspond au descripteur en mode écriture

Figure 36. Tune ordinaire

Faculté des Sciences Département de Mathématiques et Informatique

31
 Chapitre 3 COMMUNICATION ENTRE PROCESSUS

Exemple d’utilisation des tubes ordinaires :

pipe.c
# include <stdio.h>
# include <unistd.h>
int tube[2];
char buf[20];
main()
{ pipe(tube);
if (fork())
{ /* pere */
close (tube[0]);
write (tube[1], "bonjour", 8);
}
else
{ /* fils */
close (tube[1]);
read (tube[0], buf, 8);
printf ("%s bien recu \n", buf);
}
}

Figure 37. Code d'utilisation de tube ordinaire

L’exécution de ce programme ("pipe") donne le résultat suivant :

$ pipe
$ bonjour bien recu
$
Question : Comment réaliser une communication bidirectionnelle avec les pipes ?
Réponse : Utilisation de deux pipes entre deux processus.
 Tubes nommés :
Les tubes de communication nommés fonctionnent aussi comme des files de
discipline FIFO (first in first out). Ils peuvent être utilisés par des processus
indépendants ; à condition qu’ils s’exécutent sur une même machine.
Les tubes nommés sont créés par la commande « mkfifo» ou « mknod » ou par
l’appel système mknod() ou mkfifo().
#include <sys/types.h>
#include <sys/stat.h>
int mkfifo(const char *nomfichier, mode_t mode) ; nomfichier :
définit le chemin d’accès au tube et mode les droits d’accès des différents
utilisateurs à cet objet.

Faculté des Sciences Département de Mathématiques et Informatique

32
 Chapitre 3 COMMUNICATION ENTRE PROCESSUS

Exemple
Le programme suivant permet l’envoi d’un message sur le tube «mypipe» .
writer.c
#include <unistd.h>
#include <stdio.h>
#include <fcntl.h>
int main()
{ int fd;
char message[100];
sprintf(message, "bonjour du writer [%d]", getpid());
fd = open("mypipe", O_WRONLY); //Ouverture du tube mypipe en mode écriture
printf("ici writer[%d] \n", getpid());
if (fd!=‐1) write(fd, message, strlen(message)+1); // Dépot d’un message sur le tube
else printf( " désolé, le tube n' est pas disponible \n");
close(fd);
return 0;
}

Figure 38. Envoi d'un message via le tube nommé

Le programme suivant montre comment un processus lit un message à partir du

tube « mypipe».
reader.c
#include <unistd.h>
#include <stdio.h>
#include <fcntl.h>
int main()
{ int fd,n;
char message[100];
fd = open("mypipe", O_RDONLY); // ouverture du tube mypipe en mode lecture
printf("ici reader[%d] \n",getpid());
if (fd!=‐1)
{ while ((n = read(fd,message,100))>0) // récupérer un message du tube, taille maximale est 100.
printf("%s\n", message); // n est le nombre de caractères lus
} else printf( "désolé, le tube n' est pas disponible\n");
close(fd);
return 0;
}

Figure 39. Réception d'un message via le tube nommé

Remarque :
- Si un processus ouvre un tube nommé en lecture (resp. écriture) alors qu’il n’y a
aucun processus qui ait fait une ouverture en écriture (resp. lecture) alors, le
processus sera bloqué jusqu’à ce qu’un processus effectue une ouverture en
écriture (resp. en lecture).
- Attention au situation d’interblocage :

Faculté des Sciences Département de Mathématiques et Informatique

33
 Chapitre 3 COMMUNICATION ENTRE PROCESSUS

/* processus 1*/ /* processus 2*/

int f1, f2 ; int f1, f2 ;

… …
f1 = open("fifo1", O_WRONLY); f1 = open("fifo2", O_WRONLY);
f2 = open("fifo2", O_RDONLY); f2 = open("fifo1", O_RDONLY);
… …

Figure 40. Situation d'interblocage avec les tubes nommés

b. Communication par IPC (Inter Process Communication) :

Les IPC d’UNIX représentent trois outils de communication entre des processus situés
sur une même machine.
- Les files de messages
- Les segments de mémoire partagée
- Les sémaphores
Les IPC ont un certain nombre de propriétés en commun :
- A chacun des trois mécanismes est affecté une table de taille prédéfinie.
- Dans chacune des tables toute entrée active est associée à une clé numérique
choisie par l'utilisateur, et servant de nom d'identification global.
- Un appel système 'XXXget' (xxx → shm (mémoire partagée), msg (files de messages) ou
sem (sémaphores)) permet de créer une nouvelle entrée ou d'accéder une entrée
existante.

Remarque : la commande ipcs permet la consultation des tables d’IPC.

1. L
e Figure 41. La commande ipcs
s

1. segments de mémoire partagée : Les segments de mémoire partagée

permettent à deux processus distincts de partager physiquement des données. Le
partage est réalisé par l'espace d'adressage de chacun des processus, dont
une zone pointe vers un segment de mémoire partagée. Lorsqu'un processus
modifie la mémoire, tous les autres processus voient la modification.

Faculté des Sciences Département de Mathématiques et Informatique

34
 Chapitre 3 COMMUNICATION ENTRE PROCESSUS

Figure 42. Segment partagé entre deux processus

Pour utiliser un segment de mémoire partagée, un processus doit allouer le segment.

Puis, chaque processus désirant accéder au segment doit l'attacher. Après avoir fini
d'utiliser le segment, chaque processus le détache.
Remarque
Comme le noyau ne coordonne pas les accès à la mémoire partagée, vous devez
mettre en place votre propre synchronisation. Par exemple, deux processus ne doivent
pas écrire au même emplacement en même temps. Une stratégie courante pour éviter
ces conditions de concurrence est d'utiliser des sémaphores.
 Création d’un nouveau segment ou recherche de l’identifiant d’un segment déjà
existant:
int segment_id = shmget (shm_key, getpagesize (), IPC_CREAT |
S_IRUSR | S_IWUSR);
- shm_key: spécifié la clé externe du segment de mémoire à créer. Il est utile
de spécifier IPC_PRIVATE comme valeur de clé qui garantit qu'un nouveau
segment mémoire est créé.
- IPC_CREAT: indicateur demande la création d'un nouveau segment.
- S_IRUSR et S_IWUSR spécifient des permissions de lecture et écriture pour le
propriétaire du segment de mémoire partagée.
Si l'appel se passe bien, shmget renvoie un identifiant de segment. Si le
segment de mémoire partagée existe déjà, les permissions d'accès sont
vérifiées.
 Attachement d’un segment : Elle rend l’adresse à laquelle le segment a été
attaché.
char*shared_memory= (char*)shmat(int shmid, void *adr, int
flags);
- shmid: identifiant du segment de mémoire partagée.
- adr : adresse d’attachement dans l’espace de processus. adr = 0 : e
système choisit l’adresse d’attachement.
 Détachement d’un segment :
int shmdt(void *adr);
- adr: adresse du segment partagé attaché(adr renvoyée par shmat).
- rend 0 en cas de succès et ‐1 sinon.
 Suppression d’un segment :
int shmctl(int shmid, int cmd, shmid_ds *buf);
- cmd = IPC_RMID
- buf= NULL.
Faculté des Sciences Département de Mathématiques et Informatique
35
 Chapitre 3 COMMUNICATION ENTRE PROCESSUS

Exemple (fichier shm.c):

shm.c
#include <stdio.h>
#include <sys/shm.h>
#include <sys/stat.h>
int main ()
{
int segment_id; char* shared_memory; struct shmid_ds shmbuffer;
int segment_size; const int shared_segment_size = 0x6400;

/* Alloue le segment de mémoire partagée. */

segment_id = shmget (IPC_PRIVATE, shared_segment_size, IPC_CREAT |
S_IRUSR | S_IWUSR);
/* Attache le segment de mémoire partagée. */
shared_memory = (char*) shmat (segment_id, 0, 0);
printf ("mémoire partagée attachée à l'adresse %p\n", shared_memory);

/* Écrit une chaîne dans le segment de mémoire partagée. */

sprintf (shared_memory, "Hello, world.");
/* Détache le segment de mémoire partagée. */
shmdt (shared_memory);

/* Réattache le segment de mémoire partagée à une adresse différente.*/

shared_memory = (char*) shmat (segment_id, (void*) 0x5000000, 0);
printf ("mémoire partagée réattachée à l'adresse %p\n", shared_memory);
/* Affiche la chaîne de la mémoire partagée. */
printf ("%s\n", shared_memory);
/* Détache le segment de mémoire partagée. */
shmdt (shared_memory);
/* Libère le segment de mémoire partagée. */
shmctl (segment_id, IPC_RMID, 0);
return 0;
}

Figure 43. Code d'utilisation d'un segment partagé

2. Les files de messages :

C'est une implantation UNIX du concept de boîte aux lettres, qui permet la
communication indirecte entre des processus. Les messages étant typés,
chaque processus peut choisir les messages qu'il veut lire (extraire de la file).
Les informations sont stockées dans les files de messages en DATAGRAM
(un message à la fois). Les files sont de type FIFO (First In, First Out).
Un processus peut émettre des messages vers plusieurs processus, par l'intermédiare
d'une même file de message (multiplexage).

 Création ou recherche des files de messages :

int msgid = msgget(key_t cle, int flags);
NB: les arguments de la primitive msgget sont les mêmes que celle du
shmget.
Si l'appel se passe bien, msgget renvoie un identifiant de file de message
crée. Si la file de message existe déjà, les permissions d'accès sont vérifiées.
Faculté des Sciences Département de Mathématiques et Informatique
36
 Chapitre 3 COMMUNICATION ENTRE PROCESSUS

 Émission des messages :

int msgsnd(int msgid, struct msgbuf *msg,int taille,int flags);
où : struct msgbuf { /* définie dans sys/msg.h */
long mtype; /* type du message */
char mtext[1]; /* texte du message */
};
Avec possibilité de redéfinir cette structure en fonction de ses besoins.
Cette primitive permet à un processus d’envoyer le message, msg, dans la file de
message spécifié par l’id msgid. Elle retourne 0 en cas de succès et ‐1 sinon.
Remarque : La primitive msgsnd est une fonction bloquante i.e. si la file de
message est plein, le processus est suspendu jusqu’à extraction de messages
de la file ou bien suppression du système de la file (retourne ‐1). Si
IPC_NOWAIT → flags, et que la file est pleine, la fonction devient non
bloquante. Donc, le message ne sera pas envoyé et le processus peut
reprendre la main immédiatement.
 Réception des messages :
int msgrcv(int msgid, struct msgbuf *msg, int taille, long
type, int flags);
La primitive msgrcv permet de retirer un message de la file en fonction de son type.
Comme pour msgsnd, IPC_NOWAIT rend l’appel non bloquant.
- type = 0 : le premier message est lu
- type>0 : le premier message de type msgtype est lu
- type<0 : le premier message dont le type est inférieur ou égal à
|msgtyp| est lu
 Suppression des files de messages :
int msgctl(int msgid, int cmd, msqid_ds *buf);
- cmd = IPC_RMID.
- Buf = NULL.
Exemple (fichier shm.c):
shm.c
#include <sys/ipc.h>
#include <sys/msg.h>
…
int msg_id; struct msqid_ds *buf;
struct message {
long type;
char texte[128];
} msg;
…
msg_id = msgget (IPC_PRIVATE, IPC_CREAT);
…
msg.type = 1;
for ( ; ; ) {
printf ( "Entrer le texte a emettre \n");
scanf("%s",msg.texte);
msgsnd(msg_id , &msg , sizeof( struct message ) , 0);
…
}

Figure 44. Code d'utilisation une file de messages

Faculté des Sciences Département de Mathématiques et Informatique

37
 Chapitre 3 COMMUNICATION ENTRE PROCESSUS

3. Les sémaphores :
Tous les problèmes de synchronisation ne sont pas solubles avec les
sémaphores simples de Djiskstra, tels qu'ils ont été décrits précédemment.
Exemple : la demande de m ressources différentes, dans un ensemble de n ressources
(m <= n).
Soit les n sémaphores S1, S2, ..., Sn permettant de bloquer les n ressources. Si
P1 demande R1, R2, R3 et R4 et P2 demande R2, R3, R4 et R5 alors on a :
P1 -> P(S1), P(S2), P(S3), P(S4) et
P2 -> P(S3), P(S4), P(S5), P(S2)

On a un risque d'interblocage.
Solution : Si les 4 opérations P étaient atomiques, on éviterait les interblocages
(deadlock) :
P1 -> P(S1,S2,S3,S4) et
P2 -> P(S3,S4,S5,S2)
Idée : ensemble de sémaphores.
 Création ou recherche de l’identifiant d’un ens. de sémaphores :
int sem_id = semget(key_t cle, int nsems, int flags);
- nsem: nombre de sémaphores à créer dans le groupe.
Cette fonction renvoie l'id. de l’ens. des sémaphores ds la table en cas de
succès (> 0) ‐1 sinon.
 Initialisation des sémaphores :
int semctl (int semid, int semnum, int cmd, union semun arg);
- semnum : numéro du sémaphore choisi dans le groupe (0 pour le premier).
- cmd : type d'opération à effectuer sur le sémaphore, par exemple SETVAL pour
initialiser le sémaphore à la valeur contenue dans "arg".
- arg : sert à passer des arguments aux commandes exécutées par "cmd".
 Opérations sur les sémaphores :
int semop(int semid, struct sembuf *sops, unsigned nsops);
structure d’une operation:
struct sembuf {
ushort sem_num; /* N° du semaphore*/
short sem_op; /* opération sur le sémaphore */
shrot sem_flag; /* options */
};
- sops : tableau de structures qui contient la liste des opérations.
Cette fonction retourne 0 en cas de succès et ‐1 sinon.
L'opération semop est en principe bloquante, i.e. le processus est mis en
sommeil si l'une des opérations de l'ensemble ne peut être effectuée.
Dans ce cas, aucune opération de l'ensemble n'est réalisée.
Une opération élémentaire comporte un numéro de sémaphore et
une opération qui peut avoir trois valeurs :

Faculté des Sciences Département de Mathématiques et Informatique

38
 Chapitre 3 COMMUNICATION ENTRE PROCESSUS

 une sem_op > 0, pour une opération Vsem_op, (semval = semval + sem_op)
Tous les processus en attente d'une augmentation du sémaphore sont reveilles.
 une sem_op = 0, teste si le sémaphore a la valeur 0. Si ce n'est pas le cas, le processus est mis
en attente de la mise à zéro du sémaphore.
 une sem_op < 0, pour une opération Psem_op (semval = semval - |sem_op|)
Si le résultat est :
nul: tous les processus en attente de cet événement sont réveillés
négatif: le processus est mis en attente d'une augmentation du sémaphore

Exemple (semEM.c) :
semEM.c
#include <sys/ipc.h>
#include <sys/sem.h>

#define SEM_EXCL_MUT 0
#define NB_SEM 1
int FLAGS = IPC_CREAT; int sem_id;
struct sembuf op;
main ( )
{
sem_id = semget (IPC_PRIVATE, NB_SEM, FLAGS );
semctl(sem_id, SEM_EXCL_MUT, SETVAL, 1);
…
P(SEM_EXCL_MUT);
/* Section Critique */
V(SEM_EXCL_MUT);
…
semctl(sem_id, SEM_EXCL_MUT, IPC_RMID, 0);
}

void P (int sem) /* Primitive P() sur sémaphores */

{ /* sem = Identifiant du sémaphore */
op.sem_num = sem; /* Identification du sémaphore impliqué */
op.sem_op = -1; /* Définition de l’opération à réaliser */
op.sem_flg = SEM_UNDO; /* Positionnement du bit SEM_UNDO */
semop (sem_id, &op, 1); /* Exécution de l’opération définie */
};

void V(int sem) /* Primitive V() sur sémaphores */

{
op.sem_num = sem;
op.sem_op = 1;
op.sem_flg = SEM_UNDO;
semop (sem_id, &op, 1);
};

Figure 45. Code d'utilisation de sémaphore

Faculté des Sciences Département de Mathématiques et Informatique

39
 Chapitre 3 COMMUNICATION ENTRE PROCESSUS

Exercice (Rendez‐vous de processus) :

Soit une application décomposée en N modules qui s'exécuteront de manière concurrente
et ont la particularité d'être constitués de deux parties logiques Ai:Bi.
L'objectif est de faire en sorte que les N processus ne commencent l'exécution des
séquences Bi, uniquement (point de rendez‐vous) lorsque toutes les séquences Ai
auront été complètement exécutées. Cela signifie que les processus doivent se
synchroniser sur le processus j le plus lent à exécuter sa séquence Aj ; il est donc nécessaire de
mettre en place entre les séquences Ai et Bi un mécanisme bloquant les processus quand ils
terminent leur séquence Ai.

Faculté des Sciences Département de Mathématiques et Informatique

40
 Chapitre 4
INTERBLOCAGE

1. Introduction

Dans un système informatique, l’exécution d’un processus nécessite l’utilisation des ressources
(déf Chapitre 2). Sachant que le système dispose un nombre limité de ressources et certaines
sont non‐partageables. L’accès concurrent à ces ressources par les processus risque de créer
une situation de blocage.

2. Interblocage

A. Définition de l’interblocage (deadlock)

Un ensemble de processus sont interbloqués si chacun d’eux est bloqué en attente d’un
événement qui ne peut être déclenché que par un autre processus de l’ensemble.
Exemples :
Exemple1 : Utilisation croisée de 2 ressources critiques (Figure 46)

P1 P2
1‐ Demande(R1) 1‐ Demande(R2)
<Utilisation R1> <Utilisation R2>
2‐ Demande(R2) 2‐ Demande(R1)
<Utilisation R2> <Utilisation R1>
3‐ Libération (R2) 3‐ Libération (R2)
4‐ Libération(R1) 4‐ Libération(R1)

Figure 46. Utilisation croisée de 2 ressources critiques

La séquence suivante : 1, 1, 2, 2… induit à un interblocage i.e. P1 attend P2 et P2 attend

P1). Les deux processus vont attendre indéfiniment.
Exemple2 (Allocation partielle d’une ressource existant en (N) plusieurs exemplaires)
Nombre d’unités de ressources disponibles : Rlibre=4 ;

P1 P2
1‐ Demander(3) 1‐ Demander(3)
<Obtient 2 unités> <Obtient 2 unités>
2‐ Attend 1 unité 2‐ Attend 1 unité

Rlibre = 0 ;

Figure 47. Allocation partielle d’une ressource

Faculté des Sciences Département de Mathématiques et Informatique

41
 Chapitre 4 INTERBLOCAGE

B. Conditions d’interblocage

Plusieurs conditions sont requises pour qu’il puisse y avoir interblocage :

a. Condition1 (Exclusion Mutuelle) : Elle concerne les ressources critiques (un seul
exemplaire non partageable) car l’exclusion mutuelle entre processus est nécessaire
pour les utiliser.
b. Condition2 (Occupation et attente, Hold and Wait) : Un processus qui possède déjà
des ressources peut faire de nouvelles demandes d’allocation et donc se bloquer en
attente de l’obtention de la nouvelle ressource demandée sans libérer celles qu’il
détient.
c. Condition3 (Pas de préemption) : Elle concerne les ressources non préemptibles3
(non soumises à réquisition) avec demandes bloquantes. Dans ce cas, une ressource
ne peut être retirée à un processus avant qu’il n’ait fini de l’utiliser.
d. Condition4 (Attente circulaire) : Les processus peuvent être rangés dans une liste
circulaire, chaque processus attendant une ressource possédée par le suivant.

C. Modèles d’interblocage

Les problèmes de l’interblocage peuvent être classés en une hiérarchie de 5 modèles

principaux selon le mode de demande de ressources :
a. Modèle ressource simple : un processus exprime une requête vers au plus une
ressource.
b. Modèle and : un processus effectue une requête portant sur plusieurs ressources à
la fois. Le processus se bloque jusqu’à l’obtention de toutes les ressources
demandées.
c. Modèle or : un processus est bloqué jusqu’à l’obtention d’au moins une des
ressources demandées.
d. Modèle c(m, n) : un processus est bloqués jusqu’à l’obtention de n ressources
quelconques parmi m ressources.
e. Modèle and‐or : c’est une généralisation des modèles b et c. La requête est une
combinaison des opérateurs and et or (ex : Demande[R1 and (R2 or R3)]).
Notre étude va se porter sur le modèle and.

3. Formalisation de l’état d’un système

a. Modélisation matricielle :
1. Vecteur des ressources maximales : Nous admettons que le système comprend
m classes de ressources (C1 à Cm). L’ensemble des ressources existantes peut être
représenté par un vecteur : Rmax = [r1max r2max … rmmax] dans lequel

3
Classes des ressources : Ress réquisitionnables (récupération de la Ress pendant sont
utilisation ex : mémoire) et Ress non réquisitionnables (ex : graveur, imprimante…) .

Faculté des Sciences Département de Mathématiques et Informatique

42
 Chapitre 4 INTERBLOCAGE

rimax indique le nombre maximale d’exemplaires de la ressource de classe i

présente dans le système.
2. Vecteurs des ressources disponibles : Lorsque des allocations ont été
éffectuées, le nombre de ressources disponibles est contenu dans un autre
vecteur Available où Available[i] représente le nombre d’unités
disponibles de la classe de ressources Ci.
3. Matrices des unités de ressources allouées : On dispose, en outre, d’une
matrice Allocate décrivant les allocations courantes des ressources aux
processus dans laquelle Allocate[i,j] comptabilise le nombre de ressources
de la classe Cj allouées au processus Pi.
4. Matrices des demandes en attente (requêtes en attentes) : Les requêtes
(demandes) des différents processus sont également décrites par une matrice
Request dans laquelle Request[i,j] désigne le nombre de ressources de la
classe Cj demandées et non encore obtenues par le processus Pi.
 Notion d’état réalisable :
L’état d’un système est dit réalisable si les contraintes de cohérence suivantes
sont respectées :
1. Le nombre d’unités disponibles est toujours positifs ou nul, et un processus
ne peut demander plus de ressources qu’il n’en existe dans le système. À
l’initialisation (t=0): Available = Rmax.
La contrainte1 s’écrira : Available≥[[0]]et Request[i,*]≤ Rmax
2. L’ensemble des ressources détenues par un processus ne peut dépasser
l’ensemble des ressources maximales disponibles, et un processus ne peut
détenir plus de ressources qu’il n’en a demandé. Dans ce cas la contrainte2
s’écrira : Allocate[i,*]≤ Rmax et
Rmax≥ Allocate[i,*] + Request[i,*] ≥ Allocate[i,*]
3. A tout instant, la somme des acquisitions des processus ne peut dépasser le
totalité des ressources du système :

 Allocatei,*  R max
n
La contrainte3 :
i 1

Remarque : Le système passe d’un état à un autre par l’intermédiaire de l’une des
opérations : Demander, allouer ou libérer comme suit :
- Demandé : Requesti(t+1) = Requesti(t) + Requesti.
- Allocation : Allocatei(t+1) = Allocatei(t) + Allocatei et
Available(t+1) = Available(t) – Allocatei.
- Libération : Allocatei(t+1) = Allocatei(t) - Allocatei et
Requesti(t+1) = Requesti(t) - Allocatei et
Available(t+1) = Available(t) + Allocatei.

Faculté des Sciences Département de Mathématiques et Informatique

43
 Chapitre 4 INTERBLOCAGE

Exemple :
Un état réalisable peut être décrit par les vecteurs suivants :
Rmax=[4 2 3 1] et Available=[2 1 0 0]
Avec les matrices suivantes pour les allocations et les requêtes :

b. Modélisation par graphe : De même que l’on a représenté l’état du système par un
ensemble de vecteurs et matrices, on peut le représenter par un graphe d’état (ou
graphe d’allocation de ressources).
Le graphe d’allocation des ressources est un graphe biparti G(V, E) composé de deux
types de nœuds et d’un ensemble d’arcs :
- Les processus qui sont représentés par des cercles;
- Les ressources qui sont représentées par des rectangles. Chaque rectangle
contient autant de points qu’il y a d’exemplaires de la ressource
représentée
- Un arc orienté d’une ressource vers un processus signifie que des unités de
la ressource sont allouées au processus
- Un arc orienté d’un processus vers une ressource signifie que des unités de
la ressource sont demandées par le processus.
Le graphe indique pour chaque processus les ressources qu’il détient ainsi que
celles qu’il demande.

NB : Interblocage = trouver un cycle dans le graphe.

Exemple :
Soit un système à 2 classes de ressources et 4 processus caractérisé par l’état
suivant : Rmax=[2 2] et Available=[0 0]

Faculté des Sciences Département de Mathématiques et Informatique

44
 Chapitre 4 INTERBLOCAGE

Le graphe d’allocation correspondant (Figure 48) :

C1
P2
P1

P3

P4
C2
Figure 48. Graphe d’allocation de ressources

Exercice1 : Soient trois processus P1, P2 et P3 qui utilisent trois classes de

ressources C1, C2 et C3 comme suit :

P1 P2 P3
Demander(C1) Demander(C2) Demander(C3)
Demander(C2) Demander(C3) Demander(C1)
Libérer(C1) Libérer(C2) Libérer(C3)
Libérer(C2) Libérer(C3) Libérer(C1)

 Si les processus sont exécutés séquentiellement P1 suivi de P2 suivi de P3,

il n’y aurait pas d’interblocage.

 Supposons que l’exécution des processus est gérée par un ordonnanceur

circulaire. On atteindrait une situation d’interblocage, si les instructions
sont exécutées dans cet ordre :

P1 demande C1 ; P2 demande C2 ; P3 demande C3 ; P1 demande C2 ;

P2 demande C3 ; P3 demande C1 ;

C1 C2 C3

P1 P2 P3

Figure 49. Graphe d'allocation de ressources avec une situation d'interblocage

Dans ce graphe, P1 dispose d’une instance (un exemplaire) de la classe C1 et

demande un exemplaire de la classe de ressources C2, déjà, allouée à P2. Ce dernier
attend une ressource de C3, déjà, allouée à P3 et P2 est en attente d’une ressource
de C1 allouée à P1.
Faculté des Sciences Département de Mathématiques et Informatique
45
 Chapitre 4 INTERBLOCAGE

P1 ‐‐‐‐> C2 ‐‐‐‐>P2‐‐‐‐>C3 ‐‐‐‐>P3 ‐‐‐‐>C1‐‐‐‐> P1.

Un cycle apparaît est aucune ressources des trois classes n’est disponible, donc un
interblocage.
Remarques :
- Si chaque ressource existe en un seul exemplaire, alors un interblocage
existe si le graphe d’allocation des ressources contient un cycle.
- L’existence d’un cycle dans le graphe d’allocation n’est pas une CNS pour
détecter les interblocages si une ressource peut exister en plusieurs
exemplaires.

Exercice :
Supposons un système avec 7 processus et 6 classes de ressources.
Considérons l’attribution des ressources suivante :
P1 détient C1 et demande C2 ; P2 demande C3 ; P3 demande C2 ; P4 détient C4
et demande C2 et C3; P5 détient C3 et demande C5 ; P6 détient C6 et
demande C2 ; P7 détient C5 et demande C4.
Construire le graphe d’allocation des ressources. Y a‐t‐il un interblocage ? Si oui,
quels sont les processus concernés ?

 Autres représentations : L’état du système peut être représenté par un graphe

(graphe d’attente) dont les nœuds représentent les processus et les arcs (Pi, Pj)
qui indiquent que Pi attend au moins une ressource allouée à Pj.

4. Traitements des interblocages

Plusieurs stratégies peuvent être utilisées face à l’interblocage à savoir : Prévention, évitement
ou la détection/guérison4.

1. Stratégies de Prévention : Le risque d’interblocage survient dès que des processus

qui possèdent des ressources peuvent en demander de nouvelles. Si on exclut cette
éventualité, il n’y a plus de risque d’interblocage. Trois techniques peuvent être
employées en ce sens :
 Allouer toutes les ressources en une seule fois. Il n’y a plus d’interblocage, mais
des ressources peuvent être immobilisées alors qu’elles ne sont pas réellement
utilisées.
 Libérer toutes les ressources affectées à un processus avant toute nouvelle
demande ; en général, le processus redemande simultanément toutes les
ressources qu’il a été forcé de libérer, plus la nouvelle.

4
La guérison de l’interblocage vise à reprendre l’exécution du système dans un état cohérent et sain.

Faculté des Sciences Département de Mathématiques et Informatique

46
 Chapitre 4 INTERBLOCAGE

 Méthode des classes ordonnées

o Les ressources sont organisées en classes C1, C2, ∙ ∙ ∙ , Cn
o Dans une classe, les ressources sont allouées en une seule fois
o Les ressources doivent être demandées dans l’ordre des classes.
Cette technique est une amélioration de l’allocation en une seule fois ; elle est
très utilisée pour l’allocation des ressources matérielles en rangeant les
ressources dans l’ordre croissant de leur coût (pour diminuer le coût
d’immobilisation). On peut ainsi demander d’abord des périphériques, puis de
la mémoire et enfin l’unité centrale.
2. Stratégie d’Évitement5 : L’évitement est une méthode d’allocation des ressources
avec précaution. Si l’allocation d’une ressource peut conduire à un interblocage, elle
est retardée jusqu’à ce qu’il n’y ait plus de risque. En effet, Dans ce cas, lorsqu’un
processus demande une ressource, le système doit déterminer si l’attribution de la
ressource est sûre (mènent vers un état fiable). Si c’est le cas, il lui attribue la
ressource, Sinon, la ressource n’est pas accordée.
Cette méthode impose à tout processus de déclarer ses besoins (annonces) avant
son exécution.
Définition (état fiable): Un état est fiable si tous les processus peuvent terminer leur
exécution (il existe un ordre d’allocation de ressources qui permet à tous les
processus de se terminer). En effet, il existe une suite fiable de processus
S = P1P2,…,Pn tq : rang(Pi) = i, i=1..n et
i 1
Annonce i,*  Allocate i,*  Available   Allocate  k ,*
k 1

Propriétés des suites fiables

Lorsque l’état du système est fiable (non interbloqué) alors on peut construire au
moins une suite fiable complète de processus.
 Méthode d’évitement (Algorithme du Banquier) :
Un état de système est définie par :
- Rmax[1..m] : Nombre total, initial, de ressources.
- Annonce[p,*] : Nombre maximal de ressources nécessaires au processus p.
- Allocate[p,*] : Nombre de ressources couramment allouées au processus p.
- Available[1..m] : Nombre de ressources disponibles.

5
Appelée aussi, stratégie de prévention dynamique

Faculté des Sciences Département de Mathématiques et Informatique

47
 Chapitre 4 INTERBLOCAGE

Algorithme Banquier
Debut
(1) Chercher Pi non marqué tel que : Need[i,*]=(Annonce[i,*] – Allocate[i,*])  Available.
(2) Si Pi n’existe pas:
(3) Aller en 7.
(4) Available ← Available + Allocate[i,*].
(5) Marquer Pi.
(6) Aller en 1.
(7) Si il reste un processus non marqué:
(8) Il est en situation d’interblocage.
Fin.

Figure 50.Algorithme du Banquier

Remarque : Si tous les processus sont marqués, selon l’algorithme du Banquier,

alors l’état du système est fiable. Sinon, l’état n’est pas fiable.

Exemple1 : À instant t donné, l’état du système peut être le suivant :

Rmax=[10 5 7], Available=[3 3 2]

Question : Cet état est‐il un état faible ?

Exemple2 :
Considérons un système de 4 processus (P1, P2, P3 et P4) et disposant de 10 unités
d’une ressource (Rmax =[10]). Le vecteur des annonces est : Annonce= [6 5 4 7].
Supposons que des allocations aient été effectuées et décrites par le vecteur
Allocate = [1 1 2 4] ; le nombre de ressources libres est alors Available = [2].
Question : Déterminez s’il y a interblocage dans le système (Cet état est‐il un état
fiable ?).
(1) Need[3,*]=Annonce[3,*]–Allocate[3,*]Available.
P3 est marqué, Available=Available+Allocate[3,*]=[4].
(2) Need[2,*]=Annonce[2,*]–Allocate[2,*]Available.
P2 est marqué, Available=Available+Allocate[2,*]= [5].
(3) Need[1,*]=Annonce[1,*]–Allocate[1,*]Available.
P1 est marqué, Available=Available+Allocate[1,*]=[6].
(4) Need[4,*]=Annonce[4,*]–Allocate[4,*]Available.
P4 est marqué, Available=Available+Allocate[4,*]=[10].
L’état du système est fiable, pas d’interblocage.

Faculté des Sciences Département de Mathématiques et Informatique

48
 Chapitre 4 INTERBLOCAGE

3. Détection/Guérison : Selon cette approche, aucune mesure préventive n’est prise : on

laisse les processus évoluer librement, si une situation d’interblocage est détectée
alors une méthode de guérison est appliquée pour remettre le système dans un état
cohérent.
A. Cas de ressources en plusieurs exemplaires : La méthode se base sur la détection
de l’état sain du système ; un état sain est un état où l’interblocage est impossible.
 Définition (état sain) : Le système est dit dans l’état sain si on peut allouer les
ressources dans un certain ordre tel que tous les processus du système peuvent
s’exécuter jusqu’à leur fin sans interblocage. D’une manière plus formelle ceci revient
à trouver une suite S dite saine et complète de processus S = P1P2,…,Pn tq : rang(Pi) = i,
i=1..n, suite ordonnée contenant les n processus du système et telle que pour tout
processus Pi de cette suite les requêtes de Pi en attente peuvent être totalement
satisfaites en prenant l’ensemble des ressources disponibles et des ressources
détenues par l’ensemble des processus qui précèdent Pi (de rang infèrieur à rang(Pi)).
Donc cette propriété s’écrira pour tout processus Pi de rang i dans S (avec Card(S)=n) :

 Propriétés des suites saines :

 Lorsque l’état du système est sain (non interbloqué) alors, on peut construire au
moins une suite saine complète de processus.
 Lorsque l’état du système est sain (non interbloqué) alors toute suite saine
partielle (incomplète) peut être prolongée en une suite saine complète de
processus.

 Conséquences : Pour détecter un interblocage dans un système, il suffit de réaliser

un algorithme permettant de construire une suite saine de processus S. Si la suite S est
complète (Card(S) = n) alors le système est dans un état sain et il n’y pas
d’interblocage. Si S est incomplète et ne peut plus être prolongée en une suite saine
complète alors l’état n’est pas sain et il y a interblocage : dans ce cas si Card(S) = k<n
alors il y a (n‐k) processus interbloqué.
 Équivalence dans le graphe d’allocation de ressources :
Un processus est dit réducteur du graphe si toutes ses requêtes peuvent être
satisfaites, i.e. si tous ses arcs de requêtes en attente peuvent être transformés en
arcs d’allocation. Dans le graphe d’état, une suite saine de processus est une suite
de processus réducteurs du graphe. L’état sera sain si la suite processus réducteurs
est complète (contient tous les processus du graphe) i.e. le graphe est totalement
réduit. Dans le cas contraire (graphe partiellement réduit) on n’obtient que k

Faculté des Sciences Département de Mathématiques et Informatique

49
 Chapitre 4 INTERBLOCAGE

processus réducteurs (k<n) alors les (n‐k) processus restants (non réducteurs du
graphe) sont donc interbloqués.
 Méthode de détection (Algorithme TestSain) :
Un état de système est définie par :
- Rmax[1..m] : Nombre total, initial, de ressources.
- Request[p,*] : Nombre de ressources demandées et non encore obtenues
par le processus p.
- Allocate[p,*] : Nombre de ressources couramment allouées au processus p.
- Available[1..m] : Nombre de ressources disponibles.

Algorithme TestSain
Debut
(1) Chercher Pi non marqué tel que : Request[i,*]  Available.
(2) si Pi n’existe pas:
(3) aller en 7.
(4) Available ← Available + Allocate[I,*].
(5) Marquer Pi.
(6) Aller en 1.
(7) si il reste un processus non marqué:
(8) il est en situation d’interblocage.
Fin.

Figure 51. Algorithme TestSain

Remarque :
 Si tous les processus sont marqués, selon l’algorithme de TestSain, alors l’état du
système est sain. Sinon, il y a interblocage et tous les processus non marqués sont
interbloqués.
 La compléxité de cet algorithme est polynomiale : O (mxn2) où m : nombre de classe
de ressource, n : nombre de processus.

Exemple : Soit un système à 2 classes de ressources et 4 processus caractérisé par l’état

suivant : Rmax = [2 2] , Available = [0 0]

Faculté des Sciences Département de Mathématiques et Informatique

50
 Chapitre 4 INTERBLOCAGE

Question : Cet état est‐il un état sain ?

(1) : Request[2,*]  Available :
marqué P2 : Available = Available + Allocate[2,*].
(2) : Request[4,*]  Available :
marqué P4 : Available = Available + Allocate[4,*].
(3) : Request[3,*]  Available :
marqué P3 : Available = Available + Allocate[3,*].
(4) : Request[1,*]  Available :
marqué P1 : Available = Available + Allocate[1,*].

Tous les processus sont marqués, l’état du système est sain et donc pas d’interblocage.
B. Cas de ressources en un seul exemplaire : Dans ce cas, pour réduire le nombre
d’opérations de l’algorithme de test de l’état sain, on utilise une variante du graphe
d’état appelée graphes des attentes. Ce dernier graphe est obtenu en éliminant du
graphe d’allocation de ressources tous les sommets de type ressource et en ne
gardant que les sommets de type processus. Ensuite, on effectue la fusion des arcs
appropriés :
(Pi, Rk) et (Rk, Pj) ‐‐‐‐> (Pi, Pj) : ceci indique que Pi attend une ressource détenue par Pj.
 Méthode de détection :
1. Construire le graphe des attentes,
2. Détecter un interblocage revient à rechercher au moins un cycle (circuit) dans le
graphe des attentes. L’absence de cycle indique un état sain (pas
d’interblocage) ; sinon, les processus interbloqués sont ceux formant le cycle.
Remarque : La complexité de l’algorithme devient maintenant : O(n2)
 Mise en œuvre de la détection : Le premier problème qui se pose est de choisir
quand lancer l’algorithme de détection d’interblocage.
La réponse à cette question dépend de deux facteurs :
- La fréquence d’apparition des interblocages.
- Le nombre moyen de processus interbloqués.
Il faut trouver un critère permettant d’éviter un coût trop élevé pour le système,
i.e. qui évite de trop pénaliser le rendement du système (temps moyen d’exécution
d’un processus).
Les principaux inconvénients de la détection sont :
- L’overhead ou proportion de temps importante prise par le système pour
l’entretien des graphes et la détection de l’interblocage (le graphe doit être
mis à jour à chaque allocation ou libération de ressource).
- Le nombre de cycles des graphes peut être important.
 Guérison de l’interblocage: La guérison de l’interblocage vise à reprendre
l’exécution du système dans un état cohérent et sain. Ceci ne peut être fait qu’en
récupérant des ressources déjà allouées : il y aura donc réquisition ou retrait forcé
appliquée à ces ressources. Ceci entraine une transformation de ces ressources en

Faculté des Sciences Département de Mathématiques et Informatique

51
 Chapitre 4 INTERBLOCAGE

ressources préemptibles (sauvegarde de copies totales et/ou partielles éventuelles

des ressources). Une fois le problème de la préemption est résolu, il reste 3
problèmes à résoudre :
1. Choix du processus victimes : le choix doit porter sur le processus qui
engendre un cout minimal en doit tenir compte de priorité des processus,
leur évolution (temps écoulé, temps restant, ressources utilisées et
ressources restantes).
2. Problème de retour arrière (Roll Back) : il faut effectuer une « marche
arrière » au processus victimes i.e. le réexécuter à partir d’un état cohérent
antérieur à celui où il était (cet état cohérent doit être sain). Généralement,
pour éviter de recommencer complètement l’exécution du processus
victime on utilise souvent la technique des points de reprise « check
points ». Le système mémorise (généralement sur disque) un cliché complet
de l’espace mémoire occupé par le processus et de l’état des ressources
utilisées par le processus de façon à pouvoir reprendre son exécution dans
un état cohérent. Ce qui nécessite un espace mémoire considérable.
3. Problème de privation (Famine): La privation concernée ici est le rsique de
choisir trop fréquemment le même processus victimes. Diverses méthodes
ont été proposées pour y remédier :
- Techniques du privilège circulant ou jeton qui protège le processus
qui le détient contre la destruction forcée.
- Utilisation d’un facteur de coût croissant avec le nombre de
destructions forcées : on choisira donc comme victime le processus
qui a le plus petit facteur de coût.

5. Conclusion : Approche combinée de traitement de l’interblocage

Le problème de choisir entre les méthodes de traitement de l’interblocage ne peut se résoudre

qu’en évaluant le coût (rendement du système) engendré par l’adoption de chacune de ces
approches en tenant compte des facteurs : fréquence des interblocages, nombre de processus
interbloqués. En fait, aucune approche n’est totalement satisfaisante pour résoudre à elle seule
tous les cas d’interblocage.
L’expérience prouve qu’il est en général meilleur de combiner plusieurs méthodes de
préventions et de détection/guérison pour résoudre le problème de l’interblocage dans le
système. Il est donc recommandé de partitionner ce problème en plusieurs sous‐problèmes et
de trouver pour chacun d’eux la méthode la plus adéquate.
On peut illustrer cette démarche sur l’exemple suivant :
Soit un système partitionné en 4 sous‐ensembles de ressources :
1. Ressources internes utilisées par le système pour gérer les processus (ex : PCB,
structures représentatives internes,…)
2. Mémoire centrale.
3. Ressources communes aux travaux (périphériques, fichiers,…).

Faculté des Sciences Département de Mathématiques et Informatique

52
 Chapitre 4 INTERBLOCAGE

4. Espace réservé au SWAP6 en mémoire secondaire.

On associé à chaque sous‐ensemble une méthode spécifique de traitement de
l’interblocage :
1. Sous‐ensemble1 : prévention par ordonnancement des ressources internes
(classes ordonnées)
2. Sous‐ensemble2 : prévention par préemption (éviter la condition 3 d’interblocage
par SWAP).
3. Sous‐ensemble3 : prévention dynamique (algorithme du Banquier)
4. Sous‐ensemble4 : prévention par allocation globale (éviter la condition 2
d’interblocage par pré‐allocation d’espace en mémoire secondaire pour chaque
job en déclarant une taille maximale).

6
SWAP : opération de transfert de contenu entre deux types de mémoires (ex : stocker le
contenu non actif de la RAM dans le disque dur (mémoire virtuelle))

Faculté des Sciences Département de Mathématiques et Informatique

53
 Références

Références

[1] F. S. P. B. J‐L. Peterson, Operating systems concepts, Fourth Edition.

[2] Crocus, Systèmes d’exploitation des ordinateurs, Dunod informatique, 1975.

[3] B. B. J. Beauquier, Systèmes d’exploitation : concepts et algorithmes, McGraw Hill , 1990.

[4] P. B. G. A. Silberschatz, Principes des systèmes d’exploitation, 4e Edition, Addison

Wessley.

[5] A. S. Tanenbaum, Moderrn operating systems, Prentice Hall, Second Edition .

[6] t. p. G. Maurice J.Bach, Conception du système UNIX, Masson et Prentice Hall , 1990.

Faculté des Sciences Département de Mathématiques et Informatique

54