Programowanie współbieżne i rozproszone/PWR Ćwiczenia 1

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.

1. Czy protokoły wstępne i końcowe można pozostawić puste?
2. Co oznacza bezpieczeństwo w przypadku tak sformułowanego zadania?
3. A żywotność?
4. 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.

1. 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

1. Formułując problem wzajemnego wykluczania zakłada się, że:
   1. Każdy proces, który wszedł do sekcji krytycznej w skończonym czasie ją opuści.
   2. Proces może przebywać w sekcji krytycznej nie dłużej niż ustalony z góry czas.
   3. Proces nie może zakończyć się w sekcji krytycznej.
   4. Proces może się zakończyć w sekcji krytycznej ale tylko w sposób poprawny.
2. Proces, który rozpoczął wykonywanie własnych_spraw:
   1. musi w skończonym czasie zakończyć je i przejść do protokołu wstępnego.
   2. może zakończyć swoje działanie na skutek błędu.
   3. 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:

1. Czy ma ono własność bezpieczeństwa?
2. Czy ma ono własność żywotność?
3. 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<\tt>, to drugi może swobodnie wchodzić do rejonu krytycznego, ile razy zechce.

Ćwiczenie (ukrywajka)

Czy to rozwiązanie jest

1. bezpieczne?
2. ż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

1. bezpieczne?
2. ż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.