Problem wzajemnego wykluczania

Przykład algorytmu wzajemnego wykluczania

Algorytmy wzajemnego wykluczania (w skrócie często nazywane mutex, z ang. mutual exclusion) są używane w przetwarzaniu współbieżnym w celu uniknięcia równoczesnego użycia wspólnego zasobu (np. zmiennej globalnej) przez różne wątki/procesy w częściach kodu zwanych sekcjami krytycznymi. Sekcja krytyczna jest fragmentem kodu, w którym wątki (lub procesy) odwołują się do wspólnego zasobu. Sama w sobie nie jest ani mechanizmem, ani algorytmem wzajemnego wykluczania. Program, proces lub wątek może posiadać sekcje krytyczne bez mechanizmów czy algorytmów implementujących wzajemne wykluczanie.

Przykładami takich zasobów są flagi drobnoziarniste, liczniki czy kolejki, używane do komunikacji pomiędzy wykonywanymi współbieżnie częściami kodu, takimi jak aplikacje i ich procedury obsługi przerwań. Synchronizacja dostępu do tych zasobów nie jest prostym zagadnieniem, ponieważ wątki mogą być zatrzymywane i uruchamiane w różnych momentach.

Na przykład: Przypuśćmy, że sekcja kodu modyfikuje jakieś dane w kilku krokach. W tym samym czasie uruchamiany jest inny wątek, który próbuje odczytać te same dane. Ze względu na to, że dane są w trakcie modyfikacji przez pierwszy wątek, ich stan jest niespójny. Wynik działania drugiego wątku może być nieoczekiwany. Jeśli drugi wątek spróbuje ponadto zmodyfikować dane, staną się one niespójne i przestaną być użyteczne dla któregokolwiek z wątków. Z tego względu wspólne dane używane w sekcjach krytycznych powinny być zabezpieczone, to znaczy inne procesy czytające lub modyfikujące dane powinny być wykluczone.

Nazwą mutex określane są obiekty negocjujące dostęp pomiędzy wątkami, zwane również blokadami.

Wymuszanie wzajemnego wykluczania

Istnieją dwa sposoby do wymuszania wzajemnego wykluczania:

Rozwiązania sprzętowe

Na systemach jedno-procesorowych najczęstszym sposobem wzajemnego wykluczania w jądrach systemów operacyjnych jest wyłączenie przerwań dla jak najmniejszej liczby instrukcji kodu, chroniąc przed uszkodzeniem struktury dzielonych danych sekcji krytycznej. Zapobiega to uruchamianiu kodu w sekcji krytycznej, oraz chroni przed zmianami procesów opartych na technologii przerwań.

W komputerach, które dzielą pamięć między własnymi procesorami, niepodzielna instrukcja test-and-set flagi jest używana w pętlach w celu przeczekania do momentu aż procesor wyczyści flagę. Instrukcja ta przeprowadza dwie operacje bez wypuszczania pamięci z wyłączności. Kiedy kod opuszcza sekcje krytyczną, czyści flagę. Nazywa się to „Spinlock” lub „Busy wait”.

Podobną operacją atomową jest “compare-and-swap” używana do synchronizacji nieblokującej dla list łączonych i innych struktur danych.

Rozwiązania programowe

Implementacja muteksu musi spełniać następujące warunki:

• Niedoprowadzanie do blokady – gdy kilka procesów wyraża chęć wejścia do sekcji krytycznej, jeden z nich musi w końcu wejść.
• Nie może prowadzić do zagłodzenia – jeśli pewien proces wyraża chęć wejścia do sekcji krytycznej, to musi być w końcu dopuszczony. Jest to tak zwana uczciwość. Wyróżnia się:
  • uczciwość słabą, jeśli proces ciągle zgłasza żądanie, to w końcu zostanie dopuszczony do sekcji krytycznej.
  • uczciwość mocną, gdy proces zgłasza żądanie nieskończenie wiele razy, to zostanie w końcu dopuszczony do sekcji krytycznej
  • oczekiwanie liniowe, jeśli proces zgłasza żądanie, będzie dopuszczony do sekcji krytycznej nie później niż po tym jak każdy inny proces zostanie obsłużony jeden raz.
  • FIFO, tak jak w przypadku kolejki (bufora FIFO – pierwszy wszedł, pierwszy wyjdzie), procesy zostaną obsłużone w kolejności zgłoszenia żądań.
• Nie może prowadzić do blokady w przypadku braku współzawodnictwa. Gdy tylko jeden proces wyraża chęć wejścia do sekcji krytycznej, powinien zostać dopuszczony.

Poza rozwiązaniami wspomaganymi sprzętowo, istnieją rozwiązania wykorzystujące „Busy wait” do osiągnięcia celów.

Przykłady:

• Algorytm Dekkera
• Algorytm Petersona
• Algorytm piekarniany
• Semafor
• Monitory
• Message passing
• Tuple space

Klasycznymi metodami zmniejszenia opóźnienia i „Busy wait” jest używanie kolejek i przełączanie kontekstu.

Wiele sposobów wzajemnego wykluczania daje efekty uboczne, np. klasyczne semafory mogą prowadzić do zakleszczeń – gdy jeden proces dostaje semafor, a inny proces dostaje drugi semafor, wówczas oba procesy czekają na wzajemnie przez siebie zajęte semafory. Inny efekt uboczny polega na zagłodzeniu, w którym jeden proces nigdy nie otrzyma wystarczającej ilości zasobów do wykonania polecenia, inwersja priorytetów, w której wątek o wyższym priorytecie czeka na wątek z niższym priorytetem, gdzie duże opóźnienie może powodować brak odpowiedzi na przerwanie.

Badanie skierowane na eliminowanie powyższych efektów polega na gwarantowaniu synchronizacji nieblokujących. Nie opisano do tej pory schematów bez skutków ubocznych.

Czytaj też

• Michel Raynal: Algorithms for Mutual Exclusion, MIT Press, ISBN 0-262-18119-3
• Sunil R. Das, Pradip K. Srimani: Distributed Mutual Exclusion Algorithms, IEEE Computer Society, ISBN 0-8186-3380-8
• Thomas W. Christopher, George K. Thiruvathukal: High-Performance Java Platform Computing, Prentice Hall, ISBN 0-13-016164-0
• Gadi Taubenfeld, Synchronization Algorithms and Concurrent Programming, Pearson/Prentice Hall, ISBN 0-13-197259-6

Zobacz też

• Problem ucztujących filozofów

Linki zewnętrzne

• Common threads: POSIX threads explained – The little things called mutexes autor: Daniel Robbins
• Mutual exclusion algorithm discovery
• Mutual Exclusion Petri Net. cs.adelaide.edu.au. [zarchiwizowane z tego adresu (2004-12-05)].
• Mutual Exclusion with Locks – an Introduction
• Mutual exclusion variants in OpenMP
• The Black-White Bakery Algorithm