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:

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.