Sémaphores : Synchronisation et Problème des Philosophes Dîneurs
Classé dans Informatique
Écrit le en français avec une taille de 4,31 KB
Les Sémaphores : Un Outil de Synchronisation
Les sémaphores sont des outils fondamentaux de synchronisation utilisés pour résoudre les problèmes liés aux sections critiques et à la coordination des processus. Un sémaphore est une variable entière, accessible uniquement via deux opérations atomiques : Wait
(souvent notée P
) et Signal
(souvent notée V
). Lorsqu'un processus modifie la valeur d'un sémaphore, aucun autre processus ne peut le faire simultanément.
Un sémaphore est initialisé avec une valeur non négative. L'opération Wait(s)
décrémente la valeur du sémaphore s
. Si la valeur de s
devient négative, le processus appelant est bloqué. L'opération Signal(s)
incrémente la valeur du sémaphore s
. Si la valeur de s
est positive (après incrémentation), un processus bloqué par Wait
est débloqué.
La définition classique de ces opérations est la suivante :
P(s):
while (s <= 0) { /* attente active */ }
s--;
V(s):
s++;
Les systèmes d'exploitation utilisent des sémaphores pour contrôler l'accès aux sections critiques ou pour gérer le partage des ressources. Un sémaphore est généralement initialisé avec une valeur correspondant au nombre de ressources disponibles. Chaque processus souhaitant utiliser une ressource effectue une opération Wait
sur le sémaphore. Lorsqu'il libère la ressource, il effectue une opération Signal
. Lorsque le compteur du sémaphore atteint 0, toutes les ressources sont utilisées. Les processus qui tentent d'acquérir une ressource sont alors bloqués jusqu'à ce que le compteur redevienne supérieur à 0.
Mise en Œuvre des Sémaphores
L'une des problématiques soulevées par la définition simple de P(s)
est l'attente active (ou "spin lock"). Si un processus ne peut pas immédiatement accéder à une ressource (c'est-à-dire si s <= 0
), il entre dans une boucle d'attente, gaspillant ainsi des cycles CPU. Pour éviter ce problème, on utilise une méthode de blocage :
- Lorsqu'un processus ne peut pas accéder à la ressource, il est suspendu et placé dans une file d'attente associée au sémaphore.
- Le processus passe alors à l'état "bloqué" ou "en attente".
- Le contrôle est ensuite rendu à l'ordonnanceur du CPU, qui sélectionne un autre processus à exécuter.
- Un processus bloqué sur un sémaphore est redémarré lorsqu'un autre processus exécute une opération
Signal
sur ce même sémaphore. - Le processus est alors "réveillé", ce qui change son état de "bloqué" à "prêt".
- Ce processus est ensuite placé dans la file d'attente des processus "prêts" pour être exécuté.
Le Problème des Philosophes Dîneurs
Le problème des philosophes dîneurs est un problème classique de synchronisation, servant d'exemple pour une large classe de problèmes de contrôle de concurrence. C'est une représentation simple de la nécessité d'allouer des ressources multiples entre plusieurs processus.
Imaginez cinq philosophes qui passent leur vie à penser et à manger. Ils partagent une table ronde avec cinq chaises, une pour chaque philosophe. Au centre de la table se trouvent un bol de riz et cinq baguettes.
- Quand un philosophe pense, il n'interagit pas avec ses collègues.
- Quand un philosophe a faim, il tente de prendre les deux baguettes les plus proches.
- Il ne peut prendre qu'une baguette à la fois.
- Il ne peut pas prendre une baguette déjà tenue par un autre philosophe.
- Pendant qu'il mange, il ne libère pas les baguettes. Une fois qu'il a fini de manger, il les repose et recommence à penser.
Solution avec les Sémaphores
Pour résoudre ce problème, chaque baguette peut être représentée par un sémaphore. Un philosophe tente de prendre une baguette en exécutant une opération Wait
sur le sémaphore correspondant à cette baguette. Il libère les baguettes avec une opération Signal
une fois qu'il a fini de manger.