PROGRAMOWANIE WSPÓŁBIEŻNE

PODSTAWOWE POJĘCIA I PROBLEMY

• proces - program sekwencyjny w trakcie wykonywania

• dwa procesy są współbieżne, jeżeli jeden z nich rozpoczyna się przed zakończeniem drugiego

• będą nas interesować jedynie takie procesy, których wykonania są od siebie uzależnione, przy czym uzależnienie wynika z faktu, że procesy ze sobą współpracują lub między sobą współzawodniczą.

• komunikacja i synchronizacja:

Współpraca wymaga od procesów komunikowania się. Akcje komunikujących się procesów muszą być częściowo uporządkowane w czasie, ponieważ informacja musi najpierw zostać utworzona, zanim zostanie wykorzystana. Takie porządkowanie w czasie różnych procesów nazywa się synchronizacją.

Współzawodnictwo także wymaga synchronizacji - akcja procesu musi być wstrzymana, jeśli zasób potrzebny do jej wykonania jest w danej chwili zajęty przez inny proces.

• program współbieżny jest zbiorem procesów (wątków)

PROBLEM WZAJEMNEGO WYKLUCZENIA

• W teorii procesów współbieżnych wspólny obiekt, z którego może korzystać w sposób wyłączny wiele procesów (np. łazienka, koszyk w sklepie) nazywa się zasobem współdzielonym, natomiast fragment procesu, w którym korzysta on z obiektu dzielonego (mycie się, zakupy), nazywa się sekcją krytyczną tego procesu

• Problem wzajemnego wykluczenia definiuje się następująco:

zsynchronizować N procesów, z których każdy w nieskończonej pętli na przemian zajmuje się własnymi sprawami i wykonuje sekcję krytyczną, w taki sposób, aby wykonanie sekcji krytycznych jakichkolwiek dwóch lub więcej procesów nie pokrywało się w czasie

Aby ten problem rozwiązać, należy do treści tego procesu wprowadzić dodatkowe instrukcje poprzedzające sekcję krytyczną (nazywa się je protokołem wstępnym) i instrukcje następujące bezpośrednio po sekcji krytycznej (zwane protokołem końcowym)

PRZYKŁĄD PROBLEMU WZAJEMNEGO WYKLUCZENIA

• system komputerowy (jedno- lub wieloprocesorowy) z pamięcią wspólną

• dwa procesy współbieżne, z których jeden realizuje operację x = x + 1, a drugi x = x + 2

• każda z powyższych operacji realizowana jest w za pomocą trzech operacji maszynowych, tj. (i) load x, (ii) add 1 lub 2, (iii) store x

• przypuśćmy, że x = 5, wówczas jeden z możliwych scenariuszy wygląda następująco:

1. Pierwszy proces pobiera swoją kopię x : x = 5 .

1. Pierwszy proces oblicza x = x + 1 : x = 6 (lecz wartość wynikowa nie zostaje jeszcze zapisana do pamięci wspólnej) .

1. Drugi proces włącza się do akcji, pobierając swoją kopię x : x = 5 .

1. Drugi proces oblicza x = x + 2 : x = 7, nie zapisując wyniku do pamięci wspólnej.

1. Pierwszy proces zapisuje swój wynik x = 6 do pamięci.

1. Drugi proces zapisuje swój wynik x = 7 do pamięci wspólnej.

Wniosek: Otrzymujemy x = 7 zamiast prawidlowego wyniku

x = 8

BLOKADA I ZAGŁODZENIE

• W poprawnym programie współbieżnym, tj. posiadającym własność żywotności, w każdym procesie powinno w końcu nastąpić oczekiwane zdarzenie

• W niepoprawnym programie mogą wystąpić zjawiska blokady lub zagłodzenia

• Zbiór procesów znajduje się w stanie blokady, jeżeli każdy z tych procesów jest wstrzymany w oczekiwaniu na zdarzenie, które może spowodowane tylko przez jakiś inny proces z tego zbioru

• Inna nazwa zjawiska blokady to zastój, zakleszczenie lub martwy punkt

• Specyficznym przypadkiem nieskończonego wstrzymywania procesu jest zjawisko zagłodzenia

• Jeżeli sygnał synchronizacyjny może być odebrany tylko przez jeden z czekających nań procesów, powstaje problem, który z procesów wybrać.

• Zjawisko zagłodzenia występuje wówczas, gdy proces nie zostaje wznowiony, mimo, że zdarzenie na które czeka występuje dowolną liczbę razy. Za każdym razem, gdy proces ten mógłby być wznowiony, jest wybierany jakiś inny czekający proces.

MECHANIZMY SYNCHRONIZACJI

• Do rozwiązania problemu wzajemnego wykluczenia można zastosować niskopoziomowy mechanizm, jakim są przerwania, które umożliwiają przelączenie procesora na wykonywanie innego procesu

• W systemie jednoprocesorowym do realizacji wzajemnego wykluczenia można wykorzystać (i) procedury obsługi przerwań spowodowanych wykonaniem specjalnej instrukcji oraz (ii) mechanizm maskowania przerwań, umożliwiający zablokowanie następnych przerwań w czasie, gdy jest realizowana procedura obsługi poprzedniego przerwania

• Wadą takiego podejścia jest konieczność ingerencji w obszar systemu operacyjnego (instrukcje procedury obsługi przerwania wykonywane są przez system operacyjny, który posiada najwyższy priorytet)

• w systemie wieloprocesorowym mechanizm przerwań nie gwarantuje wzajemnego wykluczenia przy dostępie do pamięci, gdyż dwa różne procesory mogą w tym samym czasie realizować różne przerwania

• mechanizmy wysokopoziomowe: semafory i monitory

SEMAFORY

Semafor - abstrakcyjny typ danych, na którym oprócz określenia jego stanu początkowego, można wykonywać tylko dwie operacje, umożliwiające wstrzymywanie i wznawianie procesów, a mianowicie:

• opuszczenie semafora,

• podniesienie semafora,

o których zakłada się, że są niepodzielne, co oznacza, że dana operacja musi być wykonana od początku do końca bez możliwości przerwania przez inną operację

SEMAFOR BINARNY

definicja klasyczna:

• opuszczenie semafora binarnego to wykonanie instrukcji PB(S):

czekaj aż S = = 1; wtedy ustaw S = 0 (i kontynuuj proces)

• podniesienie semafora binarnego VB(S) :

S = 1

definicja praktyczna :

• opuszczenie semafora binarnego PB(S) :

jeżeli S = = 1, to S =0, w przeciwnym razie wstrzymaj

działanie procesu wykonującego tę operację;

• podniesienie semafora binarnego VB(S) :

jeżeli są procesy wstrzymane w wyniku wykonania operacji

opuszczania semafora S, to wznów jeden z nich, w przeciwnym

razie S = 1.

SEMAFOR OGÓLNY

definicja praktyczna :

• opuszczenie semafora ogólnego P(S) :

jeżeli S > 0, to S =S -1, w przeciwnym razie wstrzymaj

działanie procesu wykonującego tę operację;

• podniesienie semafora ogólnego V(S) :

jeżeli są procesy wstrzymane w wyniku wykonania operacji

opuszczania semafora S, to wznów jeden z nich, w przeciwnym

razie S = S + 1 .

Definiowanie zmiennych semaforowych w programach

semafor ogólny

semaphore SEM = 4;

semafor binarny

binary semaphore SEM = 1;

PRZYKŁADY PROGRAMÓW WSPÓŁBIEŻNYCH

Z WYKORZYSTANIEM SEMAFORÓW

WZAJEMNE WYKLUCZENIE

int n = ? ;

binary semaphore S = 1;

process P ( int i ) /* i = 0 . . n-1 */

{ while {true}

{ własne_sprawy;

PB(S);

sekcja_krytyczna;

VB(S);

}

}

PROBLEM PIĘCIU FILOZOFÓW

Rozwiązanie z możliwością blokady

binary semaphore widelec [5] = {1, 1, 1, 1, 1};

process FILOZOF(int i) /* i = 0 . . 4 */

{ while {true}

{ myślenie;

PB(widelec [i] );

PB(widelec[ (i+1) % 5 ] );

jedzenie;

VB(widelec [i] );

VB(widelec[ (i+1) % 5 ] );

}}

PROBLEM PIĘCIU FILOZOFÓW

Rozwiązanie poprawne

binary semaphore widelec [5] = {1, 1, 1, 1, 1};

semaphore LOKAJ = 4;

process FILOZOF(int i) /* i = 0 . . 4 */

{ while {true}

{ myślenie;

P(LOKAJ);

PB(widelec [i] );

PB(widelec[ (i+1) % 5 ] );

jedzenie;

VB(widelec [i] );

VB(widelec[ (i+1) % 5 ] );

V(LOKAJ);

} }

MONITORY

Monitor to zebrane w jednej konstrukcji programowej pewne wyróżnione zmienne oraz procedury i funkcje synchronizujące działające na tych zmiennych. Część tych procedur i funkcji jest udostępniona na zewnątrz monitora. Tylko ich wywołanie umożliwia procesom dostęp do zmiennych ukrytych wewnątrz monitora.

• Wykonanie procedury monitora jest sekcją krytyczną wykonu- jącego go procesu. Oznacza to, że w danej chwili tylko jeden spośród współbieżnie wykonujących się procesów może wykonywać procedurę monitora.

• Oprócz tego istnieje możliwość wznawiania i wstrzymywania procesów wewnątrz procedury monitorowej. Służą do tego zmienne specjalnego typu warunkowego (condition). Na zmiennych tego typu można wykonywać dwie operacje:

- wait ( c ) powoduje wstrzymanie procesu wykonującego tę

operację i wstawienie go na koniec kolejki związanej ze

zmienną c , z jednoczesnym zwolnieniem monitora,

- signal ( c ) powoduje wznowienie pierwszego procesu wstrzy

manego w kolejce związanej ze zmienną c . Jeśli operacja ta nie

jest ostatnią instrukcją procedury monitorowej, to proces wyko-

nujący tę operację jest wstrzymany aż do chwili, gdy wznowio-

ny przezeń proces zwolni monitor. Jeśli w chwili wywołania

operacji signal żaden proces nie czeka w kolejce, to operacja ta

ma efekt pusty.

PROCES A MONITOR M

procedure P(x : integer);

M.P(y) begin

Procesy . . .

oczekujące

na wejście wait ( C ) ;

. . .

Procesy

wstrzymane signal ( C ) ; Procesy

po signal oczekujące na C

. . .

end;

• Gdy jakiś proces wykonuje w danej chwili procedurę monitora, jednoczśnie mogą żądać dostępu do monitora inne procesy. Będą one czekać w trojakiego rodzaju kolejkach :

• Procesy, które chcą rozpocząć wykonanie procedury monitora, czekają w kolejce wejściowej, a te, które zostały wstrzymane w wyniku operacji wait, czekają w kolejce związanej ze zmienną c. Na wejście do monitora, odłożone na stos, mogą również czekać procesy, które wykonały operację signal, ale same zostały wstrzymane.

• Jeżeli proces P znajdujący się wewnatrz monitora wykona operację signal(c) , będzie odłożony na stos, a do monitora wejdzie pierwszy proces czekający w kolejce związanej ze zmienną c .

• Jeżeli proces P opuści monitor albo wykonując operację wait(c), albo kończąc procedurę monitora, to do monitora wejdzie proces odłożony, który poprzednio wznowił proces P . Jeśli takiego procesu nie ma, oznacza to. że stos procesów odłożonych jest pusty i do monitora może wejść proces czekający w kolejce wejściowej.

PROBLEM PIĘCIU FILOZOFÓW

ROZWIĄZANIE POPRAWNE Z MONITOREM

monitor WIDELCE;

var WIDELEC : array [0 .. 4] of condition;

zajęty : array [0 .. 4] of boolean;

LOKAJ : condition;

jest , i : integer;

export procedure BIORĘ (i : integer);

begin

if jest = 4 then wait (LOKAJ); jest := jest + 1;

if zajęty[i] then wait (WIDELEC [ i ] );

zajęty [ i ] := true;

if zajęty[ (i+1) mod 5] then wait (WIDELEC [(i+1) mod 5 ] );

zajęty [ (i+1) mod 5 ] := true;

end; {BIORĘ}

export procedure ODKŁADAM (i : integer);

begin

zajęty [i] := false;

SIGNAL (WIDELEC [i] );

zajęty[ (i+1) mod 5] := false;

signal (WIDELEC [ (i+1) mod 5 ] );

jest := jest -1; SIGNAL (LOKAJ);

end; {ODKŁADAM}

begin

for i := 0 to 4 do zajęty [i] := false;

jest := 0;

end; {WIDELCE}

PROBLEM PIĘCIU FILOZOFÓW

ROZWIĄZANIE POPRAWNE Z MONITOREM

process FILOZOF (i: 0 .. 4);

begin

while (true) do

begin

myślenie;

WIDELCE . BIORĘ (i);

jedzenie;

WIDELCE . ODKŁADAM (i);

end;

end;

---