Wykład (30 godzin) + laboratorium/ćwiczenia (30 godzin)
Celem wykładu jest zaprezentowanie najważniejszych technik stosowanych do synchronizacji procesów i realizacji komunikacji między nimi, problemów, jakie stają przed programistą opracowującym programy współbieżne. Omówiony zostanie scentralizowany i rozproszony model programu współbieżnego. Problematyka zostanie zilustrowana przykładami klasycznych problemów współbieżności oraz mechanizmów synchronizacji procesów i wątków w systemie operacyjnym Linux. Przedstawione też zostaną metody weryfikacji programów współbieżnych oraz notacje do opisu współbieżności oraz podstawowe algorytmy rozproszone.
Zadaniem przedmiotu "Programowanie współbieżne" jest przedstawienie problematyki związanej z tworzeniem programów, w których wiele czynności może odbywać się równocześnie. Zajmiemy się przede wszystkim problematyką właściwej synchronizacji czynności składających się na program współbieżny i zagadnieniami związanymi z ich poprawnością.
Pisanie programów jest trudne. Jest to stwierdzenie prawdziwe już w przypadku programów sekwencyjnych, gdy na raz wykonuje się jedna instrukcja i nie trzeba rozważać wszystkich możliwych interakcji z innymi działającymi w tym samym czasie programami. Wprowadzenie współbieżności jeszcze bardziej utrudnia programowanie. Dlaczego zatem warto i należy rozważać programy współbieżne?
Odpowiedzieć na to pytanie można na wiele sposobów.
A oto przykłady "prac", które można realizować współbieżnie.
współbieżnie licząc na przykład jednocześnie wyrażenia w nawiasach.
procedure sortuj (i, j) { sortuje tablicą A[i..j] } begin ... m := (i+j) div 2; sortuj (i, m); sortuj (m+1, j); scal (i, m, j); end
Zauważmy, że oba wywołania rekurencyjne procedury są tu niezależne od siebie --- dotyczą rozłącznych fragmentów tablicy. Nic nie stoi na przeszkodzie, aby były wykonywane w tym samym czasie: na różnych procesorach lub nawet na jednym z podziałem czasu. Taki równoległy algorytm możemy zapisać w postaci:
procedure sortuj (i, j) { sortuje tablicą A[i..j] }
begin
...
m := (i+j) div 2;
cobegin
sortuj (i, m);
sortuj (m+1, j);
coend
scal (i, m, j);
end
Słowa kluczowe cobegin i coend oznaczają, że czynności znajdujące się między nimi można wykonywać współbieżnie. Algorytm ten dobrze ilustruje również problem właściwej synchronizacji. Co stałoby się, gdybyśmy także wywołanie scal umieścili między cobegin i coend? Wówczas scalanie odbywałoby się współbieżnie z sortowaniem obu fragmentów tablicy. Wtedy scalanie mogłoby działać na jeszcze nie uporządkowanych fragmentach tablicy, co spowodowałoby niepoprawne działanie całego algorytmu. Na marginesie zauważmy, że w trakcie tego przedmiotu nie będziemy układać algorytmów równoległych. Zajmiemy się jedynie zagadnieniami związanymi z synchronizacją: problemami, mechanizmami i notacjami.
cobegin
while true do
begin
wczytaj znak z klawiatury;
wypisz go do bufora
end
while true do
begin
wczytaj znak z bufora;
wypisz go na ekran
end
end
Wspomnieliśmy o tym, że akcje współbieżne mogą być wykonywane faktycznie jednocześnie lub też (pod kontrolą systemu operacyjnego z podziałem czasu) fragment po fragmencie naprzemiennie z akcjami innego procesu. Opisując wykonanie pewnego procesu będziemy używać następującej terminologii:
Zanim przejdziemy do dalszego ciągu wykładu, przypomnijmy różnicę między procesem a programem. Program to obiekt statyczny --- tekst wykonywanego przez proces kodu. Proces to obiekt dynamiczny, "żywy", to wykonanie programu w pewnym środowisku lub wstrzymane wykonanie (w oczekiwaniu na jakiś zasób). Proces ma przydzielone zasoby (pamięć, urządzenia we/wy) i rywalizuje o dostęp do procesora. Procesy wykonują się pod kontrolą systemu operacyjnego. Przypomnijmy kilka najważniejszych faktów dotyczących zarządzania procesami.
Każdy proces znajduje się w jednym z kilku możliwych stanów. Dokładna analiza tych stanów została przedstawiona na systemach operacyjnych. Do zrozumienia dalszego ciągu zajęć potrzebna nam będzie jednak wiedza o trzech możliwych stanach procesu:
Zauważmy, że w rywalizacji o przydział procesora biorą udział procesy gotowe. Zakładamy, że jeśli jakiś proces jest gotowy do wykonania, to w końcu stanie się wykonywany. Jest to bardzo ważne założenie, które będziemy nazywać sprawiedliwością systemu operacyjnego. Oznacza ono, że każdy proces, który ma niezbędne zasoby w skończonym czasie zacznie się wykonywać. Nie zdarzy się tak, że pewien proces P jest gotowy do wykonania i za każdym razem gdy dochodzi do przełączenia konktekstu, procesor otrzymuje inny proces. Bez założenia o sprawiedliwości systemu operacyjnego nie będziemy w stanie wykazać poprawności żadnego programu współbieżnego.
Zauważmy również, że procesy wstrzymane nie rywalizują o procesor --- nie są uwzględniane przy przełączaniu konktekstu. Jeśli zatem będziemy chcieli wstrzymać wykonanie pewnego procesu, będziemy przenosić go do kolejki procesów wstrzymanych za pomocą mechanizmów udostępnianych przez system operacyjny. O takim wstrzymaniu procesu mówimy, że jest nieaktywne. W odróżnieniu, oczekiwanie aktywne polega na tym. że wstrzymywany proces cały czas korzysta z procesora i na przykład w pętli sprawdza co jakiś czas warunek na kontynuowanie działania. Należy już w tym momencie podkreślić, że oczekiwanie aktywne jest niekorzystne i będziemy traktować je jako błąd synchronizacyjny. Nie ma bowiem sensu marnowanie czasu procesora, jeśli można odwołać się do mechanizmów systemu operacyjnego i wstrzymać proces w sposób nieaktywny.
Jest jeden wyjątek od powyższej zasady. Jeśli system operacyjny nie daje programiście żadnych mechanizmów synchronizacyjnych (a obecnie każdy system takie mechanizmy udostępnia), to aktywne oczekiwanie jest jedynym sposobem wstrzymania procesu. Wykorzystamy ten mechanizm na pierwszych ćwiczeniach. Czasem oczekiwanie aktywne stosuje sam system operacyjny. Dzieje się tak w sytuacjach, kiedy wiadomo, że proces zostaje wstrzymywany jedynie na chwilę i przenoszenie go do kolejki procesów wstrzymanych, a następnie znów do kolejki procesów gotowych trwałoby dłużej niż kilka obrotów aktywnej pętli.
Program współbieżny składa się z kilku (co najmniej dwóch) współbieżnych procesów sekwencyjnych, które muszą się ze sobą komunikować lub synchronizować swoje działania. Nie interesują nas procesy rozłączne, czyli takie które działają niezależnie od siebie, nie wymagając żadnych działań synchronizacyjnych ani nie wymieniając między sobą danych.
Zajmiemy się omówieniem mechanizmów udostępnianych przez systemy operacyjne do synchronizacji procesów. Zwrócimy uwagę na pułapki, w jakie może wpaść programista. Nauczymy się także szukać przeplotów prowadzących do nieprawidłowych wykonań i ograniczać ich liczbę tak, aby z jednej strony nie ograniczać zbytnio współbieżności, a z drugiej strony nie dopuszczać do powstanie nadmiernej ich liczby.
Zajęcia z programowania współbieżnego składają się z 15 wykładów i 15 ćwiczeń. Każdy wykład zawiera materiał przeznaczony do samodzielnego przeczytania i przyswojenia. Ćwiczenia zawieraja materiał do wykonania przez studenta. Są dwa rodzaje ćwiczeń:
Tak jak w przypadku programów sekwencyjnych mówimy o poprawności programów współbieżnych. Pojęcia częściowej poprawności i całkowitej poprawności stosowane w analizie poprawności programów sekwencyjnych tracą jednak tutaj swój sens. Przypomnijmy, że poprawność częściowa to własność mówiąca, że jeśli program kończy się, to daje poprawne wyniki. Programy współbieżne jednak składają się z wielu procesów, z których każdy najczęściej działa w pętli nieskończonej. Nie jesteśmy tutaj zainteresowani uzyskaniem konkretnych wartości, ale raczej zapewnieniem poprawnej synchronizacji przez cały czas działania programu. Tym bardziej nie ma sensu wymaganie, aby program współbieżny kończył się, jak wymaga się tego, przy poprawności całkowitej.
W związku z tym musimy przedefiniować pojęcie poprawności.
Podstawowym pojęciem wykorzystywanym przy analizie programów współbieżnych jest przeplot. Zanim wyjaśnimy to pojęcie zajmijmy się przez chwilę procesem sekwencyjnym. Ciąg wykonawczy takiego procesu to ciąg złożony z kolejno wykonywanych przez niego akcji. Może on być skończony (tak zwykle bywało przy analizie poprawności programów sekwencyjnych) lub nieskończony (jeśli proces działa w pętli nieskończonej).
Jeśli rozpatrujemy program współbieżny składający się z pewnej liczby procesów sekwencyjnych, to musimy uwzględnić każdą możliwą do uzystkania kolejność potencjalnie współbieżnych akcji. Nie wolno nam zakładać, że jeden z procesów wykonuje się szybciej, a drugi wolniej. Musimy wziąć pod uwagę każde możliwe do uzyskania wykonanie. Takie wykonanie to właśnie przeplot. Zatem
Przeplot jest bardzo ważnym pojęciem. Jeśli chcemy pokazać, że program współbieżny nie działa poprawnie, to wystarczy pokazać jeden przeplot, przy którym dochodzi do sytuacji błędnej. Z kolei poprawny program współbieżny działa dobrze dla każdego przeplotu. Podkreślmy jeszcze raz: dla każdego przeplotu, nawet tego najbardziej nieprawdopodobnego.
Możemy także mówić o ciągu wykonawczym programu współbieżnego. W odróżnieniu od ciągu wykonawczego procesu sekwencyjnego jest to tym razem zbiór:
Ze względu na to, że program współbieżny składa się z procesów, które działają w pętli nieskończonej, zbiór ten jest nieskończonym zbiorem złożonym z nieskończonych ciągów.
Takie podejście do poprawności niesie za sobą szereg problemów. Zauważmy, że testowanie programów współbieżnych staje się właściwie nieprzydatne. Jeśli program jest błędny, to może dawać podczas testowania poprawne wyniki. Błąd może ujawniać się raz na tysiąc uruchomień i wówczas bardzo trudno go zlokalizować.
Również zadanie formalnego pokazania poprawności programu współbieżnego jest trudne. Trzeba bowiem pokazać, że pewna własność zachodzi dla każdego możliwego wykonania programu. W dodatku, jak się za chwilę przekonamy, interestujące nas własności mogą mieć same dość skomplikowaną strukturę logiczną.
Program współbieżny musi mieć własnośćbezpieczeństwa zwaną również własnością zapewniania. Najkrócej tę własność można wyrazić następująco:
Popatrzmy na przykład. Przypuśćmy, że rozpatrujemy ruchliwe skrzyżowanie w środku dużego miasta. Procesy to samochody usiłujące przez to skrzyżowanie przejechać (na wprost). Własność bezpieczeństwa wyraża fakt, że nie dojdzie do kolizji. Możemy ją wyrazić tak:
Własność bezpieczeństwa zazwyczaj jest podawana w specyfikacji zadania, które należy rozwiązać. Stanowi ona odpowiednik częściowej poprawności.
W omawianym przykładzie skrzyżowania własność bezpieczeństwa można bardzo łatwo zagwarantować: nie wpuszczać na skrzyżowanie żadnego samochodu! Mamy wtedy bardzo bezpieczne rozwiązanie, ale ... trudno uznać je za poprawne. Z tego powodu poprawny program współbieżny powinien mieć także inną własność.
Własność żywotności można wyrazić tak:
W przykładzie skrzyżowania oznacza to, że każdy samochód, który chce przez skrzyżowanie przejechać, w końcu przez to skrzyżowanie przejedzie.
Własność żywotności nie jest zazwyczaj podawana w specyfikacji problemu. Należy jednak pamiętać, że jest ona równie ważna, co własność zapewniania. W przypadku braku żywotności dochodzi do jednej z dwóch rodzajów błędów:
Zakleszczenie jest zjawiskiem, które dużo łatwiej wykryć i łatwiej jest go uniknąć. Zagłodzenie trudniej zauważyć i trudniej mu przeciwdziałać.
Program współbieżny jest zatem poprawny, jeśli dla każdego przeplotu ma własność bezpieczeństwa oraz własność żywotności. Aby pokazać, że program jest niepoprawny, wystarczy skonstruować przeplot prowadzący do braku bezpieczeństwa lub braku żywotności.
Zauważmy, że we wszystkich dotychczasowych sformułowaniach nie wystąpiła żadna miara czasu. Używamy terminu w końcu lub w skończonym czasie. I tak będzie do końca tych zajęć. Przygotowując program współbieżny nie przyjmujemy żadnym założeń dotyczących czasu. Nie interesuje nas jak długo będzie trwała dana czynność, a jedynie to, czy się skończonym czasie zakończy, czy wystąpi jakaś reakcja na nią itp.
Projektując program współbieżny w konkretnym języku programowania nie powinniśmy także nic zakładać na temat tego, czy dana instrukcja jest realizowana w sposób niepodzielny, czy nie. W szczególności pisząc
nie wolno założyć, że zmienna x zostanie odczytana, zmieniona i zapisana w jednym cyklu procesora. Więcej na ten temat na następnym wykładzie.
Czasami narzucające się rozwiązanie problemu synchronizacyjnego jest bezpieczne i żywotne, ale jest nie do przyjęcia z innych powodów. Załóżmy, że w przykładzie ze skrzyżowaniem występują dwa procesy (jeden jadący ciągle z północy), drugi jadący ciągle ze wschodu. Przyjmijmy, że każdy z nich w pętli nieskończonej przejeżdża skrzyżowanie, po czym wraca inną drogą itd. Narzucające się rozwiązanie polega na tym, aby wpuszczać te samochody na skrzyżowanie na zmianę. Jeśli jednak jeden z nich chciałby przejeżdżać przez skrzyżowanie raz na dwa dni, a drugi raz na godzinę, to takie rozwiązanie powodowałoby, że drugi oczekiwałby bezczynnie przez prawie cały czas swojego działania. Taką sytuację nazywamy zbyt ścisłym powiązaniem procesów i będziemy ją również traktować jak błąd.
Pierwszym klasycznym problemem synchronizacyjnym, chyba najczęściej pojawiającym się w praktyce, jest problem wzajemnego wykluczania. Przypuśćmy, że mamy procesy, z których każdy wykonuje następujący program:
process P;
begin
while true do
begin
własne_sprawy;
protokół_wstępny;
sekcja_krytyczna;
protokół_końcowy;
end
end;
Procedura własne_sprawy to fragment kodu, który nie wymaga żadnych działań synchronizacyjnych. Proces może wykonywać własne sprawy dowolnie długo (nawet nieskończenie długo), może ulec tam awarii. Sekcja_krytyczna to fragment programu, który może być jednocześnie wykonywany przez co najwyżej jeden proces. Zakładamy, że każdy proces, który wchodzi do sekcji krytycznej, w skończonym czasie z niej wyjdzie. Oznacza to w szczególności, że podczas pobytu procesu w sekcji krytycznej nie wystąpi błąd, proces nie zapętli się tam. Zadanie polega na napisaniu protokołu wstępnego i protokołu końcowego tak, aby:
Protokoły wstępny i końcowy konstruuje się korzystając z dostępnych mechanizmów synchronizacyjnych. W przypadku braku jakiegokolwiek wsparcia ze strony systemu operacyjnego należy zastosować jeden z algorytmów synchronizacyjnych, np. algorytm Petersona.
Czasem rozpatruje się też wariant problemu wzajemnego wykluczania, w którym jednocześnie może przebywać więcej procesów. Mamy na przykład N procesów działających, z których w sekcji może przebywać jednocześnie 0<K<N.
W systemie działa P>0 procesów, które produkują pewne dane oraz K>0 procesów, które odbierają dane od producentów. Między producentami a konsumentami może znajdować się bufor o pojemności B, którego zadaniem jest równoważenie chwilowych różnic w czasie działania procesów. Procesy produkujące dane będziemy nazywać producentami, a procesy odbierające dane --- konsumentami. Zadanie polega na synchronizacji pracy producentów i konsumentów, tak aby:
Rozpatruje się różne warianty tego problemu:
Problem producentów i konsumentów jest abstrakcją wielu sytuacji występujących w systemach komputerowych, na przykład zapis danych do bufora klawiatury przez sterownik klawiatury i ich odczyt przez system operacyjny.
W systemie działa C>0 procesów, które odczytują pewne dane oraz P>0 procesów, które zapisują te dane. Procesy zapisujące będziemy nazywać pisarzami, a procesy odczytujące --- czytelnikami, zaś moment, w którym procesy mają dostęp do danych, będziemy nazywać pobytem w czytelni.
Zauważmy, że jednocześnie wiele procesów może odczytywać dane. Jednak jeśli ktoś chce te dane zmodyfikować, to rozsądnie jest zablokować dostęp do tych danych dla wszystkich innych procesów na czas zapisu. Zapobiegnie to odczytaniu niespójnych informacji (na przykład danych częściowo tylko zmodyfikowanych). Ogólny schemat działania procesów jest więc następujący:
process Czytelnik;
begin
repeat
własne_sprawy;
protokół_wstępny_czytelnika;
CZYTANIE;
protokół_końcowy_czytelnika
until false
end
|
process Pisarz;
begin
repeat
własne_sprawy;
protokół_wstępny_pisarza;
PISANIE;
protokół_końcowy_pisarza
until false
end
|
Należy tak napisać protokoły wstępne i końcowe poszczególnych procesów, aby:
Rozpatruje się różne warianty tego problemu:
Wzajemną interakcję czytelników i pisarzy demonstruje poniższy applet[1]:
Ten problem nie ma praktycznych analogii, jak w przypadku poprzednich klasycznych problemów, ale bardzo dobrze ilustruje problemy występujące przy tworzeniu programów współbieżnych.
Pięciu filozofów siedzi przy okrągłym stole. Przed każdym stoi talerz. Między talerzami leżą widelce. Pośrodku stołu znajduje się półmisek z rybą. Każdy filozof myśli. Gdy zgłodnieje sięga po widelce znajdujące się po jego prawej i lewej stronie, po czym rozpoczyna posiłek. Gdy się już naje, odkłada widelce i ponownie oddaje się myśleniu. Schemat działania filozofa jest więc następujący:
process Filozof (i: 0..4);
begin
repeat
myśli;
protokół_wstępny;
je;
protokół_końcowy;
until false
end;
Należy tak napisać protokoły wstępne i końcowe, aby:
Chcemy ponadto, aby każdy filozof działał w ten sam sposób.
Spróbujmy zastanowić się, jak mogłyby wyglądać przykładowe protokoły wstępne i końcowe filozofa. Pierwszy pomysł polega na tym, aby każdy filozof, gdy zgłodnieje, sprawdzał czy widelec po jego lewej stronie jest wolny. Jeśli tak, to filozof powinien podnieść ten widelec i oczekiwać na dostępność drugiego.
Jak widać, po pewnym czasie dochodzi do zakleszczenia (można przyspieszyć jego wystąpienie skracając suwakiem czas jedzenia i rozmyślania filozofów). Dzieje się tak wówczas, gdy filozofowie jednocześnie zgłodnieją i każdy z nich w tej samej chwili podniesie lewy widelec. Każdy oczekuje teraz na prawy widelec, ale nigdy się na niego nie doczeka.
A co stałoby się, jeśli każdy filozof podnosiłby na raz oba widelce, jeśli oba są wolne? Wtedy do zakleszczenia nie dochodzi.
Tym razem doszło do zagłodzenia filozofa. Mamy przykład braku żywotności, różny od zakleszczenia. Jeśli dwaj sąsiedzi pewnego filozofa "zmówią się" przeciw niemu, to mogą nie dopuścić do sytuacji, w której obydwa widelce będą dostępne.
Poprawne rozwiązanie tego problemu przedstawimy w następnym wykładzie.
Rozważając programy współbieżne, możemy analizować dwa modele środowiska, w którym wykonują się procesy.
Taki podział należy przy tym rozważać na płaszczyźnie funkcjonalnej. Możemy na przykład mówić o modelu rozproszonym, choć procesy wykonują się na tym samym komputerze we wspólnej pamięci, która logicznie jest jednak podzielona na niezależne przestrzenie adresowe. Możemy także myśleć o modelu scentralizowanym, choć wspólna pamięć jest tak naprawdę realizowana za pomocą serwera segmentów pamięci dzielonej. Procesy nie muszą znać mechanizmów udostępniania tej pamięci. Z punktu widzenia procesu ważne jest jedynie to, czy istnieje możliwość odczytania/modyfikacji zmiennej współdzielonej, a nie sposób implementacji takiej zmiennej.
Podstawową cechą modelu scentralizowanego jest możliwość stosowania zmiennych, które są dostępne do zapisu i odczytu przez wiele procesów. Takie zmienne będziemy nazywać zmiennymi dzielonymi lub zmiennymi współdzielonymi. Istnienie takich zmiennych w kontekście wykonujących się jednocześnie procesów może powodować pewne problemy. Trzeba na przykład odpowiedzieć na pytanie: co się dzieje, jeśli dwa procesy w tym samym momencie próbują zmodyfikować tę samą komórkę pamięci? Z reguły taki konflikt jest rozstrzygany przez układ sprzętowy, noszący nazwę arbitra pamięci, który w jakiś sposób szereguje takie żądania. Mamy więc gwarancję, że na skutek wykonania takiego "jednoczesnego" przypisania, zmienna dzielona będzie miała jedną z wartości, które próbowano ustawić, a nie jakąś przypadkową nieznaną nam wartość. Własność tę wykorzystaliśmy na poprzednich ćwiczeniach projektując algorytm Petersona.
Obecność zmiennych globalnych powoduje jednak często niezgodne z intuicją zachowania programów współbieżnych.
Rozpatrzmy następujący program, złożony z dwóch identycznych procesów korzystających ze zmiennej współdzielonej x:
var x : integer; | |
process P;
var
y, i: integer;
begin
for i := 1 to 5 do
begin
y := x;
y := y + 1;
x := y
end;
end;
|
process P;
var
y, i: integer;
begin
for i := 1 to 5 do
begin
y := x;
y := y + 1;
x := y
end;
end;
|
Jak widać, każdy z procesów pięciokrotnie:
Skutkiem jest zwiększenie zmiennej współdzielonej o pięć. I faktycznie, jeśli uruchomimy jeden z tych procesów, to tak się stanie. Podobnie jeśli uruchomimy drugi proces P po zakończeniu działania przez pierwszy proces --- wtedy zmienna zwiększy się o 10.
Co jednak zdarzy się, jeśli procesy uruchomimy współbieżnie? Powiedzmy, że początkową wartością zmiennej x jest 0. Jaka będzie wartość końcowa? Otóż okazuje się, że możemy otrzymać, w zależności od przeplotu akcji poszczególnych procesów, dowolną wartość między 5 a 10. Jak pokazuje ten przykład, korzystając ze zmiennych współdzielonych trzeba zachować dużą ostrożność. Omawiany program byłby programem prawidłowo zwiększającym wartość zmiennej współdzielonej, jeśli całe wnętrze pętli było sekcją krytyczną i obliczało się z wzajemnym wykluczaniem (tak się dzieje po zaznaczeniu "Synchronizuj"). Mielibyśmy wówczas pewność, że od chwili odczytania wartości zmiennej x do chwili zapisania jej zmodyfikowanej wartości, żaden proces nie odczyta starej (tj.: jeszcze niezmodyfikowanej) wartości. Ponieważ taka niepodzielność wnętrza pętli wydaje się tu bardzo krytyczna, przeanalizujmy inny przykład.
var x : integer; | |
process P;
var
i: integer;
begin
for i := 1 to 5 do
x := x + 1
end;
|
process P;
var
i: integer;
begin
for i := 1 to 5 do
x := x + 1
end;
|
Tym razem procesy zmieniają wartość zmiennej współdzielonej za pomocą pojedynczej instrukcji wysokopoziomowej. Czy gwarantuje to, że zwiększenie jest realizowane niepodzielnie? Otóż nie, jak wiemy program w języku wysokiego poziomu jest tłumaczony na język wewnętrzy. Programista nie wie, a nawet nie powinien wiedzieć, czy instrukcja x := x + 1 jest realizowana jako jeden rozkaz maszynowy, czy też rozdzielona między rozkazy odczytu pamięci, załadowania wartości do rejestru, zwiększenia rejestru i zapisu do pamięci. Zatem z naszego punktu widzenia powyższy program ma te same właściwości co poprzedni. W dalszym ciągu nie wiemy, jaka będzie końcowa wartość zmiennej x.
Zapamiętajmy. Pisząc program współbieżny nie wolno nic założyć o niepodzielności instrukcji języka, w którym ten program tworzymy.
Model scentralizowany jest trudniejszy dla programisty. Trudniej jest zapewnić poprawność programu współbieżnego korzystającego ze zmiennych współdzielonych. Z tego powodu odłożymy go na później. Już teraz jednak zapowiemy, że wśród omawianych mechanizmów synchronizacyjnych znajdą się semafory, monitory i muteksy.
Model rozproszony stosuje się najczęściej wtedy, gdy procesy składające się na program współbieżny wykonują się na różnych komputerach. Nie ma wtedy fizycznie miejsca, w którym można by składować zmienne współdzielone. Z tego powodu procesy w tym modelu komunikują się wyłącznie poprzez wymianę komunikatów. Jak wspomnieliśmy poprzednio, będziemy także mówić o modelu rozproszonym w sytuacji, gdy procesy działają na tym samym komputerze, ale ich przestrzenie adresowe tworzą logicznie odrębne jednostki i domyślnie procesy nie mogą współdzielić zmiennych globalnych. Takie środowisko wykonania procesów udostępnia m.in. system operacyjny Unix.
W modelu rozproszonym możemy mówić o komunikacji synchronicznej i asynchronicznej. Różne są też modele przekazywania/adresowania komunikatów oraz identyfikacji procesów.
Z komunikacją synchroniczną mamy do czynienia wtedy, gdy chcące się ze sobą skomunikować procesy są wstrzymywane do chwili, gdy komunikacja będzie się mogła odbyć. Omówmy ten schemat na przykładzie procesów, z których jeden (zwany nadawcą) chce wysłać komunikat, a drugi (odbiorca) chce komunikat odebrać.
Przykładem komunikacji synchronicznej jest na przykład rozmowa telefoniczna. Nadawca przekazuje swój komunikat dopiero wówczas, gdy odbiorca chce go wysłuchać. Podobnie sytuacja wygląda na tradycyjnym wykładzie z programowania współbieżnego, gdy wykładowca przekazuje komunikaty mając nadzieję, że docierają one bezpośrednio do odbiorców.
Możliwe są również inne schematy komunikacji synchronicznej, w której bierze udział wiele procesów jednocześnie, nie ograniczając się przy tym jedynie do przesyłania komunikatów.
Komunikacja asynchroniczna nie wymaga współistnienia komunikujących się procesów w tym samym czasie. Polega na tym, że nadawca wysyła komunikat nie czekając na nic. Komunikaty są buforowane w jakimś miejscu (odpowiada za to system operacyjny lub mechanizmy obsługi sieci) i stamtąd pobierane przez odbiorcę.
Mamy więc następujący schemat:
Przykładem komunikacji asynchronicznej są wykłady zdalne, które właśnie czytasz. Nadawca - wykładowca umieścił komunikaty w buforze - Internecie, nie czekając na gotowość odbiorcy - studenta do ich odbioru.
W modelu rozproszonym istnieje też wiele sposobów przekazywania komunikatów.
W ciągu dalszych dwóch wykładów zajmiemy się modelem asynchronicznym. Rozpatrzymy prosty schemat z udziałem bufora i nieco bardziej złożony mechanizm umożliwiający stosowanie tzw. wyboru selektywnego. Zilustrujemy ten mechanizm konkretnymi narzędziami dostępnymi w środowisku Unix.
Przypomnijmy zatem najważniejsze cechy komunikacji asynchronicznej:
W dalszym ciągu wykładu będziemy abstrahować od konkretnych zawiłości technicznych, związanych z realizacją komunikacji asynchronicznej za pomocą konkretnego mechanizmu (na przykład łączy nienazwanych w środowisku Unix). Skupimy się jedynie na istotnych elementach synchronizacyjnych. W tym celu przyjmujemy następujące konwencje:
process P (i: integer); begin ... end
cobegin P(1); P(1); P(2); Q; coend
Problem ten rozwiążemy wprowadzając jeden bufor, do którego początkowo włożymy jeden komunikat. Nie jest przy tym istotne, co jest tym komunikatem, przyjmijmy dla ustalenia uwagi, że jest to dowolna liczba całkowita. Komunikat ten pełni funkcję biletu. Proces, który chce wejść do sekcji krytycznej musi zdobyć bilet, zatrzymuje go przy sobie przez cały czas pobytu w sekcji krytycznej i oddaje po wyjściu z niej. Prowadzi to do następującego programu:
Zmienne globalne:
var buf: buffer; bilet: integer;
Treść procesu:
process P;
var
bilet: integer;
begin
repeat
własne_sprawy;
GetMessage (buf, bilet); { bierzemy bilet }
sekcja_krytyczna;
SendMessage (buf, bilet); { oddajemy bilet }
until false
end;
Program główny:
begin
SendMessage (buf, bilet) { umieszczamy bilet w buforze }
cobegin { i uruchamiamy dwa egzemplarze procesu P }
P; P
coend
end
Własność bezpieczeństwa tego rozwiązania wynika z tego, że jest tylko jeden bilet, a operacje na buforze są niepodzielne. Jeśli pewien proces przebywa w sekcji krytycznej, to w buforze nie ma już biletu, więc drugi proces będzie musiał poczekać na instrukcji GetMessage(buf, bilet).
Żywotność gwarantuje sprawiedliwość operacji GetMessage oraz założenie, że żaden proces, który wszedł do sekcji krytycznej w skończonym czasie z niej wyjdzie. Przypomnijmy, że zakładamy, jak zwykle, sprawiedliwość systemu operacyjnego.
Spróbujmy teraz rozwiązać problem pięciu filozofów. Najpierw musimy się zastanowić, jakie procesy będą potrzebne w rozwiązaniu. Oczywiście musi działać pięć procesów reprezentujących filozofów. Jednak co z widelcami? Tutaj możliwych jest wiele rozwiązań. Zacznijmy od przykładu, w którym każdy widelec jest po prostu komunikatem. Początkowo znajduje się on w odpowiednim buforze, co oznacza, że widelec jest wolny. Buforów musi być jednak tyle, ile widelców, bo każdy filozof podnosi ściśle określone widelce, a nie dowolne. Filozof, który podniesie widelec po prostu wyjmuje komunikat z odpowiedniego bufora i zatrzymuje go, dopóki nie skończy jeść.
Definicje globalne są zatem następujące:
const
N = 5;
var
widelec: array [0..N-1] of buffer;
m: integer; { wartość nieistotna }
Treść filozofa jest bardzo krótka:
process Filozof (i: 0..N-1);
var
m: integer;
begin
repeat
myśli;
GetMessage (widelec[i], m); { podniesienie widelca po lewej stronie }
GetMessage (widelec[(i+1) mod N], m); { podniesienie widelca po prawej stronie }
je;
GetMessage (widelec[i], m); { odłożenie widelca po lewej stronie }
GetMessage (widelec[(i+1) mod N], m); { odłożenie widelca po prawej stronie }
until false;
end
Program główny musi przygotować bufory
begin
for i := 0 to N-1 do
SendMessage (widelec[i], m);
i uruchomić odpowiednią liczbę filozofów:
cobegin
for i := 0 to N-1 do
Filozof (i)
coend
end.
Bardzo łatwo zauważyć, że powyższy program jest implementacją rozwiązania, w którym każdy filozof podnosi najpierw lewy widelec, a następnie prawy. Nie powinno nas zatem dziwić to, że może tu dojść do zakleszczenia. Przypomnijmy, jeśli wszyscy skończą myśleć w tym samym czasie i każdy podniesie lewy widelec, to nigdy nie doczeka się już na prawy.
Spróbujmy teraz postąpić inaczej. Zaimplementujemy widelce jako procesy, a filozofowie będą podnosić widelce w niedeterministycznej kolejności. Implementowanie obiektów statycznych (takich jak widelce, bufory w problemie producentów i konsumentów) w postaci procesów jest dość często stosowane w modelu rozproszonym.
Skoro i filozofowie, i widelce są teraz procesami, musimy opracować pewien protokół do komunikacji między nimi. Kluczowe momenty w działaniu całego systemu to "zgłodnienie" któregoś filozofa oraz zakończenie jedzenia przez filozofa. Filozof musi zawiadomić o zaistnieniu tych faktów, procesy, których mogą one dotyczyć. W tym wypadku będą to sąsiednie widelce. Przyjmijmy więc, że filozof, który kończy jedzenie wysyła do obu widelców, które podniósł komunikat (nazwijmy go OdkładamCię), po odbiorze którego widelec wie, że jest wolny. Z kolei filozof, który zakończy myślenie wysyła do obu widelców komunikat (ChcęCię). Ale to nie wszystko. Czasem filozof będzie musiał poczekać, bo widelec jest zajęty --- je nim inny filozof. Zatem tuż po wysłaniu komunikatu ChcęCię filozof musi zostać wstrzymany w oczekiwaniu na komunikat WeźMnie, wysyłany przez wolny widelec w odpowiedzi na żądanie ChcęCię. Taki schemat żądań (w tym wypadku ChcęCię) i potwierdzeń (WeźMnie) jest dość charakterystyczny dla komunikacji asynchronicznej.
Zastanówmy się jeszcze nad tym, czy i tym razem wystarczy wysłanie komunikatu, czy potrzebna jest jakaś jego treść. Filozof chcący rozpocząć jedzenie wysyła komunikaty do sąsiednich widelców, które --- jeśli są wolne --- muszą na nie odpowiedzieć. Muszą zatem wiedzieć, do kogo wysłać potwierdzenie. Zatem w komunikacie zamawiającym widelec musi pojawić się numer filozofa. W przypadku potwierdzeń nie jest istotna ich treść, a jedynie sam fakt pojawienia się, a w komunikatach zwalniających wystarczy znów jedynie numer filozofa. Widelec, który jest w użyciu odróżni bowiem komunikat zamiawiający od komunikatu zwalniającego --- wystarczy, że będzie pamiętał, kto nim je. Tak więc w omawianym rozwiązaniu nie wystąpią komunikaty ChcęCię i OdkładamCię explicite, lecz będą po prostu komunikaty niosące ze sobą numer nadającego je filozofa.
Do ustalenia schematu komunikacji pozostaje jeszcze kwestia liczby buforów. Zauważmy, że każdy widelec odbiera komunikaty od dwóch filozofów. Nie wie przy tym, w jakiej przyjdą kolejności i powinien być w każdej chwili gotowy zareagować na komunikat od każdego z nich. Ponieważ bezczynny widelec powinien czekać nieaktywnie, więc powinien wykonać operację GetMessage na jakimś buforze. Komunikaty od filozofów powinny być umieszczane właśnie w tym buforze. Prowadzi to naturalnie do rozwiązania, w którym każdy widelec ma własny bufor, gromadzący komunikaty przesyłane do niego. Analogicznie, każdy filozof będzie miał swój bufor, do którego widelce będą wpisywać potwierdzenia.
A oto odpowiadające mu deklaracje zmiennych globalnych:
var
w: array [0..N-1] of buffer { bufory odbiorcze widelców }
f: array [0..N-1] of buffer { bufory odbiorcze filozofów }
Proces filozof działa następująco:
process Filozof (i: 0..4);
var
potw: integer;
begin
repeat
myśli;
SendMessage (w[i], i); { komunikat z numerem filozofa oznaczający ChcęCię }
GetMessage (f[i], potw); { czeka na potwierdzenie }
SendMessage (w[(i+1) mod N], i); { to samo do prawego widelca }
GetMessage (f[i], potw); { czeka na potwierdzenie }
je;
SendMessage (w[i], i); { komunikat z numerem filozofa oznaczający odkładamCię }
SendMessage (w[(i+1) mod N], i); { to samo do prawego widelca }
until false
end;
Proces widelca jest nieco bardziej złożony. Będą w nim potrzebne trzy zmienne lokalne:
Widelec powinien oczekiwać na komunikat. Po jego odbiorze powinien wysłać potwierdzenie do nadawcy, a następnie oczekiwać na dwa kolejne komunikaty. Będą to: komunikat zwalniający, a następnie zamawiający albo odwrotnie: najpierw zamawiający (na który na razie nie odpowiadamy na niego), a potem zwalniający (i wtedy trzeba wysłać potwierdzenie zamawiającemu). W obu przypadkach schemat jest ten sam: oczekujemy na dwa komunikaty, po czym wysyłamy potwierdzenie na zamówienie. Zobaczmy jak schemat ten można zaimplementować w postaci programu wykonywanego przez proces Widelec:
proces Widelec;
var
kto_je, k1, k2: integer;
begin
kto_je := 0; k2 := 0; { inicjacja na dowolne wartości, ale tak aby kto_je = k1 }
repeat
GetMessage (w[i], k1);
if k2 = kto_je then { przy pierwszym obrocie prawda }
kto_je := k1 { zamówienie było od k1 }
else
kto_je := k2; { zamówienie było od k2 }
SendMessage (f[kto_je], i); { potwierdzenie o dowolnej treści }
GetMessage (w[i], k2); { czekamy na komunikat }
until false
end;
Zauważmy, że jeśli pod koniec pętli k2=kto_je, to właśnie odebrany komunikat jest komunikatem zwalniającym i w kolejnym obrocie pętli będzie wykonane kto_je:=k1, bo kolejny komunikat będzie komunikatem zamawiającym. Jeśli jednak pod koniec pętli było kto_je=k1, to ostatnio odebrany komunikat był zamówieniem. Wtedy komunikat odebrany na początku kolejnego obrotu pętli jest zwolnieniem, po którym wykona się kto_je := k2 i zostanie wysłane zaległe potwierdzenie.
Zauważmy jednak, że zaimplementowanie widelców jako procesów nic nie zmieniło. W dalszym ciągu jest to ten sam algorytm powodujący zakleszczenie! Można teraz jednak próbować coś poprawić. Zmieńmy kolejność instrukcji w filozofie:
process Filozof (i: 0..4);
var
potw: integer;
begin
repeat
myśli;
SendMessage (w[i], i); { komunikat z numerem filozofa oznaczający ChcęCię }
SendMessage (w[(i+1) mod N], i); { to samo do prawego widelca }
GetMessage (f[i], potw); { czeka na potwierdzenie }
GetMessage (f[i], potw); { czeka na potwierdzenie }
je;
SendMessage (w[i], i); { komunikat z numerem filozofa oznaczający odkładamCię }
SendMessage (w[(i+1) mod N], i); { to samo do prawego widelca }
until false
end;
Tym razem filozof najpierw zamawia widelce, a potem oczekuje na dwa potwierdzenia. Przyjdą one w nieznanej nam z góry kolejności --- w kolejności zwalniania się widelców. Mamy więc rozwiązanie, w którym kolejność podnoszenia widelcy jest niedeterministyczna: filozof podnosi najpierw ten widelec, który jest wolny.
Czy jednak taka zmiana coś zmienia? Nie, bo w dalszym ciągu możliwy jest ten sam, prowadzący do zakleszczenia przeplot.
Popróbujmy teraz zupełnie odmiennego rozwiązania. Przypuśćmy, że oprócz filozofów działa jeszcze jeden proces Serwer, który zarządza wszystkimi widelcami. Serwer pamięta stan każdego filozofa (a tym samym stan poszczególnych widelców). Każdy filozof może myśleć lub być głodny, gdy skończył myślenie, ale oczekuje na widelce, lub jeść, jeśli ma oba widelce. Tak jak poprzednio filozof informuje o kluczowych zdarzeniach (chęć rozpoczęcia jedzenia i jego zakończenie) oraz przed rozpoczęciem jedzenia oczekuje na potwierdzenie --- tym razem od serwera. Ponieważ filozof wysyła do serwera na zmianę komunikaty zamawiające oraz komunikaty zwalniające, serwer pamiętając stan każdego filozofa będzie wiedział, czego dotyczy komunikat.
A oto deklaracje buforów:
var
serw: buffer; { do serwera }
f: array [0..N-1] of buffer;
I proces filozofa:
process Filozof (i: 0..4);
var
potw: integer;
begin
repeat
myśli;
SendMessage (serw, i); { komunikat z numerem filozofa oznaczający ChcęJeść }
GetMessage (f[i], potw); { czeka na potwierdzenie }
je;
SendMessage (serw, i); { komunikat z numerem filozofa oznaczający odkładamCię }
until false
end;
Cała synchronizacja jest ukryta w procesie serwera:
process Serwer; var stan: array [0..N-1] of (Myśli, Głodny, Je); k: integer;
Wprowadźmy pomocniczą procedurę Sprawdź(k), której zadaniem jest sprawdzenie, czy k-ty filof jest głodny i czy można mu dać oba widelce. Procedura wysyła w takim przypadku potwierdzenie do filozofa o numerze k.
procedure Sprawdź (k: 0..N-1);
begin
if (s[k] = Głodny) and
(s[(k-1) mod N) <> Je and
(s[(k+1) mod N) <> Je then
begin
s[k] := je;
SendMessage (f[k], k) { potwierdzenie o dowolnej treści }
end
end
Właściwa treść filozofa zaczyna się od inicjacji tablicy stanów poszczególnych filozofów:
begin
for k := 0 to N-1 do
stan[k] := Myśli;
W głównej pętli serwera sprawdzamy czy przyszło zamówienie czy zwolnienie i podejmujemy stosowne działania:
repeat
GetMessage (serw, k);
if stan[k] = Myśli then { jest to zamówienie }
begin
stan[k] := Głodny;
Sprawdź (k)
end else
begin
stan[k] := Myśli;
Sprawdź ((k-1) mod N); { być może można obudzić sąsiadów }
Sprawdź ((k+1) mod N)
end
until false;
end;
Tym razem dało się nam uniknąć zakleszczenia. Ale ... No właśnie, mamy rozwiązanie, w którym filozofowie podnoszą oba widelce na raz. Jak widzieliśmy to poprzednio, możemy w ten sposób doprowadzić do zagłodzenia filozofa. Zatem to rozwiązanie jest również niepoprawne.
Powróćmy do pierwszej wersji rozwiązania (tej z zakleszczeniem), ale wprowadźmy dodatkowo "bilety do stołu". Filozof, który zechce jeść, musi najpierw otrzymać jeden z czterech (nie pięciu!) biletów do stołu. Potem postępuje tak jak w rozwiązaniu pierwszym.
const
N = 5;
var
widelec: array [0..N-1] of buffer;
bilety : buffer
m: integer; { wartość nieistotna }
process Filozof (i: 0..N-1);
var
m: integer;
begin
repeat
myśli;
GetMessage (bilety, m);
GetMessage (widelec[i], m); { podniesienie widelca po lewej stronie }
GetMessage (widelec[(i+1) mod N], m); { podniesienie widelca po prawej stronie }
je;
SendMessage (widelec[i], m); { odłożenie widelca po lewej stronie }
SendMessage (widelec[(i+1) mod N], m); { odłożenie widelca po prawej stronie }
SendMessage (bilety, m);
until false;
end
Program główny:
begin
for i := 1 to N-1 do
SendMessage (bilety, m);
for i := 0 to N-1 do
SendMessage (widelec[i], m);
cobegin
for i := 0 to N-1 do
Filozof (i)
coend
end.
Tym razem otrzymujemy rozwiązanie poprawne. Zakleszczenia unikamy, gdyż przy stole może być co najwyżej czterech filozofów jednocześnie. Zatem na pewno któryś z nich otrzyma dwa widelce i będzie mógł jeść.
Zwróćmy uwagę, że taka modyfikacja nie zadziałałaby w przypadku poprzedniego rozwiązania. W przeplocie prowadzącym do zagłodzenia bierze udział bowiem trzech filozofów.
Jak wspomnieliśmy na początku, wprowadzona tu notacja jest abstrakcją rzeczywistych mechanizmów komunikacji asynchronicznej dostępnych na różnych platformach sprzętowych i pod różnymi systemami operacyjnymi. Przyjrzyjmy się teraz niektórym mechanizmom komunikacji asynchronicznej dostępnych dla platformy uniksowej.
Jednym z mechanizmów są łącza nienazwane (ang. pipe). Za pomocą łączy nienazwanych mogą komunikować się ze sobą spokrewnione procesy. Łącza nienazwane to po prostu bufory utrzymywane przez system operacyjny. Są one ograniczone i pojemność każdego z nich wynosi co najmniej 4KB. Odpowiednikiem operacji SendMessage(b, m) jest funkcja systemowa
przy czym b jest deskryptorem przeznaczonym do zapisu do uprzednio utworzonego łącza. Wszystkie właściwości funkcji SendMessage są zachowywane przez funkcję systemową write do łącza. Mamy więc gwarancję niepodzielności, nieblokujące działanie w sytuacji, gdy komunikat mieści się w łączu, dyscyplinę kolejki prostej. Różnice w obsłudze łącza ujawniają się przy próbie zapisu do łącza, gdy komunikat nie mieści się w nim w całości. Wtedy nadawca jest wstrzymywany (z pewnymi wyjątkami, szczegóły na ćwiczeniach). Odpowiednikiem funkcji GetMessage (b, m) jest funkcja systemowa
przy czym b jest deskryptorem przeznaczonym do odczytu z uprzednio utworzonego łącza. I tak jak w przypadku GetMessage funkcja systemowa read powoduje wstrzymanie procesu wykonującego ją, jeśli łącze jest puste.
Tak jak w przypadku abstrakcyjnej notacji, komunikacja za pomocą łączy nakłada na programistę obowiązek dbania o zgodność typów komunikatów wysyłanych i odbieranych. W przypadku łączy komunikat to po prostu strumień bajtów, który programista interpretuje w dogodny dla siebie sposób.
Oczywiście użycie łączy wymaga odpowiednich technicznych zabiegów, na przykład utworzenia go za pomocą funkcji systemowej pipe(fd), której wynikiem jest para deskryptorów fd, z których jeden służy do zapisywania do łącza, a drugi do odczytu z niego. Istnieją też pewne ograniczenia, np. nie można zapisywać do łącza, które nie jest przez nikogo otwarte do odczytu. Gdyby pominąć jednak wszystkie technikalia, to programowanie za pomocą łączy przypomina programowanie za pomocą mechanizmu abstrakcyjnego.
Podobnym do łączy nienazwanych mechanizmem dostępnym w środowisku uniksowym jest mechanizm łączy nazwanych. Tak jak w przypadku łączy nienazwanych takie łącza należy najpierw utworzyć (funkcja mkfifo). Następnie korzysta się z nich za pomocą funkcji systemowych read i write. W przypadku stosowania łączy nazwanych istnieją dodatkowe możliwości synchronizacji procesów na etapie otwierania łącza do odczytu i zapisu.
Trzecim popularnym mechanizmem komunikacji asynchronicznej stosowanym w systemie Unix są kolejki komunikatów. I znów są to bufory utrzymywane przez system operacyjny, do których procesy mogą zapisywać komunikaty (funkcja systemowa sndmsg) i z których komunikaty odbierają (funkcja getmsg). I tak jak poprzednio, są to kolejki komunikatów, choć istnieje również możliwość traktowania ich jak kolejek priorytetowych lub wręcz wyboru selektywnego - komunikaty mogą mieć typy, po których dokonuje się selekcji. Funkcja wysłania komunikatu w normalnych warunkach jest nieblokująca, a funkcje odbierająca wstrzymuje proces usiłujący pobrać coś z pustej kolejki. W odróżnieniu od łączy odbiór i wysyłanie komunikatów odbywa się tu jednak nie na poziomie strumieni bajtów, lecz całych komunikatów.
Inne podejście do asynchronicznego modelu komunikacji zaproponował w latach osiemdziesiątych Gelernter. Wprowadził on notację o nazwie Linda, która udostępnia tzw. przestrzeń krotek, czyli coś w rodzaju nieskończonego bufora, za pomocą którego porozumiewają się ze sobą procesy. Jest jedna wielka, globalna przestrzeń krotek. Procesy porozumiewają się ze sobą, umieszczając w przestrzeni krotek komunikaty i pobierając je z niej. Procesy nie muszą wiedzieć nic o sobie nawzajem, co więcej, mogą nie istnieć w tym samym czasie. Nadawca może odebrać komunikat od procesu, który już dawno zakończył swoje działanie.
Każdy komunikat przesyłany przez procesy to tzw. krotka.
Przykładami krotek są:
Każda krotka ma statycznie określoną długość. Nie może tworzyć krotek o dynamicznie zmienianej bądź wyliczanej długości. Typy poszczególnych elementów krotki mogą być dowolne typy proste lub typy złożone (tablice, rekordy). Nie ma jednak typu, którego wartościami byłyby krotki, więc krotka nie może być elementem krotki.
Sygnaturą krotki ('c', true, 3.14, "żeton") jest na przykład (char, boolean, real, string). W niektórych operacjach na przestrzeni krotek wymaga się podania sygnatury krotki.
Linda nie jest tak naprawdę językiem programowania, ale raczej czymś w rodzaju biblioteki oferującej pewne operacje na przestrzeni krotek. Są to:
Omówimy teraz po kolei powyższe operacji.
Ponieważ Linda jest rozproszonym mechanizmem asynchronicznym z nieograniczonym buforem, więc operacja wstawiania krotki do przestrzeni jest operacją nieblokującą. Ma ona postać
i w jej wyniku krotka t zostaje umieszczona w przestrzeni krotek. Jeśli taka krotka już się w niej znajdowała, to zostanie umieszczony kolejny egzemplarz takiej samej krotki. Przestrzeń krotek należy traktować jak multizbiór, a nie zwykły zbiór krotek . Przykładowa operacja Output ('c', "ala", 4, 3.14) wstawi do przestrzeni krotek krotkę ('c', "ala", 4, 3.14) o sygnaturze (char, string, integer, real).
Do wyjmowania krotki z przestrzeni krotek służą dwie procedury blokujące:
Argumentem obu tej procedury jest sygnatura krotki, na przykład:
wyjmuje z przestrzeni krotek krotkę o sygnaturze integer, char. Jeśli w danej chwili krotki o podanej sygnaturze nie ma w przestrzeni krotek, to proces wykonujący procedurę Input jest wstrzymywany tak długo, aż żądana krotka pojawi się w przestrzeni krotek. Na skutek wykonania operacji Input z przestrzeni krotek jest usuwana jedna krotka o podanej sygnaturze, a poszczególne jej elementy są przypisywane na zmienne występujące w opisie sygnatury. W omawianym przykładzie pierwszy element krotki zostanie przypisany na zmienną x a drugi na zmienną c.
Jeśli w przestrzeni krotek jest wiele krotek o podanej sygnaturze, to wybór usuwanej krotki jest niedeterministyczny. Niedeterminizm ten jest jednak ograniczany zasadą sprawiedliwości: jeśli operacja Input z podaną sygnaturą jest wykonywana nieskończenie często, to w końcu każda krotka o tej sygnaturze zostanie wyjęta z przestrzeni krotek.
Podobna zasada obowiązuje przy budzeniu procesów oczekujących na operacji Input. Jeśli na krotkę o pewnej sygnaturze czeka ich wiele i krotka pojawi się w przestrzeni, to wznawiany jest któryś z oczekujących procesów. Nie można zatem zakładać, że oczekujące procesy są kolejkowane, ale można oczekiwać sprawiedliwości. Mamy gwarancję, że jeśli krotka pojawi się nieskończenie wiele razy w przestrzeni, to każdy z oczekujących procesów w końcu zostanie obudzony.
Procedura Read jest operacją bardzo podobną do Input. Jedyna różnica polega na tym, że krotka nie jest usuwana z przestrzeni krotek. Podobnie jak w przypadku Input proces wykonujący Read oczekuje aż w przestrzeni zjawi się krotka o podanej sygnaturze. Również procesy oczekujące są budzone w sposób sprawiedliwy.
Zauważmy, że po pojawieniu się krotki o sygnaturze, na którą czekają procesy wykonujące Read, mogą zostać obudzone wszystkie procesy oczekujące, bo każdy z nich jedynie odczytuje krotkę z przestrzeni pozostawiając ją tam. Jeśli jednak na taką samą krotkę oczekują procesy i na operacji Read i na operacji Input, to wtedy na skutek niederministycznego wyboru budzonych procesów możliwe są różne sytuacje. Może zdarzyć się tak, że zostanie obudzony tylko jeden proces oczekujący na Input, może też obudzić się kilka (niekoniecznie wszystkie) procesy czekające na operacji Read, a po nich dopiero proces oczekujący na Input.
Oprócz omówionych procedur, do wyjmowania/odczytywania krotek z przestrzeni krotek można wykorzystać dwie funkcje logiczne:
Funkcje te działają dokładnie tak jak ich blokujące odpowiedniki: Input oraz Read z tym, że jeśli krotki o podanej sygnaturze nie ma w przestrzeni krotek, to proces nie jest wstrzymywany, a funkcje przekazują natychmiast w wyniku wartość false. Jeśli udało się pobrać/odczytać krotkę, to wynikiem jest wartość true.
Wersji nieblokujących można używać do sprawdzania, czy krotka o podanej sygnaturze w danej chwili znajduje się w przestrzeni krotek. Należy jednak przy tym uważać. Fragment programu:
if Try_Read (x:integer) then Input (x: integer);
nie oznacza, że proces nie zostanie zatrzymany na operacji Input. W chwili wykonywania operacji Try_Read (x) w przestrzeni krotek mogła bowiem znajdować się jakaś krotka o sygnaturze (integer), ale zanim proces rozpoczął wykonanie Input, krotka ta mogą zostać usunięta przez inny wykonujący się współbieżnie proces.
Istotnym rozszerzeniem omawianego mechanizmu jest możliwość wykonywania tzw. wyboru selektywnego. Polega on na możliwości wyspecyfikowania wartości konkretnych elementów krotki, którą chcemy wyjąć/odczytać z przestrzeni krotek. Przykładowo można zażyczyć sobie wyjęcia z przestrzeni krotek krotki o sygnaturze (integer, char, integer), której pierwszym elementem jest wartość 3. Odpowiednia instrukcja wygląda następująco:
Zwróćmy uwagę na bardzo ważną rolę, jaką gra składnia w Lindzie. Porównajmy następujące wywołania procedury Input:
| Input (x, c) | Input (x: integer, c) | Input (x, c: char) | Input (x: integer, c: char) |
Ostatnie z nich jest żądaniem wyjęcia dowolnej krotki o sygnaturze (integer, char) i zapisania wartości poszczególnych składowych wyjmowanej krotki w zmiennych x oraz c. Pozostałe wywołania to wybór selektywny. W pierwszym przypadku chcemy wyjąć z przestrzeni krotek krotkę, której pierwszy element ma wartość taką jak aktualna wartość zmiennej x, a drugi element jest równy co do wartości zmiennej c. Drugie i trzecie wywołanie to wybór selektywny odpowiednio po drugiej i pierwszej współrzędnej. Na przykład Input (x: integer, c) oznacza wyjęcie z przestrzeni krotek krotki, której druga współrzędna ma wartość taką jak zmienna c, a pierwsza współrzędna jest dowolną liczbą całkowitą, którą zapamiętujemy w zmiennej x.
Wybór selektywny jest bardzo przydatny i upraszcza rozwiązanie wielu problemów synchronizacyjnych. Należy jednak pamiętać o tym, że tak naprawdę jest on dość ograniczony. Nie można na przykład bezpośrednio zrealizować wyjęcia z przestrzeni krotek krotki, której dane elementy spełniają dowolny warunek logiczny. Selektywość jest ograniczana jedynie do sprawdzania równości podanych elementów krotki.
W lindzie wprowadzone jeszcze jedno rozszerzenie. W przestrzeni krotek mogą znajdować się krotki "dziurawe". Dziura to "wartość" określonego typu, która "pasuje" do dowolnej innej wartości tego typu. Dziury będziemy w dalszej części oznaczać gwiazdką wraz z typem. Na przykład krotka:
jest krotką o sygnaturze
zawierającą dwie dziury: na drugiej i czwartej pozycji. Taką krotkę można pobrać z przestrzeni krotek wykonując każdą z następujących operacji:
| Input (3, 'c', x: char, 8) | Input (i: integer, x: char, 'a', j: integer) |
W tym drugim przypadku wartość zmiennej j jest nieokreślona. Zauważmy, że nawet krotki dziurawe mają jednoznacznie określoną sygnaturę, tj. każda dziura ma typ.
Do umieszczanie w przestrzeni krotek krotek z dziurą służy także procedura Output. W miejscu dziury podajemy po prostu sygnaturę (z nazwą zmiennej, która jednak nie ma tu znaczenia):
umieści w przestrzeni krotek krotkę, która na drugiej współrzędnej ma dziurę.
Projektując program współbieżny w Lindzie, będziemy zakładać, że procesy wchodzące w jego skład są jedynymi procesami korzystającymi z przestrzeni krotek. Metoda postępowania jest przy tym następująca:
Spróbujmy zaprojektować schemat komunikacji między procesami za pomocą przestrzeni krotek. W tym celu przyjmijmy, że każdy proces ma jednoznaczny identyfikator typu integer. Załóżmy, że przestrzeń krotek jest początkowo pusta, a w trakcie działania procesów będą pojawiać się w niej krotki postaci:
przy czym definicja typu Komunikat wynika z konkretnego zastosowania.
W przestrzeni krotek będzie zawsze przebywać co najwyżej jedna krotka postaci (c: integer). Jest to licznik czytelników przebywających w czytelni. Pisarz wchodząc do czytelni zabiera krotkę i oddaje ją dopiero po zakończeniu pisania. Zatem w trakcie pisania przestrzeń krotek jest pusta. Początkowo w przestrzeni krotek umieszczamy krotkę (0). Treści poszczególnych procesów są teraz natychmiastowe:
process Czytelnik;
var
c: integer;
begin
repeat
własne_sprawy;
Input (c: integer);
Output (c+1);
CZYTANIE;
Input (c: integer);
Output (c-1);
until false
end;
|
process Pisarz;
begin
repeat
własne_sprawy;
Input (0);
PISANIE;
Output (0);
until false
end;
|
Przedstawione rozwiązanie ma własność bezpieczeństwa. Gorzej jest z żywotnością. Pisarz, który chce rozpocząć pisanie, musi poczekać aż nikogo nie będzie w czytelni. Do takiej sytuacji może jednak nigdy nie dojść, gdyż nowy czytelnik może zawsze dołączyć do przebywających w czytelni.
Zauważmy, że jeśli pisarz wejdzie do czytelni, to po jego wyjściu w przestrzeni krotek pojawi się krotka 0. Może ją pobrać albo kolejny pisarz, albo któryś z oczekujących czytelników. Co się dokładnie stanie --- nie wiemy, gdyż działa niedeterminizm. Mamy jednak gwarancję, że jeśli tylko nieskończenie wiele razy będzie się pojawiać krotka 0, to każdy z oczekujących procesów ją w końcu weźmie. Problem w tym wypadku polega jednak na tym, że taka krotka może się w ogólne nie pojawić (poza sytuacją początkową).
process Czytelnik;
var
c: integer;
begin
repeat
własne_sprawy;
Input (c: integer, 0);
Output (c+1, 0);
CZYTANIE;
Input (c: integer, p: integer);
Output (c-1, p);
until false
end;
|
process Pisarz;
begin
repeat
własne_sprawy;
Input (c: integer, 0);
Output (c, 1);
PISANIE;
Output (0, 0);
until false
end;
|
Przypomnijmy podstawowe cechy komunikacji synchronicznej. Procesy synchronizują ze sobą: nadawca czeka z wysłaniem do momentu, aż odbiorca będzie gotowy do odbioru i na odwrót: odbiorca jest wstrzymywany na instrukcji odbioru do chwili, aż sterowanie w nadawcy dojdzie do instrukcji wysłania.
Czasem trudno jest jednak wprowadzić jednoznaczne rozgraniczenie na proces nadający i odbierający, gdyż w czasie pojedynczej synchronizacji procesów może dojść do wymiany komunikatów w obie strony. Tak właśnie dzieje się to w Adzie.
Mechanizm synchronizacyjny udostępniany przez Adę to tzw. spotkania albo randki. W spotkaniu uczestniczą dwa (lub więcej) procesy, które w Adzie noszą nazwę zadań. Zacznijmy od omówienia randki między dwoma zadaniami.
Spośród zadań uczestniczących w randce jedno jest zadaniem aktywnym, a drugie zadaniem pasywnym. Zadanie aktywne inicjuje randkę, ale w czasie jej trwania nie robi nic. Zadanie pasywne jest zadaniem, które udostępnia pewne wejścia. Wejścia te mogą być wywoływane przez zadanie aktywne, które chce zainicjować randkę. Gdy dojdzie do randki, zadanie pasywne zajmuje się jej obsługą, wykonując określony fragment programu, podczas gdy zadanie aktywne jest wstrzymywane w oczekiwaniu na zakończenie randki.
Zadania w Adzie składają się z dwóch części. Pierwsza część to tzw. specyfikacja zadania. Specyfikacja określa jakie wejścia są udostępniane przez zadanie i jakie są ich argumenty. Właściwa treść zadania jest określona w osobnym fragmencie kodu.
Zacznijmy zatem od specyfikacji zadania.
Każde zadanie może udostępniać na zewnątrz pewne wejścia. Są to jakby "procedury", które mogą być wywołane przez inne zadania i realizowane "w ich imieniu" przez zadanie bierne. Każde wejście ma nazwę i, jeśli jest taka potrzeba, parametry. Te same zasady dotyczą zresztą procedur. Każdy parametr w Adzie specyfikuje się, podając jego identyfikator, typ oraz sposób przekazania. Są trzy sposoby przekazywania parametrów w Adzie:
Kierunek przekazywania parametrów jest zawsze określany z punktu widzenia specyfikowanego procesu. Przypuśćmy na przykład, że chcemy rozwiązać problem producentów i konsumentów. Chcemy, aby producenci umieszczali wyprodukowane dane w buforze, skąd pobierają je konsumenci. Pierwsze pytanie, na jakie musimy odpowiedzieć to jak zaimplementować bufor? Zastosujemy dość standardową technikę w modelu rozproszonym, wprowadzając dodatkowy proces. Proces ten o nazwie Bufor będzie procesem biernym zarówno przy komunikacji z producentem, jak i konsumentem. Wynika to z tego, że bufor nie ma żadnej możliwości stwierdzenia, kiedy przechowywana przez niego informacja będzie potrzebna konsumentowi, ani kiedy ma skomunikować się z producentem w celu odebrania od niego kolejnej porcji danych. To producent i konsument są stronami inicjującymi spotkanie.
Wyspecyfikujmy więc zadanie Bufor z dwoma wejściami:
Odpowiedni fragment kodu wygląda tak:
task Bufor is entry Weź (x: in Integer); entry Daj (x: out Integer); end Bufor;
Zauważmy, że parametr wejścia Weź jest wejściowy, bo to wywołujący przekazuje liczbę całkowitą do włożenia do bufora. Analogicznie parametr wejścia Daj jest wyjściowy, bo za jego pomocą proces aktywny dostaje liczbę z bufora.
Jak wygląda randka w Adzie? Aby w ogóle do niej doszło, proces aktywny musi wywołać pewne wejście udostępniane przez proces pasywny. Przykładowo, konsument wywołuje wejście Daj bufora za pomocą instrukcji:
przy czym x jest pewną zmienną lokalną konsumenta, na której zostanie zapisana odczytana z bufora liczba.
Wywołanie wejścia zadania biernego powoduje wstrzymanie procesu wywołującego aż do chwili, gdy sterowanie w procesie biernym dotrze do specjalnej instrukcji akceptującej. Proces wywołujący jest przy tym wstrzymywany w kolejce związanej z danym wejściem. Gdy sterowanie w zadaniu biernym dochodzi do instrukcji akceptującej --- jej składnię omówimy za chwilę --- dochodzi do randki między zadaniem biernym a zadaniem aktywnym znajdującym się na początku kolejki zadań oczekujących na danym wejściu. Należy od razu zwrócić uwagę, że może zdarzyć się także inny scenariusz. Sterowanie w procesie biernym może dojść do instrukcji akceptującej wejście, zanim zostanie ono wywołane przez jakiekolwiek zadanie aktywne. Jak przystało na model synchroniczny, zadanie bierne jest wtedy również wstrzymywane do chwili wywołania wejścia przez jakieś zadanie.
Sama randka ma następujący przebieg:
Z powyższego opisu wynika, że zadanie aktywne po przekazaniu parametrów do zadania biernego pozostaje bezczynne aż do końca randki. Na taki mechanizm można więc patrzeć jak na zwykłe wywołanie procedury, z tym że procedura jest wykonywana nie przez wywołującego, lecz przez inny proces. Zadanie aktywne to wywołujący, który po wywołaniu czeka aż zadanie bierne wykona treść procedury i przekaże wartości wynikowe i dopiero wznawia wykonanie.
Kluczową instrukcją w opisywanym mechanizmie jest instrukcja akceptująca. Ma ona następującą składnię:
accept <nazwa wejścia> (<parametry>) do <ciąg instrukcji>; end <nazwa wejścia>;
W trakcie spotkania wykonują się wszystkie instrukcje między accept a end. Jeśli ten ciąg jest pusty, to można użyć uproszczonej składni pisząc:
accept <nazwa wejścia>;
Popatrzmy jak taki mechanizm można wykorzystać do realizacji wzajemnego wykluczania dwóch procesów. Napiszmy proces Serwer z dwoma wejściami:
task Serwer is entry Chce; entry Zwalnia; end Serwer;
task body Serwer is
loop
accept Chce;
accept Zwalniam;
end loop;
end Serwer;
Jak widać serwer działa w pętli nieskończone, którą w Adzie zapisuje się w postaci loop ... end loop. W pętli na przemian wykonuje instrukcję akceptującą wejście Chce i instrukcję akceptującą wejście Zwalniam. W efekcie serwer najpierw chce koniecznie zaakceptować proces wywołujący wejście Chce. Gdy jednak już dojdzie do randki (pustej), to serwer przechodzi do kolejnej instrukcji, którą jest accept Zwalniam. Czeka zatem na tej instrukcji aż ktoś --- a może to być jedynie proces, który zwalnia sekcję krytyczną, wywoła wejście Zwalniam nie reagując na wywoływanie wejścia Chce.
Czasami zachodzi potrzeba zawieszania zadania przyjmującego w oczekiwaniu na zajście jednego z wielu zdarzeń. Stosujemy wtedy specjalną instrukcję select, której składnia jest następująca:
select
when warunek1 => accept wejście1 do
instrukcje-w-trakcie-randki;
end wejście1;
instrukcje-poza-randką;
or
when warunek2 => accept wejście2 do
instrukcje-w-trakcie-randki;
end wejście2;
instrukcje-poza-randką;
...
else
instrukcje;
end select;
Poszczególne elementy tej konstrukcji, oddzielane od siebie za pomocą słów kluczowych or nazywa się gałęziami. Ostatnia gałąź (po słowie kluczowym else) jest opcjonalna i można ją pominąć. Każda gałąź składa się z dozoru, instrukcji accept oraz instrukcji wykonywanych poza randką. Każdy z tych trzech elementów, z wyjątkiem instrukcji akceptującej, jest opcjonalny i w pewnych okolicznościach można go pominąć. I tak, dozór zbudowany ze słowa kluczowego when warunku logicznego oraz strzałki => pomija się, jeśli warunek jest zawsze prawdziwy (czyli jest nim po prostu true). Instrukcję poza ranką pomija się jeśli jest ona pusta.
Działanie instrukcji select omówimy przyjmując najpierw, że po else nie ma żadnych instrukcji. Jej wykonanie przebiega wówczas w następujących krokach:
W przypadku obecności części z else działanie instrukcji select jest nieco inne. Różnice w stosunku do powyższego opisu są przy tym następujące:
W przedstawionym powyżej opisie działania instrukcji select występuje ważne zjawisko: niedeterminizm. Jeśli są procesy oczekujące na wejściach znajdujących się w różnych gałęziach otwartych, to rozpoczynamy randkę na wejściu z niedeterministycznie wybranej gałęzi otwartej. Należy jednak pamiętać, że niedetermizm dotyczy wyboru gałęzi, a nie procesu oczekującego w kolejce związanej z wejściem występującym w tej gałęzi.
Niedeterminizm, o którym mowa, nie jest jednak niczym nieograniczony. Zachowujemy, tak jak było to w przypadku Lindy, warunek sprawiedliwości. Zakładamy mianowicie, że jeśli instrukcja select jest wykonywana nieskończenie wiele razy (na przykład w pętli) oraz pewna gałąź z niepustą kolejką jest otwarta nieskończenie wiele razy, to w końcu zostanie ona wybrana do wykonania. Takie założenia pozwala uzyskać żywotność rozwiązań zapisanych w Adzie.
Omawiając instrukcję select należy zwrócić uwagę na jeszcze jeden element. Otóż w Adzie istnieje możliwość sprawdzenia, ile procesów oczekuje na danym wejściu. Służy do tego konstrukcja o następującej składni:
wejście'count
Będziemy mówić, że count jest atrybutem wejścia, przekazującym liczbę procesów aktualnie oczekujących na tym wejściu.
Oto zapis w Adzie rozwiązania problemu producentów i konsumentów. Wejścia są udostępniane jedynie przez proces implementujący bufor (cykliczny i ograniczony). Jedno Weź służy do wstawiania porcji do bufora, a drugie Daj do odbierania ich z bufora.
task Bufor is entry Weź (x: in Integer); entry Daj (x: out Integer); end Bufor;
Procesy producenta i konsumenta nie udostępniają wejść. Ponieważ chcemy mieć dużo producentów (niech ich liczba wynosi P, gdzie P jest pewną z góry ustaloną stałą), i dużo (K) konsumentów, więc uwzględniamy to w specyfikacji zadań w następujący sposób:
task Producent (1..P) is end Producent;
task Konsument (1..K) is end Konsument;
Zapiszmy najpierw treść producenta i konsumenta:
task body Producent is
liczba: Integer;
loop
produkuj (liczba);
Bufor.Weź (liczba);
end loop
end Producent;
task body Konsument is
liczba: Integer;
loop
Bufor.daj (liczba);
konsumuj (liczba);
end loop
end Konsument;
Treść procesu bufor jest nieco bardziej złożona. Porcje będziemy pamiętać w tablicy indeksowanej od 0 do B-1, gdzie B jest pewną stałą oznaczającą pojemność bufora. Będziemy ponadto pamiętać pozycję w tablicy, na której znajduje się pierwsza liczba do wyjęcia oraz liczbę elementów w buforze:
task body Bufor is pierwsza: integer := 0; ile : integer := 0; buf: array [0..B-1] of Integer;
Bufor działa w pętli nieskończonej. Ponieważ nie da się przewidzieć w jakiej kolejności będą nadchodzić zlecenia od producenta i konsumenta bufor powinien być prawie zawsze gotowy do komunikacji z każdym z nich. No właśnie: prawie zawsze. Nie można bowiem przyjąć kolejnej porcji od producenta, jeśli w buforze nie ma już wolnego miejsca oraz nie można wysłać nic konsumentowi, jeśli bufor jest pusty. Daje to następujący fragment kodu:
loop
select
when ile <> 0 =>
accept Daj (x: out Integer) do
x := buf[pierwsza];
ile := ile - 1;
pierwsza := (pierwsza + 1) mod B;
end Daj;
or
when ile <> B =>
accept Weź (x: in Integer) do
buf[(pierwsza+ile) mod B] := x;
ile := ile + 1;
end Weź;
end select;
end loop;
end Bufor;
Zwróćmy uwagę, że ten sam efekt można uzyskać zmieniając nieco kolejność instrukcji:
loop
select
when ile <> 0 =>
accept Daj (x: out Integer) do
x := buf[pierwsza];
end Daj;
ile := ile - 1;
pierwsza := (pierwsza + 1) mod B;
or
when ile <> B =>
accept Weź (x: in Integer) do
buf[(pierwsza+ile) mod B] := x;
end Weź;
ile := ile + 1;
end select;
end loop;
end Bufor;
Powyższe dwa programy mają tę samą funkcjonalność, oba są poprawne, a różnią się jednym szczegółem. W pierwszym modyfikacja wszystkich zmiennych bufora odbywa się podczas nieaktywności producenta/konsumenta. W drugim producent i konsument są wstrzymywani jedynie na czas przekazywania wyprodukowanej porcji. Modyfikacja zmiennych bufora odbywa się już po wznowieniu działania producenta/konsumenta, czyli poza randką. Otrzymujemy w ten sposób rozwiązanie bardziej efektywne.
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?
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.
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:
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()]
]
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:
[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
]
]
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
]
]
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ć.
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?
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.
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:
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()]
]
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:
[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
]
]
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
]
]
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ć.
Przechodzimy teraz do mechanizmów synchronizacji w systemach ze wspólną pamięcią. Model ten różni się od dotychczasowych przede wszystkim tym, że można stosować zmienne współdzielone, czyli dostępne dla wielu procesów, i za ich pomocą wymieniać informacje.
Korzystanie ze zmiennych współdzielonych wymaga jednak dużej ostrożności, jak widzieliśmy to podczas pierwszego wykładu. Niekontrolowane niczym modyfikowanie takich zmiennych w wielu procesach jednocześnie może dawać niedające się przewidzieć efekty. Z tego powodu większość z omawianych w dalszym ciągu mechanizmów gwarantuje atomowość lub niepodzielność pewnych operacji.
W dalszej części wykładu omówimy szczegółowo dwie metody synchronizacji procesów w środowisku scentralizowanym: semafory i monitory. Wspomnimy także o mechanizmie zamków (muteksów). Zanim jednak to nastąpi na przykładzie wzajemnego wykluczania wspomnijmy o dwóch innych metodach synchronizacji.
Pierwsza z tym metod jest stosowana wtedy, gdy nie dysponujemy żadnym wsparciem ani ze strony sprzętu ani oprogramowania. Korzystając jedynie z wysokopoziomowych instrukcji języka programowania można zapewnić wzajemne wykluczanie w dostępie do sekcji krytycznej za pomocą m.in. algorytmu Petersona. Jego dokładne omówienie znalazło się w materiałach dotyczących pierwszych ćwiczeń. Przypomijmy jego wady: statycznie znana liczba procesów, koszt, a przede wszystkim aktywne oczekiwanie.
Czasem możemy liczyć na wsparcie sprzętowe. Może to być na przykład specjalny rozkaz maszynowy realizujący niepodzielny zapis i odczyt. Rozpatrzmy dla przykładu rozkaz Test_and_Set, który odczytuje pewien bit G i ustawia go na jeden. Działanie takiego rozkazu można by zapisać w wysokopoziomowym języku następująco:
procedure Test_and_Set (var L: 0..1);
{ Ta procedura jest atomowa! }
begin
L := G;
G := 1;
end
Problem wzajemnego wykluczania można wówczas rozwiązać następująco:
var wolny: 0..1 := 0;
process P;
var
i: 0..1;
begin
repeat
własne_sprawy;
repeat
Test_and_Set (i);
until i = 0;
sekcja_krytyczna;
wolny := 0;
until false
end;
To rozwiązanie także nie jest pozbawione wad. Pierwszą z nich jest oczywiście aktywne oczekiwanie, drugą możliwość zagłodzenia procesu.
Omówienie mechanizmów udostępnianych programowo rozpoczniemy od semaforów. Semafor jest to abstrakcyjny typ danych, na którym można wykonywać jedynie dwie operacje:
Powyższe operacje są niepodzielne i wzajemnie się wykluczają. Ponadto semafor można raz, poza procesami, zainicjować na dowolną wartość nieujemną.
O semaforze myślimy jak o pewnej zmiennej całkowitej o wartościach nieujemnych. Programista nie ma jednak dostępu do wartości tej zmiennej (poza początkową inicjacją), a operacje na niej wykonuje za pomocą operacji P i V. Ich działanie można zdefiniować na dwa sposoby.
Klasyczna definicja semafora definiuje semantykę operacji P następująco:
P(S): zaczekaj aż wartość semafora S będzie dodatnia; zmniejsz S o 1
Jeśli semafor S ma od razu wartość większą niż 0, to operacja P nie wstrzymuje wywołującego ją procesu. Jeśli S ma wartość równą 0, to proces wykonujący P jest wstrzymywany w sposób nieangażujący procesora. W czasie, gdy proces oczekuje inne procesy mogą rozpocząć wykonanie operacji P (i zostaną także wstrzymane) lub też wykonać operację V (co, jak za chwilę zobaczymy, powoduje zwiększenie wartości zmiennej semaforowej i w konsekwencji może doprowadzić do obudzenia jednego z oczekujących na operacji P procesów).
Operację V definiuje się po prostu tak:
V(S): S := S + 1
Powyższe definicje wymagają kilku wyjaśnień. Niepodzielność instrukcji V jest zrozumiała: zwiększenie semafora ma się po prostu odbyć w jednym kroku. Co jednak oznacza niepodzielność instrukcji P? Jeśli proces rozpoczyna wykonanie tej operacji i zastaje dodatnią wartość semafora, to zmniejsza jego wartość o 1, a niepodzielność gwarantuje, że operacja ta zostanie wykonana w całości zanim inny proces rozpocznie wykonanie V lub P. Jeśli jednak proces zastanie semafor równy zero to jest wstrzymany. Niepodzielność P nie gwarantuje zatem tego, że proces, który rozpoczął jej wykonanie zakończy je bez wstrzymania swojego działania. Jednak proces wstrzymany oddaje dostęp do operacji P i V, dzięki czemu inny proces może zwiększyć semafor. Któryś z oczekujących procesów (jeden z nich) może "zauważyć" tę zmianę (nie zajmujemy się sposobem implementacji tego mechanizmu) i wznowić wykonanie operacji P. I tutaj ponownie korzystamy z niepodzielności, która gwarantuje, że proces zmniejszy wartość semafora zanim ktokolwiek inny rozpocznie wykonanie P lub V.
Podkreślmy raz jeszcze: P i V to jedyne operacje na semaforze. W szczególności nie ma możliwości sprawdzenia wartości zmiennej semaforowej!.
Operacja V może spowodować obudzenie jednego spośród procesów oczekujących na semaforze. Definicja nie precyzuje jednak, który to będzie proces. Nie można w szczególności założyć, że procesy oczekują na semaforze w kolejce. Aby zapewnić żywotność programów korzystających z semaforów przyjmuje się jednak pewne założenie dotyczące oczekiwania: jest ono sprawiedliwe. Każdy proces oczekujący zostanie w skończonym czasie obudzony, jeśli tylko semafor zostanie podniesiony dostatecznie dużo razy.
W dalszym ciągu wykładu będziemy mówić, że semafor jest zamknięty, jeśli wartość zmiennej semaforowej wynosi 0, w przeciwnym razie semafor będziemy nazywać otwartym. Sformułowanie przejść pod semaforem będzie oznaczać zakończenie wykonania operacji P, a podniesienie semafora to wykonanie na nim operacji V.
Czasem wpowadza się nieco inną definicję operacji P i V:
P(S): jeśli S > 0, to S := S - 1, w przeciwnym razie wstrzymaj działanie
V(s): jeśli są procesy oczekujące na S, to obudź jeden z nich, w przeciwnym razie S := S + 1
Podstawowa różnica polega na tym, że w definicji uproszczonej nie podnosi się semafora, jeśli są procesy oczekujące. Zamiast tego proces wykonujący operację V budzi jeden z nich. Semafor zostanie podniesiony jedynie wówczas, gdy nikt pod nim nie czeka. Pozostałe założenia dotyczące niepodzielności, atomowości i sprawiedliwości operacji semaforowej pozostają w mocy.
Nazwy operacji semaforowych pochodzą z języka holenderskiego:
Pojawiające się w literaturze nazwu wait i signal rezerwujemy dla operacji na zmiennych warunkowych.
Szczególnym przypadkiem semafora jest semafor binarny. Przyjmuje on jedynie wartość 0 lub 1 (zamknięty lub otwarty), a operacje na nim wykonuje się następująco:
P(S): jeśli S > 0, to S := 0, w przeciwnym razie wstrzymaj działanie
V(S): jeśli są procesy oczekujące na S, to obudź jeden z nich, w przeciwnym razie S := 1
Semafor binarny jest oszczędniejszy pamięciowo niż semafor ogólny, gdyż wymaga tylko jednego bitu.
Zauważmy, że powyższa definicja semafora binarnego powoduje, że otwarcie otwartego semafora binarnego nie ma żadnego efektu. Może to prowadzić do subtelnych błędów w programach. Dlatego też niektórzy przyjmują, że operacja V na otwartym semaforze binarnym powoduje błąd.
Semafory będziemy deklarować używając typu semaphore lub binary semaphore. Deklaracje będziemy umieszczać poza procesami. Semafory będą inicjowane od razu w miejscu deklaracji.
Rozwiązanie problemu wzajemnego wykluczania jest bardzo proste:
mutex: binary semaphore := 1;
process P;
begin
repeat
własne_sprawy;
P (mutex);
sekcja_krytyczna;
V (mutex)
until false
end
Jeśli dostęp do sekcji krytycznej może uzyskać jednocześnie co najwyżej k procesów (dla k > 1), zastosujemy semafory ogólne:
mutex: semaphore := k;
process P;
begin
repeat
własne_sprawy;
P (mutex);
sekcja_krytyczna;
V (mutex)
until false
end
Przypuśćmy, że mamy typ danych Bufor z operacjami Wstaw i Pobierz, implementujący bufor o pojemności N. Chcemy za pomocą semaforów rozwiązać problem wielu producentów i wielu konsumentów dbając o właściwą synchronizację dostępu do bufora.
W tym celu wprowadzimy trzy semafory. Semafor mutex będzie dbać o wzajemne wykluczanie operacji na buforze (nie można jednocześnie wstawiać danych do bufora, żeby dane nie trafiły na to samo miejsce). Oprócz tego za pomocą semafora wolne będziemy "zliczać" wolne miejsca w buforze, a za pomocą semafora zajęte --- będziemy zliczać zajęte miejsca. Przyjmijmy, że bufor jest początkowo pusty. Naturalnym sposobem inicjacji semaforów jest:
mutex: binary semaphore := 1; wolne: semaphore := N; zajete: semaphore := 0; b: Buffer;
Producent przed wstawieniem danych do bufora musi się upewnić, że w buforze jest miejsce. Jeśli tak, to liczba wolnych miejsc się zmniejszy, a zwiększy się liczba miejsc zajętych. Naturalne jest więc zaimplementowanie producenta w następujący sposób:
process Producent;
var
x: integer;
begin
repeat
produkuj (x);
P (wolne);
P (mutex);
wstaw (b, x);
V (mutex);
V (zajete)
until false;
end
Proces konsumenta jest symetryczny:
process Konsument;
var
x: integer;
begin
repeat
P (zajete);
P (mutex);
x := pobierz (b);
V (mutex);
V (wolne)
until false;
end
W dotychczasowych rozważaniach wprowadziliśmy semafory ogólne i binarne. Powstaje naturalne pytanie, który z tych mechanizmów ma większą siłę wyrazu. Czy program zapisany z wykorzystaniem semaforów binarnych daje się zapisać korzystając jedynie z semaforów ogólnych (i być może dodatkowych "zwykłych" zmiennych) i na odwrót.
Ponieważ każdy semafor binarny jest zarazem semaforem ogólny, więc zamiast semaforów binarnych można zawsze użyć semaforów ogólnych (zakładamy, że nie dochodzi do próby otwarcia otwartego semafora binarnego). Również program korzystający z semaforów ogólnych daje się napisać z użyciem semaforów ogólnych i pewnych dodatkowych zmiennych, jednak stwierdzenie tego faktu nie jest już tak oczywiste.
Aby się o tym przekonać dokonajmy "symulacji" semafora ogólnego S za pomocą zmiennej całkowitej N oraz dwóch semaforów binarnych mutex i delay. Symulacja polega na zaimplementowaniu operacji P(S) oraz V (S) za pomocą operacji na semaforach mutex i delay i zmiennej całkowitej N.
Aby zaimplementować operację P(S) musimy umieć odczytać wartość zmiennej semaforowej. To jednak jest niemożliwe. Dlatego też wartość tę będziemy pamiętać na zmiennej N. Tak naprawdę zmienna ta będzie pełnić dwie funkcje. Jeśli jest dodatnia, to zapamiętuje wartość zmiennej semaforowej, jeśli jest ujemna, to jej wartość bezwzględna oznacza liczbę procesów oczekujących pod semaforem N.
Początkowe wartości poszczególnych zmiennych są następujące:
var mutex: binary semaphore := 1; delay: binary semaphore := 0; N := początkowa wartość symulowanego semafora S
Operację P(S) implementujemy następująco:
P (mutex); N := N - 1; if N <= -1 then begin V (mutex); P (delay) end else V (mutex);
Przyjrzyjmy się tej procedurze. Opuszczenie semafora ogólnego S ma być atomowe i wykluczać się z innymi operacjami na tym semaforze. Procedura zaczyna się więc od zamknięcia semafora mutex, gwarantującego wzajemne wykluczania. Następnie jest zmniejszana zmienna N. Jeśli na skutek tego zmniejszenia otrzyma ona wartość ujemną, to znaczy, że semafor jest zamknięty. Zgodnie z przedstawionymi intuicjami wartość -N oznacza wtedy liczbę procesów oczekujących, więc zmniejszenie N jest uzasadnione. W takiej sytuacji proces musi jednak poczekać. W tym celu wykonuje operację P na zamkniętym semaforze delay. Ale zanim to uczyni musi podnieść semafor mutex, aby otworzyć dostęp do operacji P(S) i V(S) dla innych procesów (gdybyśmy nie podnieśli semafora mutex doszłoby do zakleszczenia)!
Jeśli semafor był otwarty, to proces kontynuuje swoje działanie bez oczekiwania, więc nie wykonuje operacji P(delay) a jedynie V(mutex).
Operacja V(S) wygląda następująco:
P (mutex); N := N + 1; if N <= 0 then V (delay); V (mutex);
I znów semafor mutex dba o wzajemne wykluczanie i niepodzielność. Zwiększenie zmiennej N jest potrzebne niezależnie od tego czy przed semaforem nikt nie czekał (N >= 0) i w związku z tym trzeba zwiększyć wartość zmiennej semaforowej (czyli zwiększyć N), czy też były procesy oczekujące (N < 0) i jeden z nich należy obudzić, czyli zmniejszyć wartość -N (zwiększając N). Jeśli jednak N było początkowo mniejsze niż zero, to trzeba obudzić jeden z procesów oczekujących na semaforze delay --- stąd operacja V(delay).
Ta z pozoru sensowna symulacja zawiera jednak pewien subtelny błąd. Aby go znaleźć prześledźmy symulację następującego programu:
var S: semaphore := 2;
proces P(i: 1..4);
begin
własne_sprawy;
P (S);
sekcja_krytyczna;
V (S)
end
Widzimy, że jest to rozwiązanie problemu wzajemnego wykluczania, przy czym w sekcji krytycznej mogą przebywać jednocześnie co najwyżej dwa procesy.
Przepiszmy powyższy program zastępując operacje na semaforze S ich implementacją:
var N: integer := 2; mutex : binary semaphore := 1; delay : binary semaphore := 0;
proces P(i: 1..4);
begin
własne_sprawy;
P (mutex);
N := N - 1;
if N <= -1 then
begin
V (mutex);
P (delay) {*}
end else
V (mutex);
sekcja_krytyczna;
P (mutex);
N := N + 1;
if N <= 0 then V (delay);
V (mutex);
end
Przypuśćmy, że do sekcji krytycznej usiłują wejść dwa procesy: P(1) i P(2). Oczywiście udaje im się to. Zmienna N zostaje zmniejszona o 2 ma więc wartość 0, semafor delay jest nadal zamknięty, a mutex otwarty. Popatrzmy, co się stanie, jeśli proces P(3) będzie usiłował wejść do sekcji krytycznej. Zamyka on semafor mutex, zmniejsza N o 1 stwierdza, że N = -1 więc podnosi semafor mutex i ma się zawiesić na semaforze delay. Jest to zgodne z oczekiwaniami, gdyż sekcja krytyczna jest już zajęta przez dwa procesy. Przypuśmy jednak, że zanim proces zawiesi się w wierszu oznaczonym * analogiczny ciąg instrukcji wykona proces P(4). Mamy wówczas następującą sytuację:
Procesy P(1) i P(2) są w sekcji krytycznej. Procesy P(3) i P(4) są tuż przed wykonaniem instrukcji (*). Zmienna N ma wartość -2. Semafor mutex jest otwarty. Semafor delay jest zamknięty.
Przypuśmy, że teraz procesy P(1) i P(2) po kolei wychodzą z sekcji krytycznej. Proces P(1) zamyka semafor mutex , zwiększa N o jeden na -1, wykonuje operację V (delay) i V(mutex). Sytuacja jest następująca:
Proces P(2) jest w sekcji krytycznej. Procesy P(3) i P(4) są tuż przed wykonaniem instrukcji (*). Zmienna N ma wartość -1. Semafor mutex jest otwarty. Semafor delay jest otwarty.
Teraz proces P(2) wykonuje analogiczny fragment kodu: zamyka semafor mutex, zwiększa N o 1 i ... podnosi semafor delay! Ale semafor ten jest już otwarty. W zależności od semantyki powoduje to błąd lub nie daje efektu. Przypuśćmy, że nic się nie zmienia. Proces P(2) kontynuuje otwierając semafor mutex, co prowadzi do:
Procesy P(3) i P(4) są tuż przed wykonaniem instrukcji (*). Zmienna N ma wartość 0. Semafor mutex jest otwarty. Semafor delay jest otwarty.
Teraz swoje działanie kontynuuje proces P(3). Wykonuje operację P (delay) i wchodzi do sekcji krytycznej:
Proces P(3) jest w sekcji krytycznej. Proces P(4) jest tuż przed wykonaniem instrukcji (*). Zmienna N ma wartość 0. Semafor mutex jest otwarty. Semafor delay jest zamknięty.
Gdy proces P(4) spróbuje kontynuować swoje działanie, to wykona operację P(delay) i zostanie wstrzymany, mimo że w sekcji krytycznej jest jeszcze miejsce!. Pokazaliśmy zatem scenariusz ilustrujący błędne (to znaczy niezgodne z oryginalnym programem) działanie symulacji.
Opisaną powyżej symulację na szczęście można łatwo poprawić. Zaskakujący jest przy tym sposób ---- z pozoru bezsensowny, a w rzeczywistości prowadzący do ważnej techniki konstruowania programów wykorzystujących semafory.
Zestawmy dotychczasową implementację operacji P(S) i V(S) z nową, poprawną wersją:
własne_sprawy; P (mutex); N := N - 1; if N <= -1 then begin V (mutex); P (delay) end else V (mutex); sekcja_krytyczna; P (mutex); N := N + 1; if N <= 0 then V (delay); V (mutex); |
własne_sprawy; P (mutex); N := N - 1; if N <= -1 then begin V (mutex); P (delay) end; V (mutex); sekcja_krytyczna; P (mutex); N := N + 1; if N <= 0 then V (delay) else V (mutex); |
Przyjrzyjmy się implementacji operacji P(S):
P (mutex); N := N - 1; if N <= -1 then begin V (mutex); P (delay) end; V (mutex);
Jeśli warunek jest spełniony, to semafor mutex jest zamykany raz a otwierany dwukrotnie! Analogicznie w V(S):
P (mutex); N := N + 1; if N <= 0 then V (delay) else V (mutex);
może się zdarzyć opuszczenie semafora mutex bez jego podniesienia!
Pomimo tego implementacja jest poprawna. Przyjrzyjmy się bliżej zastosowanemu trikowi, który polega na założeniu, że proces budzony z semafora delay zastanie zamknięty semafor mutex. Przy takim założeniu jasna staje się konieczność bezwarunkowego podniesienia semafora mutex na końcu operacji P(S). Z drugiej strony w kodzie operacji V(S) należy zagwarantować, że obudzony proces faktycznie zastanie opuszczony semafor mutex. Aby to zapewnić w implementacji V(S) mutex jest podnoszony jedynie wówczas, gdy nikogo nie budzimy. Jeśli jednak podnosimy semafor delay, to mutex pozostaje zamknięty --- właśnie po to aby proces obudzony z semafora delay zastał zamknięty semafor mutex.
Co daje taka technika? Wyjaśnijmy to na przykładzie scenariusza, który prowadził do błędnego działania poprzedniej symulacji. Zacznijmy od sytuacji, w której procesy P(1) i P(2) są już w sekcji krytycznej, a P(3) i P(4) tuż przed zawieszeniem się na operacji P(delay). Semafor mutex jest otwarty, a semafor delay --- zamknięty. Zmienna N ma wartość -2. Przypuśćmy, że proces P(1) wychodzi teraz z sekcji krytycznej. Zamyka semafor mutex, zwiększa zmienną N na -1 i podnosi semafor delay. Ale mutex pozostaje zamknięty! Z tego powodu zanim proces P(2) będzie mógł rozpocząć wykonanie kodu za swoją sekcją krytyczną, któryś z procesów P(3) lub P(4) (albo oba) muszą wykonać operację V(delay). Ponieważ delay jest w tym momencie otwarty, więc jeden z procesów przejdzie przez niego, zamykając go za sobą i wykona operację V(mutex). Dopiero wtedy dostęp do fragmentów kodu chronionych semaforem mutex staje się otwarty, a scenariusz powodujący błędne działanie poprzedniej symulacji nie jest już możliwy.
Opisaną technikę w ogólności można ująć w następujący schemat. Zawieszanie procesu realizujemy w następujący sposób (dodatkowa zmienna ile_czeka zlicza ile procesów oczekuje na początkowo zamkniętym semaforze sem:
P(mutex);
...
if warunek then
begin
ile_czeka := ile_czeka + 1;
V(mutex);
P(sem); { obudzony proces zastanie zamknięty mutex }
ile_czeka := ile_czeka -1
...
end;
...
V(mutex)
Budzenie procesu realizujemy następująco:
P(mutex) ... if ile_czeka > 0 then V (sem) else V (mutex)
Opisana technika nosi nazwę dziedziczenia sekcji krytycznej, bo budzony z semafora sem proces dziedziczy wyłączny dostęp do sekcji krytycznej chronionej semaforem mutex po procesie budzącym. Umiejętne stosowanie tej techniki pozwala ograniczyć liczbę możliwych przeplotów i uniknąć wielu błędów synchronizacyjnych poprzez wymuszenie niepodzielności akcji budzenia i wznowienia działania przez proces obudzony.
Przechodzimy teraz do mechanizmów synchronizacji w systemach ze wspólną pamięcią. Model ten różni się od dotychczasowych przede wszystkim tym, że można stosować zmienne współdzielone, czyli dostępne dla wielu procesów, i za ich pomocą wymieniać informacje.
Korzystanie ze zmiennych współdzielonych wymaga jednak dużej ostrożności, jak widzieliśmy to podczas pierwszego wykładu. Niekontrolowane niczym modyfikowanie takich zmiennych w wielu procesach jednocześnie może dawać niedające się przewidzieć efekty. Z tego powodu większość z omawianych w dalszym ciągu mechanizmów gwarantuje atomowość lub niepodzielność pewnych operacji.
W dalszej części wykładu omówimy szczegółowo dwie metody synchronizacji procesów w środowisku scentralizowanym: semafory i monitory. Wspomnimy także o mechanizmie zamków (muteksów). Zanim jednak to nastąpi na przykładzie wzajemnego wykluczania wspomnijmy o dwóch innych metodach synchronizacji.
Pierwsza z tym metod jest stosowana wtedy, gdy nie dysponujemy żadnym wsparciem ani ze strony sprzętu ani oprogramowania. Korzystając jedynie z wysokopoziomowych instrukcji języka programowania można zapewnić wzajemne wykluczanie w dostępie do sekcji krytycznej za pomocą m.in. algorytmu Petersona. Jego dokładne omówienie znalazło się w materiałach dotyczących pierwszych ćwiczeń. Przypomijmy jego wady: statycznie znana liczba procesów, koszt, a przede wszystkim aktywne oczekiwanie.
Czasem możemy liczyć na wsparcie sprzętowe. Może to być na przykład specjalny rozkaz maszynowy realizujący niepodzielny zapis i odczyt. Rozpatrzmy dla przykładu rozkaz
Test_and_Set, który odczytuje pewien bit G i ustawia go na jeden. Działanie takiego rozkazu można by zapisać w wysokopoziomowym języku następująco:
procedure Test_and_Set (var L: 0..1);
{ Ta procedura jest atomowa! }
begin
L := G;
G := 1;
end
Problem wzajemnego wykluczania można wówczas rozwiązać następująco:
var
wolny: 0..1 := 0;
process P;
var
i: 0..1;
begin
repeat
własne_sprawy;
repeat
Test_and_Set (i);
until i = 0;
sekcja_krytyczna;
wolny := 0;
until false
end;
To rozwiązanie także nie jest pozbawione wad. Pierwszą z nich jest oczywiście aktywne oczekiwanie, drugą możliwość zagłodzenia procesu.
Omówienie mechanizmów udostępnianych programowo rozpoczniemy od semaforów. Semafor jest to abstrakcyjny typ danych, na którym można wykonywać jedynie dwie operacje:
Powyższe operacje są niepodzielne i wzajemnie się wykluczają.
Ponadto semafor można raz, poza procesami, zainicjować na dowolną wartość nieujemną.
O semaforze myślimy jak o pewnej zmiennej całkowitej o wartościach nieujemnych. Programista nie ma jednak dostępu do wartości tej zmiennej (poza początkową inicjacją), a operacje na niej wykonuje za pomocą operacji P i V. Ich działanie można zdefiniować na dwa sposoby.
Klasyczna definicja semafora definiuje semantykę operacji P następująco:
P(S):
zaczekaj aż wartość semafora S będzie dodatnia;
zmniejsz S o 1
Jeśli semafor S ma od razu wartość większą niż 0, to operacja P nie wstrzymuje wywołującego ją procesu. Jeśli S ma wartość równą 0, to proces wykonujący P jest wstrzymywany w sposób nieangażujący procesora. W czasie, gdy proces oczekuje inne procesy mogą rozpocząć wykonanie operacji P (i zostaną także wstrzymane) lub też wykonać operację V (co, jak za chwilę zobaczymy, powoduje zwiększenie wartości zmiennej semaforowej i w konsekwencji może doprowadzić do obudzenia jednego z oczekujących na operacji P procesów).
Operację V definiuje się po prostu tak:
V(S):
S := S + 1
Powyższe definicje wymagają kilku wyjaśnień. Niepodzielność instrukcji V jest zrozumiała: zwiększenie semafora ma się po prostu odbyć w jednym kroku. Co jednak oznacza niepodzielność instrukcji P? Jeśli proces rozpoczyna wykonanie tej operacji i zastaje dodatnią wartość semafora, to zmniejsza jego wartość o 1, a niepodzielność gwarantuje, że operacja ta zostanie wykonana w całości zanim inny proces rozpocznie wykonanie V lub P. Jeśli jednak proces zastanie semafor równy zero to jest wstrzymany. Niepodzielność P nie gwarantuje zatem tego, że proces, który rozpoczął jej wykonanie zakończy je bez wstrzymania swojego działania. Jednak proces wstrzymany oddaje dostęp do operacji P i V, dzięki czemu inny proces może zwiększyć semafor. Któryś z oczekujących procesów (jeden z nich) może "zauważyć" tę zmianę (nie zajmujemy się sposobem implementacji tego mechanizmu) i wznowić wykonanie operacji P. I tutaj ponownie korzystamy z niepodzielności, która gwarantuje, że proces zmniejszy wartość semafora zanim ktokolwiek inny rozpocznie wykonanie P lub V.
Podkreślmy raz jeszcze: P i V to jedyne operacje na semaforze. W szczególności nie ma możliwości sprawdzenia wartości zmiennej semaforowej!.
Operacja V może spowodować obudzenie jednego spośród procesów oczekujących na semaforze. Definicja nie precyzuje jednak, który to będzie proces. Nie można w szczególności założyć, że procesy oczekują na semaforze w kolejce. Aby zapewnić żywotność programów korzystających z semaforów przyjmuje się jednak pewne założenie dotyczące oczekiwania: jest ono sprawiedliwe. Każdy proces oczekujący zostanie w skończonym czasie obudzony, jeśli tylko semafor zostanie podniesiony dostatecznie dużo razy.
W dalszym ciągu wykładu będziemy mówić, że semafor jest zamknięty, jeśli wartość zmiennej semaforowej wynosi 0, w przeciwnym razie semafor będziemy nazywać otwartym. Sformułowanie przejść pod semaforem będzie oznaczać zakończenie wykonania operacji P, a podniesienie semafora to wykonanie na nim operacji V.
Czasem wpowadza się nieco inną definicję operacji P i V:
P(S):
jeśli S > 0, to S := S - 1, w przeciwnym razie wstrzymaj działanie
V(s):
jeśli są procesy oczekujące na S, to obudź jeden z nich, w przeciwnym razie
S := S + 1
Podstawowa różnica polega na tym, że w definicji uproszczonej nie podnosi się semafora, jeśli są procesy oczekujące. Zamiast tego proces wykonujący operację V budzi jeden z nich. Semafor zostanie podniesiony jedynie wówczas, gdy nikt pod nim nie czeka. Pozostałe założenia dotyczące niepodzielności, atomowości i sprawiedliwości operacji semaforowej pozostają w mocy.
Nazwy operacji semaforowych pochodzą z języka holenderskiego:
Pojawiające się w literaturze nazwu wait i signal rezerwujemy dla operacji na zmiennych warunkowych.
Szczególnym przypadkiem semafora jest semafor binarny. Przyjmuje on jedynie wartość 0 lub 1 (zamknięty lub otwarty), a operacje na nim wykonuje się następująco:
P(S):
jeśli S > 0, to S := 0, w przeciwnym razie wstrzymaj działanie
V(S):
jeśli są procesy oczekujące na S, to obudź jeden z nich, w przeciwnym razie
S := 1
Semafor binarny jest oszczędniejszy pamięciowo niż semafor ogólny, gdyż wymaga tylko jednego bitu.
Zauważmy, że powyższa definicja semafora binarnego powoduje, że otwarcie otwartego semafora binarnego nie ma żadnego efektu. Może to prowadzić do subtelnych błędów w programach. Dlatego też niektórzy przyjmują, że operacja V na otwartym semaforze binarnym powoduje błąd.
Semafory będziemy deklarować używając typu semaphore lub binary semaphore. Deklaracje będziemy umieszczać poza procesami. Semafory będą inicjowane od razu w miejscu deklaracji.
Rozwiązanie problemu wzajemnego wykluczania jest bardzo proste:
mutex: binary semaphore := 1;
process P;
begin
repeat
własne_sprawy;
P (mutex);
sekcja_krytyczna;
V (mutex)
until false
end
Jeśli dostęp do sekcji krytycznej może uzyskać jednocześnie co najwyżej k procesów (dla k > 1), zastosujemy semafory ogólne:
mutex: semaphore := k;
process P;
begin
repeat
własne_sprawy;
P (mutex);
sekcja_krytyczna;
V (mutex)
until false
end
Przypuśćmy, że mamy typ danych Bufor z operacjami Wstaw i Pobierz, implementujący bufor o pojemności N. Chcemy za pomocą semaforów rozwiązać problem wielu producentów i wielu konsumentów dbając o właściwą synchronizację dostępu do bufora.
W tym celu wprowadzimy trzy semafory. Semafor mutex będzie dbać o wzajemne wykluczanie operacji na buforze (nie można jednocześnie wstawiać danych do bufora, żeby dane nie trafiły na to samo miejsce). Oprócz tego za pomocą semafora wolne będziemy "zliczać" wolne miejsca w buforze, a za pomocą semafora zajęte --- będziemy zliczać zajęte miejsca. Przyjmijmy, że bufor jest początkowo pusty. Naturalnym sposobem inicjacji semaforów jest:
mutex: binary semaphore := 1;
wolne: semaphore := N;
zajete: semaphore := 0;
b: Buffer;
Producent przed wstawieniem danych do bufora musi się upewnić, że w buforze jest miejsce. Jeśli tak, to liczba wolnych miejsc się zmniejszy, a zwiększy się liczba miejsc zajętych. Naturalne jest więc zaimplementowanie producenta w następujący sposób:
process Producent;
var
x: integer;
begin
repeat
produkuj (x);
P (wolne);
P (mutex);
wstaw (b, x);
V (mutex);
V (zajete)
until false;
end
Proces konsumenta jest symetryczny:
process Konsument;
var
x: integer;
begin
repeat
P (zajete);
P (mutex);
x := pobierz (b);
V (mutex);
V (wolne)
until false;
end
W dotychczasowych rozważaniach wprowadziliśmy semafory ogólne i binarne. Powstaje naturalne pytanie, który z tych mechanizmów ma większą siłę wyrazu. Czy program zapisany z wykorzystaniem semaforów binarnych daje się zapisać korzystając jedynie z semaforów ogólnych (i być może dodatkowych "zwykłych" zmiennych) i na odwrót.
Ponieważ każdy semafor binarny jest zarazem semaforem ogólny, więc zamiast semaforów binarnych można zawsze użyć semaforów ogólnych (zakładamy, że nie dochodzi do próby otwarcia otwartego semafora binarnego). Również program korzystający z semaforów ogólnych daje się napisać z użyciem semaforów ogólnych i pewnych dodatkowych zmiennych, jednak stwierdzenie tego faktu nie jest już tak oczywiste.
Aby się o tym przekonać dokonajmy "symulacji" semafora ogólnego S za pomocą zmiennej całkowitej N oraz dwóch semaforów binarnych mutex i delay. Symulacja polega na zaimplementowaniu operacji P(S) oraz V (S) za pomocą operacji na semaforach mutex i delay i zmiennej całkowitej N.
Aby zaimplementować operację P(S) musimy umieć odczytać wartość zmiennej semaforowej. To jednak jest niemożliwe. Dlatego też wartość tę będziemy pamiętać na zmiennej N.
Tak naprawdę zmienna ta będzie pełnić dwie funkcje. Jeśli jest dodatnia, to
zapamiętuje wartość zmiennej semaforowej, jeśli jest ujemna, to jej wartość bezwzględna oznacza liczbę procesów oczekujących pod semaforem N.
Początkowe wartości poszczególnych zmiennych są następujące:
var
mutex: binary semaphore := 1;
delay: binary semaphore := 0;
N := początkowa wartość symulowanego semafora S
Operację P(S) implementujemy następująco:
P (mutex);
N := N - 1;
if N <= -1 then
begin
V (mutex);
P (delay)
end else
V (mutex);
Przyjrzyjmy się tej procedurze. Opuszczenie semafora ogólnego S ma być atomowe i wykluczać się z innymi operacjami na tym semaforze. Procedura zaczyna się więc od zamknięcia semafora mutex, gwarantującego wzajemne wykluczania. Następnie jest zmniejszana zmienna N. Jeśli na skutek tego zmniejszenia otrzyma ona wartość ujemną, to znaczy, że semafor jest zamknięty. Zgodnie z przedstawionymi intuicjami wartość -N oznacza wtedy liczbę procesów oczekujących, więc zmniejszenie N jest uzasadnione.
W takiej sytuacji proces musi jednak poczekać. W tym celu wykonuje operację P na zamkniętym semaforze delay. Ale zanim to uczyni musi podnieść semafor mutex, aby otworzyć dostęp do operacji P(S) i V(S) dla innych procesów (gdybyśmy nie podnieśli semafora mutex doszłoby do zakleszczenia)!
Jeśli semafor był otwarty, to proces kontynuuje swoje działanie bez oczekiwania, więc nie wykonuje operacji P(delay) a jedynie V(mutex).
Operacja V(S) wygląda następująco:
P (mutex);
N := N + 1;
if N <= 0 then V (delay);
V (mutex);
I znów semafor mutex dba o wzajemne wykluczanie i niepodzielność. Zwiększenie zmiennej N jest potrzebne niezależnie od tego czy przed semaforem nikt nie czekał (N >= 0) i w związku z tym trzeba zwiększyć wartość zmiennej semaforowej (czyli zwiększyć N), czy też były procesy oczekujące (N < 0) i jeden z nich należy obudzić, czyli zmniejszyć wartość -N (zwiększając N). Jeśli jednak N było początkowo mniejsze niż zero, to trzeba obudzić jeden z procesów oczekujących na semaforze delay --- stąd operacja V(delay).
Ta z pozoru sensowna symulacja zawiera jednak pewien subtelny błąd. Aby go znaleźć prześledźmy symulację następującego programu:
var
S: semaphore := 2;
proces P(i: 1..4);
begin
własne_sprawy;
P (S);
sekcja_krytyczna;
V (S)
end
Widzimy, że jest to rozwiązanie problemu wzajemnego wykluczania, przy czym w sekcji krytycznej mogą przebywać jednocześnie co najwyżej dwa procesy.
Przepiszmy powyższy program zastępując operacje na semaforze S ich implementacją:
var
N: integer := 2;
mutex : binary semaphore := 1;
delay : binary semaphore := 0;
proces P(i: 1..4);
begin
własne_sprawy;
P (mutex);
N := N - 1;
if N <= -1 then
begin
V (mutex);
P (delay) {*}
end else
V (mutex);
sekcja_krytyczna;
P (mutex);
N := N + 1;
if N <= 0 then V (delay);
V (mutex);
end
Przypuśćmy, że do sekcji krytycznej usiłują wejść dwa procesy: P(1) i P(2). Oczywiście udaje im się to. Zmienna N zostaje zmniejszona o 2 ma więc wartość 0, semafor delay jest nadal zamknięty, a mutex otwarty. Popatrzmy, co się stanie, jeśli proces P(3) będzie usiłował wejść do sekcji krytycznej. Zamyka on semafor mutex, zmniejsza N o 1 stwierdza, że N = -1 więc podnosi semafor mutex i ma się zawiesić na semaforze delay. Jest to zgodne z oczekiwaniami, gdyż sekcja krytyczna jest już zajęta przez dwa procesy. Przypuśmy jednak, że zanim proces zawiesi się w wierszu oznaczonym * analogiczny ciąg instrukcji wykona proces P(4). Mamy wówczas następującą sytuację:
Procesy P(1) i P(2) są w sekcji krytycznej.
Procesy P(3) i P(4) są tuż przed wykonaniem instrukcji (*).
Zmienna N ma wartość -2.
Semafor mutex jest otwarty.
Semafor delay jest zamknięty.
Przypuśmy, że teraz procesy P(1) i P(2) po kolei wychodzą z sekcji krytycznej. Proces P(1) zamyka semafor mutex , zwiększa N o jeden na -1, wykonuje operację V (delay) i V(mutex). Sytuacja jest następująca:
Proces P(2) jest w sekcji krytycznej.
Procesy P(3) i P(4) są tuż przed wykonaniem instrukcji (*).
Zmienna N ma wartość -1.
Semafor mutex jest otwarty.
Semafor delay jest otwarty.
Teraz proces P(2) wykonuje analogiczny fragment kodu: zamyka semafor mutex, zwiększa N o 1 i ... podnosi semafor delay! Ale semafor ten jest już otwarty. W zależności od semantyki powoduje to błąd lub nie daje efektu. Przypuśćmy, że nic się nie zmienia.
Proces P(2) kontynuuje otwierając semafor mutex, co prowadzi do:
Procesy P(3) i P(4) są tuż przed wykonaniem instrukcji (*).
Zmienna N ma wartość 0.
Semafor mutex jest otwarty.
Semafor delay jest otwarty.
Teraz swoje działanie kontynuuje proces P(3). Wykonuje operację P (delay) i wchodzi do sekcji krytycznej:
Proces P(3) jest w sekcji krytycznej.
Proces P(4) jest tuż przed wykonaniem instrukcji (*).
Zmienna N ma wartość 0.
Semafor mutex jest otwarty.
Semafor delay jest zamknięty.
Gdy proces P(4) spróbuje kontynuować swoje działanie, to wykona operację P(delay) i zostanie wstrzymany, mimo że w sekcji krytycznej jest jeszcze miejsce!. Pokazaliśmy zatem scenariusz ilustrujący błędne (to znaczy niezgodne z oryginalnym programem) działanie symulacji.
Opisaną powyżej symulację na szczęście można łatwo poprawić. Zaskakujący jest przy tym sposób ---- z pozoru bezsensowny, a w rzeczywistości prowadzący do ważnej techniki konstruowania programów wykorzystujących semafory.
Zestawmy dotychczasową implementację operacji P(S) i V(S) z nową, poprawną wersją:
|
własne_sprawy; P (mutex); N := N - 1; if N <= -1 then begin V (mutex); P (delay) end else V (mutex); sekcja_krytyczna; P (mutex); N := N + 1; if N <= 0 then V (delay); V (mutex); |
własne_sprawy; P (mutex); N := N - 1; if N <= -1 then begin V (mutex); P (delay) end; V (mutex); sekcja_krytyczna; P (mutex); N := N + 1; if N <= 0 then V (delay) else V (mutex); |
Przyjrzyjmy się implementacji operacji P(S):
P (mutex);
N := N - 1;
if N <= -1 then
begin
V (mutex);
P (delay)
end;
V (mutex);
Jeśli warunek jest spełniony, to semafor mutex jest zamykany raz a otwierany dwukrotnie! Analogicznie w V(S):
P (mutex);
N := N + 1;
if N <= 0 then V (delay) else
V (mutex);
może się zdarzyć opuszczenie semafora mutex bez jego podniesienia!
Pomimo tego implementacja jest poprawna. Przyjrzyjmy się bliżej zastosowanemu trikowi, który polega na założeniu, że proces budzony z semafora delay zastanie zamknięty semafor mutex. Przy takim założeniu jasna staje się konieczność bezwarunkowego podniesienia semafora mutex na końcu operacji P(S). Z drugiej strony w kodzie operacji V(S) należy zagwarantować, że obudzony proces faktycznie zastanie opuszczony semafor mutex. Aby to zapewnić w implementacji V(S) mutex jest podnoszony jedynie wówczas, gdy nikogo nie budzimy. Jeśli jednak podnosimy semafor delay, to mutex pozostaje zamknięty --- właśnie po to aby proces obudzony z semafora delay zastał zamknięty semafor mutex.
Co daje taka technika? Wyjaśnijmy to na przykładzie scenariusza, który prowadził do błędnego działania poprzedniej symulacji. Zacznijmy od sytuacji, w której procesy P(1) i P(2) są już w sekcji krytycznej, a P(3) i P(4) tuż przed zawieszeniem się na operacji P(delay). Semafor mutex jest otwarty, a semafor delay --- zamknięty. Zmienna N ma wartość -2. Przypuśćmy, że proces P(1) wychodzi teraz z sekcji krytycznej. Zamyka semafor mutex, zwiększa zmienną N na -1 i podnosi semafor delay. Ale mutex pozostaje zamknięty! Z tego powodu zanim proces P(2) będzie mógł rozpocząć wykonanie kodu za swoją sekcją krytyczną, któryś z procesów P(3) lub P(4) (albo oba) muszą wykonać operację V(delay). Ponieważ delay jest w tym momencie otwarty, więc jeden z procesów przejdzie przez niego, zamykając go za sobą i wykona operację V(mutex). Dopiero wtedy dostęp do fragmentów kodu chronionych semaforem mutex staje się otwarty, a scenariusz powodujący błędne działanie poprzedniej symulacji nie jest już możliwy.
Opisaną technikę w ogólności można ująć w następujący schemat. Zawieszanie procesu realizujemy w następujący sposób (dodatkowa zmienna ile_czeka zlicza ile procesów oczekuje na początkowo zamkniętym semaforze sem:
P(mutex);
...
if warunek then
begin
ile_czeka := ile_czeka + 1;
V(mutex);
P(sem); { obudzony proces zastanie zamknięty mutex }
ile_czeka := ile_czeka -1
...
end;
...
V(mutex)
Budzenie procesu realizujemy następująco:
P(mutex)
...
if ile_czeka > 0 then
V (sem)
else
V (mutex)
Opisana technika nosi nazwę dziedziczenia sekcji krytycznej, bo budzony z semafora sem proces dziedziczy wyłączny dostęp do sekcji krytycznej chronionej semaforem mutex po procesie budzącym. Umiejętne stosowanie tej techniki pozwala ograniczyć liczbę możliwych przeplotów i
uniknąć wielu błędów synchronizacyjnych poprzez wymuszenie niepodzielności akcji budzenia i wznowienia działania przez proces obudzony.
Popatrzmy teraz, jak za pomocą semaforów można zapisać różne wersje rozwiązań problemu pięciu filozofów. Zacznijmy od wersji najprostszej. Role widelców grają semafory binarne, przy czym semafor otwarty oznacza, że widelec jest dostępny, a semafor zamknięty, że widelcem ktoś już się posługuje. Każdy filozof najpierw bierze widelec po swojej lewej stronie, potem po stronie prawej:
var
wid: array [0..4] of binary semaphore := (1, 1, 1, 1, 1);
process Filozof (i: 0..4);
begin
repeat
Myśli;
P (wid[i]);
P (wid[(i+1) mod 5];
Je;
V (wid[i]);
V (wid[(i+1) mod 5];
until false
end;
Oczywiście z powodów już uprzednio omawianych ten program powoduje zakleszczenie filozofów.
Przypomnijmy, że rozwiązanie poprawne polega na dopuszczeniu do stołu co najwyżej 4 filozofów. W tym celu do poprzedniego przykładu dodamy semafor ogólny lokaj zainicjowany na 4:
var
lokaj: semaphore := 4;
wid: array [0..4] of binary semaphore := (1, 1, 1, 1, 1);
process Filozof (i: 0..4);
begin
repeat
Myśli;
P (lokaj);
P (wid[i]);
P (wid[(i+1) mod 5];
Je;
V (wid[i]);
V (wid[(i+1) mod 5];
V (lokaj)
until false
end;
Spróbujmy jeszcze zapisać rozwiązanie, w którym filozofowie podnoszą jednocześnie oba widelce. Przypomnijmy, że taki algorytm może prowadzić do zagłodzenia filozofa przez jego sąsiadów. Zobaczmy jednak, jakiego rodzaju problemy techniczne występują przy zapisie tego rozwiązania za pomocą semaforów.
Po pierwsze wprowadzamy tablicę stanów poszczególnych filozofów:
stan: array [0..4] of (myśli, głodny, je) := (myśli, myśli, myśli, myśli, myśli); mutex: binary semaphore := 1; furtka: array [0..4] of binary semaphore := (0, 0, 0, 0, 0);
Każdy filozof ma swój własny semafor furtka. Jest on początkowo zamknięty. Każdy filozof sprawdza, czy może rozpocząć jedzenie i jeśli tak, to otwiera sobie ten semafor. Po zakończeniu jedzenia i odłożeniu widelców, filozof sprawdza, czy jego sąsiedzi są głodni i mają już komplet widelców. Jeśli tak, to ich budzi.
Procedura test zajmuje się sprawdzeniem, czy i-ty filozof może rozpocząć jedzenie:
procedure test (i: 0..4);
begin
if stan[i] = głodny and
stan[(i+1) mod 5] <> je and
stan[(i+4) mod 5] <> je then
begin
stan[i] := je;
V (furtka[i]
end
end;
Treść procesu filozof wygląda następująco:
process Filozof (i:0..4);
begin
repeat
myśli;
P(mutex);
stan[i] := głodny;
test (i);
V(mutex);
P (furtka[i]);
je;
stan[i] := myśli;
test ((i+4) mod 5);
test ((i+1) mod 5);
V (mutex);
until false
end
System operacyjny Unix oferuje implementację semaforów w ramach pakietu InterProcess Communication (IPC). Funkcjonalność semaforów uniksowych znacznie wykracza poza klasyczne funkcje. Przede wszystkim operacje podnoszenia i opuszczania semaforów można wykonywać nie tylko o jedną jednostkę, ale o dowolną wartość. Abstrahując od rzeczywistego sposobu zapisu operacji na semaforach w języku C, oznaczmy operacje zwiększenia i zmniejszenia semafora uniksowego S o n przez odpowiednio V(S, n) i P (S, n).
Operacja V(S, n) jest nieblokująca. Proces zawsze może ją wykonać. Operacja P(S, n) zatrzymuje proces, jeśli aktualna wartość semafora jest mniejsza niż S, a zmienna semaforowa nie zmienia się. Dopiero gdy proces doczeka się na wartość co najmniej n, to zmniejsza wartość semafora o n i kończy wykonanie operacji P(S, n).
Przypuśćmy, że aktualną wartością zmiennej semaforowej jest m. Przypuśćmy, że pewien proces oczekuje na wykonanie operacji P (S, n) (bo m < n). Jeśli teraz inny proces wywoła operację P(S, k), przy k < m, to wykona on operację P(s, k) bez zawieszania. Taka implementacja może prowadzić do głodzenia procesów oczekujących na operacji P (S, n) z dużym n.
Dodatkową operacją, którą można wykonywać na semaforach uniksowych jest operacja oczekiwania aż semafor będzie miał wartość 0. Oznaczmy tę operację przez Z(S).
Semafory uniksowe występują w zestawach złożonych z jednego lub więcej semaforów. Unix umożliwia wykonywanie jednoczesnych operacji na semaforach należących do tego samego zestawu. Takie jednoczesne operacje będziemy w dalszym ciągu zapisywać ujmując je w nawiasy kwadratowe. Semantyka operacji jednoczesnych [op(1), op(2), ..., op(n)] jest następująca.
System operacyjny próbuje wykonać operacje w kolejności op(1), op(2), ..., op(n). Jeśli i-ta operacja nie powoduje zawieszenia procesu, to przechodzi do wykonania operacji i+1. Jeśli jednak i-ta operacja powoduje wstrzymanie procesu, to system anuluje już wykonane operacje op(1), ..., op(i-1) przed zawieszeniem procesu. Z punktu widzenia procesu efekt jest taki, jakby zostały wykonane wszystkie operacje albo żadna. Po obudzeniu proces ponownie próbuje wykonać wszystkie operacje od op(1) do op(n).
Z powyższego opisu wynika, że kolejność operacji przeznaczonych do jednoczesnego wykonania jest istotna. Popatrzmy na przykład. Operacja [V(S, 1), P(S, 1)] jest nieblokująca: najpierw bowiem otwieramy semafor, a potem próbujemy przejść pod otwartym semaforem, co się zawsze uda. Oczywiście taka operacja nie ma żadnego efektu na semafor S. Z kolei [P(S, 1), V(S, 1)] również nie zmieni wartości semafora S, ale wstrzyma proces, jeśli semafor jest zamknięty!
Operacje P i Z na semaforach uniksowych mają także swoje nieblokujące wersje. Polegają one na tym, że zamiast wstrzymywać proces, kończą się one natychmiast przekazując informacje o niepowodzeniu. Ponadto istnieje możliwość ustawienia wartości semafora i odczytania go oraz sprawdzenia, ile procesów oczekuje na poszczególnych operacjach.
Zilustrujmy działanie jednoczesnych operacji semaforowych do rozwiązania problemu czytelników i pisarza. Przypuśćmy, że mamy zestaw semaforów złożony z dwóch semaforów: CZYT oraz PIS. Semafor CZYT zlicza czytelników przebywających w czytelni, a semafor PIS --- pisarzy w czytelni. Czytelnik przed wejściem do czytelni powinien niepodzielnie upewnić się, że nie ma w niej pisarza i zwiększyć licznik czytelników. Prowadzi to do następującego kodu:
'process Czytelnik;
begin
repeat
własne_sprawy;
[Z(PIS), V(CZYT)]
czytanie;
P(CZYT)
until false
end
Proces pisarza musi upewnić się, że w czytelni nie ma nikogo i dopiero wówczas może do niej wejść zwiększając licznik pisarzu:
'process Pisarz;
begin
repeat
własne_sprawy;
[Z(PIS), Z (CZYT), V(PIS)]
czytanie;
P(PIS)
until false
end
Niestety, przedstawione rozwiązanie, choć ma własność bezpieczeństwa, nie gwarantuje żywotności pisarzy. Może się bowiem zdarzyć, że ciągły napływ czytelników spowoduje, że czytelnia nigdy nie będzie pusta i pisarze będą w nieskończoność oczekiwać na dostęp do czytelni.
Spróbujmy poprawić rozwiązanie. Niech semafor CZYT w dalszym ciągu zlicza czytających czytelników. Zamiast semafor zliczającego pisarzy tym razem zastosujemy semafor POCZ chroniący dostęp do poczekalni. Każdy proces musi najpierw przejść przez poczekalnie. Proces pisarza po wejściu do poczekalni blokuje do niej dostęp, czeka aż wszyscy czytający czytelnicy opuszczą czytelnię, rozpoczyna pisanie i po jego zakończeniu zwalnia dostęp do poczekalni. Początkowo semafor CZYT jest równy zero, a semafor POCZ jest inicjowany na 1.
'process Pisarz;
begin
repeat
własne_sprawy;
P(POCZ);
Z(CZYT);
pisanie;
V(POCZ)
until false
end
Proces czytelnika wchodzi do poczekalni nie blokując dostępu do niej dla innych i rozpoczyna czytanie zwiększając licznik czytelników. Po wyjściu z czytelni zmniejsza semafor CZYT.
'process Czytelnik;
begin
repeat
własne_sprawy;
[P(POCZ), V(POCZ), V(CZYT)]
czytanie;
P(CZYT)
until false
end
W literaturze pojawiają się też inne rodzaje semaforów. Omówmy najważniejsze z nich.
Inspiracją dla semaforów dwustronnie ograniczonych był problem producenta i konsumenta. Semafory dwustronnie ograniczone charakteryzują się symetrycznymi operacjami P i V. Obie operacje mogą spowodować wstrzymanie procesu. Dodatkowym parametrem semafora dwustronnie ograniczonego jest maksymalna wartość k, jaką może przyjmować zmienna semaforowa.
Operacje na semaforze dwustronnie ograniczonym definiuje się w następujący sposób:
Czekaj aż S >0; S := S - 1;
Czekaj aż S < k; S := S + 1
Oczywiście założenia dotyczące niepodzielności i ich wzajemnym wykluczaniu się pozostają w mocy.
Semafory dwustronnie ograniczone nie zwiększają mocy wyrazu zwykłych semaforów --- można je zaimplementować za pomocą dwóch semaforów ogólnych.
Semafor uogólniony w odróżnieniu od semafora ogólnego umożliwia wykonywanie operacji P i V o większą liczbę jednostek, a niekoniecznie o 1.
Czekaj aż S > n; S := S - n;
S := S + n
Jak już wspomnieliśmy przy omówieniu semaforów uniksowych, dość ostrożnie należy podchodzić do implementacji takich semaforów ze względu na możliwość głodzenia procesów, próbujących wykonać operację P(S, n) z dużą wartością n. Implementację gwarantującą żywotność przedstawiamy na ćwiczeniach.
Semafory Agerwali wprowadzają jednoczesne operacje na zwykłych semaforach, przy czym wykonanie operacji zamykania zależy od stanu innych semaforów. Operacja P jako argument bierze dwie grupy semaforów:
P(S1, S2, ..., Sn; T1, T2, ..., Tm): Czekaj aż wszystkie semafory S będą otwarte, a wszystkie semafory T zamknięte; for i := 1 to n do Si := Si - 1
Operacja V podnosi wszystkie przekazane jej jako argumenty semafory:
V(S1, ..., Sn): for i := 1 to n do Si := Si + 1
Motywacją dla semaforów Agerwali było m.in. wprowadzenie priorytetowego dostępu do zasobów. Przypuśćmy, że w systemie znajduje się jeden zasób, z którego korzystają procesy P(1..N). Jednocześnie z zasoby może korzystać co najwyżej jeden proces. Jeśli zasób staje się wolny, a oczekuje na niego wiele procesów, to pierwszeństwo ma ten o mniejszej wartości parametru.
Rozwiązanie polega na wykorzystaniu semaforów Agerwali. Z każdym procesem związany jest jego prywatny semafor chce. Jego podniesienie oznacza, że proces chce skorzystać z zasobu i jeszcze go nie otrzymał. Oprócz tego korzystamy z semafora mutex gwarantującego wyłączny dostęp do zasobu:
var chce: array [1..N] of binary semaphore := (0, 0, ..., 0); mutex: binary semaphore := 1;
Tekst procesu możemy wówczas zapisać następująco:
process P (i: 1..N);
begin
repeat
własne_sprawy;
V (chce[i]);
P (mutex; chce[1], ..., chce[i-1]);
P (chce[i]);
sekcja_krytyczna;
V (mutex)
until false
end
Podstawową wadą semafora jest to, że nie jest to mechanizm strukturalny, przez co trudno jest analizować programy współbieżne i ogarnąć wszystkie możliwe przeploty. Dochodzą do tego częste błędy polegające chociażby na niezamierzonej zamianie operacji P i V ze sobą.
Powyższych wad jest pozbawiony monitor, który stanowi połączenie modułu programistycznego z sekcją krytyczną. Monitor jest po prostu modułem zawierającym deklaracje stałych, zmiennych, funkcji i procedur. Wszystkie te obiekty, z wyjątkiem jawnie wskazanych funkcji i procedur są lokalne w monitorze i nie są widoczne na zewnątrz niego. Wskazane funkcje i procedury (tzw. eksportowane) są widoczne na zewnątrz monitora. Mogą je wywoływać procesy i za ich pośrednictwem manipulować danymi ukrytymi w monitorze. Monitor zawiera też kod, który służy do jego inicjacji, na przykład do ustawienia wartości początkowych zmiennych deklarowanych w monitorze.
Monitor będziemy definiować korzystając z następującej składni:
monitor Nazwa; definicje stałych i typów; deklaracje zmiennych lokalnych; deklaracje procedur i funkcji; begin instrukcje inicjujące monitor; end;
Definiując stałe, typy, zmienne i procedury będziemy stosować składnię Pascala z tym, że procedury i funkcje udostępniane na zewnątrz będziemy poprzedzać słowem kluczowym export.
Aby wywołać eksportowaną przez monitor M procedurę P w pewnym procesie użyjemy notacji:
M.P (parametry)
Z powyższego opisu wynika, że monitor jest po prostu modułem, ukrywającym część informacji i udostępniającym na zewnątrz pewne funkcje i procedury. Ale to nie są jeszcze wszystkie własności monitora.
Monitor jest z definicji sekcją krytyczną. Co to oznacza? Otóż jednocześnie co najwyżej jeden proces może być w trakcie wykonania kodu znajdującego się w monitorze. Innymi słowy: jeśli jakiś proces wywoła procedurę eksportowaną przez monitor M i rozpocznie jej wykonanie, to do czasu powrotu z tej procedury żaden inny proces nie może rozpocząć wykonania tej ani żadnej innej procedury/ funkcji monitora. O procesie, który wywołał funkcję/procedurę monitora i nie zakończył jeszcze jej wykonania, będziemy mówić, że znajduje się w monitorze. Zatem jednocześnie w monitorze może przebywać co najwyżej jeden proces.
Taka definicja narzuca sposób naturalny sposób korzystania ze zmiennych współdzielonych przez procesy. Po prostu należy umieścić je w monitorze i dostęp do nich realizować za pomocą eksportowanych procedur i funkcji. Programista korzystający w taki właśnie sposób ze zmiennej dzielonej nie musi myśleć o zapewnianiu wyłączności w dostępie do niej --- robi to za niego automatycznie sam monitor.
Co się jednak dzieje, jeśli pewien proces wywoła procedurę monitora w chwili, gdy inny proces już się w nim znajduje? Otóż taki proces musi poczekać. Z każdym monitorem jest związana kolejka procesów oczekujących na "wejście" do niego. Jest to kolejka prosta: proces, który zgłosił się jako pierwszy i został wstrzymany przed wejściem do monitora, jako pierwszy zostanie wznowiony. Zaznaczmy, niezależnie od tego, którą procedurę czy funkcję monitora proces wywołał, zostanie on w razie konieczności wstrzymany i umieszczony w tej samej kolejce. Jest jedna kolejka procesów oczekujących na wejście do monitora, a nie tak jak w Adzie, osobne kolejki do poszczególnych procedur eksportowanych.
Gdy proces, który przebywał w monitorze, opuści go, czyli gdy następuje powrót z wywołanej funkcji/procedury monitora do procesu, pierwszy proces w kolejce procesów oczekujących na wejście do monitora jest automatycznie budzony. I znów dzieje się to automatycznie, programista nie musi się o to martwić.
Często oprócz zapewnienia wyłącznego dostępu do zmiennych dzielonych zachodzi także potrzeba synchronizacji procesów w inny sposób. Proces musi na przykład poczekać na dostępność pewnych zasobów lub zakończenie przetwarzania przez inne procesy. Aby realizować tego typu zadania, monitor oferuje specjalny typ danych, tzw. zmienne warunkowe.
Zmienne warunkowe deklarujemy jako zmienne typu condition. Mogą one wystepować jedynie wewnątrz moniora. Na zmiennej warunkowej c proces może wykonać następujące operacje:
Bliższa analiza działania operacji signal prowadzi do niepokojących spostrzeżeń. Zgodnie z powyższą semantyką signal (c) budzi pierwszy proces z kolejki procesów oczekujących w kolejce związaną ze zmienną c. Obudzony proces ma natychmiast wznowić działanie w monitorze. Ale przecież w monitorze jest już inny proces: ten, który wykonał signal. Mamy więc dwa procesy w monitorze, co przeczy temu, że monitor jest sekcją krytyczną.
Aby poradzić sobie z tym problemem przyjmijmy na razie, że signal musi być ostatnią instrukcją wykonywaną przez proces w monitorze. Wtedy proces po wykonaniu operacji signal wychodzi z monitora oddając go obudzonemu procesowi. Podkreślmy to raz jeszcze. Jeśli proces wykonuje signal na niepustej kolejce i wychodzi z monitora, to do monitora wróci obudzony proces przed jakimikolwiek procesami oczekującymi na wejście do monitora. Jest to bardzo ważna i pożyteczna cecha monitora.
Popatrzmy teraz, jak zazwyczaj korzysta się z monitorów. W zasadzie każdy problem synchronizacyjny można przedstawić w postaci następującego schematu procesu:
process P;
begin
repeat
praca nie wymagająca synchronizacji;
protokół wstępny;
fragment wymagający synchronizacji;
protokół końcowy
until false;
end;
Protokoły wstępny i końcowy zazwyczaj wymagają wzajemnego wykluczania. Naturalnym podejściem jest zatem umieszczenie ich w monitorze w postaci eksportowanych procedur. Zmienne potrzebne do zapewnienia właściwej synchronizacji umieszczamy także w tym samym monitorze, jako zmienne lokalne.
Spójrzmy, jak takie podejście sprawdza się przy problemie dostępu do sekcji krytycznej. Przypuśćmy, że z sekcji krytycznej może jednocześnie korzystać co najwyżej k procesów. Kod procesu jest oczywisty:
process P;
begin
repeat
własne_sprawy;
M.Chce;
sekcja_krytyczna;
M.Zwalniam;
until false;
end;
W monitorze M umieścimy zmienną zliczającą aktualną liczbę wolnych miejsc w sekcji krytycznej, zmienną warunkową czekaj służącą do wstrzymywania procesów, gdy nie ma dla nich miejsca w sekcji krytycznej:
monitor M; var wolnych: integer; czekaj: condition;
Następnie implementujemy procedurę Chce. Przygotowując procedury monitorowe, a zwłaszcza protokoły wstępne, dobrze jest wychwycić warunek na wstrzymanie procesu i zastosować instrukcję warunkową, która przy prawdziwym warunku powoduje zawieszenie procesu. Dalsze czynności wykonywane przez proces w protokole wstępnym często nie zależą od tego, czy proces czekał, czy nie. Z technicznego punktu widzenia oznacza to, że we wspomnianej instrukcji warunkowej najczęściej nie jest potrzebna część po else.
W omawianym przekładzie proces powinien poczekać, jeśli nie ma wolnych miejsc. Gdy będą już wolne miejsca, to należy zmniejszyć ich liczbę i wyjść z monitora:
export procedure Chce;
begin
if wolnych = 0 then
wait (czekaj);
wolnych := wolnych - 1
end;
Protokół końcowy zwalnia jedno miejsce i budzi proces oczekujący na wejście do sekcji krytycznej:
export procedure Zwalniam; begin wolnych := wolnych + 1; signal (czekaj) end;
Monitor wymaga również zainicjowania zmiennych:
begin wolnych := k end.
Zwróćmy uwagę, że w procedurze Zwalniam sygnał jest wysyłany bezwarunkowo. Jeśli nikt nie czekał na warunku czekaj, to nie stanie się nic złego, gdyż taki sygnał nie powoduje żadnego efektu.
Przeanalizujmy jeszcze rozwiązanie problemu czytelników i pisarzy. Tak jak w poprzednim przykładzie, protokoły wstępne i końcowe czytelnika i pisarza umieścimy w monitorze, co prowadzi do następującego kodu procesów:
proces Czytelnik;
begin
repeat
własne_sprawy;
Czytelnia.ChceCzytać;
czytanie;
Czytelnia.KoniecCzytania;
until false;
end;
proces Pisarz;
begin
repeat
własne_sprawy;
Czytelnia.ChcePisać;
pisanie;
Czytelnia.KoniecPisania;
until false;
end;
Monitor Czytelnia zwiera dwie zmienne warunkowe: do wstrzymywania czytelników i pisarzy. Oprócz tego jest potrzebna zmienna pamiętająca ilu czytelników czyta i ilu pisarzy pisze. Ta druga zmienna mogłaby być zmienną logiczną, ale dla symetrii niech obie zmienne będą zmiennymi całkowitymi:
monitor Czytelnia; var iluczyta: integer; ilupisze: integer; czytelnicy: condition; pisarze: condition;
Rozpocznijmy od protokołu wstępnego pisarza. Pisarz musi czekać, jeśli ktokolwiek jest w czytelni:
export procedure ChcePisać;
begin
if iluczyta+ilupisze> 0 then
wait (pisarze);
ilupisze := ilupisze + 1
end;
Protokół wstępny czytelnika jest podobny. Czytelnik musi poczekać, jeśli ktoś pisze lub --- aby nie zagłodzić pisarzy --- są pisarze oczekujący na pisanie. Instrukcję oznaczoną gwiazdką wyjaśnimy nieco później:
export procedure ChceCzytać;
begin
if (ilupisze > 0) or not empty (pisarze) then
wait (czytelnicy);
iluczyta := iluczyta + 1;
signal (czytelnicy) {*}
end;
Protokół końcowy czytelnik jest prosty. Jeśli jest on ostatnim wychodzącym z czytelni, to budzi pisarza:
export procedure KoniecCzytania;
begin
iluczyta := iluczyta - 1;
if iluczyta = 0 then
signal (pisarze)
end;
Z protokołem końcowym pisarza jest jednak pewien problem. Umówiliśmy się, że operacja signal jest ostatnią operacją wykonywaną w monitorze. Tymczasem pisarz powinien wpuścić wszystkich oczekujących czytelników, o ile są jacyś, lub jednego pisarza, jeśli nie czekają czytelnicy. Wpuszczenie wszystkich oczekujących czytelników wymagałoby wykonanie operacji signal w pętli, a to powoduje, że signal nie jest ostatnią operacją monitora. Spróbujmy zastosować inne rozwiązanie. Niech pisarz budzi jednego czytelnika, o ile są oczekujący czytelnicy. Zauważmy, że obudzony czytelnik, dzięki dodanej do protokołu wstępnego instrukcji oznaczonej {*} obudzi kolejnego czytelnika, ten kolejny czytelnik obudzi następnego itd. aż do obudzenia wszystkich. Taką technikę będziemy nazywać kaskadowym zwalnianiem:
export procedure KoniecPisania;
begin
ilupisze := ilupisze - 1;
if not empty (czytelnicy) then
signal (czytelnicy)
else
signal (pisarze)
end;
Pozostała jeszcze część inicjująca monitor:
begin iluczyta := 0; ilupisze := 0; end.
Umieszczenie operacji signal na końcu kodu procesu nie jest jednak zawsze możliwe. Aby móc stosować signal także wewnątrz procedury monitora trzeba uściślić semantykę operacji signal w następujący sposób. Signal(c) powoduje obudzenie pierwszego procesu z kolejki procesów oczekujących na zmiennej warunkowej c. Jeśli kolejka jest pusta, to instrukcja nie daje żadnego efektu. W przeciwnym razie obudzony proces natychmiast wznawia swoje działanie w monitorze od kolejnej instrukcji za wait, w którym został wstrzymany, a proces wykonujący operację signal opuszcza tymczasowo monitor i zostaje umieszczony na początku kolejki procesów oczekujących na wejście do monitora.
Dzięki temu, że proces budzący opuszcza monitor, proces obudzony może wznowić swoje działanie bez obawy, że nie będzie jedynym procesem w monitorze. Z drugiej strony, umieszczenie budzącego na początku kolejki na wejściu do monitora zapewnia, że zostanie on wznowiony przed procesami oczekującymi na wejście do monitora, gdy tylko obudzony przez niego proces wyjdzie z niego.
Taka semantyka powoduje jednak pewne problemy. Kolejność instrukcji w, z pozoru niepodzielnej procedurze monitora, zaczyna mieć istotne znaczenie. Aby to zilustrować przyjrzyjmy się następującemu rozwiązaniu problemu wzajemnego wykluczania (z jednym procesem w sekcji krytycznej):
monitor M;
var
wolne: boolean;
czekaj: condition;
export procedure Chce;
begin
if not wolne then
wait (czekaj);
wolne := false
end;
export procedure Zwalniam; begin wolne := true; signal (czekaj) end;
begin wolne := true end.
Powyższe rozwiązanie jest poprawne. Zamieńmy jednak kolejność instrukcji w procedurze Zwalniam:
export procedure Zwalniam; begin signal (czekaj); wolne := true end;
Program przestał być poprawny! Przypuśćmy, że proces P(1) wykona procedurę Chce. Spowoduje to ustawienie zmiennej wolne na false, a proces P(1) kończy wykonanie procedury Chce i wchodzi do sekcji krytycznej. Jeśli teraz proces P(2) wywoła procedurę Chce, to zostanie wstrzymany na zmiennej czekaj. Niech proces P(1) opuści teraz sekcję krytyczną. Wywoła wówczas procedurę Zwalniam. Pierwszą instrukcją jest signal. Zatem proces P(1) wyjdzie na chwilę z monitora, a obudzony zostanie proces P(2), który wznowi swoje działanie w procedurze Chce i ustawi zmienną wolne na true, po czym wyjdzie z monitora i przejdzie do sekcji krytycznej. Ponieważ monitor jest pusty, więc wraca do niego proces P(1), który wykona wolne := true. Efekt: proces P(2) jest w sekcji krytycznej, a zmienna wolne ma wartość true. Jeśli teraz proces P(1) ponownie wywoła procedurę Chce, to zostanie wpuszczony do sekcji krytycznej, mimo że przebywa tam już inny proces.
Do tej pory nie zajmowaliśmy się w sposób formalny poprawnością programów współbieżnych. Wspomnieliśmy jedynie, że rozważa się dwie formy poprawności: bezpieczeństwo (albo inaczej zapewnianie) oraz żywotność.
Obecnie zaprezentujemy jedno z wielu możliwych podejść do weryfikacji programów współbieżnych. Pokażemy, w jaki sposób można specyfikować własności bezpieczeństwa i żywotności w logice temporalnej o nazwie Computational Tree Logic. Ponieważ jest to logika rozstrzygalna pokażemy też w jaki sposób, poprzez badanie modeli (ang. model chcecking) można weryfikować poprawność programów współbieżnych.
Przypomnijmy, że własność bezpieczeństwa wyraża fakt, że nigdy nie dojdzie do sytuacji niepożądanej: nigdy dwa procesy nie będą jednocześnie w sekcji krytycznej, producent nie nadpisze danych w buforze itp. Własność bezpieczeństwa jest własnością statyczną w tym sensie, że pojawia się w specyfikacji problemu.
Własność żywotności to własność dynamiczna. Ogólnie można powiedzieć, że warunek żywotności wyraża następujący fakt: Jeśli proces chce wykonać pewną akcję, to w skończonym czasie mu się to uda. Przykładem własności żywotności jest żądanie, aby proces, który chce wejść do sekcji krytycznej w końcu mógł do niej wejść. Podobnie czytelnik, który chce rozpocząć czytanie powinien w skończonym czasie wejść do czytelni.
Przejawem braku żywotności jest zakleszczenie albo zagłodzenie. Zjawiska te polegają na tym, że proces (lub procesy) nie mogą wykonać żadnej pożytecznej pracy. Jeśli jest to zjawisko globalne mówimy o zakleszczeniu, jeśli brak żywotności dotyczy pojedynczego procesu (pojedynczych procesów) mówimy o zagłodzeniu.
Dla potrzeb tej części wykładu wprowadźmy abstrakcyjny model procesu.
Proces modelujemy jako trójkę: \((S, R, I)\), gdzie:
Mając powyższy model procesu można formalnie zdefiniować ciąg wykonawczy procesu:
Niech \(P = (S, R, I)\) będzie procesem. Określmy następujące zbiory:
Wówczas ciągiem wykonawczym procesu nazwiemy dowolną ścieżkę \(p\in\bigcup_{s\in I}\,{Path}_s\).
Zauważmy, że zbiór wszystkich ciągów wykonawczych danego procesu jest drzewem.
Computational Tree Logic jest zdaniową logiką temporalną. Można w niej wyrażać nie tylko proste fakty typu własność p zachodzi w pewnym stanie, ale także stwierdzenia zawierające kwantyfikatory dotyczące czasu: kiedyś w przyszłości, zawsze w przyszłości oraz kwantyfikatory dotyczące możliwości: na pewno, może się zdarzyć. Zauważmy, że własności, które chcemy formułować jako warunki poprawności zawierają takie właśnie kwantyfikatory: na pewno nigdy w przyszłości dwa procesy nie będą w sekcji krytycznej.
Aby zdefiniować logikę powinniśmy określić co najmniej jej składnię i semantykę. Zaczniemy od definicji składni. Formuły w CTL dzielą się na dwie kategorie: formuły stanowe i formuły ścieżkowe. Ich definicja jest wzajemnie rekurencyjna.
Niech \(V=\{v_1, v_2,\ldots\}\) będzie przeliczalnym zbiorem zmiennych zdaniowych.
Spójniki \(\neg, \wedge, \vee, \leftrightarrow\) definiuje się na formułach stanowych za pomocą \(\rightarrow\)
Prawdziwość formuł w logice CTL będziemy wyliczać w strukturach Kripkego. Intuicyjnie, struktura Kripkego to proces wzbogacony o wartościowanie zmiennych zdaniowych w każdym stanie. Innymi słowy: z każdym stanem procesu związujemy zbiór faktów (zmiennych zdaniowych), które w tym stanie są prawdziwe. Ponieważ proces wykonuje się (zmienia stany zgodnie z relacją przejścia) to prawdziwość zmiennych zdaniowych zmienia się w czasie.
Struktura Kripkego to czwórka uporządkowana \((S, R, I, \delta)\), gdzie
Funkcję \(\delta\) można uważać za wartościowanie zmiennych zdaniowych, ale wartościowanie to zależy od stanu, w którym znajduje się proces.
Mając strukturę Kripkego i formułę CTL możemy rozstrzygać, czy jest ona prawdziwa w tej strukturze. Najpierw jednak musimy zdefiniować prawdziwość formuły stanowej w określonym zadanym stanie oraz prawdziwość formuły ścieżkowej dla zadanej ścieżki.
Niech \(s\in S\) dowolnym stanem.
Powiemy, że struktura Kripkego \(K, s \vDash \phi\).
A oto przykładowe formuły i ich sens:
Dana jest struktura Kripkego \(\phi\). Sprawdzić, czy \(K \vDash \phi\).
Można pokazać, że zadanie to sprowadza się do wielokrotnego przeszukiwania grafu reprezentującego proces. Zatem problem sprawdzenia, czy dana struktura Kripkego jest modelem dla zadanej formuły jest rozstrzygalny. Można to wykorzystać proponując następujący sposób weryfikacji programów współbieżnych:
Zadanie to można przeprowadzić za pomocą narzędzi wspomagających takich jak na przykład SMV. A oto formalizacja algorytmu Petersona z pierwszego wykładu w postaci kodu w SMV.
MODULE main
VAR
chce1 : boolean;
chce2 : boolean;
kto : {1, 2};
proc1 : process proc1(chce1,chce2,kto);
proc2 : process proc2(chce1,chce2,kto);
ASSIGN init(chce1) := 0; init(chce2) := 0;
SPEC AG (! (proc1.stan = sekcja & proc2.stan = sekcja))
MODULE proc1 (chce1,chce2,kto)
VAR
stan : {wlasne,chce,zmkto,while1,while2,sekcja,wyjscie};
ASSIGN
init(stan) := wlasne;
next(stan) :=
case
stan = wlasne : {wlasne, chce};
stan = chce : zmkto;
stan = zmkto : while1;
stan = while1 & !chce2 : sekcja;
stan = while1 & chce2 : while2;
stan = while2 & kto!=1 : sekcja;
stan = while2 & kto=1 : while1;
stan = sekcja : {sekcja, wyjscie};
stan = wyjscie : wlasne;
1: stan;
esac;
next(chce1) :=
case
stan = chce : 1;
stan = wyjscie : 0;
1 : chce1;
esac;
next (kto) :=
case
stan = zmkto : 1;
1 : kto;
esac;
SPEC
AG (stan = chce -> AF stan = sekcja)
FAIRNESS running
FAIRNESS stan != sekcja
MODULE proc2 (chce1,chce2,kto)
VAR
stan : {wlasne,chce,zmkto,while1,while2,sekcja,wyjscie};
ASSIGN
init(stan) := wlasne;
next(stan) :=
case
stan = wlasne : {wlasne, chce};
stan = chce : zmkto;
stan = zmkto : while1;
stan = while1 & !chce1 : sekcja;
stan = while1 & chce1 : while2;
stan = while2 & kto!=2 : sekcja;
stan = while2 & kto=2 : while1;
stan = sekcja : {sekcja, wyjscie};
stan = wyjscie : wlasne;
1: stan;
esac;
next(chce2) :=
case
stan = chce : 1;
stan = wyjscie : 0;
1 : chce2;
esac;
next (kto) :=
case
stan = zmkto : 2;
1 : kto;
esac;
SPEC AG (stan = chce -> AF stan = sekcja)
FAIRNESS running
FAIRNESS stan != sekcja