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

CSP jako notacja do opisu współbieżności

Omówimy teraz nieco inną notację, która szczególnie dobrze nadaje się do opisu komunikacji w systemach rozproszonych. Przez system rozproszony rozumiemy przy tym zestaw niezależnych komputerów nie dysponujących wspólną pamięcią, które porozumiewają się ze sobą jedynie poprzez wysyłanie i odbieranie komunikatów.

Communicating Sequential Processes (w skrócie CSP) jest notacją zaproponowaną przez C.A.R. Hoare'a pod koniec lat osiemdziesiątych. W odróżnieniu od poprzednio omawianych formalizmów jest to notacja a nie język programowania. Wiąże się z tym w szczególności brak kompilatora i środowiska do uruchamiania "programów" przygotowywanych w CSP. Pomimo tego CSP stała się pierwowzorem dla rzeczywistych języków programowania, np. Occama.

Pierwotnie CSP było jedynie prostą notacją do opisu współbieżności. Stopniowo jednak badania nad teoretycznymi własnościami tego formalizmu spowodowały powstanie licznych prac dotyczących m.in. algebr procesów. Na tych zajęciach skupimy się jednak nad własnościami CSP jako notacji do opisu współbieżności.

Identyfikacja symetryczna

CSP jest notacją synchroniczną. Komunikują się ze sobą zawsze dwa procesy, z których jeden jest nadawcą, a drugi jest odbiorcą. Nadawca musi jawnie określić identyfikator procesu, do którego kieruje przesyłaną wiadomość. Analogicznie odbiorca musi podać identyfikator procesu, od którego chce odebrać komunikat. Taki schemat nazywamy identyfikacją symetryczną, gdyż oba procesy biorące udział w komunikacji znają swoje nazwy.

Jak zwykle w mechanizmach synchronicznych procesy oczekują na siebie. Proces, który chce wysłać komunikat będzie zatem wstrzymywany do chwili, gdy odbiorca będzie gotowy do odbioru tego komunikatu. I na odwrót: odbiorca będzie oczekiwał do momentu, aż nadawca będzie gotowy do przesłania komunikatu. Dopiero, gdy obie strony będą gotowe, dojdzie do komunikacji. Szczegóły związane z takim mechanizmem omówimy w części poświęconej instrukcjom wejścia/ wyjścia.

Niedeterminizm

"Program" w CSP jest zbudowany z deklaracji i instrukcji. Każda instrukcja może wykonać się poprawnie lub załamać się. Ponieważ traktujemy CSP jak notację, a nie język programowania, nie precyzujemy, co dokładnie oznacza załamanie instrukcji.

Cechą charakterystyczną niektórych instrukcji CSP jest występujący w nich niedeterminizm. Oznacza to, że instrukcja może wykonywać się w różny sposób i jej wynik nie musi być jednoznacznie wyznaczany przez stan początkowy. Zatem dwa różne wykonania tego samego programu dla tych samych danych wejściowych może dać różne wyniki.

Niedeterminizm jest bardzo silnym mechanizmem i będziemy z niego wielokrotnie korzystać.

Składnia i semantyka CSP

Przejdźmy teraz do omówienia składni CSP i znaczenia poszczególnych instrukcji. Składnię zaprezentujemy wykorzystując notację BNF. Podamy też przykłady poszczególnych konstrukcji. Semantykę przedstawimy w nieformalny sposób w postaci opisu w języku naturalnym.

Instrukcje

<instrukcja> ::= <instrukcja prosta> | <instrukcja strukturalna>
<instrukcja prosta> ::= <instrukcja pusta> | <przypisanie> | <wejście> | <wyjście> 
<instrukcja strukturalna> ::= <alternatywa> | <iteracja> | <instrukcja równoległa> 
<instrukcja pusta> ::= skip
<ciąg instrukcji> ::= {<deklaracja>; | <instrukcja>; } <instrukcja>

Instrukcje mogą być proste (instrukcja pusta, przypisanie, wejście, wyjście) bądź strukturalne. Jak już wspomnieliśmy każda instrukcja wykonuje się poprawnie lub kończy błędem (załamuje się). Omawiając poszczególne instrukcje proste podamy sytuacje, które powodują błąd. Jeśli jakakolwiek składowa instrukcji strukturalnej kończy się błędem, to również cała instrukcja strukturalna kończy się błędem.

Ciąg instrukcji to niepusty ciąg złożony z przeplecionych ze sobą deklaracji i instrukcji, oddzielanych od siebie średnikami. Zakres zmiennej rozciąga się od miejsca jej deklaracji do końca ciągu instrukcji, w którym została zadeklarowana.

Zanim przejdziemy do szczegółowego omówienia poszczególnych instrukcji popatrzmy jeszcze na przykładowy program w CSP (nie wchodząc w jego szczegóły):

[x, y: integer;
  x := 1; y := 2;
  [ pom: integer;
    pom := x; x := y; y := pom 
  ]
 ] 

Przypisanie

<przypisanie> ::= <zmienna docelowa> := <wyrażenie> 
<wyrażenie> ::= <wyrażenie proste> | <wyrażenie strukturalne> 
<wyrażenie strukturalne> ::= <konstruktor> ( <ciąg wyrażeń> )
<konstruktor> ::= <nazwa> | $ϵ$
<ciąg wyrażeń> ::= <wyrażenie> {, <wyrażenie>} | $ϵ$
<zmienna docelowa> ::= <zmienna prosta> | <zmienna strukturalna>
<zmienna strukturalna> ::= <konstruktor> ( <ciąg zmiennych docelowych> ) 
<ciąg zmiennych docelowych> ::= <zmienna docelowa> {, <zmienna docelowa>} | $ϵ$