Propriété d'un algorithme garantissant que, même si un thread s'arrête en cours de route, au moins un des autres threads peut progresser. Réalisé avec des instructions atomiques comme CAS.
Nom japonais: ロックフリー
« Sans verrou (lock-free) » apparaît dans 4 questions d'entraînement réparties sur 1 thèmes, dont Multicœur et synchronisation.
Domaine: Multicœur et synchronisation
Réponse : B. Lorsque la valeur passe de A à B puis revient à A, CAS ne remarque pas le changement et réussit
Si le pointeur de tête d’une liste chaînée vaut A, il peut arriver que, pendant qu’un thread lit A et prépare son CAS, un autre thread retire A, effectue une opération sur B, puis réinsère un nœud à la même adresse A. Le CAS réussit puisque la valeur est toujours A, mais le contenu de la liste a déjà changé et la structure est corrompue. On l’évite en associant au pointeur un compteur de mises à jour comparé en même temps, ou en utilisant LR/SC.
Réponse : A. Même si un thread s’arrête en cours de route, au moins un des autres threads peut progresser
Avec un verrou, si le thread détenteur est arrêté par une interruption ou une faible priorité, tous les autres attendent. Un algorithme sans verrou met à jour directement les données partagées, par exemple par CAS, de sorte qu’un thread n’échoue et ne recommence que lorsqu’un autre a réussi. Globalement, un thread progresse donc toujours. Cependant, ces algorithmes sont difficiles à écrire correctement et exigent de prendre garde notamment au problème ABA.
Un algorithme sans verrou met à jour directement les données partagées, par exemple par CAS, de sorte qu’un thread n’échoue et ne recommence que lorsqu’un autre a réussi.
Quelle propriété caractérise un algorithme sans verrou (loc…Parmi elles figurent CAS (compare-and-swap), fetch-and-add, ainsi que LR/SC et les instructions AMO de RISC-V ; elles servent de base à la construction des verrous et des structures de données sans verrou.
Quelle description d’une instruction atomique (instruction …Avec une boucle qui, en cas d’échec, relit, recalcule et retente le CAS, on met à jour une valeur partagée en toute sécurité sans verrou.
Quel est le fonctionnement de l’instruction atomique CAS (c…Problème ABA LR/SC Instruction atomique Compare-and-swap Interruption Acquisition-libération (acquire-release) Barrière mémoire Cohérence séquentielle Course aux données (data race) Espionnage de bus (snooping)