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.