À quoi sert Test-and-Set?

Question

Après avoir lu la entrée Wikipedia test-and-set, je suis toujours il reste la question "À quoi servirait un Test-and-Set?"

Je réalise que vous pouvez l'utiliser pour implémenter Mutex (comme décrit dans wikipedia), mais quelles autres utilisations a-t-il?

Answer 1

Vous l'utilisez chaque fois que vous souhaitez écrire des données dans la mémoire après un travail et vous assurer qu'un autre thread n'a pas écrasé la destination depuis le début. De nombreux algorithmes de verrouillage / suppression de mutex prennent ce formulaire.

Answer 2

Un bon exemple est "l'incrément".

Disons que deux threads exécutent a = a + 1 . Disons que a commence par la valeur 100 . Si les deux threads s'exécutent en même temps (multi-core), ils chargeront un en tant que 100 , incrémenteront vers 101 et stockeront celui-ci. retournez dans a . Faux!

Avec test-and-set, vous dites que "définir a " sur 101 , mais uniquement s'il a la valeur 100 . " Dans ce cas, un thread passera ce test mais l'autre échouera. En cas d'échec, le thread peut réessayer l'intégralité de l'instruction, en chargeant a sous 101 . Succès.

Cela est généralement plus rapide que d'utiliser un mutex car:

1. La plupart du temps, il n'y a pas de condition de concurrence critique. La mise à jour s'effectue donc sans qu'il soit nécessaire d'acquérir une sorte de mutex.
2. Même en cas de collision, un thread n'est pas bloqué du tout et il est plus rapide pour l'autre thread de tourner et de réessayer que de se suspendre lui-même pour un mutex.

Answer 3

Imaginez que vous écriviez une application bancaire et que votre application demande de retirer dix livres (oui, je suis anglais;)) de votre compte. Vous devez donc lire le solde du compte courant dans une variable locale, soustraire le retrait, puis réécrire le solde en mémoire.

Cependant, que se passe-t-il si une autre demande simultanée se produit entre la lecture de la valeur et son écriture? Il est possible que le résultat de cette demande soit complètement écrasé par le premier et que le solde du compte soit incorrect.

Test-and-set nous aide à résoudre ce problème en vérifiant que la valeur que votre écrasement correspond à ce que vous pensez qu'elle devrait être. Dans ce cas, vous pouvez vérifier que la balance correspond à la valeur d'origine que vous avez lue. Puisque c'est atomique, c'est non-interruptible afin que personne ne puisse tirer le tapis de dessous entre la lecture et l'écriture.

Un autre moyen de résoudre le même problème consiste à verrouiller l’emplacement de la mémoire. Malheureusement, les verrous sont extrêmement difficiles à corriger, difficiles à raisonner, ont des problèmes d’évolutivité et se comportent mal en cas d’échec; ils ne constituent donc pas une solution idéale (mais bien pratique). Les approches test-and-set constituent la base de certaines mémoires transactionnelles logicielles, qui permettent, de manière optimiste, l’exécution simultanée de chaque transaction, au prix de leur annulation en cas de conflit.

Answer 4

Fondamentalement, son utilisation s’applique exactement aux mutex, étant donné l’importance considérable de l’atomicité. C'est ça.

Test-and-set est une opération qui peut être exécutée avec deux autres instructions, non atomique et plus rapide (atomicity entraîne une surcharge matérielle sur les systèmes multiprocesseurs). Vous ne l'utiliserez donc généralement pas pour d'autres raisons.

Answer 5

Il est utilisé lorsque vous avez besoin d'obtenir une valeur partagée, de faire quelque chose avec cette valeur et de la modifier, en supposant qu'un autre thread ne l'ait pas déjà modifiée.

En ce qui concerne les utilisations pratiques, la dernière fois que j’ai vu cela, c’était dans l’implémentation de files d’attente simultanées (files pouvant être poussées / sautées par plusieurs threads sans nécessiter de sémaphores ou de mutex).

Pourquoi voudriez-vous utiliser TestAndSet plutôt qu'un mutex? Parce qu'il nécessite généralement moins de frais généraux qu'un mutex. Lorsqu'un mutex nécessite une intervention du système d'exploitation, un TestAndSet peut être implémenté en tant qu'instruction atomique unique sur la CPU. Lorsque vous travaillez dans des environnements parallèles avec des centaines de threads, un seul mutex dans une section critique de code peut entraîner de sérieux goulots d'étranglement.