Programowanie współbieżne i rozproszone/PWR Ćwiczenia 1: Różnice pomiędzy wersjami
Nie podano opisu zmian |
|||
| Linia 447: | Linia 447: | ||
=== Piąta próba rozwiązania. Algorytm Petersena === | === Piąta próba rozwiązania. Algorytm Petersena === | ||
Poprawne rozwiązanie znane pod nazwą ''algorytmu Petersena'' jest sprytnym | Poprawne rozwiązanie znane pod nazwą ''algorytmu Petersena'' jest sprytnym | ||
połączeniem [[PWR_Cwiczenia_1# | połączeniem [[PWR_Cwiczenia_1#Pierwsza_próba_rozwiązania]] z | ||
przedostatnim. Utrzymujemy zmienne {\tt chce1} i {\tt chce2}, które | przedostatnim. Utrzymujemy zmienne {\tt chce1} i {\tt chce2}, które | ||
oznaczają chęć wejścia procesu do rejonu krytycznego. W razie gdy oba | oznaczają chęć wejścia procesu do rejonu krytycznego. W razie gdy oba | ||
procesy chcą wejść do rejonu krytycznego rozstrzygamy konflikt za | procesy chcą wejść do rejonu krytycznego rozstrzygamy konflikt za | ||
pomocą zmiennej {\tt ktoczeka}: | pomocą zmiennej {\tt ktoczeka}: | ||
Wersja z 11:37, 9 cze 2006
Zadanie
Treść
Uruchamiamy współbieżnie dwa następujące procesy:
process P1;
begin
while true do
begin
własne_sprawy;
protokół_wstępny;
sekcja_krytyczna;
protokół_końcowy;
end
end;
|
process P2;
begin
while true do
begin
własne_sprawy;
protokół_wstępny;
sekcja_krytyczna;
protokół_końcowy;
end
end;
|
Chcemy zapewnić, że w tym samym czasie co najwyżej jeden z nich wykonuje fragment programu oznaczony jako sekcja_krytyczna. Jakie instrukcje należy umieścić w protokołach, aby zrealizować ten cel? Nie dysponujemy żadnymi mechanizmami synchronizacyjnymi, więc protokoły powinny umiejętnie wykorzystać zmienne globalne oraz instrukcje języka programowania.
- Ćwiczenie (ukrywajka)
- Odpowiedz na poniższe pytania przed przystąpieniem do dalszej części ćwiczenia.
Jeśli masz kłopoty ze znalezieniem odpowiedzi przeczytaj jeszcze raz fragment wykładu.
- Czy protokoły wstępne i końcowe można pozostawić puste?
- Co oznacza bezpieczeństwo w przypadku tak sformułowanego zadania?
- A żywotność?
- Jaką nazwę nosi ten problem?
Postawiony powyżej problem to Problem wzajemnego wykluczania. Protokoły wstępne i końcowe nie mogą pozostać puste --- wtedy nic nie powstrzymywałoby procesu przed rozpoczęciem wykonania sekcji_krytycznej nawet wówczas, gdy drugi proces jest w trakcie jej wykonywania. Mielibyśmy jednak wtedy dwa procesy w sekcji krytycznej, co przeczy specyfikacji zadania. Ta specyfikacja określa właśnie własność bezpieczeństwa: Nigdy nie dojdzie do niepożądanej sytuacji. Ta niepożądana sytuacja to w tym przypadku jednoczesny pobyt obu procesów w sekcji krytycznej. własność żywotności w kontekście postawionego problemu oznacza, że każdy proces, który będzie chciał wejść do sekcji krytycznej, w końcu (po skończonym czasie) do niej wejdzie.
W rozwiązaniu będziemy korzystać ze zmiennych globalnych i lokalnych. Zmienna lokalna znajduje się w prywatnej przestrzeni adresowej procesu. Pozostałe procesy nie mają do niej dostępu, nie mogą jej zatem ani odczytywać ani modyfikować. Inaczej sytuacja wygląda ze zmiennymi globalnymi. Są one współdzielone przez procesy, co oznacza, że w dowolnej chwili każdy z nich może takie zmienne modyfikować lub odczytywać.
- Ćwiczenie (ukrywajka)
- Odpowiedz na poniższe pytania przed przystąpieniem do dalszej części ćwiczenia.
Jeśli masz kłopoty ze znalezieniem odpowiedzi przeczytaj jeszcze raz ten fragment wykładu.
- Co dzieje się, gdy dwa
wykonujące się równolegle procesy w tej samej chwili chcą uzyskać dostęp do tej samej zmiennej, a zatem do tej samej komórki (tych samych komórek) pamięci?
Konflikt rozwiązuje sprzęt za pomocą arbitra pamięci. Jest to układ sprzętowy, który realizuje wzajemne wykluczanie na poziomie pojedynczych komórek pamięci. Jednoczesne odwołania do tej samej komórki pamięci zostaną w jakiś, nieznany z góry, sposób uporządkowane w czasie i wykonane. W dalszej części rozważań zakładamy istnienie arbitra pamięci i jego poprawne działanie.
Pierwsza próba rozwiązania
Spróbujmy rozwiązać problem wprowadzając zmienną globalną ktoczeka. Będzie ona przyjmować wartości 1 lub 2. Wartość 1 oznacza, że proces pierwszy musi poczekać na wejście do sekcji krytycznej, a prawo wejścia do niej ma proces drugi. Oczekiwanie na wejście realizujemy poprzez pustą pętlę, której jedynym zadaniem jest cykliczne sprawdzanie warunku na wejście do sekcji krytycznej. Proces, który skorzysta z sekcji krytycznej przekazuje pierwszeństwo drugiemu.
- Ćwiczenie (ukrywajka)
- Zapisz treść procesów
Treść procesów wygląda następująco:
var kto_czeka: 1..2 := 1 | |
process P1;
begin
while true do
begin
własne_sprawy;
while kto_czeka = 1 do {nic};
sekcja_krytyczna;
kto_czeka := 1;
end
end;
|
process P2;
begin
while true do
begin
własne_sprawy;
while kto_czeka = 2 do {nic};
sekcja_krytyczna;
kto_czeka := 2
end
end;
|
Zanim przystąpimy do analizy poprawności rozwiązania przypomnijmy założenia dotyczące sekcji krytycznej, własnych spraw i systemu operacyjnego, który nadzoruje wykonywanie procesów.
- Test wielokrotnego wyboru
- Formułując problem wzajemnego wykluczania zakłada się, że:
- Każdy proces, który wszedł do sekcji krytycznej w skończonym czasie ją opuści.
- Proces może przebywać w sekcji krytycznej nie dłużej niż ustalony z góry czas.
- Proces nie może zakończyć się w sekcji krytycznej.
- Proces może się zakończyć w sekcji krytycznej ale tylko w sposób poprawny.
- Proces, który rozpoczął wykonywanie własnych_spraw:
- musi w skończonym czasie zakończyć je i przejść do protokołu wstępnego.
- może zakończyć swoje działanie na skutek błędu.
- może zakończyć swoje działanie ale tylko w sposób poprawny.
- Ćwiczenie (ukrywajka)
- Spróbuj przeanalizować samodzielnie powyższe rozwiązanie i odpowiedzieć na pytania:
- Czy ma ono własność bezpieczeństwa?
- Czy ma ono własność żywotność?
- A może widzisz inne jego wady?
Własnośc bezpieczeństwa jest zachowana --- nigdy oba procesy nie będą jednocześnie w sekcji krytycznej. Mamy jednak niestety problem z żywotnością. Przypomnijmy założenie, że proces nie przebywa nieskończenie długo w sekcji krytycznej. Zatem po wyjściu z niej (które na pewno w końcu nastąpi) rozpocznie wykonanie własnych spraw. I tu pojawia się problem, bo o tym fragmencie programu nic założyć nie możemy. Jeśli proces utknie w tym fragmencie kodu (bo nastąpi błąd, zapętlenie itp.), to drugi z procesów będzie mógł wejść do sekcji krytycznej jeszcze co najwyżej raz. Kolejna próba zakończy się wstrzymaniem procesu w protokole wstępnym "na zawsze". Zatem przedstawione rozwiązanie nie ma własności żywotności. Inną wadą tego rozwiązania jest zbyt "ścisłe powiązanie" ze sobą procesów. Muszą one korzystać z sekcji krytycznej na zmianę, a przecież potrzeby obu procesów mogą być różne. Jeśli ponadto działają one z różną "szybkością" (bo na przykład program znajdujący się we własnych sprawach jednego z nich wykonuje się dłużej niż własne sprawy drugiego), to proces "szybszy" będzie równał tempo pracy do wolniejszego.
Druga próba rozwiązania
Spróbujmy podejść do problemu w inny sposób. Wprowadźmy dwie logiczne zmienne globalne: jest1 oznaczającą, że proces P1 jest w sekcji krytycznej i analogiczną zmienną jest2 dla procesu P2. Przed wejściem do sekcji krytycznej proces sprawdza, czy jego rywal jest już w sekcji krytycznej. Jeśli tak, to czeka. Gdy sekcja krytyczna się zwolni, proces ustawi swoją zmienną na true sygnalizując, że jest w sekcji, po czym wejdzie do niej.
var jest1: boolean := false; jest2: boolean := false; | |
process P1;
begin
while true do
begin
własne_sprawy;
while jest2 do {nic};
jest1 := true;
sekcja_krytyczna;
jest1 := false;
end
end;
|
process P2;
begin
while true do
begin
własne_sprawy;
while jest1 do {nic};
jest2 := true;
sekcja_krytyczna;
jest2 := false;
end
end;
|
Zauważmy, że to rozwiązanie nie uzależnia już procesów od siebie. Jeśli jeden z nich nie chce korzystać z sekcji krytycznej lub awaryjnie zakończy swoje działanie we własnych sprawach, to drugi może swobodnie wchodzić do rejonu krytycznego, ile razy zechce.
- Ćwiczenie (ukrywajka)
- Czy to rozwiązanie jest
- bezpieczne?
- żywotne?
Nie ma też problemu z żywotnością. Jeśli pierwszy proces utknął w pętli w protokole wstępnym, to drugi proces musi znajdować się gdzieś między przypisaniem jest2 := true a przypisaniem jest2 := false . Po skończonym czasie wyjdzie z sekcji krytycznej i ustawi swoją zmienną jest2 na false pozwalając pierwszemu procesowi wyjść z jałowej pętli i wejść do sekcji krytycznej. Niestety, przy pewnych złośliwych przeplotach może się zdarzyć, że do rejonu krytycznego wejdą oba procesy.
- Ćwiczenie (ukrywajka)
- Wskaż taki scenariusz numerując kolejne wykonywane fragmenty procesów.
Oto scenariusz (przeplot), który wprowadza oba procesy do sekcji krytycznej:
process P1;
1: własne_sprawy;
2: while jest2 do {nic};
5: jest1 := true;
6: sekcja_krytyczna;
|
process P2;
3: własne_sprawy;
4: while jest1 do {nic};
7: jest2 := true;
8: sekcja_krytyczna;
|
Przeanalizujmy wartości zmiennych jest1 oraz jest2 po kolejnych krokach wykonania tego programu
| Krok | jest1 | jest2 |
|---|---|---|
| 1 | false | false |
| 2 | false | false |
| 3 | false | false |
| 4 | false | false |
| 5 | true | false |
| 6 | true | true |
Jak widać w krokach 2 i 4, gdy procesy sprawdzają warunki pętli zmienne mają jeszcze wartość false. Przyczyną takiej sytuacji jest zbyt późne ustawienie zmiennych logicznych. Proces już "prawie" był w sekcji krytycznym (bo przeszedł przez wstrzymującą go pętlę i nic go teraz nie może już powstrzymać), a jeszcze nie poinformował (tj. nie ustawił swojej zmiennej jest) o tym, że jest w sekcji krytycznej.
Ponieważ pokazaliśmy istnienie przeplotu, który prowadzi do błędnej sytuacji, więc zgodnie z definicją poprawności (musi być "dobrze" dla każdego przeplotu) stwierdzamy, że powyższy program jest niepoprawny. Zauważmy jednak, że gdyby sprawdzenie warunku w pętli oraz zmiana wartości zmiennej były niepodzielne, to takiego złego scenariusza nie dałoby się pokazać. Tyle tylko, że zagwarantowanie niepodzielności oznacza stworzenie sekcji krytycznej, a to jest właśnie problem, który rozwiązujemy.
Trzecia próba
Ponieważ zmiana wartości zmiennych globalnych w poprzednim rozwiązaniu została dokonana zbyt późno, więc spróbujmy zmienić kolejność czynności i ustawmy najpierw zmienne logiczne, a potem dopiero próbujmy przejść przez pętle. Teraz zmienne logiczne oznaczają chęć wejścia do sekcji krytycznej:
var chce1: boolean := false; chce2: boolean := false; | |
process P1;
begin
while true do
begin
własne_sprawy;
chce1 := true;
while chce2 do {nic};
sekcja_krytyczna;
chce1 := false;
end
end;
|
process P2;
begin
while true do
begin
własne_sprawy;
chce2 := true;
while chce1 do {nic};
sekcja_krytyczna;
chce2 := false;
end
end;
|
- Ćwiczenie (ukrywajka)
- Czy to rozwiązanie jest
- bezpieczne?
- żywotne?
Tym razem mamy program bezpieczny. Faktycznie w rejonie krytycznym może znajdować się co najwyżej jeden proces. Ale brakuje żywotności!
- Ćwiczenie (ukrywajka)
- Wskaż scenariusz pokazujący brak żywotności.
Oto scenariusz (przeplot), który doprowadza do sytuacji, gdy oba procesy chcą wejść do sekcji krytycznej, a nie mogą:
process P1;
1: własne_sprawy;
2: chce1 := true;
5: while chce2 do {nic};
|
process P2;
3: własne_sprawy;
4: chce2 := true;
6: while chce1 do {nic};
|
W krokach 5 i 6 oba procesy sprawdzają warunki pętli, które są prawdziwe, bo wcześniej zmienne chce zostały ustawione na true.
- Test wyboru
- Przedstawiony tu scenariusz prowadzi do:
- zagłodzenia
- zakleszczenia
Otrzymane rozwiązanie jest zatem znowu niepoprawne!
Czwarta próba
Można próbować ratować sytuację zmuszając procesy do chwilowej rezygnacji z wejścia do sekcji i ustąpienia pierwszeństwa rywalowi:
var chce1: boolean := false; chce2: boolean := false; | |
process P1;
begin
while true do
begin
własne_sprawy;
chce1 := true;
while chce2 do
begin
chce1 := false;
chce1 := true;
end;
sekcja_krytyczna;
chce1 := false;
end
end;
|
process P2;
begin
while true do
begin
własne_sprawy;
chce2 := true;
while chce1 do
begin
chce2 := false;
chce2 := true;
end;
sekcja_krytyczna;
chce2 := false;
end
end;
|
- Test wyboru
- Ten program
- jest bez sensu --- po co zmieniać wartość zmiennej na <false> jeśli za chwilę przywraca się jej wartość true
- ma własność bezpieczeństwa i żywotności
- ma własność bezpieczeństwa, ale nie żywotności
- ma własność żywotności, ale nie bezpieczeństwa
- byłby poprawny, gdybyśmy mogli zatrzymać wykonanie procesów w pętli while na jakiś krótki czas
Choć program jest bezpieczny, to jednak niestety znów istnieje (bardzo) złośliwy przeplot, który powoduje brak żywotności.
- Ćwiczenie (ukrywajka)
- Znajdź go!
Oto szukany przeplot. Po kroku 10 wykonujemy ponownie krok 5 i tak w pętli nieskończonej:
var chce1: boolean := false; chce2: boolean := false; | |
process P1;
1: własne_sprawy;
2: chce1 := true;
5: while chce2 do
begin
6: chce1 := false;
7: chce1 := true;
end;
|
process P2;
3: własne_sprawy;
4: chce2 := true;
8: while chce1 do
begin
9: chce2 := false;
10: chce2 := true;
end;
|
- Test wielokrotnego wyboru
- Co sądzisz o tym przeplocie:
- W praktyce jest bardzo mało prawdopodobne, żeby procesy wykonywały poszczególne instrukcje w nieskończoność w takiej kolejności
- W związku z powyższym program jest poprawny
- Nie można uznać tego programu za poprawny
Ten program jest niepoprawny. Nie pomoże argumentacja, że błędny przeplot jest "w zasadzie" nieprawdopodobny. Zgodnie z definicją poprawności, skoro istnieje scenariusz powodujący brak żywotności, to program jest niepoprawny.
Piąta próba rozwiązania. Algorytm Petersena
Poprawne rozwiązanie znane pod nazwą algorytmu Petersena jest sprytnym połączeniem PWR_Cwiczenia_1#Pierwsza_próba_rozwiązania z przedostatnim. Utrzymujemy zmienne {\tt chce1} i {\tt chce2}, które oznaczają chęć wejścia procesu do rejonu krytycznego. W razie gdy oba procesy chcą wejść do rejonu krytycznego rozstrzygamy konflikt za pomocą zmiennej {\tt ktoczeka}:
