W ogólnej strukturze algorytmu wzajemnego wykluczania wyróżnia się 4 część:
W celu wyeksponowania protokołu dostępu, algorytmy prezentowane na kolejnych slajdach rozpoczynają się od sekcji wejściowej. Ponadto, abstrahuje się od kwestii aplikacyjnych, z których mogłoby wynikać, że w procesie jest kilka niezależnych sekcji krytycznych, związanych z dostępem do różnych zmiennych współdzielonych lub zasobów. Istotą jest realizacja protokołu dostępu !
W algorytmach tych nie wyróżnia się również procesu, który byłby arbitrem dla procesów rywalizujących o sekcję krytyczną. Wszystkie decyzje odnośnie wejścia do sekcji krytycznej podejmowane są na podstawie informacji, znajdujących się we współdzielonym obszarze pamięci. Podejścia z arbitrem wbrew pozorom nie ułatwiają rozwiązania problemu, gdyż wymagają pewnych środków komunikacji międzyprocesowej, których implementacja na bazie pamięci współdzielonej wymaga z kolei odpowiednich mechanizmów synchronizacji, w szczególności gwarancji wzajemnego wykluczania. W pewnym sensie jednak rozwiązania bazujące na mechanizmach systemowych (np. semaforach) opierają się na arbitrażu ze strony jądra systemu operacyjnego, które decyduje o przejściu procesu zablokowanego w stan gotowości.
Zasadnicze założenie na potrzeby analizy poprawności rozwiązania problemu wzajemnego wykluczania to skończony czas przebywania procesu w swojej sekcji krytycznej.
Warunkiem bezpieczeństwa jest wzajemne wykluczanie, co oznacza, że nigdy w systemie nie może zaistnieć stan, w którym dwa (lub więcej) procesy byłyby w swojej sekcji krytycznej.
Warunek postępu oznacza, że jeśli nie ma żadnego procesu w sekcji krytycznej, a są procesy w sekcji wejściowej, to jeden z nich w skończonym czasie (po zajściu skończonej liczby zdarzeń w systemie) wejdzie do sekcji krytycznej.
Warunek postępu nie gwarantuje, że konkretny proces wejdzie do sekcji krytycznej. Może się zdarzyć tak, że w momencie przejścia do sekcji wyjściowej, proces opuszczający sekcję krytyczną do sygnał do wejścia procesom oczekującym w sekcji wejściowej, w wyniku którego jakiś proces wejdzie do sekcji krytycznej, a inny (przy zachowaniu warunku bezpieczeństwa) oczywiście nie wejdzie. Przy kolejnym sygnale ze strony procesu wychodzącego z sekcji krytycznej pominięty poprzednio proces ponownie może nie uzyskać prawa wejścia, podczas gdy inny proces wykonujący swoją sekcję wejściową prawo takie dostanie. Sytuacja może się powtarzać w nieskończoność. Postęp jest zachowany bo jakiś proces wchodzi do sekcji krytycznej, ale istnieje proces permanentnie pomijany.
Warunek ograniczonego czekania gwarantuje właśnie, że każdy proces ubiegający się o wejście do sekcji krytycznej w końcu (w skończonym czasie, po skończonej liczbie zdarzeń w systemie) uzyska prawo wejścia do niej. Warto podkreślić, że nie wszystkie algorytmy gwarantuję tę własność.
Pierwsze podejście do rozwiązania problemu wzajemnego wykluczania w oparciu o pamięć współdzieloną polega na wykorzystaniu współdzielonej zmiennej wejściowo-wyjściowej numer, wskazującej numer (identyfikator) procesu, który ma prawo wejść do sekcji krytycznej. Podejście rozważane jest w kontekście dwóch procesów, mogłoby jednak być uogólnione na większą ich liczbę. Drugi z procesów wykonuje analogiczne operacje, przy czym w miejscu numeru i występuje j i odwrotnie. Kod dla Pj wygląda zatem następująco:
while numer ≠ j do nic; sekcja krytycznaj; numer := i; resztaj;
Zmienna numer, ze względu na fakt współdzielenia, jest inicjalizowana globalnie wartością, która jest numerem jednego z procesów. Proces o tym numerze będzie mógł jako pierwszy wejść do sekcji krytycznej, podczas gdy wszystkie pozostałe procesy, ubiegające się o wejście, utkną w pętli while.
Ponieważ dopiero w sekcji wyjściowej proces ustawia numer następnego procesu do wejścia do sekcji krytycznej, nie ma ryzyka naruszenie warunku bezpieczeństwa. Podejście to wymusza jednak naprzemienność zajmowania sekcji krytycznej przez dwa procesy. Nie jest zatem spełniony warunek postępu, gdyż proces Pi, wychodząc z sekcji krytycznej, nie może zająć jej ponownie, zanim nie zrobi tego proces Pj. Może więc dojść do takiego stanu, w którym proces Pi po opuszczeniu sekcji krytycznej ponownie wchodzi do sekcji wejściowej i nie może zająć sekcji krytycznej. Jeśli z programu procesu Pj wynika, że nie będzie on już wchodził do sekcji krytycznej, proces Pi nie wejdzie tam nigdy.
Podejście bazuje na współdzielonej tablicy znacznik, przy czy każdy z dwóch procesów modyfikuje w niej pozycję odpowiadającą swojemu numerowi. Traktując poszczególne pozycje tablicy znacznik w odseparowaniu można stwierdzić, że dla procesu Pi znacznik[i ] jest zmienną wyjściową, a dla Pj jest zmienną wejściową. Odwrotna zależność dotyczy oczywiście zmiennej znacznik[j].
W rozwiązaniu tym proces sygnalizuje zamiar lub docelowo fakt wejścia do sekcji krytycznej, ustawiając znacznik na swojej pozycji na true. W celu stwierdzenia dostępności sekcji krytycznej sprawdza wartość znacznika na pozycji odpowiadającej rywalowi (dla Pi rywalem jest Pj i odwrotnie). Jeśli znacznik na pozycji rywala ma wartość false, proces przerywa pętlę while i tym samym wchodzi do sekcji krytycznej.
Własność bezpieczeństwa łatwo można wykazać metodą nie wprost. Zakładając, że dwa procesy mogą jednocześnie wykonywać sekcję krytyczną, każdy z nich musiał odczytać wartość false z pozycji tablicy znacznik, odpowiadającej rywalowi. Wcześniej jednak każdy z nich ustawił wartość true na swojej pozycji. Przeplot z punktu widzenia każdego z procesów musi zatem uwzględniać fakt, że nie została ustawiona wartość true na pozycji rywala. Dla Pi oznacza to, że podstawienie true pod znacznik[j] wykonało się po zakończeniu przez niego pętli while. Dla Pj sytuacja jest odwrotna, więc Pi musiałby wykonać pętlę po podstawieniu true pod znacznik[j].
Własność postępu nie jest spełniona, gdyż mogą nastąpić podstawienia true pod odpowiednie pozycje znacznika, czyli:
znacznik[i] := true;
znacznik[j] := true;
W takim stanie systemu oba procesy utkną w pętli while w swoich sekcjach wejściowych i żaden nie wejdzie do sekcji krytycznej. Stan taki będzie stabilny, tzn. nie zmieni się, jeśli nie nastąpi jakaś interwencja z zewnątrz (spoza zbioru procesów). Jest to przykład zakleszczenia (ang. deadlock).
Przedstawione podejście jest podobne do poprzedniego. Różnica polega na tym, że zamiast tylko testować znacznik na pozycji odpowiadającej procesowi rywalizującemu po ustawieniu wartości true na własnej pozycji, proces dodatkowo wykonuje kolejno dwa podstawienia — wartości false oraz true — na swojej pozycji w tablicy znacznik. Pomiędzy tymi podstawieniami może być pewna zwłoka czasowa. W ten sposób stwarza szansę rywalowi, że „wplecie” się z odczytem znacznika (w nagłówku pętli while) pomiędzy te dwa podstawienia, odczyta false i wejdzie do sekcji krytycznej. Przykładowy przeplot w najprostszym przypadku byłby następujący:
{Pi} znacznik[i] := true; {Pj} znacznik[j] := true; {Pi} while znacznik[j] do {Pi} znacznik[i] := false; {Pj} while znacznik[i] do ... // wyjście z pętli {Pj} sekcja krytycznaj
Nie ma tu zatem zakleszczenia, gdyż przy asynchroniczności przetwarzania cały czas istnieje potencjalna szansa, że jeden z procesów opuści sekcję wejściową i wejdzie do sekcji krytycznej. Z drugiej strony nie ma pewności, że tak się kiedyś stanie. Stan taki nie jest stabilny — może (ale nie musi) się zmienić — i nazywany jest uwięzieniem (ang. livelock). Pojęcie uwięzienia można kojarzyć z głodzeniem procesu. Głodzenie dotyczy jednak określonego procesu, którego obsługa — najczęściej ze względu na niski priorytet — jest odkładana na dalszy plan, przy czym w systemie ciągle jest rywal o wyższym priorytecie. Uwięzienie z kolei dotyczy ogółu rywalizujących procesów, można zatem powiedzieć, że jest to głodzenie wszystkich współpracujących procesów.
Rozwiązanie to jest wynikiem połączenia podejścia 1 i 2. Za pośrednictwem tablicy znacznik procesy informują się nawzajem o swoim stanie, a za pośrednictwem zmiennej numer rozstrzygają ewentualny konflikt. Jeśli zatem wartość w tablicy znacznik na pozycji odpowiadającej procesowi rywalizującemu jest ustawiona na false, to nie ubiega się on o sekcję krytyczną. Następuje wówczas opuszczenie pętli while, tym samym sekcji wejściowej i wejście do sekcji krytycznej. W przypadku, gdy dwa rywalizujące procesu ustawią wartość true na swoich pozycjach w tablicy znacznik, rozstrzygnięcie sporu zależy od wartości zmiennej numer. Ten z procesów, który później ustawi w niej numer rywala, ten musi poczekać, aż rywal wyjdzie z sekcji krytycznej.
Przedstawione rozwiązanie znane jest pod nazwą algorytmu Petersona. Algorytm ten można uogólnić na n procesów, stosując podejście „wieloetapowe”. Na każdym etapie eliminowany jest jeden proces. Zmienna numer musi być wówczas tablicą n-1 - elementową, a tablica znacznik przechowuje numer etapu, na którym jest dany proces.
Idea algorytm piekarni, zaproponowanego przez Lamporta, opiera się na przydzielaniu kolejnego numeru w kolejce oczekujących petentów i wpuszczaniu petenta z najniższym numerem. Algorytm stosowany jest w niektórych urzędach, bankach oraz przychodniach lekarskich.
Etap algorytmu, w którym przydzielany jest numer, nazywany jest przejściem przez drzwi. Jest to część sekcji wejściowej. Proces, przechodząc przez drzwi, odczytuje numer wszystkich pozostałych, wybiera maksymalny z nich, zwiększa go o 1 i w ten sposób ustala swój własny numer. Proces, który wykonuje resztę, ma numer 0. Numery przydzielone procesom przechowywane są w tablicy współdzielonej numer . Pozycja i -ta tej tablicy jest zmienną wyjściową procesu Pi , a wszystkie pozostałe pozycje tablicy są dla niego zmiennymi wejściowymi. Wynika to z rozwinięcia operacji max, która w pełnej postaci mogłaby wyglądać następująco:
tmp := numer[0]; for k := 1 to n -1 do if numer[k] > tmp then tmp := numer[k]; numer[i] := tmp;
Dodatkowo można by jeszcze wykluczyć przypadek k = i w pętli. Początkowo tablica numer wypełniona jest oczywiście wartościami 0
W celu kontroli przydziału numeru każdy proces ustawia na swojej pozycji w tablicy wybieranie wartość true na czas ustalania swojego numeru. Początkowo tablica wypełniona jest oczywiście wartościami false.
Analizując szczegóły operacji na zmiennych współdzielonych, można zauważyć, że wszystkie zmienne są modyfikowane przez 1 proces, a czytane przez pozostałe. Są to tzw. współdzielone rejestry typu „jeden zapisujący wielu odczytujących” (ang. single-writer-multiple-readers shared registers).
Po ustaleniu numeru zaczyna się właściwa sekcje wejściowa, w której dokonuje się rozstrzygnięcie odnośnie zajęcia sekcji krytycznej. W tym celu proces Pi sprawdza zamiary kolejnych rywali, analizując współdzielone tablice począwszy od pozycji 0 z pominięciem własnej pozycji. Jeśli analizowana pozycja odnosi się do procesu, który jest w trakcie wybierania numeru, wykonywana jest pętla oczekiwania na zakończenie wyboru (linia 3). Wykazanie konieczności takiego oczekiwania jest jednym z zadań ćwiczeniowych.
Po ewentualnym zakończeniu wyboru następuje sprawdzenie stanu potencjalnego rywala. Jeśli ma on przydzielony numer 0, to znaczy, że wykonuje resztę i nie jest zainteresowany sekcją krytyczną — pętla while w linii 4 kończy się i rozpoczyna się kolejna iteracji pętli for. To samo dzieje się, gdy numer rywala jest większy. Możliwy jest jednak przypadek, gdy dwa procesu uzyskają te same numery. Rozstrzygający jest wówczas numer procesu, który z założenia jest unikalny. Stąd porównanie:(numer [k],k ) < (numer [i],i) ≡ numer [k] < numer [i] ∨ (numer [k] = numer [i] ∧ k < i ), które można by również zapisać jako (numer [k] · n + k) < (numer [i] · n + i ).
Jeśli w ten sposób procesowi Pi uda się zakończyć pętlę for , to znaczy, że nie ma w systemie procesu ubiegającego się o sekcję krytyczną, którego numer byłby mniejszy (lub równy przy mniejszym identyfikatorze) od Pi i możne on opuścić sekcję wejściową, zajmując tym samym sekcję krytyczną.
Po wyjściu z sekcji krytycznej, proces sygnalizuje brak zainteresowania rywalizacją, wpisując wartość 0 jako swój numer.