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

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.

Złożenie sekwencyjne

<ciąg instrukcji> ::= {<deklaracja>; | <instrukcja>; } <instrukcja>

Ciąg instrukcji to niepusty ciąg złożony z przeplecionych ze sobą deklaracji i instrukcji, oddzielanych od siebie średnikami. Średnik w CSP pełni funkcję złożenia sekwencyjnego. Oddziela on od siebie dwie instrukcje, przy czym wykonanie drugiej rozpoczyna się dopiero po zakończeniu pierwszej. Pod tym względem nie różni się od średnika stosowanego na przykład w Pascalu (ale nie w C, gdzie średnik jest elementem każdej instrukcji!).

Jeśli w ciągu instrukcji wystąpi deklaracja, to 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>} | $ϵ$   

Zmienną, której wartość ustawiamy instrukcją przypisania nazywamy zmienną docelową. Może ona być zmienną prostą lub zmienną strukturalną. Najprostszą postacią przypisania jest przypisanie wyrażenia prostego na zmienną prostą, jak na przykład:

x := y + 1

Semantyka takiego przypisania jest standardowa --- nie różni się ono niczym od przypisania występującego w językach imperatywnych takich jak Pascal czy C. Tego rodzaju przypisanie kończy się błędem, jeśli wartość wyrażenia jest nieokreślona lub w razie niezgodności typów.

Przypisanie w CSP może być jednak bardziej złożone. Przede wszystkim istnieje możliwość używania tzw. wyrażeń strukturalnych. Wyrażenie strukturalne jest abstrakcyjną wartością złożoną z konstruktora i jego argumentów, które są ciągiem wyrażeń. Prawidłowym wyrażeniem strukturalnym jest na przykład:

CONS (5, x)

złożone z konstruktora CONS z argumentami 5 oraz x. Wyrażenia strukturalne można przypisywać na zmienne proste:

 y := CONS (5, x)

lub też na zmienne strukturalne (które składają się z konstruktora i ciągu zmiennych docelowych). W tym ostatnim przypadku, przypisanie wykonuje się poprawnie jeśli zmienna strukturalna pasuje do wyrażenia strukturalnego, tzn.:

1. Nazwy konstruktorów i liczba ich argumentów są takie same.
2. Poszczególne wyrażenia w ciągu wyrażeń pasują do odpowiednich zmiennych w ciągu zmiennych.

Wykonanie przypisania strukturalnego polega na jednoczesnym wykonaniu przypisań poszczególnych wyrażeń z ciągu wyrażeń na odpowiednie zmienne docelowe. Na przykład:

 CONS (x, y) := CONS (3, 4)

jest poprawnym przypisaniem, które nada zmiennej x wartość 3, a zmiennej y wartość 4.

 CONS (y, x) := CONS (5, y+1)

nada zmiennej x dotychczasową wartość zmiennej y zwiększoną o 1, a zmiennej y wartość 5.

 CONS (y, x) := CAR (3, 5)

kończy się błędem.

Wartości strukturalne są często stosowane w instrukcjach wejścia oraz wyjścia do nazywania przesyłanej wiadomości i do przesłania wielu wartość w czasie jednej synchronizacji.

Szczególną postacią wartości strukturalnych są wartości z pustym konstruktorem. Można je wykorzystywać do jednoczesnego przypisywania wielu wartości na różne zmienne:

 (x, y) := (y, x)

powoduje zamianę wartości zmiennych x oraz y. Po lewej stronie występuje zmienna strukturalna z pustym konstruktorem, a po prawej stronie wyrażenie strukturalne z pustym konstruktorem.

Jeszcze inna często stosowana w instrukcjach wejścia/wyjścia postać wyrażenia strukturalnego to konstruktor bez argumentów. Taką wartość będziemy nazywać sygnałem.

Alternatywa

<alternatywa> ::= [<instrukcja dozorowana> { | <instrukcja dozorowana>} ]
<instrukcja dozorowana> ::= <dozór> -> <ciąg instrukcji> | (<zakres> {, <zakres>}) <dozór> -> <ciąg instrukcji>
<dozór> ::= <ciąg dozorów> | <wejście> | <ciąg dozorów>; <wejście>
<ciąg dozorów> ::= <element dozoru> {; <element dozoru> }
<element dozoru> ::= <wyrażenie logiczne> | <deklaracja>

Instrukcja alternatywy jest instrukcją strukturalną. Przypomina ona instrukcje warunkowe znane z języków imperatywnych. Alternatywa w CSP jest jednak niedeterministyczna.

Alternatywa składa się z oddzielonych od siebie znakiem | instrukcji dozorowanych. Każda instrukcja dozorowana w swojej najprostszej postaci składa się z dozoru, który jest po prostu wyrażeniem logicznych oraz ciągu instrukcji do wykonania. Początek alternatywy oznaczamy nawiasem kwadratowych otwierającym, a jej koniec --- nawiasem kwadratowym zamykającym. Oto przykład:

[ x $<$ 0 -> y := x 
| x $\ge$ 0 -> y := -x]

Wykonanie instrukcji alternatywy polega na wyliczeniu dozorów i wykonaniu tej instrukcji dozorowanej, której dozór jest prawdziwy. Zatem przedstawiony powyżej przykład przypisuje na zmienną y wartość bezwzględną x.

Co się jednak stanie, jeśli prawdziwych będzie więcej dozorów? Popatrzmy na przykład:

[ x $\le$ 0 -> y := x 
| x $\ge$ 0 -> y := -x]

Otóż w takiej sytuacji zostanie wybrana jedna instrukcja dozorowana spośród tych z prawdziwym dozorem. Która? Nie wiemy. Tu właśnie dochodzi do wyboru niedeterministycznego. Przedstawiony powyżej program nadal poprawnie oblicza wartość bezwzględną x, ale dla x=0 nie jesteśmy w stanie powiedzieć, która instrukcja dozorowana się wykona (choć wiemy, że niezależnie od tego y otrzyma wartość 0).

Jeszcze lepiej ów niedeterminizm widać w następującym przykładzie:

[ x > 10 -> y := 3 
| x < 20 -> y := 1]

Jeśli x $\ge 20$, to po wykonaniu tego programu y będzie równy 3, podobnie jeśli x <math\leq 10</.math>, to y będzie miał wartość 1. Jeśli jednak program uruchomimy z wartością $x\in (10,20)$, to wartością zmiennej y będzie albo 1 albo 3.

Spójrzmy na jeszcze jeden przykład:

[ x < 0 -> y := -x 
| x > 0 -> y := x]

Co stanie się, jeśli x = 0? Wtedy żaden dozór nie jest prawdziwy! Otóż w takiej sytuacji dochodzi do zerwania obliczeń, zatem alternatywa, w której żaden dozór nie jest prawdziwy jest błędna.

Co w takim razie zrobić jeśli chcemy wykonać pewne instrukcje, o ile warunek nie jest prawdziwy, a w przeciwnym razie nie robić nic. Wtedy z pomocą przychodzi instrukcja pusta skip. Instrukcja pusta jest instrukcją, która nie robi nic i zawsze kończy się powodzeniem. Wykorzystuje się ją, głównie w instrukcjach alternatywy i iteracji:

y := x;
[ x < 0 -> y := -y 
| x $\ge$0 -> skip]

Podsumujmy. Alternatywa pełni w CSP funkcję podobną do instrukcji warunkowych z języków imperatywnych. Alternatywa może składać się z wielu instrukcji dozorowanych, ale należy zadbać o to, aby zawsze co najmniej w jednej z nich dozór był prawdziwy. Wyliczenie alternatywy polega na wyznaczeniu instrukcji dozorowanych z prawdziwymi dozorami i wykonaniu jednej z nich.

Dozory złożone

Składnia CSP zezwala na umieszczenie w jednej instrukcji dozorowanej wielu dozorów jak w pierwszej instrukcji dozorowanej w następującym przykładzie:

[ x > 10; x < 20 -> y := 1
| x $\le 10$ -> y := 2
| x $\ge 20$ -> y := 3 ]

Taki dozór nazywamy dozorem złożonym. Jego wyliczenie polega na sekwencyjnym wyliczaniu poszczególnych wyrażeń logicznych (od lewej strony). Jeśli w wyniku otrzymujemy fałsz, to cały dozór jest fałszywy i jego dalsze obliczanie jest zaniechane, w przeciwnym razie przechodzimy do kolejnego wyrażenia logicznego. Jeśli wszystkie wyrażenia są prawdziwe, to cały dozór jest także prawdziwy.

Zgodnie z powyższym, dozory złożone zachowują się jak wyliczane leniwie koniunkcje warunków logicznych.

Tablice dozorów

Ostatnia postać alternatywy umożliwia zwarty zapis konstukcji typu:

[ a(1) > 1 -> a(1) := a(1) + 1
| a(2) > 2 -> a(2) := a(2) + 2
| a(3) > 3 -> a(3) := a(3) + 3 
...
]

W powyższym przykładzie a jest tablicą liczb całkowitych zadeklarowaną jako

a: (1..100) integer;

Chcemy zwiększyć o i któryś z elementów a(i) większych od i. W CSP zapiszemy to w postaci tablicy dozorów:

[(k: 1..100) a(k) > k -> a(k) := a(k) + k ]

Powyższa konstrukcja jest tak naprawdę czymś w postaci makra. W wyniku jego rozwinięcia uzyskujemy alternatywę złożoną ze 100 instrukcji dozorowanych, przy czym w pierwszej z nich wszystkie wystąpienia k są zastępowane jedynką, w drugiej --- dwójką itd.

Instrukcja pusta

Instrukcję pustą wykorzystaliśmy już w alternatywie. Jest to instrukcja, która nic nie robi i zawsze kończy się powodzeniem.