Chapitre 5 : Les mécanismes de synchronisation
Sémaphore d’exclusion mutuelle
Les sémaphores peuvent être utilisés pour résoudre le problème de l’exclusion mutuelle.
Avant d’entrer dans sa section critique, tout processus doit faire une demande explicite. Cette demande peut être bloquante (si la section critique est occupée). Intuitivement cette demande se traduit par l’exécution de l’opération P, seule opération bloquante sur les sémaphores.
Le processus sortant doit libérer la section critique permettant à un autre processus bloqué à l’entrée d’y accéder. Intuitivement cette libération se traduit par l’exécution de l’opération V, seule opération pouvant s’accompagner d’un déblocage de processus.
Mais la question importante est de savoir quelle est la valeur initiale devant être donnée au sémaphore utilisé ?
La valeur du compteur représente le nombre de tickets disponibles. Elle détermine par conséquent le nombre d’autorisations pouvant être accordées en même temps aux processus pour franchir cette barrière. Mais le nombre de processus autorisé de passer dans la section critique en même temps est égal à 1 (exclusion mutuelle). Donc, cette valeur ne devra jamais dépasser la valeur 1.
Il faut utiliser un sémaphore (mutex) initialisé à 1
Les deux sections de ce protocole se définissent de la manière suivante :
Prologue (section d’entrée) :
MUTEX.P() ;
/*plus besoin d’une boucle pour faire attendre le processus. L’opération P bloque le progrès du processus si la section critique n’est pas libre*/
Epilogue (section d’entrée) :
MUTEX .V() ;
/*s’il y a un processus en attente alors il sera automatiquement débloqué*/
Le comportement des processus est décrit par le schéma suivant :
while(1)
{
< Section Restante
MUTEX .P() ;
< Section Critique >
MUTEX .V() ;
}
Les processus doivent s’exécuter selon le schéma suivant :
Pour établir la validité de cette solution, il faut montrer :
Qu’à tout instant, un processus au plus se trouve dans la section critique
Lorsque aucun processus ne se trouve dans la section critique, l’entrée en section critique se fait au bout d’un temps fini
Pour étudier la réalisation de l’exclusion mutuelle. On va démontrer que le nombre de processus se trouvant en section critique à un instant donné est toujours inférieur ou égal à 1.
Le nombre de processus se trouvant dans la section critique est donné par :
nombre de processus ayant franchi le sémaphore
-
nombre de processus ayant quitté la section critique
C’est à dire : NF – NV
Par ailleurs, nous savons que NF = min (NP, NV + 1) /*compteur0==1*/
Donc, NF = NV + 1 ce qui implique NF – NV = 1
Par conséquent, l’exclusion mutuelle est réalisée.
Pour étudier la vérification de la condition de progression
On va effectuer un raisonnement par l’absurde :
Si aucun processus ne se trouve dans la section critique alors on aurait :
NF – NV == 0 c’est à dire NF == NV
S’il existe de processus attendant derrière le sémaphore MUTEX, alors on aurait :
NF < NP
Mais, NF == min (NP, NV + 1). Dans ce cas, NF serait égale à NV + 1
Donc, (NF == NV + 1) et (NF == NV) en même temps. D’où la contradiction. Par conséquent, la condition de progression est réalisée.
Ca déchire hein ?
