Was verhindert eine Rennbedingung an einem Schloss?

24

Ich verstehe die Grundlagen dessen, was Datenrassen sind und wie Sperren / Mutexe / Semaphoren helfen, sie zu verhindern. Aber was passiert, wenn Sie eine "Race Condition" für das Schloss selbst haben? Beispielsweise versuchen zwei verschiedene Threads, die möglicherweise in derselben Anwendung, jedoch auf unterschiedlichen Prozessoren ausgeführt werden, genau zur gleichen Zeit eine Sperre zu erlangen .

Was passiert dann? Was wird getan, um das zu verhindern? Ist es unmöglich oder einfach unwahrscheinlich? Oder ist es eine echte Rennbedingung, die darauf wartet, passiert zu werden?

Gavin Howard
quelle
Diese Frage wurde zuvor auf SO gestellt: stackoverflow.com/questions/980521/…
Doc Brown
und eine verwandte Frage hier auf P.SE: programmers.stackexchange.com/questions/228827/…
Ratschenfreak
Sie erwerben eine Sperre, um die Sperre zu erwerben;) (mit anderen Worten, wenn Ihre Sperre eine Racebedingung aufweist, ist sie nicht korrekt implementiert - eine Sperre ist so ziemlich als Konstrukt definiert, das den gegenseitigen Ausschluss implementiert.)
Tangrs
Sie haben einen wichtigen Punkt in der Funktionsweise von Schlössern übersehen . Sie sind so konstruiert, dass es nicht möglich ist, ein Rennen auf einem Schloss zu veranstalten, sonst sind sie völlig unbrauchbar.
Zane

Antworten:

36

Ist es unmöglich oder einfach unwahrscheinlich?

Unmöglich. Es kann auf verschiedene Arten implementiert werden, z. B. über Compare-and-Swap, wobei die Hardware die sequentielle Ausführung garantiert. Bei Vorhandensein mehrerer Kerne oder sogar mehrerer Sockel kann es etwas kompliziert werden, und es ist ein kompliziertes Protokoll zwischen den Kernen erforderlich , für das jedoch alles gesorgt ist.

maaartinus
quelle
3
Gott sei Dank ... es wird in Hardware gehandhabt ... (oder zumindest ein Level niedriger als wir berühren.)
Corsika
2
@gdhoward Ich kann es nicht glauben ... diese Antwort hat weniger als 5 Minuten gedauert und es ist die dritthöchste von meinen vierhundert Antworten (hauptsächlich SO). Und wahrscheinlich auch die kürzeste.
Maaartinus
1
@maaartinus - Kurz und bündig macht das manchmal.
Bobson
17

Studieren Sie das Konzept atomarer "Test and Set" -Operationen.

Grundsätzlich kann die Operation nicht aufgeteilt werden - es ist nicht möglich, dass zwei Dinge genau zur gleichen Zeit ausgeführt werden. Es prüft einen Wert, setzt ihn, wenn er klar ist, und gibt den Wert wie beim Test zurück. Bei einer Sperroperation lautet das Ergebnis nach einem Test und Setzen immer "lock == TRUE". Der einzige Unterschied besteht darin, ob es beim Start gesetzt wurde oder nicht.

Auf Mikrocode-Ebene in einem Single-Core-Prozessor ist dies eine unteilbare Anweisung und einfach zu implementieren. Mit Mehrkern- und Mehrkernprozessoren wird es schwieriger, aber als Programmierer brauchen wir uns keine Sorgen zu machen, da es für die wirklich intelligenten Leute entwickelt wurde, die das Silizium herstellen. Im Wesentlichen machen sie dasselbe - sie machen eine atomare Anweisung, die eine ausgefallene Version von Test & Set ist

mattnz
quelle
2
Grundsätzlich verfügt die Hardware, wenn sie auf einer bestimmten Ebene nicht von sich aus sequenziell ist, über einen Mechanismus, der es ihr ermöglicht, Verbindungen zu unterbrechen, die andernfalls auftreten könnten.
Bill Michell
@ BillMichell, daran hätte ich denken sollen. Eigentlich habe ich getan; Ich wusste nur nicht, ob meine Annahme richtig war.
Gavin Howard
2

Geben Sie einfach den Code ein, um in den kritischen Bereich zu gelangen. Er wurde speziell entwickelt, damit eine Rennbedingung den gegenseitigen Ausschluss nicht verletzt.

Die meiste Zeit werden atomare Vergleichs- und Set-Schleifen verwendet, die auf Hardwareebene ausgeführt werden

while(!CompareAndSet(&lock, false, true));//busy loop won't continue until THIS thread has set the lock to true
//critical section
CompareAndSet(&lock, true, false);

In Ermangelung dessen gibt es gut untersuchte Softwarelösungen , die den gegenseitigen Ausschluss ermöglichen.

Ratschenfreak
quelle
1

Es ist nicht möglich, dass zwei (oder mehr) Threads gleichzeitig eine Sperre erhalten. Es gibt zum Beispiel einige Arten von Synchronisationsmethoden:

Aktives Warten - Drehsperre

Pseudocode:

1. while ( xchg(lock, 1) == 1); - entry protocole

XCHG ist ein Beispiel für eine atomare Operation (in der x86-Architektur vorhanden), bei der zuerst ein neuer Wert für eine "Sperr" -Variable festgelegt und dann ein alter Wert zurückgegeben wird. Atomic bedeutet, dass es nicht unterbrochen werden kann - im obigen Beispiel zwischen dem Setzen eines neuen Werts und dem Zurückgeben eines alten. Atomdeterministisches Ergebnis, egal was passiert.

2. Your code
3. lock = 0; - exit protocol

Wenn lock gleich 0 ist, kann ein anderer Thread in den kritischen Bereich eintreten - während die Schleife endet.

Thread-Suspending - zum Beispiel Zählen von Semaphoren

Es gibt zwei atomare Operationen .Wait()und .Signal()wir haben eine Integer-Variable, die wir aufrufen können int currentValue.

Wait():
if (currentValue > 0) currentValue -= 1;
else suspend current thread;

Signal():
If there exists thread suspended by semaphore wake up one of them
Else currentValue += 1;

Das Lösen von Problemen mit kritischen Abschnitten ist jetzt ganz einfach:

Pseudocode:

mySemaphore.Wait();
do some operations - critical section
mySemaphore.Signal();

Normalerweise sollte Ihre Programmierthread-API Ihnen die Möglichkeit geben, maximal gleichzeitige Threads im semaphorenkritischen Abschnitt anzugeben. Offensichtlich gibt es in Multithread-Systemen (Mutex, Monitore, Binärsemaphore usw.) mehr Arten der Synchronisation, aber sie basieren auf den obigen Vorstellungen. Man könnte argumentieren, dass Methoden, die Thread-Suspending verwenden, dem aktiven Warten vorgezogen werden sollten (damit CPU nicht verschwendet wird) - es ist nicht immer die Wahrheit. Wenn der Thread angehalten wird, findet ein teurer Vorgang statt, der als Kontextwechsel bezeichnet wird. Es ist jedoch sinnvoll, wenn die Wartezeit kurz ist (Anzahl der Threads ~ Anzahl der Kerne).

fex
quelle