Informatyka MIMUW

Pojęcie krotki i przestrzeni krotek

Inne podejście do asynchronicznego modelu komunikacji zaproponował w latach osiemdziesiątych Gelernter. Wprowadził on notację o nazwie Linda, która udostępnia tzw. przestrzeń krotek, czyli coś w rodzaju nieskończonego bufora, za pomocą którego porozumiewają się ze sobą procesy. Jest jedna wielka, globalna przestrzeń krotek. Procesy porozumiewają się ze sobą, umieszczając w przestrzeni krotek komunikaty i pobierając je z niej. Procesy nie muszą wiedzieć nic o sobie nawzajem, co więcej, mogą nie istnieć w tym samym czasie. Nadawca może odebrać komunikat od procesu, który już dawno zakończył swoje działanie.

Każdy komunikat przesyłany przez procesy to tzw. krotka.

Krotka

to ciąg (skończony), którego kolejnymi elementami są dane o określonych typach.

Przykładami krotek są:

• jednokrotki: (4), (3.14), ("żeton")
• pary: ('c', true), (5, 123)
• dłuższe krotki: (6, 'c', 3.14, "dane")

Każda krotka ma statycznie określoną długość. Nie może tworzyć krotek o dynamicznie zmienianej bądź wyliczanej długości. Typy poszczególnych elementów krotki mogą być dowolne typy proste lub typy złożone (tablice, rekordy). Nie ma jednak typu, którego wartościami byłyby krotki, więc krotka nie może być elementem krotki.

Sygnatura krotki

to ciąg, którego elementami są typy poszczególnych elementów krotki.

Sygnaturą krotki ('c', true, 3.14, "żeton") jest na przykład (char, boolean, real, string). W niektórych operacjach na przestrzeni krotek wymaga się podania sygnatury krotki.

Proste operacje na przestrzeni krotek

Linda nie jest tak naprawdę językiem programowania, ale raczej czymś w rodzaju biblioteki oferującej pewne operacje na przestrzeni krotek. Są to:

• Operacja wstawienia krotki t do przestrzeni krotek:

Output(t)

• Operacje odczytywania i obierania krotki o sygnaturze s:

Input (s) oraz Read (s)

• Nieblokujące wersje powyższych operacji w postaci funkcji logicznych:

Try_Input (s) oraz Try_Read (s)

Omówimy teraz po kolei powyższe operacji.

Wstawianie krotki

Ponieważ Linda jest rozproszonym mechanizmem asynchronicznym z nieograniczonym buforem, więc operacja wstawiania krotki do przestrzeni jest operacją nieblokującą. Ma ona postać

Output (t)

i w jej wyniku krotka t zostaje umieszczona w przestrzeni krotek. Jeśli taka krotka już się w niej znajdowała, to zostanie umieszczony kolejny egzemplarz takiej samej krotki. Przestrzeń krotek należy traktować jak multizbiór, a nie zwykły zbiór krotek . Przykładowa operacja Output ('c', "ala", 4, 3.14) wstawi do przestrzeni krotek krotkę ('c', "ala", 4, 3.14) o sygnaturze (char, string, integer, real).

Wyjmowanie krotki

Do wyjmowania krotki z przestrzeni krotek służą dwie procedury blokujące:

input(s).

Argumentem obu tej procedury jest sygnatura krotki, na przykład:

input (x:integer, c: char)

wyjmuje z przestrzeni krotek krotkę o sygnaturze integer, char. Jeśli w danej chwili krotki o podanej sygnaturze nie ma w przestrzeni krotek, to proces wykonujący procedurę Input jest wstrzymywany tak długo, aż żądana krotka pojawi się w przestrzeni krotek. Na skutek wykonania operacji Input z przestrzeni krotek jest usuwana jedna krotka o podanej sygnaturze, a poszczególne jej elementy są przypisywane na zmienne występujące w opisie sygnatury. W omawianym przykładzie pierwszy element krotki zostanie przypisany na zmienną x a drugi na zmienną c.

Jeśli w przestrzeni krotek jest wiele krotek o podanej sygnaturze, to wybór usuwanej krotki jest niedeterministyczny. Niedeterminizm ten jest jednak ograniczany zasadą sprawiedliwości: jeśli operacja Input z podaną sygnaturą jest wykonywana nieskończenie często, to w końcu każda krotka o tej sygnaturze zostanie wyjęta z przestrzeni krotek.

Podobna zasada obowiązuje przy budzeniu procesów oczekujących na operacji Input. Jeśli na krotkę o pewnej sygnaturze czeka ich wiele i krotka pojawi się w przestrzeni, to wznawiany jest któryś z oczekujących procesów. Nie można zatem zakładać, że oczekujące procesy są kolejkowane, ale można oczekiwać sprawiedliwości. Mamy gwarancję, że jeśli krotka pojawi się nieskończenie wiele razy w przestrzeni, to każdy z oczekujących procesów w końcu zostanie obudzony.

Odczytywanie krotki

Procedura Read jest operacją bardzo podobną do Input. Jedyna różnica polega na tym, że krotka nie jest usuwana z przestrzeni krotek. Podobnie jak w przypadku Input proces wykonujący Read oczekuje aż w przestrzeni zjawi się krotka o podanej sygnaturze. Również procesy oczekujące są budzone w sposób sprawiedliwy.

Zauważmy, że po pojawieniu się krotki o sygnaturze, na którą czekają procesy wykonujące Read, mogą zostać obudzone wszystkie procesy oczekujące, bo każdy z nich jedynie odczytuje krotkę z przestrzeni pozostawiając ją tam. Jeśli jednak na taką samą krotkę oczekują procesy i na operacji Read i na operacji Input, to wtedy na skutek niederministycznego wyboru budzonych procesów możliwe są różne sytuacje. Może zdarzyć się tak, że zostanie obudzony tylko jeden proces oczekujący na Input, może też obudzić się kilka (niekoniecznie wszystkie) procesy czekające na operacji Read, a po nich dopiero proces oczekujący na Input.

Wersje nieblokujące

Oprócz omówionych procedur, do wyjmowania/odczytywania krotek z przestrzeni krotek można wykorzystać dwie funkcje logiczne:

Try_Input(s) oraz Try_Read(s)

Funkcje te działają dokładnie tak jak ich blokujące odpowiedniki: Input oraz Read z tym, że jeśli krotki o podanej sygnaturze nie ma w przestrzeni krotek, to proces nie jest wstrzymywany, a funkcje przekazują natychmiast w wyniku wartość false. Jeśli udało się pobrać/odczytać krotkę, to wynikiem jest wartość true.

Wersji nieblokujących można używać do sprawdzania, czy krotka o podanej sygnaturze w danej chwili znajduje się w przestrzeni krotek. Należy jednak przy tym uważać. Fragment programu:

if Try_Read (x:integer) then
  Input (x: integer);

nie oznacza, że proces nie zostanie zatrzymany na operacji Input. W chwili wykonywania operacji Try_Read (x) w przestrzeni krotek mogła bowiem znajdować się jakaś krotka o sygnaturze (integer), ale zanim proces rozpoczął wykonanie Input, krotka ta mogą zostać usunięta przez inny wykonujący się współbieżnie proces.

Wybór selektywny

Istotnym rozszerzeniem omawianego mechanizmu jest możliwość wykonywania tzw. wyboru selektywnego. Polega on na możliwości wyspecyfikowania wartości konkretnych elementów krotki, którą chcemy wyjąć/odczytać z przestrzeni krotek. Przykładowo można zażyczyć sobie wyjęcia z przestrzeni krotek krotki o sygnaturze (integer, char, integer), której pierwszym elementem jest wartość 3. Odpowiednia instrukcja wygląda następująco:

Input (3, c:char, x: integer)

Zwróćmy uwagę na bardzo ważną rolę, jaką gra składnia w Lindzie. Porównajmy następujące wywołania procedury Input:

Ostatnie z nich jest żądaniem wyjęcia dowolnej krotki o sygnaturze (integer, char) i zapisania wartości poszczególnych składowych wyjmowanej krotki w zmiennych x oraz c. Pozostałe wywołania to wybór selektywny. W pierwszym przypadku chcemy wyjąć z przestrzeni krotek krotkę, której pierwszy element ma wartość taką jak aktualna wartość zmiennej x, a drugi element jest równy co do wartości zmiennej c. Drugie i trzecie wywołanie to wybór selektywny odpowiednio po drugiej i pierwszej współrzędnej. Na przykład Input (x: integer, c) oznacza wyjęcie z przestrzeni krotek krotki, której druga współrzędna ma wartość taką jak zmienna c, a pierwsza współrzędna jest dowolną liczbą całkowitą, którą zapamiętujemy w zmiennej x.

Wybór selektywny jest bardzo przydatny i upraszcza rozwiązanie wielu problemów synchronizacyjnych. Należy jednak pamiętać o tym, że tak naprawdę jest on dość ograniczony. Nie można na przykład bezpośrednio zrealizować wyjęcia z przestrzeni krotek krotki, której dane elementy spełniają dowolny warunek logiczny. Selektywość jest ograniczana jedynie do sprawdzania równości podanych elementów krotki.

Krotki dziurawe

W lindzie wprowadzone jeszcze jedno rozszerzenie. W przestrzeni krotek mogą znajdować się krotki "dziurawe". Dziura to "wartość" określonego typu, która "pasuje" do dowolnej innej wartości tego typu. Dziury będziemy w dalszej części oznaczać gwiazdką wraz z typem. Na przykład krotka:

(3, *: char, 'a', *:integer)

jest krotką o sygnaturze

(integer, char, char, integer)

zawierającą dwie dziury: na drugiej i czwartej pozycji. Taką krotkę można pobrać z przestrzeni krotek wykonując każdą z następujących operacji:

W tym drugim przypadku wartość zmiennej j jest nieokreślona. Zauważmy, że nawet krotki dziurawe mają jednoznacznie określoną sygnaturę, tj. każda dziura ma typ.

Do umieszczanie w przestrzeni krotek krotek z dziurą służy także procedura Output. W miejscu dziury podajemy po prostu sygnaturę (z nazwą zmiennej, która jednak nie ma tu znaczenia):

Output (3, c:char)

umieści w przestrzeni krotek krotkę, która na drugiej współrzędnej ma dziurę.

Przykłady

Projektując program współbieżny w Lindzie, będziemy zakładać, że procesy wchodzące w jego skład są jedynymi procesami korzystającymi z przestrzeni krotek. Metoda postępowania jest przy tym następująca:

1. Projektujemy postać wszystkich potrzebnych nam krotek: sygnaturę, znaczenie poszczególnych elementów.
2. Opisujemy początkową zawartość przestrzeni: jakie krotki, w jakiej liczbie.
3. Dopiero teraz przystępujemy do projektowania poszczególnych procesów.

Realizacja komunikacji między procesami za pomocą przestrzeni krotek

Spróbujmy zaprojektować schemat komunikacji między procesami za pomocą przestrzeni krotek. W tym celu przyjmijmy, że każdy proces ma jednoznaczny identyfikator typu integer. Załóżmy, że przestrzeń krotek jest początkowo pusta, a w trakcie działania procesów będą pojawiać się w niej krotki postaci:

(nadawca: integer, odbiorca: integer, kom: Komunikat)

przy czym definicja typu Komunikat wynika z konkretnego zastosowania.

1. Jeśli proces o identyfikatorze ID zechce wysłać do procesu o identyfikatorze ODB komunikat kom, to umieści w przestrzeni krotek krotkę:

   (ID, ODB, kom)

2. Proces o identyfikatorze ID odbiera komunikaty w sposób selektywny tak, aby docierały do niego jedynie komunikaty, których jest adresatem:

   Input (nad: integer, ID, kom: Komunikat)

3. Jeśli proces chce wysłać komunikat do dowolnego procesu, to umieszcza w przestrzeni krotek krotkę dziurawą:

   (ID: integer, *: integer, kom: Komunikat)

4. Rozgłaszanie, czyli wysłanie komunikatu do wszystkich procesów można zrealizować tak, że procesy odbierające wykonują Read zamiast Input. Pozostaje jednak wtedy problem z usunięciem komunikatu po odczytaniu go przez ostatni proces. Jeśli liczba procesów jest znana, można go rozwiązać wprowadzając w takim komunikacie licznik procesów, które go już odebrały.

Czytelnicy i pisarze. Wersja 1.

W przestrzeni krotek będzie zawsze przebywać co najwyżej jedna krotka postaci (c: integer). Jest to licznik czytelników przebywających w czytelni. Pisarz wchodząc do czytelni zabiera krotkę i oddaje ją dopiero po zakończeniu pisania. Zatem w trakcie pisania przestrzeń krotek jest pusta. Początkowo w przestrzeni krotek umieszczamy krotkę (0). Treści poszczególnych procesów są teraz natychmiastowe:

process Czytelnik;
var
  c: integer;
begin
  repeat
    własne_sprawy;
    Input (c: integer);    
    Output (c+1);
    CZYTANIE;
    Input (c: integer);    
    Output (c-1);
  until false
end;

process Pisarz;
begin
  repeat
    własne_sprawy;
    Input (0);             
    PISANIE;
    Output (0);            
  until false
end;

Przedstawione rozwiązanie ma własność bezpieczeństwa. Gorzej jest z żywotnością. Pisarz, który chce rozpocząć pisanie, musi poczekać aż nikogo nie będzie w czytelni. Do takiej sytuacji może jednak nigdy nie dojść, gdyż nowy czytelnik może zawsze dołączyć do przebywających w czytelni.

Zauważmy, że jeśli pisarz wejdzie do czytelni, to po jego wyjściu w przestrzeni krotek pojawi się krotka 0. Może ją pobrać albo kolejny pisarz, albo któryś z oczekujących czytelników. Co się dokładnie stanie --- nie wiemy, gdyż działa niedeterminizm. Mamy jednak gwarancję, że jeśli tylko nieskończenie wiele razy będzie się pojawiać krotka 0, to każdy z oczekujących procesów ją w końcu weźmie. Problem w tym wypadku polega jednak na tym, że taka krotka może się w ogólne nie pojawić (poza sytuacją początkową).

Czytelnicy i pisarze. Wersja 2.

process Czytelnik;
var
  c: integer;
begin
  repeat
    własne_sprawy;
    Input (c: integer, 0);    
    Output (c+1, 0);
    CZYTANIE;
    Input (c: integer, p: integer);    
    Output (c-1, p);
  until false
end;

process Pisarz;
begin
  repeat
    własne_sprawy;
    Input (c: integer, 0); 
    Output (c, 1);            
    PISANIE;
    Output (0, 0);            
  until false
end;