Was ist-Test-and-Set verwendet?

Question

Nach dem Lesen des Test-and-Set Wikipedia-Eintrag , bin ich immer noch blieb die Frage: „Was für ein Test-and-Set verwendet werden würde?“

Ich weiß, dass Sie es verwenden können Mutex zu implementieren (wie in wikipedia beschrieben), aber was für andere Verwendungen hat es?

Answer 1

Sie verwenden es, wann immer Sie wollen Daten in den Speicher zu schreiben, nachdem einige Arbeit zu tun und sicherstellen, dass ein anderer Thread das Ziel nicht überschrieben hat, seit Sie begonnen. Viele lock / Mutex freie Algorithmen nehmen diese Form.

Answer 2

Ein gutes Beispiel ist "Zuwachs".

Sprich zwei Threads a = a + 1 auszuführen. Sprich a mit dem Wert 100 beginnt. Wenn beide Threads zur selben Zeit (Multi-Core) ausgeführt werden, würde laden beide a als 100, Inkrement 101 und speichern, die zurück in a. Falsch!

Mit Test-and-Set, Sie sagen, "Set a 101, aber nur, wenn sie zur Zeit den Wert 100 haben." In diesem Fall wird ein Thread, den Test bestehen, aber der andere wird scheitern. Im Fehlerfall kann der Faden die gesamte Anweisung, diesmal als Lade a 101 wiederholen. Erfolg.

Dies ist in der Regel schneller als einen Mutex, weil:

1. Die meiste Zeit ist es nicht eine Race-Bedingung, so dass die Aktualisierung geschieht ohne irgendeine Art von Mutex erwerben zu müssen.
2. Sogar während einer Kollision, wird ein Thread überhaupt nicht blockiert, und es ist schneller für die anderen Thread nur zu spinnen und versuchen Sie es erneut, als es sich für einige Mutex in Linie auszusetzen wäre.

Answer 3

Stellen Sie sich eine Bankanwendung geschrieben haben, und Ihre Anwendung hatte eine Anfrage zehn Pfund zurückzuziehen (ja, ich bin Englisch;)) aus dem Konto. So müssen Sie den aktuellen Kontostand in eine lokale Variable lesen, den Abzug abziehen und dann das Gleichgewicht schreiben zurück in den Speicher.

Was aber, wenn eine andere, geschieht gleichzeitig Anforderung zwischen Ihnen den Wert zu lesen und Sie es heraus zu schreiben? Es gibt die Möglichkeit, dass das Ergebnis dieser Anfrage wird vollständig durch die ersten überschrieben werden, und der Kontostand falsch sein wird.

Test-and-Set hilft uns, dieses Problem zu beheben, indem Sie prüfen, ob der Wert Ihrer Überschreibung ist das, was Sie denken, es sein sollte. In diesem Fall können Sie überprüfen, dass das Gleichgewicht der ursprüngliche Wert war, die Sie gelesen. Da es atomar ist, ist es nicht unterbrechbare so kann niemand den Teppich zwischen dem Lese unter Ihnen herausziehen und den Schreibvorgang.

Eine andere Möglichkeit, das gleiche Problem zu beheben, ist auf dem Speicherplatz, eine Sperre zu nehmen. Leider sind die Schlösser enorm schwierig richtig zu machen, schwer zu argumentieren über, haben Probleme Skalierbarkeit und schlecht angesichts der Ausfälle verhalten, so sind sie nicht ideal (aber auf jeden Fall praktisch) Lösung. Test-and-Set Ansätze bilden die Grundlage für einige Software Transactional Erinnerungen, die jeder Transaktion optimistischer erlauben gleichzeitig auszuführen, auf Kosten der sie alle wieder, wenn sie Konflikte rollen.

Answer 4

Im Grunde ist seine Verwendung genau für Mutexe, die enorme Bedeutung der Unteilbarkeit gegeben. Das ist es.

Test-and-Set ist ein Vorgang, der mit zwei anderen Anweisungen ausgeführt werden kann, nicht-atomaren und schneller (Unteilbarkeit trägt einen Hardware-Overhead, wenn auf Multi-Prozessor-Systemen), so die Regel würden Sie es aus anderen Gründen nicht verwendet werden.

Answer 5

Er wird verwendet, wenn Sie einen gemeinsamen Wert erhalten müssen, tun Sie etwas mit ihm, und ändern Sie den Wert, hat ein anderer Thread unter der Annahme nicht bereits verändert es.

Wie für praktische Anwendungen, das letzte Mal sah ich es war in Implementierungen von gleichzeitigen Warteschlangen (Queues, die Semaphore oder Mutexe, ohne durch mehrere Threads geschoben / geknallt werden kann).

Warum würden Sie TestAndSet eher als ein Mutex? Weil es erfordert in der Regel weniger Overhead als ein Mutex. Wo ein Mutex O Intervention erfordert, kann ein TestAndSet als eine einzige atomare Anweisung auf dem CPU implementiert werden. Wenn parallel Umgebungen mit 100 von Threads ausgeführt wird, kann ein einzelnes Mutex in einem kritischen Abschnitt von Code ernsthaften Engpässen führen.