Spinlock contre sémaphore

Quelles sont les différences fondamentales entre un sémaphore et un verrou tournant?

Quand utiliserions-nous un sémaphore sur un verrou tournant?

Spinlock et sémaphore diffèrent principalement en quatre choses:

1. Ce qu'ils sont
Un verrou tournant est une implémentation possible d'un verrou, à savoir celle qui est implémentée par attente occupée («spinning»). Un sémaphore est une généralisation d'un verrou (ou, à l'inverse, un verrou est un cas particulier d'un sémaphore). Habituellement, mais pas nécessairement , les verrous rotatifs ne sont valides que dans un processus, tandis que les sémaphores peuvent également être utilisés pour synchroniser différents processus.

Un verrou fonctionne pour l'exclusion mutuelle, c'est-à-dire qu'un thread à la fois peut acquérir le verrou et procéder à une «section critique» de code. Habituellement, cela signifie du code qui modifie certaines données partagées par plusieurs threads.
Un sémaphore a un compteur et se permettra d'être acquis par un ou plusieurs threads, en fonction de la valeur que vous lui envoyez, et (dans certaines implémentations) en fonction de sa valeur maximale autorisée.

Dans la mesure où, on peut considérer un verrou comme un cas particulier d'un sémaphore de valeur maximum 1.

2. Ce qu'ils font
Comme indiqué ci-dessus, un verrou tournant est un verrou, et donc un mécanisme d'exclusion mutuelle (strictement 1 à 1). Il fonctionne en interrogeant et / ou en modifiant à plusieurs reprises un emplacement mémoire, généralement de manière atomique. Cela signifie que l'acquisition d'un verrou tournant est une opération "occupée" qui peut brûler les cycles du processeur pendant une longue période (peut-être pour toujours!) Alors qu'elle n'obtient effectivement "rien".
La principale motivation pour une telle approche est le fait qu'un changement de contexte a une surcharge équivalente à une rotation de quelques centaines (ou peut-être des milliers) de fois, donc si un verrou peut être acquis en brûlant quelques cycles de rotation, cela peut globalement très bien être plus efficace. En outre, pour les applications en temps réel, il peut ne pas être acceptable de bloquer et d'attendre que le planificateur y revienne à un moment lointain dans le futur.

Un sémaphore, en revanche, soit ne tourne pas du tout, soit ne tourne que pendant très peu de temps (comme une optimisation pour éviter la surcharge de l'appel système). Si un sémaphore ne peut pas être acquis, il se bloque, laissant le temps CPU à un autre thread prêt à fonctionner. Cela peut bien sûr signifier que quelques millisecondes s'écoulent avant que votre thread ne soit à nouveau planifié, mais si ce n'est pas un problème (généralement ce n'est pas le cas), cela peut être une approche très efficace et conservatrice du processeur.

3. Comment ils se comportent en présence de congestion
Il est courant de penser à tort que les verrous rotatifs ou les algorithmes sans verrouillage sont "généralement plus rapides", ou qu'ils ne sont utiles que pour des "tâches très courtes" (idéalement, aucun objet de synchronisation ne devrait être conservé plus longtemps que absolument nécessaire, jamais).
La seule différence importante est la façon dont les différentes approches se comportent en présence de congestion .

Un système bien conçu a normalement peu ou pas de congestion (cela signifie que tous les threads n'essaient pas d'acquérir le verrou exactement en même temps). Par exemple, on n'écrirait normalement pas de code qui acquiert un verrou, puis charge un demi-mégaoctet de données compressées par zip à partir du réseau, décode et analyse les données, et finalement modifie une référence partagée (ajouter des données à un conteneur, etc.) avant de relâcher le verrou. Au lieu de cela, on acquerrait le verrou uniquement dans le but d'accéder à la ressource partagée .
Puisque cela signifie qu'il y a beaucoup plus de travail à l'extérieur de la section critique qu'à l'intérieur de celle-ci, naturellement la probabilité qu'un fil soit à l'intérieur de la section critique est relativement faible, et ainsi peu de filets se disputent le verrou en même temps. Bien sûr, de temps en temps, deux threads essaieront d'acquérir le verrou en même temps (si cela ne pouvait pas arriver, vous n'auriez pas besoin d'un verrou!), Mais c'est plutôt l'exception que la règle dans un système «sain» .

Dans un tel cas, un verrou tournant surpasse largement un sémaphore car s'il n'y a pas de congestion de verrouillage, la surcharge d'acquisition du verrou tournant n'est que d'une douzaine de cycles par rapport à des centaines / milliers de cycles pour un changement de contexte ou 10 à 20 millions de cycles pour la perte le reste d'une tranche de temps.

D'un autre côté, étant donné une forte congestion, ou si le verrou est maintenu pendant de longues périodes (parfois vous ne pouvez tout simplement pas vous en empêcher!), Un spinlock brûlera des quantités insensées de cycles CPU pour ne rien faire.
Un sémaphore (ou mutex) est un bien meilleur choix dans ce cas, car il permet à un thread différent d'exécuter des tâches utiles pendant ce temps. Ou, si aucun autre thread n'a quelque chose d'utile à faire, cela permet au système d'exploitation de ralentir le processeur et de réduire la chaleur / économiser de l'énergie.

En outre, sur un système single-core, un spinlock sera tout à fait inefficace en présence de la congestion de verrouillage, comme un fil de filature va perdre son attente temps complet pour un changement d'état qui ne peut éventuellement se produire (pas jusqu'à ce que le fil de libération est prévue, ce qui ISN ne se produit pas pendant que le thread en attente est en cours d'exécution!). Par conséquent, compte tenu de toute quantité de conflit, l'acquisition du verrou prend environ 1 1/2 tranches de temps dans le meilleur des cas (en supposant que le thread de libération est le suivant en cours de planification), ce qui n'est pas un très bon comportement.

4. Comment ils sont implémentés
Un sémaphore va de nos jours typiquement s'enrouler sys_futexsous Linux (éventuellement avec un verrou tournant qui se termine après quelques tentatives).
Un verrou tournant est généralement implémenté à l'aide d'opérations atomiques, et sans utiliser quoi que ce soit fourni par le système d'exploitation. Dans le passé, cela signifiait utiliser soit les éléments intrinsèques du compilateur, soit des instructions d'assembleur non portables. Pendant ce temps, C ++ 11 et C11 ont des opérations atomiques dans le cadre du langage, donc, mis à part la difficulté générale d'écrire un code sans verrouillage prouvé correctement, il est maintenant possible d'implémenter un code sans verrouillage dans un tout portable et (presque) manière indolore.

très simplement, un sémaphore est un objet de synchronisation "cédant", un verrou tournant est un objet "busywait". (il y a un peu plus aux sémaphores en ce sens qu'ils synchronisent plusieurs threads, contrairement à un mutex ou un garde ou un moniteur ou une section critique qui protège une région de code d'un seul thread)

Vous utiliseriez un sémaphore dans plus de circonstances, mais utilisez un verrou tournant où vous allez verrouiller pendant très peu de temps - il y a un coût à verrouiller, surtout si vous verrouillez beaucoup. Dans de tels cas, il peut être plus efficace de verrouiller la rotation pendant un moment en attendant que la ressource protégée soit déverrouillée. Il y a évidemment un impact sur les performances si vous tournez trop longtemps.

généralement si vous tournez plus longtemps qu'un quantum de thread, vous devez utiliser un sémaphore.

Au-delà de ce que Yoav Aviram et gbjbaanb ont dit, l'autre point clé était que vous n'utiliseriez jamais de verrou tournant sur une machine à processeur unique, alors qu'un sémaphore aurait du sens sur une telle machine. De nos jours, vous avez souvent du mal à trouver une machine sans plusieurs cœurs, ni hyperthreading, ou équivalent, mais dans les circonstances où vous n'avez qu'un seul processeur, vous devez utiliser des sémaphores. (J'espère que la raison est évidente. Si le processeur unique est occupé à attendre que quelque chose d'autre libère le verrou tournant, mais qu'il fonctionne sur le seul processeur, il est peu probable que le verrou soit libéré jusqu'à ce que le processus ou le thread actuel soit préempté par l'O / S, ce qui peut prendre un certain temps et rien d'utile ne se produit jusqu'à ce que la préemption se produise.)

À partir des pilotes de périphériques Linux par Rubinni

Contrairement aux sémaphores, les verrous spin peuvent être utilisés dans du code qui ne peut pas dormir, comme les gestionnaires d'interruption

Je ne suis pas un expert du noyau mais voici quelques points:

Même une machine monoprocesseur peut utiliser des verrous rotatifs si la préemption du noyau est activée lors de la compilation du noyau. Si la préemption du noyau est désactivée, alors spin-lock se développe (peut-être) en une instruction void .

De plus, lorsque nous essayons de comparer Semaphore vs Spin-lock, je crois que le sémaphore fait référence à celui utilisé dans le noyau - PAS celui utilisé pour IPC (userland).

Fondamentalement, le verrouillage de rotation doit être utilisé si la section critique est petite (plus petite que la surcharge de sommeil / réveil) et si la section critique n'appelle rien qui puisse dormir! Un sémaphore doit être utilisé si la section critique est plus grande et peut dormir.

Raman Chalotra.

Spinlock fait référence à une implémentation du verrouillage inter-thread à l'aide d'instructions d'assemblage dépendant de la machine (telles que test-and-set). C'est ce qu'on appelle un verrou tournant parce que le thread attend simplement dans une boucle ("tourne") en vérifiant à plusieurs reprises jusqu'à ce que le verrou devienne disponible (attente occupée). Les spinlocks sont utilisés comme substitut aux mutex, qui sont une fonction fournie par les systèmes d'exploitation (et non par le processeur), car les spinlocks fonctionnent mieux s'ils sont verrouillés pendant une courte période.

Un sémaphore est une installation fournie par les systèmes d'exploitation pour IPC, c'est pourquoi son objectif principal est la communication inter-processus. Étant une installation fournie par le système d'exploitation, ses performances ne seront pas aussi bonnes que celles d'un verrou tournant pour le verrouillage inter-thead (bien que possible). Les sémaphores sont meilleurs pour verrouiller pendant de plus longues périodes.

Cela dit, la mise en œuvre de splinlocks dans l'assemblage est délicate et non portable.

Je voudrais ajouter mes observations, plus générales et peu spécifiques à Linux.

Selon l'architecture de la mémoire et les capacités du processeur, vous pourriez avoir besoin d'un verrou tournant pour implémenter un sémaphore sur un système multicœur ou multiprocesseur, car dans de tels systèmes, une condition de concurrence peut se produire lorsque deux ou plusieurs threads / processus le souhaitent pour acquérir un sémaphore.

Oui, si votre architecture mémoire propose le verrouillage d'une section mémoire par un cœur / processeur retardant tous les autres accès, et si vos processeurs proposent un test-and-set, vous pouvez implémenter un sémaphore sans spin-lock (mais très prudemment! ).

Cependant, comme des systèmes multicœurs simples / bon marché sont conçus (je travaille dans des systèmes embarqués), toutes les architectures de mémoire ne prennent pas en charge de telles fonctionnalités multi-cœur / multiprocesseur, uniquement des tests et des ensembles ou l'équivalent. Ensuite, une implémentation pourrait être la suivante:

• acquérir le verrou tournant (attente occupée)
• essayer d'acquérir le sémaphore
• relâchez le verrou tournant
• si le sémaphore n'a pas été acquis avec succès, suspendez le thread actuel jusqu'à ce que le sémaphore soit libéré; sinon continuez avec la section critique

La libération du sémaphore devrait être implémentée comme suit:

• acquérir le spin-lock
• libérer le sémaphore
• relâchez le verrou tournant

Oui, et pour les sémaphores binaires simples au niveau du système d'exploitation, il serait possible d'utiliser uniquement un verrou tournant en remplacement. Mais seulement si les sections de code à protéger sont vraiment très petites.

Comme indiqué précédemment, si et quand vous implémentez votre propre système d'exploitation, assurez-vous d'être prudent. Déboguer de telles erreurs est amusant (à mon avis, pas partagé par beaucoup), mais surtout très fastidieux et difficile.

Un «mutex» (ou «verrouillage d'exclusion mutuelle») est un signal que deux ou plusieurs processus asynchrones peuvent utiliser pour réserver une ressource partagée à des fins d'utilisation exclusive. Le premier processus qui obtient la propriété du «mutex» obtient également la propriété de la ressource partagée. Les autres processus doivent attendre que le premier processus libère la propriété du «mutex» avant de tenter de l'obtenir.

La primitive de verrouillage la plus courante dans le noyau est le verrou tournant. Le verrou tournant est un verrou à un seul support très simple. Si un processus tente d'acquérir un verrou tournant et qu'il n'est pas disponible, le processus continuera d'essayer (tourner) jusqu'à ce qu'il puisse acquérir le verrou. Cette simplicité crée un verrou petit et rapide.

Spinlock est utilisé si et seulement si vous êtes à peu près certain que le résultat attendu se produira très prochainement, avant l'expiration de la tranche d'exécution de votre thread.

Exemple: dans le module de pilote de périphérique, le pilote écrit "0" dans le registre matériel R0 et il doit maintenant attendre que ce registre R0 devienne 1. Le H / W lit le R0 et effectue un certain travail et écrit "1" dans R0. C'est généralement rapide (en micro secondes). Maintenant, la rotation est bien meilleure que de s'endormir et d'être interrompu par le H / W. Bien sûr, lors de l'essorage, la condition de défaillance H / W doit être prise en compte!

Il n'y a absolument aucune raison pour qu'une application utilisateur tourne. Cela n'a pas de sens. Vous allez tourner pour qu'un événement se produise et cet événement doit être complété par une autre application de niveau utilisateur, ce qui n'est jamais garanti dans un délai rapide. Donc, je ne tournerai pas du tout en mode utilisateur. Je préfère dormir () ou mutexlock () ou sémaphore lock () en mode utilisateur.

De quelle est la différence entre les verrous rotatifs et les sémaphores? par Maciej Piechotka :

Les deux gèrent une ressource limitée. Je vais d'abord décrire la différence entre le sémaphore binaire (mutex) et le verrouillage de rotation.

Les verrous rotatifs effectuent une attente occupée - c'est-à-dire qu'ils continuent à fonctionner en boucle:

while (try_acquire_resource ()); 
 ...  
Libération();

Il effectue un verrouillage / déverrouillage très léger, mais si le thread de verrouillage est préempté par un autre qui essaiera d'accéder à la même ressource, le second essaiera simplement d'acquérir la ressource jusqu'à ce qu'il en soit épuisé.
D'un autre côté, les mutex se comportent plus comme:

if (! try_lock ()) {
    add_to_waiting_queue ();
    attendre();
}
...
process * p = get_next_process_from_waiting_queue ();
p-> wakeUp ();

Par conséquent, si le thread essaie d'acquérir une ressource bloquée, il sera suspendu jusqu'à ce qu'il soit disponible pour cela. Le verrouillage / déverrouillage est beaucoup plus lourd mais l'attente est «libre» et «juste».

Le sémaphore est un verrou qui peut être utilisé plusieurs fois (depuis l'initialisation) - par exemple, 3 threads sont autorisés à contenir simultanément la ressource, mais pas plus. Il est utilisé par exemple en problème producteur / consommateur ou en général dans les files d'attente:

P (ressources_sem)
ressource = resources.pop ()
...
resources.push (ressources)
V (ressources_sem)

Différence entre sémaphore, mutex et spinlock?

Verrouillage sous Linux

Le verrouillage de rotation ne peut être maintenu que par un seul processus tandis que le sémaphore peut être maintenu par un ou plusieurs processus. Verrouillage rotatif attendez que le processus libère un verrou, puis acquiert un verrou. Le sémaphore est en train de dormir, c'est-à-dire qu'il attend et s'endort.