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.