Analiza programowych rozwiązań problemu wzajemnego wykluczania
Spis treści |
[edytuj] Formalne sformułowanie problemu
Dany jest zbiór procesów sekwencyjnych komunikujących się przez wspólną pamięć. Każdy z procesów zawiera sekcję krytyczną, w której następuje dostęp do wspólnej pamięci. Procesy te są procesami cyklicznymi
Zakłada się ponadto:
- Zapis i odczyt wspólnych danych jest operacją niepodzielną, a próba jednoczesnych zapisów lub odczytów realizowana jest sekwencyjnie w nieznanej kolejności.
- Sekcje krytyczne nie mają priorytetu.
- Względne prędkości wykonywania procesów są nieznane.
- Proces może zostać zawieszony poza sekcją krytyczną.
- Procesy realizujące instrukcje poza sekcją krytyczną nie mogą uniemożliwiać innym procesom wejścia do sekcji krytycznej. Inaczej słaby warunek postępu.
- Procesy powinny uzyskać dostęp do sekcji krytycznej w skończonym czasie. Inaczej mocny warunek postępu.
Przy tych założeniach należy zagwarantować, że w każdej chwili czasu co najwyżej jeden proces jest w swej sekcji krytycznej. Nazywa sie to warunkiem bezpieczeństwa.
[edytuj] Algorytm naiwny nr 1
01 program VERSIONONE; 02 var processNumber: INTEGER; 03 procedure PROCESSONE; 04 begin 05 while True do 06 begin 07 while processNumber=2 do; 08 criticalSectionOne; 09 processNumber:=2; 10 otherStuffOne; 11 end; 12 end; 13 procedure PROCESSTWO; 14 begin 15 while True do 16 begin 17 while processNumber=1 do; 18 criticalSectionTwo; 19 processNumber:=1; 20 otherStuffTwo; 21 end; 22 end; 23 begin 24 processNumber:= 1; 25 parbegin 26 PROCESSONE; 27 PROCESSTWO; 28 parend; 29 end.
Procesy sekwencyjnie wchodzą do sekcji jeden po drugim (nie ma możliwości aby jeden proces wszedł do sekcji dwa razy pod rząd). O tym, który proces może wejść decyduje zmienna processNumber na której odbywa się aktywne czekanie w liniach 17 i 07.
[edytuj] Problemy
Procesy dokonują ścisłej wymiany - jeżeli jeden z nich się zawiesi, drugi nie będzie mógł ponownie wejść do sekcji krytycznej. Powiedzmy, że proces pierwszy po wyjściu z sekcji krytycznej zawiesza się podczas wykonywania otherStuffOne (wg. punktu 4. może tak się zdarzyć). Proces drugi wchodzi do sekcji krytycznej, wychodzi z niej przestawiając processNumber na 1, a następnie czeka w nieskończoność, aż proces pierwszy przestawi ją znów na 2. Niespełnione są więc punkty 5 i 6 - słaby oraz silny warunek postępu. Identyczna sytuacja będzie miała miejsce, jeżeli jeden z procesów zakończy swoje działanie.
[edytuj] Algorytm naiwny nr 2
01 program VERSIONTWO; 02 var P1inside, P2inside: BOOLEAN; 03 procedure PROCESSONE; 04 begin 05 while True do 06 begin 07 while P2inside do; 08 P1inside:=True; 09 criticalSectionOne; 10 P1inside:=False; 11 otherStaffOne; 12 end; 13 end; 14 procedure PROCESSTWO; 15 begin 16 while True do 17 begin 18 while P1inside do; 19 P2inside:=True; 20 criticalSectionTwo; 21 P2inside:=False; 22 otherStaffTwo; 23 end; 24 end; 25 begin 26 P1inside:=False; 27 P2inside:=False; 28 parbegin 29 PROCESSONE; 30 PROCESSTWO; 31 parend; 32 end.
Procesy informują siebie nawzajem o tym, że weszły do sekcji krytycznej przy pomocy zmiennych P1inside i P2inside. Proces zanim wejdzie do sekcji krytycznej sprawdza czy drugi proces już tam nie jest (aktywne czekanie w linijkach 07 i 18).
[edytuj] Problemy
Operacje sprawadzania i ustawiania zmiennych mówiacych o obecności innego procesu w sekcji krytycznej nie są atomowe. Możemy wyobrazić sobie sytuacje gdy obie zmienne P1inside i P2inside ustawione są na false, następnie wykonywana jest linijka 07, a tuż po niej linijka 18. Oba procesy wejdą w takiej sytuacji do sekcji krytycznej w tym samym momencie.
[edytuj] Algorytm naiwny nr 3
01 program VERSIONTHREE; 02 var P1WantsToEnter: BOOLEAN; 03 var P2WantsToEnter: BOOLEAN; 04 procedure PROCESSONE; 05 begin 06 while True do 07 begin 08 P1WantsToEnter:=True; 09 while P2WantsToEnter do; 10 criticalSectionOne; 11 P1WantsToEnter:=False; 12 otherStuffOne; 13 end; 14 end; 15 procedure PROCESSTWO; 16 begin 17 while True do 18 begin 19 P2WantsToEnter:=True; 20 while P1WantsToEnter do; 21 criticalSectionTwo; 22 P2WantsToEnter:=False; 23 otherStuffTwo; 24 end; 25 end; 26 begin 27 P1WantsToEnter:=False; 28 P2WantsToEnter:=False; 29 parbegin 30 PROCESSONE; 31 PROCESSTWO; 32 parend; 33 end.
Oba procesy deklarują chęć wejścia do sekcji krytycznej przy pomocy zmiennych P1WantsToEnter i P2WantsToEnter po czym sprawdzają, czy inny proces też nie wyraża takiej chęci - jeżeli nie, wchodzą do sekcji krytycznej.
[edytuj] Problemy
Zadeklarowanie chęci wejścia do sekcji i sprawdzenie, czy inny proces nie chce wejść, nie jest atomowe. Można wyobrazić sobie sytuację, w której przy początkowych wartościach false obu zmiennych wykonywane są kolejno linie 08 (pierwszy deklaruje chęć wejścia) i 19 (drugi robi to samo) po czym oba procesy wpadają w nieskończone pętle na liniach 09 i 20. Następuje zakleszcze, więc nie zostaje spełniony warunek 6 (skończony czas dostępu).
[edytuj] Algorytm naiwny nr 4
01 program VERSIONFOUR; 02 var P1WantsToEnter: BOOLEAN; 03 var P2WantsToEnter: BOOLEAN; 04 procedure PROCESSONE; 05 begin 06 while True do 07 begin 08 P1WantsToEnter:=True; 09 while P2WantsToEnter do 10 begin 11 P1WantsToEnter:=False; 12 delay(random,freecycles); 13 P1WantsToEnter:=True; 14 end; 15 criticalSectionOne; 16 P1WantsToEnter:=False; 17 otherStuffOne; 18 end; 19 end; 20 procedure PROCESSTWO; 21 begin 22 while True do 23 begin 24 P2WantsToEnter:=True; 25 while P1WantsToEnter do 26 begin 27 P2WantsToEnter:=False; 28 delay(random,freecycles); 29 P2WantsToEnter:=True; 30 end; 31 criticalSectionTwo; 32 P2WantsToEnter:=False; 33 otherStuffTwo; 34 end; 35 end; 36 begin 37 P1WantsToEnter:=False; 38 P2WantsToEnter:=False; 39 parbegin 40 PROCESSONE; 41 PROCESSTWO; 42 parend; 43 end.
Jest to zmodyfikowana wersja poprzedniego algorytmu polegająca na tym, że podczas aktywnego czekania, aż drugi proces zrezygnuje z ubiegania się o sekcję krytyczną, następuje rezygnacja z ubiegania się o sekcję krytyczną i uśpienie na losowy okres czasu (linie 09-14 i 25-30).
[edytuj] Problemy
Zastosowane zmiany mają przeciwdziałać zakleszczeniom, powodując, że w krytycznym przypadku przedstawionym w poprzednim algorytmie jeden proces zwolni zasoby na losowy okres czasu, a drugi w tym czasie wskoczy na jego miejsce. Problem polega na tym, że istnieje niezerowe prawdopodobieństwo, że oba procesy będą usypiane w tych samych momentach na ten sam okres czasu i nadal będą trwały w zakleszczeniu. Prawdopodobieństwo to maleje wraz ze wzrostem przedziału czasu, z którego losujemy czas "drzemki". Wydłużenie tego czasu do nieskończoności daje nam nadal złamanie warunku 6.
Możliwa jest też sytuacja, w której drugi proces czeka, aż pierwszy skończy, podczas gdy drugi w nieskończoność "wskakuje" w "drzemkę" drugiego procesu głodząc go.
[edytuj] Algorytm Hymana
01 var flaga: array[1..2] of integer; (* początkowo 0 *) 02 numer: 1..2; 03 repeat 04 flaga[i]:=numer; 05 while numer<>i do 06 begin 07 while flaga[j]<>0 do nic; 08 numer:=i; 09 end; 10 criticalSection; 11 flaga[i]:=0; 12 otherStuff; 13 until false;
Podejście zaproponowane przez Hymana - nie spełnia jednak warunku bezpieczeństwa.
[edytuj] Problemy
Poniższa sekwencja doprowadza oba procesy do jednoczesnego wejscia do sekcji krytycznej.
| flaga[1] = flaga[2] = 0; numer = 2 | |
| Proces nr 1 (i = 1) | Proces nr 2 (i = 2) |
| 04 flaga[1] = 2 | ... |
| 05 while numer<>1 do | |
| 06 begin | |
| 07 while flaga[2]<>0 do nic; | |
| ... | |
| 04 flaga[2] = 2 | |
| 05 while numer<>2 do | |
| 10 criticalSection; | |
| 08 numer:=1; | |
| 10 criticalSection; | |
[edytuj] Algorytm Dekkera
01 program DEKKERALGORITHM; 02 var favoredProcess: enum (First, Second); 03 var P1WantsToEnter, P2WantsToEnter: BOOLEAN; 04 procedure PROCESSONE; 05 begin 06 while True do 07 begin 08 P1WantsToEnter:=True; 09 while P2WantsToEnter do 10 if favoredProcess=Second then 11 begin 12 P1WantsToEnter:=False; 13 while favoredProcess=Second do; 14 P1WantsToEnter:=True; 15 end; 16 criticalSectionOne; 17 favoredProcess:=Second; 18 P1WantsToEnter:=False; 19 otherStuffOne; 20 end; 21 end; 22 procedure PROCESSTWO; 23 begin 24 while True do 25 begin 26 P2WantsToEnter:= True; 27 while P1WantsToEnter do 28 if favoredProcess=First then 29 begin 30 P2WantsToEnter:=False; 31 while favoredProcess=First do; 32 P2WantsToEnter:= True; 33 end; 34 criticalSectionTwo; 35 favoredProcess:=First; 36 P2WantsToEnter:=False; 37 otherStuffTwo; 38 end; 39 end; 40 begin 41 P1WantsToEnter:= False; 42 P2WantsToEnter:= False; 43 favoredProcess:= First; 44 parbegin 45 PROCESSONE; 46 PROCESSTWO; 47 parend; 48 end.
Jest to rozwinięcie ostatniego algorytmu, w którym w specjalny sposób traktuje się sytuację, gdy dwa procesy naraz zgłosiły chęć wejścia do sekcji krytycznej. Zmienna favoredProcess określa, którego procesu jest właśnie kolej. Jeżeli nasza to czekamy, aż drugi proces zmieni zmienną P2WantsToEnter. W przeciwnym wypadku zwalniamy swoją zmienną P1WantsToEnter i czekamy na naszą kolej. Uzyskujemy naprzemienny dostęp w krytycznych przypadkach jednoczesnej próby dostępu i to bez zaawansowanych narzędzi, takich jak semafory.
Dzięki rezerwowaniu zasobów zapewniamy, że oba procesy nie wejdą na raz do sekcji krytycznej. favoredProcess zapewnia, że każdy proces kiedyś wejdzie. Dzięki temu, że procesy nie czekają ciągle rezerwując zasoby, nie dojdzie do zakleszczenia.
[edytuj] Algorytm Dijkstry
01 program DIJKSTRAALGORITHM; 02 begin 03 shared 04 flag[1..n]: 0..2; 05 turn : 1..n; 06 local 07 testi : 0..2; 08 k, otheri, tempi: 1..n; 09 while True do 10 begin 11 L: flag[i]:=1; 12 otheri:=turn; 13 while otheri≠i do 14 begin 15 testi:=flag[otheri]; 16 if testi=0 then 17 turn:=i; 18 otheri:=turn; 19 end; 20 flag[i]:=2; 21 for k:=1 to n do 22 if k≠i then 23 begin 24 testi:=flag[k]; 25 if testi=2 then 26 goto L; 27 end; 28 criticalSection; 29 flag[i]:=0; 30 otherStuff; 31 end; 32 end.
Algorytm składa się z dwóch faz. W pierwszej sprawdzamy, czy jest nasza kolej. Jeżeli nie, a proces, którego jest kolej, wyszedł z sekcji krytycznej (flag[turn]=0), to ustawiamy kolej na siebie. W drugiej fazie sprawdzamy, czy którykolwiek inny proces nie jest w drugiej fazie. Jeżeli tak, to wracamy do fazy pierwszej. W przeciwnym wypadku wchodzimy do sekcji krytycznej.
[edytuj] Problemy
Algorytm ten nie spełnia silnego warunku postępu. Mianowicie przy pewnych prędkościach wykonywania procesów, pewien proces, który przebrnął przez sekcje krytyczną może z powrotem do niej trafić, nie wpuszczając "oczekujących" pozostałych procesów. Ma to miejsce wtedy, jeżeli czekające procesy nie zdążą "zauważyć" zmiany flag[i] na 0). Taka sytuacja może się powtarzać cyklicznie, czyli czekające procesy zostaną "zagłodzone".
[edytuj] Algorytm Petersona dla 2 procesów
01 program PATERSONALGORITHM; 02 begin 03 shared 04 flag[0..1]: BOOLEAN; 05 turn: INTEGER; 06 local 07 otheri: BOOLEAN; 08 whosei: INTEGER; 09 while True do 10 begin 11 flag[i]:= True; 12 turn:=1-i; 13 repeat 14 whosei:=turn; 15 otheri:=flag[1-i]; 16 until (whosei=i or not otheri); 17 criticalSection; 18 flag[i]:= False; 19 remainderSection; 20 end; 21 end.
Parametr i przyjmuje wartości 0 lub 1 (w zależności od procesu). W algorytmie najpierw w liniach 11 i 12 ustawiamy chęć wejścia do sekcji krytycznej i kolej (turn) na przeciwny proces. Następnie czekamy, aż nie nastąpi nasza kolej albo drugi proces nie będzie wyrażał chęci wejścia do sekcji krytycznej. Dzięki zmiennej turn w przypadku jednoczesnej próby wejścia do sekcji krytycznej zawsze zostanie wybrany tylko jeden proces.
[edytuj] Algorytm Petersona dla n procesów
01 program PATERSONALGORITHM_N; 02 begin 03 shared 04 flag[1..n]: INTEGER; 05 turn[1..n-1]: INTEGER; 06 local 07 k, l, otheri, whosei: INTEGER; 08 while True do 09 begin 10 for k:=1 to n-1 do 11 begin 12 flag[i]:=k; 13 turn[k]:=i; 14 repeat 15 whosei:=turn[k]; 16 if whosei≠i then break; 17 for l:=1 to n do 18 begin 19 if l≠i then begin 20 otheri:=flag[l]; 21 if otheri≥k then break; end; 22 end; 23 until otheri<k; 24 end; 25 criticalSection; 26 flag[i]:=0; 27 remainderSection; 28 end; 29 end.
Zmienna flag[i] przechowuje informacje o etapie wchodzenia do sekcji krytycznej i-tego procesu, etapów jest n-1, gdzie n - to liczba procesów ubiegających się o zasoby. Zmienna turn[k] przechowuje informacje o procesie o najniższym priorytecie na k-tym etapie. Jeżeli proces i-ty jest tym o najniższym priorytecie, wtedy musi on wykonać pętle for (linie od 17 do 22). Pozostałe procesy przechodzą od razu do następnego etapu dotarcia do sekcji krytycznej. W ten sposób, na każdym następnym etapie zostaje jeden proces. Każdy z tych pozostających procesów może przejść do następnego etapu, jeżeli żaden inny proces nie jest na etapie dalszym (warunek z linii 23). Po wykonaniu sekcji krytycznej, etap dotarcia procesu ustawiany jest na 0 (linia 26), co oznacza, że proces będący na najwyższym etapie, może przejść do następnego etapu, gdyż żaden inny proces nie jest bliżej sekcji krytycznej.
[edytuj] Algorytm Lamporta dla n procesów
01 program LAMPORTALGORITHM; 02 begin 03 shared 04 choosing[1..n]: 0..1; 05 num[1..n]: INTEGER; 06 local 07 testi: 0..1; 08 k, minei : INTEGER; 09 otheri, tempi: INTEGER; 10 while True do 11 begin 12 choosing[i]:=1; 13 for k:=1 to n do 14 if k≠i then 15 begin 16 tempi:=num[k] ; 17 minei:=max(minei,tempi); 18 end; 19 minei:= minei+1; 20 num[i]:= minei; 21 choosing[i]:=0; 22 for k:=1 to n do 23 if k≠i then 24 begin 25 repeat 26 testi:=choosing[k]; 27 until testi=0; 28 repeat 29 otheri:=num[k]; 30 until otheri=0 or (minei,i)<(otheri,k); 31 end; 32 criticalSection; 33 num[i]:=0 ; 34 otherStuff; 35 end; 36 end.
Algorytm ten opiera się na przydzielaniu numerów wszystkim procesom, które chcą wejść do sekcji krytycznej. Pierwszej fazie (linie 12-21) przydzielamy procesowi numer - największy dotychczas przydzielony + 1. Następnie w drugiej fazie dla każdego procesu sprawdzamy czy aby nie jest nadal w fazie pierwszej (linie 25-27) oraz czy jego numer jest większy od naszego. Przydzielane numery pełnią tutaj rolę priorytetów - im mniejszy numer tym wyższy priorytet.
Nie ma jednak sposobu, aby zapewnić, że zawsze zostanie przydzielony unikatowy numer (dwa procesy mogą na raz wykonywać pierwszą fazę i uzyskać ten sam numer. Dlatego jako dodatkowy współczynnik wykorzystuje się unikatowy id procesu - reprezentowany przez zmienną i. De facto dokonuje się tego w linii 30. (minei,i)<(otheri,k) można rozpisać jako (minei < otheri) or (minei = otheri and i < k).
Algorytm ten znany jest również pod nazwą bakery algorithm.
Co by się stało po usunięciu linii 25-27:
| num[0] = num[1] = 0 | |
| Proces nr 0 (i = 0) | Proces nr 1 (i = 1) |
| ... | ... |
| 19: minei = 1, num[0] = 0 | |
| 20: num[1] = 1 | |
| ... | |
| 29: (k = 0) otheri = 0 | |
| 30: until otheri = 0 or ... (OK) | |
| sekcja krytyczna | |
| 20: num[0] = 1 | |
| ... | |
| 29: (k = 1) otheri = 1 | |
| 30: until otheri = 0 or (minei, i) < (otheri, k) // (1, 0) < (1, 1) (OK) | |
| sekcja krytyczna | |
Pewnym problemem związanym z algorytmem Lamporta jest skończony zakres zmiennej mine. Przykładowe rozszerzenie zapobiegające 'przekręceniu' wygląda następująco:
01 program LAMPORTALGORITHMv2.0; 02 begin 03 shared 04 choosing[1..n]: 0..1; 05 num[1..2][1..n]: INTEGER; 06 active: 1..2; 07 bank: 1..2; 08 MAX: INTEGER := MAX_INT-n; 09 local 10 testi: 0..1; 11 k, minei : INTEGER; 12 otheri, tempi: INTEGER; 13 mybanki: 1..2; 14 while True do 15 begin 16 minei:=0; 17 choosing[i]:=1; 18 mybanki:=bank; 19 for k:=1 to n do 20 if k≠i then 21 begin 22 tempi:=num[mybanki][k]; 23 minei:=max(minei,tempi); 24 end; 25 minei:= minei+1; 26 if mine>MAX then 27 bank:=(mybanki mod2)+1; 28 num[mybanki][i]:= minei; 29 choosing[i]:=0; 30 while mybanki<>active do; 31 for k:=1 to n do 32 if k≠i then 33 begin 34 repeat 35 testi:=choosing[k]; 36 until testi=0; 37 repeat 38 otheri:=num[mybanki][k]; 39 until otheri=0 or (minei,i)<(otheri,k); 40 end; 41 criticalSection; 42 num[mybanki][i]:=0 ; 43 remainderSection; 44 end; 45 end. 46 program SUPERVISOR; 47 begin 48 shared 49 choosing[1..n]: 0..1; 50 num[1..2][1..n]: INTEGER; 51 active: 1..2; 52 bank: 1..2; 53 MAX: INTEGER := MAX_INT-n; 54 local 55 test: 0..1; 56 k : INTEGER; 57 other: INTEGER; 58 while True do 59 begin 60 while bank=active do; 61 for k:=1 to n do 62 begin 63 repeat 64 test:=choosing[k]; 65 until test=0; 66 repeat 67 other:=num[active][k]; 68 until other=0; 69 end; 70 active:=bank; 71 end; 72 end.
Rozwiązanie to polega na wykorzystywaniu na zmianę dwóch banków numerów. Gdy jakiś proces stwierdzi, że nadany mu numer jest odpowiednio duży (większy od wartości MAX), przełącza bank na przeciwny, w wyniku czego kolejnym procesom nadawane są numery od zera. Procesy te jednak po otrzymaniu numeru muszą czekać, aż ich bank stanie się aktywnym (linia 30). Przełączeniem zajmuje się wyróżniony proces nadzorcy, który nic nie robi, dopóki aktywnym bankiem jest aktualnie używany (linia 60), a w przeciwnym wypadku czeka do momentu, aż aktywny bank zostanie wyzerowany (wszystkie procesy posiadające numery z tego banku opuszczą sekcję krytyczną), po czym ustawia wartość zmiennej active na ten bank, z którego są aktualnie przydzielane numery (linia 70).
Rozwiązanie to działa poprawnie dla liczby procesów mniejszej od największej wartości typu Integer podzielonej przez dwa (wartość MAX musi być większa od liczby procesów).
Inne rozwiazanie 2008 (wyklady) zapobiegajace przepelnieniu licznika
1 program LAMPORTALGORITHM; 02 begin 03 shared 04 choosing[1..n]: 0..1; 05 num[1..n]: INTEGER; //------------------------ updating := 0; // okresla czy nastepuje "przesuniecie kolejki" //------------------------ 06 local 07 testi: 0..1; 08 k, minei : INTEGER; 09 otheri, tempi: INTEGER; 10 while True do 11 begin //------------------------ while updating = 1 do; // jesli następuje odświeżanie kolejki to się // wstrzymujemy z szukaniem numerka //------------------------ 12 choosing[i]:=1; 13 for k:=1 to n do 14 if k≠i then 15 begin 16 tempi:=num[k]; 17 minei:=max(minei,tempi); 18 end; 19 minei:= minei+1; 20 num[i]:= minei; 21 choosing[i]:=0; 22 for k:=1 to n do 23 if k≠i then 24 begin 25 repeat 26 testi:=choosing[k]; 27 until testi=0; 28 repeat 29 otheri:=num[k]; 30 until otheri=0 or (minei,i)<(otheri,k); 31 end; //------------------------ updating := 1; // zaznaczamy, że zaczyna się przesuwanie numerków w // kolejce for k:= 1 to n do while choosing[k] do; // jeśli ktoś jeszcze wybiera numerek, to // wstrzymujemy się z przesuwaniem kolejki, aż sobie nie wybierze // w tym miejscu nikt nie zacznie wybierania numerka (numerku?) for k:= 1 to n do if num[k] != 1 num[k] := num[k] -1; // zmniejszamy wszystkim numerek o 1, // chyba że oznaczaloby to zmianę wartości na 0 updating := 0; // kończymy przesuwanie kolejki //------------------------ 32 criticalSection; 33 num[i]:=0 ; 34 otherStuff; 35 end; 36 end.
