Programowanie współbieżne i rozproszone/PWR Wykład 4

From Studia Informatyczne

Spis treści

Komunikacja synchroniczna

Przypomnijmy podstawowe cechy komunikacji synchronicznej. Procesy synchronizują ze sobą: nadawca czeka z wysłaniem do momentu, aż odbiorca będzie gotowy do odbioru i na odwrót: odbiorca jest wstrzymywany na instrukcji odbioru do chwili, aż sterowanie w nadawcy dojdzie do instrukcji wysłania.

Czasem trudno jest jednak wprowadzić jednoznaczne rozgraniczenie na proces nadający i odbierający, gdyż w czasie pojedynczej synchronizacji procesów może dojść do wymiany komunikatów w obie strony. Tak właśnie dzieje się to w Adzie.

Spotkania (randki) w Adzie

Mechanizm synchronizacyjny udostępniany przez Adę to tzw. spotkania albo randki. W spotkaniu uczestniczą dwa (lub więcej) procesy, które w Adzie noszą nazwę zadań. Zacznijmy od omówienia randki między dwoma zadaniami.

Zadanie aktywne i pasywne

Spośród zadań uczestniczących w randce jedno jest zadaniem aktywnym, a drugie zadaniem pasywnym. Zadanie aktywne inicjuje randkę, ale w czasie jej trwania nie robi nic. Zadanie pasywne jest zadaniem, które udostępnia pewne wejścia. Wejścia te mogą być wywoływane przez zadanie aktywne, które chce zainicjować randkę. Gdy dojdzie do randki, zadanie pasywne zajmuje się jej obsługą, wykonując określony fragment programu, podczas gdy zadanie aktywne jest wstrzymywane w oczekiwaniu na zakończenie randki.

Zadania w Adzie składają się z dwóch części. Pierwsza część to tzw. specyfikacja zadania. Specyfikacja określa jakie wejścia są udostępniane przez zadanie i jakie są ich argumenty. Właściwa treść zadania jest określona w osobnym fragmencie kodu.

Zacznijmy zatem od specyfikacji zadania.

Wejścia

Każde zadanie może udostępniać na zewnątrz pewne wejścia. Są to jakby "procedury", które mogą być wywołane przez inne zadania i realizowane "w ich imieniu" przez zadanie bierne. Każde wejście ma nazwę i, jeśli jest taka potrzeba, parametry. Te same zasady dotyczą zresztą procedur. Każdy parametr w Adzie specyfikuje się, podając jego identyfikator, typ oraz sposób przekazania. Są trzy sposoby przekazywania parametrów w Adzie:

  1. Parametry wejściowe to parametry określane za pomocą słowa kluczowego in. Ich wartości mogą być w trakcie spotkania (lub wewnątrz procedury/funkcji) odczytywane, ale nie można nic na nie zapisać. W szczególności nie mogą więc występować po lewej stronie instrukcji przypisania.
  2. Parametry wyjściowe są określane za pomocą słowa kluczowego out. Można na nie zapisywać wewnątrz procedury, ale ich wartości początkowe są nieokreślone.
  3. Parametry wejściowo-wyjściowe specyfikowane za pomocą słowa kluczowego inout. Są one połączeniem parametrów wejściowych i wyjściowych. Są one odpowiednikiem parametrów przekazywanych przez zmienną z języka Pascal.

Kierunek przekazywania parametrów jest zawsze określany z punktu widzenia specyfikowanego procesu. Przypuśćmy na przykład, że chcemy rozwiązać problem producentów i konsumentów. Chcemy, aby producenci umieszczali wyprodukowane dane w buforze, skąd pobierają je konsumenci. Pierwsze pytanie, na jakie musimy odpowiedzieć to jak zaimplementować bufor? Zastosujemy dość standardową technikę w modelu rozproszonym, wprowadzając dodatkowy proces. Proces ten o nazwie Bufor będzie procesem biernym zarówno przy komunikacji z producentem, jak i konsumentem. Wynika to z tego, że bufor nie ma żadnej możliwości stwierdzenia, kiedy przechowywana przez niego informacja będzie potrzebna konsumentowi, ani kiedy ma skomunikować się z producentem w celu odebrania od niego kolejnej porcji danych. To producent i konsument są stronami inicjującymi spotkanie.

Wyspecyfikujmy więc zadanie Bufor z dwoma wejściami:

  • Weź do wkładania do niego danych i
  • Daj do pobierania danych.

Odpowiedni fragment kodu wygląda tak:

task Bufor is
  entry Weź (x: in Integer);
  entry Daj (x: out Integer);
end Bufor;

Zauważmy, że parametr wejścia Weź jest wejściowy, bo to wywołujący przekazuje liczbę całkowitą do włożenia do bufora. Analogicznie parametr wejścia Daj jest wyjściowy, bo za jego pomocą proces aktywny dostaje liczbę z bufora.

Semantyka randki

Jak wygląda randka w Adzie? Aby w ogóle do niej doszło, proces aktywny musi wywołać pewne wejście udostępniane przez proces pasywny. Przykładowo, konsument wywołuje wejście Daj bufora za pomocą instrukcji:

Bufor.Daj (x)

przy czym x jest pewną zmienną lokalną konsumenta, na której zostanie zapisana odczytana z bufora liczba.

Wywołanie wejścia zadania biernego powoduje wstrzymanie procesu wywołującego aż do chwili, gdy sterowanie w procesie biernym dotrze do specjalnej instrukcji akceptującej. Proces wywołujący jest przy tym wstrzymywany w kolejce związanej z danym wejściem. Gdy sterowanie w zadaniu biernym dochodzi do instrukcji akceptującej --- jej składnię omówimy za chwilę --- dochodzi do randki między zadaniem biernym a zadaniem aktywnym znajdującym się na początku kolejki zadań oczekujących na danym wejściu. Należy od razu zwrócić uwagę, że może zdarzyć się także inny scenariusz. Sterowanie w procesie biernym może dojść do instrukcji akceptującej wejście, zanim zostanie ono wywołane przez jakiekolwiek zadanie aktywne. Jak przystało na model synchroniczny, zadanie bierne jest wtedy również wstrzymywane do chwili wywołania wejścia przez jakieś zadanie.

Sama randka ma następujący przebieg:

  1. Zadanie aktywne przekazuje do zadania biernego wartości wszystkich parametrów wejściowych i wejściowo-wyjściowych.
  2. Zadanie aktywne zostaje wstrzymane do czasu zakończenia randki.
  3. Zadanie bierne wykonuje instrukcje stanowiące treść instrukcji akceptującej.
  4. Po zakończeniu instrukcji akceptującej zadanie bierne przekazuje do zadania aktywnego wartości wszystkich parametrów out oraz inout i przechodzi do kolejnej instrukcji za instrukcją akceptującą.
  5. Po odebraniu wartości parametrów wyjściowych zadanie aktywne wznawia swoje działanie.

Z powyższego opisu wynika, że zadanie aktywne po przekazaniu parametrów do zadania biernego pozostaje bezczynne aż do końca randki. Na taki mechanizm można więc patrzeć jak na zwykłe wywołanie procedury, z tym że procedura jest wykonywana nie przez wywołującego, lecz przez inny proces. Zadanie aktywne to wywołujący, który po wywołaniu czeka aż zadanie bierne wykona treść procedury i przekaże wartości wynikowe i dopiero wznawia wykonanie.

Kluczową instrukcją w opisywanym mechanizmie jest instrukcja akceptująca. Ma ona następującą składnię:

accept <nazwa wejścia> (<parametry>) do
  <ciąg instrukcji>;
end <nazwa wejścia>;

W trakcie spotkania wykonują się wszystkie instrukcje między accept a end. Jeśli ten ciąg jest pusty, to można użyć uproszczonej składni pisząc:

accept <nazwa wejścia>; 

Popatrzmy jak taki mechanizm można wykorzystać do realizacji wzajemnego wykluczania dwóch procesów. Napiszmy proces Serwer z dwoma wejściami:

  • Chce wywoływane przez proces, który chce wejść do sekcji krytycznej oraz
  • Zwalnia wywoływane przez proces, który opuszcza sekcję krytyczną.
task Serwer is
  entry Chce;
  entry Zwalnia;
end Serwer;
task body Serwer is
  loop
    accept Chce;
    accept Zwalniam;
  end loop;
end Serwer;

Jak widać serwer działa w pętli nieskończone, którą w Adzie zapisuje się w postaci loop ... end loop. W pętli na przemian wykonuje instrukcję akceptującą wejście Chce i instrukcję akceptującą wejście Zwalniam. W efekcie serwer najpierw chce koniecznie zaakceptować proces wywołujący wejście Chce. Gdy jednak już dojdzie do randki (pustej), to serwer przechodzi do kolejnej instrukcji, którą jest accept Zwalniam. Czeka zatem na tej instrukcji aż ktoś --- a może to być jedynie proces, który zwalnia sekcję krytyczną, wywoła wejście Zwalniam nie reagując na wywoływanie wejścia Chce.

Oczekiwanie selektywne

Czasami zachodzi potrzeba zawieszania zadania przyjmującego w oczekiwaniu na zajście jednego z wielu zdarzeń. Stosujemy wtedy specjalną instrukcję select, której składnia jest następująca:

select
  when warunek1 => accept wejście1 do 
                                 instrukcje-w-trakcie-randki;
                               end wejście1;
                               instrukcje-poza-randką;
or 
  when warunek2 => accept wejście2 do 
                                 instrukcje-w-trakcie-randki;
                               end wejście2;
                               instrukcje-poza-randką;
  ...
else
  instrukcje;
end select;

Poszczególne elementy tej konstrukcji, oddzielane od siebie za pomocą słów kluczowych or nazywa się gałęziami. Ostatnia gałąź (po słowie kluczowym else) jest opcjonalna i można ją pominąć. Każda gałąź składa się z dozoru, instrukcji accept oraz instrukcji wykonywanych poza randką. Każdy z tych trzech elementów, z wyjątkiem instrukcji akceptującej, jest opcjonalny i w pewnych okolicznościach można go pominąć. I tak, dozór zbudowany ze słowa kluczowego when warunku logicznego oraz strzałki => pomija się, jeśli warunek jest zawsze prawdziwy (czyli jest nim po prostu true). Instrukcję poza ranką pomija się jeśli jest ona pusta.

Semantyka

Działanie instrukcji select omówimy przyjmując najpierw, że po else nie ma żadnych instrukcji. Jej wykonanie przebiega wówczas w następujących krokach:

  1. Szukamy otwartych gałęzi. Gałąź jest otwarta, jeśli występujący w niej dozór jest prawdziwy. Zauważmy, że gałęzie, w których pominięto dozór, są zawsze prawdziwe. Jeśli nie ma gałęzi otwartych, to instrukcja wyboru powoduje błąd.
  2. Sprawdzamy, czy są zadania oczekujące w kolejkach związanych z wejściami występującymi w instrukcjach accept otwartych gałęzi. Przypomnijmy, że instrukcja accept jest obowiązkowa w każdej gałęzi --- nie można jej pominąć. Co więcej występuje ona na początku każdej gałęzi (ewentualnie bezpośrednio po dozorze).
  3. Jeśli jest proces oczekujący na wejściu w pewnej otwartej gałęzi, to rozpoczyna się randka z pierwszym zadaniem w niedeterministycznie wybranej gałęzi. Podkreślmy: zadania oczekujące na randkę zbierają się na konkretnym wejściu formując kolejkę prostą. Spośród zadań oczekujących na tym samym wejściu jako pierwsze zostanie obsłużone to, które zgłosiło się jako pierwsze. Jednak jeśli są procesy oczekujące na różnych wejściach umieszczonych w otwartych gałęziach instrukcji select, to decyzja o tym, która gałąź się wykona jest podejmowana niedeterministycznie.
  4. Jeśli wszystkie kolejki w gałęziach otwartych są puste, to zadanie przyjmujące zostaje wstrzymane do chwili wywołania przez pewne zadanie aktywne wejścia w otwartej gałęzi. Wtedy rozpoczyna się randka z tym zadaniem.
  5. W trakcie randki wykonywane są instrukcje znajdujące się wewnątrz instrukcji accept obsługującej randkę. Instrukcje te są wykonywane jak zwykle przez zadanie przyjmujące, a zadanie wywołujące w tym czasie jest wstrzymywane.
  6. Gdy sterowanie w zadaniu przyjmującym dojdzie do instrukcji end kończącej randkę, zadanie aktywne jest wznawiane, a zadanie przyjmujące wykonuje instrukcje poza randką. Zwróćmy uwagę, że o ile podczas wykonywania instrukcji znajdujących się wewnątrz instrukcji accept zadanie aktywne jest wstrzymywane, to w trakcie wykonywania instrukcji poza randką zadanie aktywne już się wykonuje.
  7. Instrukcja select kończy się po wykonaniu instrukcji znajdujących się w jednej gałęzi.

W przypadku obecności części z else działanie instrukcji select jest nieco inne. Różnice w stosunku do powyższego opisu są przy tym następujące:

  1. Jeśli nie ma otwartych gałęzi, to wykonują się od razu instrukcje po else. Sytuacja taka nie powoduje tym razem błędu.
  2. Jeśli są otwarte gałęzie, ale nie ma oczekujących procesów w żadnej z nich, to zadanie nie jest wstrzymywane, ale także wykonuje się część po instrukcji else.

Niedeterminizm

W przedstawionym powyżej opisie działania instrukcji select występuje ważne zjawisko: niedeterminizm. Jeśli są procesy oczekujące na wejściach znajdujących się w różnych gałęziach otwartych, to rozpoczynamy randkę na wejściu z niedeterministycznie wybranej gałęzi otwartej. Należy jednak pamiętać, że niedetermizm dotyczy wyboru gałęzi, a nie procesu oczekującego w kolejce związanej z wejściem występującym w tej gałęzi.

Niedeterminizm, o którym mowa, nie jest jednak niczym nieograniczony. Zachowujemy, tak jak było to w przypadku Lindy, warunek sprawiedliwości. Zakładamy mianowicie, że jeśli instrukcja select jest wykonywana nieskończenie wiele razy (na przykład w pętli) oraz pewna gałąź z niepustą kolejką jest otwarta nieskończenie wiele razy, to w końcu zostanie ona wybrana do wykonania. Takie założenia pozwala uzyskać żywotność rozwiązań zapisanych w Adzie.

Zliczanie oczekujących

Omawiając instrukcję select należy zwrócić uwagę na jeszcze jeden element. Otóż w Adzie istnieje możliwość sprawdzenia, ile procesów oczekuje na danym wejściu. Służy do tego konstrukcja o następującej składni:

wejście'count

Będziemy mówić, że count jest atrybutem wejścia, przekazującym liczbę procesów aktualnie oczekujących na tym wejściu.

Przykłady

Producenci i konsumenci

Oto zapis w Adzie rozwiązania problemu producentów i konsumentów. Wejścia są udostępniane jedynie przez proces implementujący bufor (cykliczny i ograniczony). Jedno Weź służy do wstawiania porcji do bufora, a drugie Daj do odbierania ich z bufora.

task Bufor is
  entry Weź (x: in Integer);
  entry Daj (x: out Integer);
end Bufor;

Procesy producenta i konsumenta nie udostępniają wejść. Ponieważ chcemy mieć dużo producentów (niech ich liczba wynosi P, gdzie P jest pewną z góry ustaloną stałą), i dużo (K) konsumentów, więc uwzględniamy to w specyfikacji zadań w następujący sposób:

 task Producent (1..P) is
 end Producent;
 task Konsument (1..K) is
 end Konsument;

Zapiszmy najpierw treść producenta i konsumenta:

task body Producent is 
   liczba: Integer;
  loop
    produkuj (liczba);
    Bufor.Weź (liczba);
  end loop
end Producent;
task body Konsument is 
   liczba: Integer;
  loop
    Bufor.daj (liczba);
    konsumuj (liczba);
  end loop
end Konsument;

Treść procesu bufor jest nieco bardziej złożona. Porcje będziemy pamiętać w tablicy indeksowanej od 0 do B-1, gdzie B jest pewną stałą oznaczającą pojemność bufora. Będziemy ponadto pamiętać pozycję w tablicy, na której znajduje się pierwsza liczba do wyjęcia oraz liczbę elementów w buforze:

task body Bufor is
  pierwsza: integer := 0;
  ile : integer := 0;
  buf: array [0..B-1] of Integer;
 

Bufor działa w pętli nieskończonej. Ponieważ nie da się przewidzieć w jakiej kolejności będą nadchodzić zlecenia od producenta i konsumenta bufor powinien być prawie zawsze gotowy do komunikacji z każdym z nich. No właśnie: prawie zawsze. Nie można bowiem przyjąć kolejnej porcji od producenta, jeśli w buforze nie ma już wolnego miejsca oraz nie można wysłać nic konsumentowi, jeśli bufor jest pusty. Daje to następujący fragment kodu:

 loop
   select
     when ile <> 0 => 
       accept Daj (x: out Integer) do
         x := buf[pierwsza];
         ile := ile - 1;
         pierwsza := (pierwsza + 1) mod B; 
       end Daj;
   or 
     when ile <> B => 
       accept Weź (x: in Integer) do
         buf[(pierwsza+ile) mod B] := x;
         ile := ile + 1;
       end Weź;
   end select;
 end loop;
end Bufor;    

Zwróćmy uwagę, że ten sam efekt można uzyskać zmieniając nieco kolejność instrukcji:

 loop
   select
     when ile <> 0 => 
       accept Daj (x: out Integer) do
         x := buf[pierwsza];
       end Daj;
       ile := ile - 1;
       pierwsza := (pierwsza + 1) mod B; 
   or 
     when ile <> B => 
       accept Weź (x: in Integer) do
         buf[(pierwsza+ile) mod B] := x;
       end Weź;
       ile := ile + 1;
   end select;
 end loop;
end Bufor;    

Powyższe dwa programy mają tę samą funkcjonalność, oba są poprawne, a różnią się jednym szczegółem. W pierwszym modyfikacja wszystkich zmiennych bufora odbywa się podczas nieaktywności producenta/konsumenta. W drugim producent i konsument są wstrzymywani jedynie na czas przekazywania wyprodukowanej porcji. Modyfikacja zmiennych bufora odbywa się już po wznowieniu działania producenta/konsumenta, czyli poza randką. Otrzymujemy w ten sposób rozwiązanie bardziej efektywne.

Pięciu filozofów. Wersja 1.

Przyjrzyjmy się teraz rozwiązaniu problemu pięciu filozofów.

Wzajemne wykluczanie

Select po stronie aktywnej

Spotkania z udziałem wielu procesów

=== Producenci i konsumenci w wersji bez bufora

Pięciu filozofów. Wersja 2.

RPC jako implementacja spotkań