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

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.

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?

Odpowiedź

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

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?

Odpowiedź

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, to drugi może swobodnie wchodzić do rejonu krytycznego ile razy zechce.

Ćwiczenie (ukrywajka)

Czy to rozwiązanie jest

1. bezpieczne?
2. żywotne?

Odpowiedź

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.

Odpowiedź

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 krytycznej (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

1. bezpieczne?
2. żywotne?

Odpowiedź

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:

1. zagłodzenia
2. 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

1. jest bez sensu --- po co zmieniać wartość zmiennej na <false> jeśli za chwilę przywraca się jej wartość true
2. ma własność bezpieczeństwa i żywotności
3. ma własność bezpieczeństwa, ale nie żywotności
4. ma własność żywotności, ale nie bezpieczeństwa
5. 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:

1. W praktyce jest bardzo mało prawdopodobne, żeby procesy wykonywały poszczególne instrukcje w nieskończoność w takiej kolejności;
2. W związku z powyższym program jest poprawny;
3. 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 poprawność rozwiązania, wskazując na ewentualne braki żywotnosci czy bezpieczeństwa.

Oto poprawne rozwiązanie zadania:

Algorytm Petersena

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:

1. Czy można zamienić kolejność przypisań przed pętlą while?
2. Czy można umieścić zmianę wartości zmiennej kto_czeka po wyjściu z sekcji krytycznej?
3. Czy można zamienić kolejność sprawdzania warunków w pętli while?
4. Czy można zainicjować zmienną kto_czeka na inne wartości?
5. 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 ${\mathrm{\exists }}_{j<>i}$ 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 ${\mathrm{\exists }}_{j<>i}$ 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.