CSP cd. | Informatyka MIMUW

Instrukcja wejścia i instrukcja wyjścia

Instrukcja wejścia i instrukcja wyjścia tworzą synchroniczny mechanizm komunikacyjny CSP. Składnia instrukcji wejścia jest następująca:

<wejście> ::= <źródło> ? <zmienna docelowa>
<źródło>  ::= <nazwa procesu> 
<nazwa procesu> ::= <nazwa> | <nazwa> ( <indeksy> )
<indeksy> ::= <wyrażenie całkowite> {, <wyrażenie całkowite>}

Przypuśćmy, że w procesie P wystąpiła instrukcja wejścia postaci Q?x. Oznacza ona, że proces P chce odebrać od procesu Q wiadomość i zapisać ją na zmienną x. Typ tej zmiennej wyznacza zarazem typ komunikatu. Co się dzieje z procesem P, jeśli sterowanie dojdzie do takiej instrukcji? Będzie on oczekiwał aż sterowanie w procesie Q dojdzie do pasującej instrukcji wyjścia. Popatrzmy więc teraz na składnię instrukcji wyjścia:

 <wyjście> ::= <przeznaczenie> ! <wyrażenie> 
 <przeznaczenie> ::= <nazwa procesu>

Jeśli więc w procesie Q wystąpi instrukcja P!6, to oznacza ona, że proces Q chce wysłać do procesu P wartość 6. I tak jak w przypadku instrukcji wejścia proces będzie oczekiwał aż sterowanie w P dojdzie do pasującej instrukcji wejścia.

Co dokładnie oznacza słowo pasująca?

Nazwy procesów muszą sobie odpowiadać.
Wyrażenie w nadawcy musi pasować (w sensie opisanym przy okazji instrukcji przypisania) do zmiennej docelowej odbiorcy.

Gdy dojdzie do sytuacji, w której jeden proces wykonuje instrukcję wyjścia, a drugi pasującą do niej instrukcję wejścia, to dochodzi do komunikacji i zmienna docelowa w odbiorcu otrzymuje wartość wyrażenia.

Na opisany powyżej schemat można patrzeć jak na ... zwykłe przypisanie. "Jedyna" różnica polega na tym, że zmienna docelowa (na którą przypisujemy), znajduje się w innym wyrażeniu niż wyrażenie, którego wartość chcemy jej przypisać.

Przypomnijmy raz jeszcze, że opisywany schemat jest mechanizmem synchronicznym: procesy biorące udział w komunikacji muszą się zsynchronizować, aby doszła ona do skutku. Identyfikacja jest przy tym symetryczna, bo zarówno nadawca musi znać nazwę odbiorcy, jak i odbiorca musi znać nazwę nadawcy.

Popatrzmy na przykład:

 [ Producent :: 
    x: integer;
    *[ true -> produkuj (x);
               Konsument!x
     ]
 || Konsument ::
    x : integer;
    *[ true -> Producent?x;
               konsumuj(x)
    ]
 ]

Jest to poprawny zapis komunikacji między producentem a konsumentem bez bufora. Producent po wyprodukowaniu nowej wartości swojej zmiennej lokalnej x próbuje wysłać tę wartość do konsumenta. Do komunikacji dojdzie, gdy konsument będzie do tego gotowy, czyli gdy sterowanie dojdzie w nim do instrukcji wejścia. Po przekazaniu wartości konsumentowi, producent zajmuje się produkcją, a konsument --- konsumpcją. Jeśli producent wyprodukuje nową porcję zanim konsument zakończy procedurę konsumuj, to będzie oczekiwał na instrukcji wyjścia. Podobnie konsument, który zakończy procedurę konsumuj, zanim producent wyprodukuję nową porcję będzie oczekiwał na instrukcji wejścia. Nie dojdzie zatem ani do zagubienia pewnych informacji ani do pobrania porcji nie wyprodukowanej uprzednio przez producenta.

Zarówno instrukcja wejścia jak i instrukcja wyjścia mogą zakończyć się błędem. Stanie się tak, jeśli proces próbuje skomunikować się z procesem, który już zakończył swoje działanie. Od tej reguły jest jednak wyjątek: instrukcja wejścia w dozorze zachowuje się nieco inaczej.

Instrukcja wejścia w dozorze

Składnia alternatywy/iteracji sugerowała, że dozorem oprócz wyrażenia logicznego może być także instrukcja wejścia. Omówimy teraz znaczenie tego rodzaju konstrukcji. Zanim to jednak uczynimy podkreślmy bardzo wyraźnie: jedynie instrukcja wejścia może wystąpić w dozorze. Instrukcja wyjścia nigdy nie występuje w dozorze.

Aby umieszczenie instrukcji wejścia w dozorze miało sens, należy wyjaśnić jaka jest jej wartość logiczna. Przypuśćmy, że mamy instrukcję postaci:

*[ P?x -> y := x + 8 ]

Mamy trzy możliwości:

Proces P zakończył się już. Wtedy dozór wylicza się natychmiast do wartości fałsz.
Proces P działa i sterowanie w nim jest w pasującej do P?x instrukcji wyjścia. Wtedy dochodzi do komunikacji i dozór wylicza się do prawdy.
Proces P działa, ale sterowanie w nim nie znajduje się w pasującej instrukcji wyjścia. Wtedy wyliczanie dozoru jest wstrzymywane. Jeśli są inne dozory do wyliczenie (w tym przykładzie --- nie ma), to są one wyliczane. Jeśli nie zostaną znalezione żadne prawdziwe dozory, to wyliczenie instrukcji alternatywy/pętli jest wstrzymywane w oczekiwaniu na "wyjaśnienie sytuacji", czyli zakończenie procesu P lub jego gotowość do komunikacji.

Przykłady

Wzajemne wykluczanie

Przypuśćmy, że procesy S(1..100) rywalizują o dostęp do sekcji krytycznej. Dostęp do niej zrealizujemy wprowadzając dodatkowy proces P. Każdy z procesów S przed wejściem do sekcji krytycznej informuje o tym proces P wysyłając mu komunikat. Ponieważ nie jest przekazywana żadna wartość (jest ważny jedynie fakt zgłoszenia chęci wejścia do sekcji krytycznej) wykorzystamy do tego celu sygnały (wyrażenia strukturalne bez argumentów). Proces S nie musi oczekiwać na zgodę procesu P --- proces ten nie będzie słuchał próśb, jeśli ktoś jest w sekcji krytycznej. Po wyjściu z sekcji krytycznej proces S informuje o tym proces zarządzający:

[S(i: 1..100):: 
   *[ true -> własne_sprawy;
              P!Chce();
              sekcja_krytyczna;
              P!Zwalniam()
    ]
||
  P::
    *[(i: 1..100) S(i)? Chce() -> S(i)?Zwalniam()]
]

Wzajemne wykluczanie z większą liczbą procesów w sekcji krytycznej

Przypuśćmy, że chcemy wpuszczać do sekcji krytycznej nie jeden proces, ale co najwyżej 10. Zmieniamy kod procesu zarządzającego P tak, aby:

Zliczał procesy przebywające w sekcji krytycznej.
Był przygotowany na to, że komunikaty zamawiające sekcję i zwalniające ją będą nadchodzić w niedającej się przewidzieć kolejności.
Przestał słuchać próśb o wejście do sekcji krytycznej, gdy nie ma w niej miejsca. W tym celu użyjemy dozorów złożonych.

[S(i: 1..100):: 
   *[ true -> własne_sprawy;
              P!Chce();
              sekcja_krytyczna;
              P!Zwalniam()
    ]
||
  P::
    wolnych: integer;
    wolnych := 10;  
    *[(i: 1..100) wolnych > 0; S(i)? Chce() -> wolnych := wolnych - 1
     |(i: 1..100) S(i)? Zwalniam() -> wolnych := wolnych + 1
     ]
]

Pięciu filozofów

Wykorzystamy 3 rodzaje procesów: filozofów, widelce i lokaja. Filozof przed wejściem do sekcji krytycznej informuje o tym lokaja, po czym próbuje podnieść najpierw jeden widelec, potem drugi. Lokaj dba o to, aby przy stole przebywało jednocześnie co najwyżej 4 filozofów. Widelec dba o to, aby mógł nim jeść co najwyżej jeden filozof jednocześnie:

[  Filozof (i: 0..4)::
     *[ true -> mysli;
                Lokaj!Chce();
                Widelec(i)!Chce();
                Widelec((i+1) mod 5)!Chce();
                je;
                Widelec((i+1) mod 5)!Odkłada();
                Widelec(i)!Odkłada();
                Lokaj!Wychodzę()
      ]
|| Widelec (i: 0..4)::
   *[ Filozof(i)?Chce() -> Filozof(i)?Odklada()
    | Filozof((i+4) mod 5)?Chce() -> Filozof((i+4) mod 5)?Odklada()
    ]
|| Lokaj :: wolnych : integer;
   wolnych := 4;
   *[(i:0..4) wolnych > 0; Filozof(i)?Chce() -> wolnych := wolnych - 1
    |(i:0..4) Filozof(i)?Wychodze() -> wolnych := wolnych + 1
    ]
]

Silnia

A oto przykład wykorzystania potoku procesów do realizacji obliczeń rekurencyjnych. Chcemy obliczać silnię z argumentem co najwyżej równym MAX (jest to pewna stała). Tworzymy potok procesów, z których każdy odbiera od poprzedniego argument oblicza silnię (być może wykorzystując dalsze procesy) i odsyła wynik:

[silnia (i: 1..MAX):: 
    n, w : integer;
    *[silnia(i-1)?n -> [n=0 -> silnia (i-1)!1
                       |n>0 -> silnia (i+1)!(n-1);
                               silnia (i+1)?w; 
                               silnia (i-1)!w*n
                       ]
    ]
]

Proces, w którym chcemy obliczać silnię nazywamy silnia(0) i umieszczamy w nim instrukcję silnia(1)!n, gdzie n jest wartością, której silnię chcemy obliczyć.