Spinlock contre Sémaphore
quelles sont les différences fondamentales entre un sémaphore et un spin-lock?
quand utiliserons-nous un sémaphore sur un spin-lock?
10 réponses
Spinlock et sémaphore diffèrent principalement en quatre points:
1. Ce qu'ils sont
Un spinlock est une implémentation possible d'une serrure, à savoir celle qui est implémentée par busy waiting ("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 spinlocks ne sont valables que au sein d'un même processus, les sémaphores peuvent également être utilisés pour synchroniser différents processus.
une serrure fonctionne pour l'exclusion mutuelle, c'est-à-dire un fil à la fois peut acquérir la serrure et procéder avec une" section critique " de code. Habituellement, cela signifie que le code modifie certaines données partagées par plusieurs threads.
Un sémaphore dispose d'un compteur et se permettra d'être acquis par un ou plusieurs threads , en fonction de la valeur que vous y publiez, et (dans certaines implémentations) en fonction de sa valeur maximale autorisée.
dans la mesure où on peut considérer une serrure comme un boîtier spécial d'un sémaphore avec une valeur maximale de 1.
2. Ce qu'ils font
Comme indiqué ci-dessus, une toupie est un mécanisme de verrouillage, et donc un mécanisme d'exclusion mutuelle (strictement 1 à 1). Il fonctionne en questionnant à plusieurs reprises et / ou modifier un emplacement mémoire, généralement de manière atomique. Cela signifie que l'acquisition d'un spinlock est une opération "occupée" qui peut brûler les cycles CPU pendant une longue période (Peut-être pour toujours! alors qu'il atteint efficacement "rien".
La principale incitation pour une telle approche est le fait qu'un commutateur de contexte a un overhead équivalent à tourner quelques centaines (ou peut-être mille) fois, donc si une serrure peut être acquise en brûlant quelques cycles de rotation, cela peut très bien dans l'ensemble être plus efficace. Aussi, pour des applications temps-réel, il peut ne pas être acceptable pour bloquer et d'attendre que le planificateur de revenir au loin dans l'avenir.
Un sémaphore, en revanche, ne tourne pas ou tourne pendant un temps très court (comme une optimisation pour éviter le syscall généraux). Si un sémaphore ne peut pas être acquis, il bloque, abandonnant le temps CPU à un fil différent qui est prêt à fonctionner. Cela peut évidemment dire que quelques millisecondes passez avant que votre thread soit programmé à nouveau, mais si ce n'est pas un problème (ce n'est généralement pas le cas) alors cela peut être une approche très efficace, CPU-conservatrice.
3. Comment ils se comportent en présence de congestion
C'est une idée fausse courante que les spinlocks 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 qu'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 d'encombrement (cela signifie que tous les fils ne tentent pas d'acquérir la serrure en même temps). Par exemple, on devrait normalement et non écrire le code qui acquiert une serrure, puis charge un demi-mégaoctet de données compressées zip à partir du réseau, décodes et analyse les données, et modifie finalement une référence partagée (ajoute des données à un conteneur, etc.) avant de relâcher le verrou. Au lieu de cela, on acquerrait l'écluse seulement dans le but d'accéder à la ressource partagée .
Puisque cela signifie qu'il y a beaucoup plus de travail en dehors de la section critique qu'à l'intérieur de celle-ci, naturellement la probabilité qu'un thread soit à l'intérieur de la section critique est relativement faible, et donc peu de threads sont en concurrence pour le verrou en même temps. Bien sûr, de temps en temps deux threads vont essayer d'acquérir la serrure en même temps (si ce ne pouvait pas arriver, vous n'auriez pas besoin d'une serrure!), mais il s'agit plutôt de l'exception que de la règle dans un système "sain".
dans un tel cas, un spinlock largement dépasse un sémaphore parce que s'il n'y a pas de congestion de la serrure, le plafond de l'acquisition du spinlock est une simple douzaine de cycles par rapport à des centaines / milliers de cycles pour un commutateur de contexte ou 10-20 millions de cycles pour perdre le reste d'une tranche de temps.
d'un autre côté, en raison de la forte congestion, ou si l'écluse est retenue pendant de longues périodes (parfois, vous ne pouvez pas s'en empêcher!), un spinlock brûlera des quantités insensées de cycles CPU pour ne rien obtenir.
Un sémaphore (ou mutex) est un meilleur choix dans ce cas, car il permet à un fil différent d'exécuter utile Les tâches pendant cette période. Ou, si aucun autre fil n'a quelque chose d'utile à faire, il permet au système d'exploitation d'étouffer le CPU et de réduire la chaleur / économiser l'énergie.
en outre, sur un système à un seul noyau, un spinlock sera tout à fait inefficace en présence de la congestion de la serrure, comme un filetage perdra son temps complet en attendant un changement d'état qui ne peut pas se produire (pas jusqu'à ce que le fil de libération est prévu, ce qui ne se produit pas pendant que le fil d'attente est en cours d'exécution!). Par conséquent, compte tenu de n'importe quelle quantité de de la réclamation, l'acquisition de la serrure prend environ 1 1/2 tranches de temps dans le meilleur cas (en supposant que le fil de libération est le suivant étant prévu), ce qui n'est pas très bon comportement.
4. Comment ils sont mis en œuvre
Un sémaphore va aujourd'hui généralement envelopper sys_futex sous Linux (éventuellement avec un spinlock qui sort après quelques tentatives).
Un spinlock est généralement mis en œuvre en utilisant des opérations atomiques, et sans utiliser quoi que ce soit fourni par le système d'exploitation. Dans le passé, cela signifiait utiliser soit des instructions de compilateur intrinsèques, soit des instructions d'assemblage non portatives. Pendant ce temps, C++11 et C11 ont des opérations atomiques comme partie du langage, donc en dehors de la difficulté générale d'écrire du code sans serrure, il est maintenant possible d'implémenter du code sans serrure dans un code entièrement portable. et (presque) sans douleur.
très simplement, un sémaphore est un objet de synchronisation "cédante", un spinlock est un "busywait". (il y a un peu plus aux sémaphores en ce sens qu'ils synchronisent plusieurs threads, contrairement à un mutex ou un guard ou un monitor 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 spinlock où vous allez verrouiller pour un temps très court - il ya un coût de verrouillage, surtout si vous verrouiller beaucoup. Dans dans de tels cas, il peut être plus efficace de faire tourner le bouchon un peu en attendant que la ressource protégée soit déverrouillée. Évidemment, il y a un gain de performance si vous tournez trop longtemps.
généralement, si vous tournez plus longtemps qu'un quantum de fil, 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 un spin-lock sur une machine MONOPROPU, alors qu'un sémaphore aurait du sens sur une telle machine. De nos jours, vous êtes souvent pressés de trouver une machine sans plusieurs cœurs, ou hyperthreading, ou l'équivalent, mais dans les circonstances où vous avez juste un CPU simple, vous devriez utiliser des sémaphores. (J'ai confiance en la raison en est évidente. Si le CPU simple est occupé à attendre quelque chose sinon pour libérer le spin-lock, mais il tourne sur le seul CPU, le lock est peu probable d'être libéré jusqu'à ce que le processus courant ou le thread soit préempté par le O/s, ce qui pourrait prendre un certain temps et rien d'utile arrive jusqu'à ce que la préemption se produit.)
de pilotes de périphériques Linux par Rubinni
Contrairement aux sémaphores, les spinlocks peuvent être utilisés en code qui ne peuvent pas dormir, tels que les manipulateurs d'interruption
Je ne suis pas un expert du noyau mais voici quelques points:
même une machine uniprocesseur peut utiliser des serrures de spin 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 (peut-être) s'étend à une déclaration nul .
aussi, quand nous essayons de comparer sémaphore vs Spin-lock, je crois que sémaphore se réfère à celui utilisé dans le noyau - pas celui utilisé pour IPC (userland).
en gros, on doit utiliser spin-lock si la section critique est petite (plus petite que le plafond 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 qu'elle peut dormir.
Raman Chalotra.
Spinlock fait référence à une mise en œuvre du verrouillage entre les fils utilisant des instructions d'assemblage dépendant de la machine (telles que test-and-set). Il est appelé spinlock parce que le thread attend simplement dans une boucle ("spins") vérifiant à plusieurs reprises jusqu'à ce que la serrure devienne disponible (busy wait). Les Spinlocks sont utilisés comme un substitut pour les Mutex, qui sont une installation fournie par les systèmes d'exploitation (pas le CPU), parce que les spinlocks fonctionnent mieux, si verrouillé pour une courte période de temps.
un sémaphore est une installation fournie par des systèmes d'exploitation pour la CIB, donc son but principal est la communication inter-processus. Étant une installation fournie par le système d'exploitation, sa performance ne sera pas aussi bonne que celle d'un spinlock pour le verrouillage inter-thead (bien que possible). Les sémaphores sont meilleurs pour le verrouillage sur de longues périodes.
cela dit - la mise en œuvre des éclats dans l'assemblage est délicate, et non portable.
je voudrais ajouter mes observations, plus générales et pas très spécifiques à Linux.
selon l'architecture de la mémoire et les capacités du processeur, vous pourriez avoir besoin d'un spin-lock afin de mettre en œuvre un sémaphore sur un multi-core ou un système multiprocesseur, parce que dans de tels systèmes une condition de course pourrait se produire lorsque deux ou plusieurs threads/process veulent acquérir un sémaphore.
Oui, si votre architecture mémoire offre le verrouillage d'un section mémoire par un noyau / processeur retardant tous les autres accès, et si vos processeurs offrent un test-and-set, vous pouvez implémenter un sémaphore sans spin-lock (mais très soigneusement!).
cependant, comme les systèmes multicentriques simples/bon marché sont conçus (je travaille dans des systèmes intégrés), toutes les architectures mémoire ne prennent pas en charge de telles fonctionnalités multicentriques/multiprocesseurs, uniquement des tests et des tests ou l'équivalent. Alors une mise en œuvre pourrait être comme suit:
- acquérir les spin-lock (occupé attente)
- essayer d'acquérir le sémaphore
- déverrouiller le spin-lock
- si le sémaphore n'a pas été acquis avec succès, suspendre le filetage courant jusqu'à ce que le sémaphore soit libéré; sinon, continuer avec la section critique
libérer le sémaphore devrait être mis en œuvre comme suit:
- acquérir la vrille
- libérer le sémaphore
- déverrouiller le spin-lock
Oui, et pour les sémaphores binaires simples au niveau de L'OS il serait possible d'utiliser seulement un spin-lock comme remplacement. Mais seulement si les sections de code à protéger sont vraiment très petites.
comme dit avant, si et quand vous mettez en œuvre votre propre OS, assurez-vous d'être prudent. Déboguer de telles erreurs est amusant( mon avis, pas partagé par beaucoup), mais souvent très fastidieux et difficile.
Un "mutex" (ou "verrou d'exclusion mutuelle") est un signal que deux ou plusieurs processus asynchrones peuvent utiliser pour réserver une ressource partagée pour une utilisation exclusive. Le premier processus qui obtient la propriété de la "mutex" obtient également la propriété de la ressource partagée. D'autres processus doivent attendre que le premier processus libère sa propriété du "mutex" avant de pouvoir tenter de l'obtenir.
la primitive de verrouillage la plus courante dans le noyau est le spinlock. Le spinlock est une serrure à un seul support très simple. Si un processus tente d'acquérir une serrure et qu'elle n'est pas disponible, le processus continuera d'essayer (de tourner) jusqu'à ce qu'il puisse acquérir la serrure. Cette simplicité crée une serrure petite et rapide.
Spinlock est utilisé si et seulement si vous êtes assez certain que votre résultat attendu arrivera très bientôt, avant que le temps d'exécution de la tranche de votre thread n'expire.
exemple: dans le module de pilote de périphérique, le pilote écrit" 0 " dans le Registre matériel R0 et maintenant il doit attendre que ce registre R0 devienne 1. Le H / W lit le R0 et fait un peu de travail et écrit "1" dans R0. C'est généralement rapide(micro-secondes). Maintenant, la filature est beaucoup mieux que d'aller dormir et interrompu par le H/W. bien sûr, pendant la rotation, 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. Il ne fait 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 au niveau de l'utilisateur qui n'est jamais garanti pour se produire dans un délai rapide. Donc, je ne vais pas tourner du tout en mode utilisateur. Je ferais mieux de dormir() ou mutexlock() ou sémaphore lock() en mode utilisateur.
à Partir de quelle est la différence entre le spin des serrures et des sémaphores? by Maciej Piechotka :
tous 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 spin.
Spin locks effectuer une attente active - c'est à dire qu'il continue de fonctionner en boucle:
while (try_acquire_resource ()); ... release();il est très léger verrouillage / déverrouillage mais si le thread de verrouillage sera préempté par un autre qui essaiera d'accéder à la même ressource, le second essaiera simplement d'acquitter la ressource jusqu'à ce qu'elle soit épuisée CPU quanta.
D'un autre côté mutex se comportent plus comme:if (!try_lock()) { add_to_waiting_queue (); wait(); } ... process *p = get_next_process_from_waiting_queue (); p->wakeUp ();donc si le thread essaie d'acquérir une ressource bloquée, il sera suspendu jusqu'à ce qu'il soit disponible pour lui. Verrouillage/déverrouillage est beaucoup plus lourd, mais l'attente est "libre" et "juste".
sémaphore est une serrure qui est autorisé à être utilisé multiple (connu de l'initialisation) nombre de fois - par exemple 3 threads sont autorisés à tenir simultanément la ressource, mais pas plus. Il est utilisé par exemple dans producteur/consommateur problème ou en général dans les files d'attente:
P(resources_sem) resource = resources.pop() ... resources.push(resources) V(resources_sem)