Quand faut-il utiliser un spinlock au lieu d'un mutex?

294

Je pense que les deux font le même travail, comment décidez-vous lequel utiliser pour la synchronisation?

compiler-fan
la source
1
doublon possible de Spinlock Versus Semaphore!
Paul R
11
Mutex et Semaphore ne sont pas la même chose, donc je ne pense pas que ce soit un doublon. La réponse de l'article référencé l'indique correctement. Pour plus de détails, voir barrgroup.com/Embedded-Systems/How-To/RTOS-Mutex-Semaphore
nanoquack

Réponses:

729

La théorie

En théorie, lorsqu'un thread essaie de verrouiller un mutex et qu'il ne réussit pas, car le mutex est déjà verrouillé, il se met en veille, permettant immédiatement à un autre thread de s'exécuter. Il continuera à dormir jusqu'à ce qu'il soit réveillé, ce qui sera le cas une fois le mutex déverrouillé par le fil qui tenait le verrou auparavant. Lorsqu'un thread essaie de verrouiller un verrou tournant et qu'il n'y parvient pas, il réessayera continuellement de le verrouiller jusqu'à ce qu'il réussisse enfin; il ne permettra donc pas à un autre thread de prendre sa place (cependant, le système d'exploitation passera de force à un autre thread, une fois que le quantum d'exécution du CPU du thread actuel aura été dépassé, bien sûr).

Le problème

Le problème avec les mutex est que mettre les threads en veille et les réveiller à nouveau est à la fois des opérations assez coûteuses, ils auront besoin de beaucoup d'instructions CPU et prendront donc un certain temps. Si maintenant le mutex n'était verrouillé que pendant très peu de temps, le temps passé à mettre un fil en veille et à le réveiller à nouveau pourrait dépasser de loin le temps que le fil a réellement dormi et il pourrait même dépasser le temps de fil ont perdu en sondant constamment sur un spinlock. D'un autre côté, l'interrogation sur un spinlock perdra constamment du temps CPU et si le verrou est maintenu plus longtemps, cela gaspillera beaucoup plus de temps CPU et cela aurait été bien mieux si le thread dormait à la place.

La solution

L'utilisation de verrous tournants sur un système à cœur unique / à processeur unique n'a généralement aucun sens, car tant que l'interrogation des verrous tournants bloque le seul cœur de processeur disponible, aucun autre thread ne peut s'exécuter et comme aucun autre thread ne peut s'exécuter, le verrou ne fonctionne pas. être déverrouillé non plus. IOW, un spinlock ne perd que du temps CPU sur ces systèmes sans aucun avantage réel. Si le thread était mis en veille à la place, un autre thread aurait pu s'exécuter à la fois, déverrouillant éventuellement le verrou puis permettant au premier thread de poursuivre le traitement, une fois qu'il s'est réveillé.

Sur un système multicœur / multi-CPU, avec de nombreux verrous qui ne sont maintenus que très peu de temps, le temps perdu à mettre constamment les threads en veille et à les réveiller à nouveau peut diminuer sensiblement les performances d'exécution. Lorsque vous utilisez des verrous tournants à la place, les threads ont la possibilité de profiter de leur quantum d'exécution complet (toujours uniquement bloqués pendant une très courte période, mais poursuivent immédiatement leur travail), ce qui conduit à un débit de traitement beaucoup plus élevé.

La pratique

Étant donné que très souvent, les programmeurs ne peuvent pas savoir à l'avance si les mutex ou les verrous tournants seront meilleurs (par exemple, car le nombre de cœurs de processeur de l'architecture cible est inconnu), et les systèmes d'exploitation ne peuvent pas non plus savoir si un certain morceau de code a été optimisé pour un cœur unique ou environnements multi-coeurs, la plupart des systèmes ne font pas de distinction stricte entre les mutex et les verrous tournants. En fait, la plupart des systèmes d'exploitation modernes ont des mutex hybrides et des verrous tournants hybrides. Qu'est-ce que cela signifie réellement?

Un mutex hybride se comporte d'abord comme un spinlock sur un système multicœur. Si un thread ne peut pas verrouiller le mutex, il ne sera pas mis en veille immédiatement, car le mutex pourrait être déverrouillé très rapidement, donc le mutex se comportera d'abord exactement comme un verrou tournant. Ce n'est que si le verrouillage n'a toujours pas été obtenu après un certain temps (ou une nouvelle tentative ou tout autre facteur de mesure) que le fil est vraiment mis en veille. Si le même code s'exécute sur un système avec un seul cœur, le mutex ne se verrouille pas, bien que, comme indiqué ci-dessus, cela ne soit pas avantageux.

Un spinlock hybride se comporte comme un spinlock normal au début, mais pour éviter de perdre trop de temps CPU, il peut avoir une stratégie de secours. Il ne mettra généralement pas le thread en veille (car vous ne voulez pas que cela se produise lorsque vous utilisez un verrou tournant), mais il peut décider d'arrêter le thread (immédiatement ou après un certain temps) et autoriser l'exécution d'un autre thread , augmentant ainsi les chances que le verrou tournant soit déverrouillé (un commutateur de fil pur est généralement moins cher que celui qui implique de mettre un fil en veille et de le réveiller plus tard, mais pas de loin).

Résumé

En cas de doute, utilisez des mutex, ils sont généralement le meilleur choix et la plupart des systèmes modernes leur permettront de se verrouiller pendant très peu de temps, si cela semble bénéfique. L'utilisation de verrous tournants peut parfois améliorer les performances, mais seulement sous certaines conditions et le fait que vous en doutiez me dit plutôt que vous ne travaillez sur aucun projet actuellement où un verrou tournant pourrait être bénéfique. Vous pourriez envisager d'utiliser votre propre "objet verrou", qui peut soit utiliser un verrou tournant ou un mutex en interne (par exemple, ce comportement pourrait être configurable lors de la création d'un tel objet), utiliser initialement des mutex partout et si vous pensez que l'utilisation d'un verrou tournant quelque part pourrait vraiment aidez-le, essayez et comparez les résultats (par exemple en utilisant un profileur), mais assurez-vous de tester les deux cas,

Mise à jour: un avertissement pour iOS

En fait, ce n'est pas spécifique à iOS, mais iOS est la plate-forme où la plupart des développeurs peuvent être confrontés à ce problème: si votre système dispose d'un planificateur de threads, cela ne garantit pas qu'un thread, quelle que soit sa priorité, sera éventuellement exécuté, alors les verrous tournants peuvent conduire à des blocages permanents. Le planificateur iOS distingue différentes classes de threads et les threads d'une classe inférieure ne s'exécuteront que si aucun thread d'une classe supérieure ne souhaite également s'exécuter. Il n'y a pas de stratégie de sauvegarde pour cela, donc si vous avez en permanence des threads de classe élevée disponibles, les threads de classe inférieure n'obtiendront jamais de temps CPU et n'auront donc aucune chance d'effectuer un travail.

Le problème se présente comme suit: Votre code obtient un verrou tournant dans un thread de classe à faible priorité et pendant qu'il se trouve au milieu de ce verrou, le temps quantique a dépassé et le thread s'arrête de fonctionner. Le seul moyen de libérer à nouveau ce spinlock est que ce thread de classe faible prio obtienne à nouveau du temps CPU, mais cela n'est pas garanti. Vous pouvez avoir quelques threads de classe haute priorité qui veulent constamment s'exécuter et le planificateur de tâches les priorisera toujours. L'un d'eux peut traverser le verrou tournant et essayer de l'obtenir, ce qui n'est pas possible bien sûr, et le système le fera céder. Le problème est: Un thread qui a cédé est immédiatement disponible pour une nouvelle exécution! Ayant un prio plus élevé que le thread tenant le verrou, le thread tenant le verrou n'a aucune chance d'obtenir le temps d'exécution du processeur.

Pourquoi ce problème ne se produit-il pas avec les mutex? Lorsque le thread prio élevé ne peut pas obtenir le mutex, il ne cède pas, il peut tourner un peu mais sera finalement mis en veille. Un thread endormi n'est pas disponible pour s'exécuter tant qu'il n'est pas réveillé par un événement, par exemple un événement comme le mutex déverrouillé qu'il attendait. Apple est conscient de ce problème et est donc devenu obsolète OSSpinLock. Le nouveau verrou est appelé os_unfair_lock. Ce verrou évite la situation mentionnée ci-dessus car il connaît les différentes classes de priorité des threads. Si vous êtes sûr que l'utilisation des verrous tournants est une bonne idée dans votre projet iOS, utilisez-la. Reste loin deOSSpinLock! Et en aucun cas implémentez vos propres verrous tournants dans iOS! En cas de doute, utilisez un mutex! macOS n'est pas affecté par ce problème car il a un planificateur de threads différent qui ne permettra à aucun thread (même les threads à faible priorité) de fonctionner à sec sur le temps CPU, la même situation peut se produire là-bas et entraînera alors une très mauvaise performances, OSSpinLockest donc également obsolète sur macOS.

Mecki
la source
3
superbe explication ... J'ai un doute concernant le spinlock i, e puis-je utiliser un spinlock en ISR? si non pourquoi pas
haris
4
@Mecki Si je ne me trompe pas, je pense que vous avez suggéré dans votre réponse que le découpage temporel ne se produit que sur les systèmes à processeur unique. Ce n'est pas correct! Vous pouvez utiliser un verrou rotatif sur un système à processeur unique et il tournera jusqu'à l'expiration de son quantum de temps. Ensuite, un autre thread de même priorité peut prendre le relais (tout comme ce que vous avez décrit pour les systèmes multiprocesseurs).
fumoboy007
7
@ fumoboy007 "et il tournera jusqu'à ce que son quantum de temps expire" // Ce qui signifie que vous gaspillez du temps CPU / de la batterie pour absolument rien sans aucun avantage unique, ce qui est tout à fait idiot. Et non, je dit nulle part que le découpage de temps ne se produit que sur les systèmes de base unique, je l' ai dit sur les systèmes de base unique , il est seulement découpage en tranches de temps, alors qu'il ya REAL parallélisme des systèmes om multi - cœurs (et aussi découpage en tranches de temps, mais sans importance pour ce que je l' ai écrit dans mon réponse); vous avez également complètement raté le point sur ce qu'est un verrou tournant hybride et pourquoi il fonctionne bien sur les systèmes mono et multicœurs.
Mecki
11
@ fumoboy007 Le thread A détient le verrou et est interrompu. Le thread B s'exécute et veut le verrou, mais ne peut pas l'obtenir, il tourne donc. Sur un système multicœur, le thread A peut continuer à s'exécuter sur un autre noyau tandis que le thread B tourne toujours, libérez le verrou et le thread B peut continuer dans son quantum de temps actuel. Sur un système à cœur unique, il n'y a qu'un seul cœur que le thread A pourrait exécuter pour libérer le verrou et ce cœur est occupé par la rotation du fil B. Il n'y a donc aucun moyen que le verrou tournant puisse être libéré avant que le thread B n'ait dépassé son quantum de temps et donc tout le spin n'est qu'une perte de temps.
Mecki
2
Si vous voulez en savoir plus sur les verrous tournants et les mutex implémentés dans le noyau Linux, je vous recommande fortement de lire le chapitre 5 des excellents pilotes de périphériques Linux, troisième édition (LDD3) (mutex: page 109; spinlocks: page 116).
patryk.beza
7

Poursuivant la suggestion de Mecki, cet article pthread mutex vs pthread spinlock sur le blog d'Alexander Sandler, Alex sur Linux montre comment le spinlock& mutexespeut être implémenté pour tester le comportement en utilisant #ifdef.

Cependant, assurez-vous de prendre l'appel final en fonction de votre observation, sachant que l'exemple donné est un cas isolé, les exigences de votre projet, l'environnement peut être entièrement différent.

TheCottonSilk
la source
6

Veuillez également noter que dans certains environnements et conditions (tels que l'exécution sur des fenêtres au niveau de répartition> = DISPATCH LEVEL), vous ne pouvez pas utiliser mutex mais plutôt spinlock. Sous Unix - même chose.

Voici une question équivalente sur le site concurrent stackixchange unix: /unix/5107/why-are-spin-locks-good-choices-in-linux-kernel-design-instead-of-something- plus

Informations sur la répartition sur les systèmes Windows: http://download.microsoft.com/download/e/b/a/eba1050f-a31d-436b-9281-92cdfeae4b45/IRQL_thread.doc

Emplois Dan
la source
6

La réponse de Mecki le résume assez bien. Cependant, sur un seul processeur, l'utilisation d'un verrou tournant peut avoir un sens lorsque la tâche attend que le verrou soit fourni par une routine de service d'interruption. L'interruption transfèrerait le contrôle à l'ISR, qui préparerait la ressource à être utilisée par la tâche en attente. Il finirait par libérer le verrou avant de redonner le contrôle à la tâche interrompue. La tâche de rotation trouverait le verrou tournant disponible et continuerait.

AlanC
la source
2
Je ne suis pas sûr d'être entièrement d'accord avec cette réponse. Un processeur unique, si une tâche détient un verrou sur une ressource, l'ISR ne peut pas continuer en toute sécurité et ne peut pas attendre que la tâche déverrouille la ressource (car la tâche contenant la ressource a été interrompue). Dans de tels cas, la tâche doit simplement désactiver les interruptions pour appliquer l'exclusion entre elle et l'ISR. Bien sûr, cela devrait être fait pour des intervalles de temps très courts.
user1202136
3

Les mécanismes de synchronisation Spinlock et Mutex sont très courants aujourd'hui.

Pensons d'abord à Spinlock.

Fondamentalement, il s'agit d'une action d'attente occupée, ce qui signifie que nous devons attendre qu'un verrou spécifié soit libéré avant de pouvoir passer à l'action suivante. Conceptuellement très simple, lors de sa mise en œuvre ce n'est pas le cas. Par exemple: si le verrou n'a pas été libéré, le thread a été échangé et est passé en veille, devons-nous y faire face? Comment gérer les verrous de synchronisation lorsque deux threads demandent simultanément l'accès?

Généralement, l'idée la plus intuitive consiste à gérer la synchronisation via une variable pour protéger la section critique. Le concept de Mutex est similaire, mais ils sont toujours différents. Focus sur: l'utilisation du CPU. Spinlock consomme du temps CPU pour attendre de faire l'action, et donc, nous pouvons résumer la différence entre les deux:

Dans les environnements multicœurs homogènes, si le temps consacré à la section critique est petit, utilisez Spinlock, car nous pouvons réduire le temps de changement de contexte. (La comparaison monocœur n'est pas importante, car certains systèmes implémentent Spinlock au milieu du commutateur)

Sous Windows, l'utilisation de Spinlock mettra à niveau le thread vers DISPATCH_LEVEL, ce qui dans certains cas peut ne pas être autorisé, donc cette fois nous avons dû utiliser un Mutex (APC_LEVEL).

Marcus Thornton
la source
-6

L'utilisation de verrous tournants sur un système à cœur unique / à processeur unique n'a généralement aucun sens, car tant que l'interrogation des verrous tournants bloque le seul cœur de processeur disponible, aucun autre thread ne peut s'exécuter et comme aucun autre thread ne peut s'exécuter, le verrou ne fonctionne pas. être déverrouillé non plus. IOW, un spinlock ne perd que du temps CPU sur ces systèmes sans réel avantage

C'est faux. Il n'y a pas de gaspillage de cycles de processeur dans l'utilisation des verrous tournants sur les systèmes à processeur unique, car une fois qu'un processus prend un verrou tournant, la préemption est désactivée, donc en tant que tel, il ne peut y avoir personne d'autre qui tourne! C'est juste que son utilisation n'a aucun sens! Par conséquent, les verrous tournants sur les systèmes Uni sont remplacés par preempt_disable au moment de la compilation par le noyau!

Neelansh Mittal
la source
La citation est encore entièrement vraie. Si le résultat compilé du code source ne contient pas de verrous tournants, alors le guillemet n'est pas pertinent. En supposant que ce que vous avez dit soit vrai au sujet du remplacement des verrous tournants par le noyau au moment de la compilation, comment les verrous tournants sont-ils traités lorsqu'ils sont précompilés sur une autre machine qui peut ou non être unipocesseur, à moins que nous ne parlions strictement de verrous tournants uniquement dans le noyau lui-même?
Hydranix
"Une fois qu'un processus prend un verrou tournant, la préemption est désactivée". La préemption n'est pas désactivée lorsqu'un processus prend un tour. Si tel était le cas, un seul processus pourrait détruire toute la machine en entrant simplement dans un verrou tournant et sans jamais en sortir. Notez que si votre thread s'exécute dans l'espace du noyau (au lieu de l'espace utilisateur), la prise d'un verrou rotatif désactive effectivement la préemption, mais je ne pense pas que ce soit ce qui est discuté ici.
Konstantin Weitz
Au moment de la compilation par le noyau ?
Shien
@konstantin FYI spin lock ne peut être utilisé que dans l'espace noyau. Et lorsqu'un verrou tournant est pris, la préemption est désactivée sur le processeur local.
Neelansh Mittal
@hydranix Vous n'avez pas compris? Évidemment, vous ne pouvez pas compiler un module avec un noyau dans lequel CONFIG_SMP est activé et exécuter le même module sur un noyau dont CONFIG_SMP est désactivé.
Neelansh Mittal