Si j'utilise des verrous, mon algorithme peut-il toujours être sans verrouillage?

Une définition courante du verrouillage sans verrou est qu'au moins un processus progresse. ¹

Si j'ai une structure de données simple telle qu'une file d'attente, protégée par un verrou, alors un processus peut toujours progresser, car un processus peut acquérir le verrou, faire ce qu'il veut et le libérer.

Répond-il donc à la définition de verrouillage sans verrou?

¹ Voir par exemple M. Herlihy, V. Luchangco et M. Moir. Synchronisation sans obstacle: files d'attente à double extrémité, par exemple. Dans Distributed Computing, 2003. "Il est sans verrou s'il garantit seulement que certains threads progressent toujours".

Ce n'est pas une définition de verrouillage sans verrou.

Si vous pouvez garantir des progrès, vous avez sans blocage , et si vous avez finalement terminé chaque demande, alors vous avez sans faim , mais pas sans verrouillage.

Je me demande si votre simple exemple le fournit de toute façon. Vous avez besoin de hiérarchies de verrous et ainsi de suite pour réellement garantir la progression lorsque plusieurs verrous sont impliqués.

J'ai étudié The Art of Multiprocessor Programming ¹ et leur texte manque de clarté, tout comme le livre auquel vous vous référez. Voici quelques citations de TAMPP:

Citation 1 (Définition de sans verrou)

Une méthode est sans verrouillage si elle garantit que, infiniment souvent, un appel de méthode se termine en un nombre fini d'étapes.

Citation 2 (Définition de non blocage)

un appel en attente d'une méthode totale n'est jamais nécessaire pour attendre qu'un autre appel en attente se termine.

Citation 3 (affirmer que le verrouillage est non bloquant)

Les conditions de progression non bloquante sans attente et sans verrouillage garantissent que le calcul dans son ensemble progresse, indépendamment de la façon dont le système planifie les threads.

Le problème est que la revendication de la citation 3 ne découle évidemment pas de la définition de la citation 1. Comme déjà mentionné, une file d'attente synchronisée semble satisfaire la citation 1: infiniment souvent, une méthode réussit à acquérir le verrou et à se terminer.

Notez spécifiquement la phrase assez vague de la citation 3: "indépendamment de la façon dont le système planifie les threads". Ceci n'est précédé d'aucune sorte de description formelle du «système d'ordonnancement des threads», il nous reste donc à reconstruire ses propriétés en fonction de nos idées préconçues sur ce que les définitions devraient signifier:

1. le système exécute toujours les instructions d' un thread;
2. il ne peut jamais exécuter les instructions d'un thread donné ;
3. tous les threads invoquent la méthode considérée.

Sur un tel système, une méthode de blocage ne peut pas être sans verrou: si le thread qui détient le verrou n'est plus jamais planifié pour exécution, il n'y aura pas d'autre thread qui puisse terminer son invocation de méthode en un nombre fini d'étapes, mais il y aura certains threads qui exécutent des étapes de la méthode. Pour un système plus réaliste, celui qui garantit de donner éventuellement du temps CPU à chaque thread, la définition doit inclure explicitement la propriété non bloquante:

Définition corrigée du verrouillage sans verrouillage

Une méthode est sans verrouillage si elle n'est pas bloquante et, en outre, garantit que infiniment souvent un appel de méthode se termine en un nombre fini d'étapes.

¹ Maurice Herlihy, Nir Shavit, The Art of Multiprocessor Programming, Elsevier 2008, pp. 58-60

La terminologie n'est pas toujours cohérente, mais je pense que l'important est de poser les questions suivantes sur un algorithme ou un système proposé:

1. Y a-t-il une séquence d'événements où les threads pourraient se coincer en attendant les uns les autres, même si tous les threads étaient autorisés tout le temps CPU qu'ils pouvaient utiliser [si c'est le cas, ce n'est pas sans blocage]
2. Si un thread était bloqué pendant une durée arbitraire, cela pourrait-il bloquer d'autres threads ou nuire au fonctionnement du système pendant une durée arbitraire [si c'est le cas, ce n'est pas non bloquant].
3. Existe-t-il une combinaison au moins théoriquement possible de la programmation des threads qui pourrait obliger tous les threads à répéter les mêmes opérations à plusieurs reprises tout en invalidant le travail des autres, sans que personne ne progresse [si c'est le cas, ce n'est pas sans verrou]
4. Si certains threads ont suffisamment de temps CPU par rapport à un autre, pourraient-ils forcer ce dernier à continuer à réessayer indéfiniment [si c'est le cas, ce n'est pas sans attente].

Une grande partie de la signification des algorithmes sans verrouillage n'est pas qu'ils sont plus rapides que les algorithmes sans verrouillage, mais plutôt le fait qu'ils ne sont pas enclins à mourir si un thread est égaré [notez qu'une telle garantie nécessite simplement que les algorithmes ne soient pas bloquants, mais tous les algorithmes sans verrouillage le sont]. Il est possible qu'un algorithme sans verrouillage utilise des verrous, mais uniquement si les tentatives d'acquisition de verrouillage incluent des délais d'expiration avec des algorithmes pour garantir qu'il sera toujours possible pour quelqu'un de progresser (par exemple, un algorithme pourrait utiliser une CompareExchangeboucle comme son principal) méthode d'arbitrage, mais utilisez des verrous pour arbitrer l'accès lorsque la contention semble élevée; si un verrou semble être maintenu trop longtemps, d'autres threads pourraient décider d'abandonner les efforts pour utiliser ce verrou et en créer un nouveau.CompareExchange, le fait que les clients abandonnent le verrou ne compromettrait pas la cohérence du système, bien que cela puisse signifier que le code qui détenait l'ancien verrou ne fera aucun travail tant qu'il n'abandonnera pas l'ancien verrou et ne se mettra pas en ligne pour le nouveau.

Vous devez regarder la "définition" que vous citez dans son contexte :

La manière traditionnelle de mettre en œuvre des structures de données partagées consiste à utiliser l'exclusion mutuelle (verrous) pour garantir que les opérations simultanées n'interfèrent pas entre elles. Le verrouillage présente un certain nombre d'inconvénients en ce qui concerne l'ingénierie logicielle, la tolérance aux pannes et l'évolutivité (voir [8]). En réponse, les chercheurs ont étudié une variété de techniques alternatives de synchronisation qui n'utilisent pas l'exclusion mutuelle . Une technique de synchronisation est sans attente si elle garantit que chaque thread continuera à progresser malgré le retard (ou même l'échec) arbitraire des autres threads. Il est sans verrou s'il garantit uniquement que certains threads progressent toujours.

Vous utilisez des verrous pour l'exclusion mutuelle, ce n'est donc pas une technique sans verrouillage dont ils parlent.

Si j'utilise des verrous, mon algorithme peut-il toujours être sans verrouillage?

C'est possible, mais cela dépend de l'algorithme.

Si j'ai une structure de données simple telle qu'une file d'attente, protégée par un verrou, alors un processus peut toujours progresser, car un processus peut acquérir le verrou, faire ce qu'il veut et le libérer.

Répond-il donc à la définition de verrouillage sans verrou?

Remarque en soi .

Si l' étape "faire ce qu'il veut" n'implique pas l'acquisition d'autres verrous, et qu'elle est garantie de se terminer dans un temps fini, alors cette partie particulière de votre algorithme sera sans blocage.

Cependant, si ces conditions préalables ne sont pas remplies, il y a au moins le risque de blocages ...

L'exemple que vous donnez n'est pas sans verrouillage pour la raison suivante.

La prise en charge d'un thread acquiert le verrou et le planificateur du système d'exploitation a suspendu le thread pendant une période solitaire infinie, puis tout le thread ne peut pas progresser car personne ne peut acquérir le verrou acquis par le thread suspendu.

De manière générale, les algorithmes qui utilisent des verrous ne sont pas sans verrouillage.

Notez que sans blocage et sans verrouillage sont deux concepts différents. sans interblocage signifie qu'il n'y a aucune possibilité d'impasse, mais il pourrait y avoir des livelocks qui pourraient empêcher l'ensemble du système de progresser. La liberté de verrouillage est plus forte que cela, car cela signifie que certains threads du système progressent toujours avec un nombre fini d'étapes.