Pourquoi pthread_cond_wait a-t-il de faux réveils?

145

Pour citer la page de manuel:

Lors de l'utilisation de variables de condition, il existe toujours un prédicat booléen impliquant des variables partagées associées à chaque condition d'attente qui est vrai si le thread doit continuer. Des réveils parasites des fonctions pthread_cond_timedwait () ou pthread_cond_wait () peuvent se produire. Puisque le retour de pthread_cond_timedwait () ou pthread_cond_wait () n'implique rien sur la valeur de ce prédicat, le prédicat doit être réévalué lors d'un tel retour.

Donc, pthread_cond_waitpeut revenir même si vous ne l'avez pas signalé. À première vue du moins, cela semble assez atroce. Ce serait comme une fonction qui retournait aléatoirement la mauvaise valeur ou renvoyée aléatoirement avant d'atteindre réellement une instruction de retour correcte. Cela semble être un bug majeur. Mais le fait qu'ils aient choisi de documenter cela dans la page de manuel plutôt que de corriger cela semble indiquer qu'il y a une raison légitime pour laquelle pthread_cond_waitfinit par se réveiller de manière indue. Vraisemblablement, il y a quelque chose d'intrinsèque dans son fonctionnement qui fait que cela ne peut pas être aidé. La question est de savoir quoi.

Pourquoi ne pthread_cond_waitrevenir spuriously? Pourquoi ne peut-il pas garantir qu'il ne se réveillera que lorsqu'il aura été correctement signalé? Quelqu'un peut-il expliquer la raison de son comportement faux?

Jonathan M Davis
la source
5
J'imagine que cela a quelque chose à voir avec le retour chaque fois que le processus capte un signal. La plupart des * nix ne relancent pas un appel de blocage après qu'un signal l'ait interrompu; ils ne font que définir / renvoyer un code d'erreur indiquant qu'un signal s'est produit.
cHao
1
@cHao: notez cependant que parce que les variables de condition ont de toute façon d' autres raisons de faux réveils, la gestion d'un signal n'est pas une erreur pour pthread_cond_(timed)wait: "Si un signal est délivré ... le thread recommence à attendre la variable de condition comme si c'était pas interrompu, ou il doit retourner zéro en raison d'un faux réveil ". D'autres fonctions de blocage indiquent EINTRlorsqu'elles sont interrompues par un signal (par exemple read), ou doivent reprendre (par exemple pthread_mutex_lock). Donc, s'il n'y avait pas d'autres raisons pour un faux réveil, cela pthread_cond_waitaurait pu être défini comme l'un ou l'autre.
Steve Jessop
4
Un article connexe sur Wikipedia: Spurious wakeup
Palec
3
Utile Vladimir Prus: faux réveils .
iammilind
De nombreuses fonctions ne peuvent pas faire complètement leur travail (E / S interrompues) et les fonctions d'observation peuvent recevoir un non événement comme un changement dans un répertoire où le changement a été annulé ou rétabli. Quel est le problème?
curiousguy

Réponses:

77

L'explication suivante est donnée par David R. Butenhof dans "Programming with POSIX Threads" (p. 80):

Des réveils parasites peuvent sembler étranges, mais sur certains systèmes multiprocesseurs, rendre le réveil des conditions complètement prévisible peut ralentir considérablement toutes les opérations des variables de condition.

Dans la discussion comp.programming.threads suivante , il développe la réflexion derrière la conception:

Patrick Doyle a écrit: 
> Dans l'article, Tom Payne a écrit: 
>> Kaz Kylheku a écrit: 
>>: Il en est ainsi car les implémentations ne peuvent parfois pas éviter d'insérer 
>>: ces faux réveils; il pourrait être coûteux de les empêcher.

>> Mais pourquoi? Pourquoi est-ce si difficile? Par exemple, parlons-nous de
>> des situations où une attente expire juste au moment où un signal arrive? 

> Vous savez, je me demande si les concepteurs de pthreads ont utilisé une logique comme celle-ci: 
> les utilisateurs de variables de condition doivent de toute façon vérifier la condition à la sortie, 
> nous ne leur imposerons donc aucune charge supplémentaire si nous permettons 
> faux réveils; et puisqu'il est concevable qu'autoriser des
> les réveils pourraient accélérer la mise en œuvre, cela ne peut aider que si nous 
> leur permettre. 

> Ils n'avaient peut-être aucune implémentation particulière en tête. 

Vous n'êtes en fait pas loin du tout, sauf que vous ne l'avez pas poussé assez loin. 

L'intention était de forcer un code correct / robuste en exigeant des boucles de prédicat. C'était
conduit par le contingent académique prouvé correct parmi les "threads de base" dans 
le groupe de travail, même si je ne pense pas que quiconque soit vraiment en désaccord avec l'intention 
une fois qu'ils ont compris ce que cela signifiait. 

Nous avons suivi cette intention avec plusieurs niveaux de justification. Le premier était que
"religieusement" l'utilisation d'une boucle protège l'application contre ses propres imperfections 
pratiques de codage. La seconde était qu'il n'était pas difficile d'imaginer abstraitement
machines et code d'implémentation qui pourraient exploiter cette exigence pour améliorer 
la performance des opérations d'attente de condition moyenne en optimisant 
mécanismes de synchronisation. 
/ ------------------ [David.Buten ... @ compaq.com] ------------------ \ 
| Compaq Computer Corporation POSIX Thread Architect |
| Mon livre: http://www.awl.com/cseng/titles/0-201-63392-2/ |
\ ----- [http://home.earthlink.net/~anneart/family/dave.html] ----- / 

NPE
la source
22
fondamentalement, cela ne dit rien. Aucune explication n'est donnée ici si ce n'est la pensée initiale que «cela peut rendre les choses plus rapides» mais personne ne sait comment ou si cela le fait.
Bogdan Ionitza
107

Il y a au moins deux choses que pourrait signifier un `` faux réveil '':

  • Un thread bloqué dans pthread_cond_waitpeut revenir de l'appel même si aucun appel vers pthread_call_signalou pthread_cond_broadcastsur la condition ne s'est produit.
  • Un thread bloqué dans les pthread_cond_waitretours en raison d'un appel à pthread_cond_signalou pthread_cond_broadcast, cependant, après la réacquisition du mutex, le prédicat sous-jacent s'avère ne plus être vrai.

Mais ce dernier cas peut se produire même si l'implémentation de la variable de condition ne permet pas le premier cas. Considérez une file d'attente de consommateurs de producteurs et trois threads.

  • Le thread 1 vient de retirer un élément de la file d'attente et de libérer le mutex, et la file d'attente est maintenant vide. Le thread fait tout ce qu'il fait avec l'élément qu'il a acquis sur un processeur.
  • Le thread 2 tente de retirer un élément de la file d'attente, mais trouve que la file d'attente est vide lorsqu'elle est vérifiée sous le mutex, les appels pthread_cond_waitet les blocs dans l'appel en attente de signal / diffusion.
  • Le thread 3 obtient le mutex, insère un nouvel élément dans la file d'attente, notifie la variable de condition et libère le verrou.
  • En réponse à la notification du thread 3, le thread 2, qui attendait la condition, est planifié pour s'exécuter.
  • Cependant, avant que le thread 2 n'arrive à accéder au CPU et à saisir le verrou de file d'attente, le thread 1 termine sa tâche en cours et retourne dans la file d'attente pour plus de travail. Il obtient le verrou de file d'attente, vérifie le prédicat et constate qu'il y a du travail dans la file d'attente. Il procède à la suppression de l'élément que le thread 3 a inséré, libère le verrou et fait tout ce qu'il fait avec l'élément que le thread 3 a mis en file d'attente.
  • Thread 2 obtient maintenant sur un CPU et obtient le verrou, mais quand il vérifie le prédicat, il trouve que la file d'attente est vide. Le fil 1 `` a volé '' l'objet, donc le réveil semble être faux. Le thread 2 doit à nouveau attendre la condition.

Donc, comme vous devez déjà toujours vérifier le prédicat sous une boucle, cela ne fait aucune différence si les variables de condition sous-jacentes peuvent avoir d'autres types de réveils parasites.

acm
la source
23
Oui. Essentiellement, c'est ce qui se passe lorsqu'un événement est utilisé au lieu d'un mécanisme de synchronisation avec un décompte. Malheureusement, il semble que les sémaphores POSIX, (sous Linux en tout cas), sont également sujets à des réveils spurius. Je trouve juste un peu étrange qu'une défaillance de fonctionnalité fondamentale des primitives de synchronisation soit simplement acceptée comme `` normale '' et doive être contournée au niveau de l'utilisateur: (Vraisemblablement, les développeurs seraient les bras croisés si un appel système était documenté avec une section "Spurious segfault" ou, peut-être "Spurious connexion à la mauvaise URL" ou "Spurious ouverture du mauvais fichier".
Martin James
2
Le scénario le plus courant d'un "faux réveil" est probablement l'effet secondaire d'un appel à pthread_cond_broadcast (). Disons que vous avez un pool de 5 threads, deux se réveillent à la diffusion et font le travail. Les trois autres se réveillent et découvrent que le travail est terminé. Les systèmes multiprocesseurs peuvent également entraîner un signal conditionnel qui réveille plusieurs threads par accident. Le code vérifie simplement à nouveau le prédicat, voit un état invalide et se rendort. Dans les deux cas, la vérification du prédicat résout le problème. IMO, en général, les utilisateurs ne doivent pas utiliser de mutex et de conditionnels POSIX bruts.
CubicleSoft
1
@MartinJames - Que diriez-vous du classique «faux» EINTR? Je conviendrai que tester constamment EINTR dans une boucle est un peu ennuyeux et rend le code plutôt laid, mais les développeurs le font quand même pour éviter les ruptures aléatoires.
CubicleSoft
2
@Yola Non, ce n'est pas possible, car vous êtes censé verrouiller un mutex autour du pthread_cond_signal/broadcastet vous ne pourrez pas le faire tant que le mutex ne sera pas déverrouillé en appelant pthread_cond_wait.
a3f
1
L'exemple de cette réponse est très réaliste et je suis d'accord que la vérification des prédicats est une bonne idée. Cependant, ne pourrait-il pas être résolu de manière aussi saine en prenant l'étape problématique "le thread 1 termine sa tâche actuelle et retourne dans la file d'attente pour plus de travail" et en le remplaçant par "le thread 1 termine sa tâche actuelle et recommence à attendre la variable de condition "? Cela éliminerait le mode d'échec décrit dans la réponse, et je suis presque sûr que cela rendrait le code correct, en l'absence de faux réveils . Existe-t-il une mise en œuvre réelle qui produit des réveils parasites dans la pratique?
Quuxplusone
7

La section "Réveils multiples par signal de condition" dans pthread_cond_signal a un exemple d'implémentation de pthread_cond_wait et pthread_cond_signal qui implique des réveils parasites.

Jingguo Yao
la source
2
Je pense que cette réponse est fausse, dans la mesure où elle disparaît. L'exemple d'implémentation sur cette page a une implémentation de «notifier un» qui équivaut à «notifier tout»; mais il ne semble pas générer de réveils réellement faux . La seule façon pour un thread de se réveiller est par un autre thread invoquant "notifier tout", ou par un autre thread invoquant la-chose-étiquetée- "notifier un" -qui-est-vraiment- "notifier tout".
Quuxplusone
5

Bien que je ne pense pas que cela ait été envisagé au moment de la conception, voici une raison technique réelle: en combinaison avec l'annulation de thread, il existe des conditions dans lesquelles prendre l'option de se réveiller "faussement" peut être absolument nécessaire, du moins à moins que vous sont disposés à imposer des contraintes très très fortes sur les types de stratégies de mise en œuvre possibles.

Le problème clé est que, si un thread agit sur l'annulation alors qu'il est bloqué pthread_cond_wait, les effets secondaires doivent être comme s'il ne consommait aucun signal sur la variable de condition. Cependant, il est difficile (et très contraignant) de s'assurer que vous n'avez pas déjà consommé un signal lorsque vous commencez à agir sur l'annulation, et à ce stade, il peut être impossible de «re-poster» le signal dans la variable de condition, car vous pouvez être dans une situation où l'appelant de pthread_cond_signalest déjà justifié d'avoir détruit le condvar et libéré la mémoire dans laquelle il résidait.

La tolérance pour un faux réveil vous permet de sortir facilement. Au lieu de continuer à agir sur l'annulation lorsqu'il arrive alors qu'il est bloqué sur une variable de condition, si vous avez peut-être déjà consommé un signal (ou si vous voulez être paresseux, quoi qu'il arrive), vous pouvez déclarer qu'un faux réveil s'est produit à la place, et revenez avec succès. Cela n'interfère pas du tout avec l'opération d'annulation, car un appelant correct agira simplement sur l'annulation en attente la prochaine fois qu'il bouclera et appellera à pthread_cond_waitnouveau.

R .. GitHub STOP AIDING ICE
la source