Wprowadzenie do programowania współbieżnego

Wstęp

Próba definicji
Praca współbieżna polega na tym, że składające się na nią zjawiska, czynności i działania odbywają się równocześnie. Istotny jest przy tym punkt widzenia obserwatora.

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ą.

Motywacja

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.

  1. Niektóre problemy są z natury współbieżne, ich rozwiązania dają się łatwo i elegancko wyrazić w postaci niezależnie wykonujących się procedur. Przypuśćmy, że chcemy napisać grę akcji, w której wiele postaci porusza się na ekranie wykonując pewne działania. Taką scenę możemy oprogramować sekwencyjnie rozważając akcje wszystkich postaci w jednym fragmencie kodu. Jednak znacznie elegantszym rozwiązaniem jest oprogramowanie z osobna każdej postaci (można to zrobić obiektowo, nadając każdej z nich pewne indywidualne cechy), a następnie uruchomienie współbieżne tylu procesów, ile postaci chcemy uzyskać na ekranie. Oczywiście wymaga to także prawidłowej synchronizacji działania wszystkich procesów, co obejmuje działania takie jak na przykład wykrywanie kolizji i zapobieganie im.
  2. Współczesne systemy operacyjne zezwalają na uruchamianie wielu procesów jednocześnie. Gdy pewien proces czeka na zakończenie operacji wejścia/wyjścia, to inny proces może być w tym czasie wykonywany. Ta możliwość współbieżnego wykonania sięga nawet dalej.
  3. System operacyjny z podziałem czasu potrafi wykonywać wiele procesów współbieżnie dzieląc czas procesora między wiele procesów. Odbywa się to w ten sposób, że proces otrzymuje pewien kwant czasu (rzędu milisekund), w czasie którego korzysta z procesora. Gdy kwant skończy się, system operacyjny "przełącza" procesy: odkłada ten, który się wykonywał na później i zajmuje się innym. Ponieważ przełączanie odbywa się często, więc użytkownicy komputera mają wrażenie, że komputer zajmuje się wyłącznie ich procesem. Co więcej, rozwiązując pewien problem, użytkownik może uruchomić "jednocześnie" dwa procesy, które ze sobą w pewien sposób współpracują. Jest to powszechnie stosowane na przykład w środowisku systemu operacyjnego Unix, który umożliwia wykonywanie programów w potoku, np.: ls -l | grep moje | more. Wszystkie trzy programy wchodzące w skład takiego potoku wykonują się współbieżnie, z tym że wyniki generowane przez pierwszy z nich są podawane na wejście drugiego, wyniki drugiego --- na wejście trzeciego itd.
  4. Malejące ceny sprzętu sprzyjają powstawaniu architektur wieloprocesorowych, w których można uzyskać prawdziwą współbieżność, tzn. wykonywać jednocześnie wiele procesów na różnych procesorach. Wtedy system operacyjny nie musi już "oszukiwać" dzieląc czas jedynego procesora między wiele procesów, lecz może wykonywać każdy z nich na innym procesorze (przynajmniej dopóki wystarczy procesorów). Nowoczesne układy zawierają udogodnienia takie jak: wielowątkowość (hyperthreading), czy wręcz kilka rdzeni w jednej kości procesora.
  5. Rozpowszechnienie się sieci komputerowych stwarza jeszcze inne możliwości współbieżnego wykonywania. Poszczególne obliczenia składające się na duże zadanie mogą być wykonywane na różnych komputerach połączonych siecią. Rozproszone systemy operacyjne potrafią zarządzać czasem wielu procesorów, znajdujących się w wielu różnych węzłach sieci.

A oto przykłady "prac", które można realizować współbieżnie.

  1. Przypuśćmy, że chcemy obliczyć wartość wyrażenia \(a \cdot b - (c + d ) \cdot (e - f)\). Oczywiście można to robić od lewej do prawej, ale można też takie wyrażenie obliczać

współbieżnie licząc na przykład jednocześnie wyrażenia w nawiasach.

  1. Kolejny przykład to sortowanie tablicy N liczb. Sortowanie to można wykonywać za pomocą algorytmu sortowania przez scalanie:
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.

  1. Współbieżność może także uprościć zapis programu. Na przykład przetwarzanie potokowe (wspomniane już uprzednio) łatwo zapisuje się współbieżnie:
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

Równoległość a współbieżność

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:

  1. Wykonanie sekwencyjne. Poszczególne akcje procesu są wykonywane jedna po drugiej. Dokładniej: kolejna akcja rozpoczyna się po całkowitym zakończeniu poprzedniej.
  2. Wykonanie równoległe. Kilka akcji jest wykonywanych w tym samym czasie. Jest to "prawdziwa" współbieżność, możliwa do uzyskania na komputerze z wieloma procesorami.
  3. Wykonanie w przeplocie. Choć jednocześnie odbywa się wykonanie tylko jednej akcji, to jednak jest wiele czynności rozpoczętych i wykonywanych na zmianę krótkimi fragmentami.
  4. Wykonanie współbieżne. Kolejna akcja rozpoczyna się przed zakończeniem poprzedniej. Zauważmy, że nie mówimy nic na temat tego, czy akcje te są wykonywane w tym samym czasie czy też w przeplocie. Tak naprawdę wykonanie współbieżne jest abstrakcją równoległości i zawiera w sobie zarówno wykonania równoległe jak i wykonania w przeplocie.


Proces a program

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.

Założenia o środowisku działania programów

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:

  1. Proces może być gotowy do wykonania. Oznacza to, że ma wszystkie potrzebne zasoby z wyjątkiem procesora. Gdy tylko otrzyma procesor, może rozpocząć wykonanie.
  2. Proces może być wykonywany, jeśli jest gotowy i ma procesor. Jest tyle procesów wykonywanych, ile procesorów znajduje się w systemie.
  3. Proces wykonywany może zrzec się procesora i stać się wstrzymany, jeśli próbuje wykonać jakąś operacji, której nie może zrealizować natychmiast, bo na przykład nie ma niezbędnych zasobów. Klasycznym przykładem jest wykonanie operacji wejścia/wyjścia i konieczność poczekania aż niezbędne informacje zostaną sprowadzone z pamięci zewnętrznej. System operacyjny po sprowadzeniu niezbędnych zasobów zmieni stan procesu na gotowy.

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.

Zakres tematyki

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.

Organizacja zajęć i zasady zaliczania

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ń:

  1. Ćwiczenia laboratoryjne polegają na przedstawieniu pewnego mechanizmu synchronizacyjnego udostępnianiego przez system operacyjny Unix. Jest to najczęściej pewna implementacja abstrakcyjnego mechanizmu przedstawionego na wykładzie (na przykład komunikacja asynchroniczna --- łącza nienazwane i kolejko komunikatów, Ada --- RPC, semafory klasyczne --- semafory uniksowe, monitory --- muteksty). Takie ćwiczenia przedstawiają technikalia związanie z korzystaniem z danego mechanizmu, a następnie ilustrują te zagadnienia konkretnymi gotowymi programami. Każde ćwiczenie kończy się zadaniem programistycznym przeznaczonym do wykonania przez studenta.
  2. Ćwiczenia niezwiązane z programowaniem. Ich zadaniem jest przećwiczenie technik stosowanych przy korzystaniu z mechanizmu synchronizacyjnego przedstawionego na wykładzie. Materiały ćwiczeniowe wymagają od studenta przedstawienia rozwiązania konkretnego zadania synchronizacyjnego "na sucho", czyli bez tworzenia programu działającego na konkretnej platformie. Każde takie ćwiczenie kończy się postawieniem zadania, którego rozwiązanie należy przedstawić prowadzącemu.

Poprawność programów współbieżnych

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.

Przeplot

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 to ciąg złożony z przeplecionych ciągów wykonawczych procesów składowych

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:

Ciąg wykonawczy programu współbieżnego
to zbiór wszystkich możliwych przeplotów.

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ą.

Własność bezpieczeństwa (zapewniania)

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:

nigdy nie dojdzie do niepożądanej sytuacji

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:

nigdy na skrzyżowaniu nie będą jednocześnie samochody jadące w kierunku wschód-zachód i północ-południe.

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

Własność żywotności można wyrazić tak:

jeśli proces chce coś zrobić, to w końcu mu się to uda

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:

  1. Zakleszczenie. Jest to globalny brak żywotności. Nic się nie dzieje, system nie pracuje, oczekując na zajście zdarzenia, które nigdy nie zajdzie. Oto klasyczny przykład zakleszczenia. Przypuśćmy, że w systemie wykonują się dwa procesy, które w pewnym momencie muszą odczytać dane z dysku i wydrukować je na drukarce. Proces P1 prosi system o przydzielenie mu dysku i otrzymuje zgodę. Zanim jednak poprosi o drukarkę, proces P2 otrzymuje drukarkę. Teraz proces P1 czeka aż dostanie drukarkę, a proces P2 czeka na dysk. Żaden nie chce zrezygnować z zasobu, który już otrzymał, więc oczekiwanie będzie trwało w nieskończoność.
  2. Zagłodzenie. Jest to lokalny brak żywotności. Przypuśćmy, że w przedstawionym problemie skrzyżowania, procesy jadące mogą wjechać na skrzyżowanie zawsze wtedy, gdy są na nim inne procesy jadące w tym samym kierunku lub gdy skrzyżowanie jest puste. Załóżmy, że jako pierwszy zjawia się proces jadący na kierunku wschód-zachód. Oczywiście wjeżdża na skrzyżowanie. Jeśli teraz pojawi się proces jadący z północy, to oczywiści musi poczekać. Jednak jeśli zanim ze skrzyżowania zjedzie pierwszy proces pojawi się inny proces jadący ze wschodu, to będzie mógł wjechać na skrzyżowanie. Jeśli sytuacja się będzie ciągle powtarzać, to skrzyżowanie nigdy nie będzie puste --- będą na nim ciągle samochody jadące na kierunku wschód-zachód, co doprowadzi do zagłodzenia procesów drugiej grupy. W systemie coś się ciągle dzieje. Część procesów pracuje normalnie. Brak żywotności dotyka tylko niektóre procesy.

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.

Inne pożądane własności programów współbieżnych

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

x++

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.

Klasyczne problemy synchronizacyjne

Wzajemne wykluczanie

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:

  1. W sekcji krytycznej przebywał co najwyżej jeden proces jednocześnie (bezpieczeństwo).
  2. Każdy proces, który chce wykonać sekcję krytyczną w skończonym czasie do niej wszedł (żywotność).

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.

Producenci i konsumenci

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:

  1. Konsument oczekiwał na pobranie danych w sytuacji, gdy bufor jest pusty. Gdybyśmy pozwolili konsumentowi odbierać dane z bufora zawsze, to w sytuacji, gdy nikt jeszcze nic w buforze nie zapisał, odebrana wartość byłaby bezsensowna.
  2. Producent umieszczając dane w buforze nie nadpisywał danych już zapisanych, a jeszcze nie odebranych przez żadnego konsumenta. Wymaga to wstrzymania producenta w sytuacji, gdy w buforze nie ma wolnych miejsc.
  3. Jeśli wielu konsumentów oczekuje, aż w buforze pojawią się jakieś dane oraz ciągle są produkowane nowe dane, to każdy oczekujący konsument w końcu coś z bufora pobierze. Nie zdarzy się tak, że pewien konsument czeka w nieskończoność na pobranie danych, jeśli tylko ciągle napływają one do bufora.
  4. Jeśli wielu producentów oczekuje, aż w buforze będzie wolne miejsce, a konsumenci ciągle coś z bufora pobierają, to każdy oczekujący producent będzie mógł coś włożyć do bufora. Nie zdarzy się tak, że pewien producent czeka w nieskończoność, jeśli tylko ciągle z bufora coś jest pobierane.

Rozpatruje się różne warianty tego problemu:

  1. Bufor może być nieskończony.
  2. Bufor cykliczny może mieć ograniczoną pojemność.
  3. Może w ogóle nie być bufora.
  4. Może być wielu producentów lub jeden.
  5. Może być wielu konsumentów lub jeden.
  6. Dane mogą być produkowane i konsumowane po kilka jednostek na raz.
  7. Dane muszą być odczytywane w kolejności ich zapisu lub nie.

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.

Czytelnicy i pisarze

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:

  1. Wielu czytelników powinno mieć jednocześnie dostęp do czytelni.
  2. Jeśli w czytelni przebywa pisarz, to nikt inny w tym czasie nie pisze ani nie czyta.
  3. Każdy czytelnik, który chce odczytać dane, w końcu je odczyta.
  4. Każdy pisarz, który chce zmodyfikowć dane, w końcu je zapisze.

Rozpatruje się różne warianty tego problemu:

  1. W czytelni może przebywać dowolnie wielu czytelników.
  2. Czytelnia może mieć ograniczoną pojemność.
  3. Pisarze mogą mieć pierwszeństwo przed czytelnikami (ale wtedy rezygnujemy z żywotności czytelników)
  4. Czytelnicy mogą mieć pierwszeństwo przed pisarzami (ale wtedy rezygnujemy z żywotności pisarzy)

Wzajemną interakcję czytelników i pisarzy demonstruje poniższy applet[1]:

Pięciu filozofów

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:

  1. Jednocześnie tym samym widelcem jadł co najwyżej jeden filozof.
  2. Każdy filozof jadł zawsze dwoma (i zawsze tymi, które leżą przy jego talerzu) widelcami.
  3. Żaden filozof nie umarł z głodu.

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.