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ć.
Komunikacja jako synchroniczne rozproszone przypisanie
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>
