Variable conditionnelle vs sémaphore

Réponses:

207

Les verrous sont utilisés pour l'exclusion mutuelle. Lorsque vous voulez vous assurer qu'un morceau de code est atomique, mettez un verrou autour de lui. Vous pourriez théoriquement utiliser un sémaphore binaire pour ce faire, mais c'est un cas particulier.

Les sémaphores et les variables de condition s'ajoutent à l'exclusion mutuelle fournie par les verrous et sont utilisés pour fournir un accès synchronisé aux ressources partagées. Ils peuvent être utilisés à des fins similaires.

Une variable de condition est généralement utilisée pour éviter l'attente occupée (boucle répétée lors de la vérification d'une condition) en attendant qu'une ressource devienne disponible. Par exemple, si vous avez un thread (ou plusieurs threads) qui ne peuvent pas continuer jusqu'à ce qu'une file d'attente soit vide, l'approche d'attente occupée serait de faire quelque chose comme:

//pseudocode
while(!queue.empty())
{
   sleep(1);
}

Le problème avec cela est que vous perdez du temps de processeur en demandant à ce thread de vérifier à plusieurs reprises la condition. Pourquoi ne pas avoir à la place une variable de synchronisation qui peut être signalée pour indiquer au thread que la ressource est disponible?

//pseudocode
syncVar.lock.acquire();

while(!queue.empty())
{
   syncVar.wait();
}

//do stuff with queue

syncVar.lock.release();

Vraisemblablement, vous aurez un thread ailleurs qui sort des choses de la file d'attente. Lorsque la file d'attente est vide, elle peut appeler syncVar.signal()pour réveiller un thread aléatoire qui est endormi syncVar.wait()(ou il y a généralement aussi un signalAll()oubroadcast() méthode pour réveiller tous les threads en attente).

J'utilise généralement des variables de synchronisation comme celle-ci lorsque j'ai un ou plusieurs threads en attente d'une seule condition particulière (par exemple pour que la file d'attente soit vide).

Les sémaphores peuvent être utilisés de la même manière, mais je pense qu'ils sont mieux utilisés lorsque vous avez une ressource partagée qui peut être disponible et indisponible en fonction d'un nombre entier d'éléments disponibles. Les sémaphores sont bons pour les situations de producteur / consommateur où les producteurs allouent des ressources et les consommateurs les consomment.

Pensez si vous aviez un distributeur automatique de boissons gazeuses. Il n'y a qu'une seule machine à soda et c'est une ressource partagée. Vous avez un thread qui est un fournisseur (producteur) qui est responsable de garder la machine en stock et N threads qui sont des acheteurs (consommateurs) qui veulent sortir les sodas de la machine. Le nombre de sodas dans la machine est la valeur entière qui pilotera notre sémaphore.

Chaque fil acheteur (consommateur) qui arrive à la machine à soda appelle la down()méthode du sémaphore pour prendre un soda. Cela récupérera un soda de la machine et décrémentera le nombre de sodas disponibles de 1. S'il y a des sodas disponibles, le code continuera juste à dépasser ledown() instruction sans problème. Si aucun sodas n'est disponible, le thread dormira ici en attendant d'être informé du moment où le soda sera à nouveau disponible (quand il y aura plus de sodas dans la machine).

Le fil du vendeur (producteur) attendrait essentiellement que la machine à soda soit vide. Le vendeur est averti lorsque le dernier soda est retiré de la machine (et un ou plusieurs consommateurs attendent potentiellement de sortir les sodas). Le vendeur réapprovisionnerait la machine à soda avec le sémaphoreup() méthode , le nombre de sodas disponibles augmenterait à chaque fois et ainsi les threads de consommation en attente seraient informés que plus de soda est disponible.

Les méthodes wait()et signal()d'une variable de synchronisation ont tendance à être cachées dans les opérations down()et up()du sémaphore.

Il y a certainement un chevauchement entre les deux choix. Il existe de nombreux scénarios dans lesquels un sémaphore ou une variable de condition (ou un ensemble de variables de condition) pourraient tous deux servir vos objectifs. Les sémaphores et les variables de condition sont associés à un objet de verrouillage qu'ils utilisent pour maintenir l'exclusion mutuelle, mais ils fournissent ensuite des fonctionnalités supplémentaires en plus du verrou pour synchroniser l'exécution des threads. C'est principalement à vous de déterminer lequel est le plus logique pour votre situation.

Ce n'est pas nécessairement la description la plus technique, mais c'est ainsi que cela a du sens dans ma tête.

Brent écrit le code
la source
9
Excellente réponse, je voudrais ajouter d'autres réponses donc: le sémaphore est utilisé pour contrôler le nombre de threads en cours d'exécution. Il y aura un ensemble fixe de ressources. Le nombre de ressources sera décrémenté à chaque fois qu'un thread possède la même chose. Lorsque le nombre de sémaphores atteint 0, aucun autre thread n'est autorisé à acquérir la ressource. Les threads sont bloqués jusqu'à ce que d'autres threads possédant des ressources libèrent. En bref, la principale différence est combien de threads sont autorisés à acquérir la ressource à la fois? Mutex - c'est UN. Sémaphore - son DEFINED_COUNT, (autant que le nombre de sémaphores)
berkay
10
Juste pour expliquer pourquoi il y a cette boucle while au lieu d'un simple if: quelque chose appelé spurios wakeup . Citant cet article de wikipedia : "L'une des raisons à cela est un faux réveil; c'est-à-dire qu'un thread peut être réveillé de son état d'attente même si aucun thread n'a signalé la variable de condition"
Vladislavs Burakovs
3
@VladislavsBurakovs Bon point! Je pense que c'est également utile dans le cas où une diffusion réveille plus de threads qu'il n'y a de ressources disponibles (par exemple, la diffusion réveille 3 threads, mais il n'y a que 2 éléments dans la file d'attente).
Brent écrit le code
J'aurais aimé que vous répondiez jusqu'à ce que la file d'attente soit pleine;) Perfect Answer. Ce code pourrait aider à trouver les sémaphores csc.villanova.edu/~mdamian/threads/PC.htm
Mohamad-Jaafar NEHME
3
@VladislavsBurakovs Pour clarifier un peu, la raison pour laquelle la condition peut toujours être fausse pour un thread qui vient de se réveiller (ce qui entraîne un faux réveil) est qu'il peut y avoir eu un changement de contexte avant que le thread ait une chance de vérifier la condition encore une fois, où un autre thread planifié a rendu cette condition fausse. C'est une des raisons que je connais pour un faux réveil, je ne sais pas s'il y en a plus.
Max
52

Révélons ce qu'il y a sous le capot.

La variable conditionnelle est essentiellement une file d'attente , qui prend en charge les opérations d'attente de blocage et de réveil, c'est-à-dire que vous pouvez mettre un thread dans la file d'attente et définir son état sur BLOCK, puis en extraire un thread et définir son état sur READY.

Notez que pour utiliser une variable conditionnelle, deux autres éléments sont nécessaires:

  • une condition (généralement implémentée en vérifiant un drapeau ou un compteur)
  • un mutex qui protège la condition

Le protocole devient alors,

  1. acquérir mutex
  2. vérifier l'état
  3. bloquer et libérer le mutex si la condition est vraie, sinon libérer le mutex

Le sémaphore est essentiellement un compteur + un mutex + une file d'attente. Et il peut être utilisé tel quel sans dépendances externes. Vous pouvez l'utiliser comme mutex ou comme variable conditionnelle.

Par conséquent, le sémaphore peut être traité comme une structure plus sophistiquée que la variable conditionnelle, tandis que cette dernière est plus légère et flexible.

cucufrog
la source
mutex peut être considéré comme une variable de conditions, sa condition est de savoir s'il doit être maintenu ou non.
宏杰 李
18

Les sémaphores peuvent être utilisés pour implémenter un accès exclusif aux variables, mais ils sont destinés à être utilisés pour la synchronisation. Les mutex, en revanche, ont une sémantique strictement liée à l'exclusion mutuelle: seul le processus qui a verrouillé la ressource est autorisé à la déverrouiller.

Malheureusement, vous ne pouvez pas implémenter la synchronisation avec des mutex, c'est pourquoi nous avons des variables de condition. Notez également qu'avec les variables de condition, vous pouvez déverrouiller tous les threads en attente au même instant en utilisant le déverrouillage de diffusion. Cela ne peut pas être fait avec des sémaphores.

Dacav
la source
9

Les variables de sémaphore et de condition sont très similaires et sont principalement utilisées aux mêmes fins. Cependant, il existe des différences mineures qui pourraient en rendre une préférable. Par exemple, pour implémenter la synchronisation des barrières, vous ne pourrez pas utiliser de sémaphore, mais une variable de condition est idéale.

La synchronisation de la barrière est lorsque vous voulez que tous vos threads attendent jusqu'à ce que tout le monde soit arrivé à une certaine partie de la fonction de thread. cela peut être implémenté en ayant une variable statique qui est initialement la valeur du nombre total de threads décrémenté par chaque thread lorsqu'il atteint cette barrière. cela signifierait que nous voulons que chaque thread s'endorme jusqu'à ce que le dernier arrive. Un sémaphore ferait exactement le contraire! avec un sémaphore, chaque thread continuerait à fonctionner et le dernier thread (qui mettra la valeur du sémaphore à 0) se mettra en veille.

une variable de condition, d'autre part, est idéale. lorsque chaque thread atteint la barrière, nous vérifions si notre compteur statique est égal à zéro. sinon, nous mettons le thread en veille avec la fonction d'attente de variable de condition. lorsque le dernier thread arrive à la barrière, la valeur du compteur sera décrémentée à zéro et ce dernier thread appellera la fonction de signal de variable de condition qui réveillera tous les autres threads!

Danielle
la source
1

Je classe les variables de condition sous la synchronisation du moniteur. J'ai généralement vu les sémaphores et les moniteurs comme deux styles de synchronisation différents. Il existe des différences entre les deux en ce qui concerne la quantité de données d'état intrinsèquement conservées et la manière dont vous souhaitez modéliser le code - mais il n'y a vraiment aucun problème qui puisse être résolu par l'un mais pas par l'autre.

J'ai tendance à coder vers la forme de moniteur; dans la plupart des langues dans lesquelles je travaille, cela se résume aux mutex, aux variables de condition et à certaines variables d'état de sauvegarde. Mais les sémaphores feraient aussi l'affaire.

Justin R
la source
2
Ce serait une meilleure réponse si vous expliquiez ce qu'est le «formulaire moniteur».
Steven Lu
0

Les mutexet conditional variablessont hérités de semaphore.

  • Pour mutex, le semaphoreutilise deux états: 0, 1
  • Pour condition variablesle semaphore compteur d'utilisations.

Ils sont comme du sucre syntaxique

Aqua
la source
Dans la bibliothèque std C ++, ce sont tous des objets de district, tous implémentés à l'aide d'API spécifiques à la plate-forme. Il est certain qu'un sémaphore débloquera le nombre de fois signalé, la variable de condition pourrait être signalée plusieurs fois mais ne débloquera qu'une seule fois. C'est pourquoi le wair prend un mutex comme paramètre.
doron