Sémaphores et problème des philosophes dîneurs : synchronisation des processus
Résumé
Ce document présente les sémaphores, outils de synchronisation des processus basés sur les opérations atomiques Wait (P) et Signal (V). Il explique leur fonctionnement, leur utilisation pour gérer les ressources partagées et le passage de l'attente active au blocage des processus. Il traite ensuite du problème des philosophes dîneurs et de sa résolution par des sémaphores associés aux baguettes.
Points clés
- Un sémaphore est une variable entière accessible uniquement via les opérations atomiques Wait (P) et Signal (V).
- L'opération Wait décrémente le sémaphore et bloque le processus si sa valeur devient négative.
- L'opération Signal incrémente le sémaphore et débloque un processus en attente si la valeur est positive.
- Le blocage des processus évite l'attente active (spin lock), qui gaspille des cycles CPU.
- Dans le problème des philosophes dîneurs, cinq philosophes partagent cinq baguettes qu'ils ne peuvent prendre qu'une à la fois.
- Chaque baguette peut être représentée par un sémaphore pour résoudre le problème de l'allocation des ressources multiples.
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
Signalsur 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.
Télécharger
PDF Word HTMLQuestions fréquentes
Qu'est-ce qu'un sémaphore en informatique ?
Un sémaphore est une variable entière non négative, accessible uniquement via les opérations atomiques Wait (P) et Signal (V). Il sert à synchroniser les processus et à contrôler l'accès aux sections critiques.
Quelle est la différence entre attente active et blocage d'un processus ?
Avec l'attente active, le processus boucle en consommant des cycles CPU jusqu'à pouvoir accéder à la ressource. Avec le blocage, le processus est suspendu dans une file d'attente et le CPU est confié à un autre processus.
Comment les sémaphores résolvent-ils le problème des philosophes dîneurs ?
Chaque baguette est représentée par un sémaphore. Un philosophe exécute Wait sur la baguette qu'il veut prendre et Signal pour la reposer après avoir mangé.
Testez-vous
Fiches de révision
Cliquez sur une fiche pour voir la réponse.
Test
Questions générées par IA à partir du document : vérifiez les réponses avec le texte.