Co zapobiega wyścigowi na śluzie?

24

Rozumiem podstawy tego, czym są rasy danych i jak blokady / muteksy / semafory pomagają im zapobiegać. Ale co się stanie, jeśli masz „warunek wyścigu” na samym zamku? Na przykład dwa różne wątki, być może w tej samej aplikacji, ale działające na różnych procesorach, próbują uzyskać blokadę w tym samym czasie .

Co się wtedy stanie? Co zrobiono, aby temu zapobiec? Czy to niemożliwe, czy po prostu mało prawdopodobne? A może czeka Cię prawdziwy wyścig?

Gavin Howard
źródło
To pytanie zostało zadane wcześniej na SO: stackoverflow.com/questions/980521/…
Doc Brown
i powiązane pytanie tutaj na P.SE: programmers.stackexchange.com/questions/228827/…
maniak ratchet
Otrzymujesz blokadę, aby uzyskać blokadę;) (innymi słowy, jeśli twoja blokada ma warunek wyścigu, nie jest poprawnie wdrożona - blokada jest właściwie zdefiniowana jako konstrukcja, która implementuje wzajemne wykluczenie)
Tangrs
Pominąłeś ważny punkt w działaniu zamków. Są zbudowane w taki sposób, że wyścig nie jest możliwy na śluzie, w przeciwnym razie są całkowicie bezużyteczne.
Zane

Odpowiedzi:

36

Czy to niemożliwe, czy po prostu mało prawdopodobne?

Niemożliwy. Może być zaimplementowany na różne sposoby, np. Poprzez porównanie i zamianę, gdzie sprzęt gwarantuje sekwencyjne wykonanie. Może się to trochę skomplikować w obecności wielu rdzeni lub nawet wielu gniazd i wymaga skomplikowanego protokołu między rdzeniami, ale to wszystko jest załatwione.

maaartinus
źródło
3
Dzięki ... Boże ... jest obsługiwany sprzętowo ... (lub przynajmniej poziom niższy niż dotykamy.)
corsiKa
2
@gdhoward Nie mogę w to uwierzyć ... ta odpowiedź zajęła mi mniej niż 5 minut i jest to trzeci najwyższy głos spośród czterechset odpowiedzi (głównie SO). A także prawdopodobnie najkrótszy.
maaartinus
1
@maaartinus - Czasami jest krótki i słodki.
Bobson,
17

Przestudiuj pojęcie atomowych operacji „Testuj i ustaw”.

Zasadniczo operacji nie można podzielić - nie jest możliwe, aby dwie rzeczy zrobiły to dokładnie w tym samym czasie. Sprawdza wartość, ustawia ją, jeśli jest czysta, i zwraca wartość taką, jaka była podczas testu. W operacji blokowania wynikiem zawsze będzie „lock == TRUE” po testowaniu i ustawianiu, jedyną różnicą jest to, czy została ustawiona na początku, czy nie.

Na poziomie mikrokodu w procesorze jednordzeniowym jest to jedna niepodzielna instrukcja, którą można łatwo wdrożyć. W przypadku wielu i wielordzeniowych procesorów staje się to trudniejsze, ale jako programiści nie musimy się tym martwić, ponieważ jest przeznaczony do pracy naprawdę inteligentnych facetów, którzy wykonują krzem. Zasadniczo robią to samo - tworzą instrukcje atomowe, które są fantazyjną wersją testowania i ustawiania

mattnz
źródło
2
Zasadniczo, jeśli sprzęt na pewnym poziomie nie jest z natury sekwencyjny, będzie miał mechanizm, który pozwoli mu zerwać więzi, które mogłyby wystąpić w innym przypadku.
Bill Michell,
@BillMichell, powinienem o tym pomyśleć. Właściwie to zrobiłem; Po prostu nie wiedziałem, czy moje założenie było prawidłowe.
Gavin Howard
2

Wystarczy umieścić kod, aby przejść do sekcji krytycznej, jest on specjalnie zaprojektowany, aby warunki wyścigu nie naruszyły wzajemnego wykluczenia.

Przez większość czasu używane są pętle porównywania i ustawiania atomowego, które działają na poziomie sprzętowym

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);

W przypadku braku tego istnieją dobrze zbadane rozwiązania programowe umożliwiające wzajemne wykluczenie.

maniak zapadkowy
źródło
1

Nie jest możliwe, aby dwa (lub więcej) wątków uzyskało blokadę w tym samym czasie. Istnieje kilka rodzajów metod synchronizacji, na przykład:

Aktywne oczekiwanie - spin lock

Pseudo kod:

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

XCHG jest przykładem operacji atomowej (istniejącej w architekturze x86), która najpierw ustawia nową wartość dla zmiennej „lock”, a następnie zwraca starą wartość. Atom oznacza, że ​​nie można go przerwać - w powyższym przykładzie między ustawieniem nowej wartości a zwróceniem starej. Atomowy - deterministyczny wynik bez względu na wszystko.

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

Gdy blokada jest równa 0, inny wątek może wejść do sekcji krytycznej - podczas gdy pętla się kończy.

Zawieszenie wątku - na przykład liczenie semafora

Istnieje dwa operację atomową .Wait()a .Signal()i mamy całkowitą zmienna pozwala wywołać 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;

Teraz rozwiązanie problemu sekcji krytycznej jest naprawdę łatwe:

Pseudo kod:

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

Zwykle interfejs API wątku programistycznego powinien umożliwiać określenie maksymalnych współbieżnych wątków w sekcji krytycznej dla semaforów. Oczywiście istnieje więcej rodzajów synchronizacji w systemach wielowątkowych (mutex, monitory, binarny semafor itp.), Ale opierają się one na powyższych pomysłach. Można argumentować, że metody wykorzystujące zawieszanie wątków powinny być preferowane zamiast aktywnego oczekiwania (więc procesor nie jest marnowany) - nie zawsze jest to prawda. Gdy wątek jest zawieszany - ma miejsce kosztowna operacja zwana przełączaniem kontekstu. Jest to jednak rozsądne, gdy czas oczekiwania jest krótki (liczba wątków ~ liczba rdzeni).

fex
źródło