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.

Iteracja

<iteracja> ::= * <alternatywa>

Instrukcja iteracji służy do konstruowania pętli. Składniowo różni się od alternatywy jedynie gwiazdką przed nawiasem otwierającym. W najprostszej postaci składa się tylko z jednej instrukcji dozorowanej. W takiej sytuacji instrukcja po strzałce jest wykonywana tak długo, jak długo dozór (wyrażenie przed strzałką) jest prawdziwe. Gdy dozór wyliczy się do wartości fałsz, następuje przejście do następnej instrukcji za pętlą. Zwróćmy uwagę, że różni się to od semantyki alternatywy. Tam brak prawdziwego dozoru oznaczał błąd, tu --- zwykłe, poprawne wyjście z pętli.

A oto przykład programu sumującego 100 kolejnych liczb całkowitych dodatnich:

s := 0; i := 1;
*[ i $\le$ 100 -> s := s + i; i := i + 1 ]

W iteracji może być jednak wiele instukcji dozorowanych. Wtedy wykonanie iteracji przebiega następująco:

1. Wyliczamy dozory. Jeśli wszystkie są fałszywe kończymy (w sposób poprawny!) wykonanie pętli.
2. Wybieramy jedną instrukcję z prawdziwym dozorem i wykonujemy ją.
3. Wracamy do kroku 1.

W jednym obrocie instrukcji interacji jest zatem wykonywana jedna instrukcja dozorowana, a następnie ponownie oblicza się dozoru. Algorytm ten powtarzamy do momentu, aż wszystkie dozory będą fałszywe.

Wszystkie techniki omówione przy okazji alternatywy (dozory złożone, tablice dozorów) można stosować także w iteracji. A oto inny przykład:

a: (1..100) integer;
*[ (k: 1..99) a(k) > a(k+1) -> (a(k), a(k+1)) := (a(k+1), a(k)) ] 

Jest to ... sortowanie bąbelkowe! W powyższej iteracji mamy 99 instrukcji dozorowanych. W k-tej z nich sprawdzamy, czy element na pozycji k i k+1 są ze sobą w inwersji. Jeśli tak, to zamieniamy je miejscami stosując jednocześne przypisanie.

I jeszcze jeden przykład pokazujący charakterystyczny dla CSP sposób inicjowania tablic. Przypuśćmy, że wszystkie elementy tablicy a chcemy zainicjować na zero. Można tego dokonać następującą konstrukcją:

a: (1..100) integer;
*[ (k: 1..100) a(k) $\ne$0 -> a(k):= 0 ] 

Złożenie równoległe

<instrukcja równoległa> ::= [ <proces> { || <proces> }]
<proces> ::= <etykieta procesu> <ciąg instrukcji>
<etykieta procesu> ::= $ϵ$ | <nazwa> :: | <nazwa> ( <indeks> {, <indeks>})::
<indeks> ::= <stała całkowita> | <zakres> 
<stała całkowita> ::= <liczba całkowita> | <zmienna związana> 
<zmienna związana> ::= <nazwa> 
<zakres> ::= <stała całkowita> .. <stała całkowita> 

Oprócz złożenia sekwencyjnego instrukcji, oznaczanego w CSP średnikiem, mamy także do dyspozycji złożenie równoległe procesów. Proces w CSP to dowolny ciąg instrukcji, któremu dodatkowo można nadać nazwę. W najprostszej postaci nazwa to po prostu identyfikator. Procesy wchodzące w skład instrukcji równoległej oddzielamy od siebie podwójną kreską pionową. A oto przykład:

 x := 1; y := 3;
 [ P:: x := x * x || y := y + 5 ]

Powyższy program składa się z trzech instrukcji. Pierwsze dwie to zwykłe przypisania. Po ich wykonaniu dochodzi do wykonania instrukcji równoległej obejmującej dwa procesy: proces P podnoszący x do kwadratu oraz nienazwany proces zwiększający y o 5.

Instrukcja równoległa oznacza współbieżne wykonanie wchodzących w jej skład procesów. Procesy zaczynają swoje działanie jednocześnie. Instrukcja złożenia równoległego kończy się, gdy skończą się wszystkie wchodzące w jej skład procesy. Jeśli którykolwiek z tych procesów skończy się błędem, to cała instrukcja równoległa także jest błędna.

Spójrzmy na inny przykład. Przypuśćmy, że chcemy wyliczyć wartość wyrażenia: $\frac{{\mathrm{\Sigma }}_{1\le i\le n}a(2i)}{{\mathrm{\Sigma }}_{1\le i\le n}a(2i-1)}$. Możemy to zrobić tworząc dwa procesy, z których każdy oblicza odpowiednie sumy:

 a: (1..2n) real;
 s1, s2, wynik: real; 
 [ P::
    i: integer;
    i := 1; s1 := 0;
    *[ i <= 2n -> s1 := s1 + a(i); i := i + 2 ]
 ||Q::
    i: integer;
    i := 2; s2 := 0;
    *[ i <= 2n -> s2 := s2 + a(i); i := i + 2 ]
 ];
 wynik := s1 / s2;

Spójrzmy na zmienne, z których korzystają poszczególne procesy. Proces P odczytuje elementy tablicy, modyfikuje zmienną s1 oraz korzysta ze swojej lokalnej zmiennej i. Proces Q odczytuje elementy tablicy a, modyfikuje zmienną s2 oraz korzysta z lokalnej zmiennej s2. Zmienne lokalne nie stanowią problemu, jednak procesy korzystają także ze zmiennych globalnych s1 oraz s2, a nawet je modyfikują. Wiemy już w pierwszego wykładu, że próba jednoczesnej modyfikacji tej samej zmiennej przez dwa procesy może dać nieoczekiwane efekty.

Z tego powodu CSP wprowadza ograniczenie dotyczące zmiennych występujących w procesach wykonujących się w ramach tej samej instrukcji równoległej. Procesy muszą być rozłączne, czyli żaden proces nie może używać żadnej innej zmiennej docelowej (czyli modyfikowanej przez przypisanie lub instrukcję wejścia) żadnego innego procesu.

W przedstawionym przykładzie tak właśnie się dzieje. Zmienna s1 jest docelowa w P, i Q z niej nie korzysta, analogicznie zmienna s2 jako docelowa w Q nie jest wykorzystywana przez P.

Tablice procesów

Nazwą procesu nie musi być jedynie identyfikator. Procesy, podobnie jak dozory, można tablicować. Wtedy nazwą procesu jest identyfikator z indeksem oznaczającym pozycję procesu w tablicy. Deklaracja:

[ P(i: 1..3):: <ciąg instrukcji> ]

jest skrótem notacyjnym (makrem) oznaczającym następującą instrukcję złożenia równoległego:

[  P(1):: <ciąg instrukcji>${}_1$
|| P(2):: <ciąg instrukcji>${}_2$
|| P(3):: <ciąg instrukcji>${}_3$
]

przy czym <ciąg instrukcji>${}_1$ oznacza <ciąg instrukcji>, w którym wszystkie wystąpienia zmiennej związanej i zastąpiono jedynką itd.

Poprzedni przykład obliczający iloraz sum można więc zapisać teraz następująco:

 a: (1..2n) real;
 wynik: real;
 s: (1..2) real; 
 [ P(k: 1..2)::
    i: integer;
    i := k; s(k) := 0;
    *[ i <= 2n -> s(k) := s(k) + a(i); i := i + 2 ]
 ];
 wynik := s(1) / s(2);

W dalszym ciągu zajęć wprowadzimy dwa dodatkowe ograniczenia dotyczące instrukcji równoległej.

1. Będziemy stosować instrukcję równoległą jedynie na najbardziej zewnętrznym poziomie.
2. W procesach nie będziemy w ogóle stosować zmiennych globalnych. Jedynym sposobem przekazywanie informacji będą komunikaty wymieniane za pomocą instrukcji wejścia/wyjścia.