Wzajemne wykluczenie - Mutual exclusion

Usunięcie dwóch węzłów i jednocześnie powoduje, że węzeł nie zostanie usunięty.

i

i+1

i+1

W informatyce , wzajemne wykluczanie jest właściwością kontroli współbieżności , który jest ustanowiony w celu zapobiegania sytuacjom wyścigu . Jest to wymóg, aby jeden wątek wykonania nigdy nie wchodził do sekcji krytycznej, podczas gdy współbieżny wątek wykonania już uzyskuje dostęp do sekcji krytycznej, co odnosi się do przedziału czasu, w którym wątek wykonania uzyskuje dostęp do współdzielonego zasobu , takiego jak [obiekty danych współdzielonych , zasoby współdzielone, pamięć współdzielona].

Zasób udostępniony to obiekt danych, który co najmniej dwa współbieżne wątki próbują zmodyfikować (gdzie dozwolone są dwie współbieżne operacje odczytu, ale nie są dozwolone dwie współbieżne operacje zapisu lub jedna operacja odczytu i jeden zapis, ponieważ prowadzi to do niespójności danych). Algorytm wzajemnego wykluczania zapewnia, że jeśli proces wykonuje już operację zapisu na obiekcie danych [sekcja krytyczna] żaden inny proces/wątek nie może uzyskać dostępu/modyfikować tego samego obiektu, dopóki pierwszy proces nie zakończy zapisu na obiekcie danych [sekcja krytyczna] i udostępnił obiekt innym procesom do odczytu i zapisu.

Wymóg wzajemnego wykluczania został po raz pierwszy zidentyfikowany i rozwiązany przez Edsgera W. Dijkstrę w jego przełomowym artykule z 1965 r. „Rozwiązanie problemu w sterowaniu programowaniem współbieżnym”, który jest uznawany za pierwszy temat w badaniu algorytmów współbieżnych .

Prosty przykład tego, dlaczego wzajemne wykluczanie jest ważne w praktyce, można zwizualizować za pomocą pojedynczo połączonej listy czterech pozycji, z których należy usunąć drugi i trzeci. Usunięcie węzła, który znajduje się między 2 innymi węzłami, odbywa się poprzez zmianę następnego wskaźnika poprzedniego węzła, aby wskazywał na następny węzeł (innymi słowy, jeśli węzeł jest usuwany, następny wskaźnik węzła jest zmieniany na wskazywanie node , usuwając w ten sposób z połączonej listy wszelkie odniesienia do node ). Gdy taka połączona lista jest współdzielona przez wiele wątków wykonania, dwa wątki wykonania mogą próbować usunąć dwa różne węzły jednocześnie, jeden wątek wykonania zmienia następny wskaźnik węzła na punkt do węzła , podczas gdy inny wątek wykonania zmienia następny wskaźnik węzła do wskazania węzła . Chociaż obie operacje usuwania zakończyły się pomyślnie, pożądany stan połączonej listy nie został osiągnięty: węzeł pozostaje na liście, ponieważ następny wskaźnik węzła wskazuje na węzeł . $i$ $i-1$ $i+1$ $i$ $i-1$ $i+1$ $i$ $i+2$ $i+1$ $i-1$ $i+1$

Ten problem (nazywany sytuacją wyścigu ) można uniknąć, stosując wymóg wzajemnego wykluczania, aby zapewnić, że nie mogą wystąpić jednoczesne aktualizacje tej samej części listy.

Termin wzajemne wykluczanie jest również używany w odniesieniu do jednoczesnego zapisywania adresu pamięci przez jeden wątek, podczas gdy wspomniany adres pamięci jest manipulowany lub odczytywany przez jeden lub więcej innych wątków.

Opis problemu

Problem, który rozwiązuje wzajemne wykluczanie, to problem współdzielenia zasobów: w jaki sposób system oprogramowania może kontrolować dostęp wielu procesów do współdzielonego zasobu, gdy każdy proces wymaga wyłącznej kontroli nad tym zasobem podczas wykonywania swojej pracy? Rozwiązanie polegające na wzajemnym wykluczeniu sprawia, że udostępniony zasób jest dostępny tylko wtedy, gdy proces znajduje się w określonym segmencie kodu zwanym sekcją krytyczną . Kontroluje dostęp do współdzielonego zasobu, kontrolując każde wzajemne wykonanie tej części programu, w której zasób byłby używany.

Pomyślne rozwiązanie tego problemu musi mieć co najmniej te dwie właściwości:

Musi wdrażać wzajemne wykluczanie : tylko jeden proces może znajdować się w krytycznej sekcji na raz.
Musi być wolny od zakleszczeń : jeśli procesy próbują wejść do sekcji krytycznej, jeden z nich musi w końcu być w stanie zrobić to pomyślnie, pod warunkiem, że żaden proces nie pozostaje na stałe w sekcji krytycznej.

Swobodę impasu można rozszerzyć, aby zaimplementować jedną lub obie z tych właściwości:

Blokada blokady gwarantuje, że każdy proces, który chce wejść do sekcji krytycznej, będzie mógł to zrobić w końcu. Różni się to od unikania zakleszczeń, które wymaga, aby pewien proces oczekujący mógł uzyskać dostęp do sekcji krytycznej, ale nie wymaga, aby każdy proces miał turę. Jeśli dwa procesy nieustannie wymieniają między sobą zasoby, trzeci proces może zostać zablokowany i doświadczyć głodu zasobów , nawet jeśli system nie jest w impasie. Jeśli system jest wolny od blokad, zapewnia to, że każdy proces może się zmienić w pewnym momencie w przyszłości.
Nieruchomość oczekiwania k ograniczony daje bardziej precyzyjne zobowiązanie niż blokowania swobody. Blokada blokady zapewnia, że każdy proces może ostatecznie uzyskać dostęp do sekcji krytycznej: nie daje żadnej gwarancji, jak długo będzie czekać. W praktyce proces może zostać wyprzedzony dowolną lub nieograniczoną liczbę razy przez inne procesy o wyższym priorytecie, zanim nadejdzie kolej. W ramach właściwości oczekiwania z ograniczeniem k każdy proces ma skończony maksymalny czas oczekiwania. Działa to poprzez ustalenie limitu, ile razy inne procesy mogą ciąć w linii, tak aby żaden proces nie mógł wejść do sekcji krytycznej więcej niż k razy, podczas gdy inny czeka.

Program każdego procesu można podzielić na cztery sekcje, co daje cztery stany. Program wykonuje cykle przez te cztery stany w kolejności:

cykl odcinków jednego procesu

Sekcja niekrytyczna: Operacja znajduje się poza sekcją krytyczną; proces nie używa ani nie żąda zasobu udostępnionego.

Próbować: Proces próbuje wejść do sekcji krytycznej.

Krytyczny fragment: Proces może uzyskać dostęp do zasobu udostępnionego w tej sekcji.

Wyjście: Proces opuszcza sekcję krytyczną i udostępnia udostępniony zasób innym procesom.

Jeśli proces chce wejść do sekcji krytycznej, musi najpierw wykonać sekcję próbującą i poczekać, aż uzyska dostęp do sekcji krytycznej. Po tym, jak proces wykona swoją sekcję krytyczną i zakończy korzystanie z zasobów współdzielonych, musi wykonać sekcję wyjścia, aby zwolnić je do użytku innych procesów. Następnie proces powraca do swojej części niekrytycznej.

Egzekwowanie wzajemnego wykluczenia

Rozwiązania sprzętowe

W systemach jednoprocesorowych najprostszym sposobem osiągnięcia wzajemnego wykluczenia jest wyłączenie przerwań podczas krytycznej sekcji procesu. Zapobiegnie to uruchomieniu jakichkolwiek podprogramów obsługi przerwań (skutecznie zapobiegając wywłaszczeniu procesu ). Chociaż to rozwiązanie jest skuteczne, to prowadzi do wielu problemów. Jeśli sekcja krytyczna jest długa, zegar systemowy będzie dryfował za każdym razem, gdy wykonywana jest sekcja krytyczna, ponieważ przerwanie zegarowe nie jest już obsługiwane, więc czas śledzenia jest niemożliwy podczas sekcji krytycznej. Ponadto, jeśli proces zatrzyma się podczas jego krytycznej części, kontrola nigdy nie zostanie zwrócona do innego procesu, skutecznie zatrzymując cały system. Bardziej elegancką metodą osiągnięcia wzajemnego wykluczenia jest zajęte czekanie .

Zajęte oczekiwanie jest skuteczne zarówno w przypadku systemów jednoprocesorowych, jak i wieloprocesorowych . Użycie pamięci współdzielonej i atomowej instrukcji test-and-set zapewnia wzajemne wykluczanie. Proces może testować i ustawiać w lokalizacji w pamięci współdzielonej, a ponieważ operacja jest niepodzielna, tylko jeden proces może ustawić flagę na raz. Każdy proces, któremu nie powiodło się ustawienie flagi, może wykonać inne zadania i spróbować ponownie później, zwolnić procesor do innego procesu i spróbować ponownie później lub kontynuować pętlę podczas sprawdzania flagi, dopóki nie uda się jej uzyskać. Wywłaszczanie jest nadal możliwe, więc ta metoda pozwala systemowi na dalsze funkcjonowanie — nawet jeśli proces zostanie zatrzymany podczas trzymania blokady.

Kilka innych operacji atomowych może być użytych do zapewnienia wzajemnego wykluczania struktur danych; najważniejszym z nich jest porównanie i zamiana (CAS). CAS może być stosowany w celu osiągnięcia oczekiwania wolne od wzajemnego wykluczania dla każdej struktury danych wspólnej tworząc połączony liście , gdzie każdy węzeł reprezentuje pożądany operacji do wykonania. CAS jest następnie używany do zmiany wskaźników na połączonej liście podczas wstawiania nowego węzła. Tylko jeden proces może odnieść sukces w swoim CAS; wszystkie inne procesy próbujące dodać węzeł w tym samym czasie będą musiały spróbować ponownie. Każdy proces może następnie zachować lokalną kopię struktury danych, a po przejściu przez połączoną listę może wykonać każdą operację z listy na swojej lokalnej kopii.

Rozwiązania programowe

Oprócz rozwiązań obsługiwanych sprzętowo istnieją również rozwiązania programowe, które wykorzystują zajęte oczekiwanie do osiągnięcia wzajemnego wykluczenia. Przykłady obejmują:

Algorytm Dekkera
Algorytm Petersona
Algorytm piekarniczy Lamporta
Algorytm Szymańskiego
Czarno-biały algorytm piekarni Taubenfelda
Algorytm Maekawy

Algorytmy te nie działają, jeśli na platformie, która je wykonuje, używane jest wykonanie poza kolejnością . Programiści muszą określić ścisłą kolejność operacji pamięciowych w wątku.

Często preferowane jest korzystanie z funkcji synchronizacji zapewnianych przez wielowątkową bibliotekę systemu operacyjnego , która w miarę możliwości korzysta z rozwiązań sprzętowych, ale korzysta z rozwiązań programowych, jeśli nie istnieją żadne rozwiązania sprzętowe. Na przykład, gdy używana jest biblioteka blokad systemu operacyjnego i wątek próbuje uzyskać już nabytą blokadę, system operacyjny może zawiesić wątek za pomocą przełącznika kontekstowego i zamienić go na inny wątek, który jest gotowy do uruchomienia lub może umieścić ten procesor w stan niskiego poboru mocy, jeśli nie ma innego wątku, który można uruchomić. Dlatego większość nowoczesnych metod wzajemnego wykluczania próbuje zmniejszyć opóźnienia i oczekiwania zajętości za pomocą kolejkowania i przełączników kontekstu. Jeśli jednak można udowodnić, że czas poświęcony na zawieszenie wątku, a następnie jego przywrócenie, jest zawsze dłuższy niż czas, który musi być oczekiwany, aby wątek stał się gotowy do uruchomienia po zablokowaniu w określonej sytuacji, wówczas blokady spinlock są dopuszczalne. rozwiązanie (tylko dla tej sytuacji).

Związani problemem wzajemnego wykluczenia

Jeden binarny rejestr test&set wystarczy, aby zapewnić wolne od zakleszczeń rozwiązanie problemu wzajemnego wykluczania. Jednak rozwiązanie zbudowane za pomocą rejestru test&set może doprowadzić do zagłodzenia niektórych procesów, które zostaną złapane w sekcji próbującej. W rzeczywistości, aby uniknąć blokady, wymagane są odrębne stany pamięci. Aby uniknąć nieograniczonego oczekiwania, wymagane jest n odrębnych stanów pamięci. ${\ Displaystyle \ Omega ({\ sqrt {n}})}$

Odzyskiwalne wzajemne wykluczenie

Większość algorytmów wzajemnego wykluczania została zaprojektowana z założeniem, że nie dochodzi do awarii, gdy proces działa w sekcji krytycznej. Jednak w rzeczywistości takie awarie mogą być powszechne. Na przykład nagła utrata zasilania lub wadliwe połączenie może spowodować, że proces w krytycznej sekcji wystąpi nieodwracalny błąd lub w inny sposób nie będzie mógł kontynuować. Jeśli wystąpi taka awaria, konwencjonalne, nieodporne na awarie algorytmy wzajemnego wykluczania mogą spowodować zakleszczenie lub w inny sposób zawieść właściwości żywotności klucza. Aby poradzić sobie z tym problemem, zaproponowano kilka rozwiązań wykorzystujących mechanizmy odzyskiwania po awarii.

Rodzaje urządzeń wzajemnego wykluczania

Rozwiązania wyjaśnione powyżej mogą zostać użyte do zbudowania poniższych prymitywów synchronizacji:

Wiele form wzajemnego wykluczania ma skutki uboczne. Na przykład klasyczne semafory zezwalają na zakleszczenia , w których jeden proces otrzymuje semafor, inny proces otrzymuje drugi semafor, a następnie oba czekają, aż drugi semafor zostanie zwolniony. Inne typowe skutki uboczne to głód , w którym proces nigdy nie otrzymuje wystarczających zasobów, aby dokończyć; odwrócenie priorytetu , w którym wątek o wyższym priorytecie czeka na wątek o niższym priorytecie; i duże opóźnienia, w których odpowiedź na przerwania nie jest szybka.

Wiele badań ma na celu wyeliminowanie powyższych efektów, często w celu zagwarantowania nieblokującego postępu . Nie jest znany żaden doskonały schemat. Blokowanie wywołań systemowych używanych do usypiania całego procesu. Dopóki takie wywołania nie stały się threadsafe , nie było odpowiedniego mechanizmu do usypiania pojedynczego wątku w procesie (zobacz odpytywanie ).

Zobacz też

Bibliografia

Dalsza lektura

Michel Raynal: Algorytmy wzajemnego wykluczania , MIT Press, ISBN 0-262-18119-3
Sunil R. Das, Pradip K. Srimani: rozproszone algorytmy wzajemnego wykluczania , IEEE Computer Society, ISBN 0-8186-3380-8
Thomas W. Christopher, George K. Thiruvathukal: Wysokowydajna platforma obliczeniowa Java , Prentice Hall, ISBN 0-13-016164-0
Gadi Taubenfeld, Algorytmy synchronizacji i programowanie współbieżne , Pearson/Prentice Hall, ISBN 0-13-197259-6

Languages

In other projects