Système d’Exploitation 1

Chapitre 5 : Exclusion mutuelle et synchronisation

1 ère Année Second Cycle
(partie 3)

Dr. M. Baba Ahmed

1
Plan (partie 3)
Implantation des primitives P et V
Synchronisation des processus
Définition
Expression des contraintes de synchronisation
Spécification de la synchronisation
Les problèmes-types
Les techniques de synchronisation
Allocateur de ressources
Le rendez-vous
Le modèle des lecteurs/rédacteurs
Schéma général du producteur-consommateur
Le problème du diner des philosophes

2
 Les sémaphores de Dijkstra (implémentation)
• Soit à gérer deux ressources critiques R1 et R2:
• Pour cela il faut utiliser deux sémaphores SR1
et SR2

La solution précédente peut mener à une

situation d’interblocage.
Pour éviter cette situation :
Les processus utilisant les mêmes ressources
demandent celles-ci dans le même ordre

3
 La synchronisation des processus (définition)
• Un mécanisme de synchronisation doit permettre à un processus actif :
o De se bloquer (attendre une ressource ou un signal d’un autre processus)

o D’activer un autre processus en lui envoyant un signal.

• Synchronisation directe: Le processus envoie un signal à un autre processus en le désignant par son
identificateur (ou par son nom)

• Exemple : les signaux: SIGSTOP, SIGCONT, SIGCHLD,…

• Synchronisation indirecte: Le processus envoie un signal(sans désigner un processus)

• Exemple : Opération V sur un sémaphore.

4
 Spécification de la synchronisation des processus
• La spécification d’un problème de synchronisation consiste à :

• Définir pour chaque processus ses points de synchronisation/rendez vous

• Associer à chaque point de synchronisation une condition de franchissement.

Remarque :

• les points de rendez-vous sont des emplacements dans le code où les processus peuvent se synchroniser

• Les conditions de franchissement sont exprimées au moyen des variables d’état du système (état d’une
ressource : libre ou occupée, nombre de ressources libres …)

5
 Les problèmes types (Allocateur d’une seule ressource)
Schéma général :

• m processus se partagent une seule imprimante.

• L’imprimante est une ressource critique :

elle doit être utilisée en exclusion mutuelle

Solution avec les sémaphores:

• Soit mutex le sémaphore d’exclusion mutuelle

protégeant cette imprimante

6
 Les problèmes types (Allocateur de plusieurs
ressources)
• Schéma général d’un processus i

• Exemple: m processus se partagent n imprimantes

• Solution à l’aide des sémaphores:

• On utilise un sémaphore représentant le nombre

de ressources libres (imprimantes libres) : nblibres.

7
 Les problèmes types (Allocateur de plusieurs
ressources)
• La ressource « imprimante » est une ressource composée de n exemplaires

• Chaque unité ou exemplaire est une ressource critique

• n processus peuvent utiliser ces n imprimantes en même temps

• Condition de franchissement de points de synchronisation : Allocation d’une imprimante si nbre_imp_libre

>0

8
Les problèmes types (Rendez-vous de processus)
Rendez-vous de deux processus
On utilise des sémaphores de synchronisation
initialisé a 0

Rendez-vous de trois processus

Signaler a P2 et P3 de son arrivé

Attente de l’arrivé de P2 et P3

9
 Les problèmes types (Rendez-vous de processus)
Rendez-vous de n processus :
Une variable partagée et deux sémaphores compteur
La variable c’est un compteur qui permet de compter
les arrivées des processus(nombre de processus arrivés)
.
Deux sémaphores : Si oui ou non

• Le compteur est partagé donc il doit être protégé

par un sémaphore d’exclusion mutuelle initialisé à
un.
• Un sémaphore de synchronisation permettant de
mettre en attente les processus ce sémaphore est
initialisé à zéro
10
Les problèmes types (Lecteurs/Rédacteurs)
• Considérons deux classes de processus appelés : Lecteurs et Rédacteurs.

• Ces processus se partagent un fichier f.

• Les lecteurs peuvent seulement consulter le fichier

• les rédacteurs peuvent seulement écrire sur le fichier.

Les processus de ces deux classes doivent respecter les contraintes suivantes:

• Plusieurs lecteurs peuvent lire simultanément le fichier.

• Un seul rédacteur à la fois peut écrire sur le fichier.

• Un lecteur et un rédacteur ne peuvent pas utiliser en même temps le fichier.

11
Les problèmes types (Lecteurs/Rédacteurs)
• Un rédacteur : Exclut les autres rédacteurs ainsi que tous les lecteurs.

• L’accès en écriture se fait en exclusion mutuelle

• Un sémaphore appelé acces initialisé à 1.

• Un lecteur :

• Exclut les rédacteurs mais pas les autres lecteurs.

• On utilise deux sémaphores :

• Un pour l’accès à la variable nl (qui sert à connaitre où est le premier et le dernier lecteur),

• Et un autre qui sert à l’accès en lecture (acces)

12
Les problèmes types (Producteur/Consommateur)
• Soit T un tampon(buffer) accessible à 2 processus voulant communiquer. On distingue deux
processus :

• Producteur : processus désirant déposer de l’information dans un tampon T

• Consommateur : un processus désirant retirer de l’information d’un tampon T.

Contraintes de synchronisation

• Le producteur ne peut déposer un message que s’il y a de la place disponible dans le tampon.

• Le consommateur ne peut retirer un message que s’il y en a de disponible.

• Le producteur et les consommateurs ne peuvent accéder simultanément à la même case.

• La politique de gestion du tampon est FIFO

13
Les problèmes types (Producteur/Consommateur)
Gestion du tampon:

• Le tampon contient N cases (éléments)

• Le tampon sera géré de manière circulaire

• Les éléments du tampon sont numérotés de 0 à N-1.

• On considère l'élément 0 comme le successeur de l'élément N-1.

Il y a deux types de ressources critiques: les cases vides et les cases pleines.

• On associe un sémaphore à chacune des ressources critiques :

o Le sémaphore Vide initialisé au nombre de cases vides soit N

o Le sémaphore Plein initialisé à 0.

14
Les problèmes types (Producteur/Consommateur)
• Le producteur s’alloue une case vide par une opération P(Vide)

• Il remplit cette case vide et de ce fait génère une case pleine qu’il signale par une opération V(Plein).

• Cette opération réveille éventuellement le consommateur en attente d’une case pleine.

Problème :

• p producteurs et c consommateurs

• Ce cas pose deux problèmes d'exclusion mutuelle :

Exclusion mutuelle entre producteurs concurrence pour l’accès à l’index i

Solution: sémaphore d’exclusion mutuelle: Mutexi

Exclusion mutuelle entre consommateurs concurrence pour l’accès à l’index j

Solution: sémaphore d’exclusion mutuelle: Mutexj

15
Les problèmes types (Diner des philosophes)
• Un problème théorique proposé par Dijkstra.

• Cinq (5) philosophes sont assis autour d’une table circulaire.

• Un philosophe passe son temps à manger et à penser.

• Sur la table, il y a alternativement cinq plats et cinq fourchettes

• Pour manger, un philosophe a besoin de deux fourchettes qui

sont de part et d’autre de son plat.

16
Les problèmes types (Diner des philosophes)
• A tout instant, chaque philosophe est dans l’un des états suivants :

o il mange avec deux fourchettes (de droite et de gauche)

o il a faim, et attend la fourchette de droite, celle de gauche ou les deux

o il pense, et n’utilise pas de fourchette.

• Initialement, tous les philosophes pensent.

• Un philosophe qui mange s’arrête en un temps borné.

• Dîner des philosophes à un instant donné :

o Si un philosophe mange, ces deux voisins immédiats

ne peuvent pas manger.

17
Les problèmes types (Diner des philosophes)
• Les fourchettes sont des ressources partagées pour lesquelles les philosophes sont en concurrence.

• On représente les philosophes par des processus.

18
 Les problèmes types (Diner des philosophes)
• Chaque fourchette est représentée par un sémaphore initialisé à 1. ou un philosophe appelle
P(fourchette) avant de prendre une fourchette et appelle le V(fourchette) pour la libérer.

Sémaphore Interblocage possible

(si tous les philosophes
prennent
la fourchette de gauche,
personne
droite ne pourra prendre la fourchette
gauche */
à sa droite)

droite
gauche */

19
Les problèmes types (Diner des philosophes)
• Chaque philosophe a trois états : « PENSE », « A FAIM », « MANGE»

• Par lesquels il passe toujours dans cet ordre

• Lorsqu'il a faim, un philosophe peut manger que si ses deux voisins ne mangent pas, sinon attend

• Lorsqu'il termine de manger, le philosophe réveille ses voisins et se remet à penser

• Un sémaphore est attribué à chaque philosophe.

• Un philosophe qui veut prendre les fourchettes (donc manger) déclare qu'il a faim.
o Si l'un de ses deux voisins est en train de manger, il se met en attente.
o Si les deux philosophes à côté ne mangent pas alors il peut prendre les deux fourchettes et déclarer
qu'il mange.
o Quand le philosophe a fini de manger, il déclare donc qu'il pense (et réveil ses 2 voisins s’ils sont
bloqués)
20
Les problèmes types (Diner des philosophes)

{PENSE, A_FAIM, MANGE }

21