Co zapobiega wyścigowi na śluzie?

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?

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.

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

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.

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