Qu’est-ce qu’un sémaphore?

Un sémaphore est un concept de programmation fréquemment utilisé pour résoudre des problèmes de multithreading. Ma question à la communauté:

Qu’est-ce qu’un sémaphore et comment l’utilisez-vous?

    Pensez aux sémaphores comme des videurs dans une boîte de nuit. Il y a un nombre dédié de personnes autorisées dans le club en même temps. Si le club est plein, personne n’est autorisé à entrer, mais dès qu’une personne quitte une autre personne peut entrer.

    C’est simplement un moyen de limiter le nombre de consommateurs pour une ressource spécifique. Par exemple, pour limiter le nombre d’appels simultanés à une firebase database dans une application.

    Voici un exemple très pédagogique en C # 🙂

    using System; using System.Collections.Generic; using System.Text; using System.Threading; namespace TheNightclub { public class Program { public static Semaphore Bouncer { get; set; } public static void Main(ssortingng[] args) { // Create the semaphore with 3 slots, where 3 are available. Bouncer = new Semaphore(3, 3); // Open the nightclub. OpenNightclub(); } public static void OpenNightclub() { for (int i = 1; i < = 50; i++) { // Let each guest enter on an own thread. Thread thread = new Thread(new ParameterizedThreadStart(Guest)); thread.Start(i); } } public static void Guest(object args) { // Wait to enter the nightclub (a semaphore to be released). Console.WriteLine("Guest {0} is waiting to entering nightclub.", args); Bouncer.WaitOne(); // Do some dancing. Console.WriteLine("Guest {0} is doing some dancing.", args); Thread.Sleep(500); // Let one guest out (release one semaphore). Console.WriteLine("Guest {0} is leaving the nightclub.", args); Bouncer.Release(1); } } } 

    L’article Mutexes and Semaphores Demystified de Michael Barr est une brève introduction à ce qui rend les mutex et les sémaphores différents, et à quel moment ils devraient et ne devraient pas être utilisés. J’ai extrait plusieurs paragraphes clés ici.

    Le point clé est que les mutex doivent être utilisés pour protéger les ressources partagées, tandis que les sémaphores doivent être utilisés pour la signalisation. Vous ne devez généralement pas utiliser de sémaphores pour protéger les ressources partagées, ni les mutex pour la signalisation. Il y a des problèmes, par exemple, avec l’analogie du videur en termes d’utilisation des sémaphores pour protéger les ressources partagées – vous pouvez les utiliser de cette façon, mais cela peut rendre difficile le diagnostic des bogues.

    Alors que les mutex et les sémaphores présentent des similitudes dans leur implémentation, ils doivent toujours être utilisés différemment.

    La réponse la plus courante (mais néanmoins incorrecte) à la question posée en haut est que les mutex et les sémaphores sont très similaires, la seule différence significative étant que les sémaphores peuvent compter plus d’un. Presque tous les ingénieurs semblent comprendre qu’un mutex est un indicateur binary utilisé pour protéger une ressource partagée en assurant une exclusion mutuelle dans les sections critiques du code. Mais lorsqu’on leur a demandé comment utiliser un “sémaphore de comptage”, la plupart des ingénieurs – ne variant que par leur degré de confiance – expriment une certaine opinion du manuel, à savoir qu’ils sont utilisés pour protéger plusieurs ressources équivalentes.

    À ce stade, une analogie intéressante est faite en utilisant l’idée de clés de salle de bain comme protection des ressources partagées – la salle de bain. Si un magasin dispose d’une seule salle de bains, une seule clé suffit pour protéger cette ressource et empêcher plusieurs personnes de l’utiliser simultanément.

    S’il y a plusieurs salles de bains, on pourrait être tenté de les reproduire de la même manière et de créer plusieurs clés – ceci est similaire à un sémaphore mal utilisé. Une fois que vous avez une clé, vous ne savez pas réellement quelle salle de bain est disponible, et si vous suivez ce chemin, vous allez probablement finir par utiliser des mutex pour fournir ces informations et vous assurer de ne pas prendre une salle de bain déjà occupée. .

    Un sémaphore est le mauvais outil pour protéger plusieurs ressources essentiellement identiques, mais c’est le nombre de personnes qui y pensent et l’utilisent. L’analogie avec le videur est nettement différente: il n’y a pas plusieurs types de ressources identiques, mais une seule ressource pouvant accepter plusieurs utilisateurs simultanés. Je suppose qu’un sémaphore peut être utilisé dans de telles situations, mais il y a rarement des situations réelles où l’analogie existe réellement – il y en a plus souvent du même type, mais des ressources individuelles, comme les salles de bains, qui ne peuvent pas être utilisées par ici.

    L’utilisation correcte d’un sémaphore sert à signaler une tâche à une autre. Un mutex est destiné à être pris et publié, toujours dans cet ordre, par chaque tâche utilisant la ressource partagée qu’il protège. En revanche, les tâches qui utilisent des sémaphores signalent ou attendent – pas les deux. Par exemple, la tâche 1 peut contenir du code pour afficher (c.-à-d. Signaler ou incrémenter) un sémaphore particulier lorsque le bouton “power” est enfoncé et la tâche 2, qui réveille l’affichage, sur ce même sémaphore. Dans ce scénario, une tâche est le producteur du signal d’événement; l’autre le consommateur.

    Ici, un point important est fait que les mutex interfèrent avec les systèmes d’exploitation en temps réel de manière incorrecte, provoquant une inversion de priorité où une tâche moins importante peut être exécutée avant une tâche plus importante en raison du partage des ressources. En bref, cela se produit lorsqu’une tâche de moindre priorité utilise un mutex pour récupérer une ressource, A, puis essaie de saisir B, mais est suspendue car B n’est pas disponible. En attendant, une tâche de priorité supérieure est nécessaire et nécessite A, mais elle est déjà liée et par un processus qui ne fonctionne même pas car il attend B. Il existe plusieurs façons de résoudre ce problème, mais le plus souvent, il est résolu en modifiant le mutex et le gestionnaire de tâches. Le mutex est beaucoup plus complexe dans ces cas-là qu’un sémaphore binary, et l’utilisation d’un sémaphore dans un tel cas entraînera des inversions de priorité car le gestionnaire de tâches ignore l’inversion de priorité et ne peut pas agir pour le corriger.

    La cause de la confusion moderne généralisée entre mutex et sémaphores est historique, car elle remonte à l’invention du sémaphore en 1974 (capitale “S” dans cet article) par Djikstra. Avant cette date, aucun des mécanismes de synchronisation et de signalisation des tâches sans interruption connus des informaticiens ne pouvait être utilisé de manière efficace pour plus de deux tâches. Le Sémaphore révolutionnaire, sûr et évolutif de Dijkstra a été appliqué à la fois à la protection des sections critiques et à la signalisation. Et ainsi la confusion a commencé.

    Cependant, il est devenu évident par la suite pour les développeurs de systèmes d’exploitation, après l’apparition du RTOS préventif basé sur les priorités (par exemple, VRTX, vers 1980), la publication des articles universitaires établissant RMA et les problèmes causés par protocoles d’inheritance en 1990 3, il est apparu que les mutex doivent être plus que de simples sémaphores avec un compteur binary.

    Mutex: partage de ressources

    Sémaphore: signalisation

    N’utilisez pas l’un pour l’autre sans une attention particulière aux effets secondaires.

    Mutex: access membre exclusif à une ressource

    Sémaphore: access n-membre à une ressource

    En d’autres termes, un mutex peut être utilisé pour synchroniser l’access à un compteur, à un fichier, à une firebase database, etc.

    Un sempahore peut faire la même chose mais supporte un nombre fixe d’appels simultanés. Par exemple, je peux emballer mes appels de firebase database dans un sémaphore (3) afin que mon application multithread atteigne la firebase database avec au maximum 3 connexions simultanées. Toutes les tentatives seront bloquées jusqu’à ce que l’un des trois emplacements s’ouvre. Ils font des choses comme faire des étranglements naïfs vraiment très faciles.

    @Craig:

    Un sémaphore est un moyen de verrouiller une ressource de sorte qu’il est garanti que, lorsqu’un morceau de code est exécuté, seul ce morceau de code a access à cette ressource. Cela empêche deux threads d’accéder simultanément à une ressource, ce qui peut entraîner des problèmes.

    Ceci n’est pas limité à un seul thread. Un sémaphore peut être configuré pour permettre à un nombre fixe de threads d’accéder à une ressource.

    Le sémaphore peut également être utilisé comme sémaphore. Par exemple, si vous disposez de plusieurs données de mise en queue de processus dans une queue et d’une seule tâche utilisant des données de la queue. Si vous ne voulez pas que votre tâche fastidieuse interroge constamment la queue pour y trouver des données disponibles, vous pouvez utiliser le sémaphore.

    Ici, le sémaphore n’est pas utilisé comme mécanisme d’exclusion, mais comme mécanisme de signalisation. La tâche consommasortingce attend sur le sémaphore La tâche de production est en cours de publication sur le sémaphore.

    De cette façon, la tâche consommasortingce est en cours d’exécution uniquement lorsque des données doivent être retirées.

    Il existe deux concepts essentiels à la création de programmes concurrents: la synchronisation et l’exclusion mutuelle. Nous verrons comment ces deux types de verrous (les sémaphores sont plus généralement une sorte de mécanisme de locking) nous aident à réaliser la synchronisation et l’exclusion mutuelle.

    Un sémaphore est un concept de programmation qui nous aide à atteindre la simultanéité en mettant en œuvre à la fois la synchronisation et l’exclusion mutuelle. Les sémaphores sont de deux types, binarys et comptage.

    Un sémaphore comporte deux parties: un compteur et une liste de tâches en attente d’access à une ressource particulière. Un sémaphore effectue deux opérations: wait (P) [c’est comme acquérir un verrou], et release (V) [similaire à libérer un verrou] – ce sont les deux seules opérations que l’on peut effectuer sur un sémaphore. Dans un sémaphore binary, le compteur va logiquement entre 0 et 1. Vous pouvez le considérer comme un verrou avec deux valeurs: ouvert / fermé. Un sémaphore de comptage a plusieurs valeurs pour le compte.

    Ce qu’il est important de comprendre, c’est que le compteur de sémaphores garde la trace du nombre de tâches qui ne doivent pas être bloquées, c’est-à-dire qu’elles peuvent progresser. Les tâches bloquent et s’ajoutent à la liste des sémaphores uniquement lorsque le compteur est à zéro. Par conséquent, une tâche est ajoutée à la liste dans la routine P () si elle ne peut pas progresser et “libérée” à l’aide de la routine V ().

    Maintenant, il est assez évident de voir comment les sémaphores binarys peuvent être utilisés pour résoudre les problèmes de synchronisation et d’exclusion mutuelle – ce sont essentiellement des verrous.

    ex. Synchronisation:

     thread A{ semaphore &s; //locks/semaphores are passed by reference! think about why this is so. A(semaphore &s): s(s){} //constructor foo(){ ... sP(); ;// some block of code B2 ... } //thread B{ semaphore &s; B(semaphore &s): s(s){} //constructor foo(){ ... ... // some block of code B1 sV(); .. } main(){ semaphore s(0); // we start the semaphore at 0 (closed) A a(s); B b(s); } 

    Dans l’exemple ci-dessus, B2 ne peut s’exécuter qu’une fois l’exécution de B1 terminée. Disons que le thread A est exécuté en premier – il arrive à sem.P () et attend car le compteur est 0 (fermé). Le fil B arrive, termine B1, puis libère le fil A – qui complète alors B2. Nous réalisons donc la synchronisation.

    Examinons maintenant l’exclusion mutuelle avec un sémaphore binary:

     thread mutual_ex{ semaphore &s; mutual_ex(semaphore &s): s(s){} //constructor foo(){ ... sP(); //critical section sV(); ... ... sP(); //critical section sV(); ... } main(){ semaphore s(1); mutual_ex m1(s); mutual_ex m2(s); } 

    L’exclusion mutuelle est également assez simple: m1 et m2 ne peuvent pas entrer dans la section critique en même temps. Ainsi, chaque thread utilise le même sémaphore pour fournir une exclusion mutuelle pour ses deux sections critiques. Maintenant, est-il possible d’avoir plus de concurrence? Dépend des sections critiques. (Pensez à la façon dont on pourrait utiliser les sémaphores pour parvenir à l’exclusion mutuelle… indice: dois-je nécessairement utiliser un seul sémaphore?)

    Sémaphore de comptage: Sémaphore avec plus d’une valeur. Regardons ce que cela implique – un verrou avec plus d’une valeur ?? Alors ouvert, fermé et … hmm. A quoi sert un locking multi-étages en exclusion ou synchronisation mutuelle?

    Prenons le plus facile des deux:

    Synchronisation à l’aide d’un sémaphore de comptage: Supposons que vous ayez 3 tâches à exécuter après 1 et 2. Comment concevez-vous votre synchronisation?

     thread t1{ ... sP(); //block of code B1 thread t2{ ... sP(); //block of code B2 thread t3{ ... //block of code B3 sV(); sV(); } 

    Donc, si votre sémaphore démarre fermé, vous vous assurez que t1 et t2 bloquent, soyez ajouté à la liste du sémaphore. Puis vient tout important t3, termine son activité et libère t1 et t2. Dans quel ordre sont-ils libérés? Dépend de l’implémentation de la liste du sémaphore. Pourrait être FIFO, pourrait être basé sur une priorité particulière, etc. (Remarque: réfléchissez à la manière d’organiser vos P et V; si vous vouliez que t1 et t2 soient exécutés dans un ordre particulier, et si vous ne connaissiez pas l’implémentation du sémaphore)

    (Découvrez ce qui se passe si le nombre de V est supérieur au nombre de P?)

    Exclusion mutuelle En utilisant des sémaphores de comptage: je voudrais que vous construisiez votre propre pseudocode pour cela (vous fait mieux comprendre les choses!) – mais le concept fondamental est le suivant: un sémaphore de comptage = N permet à N tâches d’entrer librement dans la section critique . Cela signifie que vous avez N tâches (ou threads, si vous préférez) entrer dans la section critique, mais que la tâche N + 1 est bloquée (va sur notre liste de tâches bloquées favorites) et que seule la personne S est le sémaphore au moins une fois. Ainsi, le compteur de sémaphores, au lieu de basculer entre 0 et 1, passe maintenant entre 0 et N, permettant à N tâches d’entrer et de sortir librement, ne bloquant personne!

    Maintenant, pourquoi aurais-tu besoin d’une chose aussi stupide? Le point d’exclusion mutuelle ne consiste-t-il pas à ne pas laisser plus d’un gars accéder à une ressource? (Astuce Astuce … Vous n’avez pas toujours un seul lecteur dans votre ordinateur, n’est-ce pas …?)

    Penser à : L’exclusion mutuelle est-elle obtenue en ayant un sémaphore de comptage seul? Que se passe-t-il si vous avez 10 instances d’une ressource et 10 threads (via le sémaphore de comptage) et essayez d’utiliser la première instance?

    Considérez, un taxi qui peut accueillir un total de 3 ( arrière ) +2 ( avant ) personnes, y compris le conducteur. Ainsi, un semaphore ne permet que 5 personnes à la fois dans une voiture. Et un mutex ne permet qu’une seule personne sur un seul siège de la voiture.

    Par conséquent, Mutex doit autoriser l’access exclusif à une ressource ( comme un thread OS ) alors qu’un Semaphore doit autoriser l’access à un nombre de ressources à la fois.

    Un sémaphore est un object contenant un nombre naturel (c’est-à-dire un entier supérieur ou égal à zéro) sur lequel deux opérations de modification sont définies. Une opération, V , ajoute 1 au naturel. L’autre opération, P , diminue le nombre naturel de 1. Les deux activités sont atomiques (c’est-à-dire qu’aucune autre opération ne peut être exécutée en même temps qu’un V ou un P ).

    Comme le nombre naturel 0 ne peut pas être diminué, l’appel de P sur un sémaphore contenant un 0 bloque l’exécution du processus appelant (/ thread) jusqu’à ce que le nombre ne soit plus 0 et que P puisse être exécuté (de manière atomique) avec succès .

    Comme mentionné dans d’autres réponses, les sémaphores peuvent être utilisés pour restreindre l’access à une ressource donnée à un nombre maximal (mais variable) de processus.

    Un drapeau matériel ou logiciel Dans les systèmes multi-tâches, un sémaphore est une variable avec une valeur qui indique l’état d’une ressource commune. Un processus nécessitant la ressource vérifie le sémaphore pour déterminer l’état des ressources et décide ensuite comment procéder.

    Alors, imaginez que tout le monde essaie d’aller à la salle de bain et qu’il n’y ait qu’un certain nombre de clés dans la salle de bain. Maintenant, s’il n’y a plus assez de clés, cette personne doit attendre. Alors, pensez à sémaphore comme représentant l’ensemble des clés disponibles pour les salles de bains (les ressources système) auxquelles différents processus (utilisateurs de salles de bain) peuvent demander l’access.

    Imaginez maintenant deux processus qui tentent d’aller à la salle de bain en même temps. Ce n’est pas une bonne situation et les sémaphores sont utilisés pour empêcher cela. Malheureusement, le sémaphore est un mécanisme volontaire et les processus (nos utilisateurs de salle de bain) peuvent l’ignorer (c.-à-d. Que même s’il y a des clés, quelqu’un peut toujours ouvrir la porte).

    Il existe également des différences entre les sémaphores binarys / mutex et de comptage.

    Consultez les notes de cours à l’ adresse http://www.cs.columbia.edu/~jae/4118/lect/L05-ipc.html .

    C’est une vieille question mais l’une des utilisations les plus intéressantes des sémaphores est un verrou en lecture / écriture et il n’a pas été explicitement mentionné.

    Les serrures r / w fonctionnent de manière simple: consumz un permis pour un lecteur et tous les permis pour les écrivains. En effet, une implémentation sortingviale de ar / w lock nécessite une modification des métadonnées à la lecture (en fait deux fois) qui peut devenir un goulot d’étranglement, toujours nettement meilleure qu’un mutex ou un verrou.

    Un autre inconvénient est que les rédacteurs peuvent être lancés assez facilement, à moins que le sémaphore ne soit correct ou que les écritures ne soient autorisées dans plusieurs requêtes. Dans ce cas, elles ont besoin d’un mutex explicite entre elles.

    Lire plus loin:

    J’ai créé la visualisation qui devrait aider à comprendre l’idée. Sémaphore contrôle l’access à une ressource commune dans un environnement multithreading. entrer la description de l'image ici

     ExecutorService executor = Executors.newFixedThreadPool(6); Semaphore semaphore = new Semaphore(4); Runnable longRunningTask = () -> { boolean permit = false; try { permit = semaphore.tryAcquire(1, TimeUnit.SECONDS); if (permit) { System.out.println("Semaphore acquired"); Thread.sleep(5); } else { System.out.println("Could not acquire semaphore"); } } catch (InterruptedException e) { throw new IllegalStateException(e); } finally { if (permit) { semaphore.release(); } } }; // execute tasks for (int j = 0; j < 10; j++) { executor.submit(longRunningTask); } executor.shutdown(); 

    Sortie

     Semaphore acquired Semaphore acquired Semaphore acquired Semaphore acquired Could not acquire semaphore Could not acquire semaphore 

    Exemple de code de l' article

    Un sémaphore est un moyen de verrouiller une ressource de sorte qu’il est garanti que, lorsqu’un morceau de code est exécuté, seul ce morceau de code a access à cette ressource. Cela empêche deux threads d’accéder simultanément à une ressource, ce qui peut entraîner des problèmes.