Programowanie współbieżne i rozproszone/PWR Ćwiczenia 1: Różnice pomiędzy wersjami
| Linia 34: | Linia 34: | ||
języka programowania. | języka programowania. | ||
; Ćwiczenie | ; Ćwiczenie | ||
: Odpowiedz na poniższe pytania przed przystąpieniem do dalszej części ćwiczenia. | : 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]]. | Jeśli masz kłopoty ze znalezieniem odpowiedzi przeczytaj jeszcze raz [[fragment wykładu]]. | ||
| Linia 62: | Linia 62: | ||
zmienne modyfikować lub odczytywać. </div></div> | zmienne modyfikować lub odczytywać. </div></div> | ||
; Ćwiczenie | ; Ćwiczenie | ||
: Odpowiedz na poniższe pytania przed przystąpieniem do dalszej części ćwiczenia. | : 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]]. | Jeśli masz kłopoty ze znalezieniem odpowiedzi przeczytaj jeszcze raz [[ ten fragment wykładu]]. | ||
Wersja z 12:51, 19 lip 2006
Zadanie 1
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
- 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?
- Ćwiczenie
- 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?
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 rozwiązania
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 rozwiązania
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.
Algorytm Petersena
Poprawne rozwiązanie znane pod nazwą algorytmu Petersena jest sprytnym połączeniem pierwszego rozwiązania z przedostatnim. Utrzymujemy zmienne chce1 i chce2, które oznaczają chęć wejścia procesu do sekcji krytycznej. Gdy oba procesy chcą wejść do sekcji krytycznej rozstrzygamy konflikt za pomocą zmiennej kto_czeka.
- Ćwiczenie (ukrywajka lub jesli czas pozwoli Java script)
- Spróbuj zapisać algorytm Petersena
Java skrypt mógłby zawierać elementy algorytmu (przypisania, if, while, and) z których można by skonstruować algorytm i oceniac poprawnosc rozwiazania wskazujac na ewentualne braki zywotnosci, czy bezpieczeństwa.
Oto poprawne rozwiązanie zadania:
var chce1: boolean := false; chce2: boolean := false; kto_czeka: 1..2 := 1; | |
process P1;
begin
while true do
begin
własne_sprawy;
chce1 := true;
kto_czeka := 1;
while chce2 and (kto_czeka = 1) do {nic};
sekcja_krytyczna;
chce1 := false;
end
end;
|
process P2;
begin
while true do
begin
własne_sprawy;
chce2 := true;
kto_czeka := 2;
while chce1 and (kto_czeka = 2) do
sekcja_krytyczna;
chce2 := false;
end
end;
|
Przypomnijmy, że
- nie zakładamy atomowości (niepodzielności) poszczególnych instrukcji (w szczególności wyliczanie złożonych warunków logicznych nie musi odbywać się atomowo),
- ale zakładamy istnienie arbitra pamięci (może dojść do jednoczesnej próby zmiany wartości zmiennej kto_czeka)
Zauważmy, że w sytuacji, gdy tylko jeden proces rywalizuje o dostęp do sekcji krytycznej, to będzie on mógł do woli z niej korzystać, bo zmienna chce jego rywala ma cały czas wartość false. Dzięki temu unikamy ścisłego powiązania procesów, jak było to w rozwiązaniu pierwszym. Z drugiej strony, gdy oba procesy ciągle chcą korzystać z sekcji krytycznej, robią to na zmianę.
- Zadanie
Przeanalizuj algorytm Petersona pod kątem zmiany kolejności wykonywanych instrukcji:
- Czy można zamienić kolejność przypisań przed pętlą while?
- Czy można umieścić zmianę wartości zmiennej kto_czeka po wyjściu z sekcji krytycznej?
- Czy można zamienić kolejność sprawdzania warunków w pętli while?
- Czy można zainicjować zmienną kto_czeka na inne wartości?
- A zmienne chce1 i chce2?
Rozwiązania przedstaw prowadzącemu wraz z uzasadnieniem.
Algorytm Petersena dla dwóch procesów. Podsumowanie.
Algorytm Petersena w przedstawionej tu wersji ma dwie ważne wady:
- aktywne oczekiwanie
- ograniczenie do dwóch procesów
Aktywne oczekiwanie polega na tym, że proces, który nie może kontynuować wykonania i musi poczekać, robi to angażując czas procesora, poprzez ciągłe sprawdzanie pewnych warunków. Taki sposób oczekiwania w dalszym toku tych zajęć będzie niedopuszczalny. Jednak aby zatrzymać wykonywanie procesu w sposób nie angażujący procesora, jest potrzebne wsparcie systemu operacyjnego i pewne mechanizmy udostępniane przez system. Ponieważ dzisiaj zakładaliśmy brak jakichkolwiek mechanizmów synchronizacyjnych, więc aktywne oczekiwanie było jedyną metodą zatrzymania procesu.
Z ograniczeniem do dwóch procesów można sobie poradzić.
Zadanie 2 (opcjonalne)
Rozwiązać problem wzajemnego wykluczania dla n procesów. Wartość n jest przy tym stałą równą co najmniej 2.
Rozwiązanie
Rozwiązanie uzyskuje się przez naturalne uogólnienie algorytmu Petersena. Zauważmy, że wykonanie następującego fragmentu kodu przez n procesów:
process P (i: 1..n);
begin
while true do
begin
własne_sprawy;
chce[i] := true;
kto_czeka := i;
while chce[j] and (kto_czeka = i) do {nic};
przy zaciętej rywalizacji o dostęp do sekcji krytycznej spowoduje zatrzymanie jednego z nich w pętli while. Czekać będzie ten, który jako ostatni wykona przypisanie na zmienną kto_czeka. Zatem pętla zadziała jak bariera zatrzymująca jeden proces. Umieszczenie n-1 takich barier spowoduje zatrzymanie n-1 procesów i wpuszczenie do sekcji krytycznej co najwyżej jednego z nich.
Oczywiście konflikt przy każdej kolejnej barierze powinien być rozstrzygany przez inną zmienną, zatem kto_czeka powinno być teraz tablicą indeksowaną numerami barier. Zmienna chce jest tablicą (indeksowaną numerami procesów) i pamiętającą już nie tylko informacje o tym, czy proces chce wejść do rejonu krytycznego, ale o tym, do której bariery doszedł (lub 0, jeśli proces nie uczestniczy w wyścigu do rejonu krytycznego). Otrzymujemy w ten sposób schemat:
process P (i: 1..n);
begin
while true do
begin
własne_sprawy;
for bariera := 1 to n - 1 do
begin
chce[i] := true;
kto_czeka[bariera] := i;
while chce[j] >= bariera and (kto_czeka[bariera] = i) do {nic};
end
sekcja krytyczna;
chce[i] := 0;
end
end
Wady tej wersji algorytmu Petersena to:
- Aktywne oczekiwanie.
- Znana z góry liczba procesów
- Duża złożoność (a więc i koszt) protokołu wstępnego.
