pwir4-print.pdf

(124 KB) Pobierz
Programowanie wspólbiezne i rozproszone -- czesc IV
Programowanie współbiezne i rozproszone – czesc IV
Marcin Szpyrka
Katedra Automatyki
Akademia Górniczo-Hutnicza w Krakowie
2008/09
Programowanie współbiezne i rozproszone – czesc IV, c Marcin Szpyrka 2008/09
1
Zasoby dzielone i komunikacja
– Zasób (dane, zasoby sprzetowe itp.) o który współzawodnicz a co najmniej dwa procesy
nazywany jest zasobem dzielonym. Współzawodnictwo wystepuje wówczas, gdy dwa
procesy ubiegaj a sie o ten sam zasób dzielony.
– Czesc procesu, w której wykorzystywany jest zasób dzielony, nazywana jest sekcj a
krytyczn a. Wykonywanie sekcji krytycznej poprzedzone jest wykonaniem protokołu
wstepnego, natomiast po sekcji krytycznej proces wykonuje protokół ko ncowy.
– Problem współzawodnictwa procesów o zasób, który jednoczesnie moze byc
wykorzystywany tylko przez jeden proces, nazywany jest wzajemnym wykluczaniem.
– Komunikacja jest sytuacj a, w której dwa procesy (nadawca i odbiorca) porozumiewaj a sie
w celu przesłania danych.
– Komunikacje nazywamy synchroniczn a jezeli nadawca „z ada”, by odbiorca był gotów do
odebrania komunikatu. Przy komunikacji synchronicznej mamy do czynienia z
synchronizacj a procesów, tzn. uporz adkowaniem ich w czasie. Jezeli jeden z procesów
jako pierwszy dotrze do punktu synchronizacji, to musi czekac na drugi proces.
– Komunikacje nazywamy asynchroniczn a jezeli nadawca moze wysłac wiadomosc i
kontynuowac prace bez wstrzymania, bez wzgledu na stan odbiorcy. Przy komunikacji
asynchronicznej konieczne jest buforowanie komunikatów.
Programowanie współbiezne i rozproszone – czesc IV, c Marcin Szpyrka 2008/09
2
393671560.007.png 393671560.008.png
Semafory
Semafor jest zmienn a całkowit a przyjmuj ac a jedynie wartosci nieujemne. Na semaforze S
mozna wykonac dwie operacje:
– P(S)(Czekaj) – Jesli S>0, to S:=S 1, w przeciwnym razie wstrzymaj wykonywanie
procesu. Taki proces nazywamy wstrzymanym przez semafor S.
– V(S)(Sygnalizuj) – Jesli s a jakies procesy wstrzymane przez semafor S, to wznów jeden z
nich, w przeciwnym razie S:=S+1.
– Operacje P(S)i V(S)s a instrukcjami atomowymi, np.: zadna instrukcja nie moze byc
wpleciona miedzy sprawdzenie czy S>0, a zmniejszenie S lub wstrzymanie procesu.
– Semafor musi miec nadan a nieujemn a wartosc pocz atkow a.
– Operacja V(S)musi wznowic jeden ze wstrzymanych procesów. Ta definicja nie okresla,
który proces bedzie wznowiony.
– Semafor przyjmuj acy dowolne nieujemne wartosci nazywamy semaforem ogólnym.
Semafor przyjmuj acy jedynie wartosci 0 i 1 nazywamy semaforem binarnym.
Programowanie współbiezne i rozproszone – czesc IV, c Marcin Szpyrka 2008/09
3
Semafory
Semafor spełnia nastepuj ace niezmienniki:
S > 0;
S=S 0 +V P;
gdzie:
– S 0 jest pocz atkow a wartosci a semafora,
– V okresla liczbe operacji sygnalizuj, wykonanych na S,
– P jest liczb a zako nczonych operacji czekania na S.
Wady semaforów:
– Semafor, nie jest mechanizmem strukturalnym.
– Semafor jest mechanizmem pierwotnym niskiego poziomu.
– Synchronizacja w systemie wielomodułowym przy uzyciu semaforów powoduje
rozproszenie operacji na tym samym semaforze do wielu modułów.
– Bł ad w uzyciu semafora zagraza działaniu całego systemu i jest wyj atkowo trudny do
wykrycia.
Programowanie współbiezne i rozproszone – czesc IV, c Marcin Szpyrka 2008/09
4
393671560.009.png 393671560.010.png 393671560.001.png 393671560.002.png
Monitory
– Monitor jest to konstrukcja grupuj aca zmienne dzielone i wykonywane na nich operacje.
Dostep do zmiennych spoza monitora mozliwy jest wył acznie poprzez wywołanie
procedury monitorowej, która wykona odpowiednie działania na tych zmiennych.
Potocznie mówi sie o procesie, który rozpoczyna wykonywanie procedury monitorowej,
ze wchodzi do monitora, gdy wykonuje procedure to przebywa wewn atrz monitora,
natomiast gdy ko nczy wykonanie procedury, to wychodzi z monitora.
– Implementacja monitora zapewnia wzajemne wykluczanie wykona n wywoływanych w
nim procedur. W monitorze moze przebywac co najwyzej jeden proces. Konsekwencj a
tego jest kolejka wejsciowa procesów do monitora.
– Monitor nie jest procesem programu współbieznego, lecz statycznym modułem
zawieraj acym deklaracje danych i procedur. Monitor jest mechanizmem strukturalnym.
Jeden monitor najczesciej synchronizuje dostep do jednego zasobu (rodzaju zasobów).
– Jesli ten sam monitor jest wywoływany przez dwa procesy, to implementacja gwarantuje,
ze te procesy bed a obsłuzone w takiej kolejnosci, by zapewnic wzajemne wykluczanie.
Jesli s a wywoływane rózne monitory, ich wykonywania mog a byc przeplatane.
– Mozliwa jest symulacja semaforów za pomoc a monitorów i na odwrót. Monitor jest
jednak abstrakcj a wyzszego rzedu niz semafor.
Programowanie współbiezne i rozproszone – czesc IV, c Marcin Szpyrka 2008/09
5
Monitory
Procesy mog a warunkowo opuszczac monitor, aby poczekac na spełnienie warunku
umozliwiaj acego kontynuacje działa n. Do tego celu słuz a specjalne zmienne warunkowe, na
których mozna wykonac operacje:
– wait(C)– zawieszenie wywołuj acego procedure procesu w kolejce zmiennej C
z jednoczesnym opuszczeniem monitora i umozliwieniem wejscia do niego innemu
procesowi (który moze dopomóc, by zaszedł warunek wymagany przez C);
– signal(C)– w przypadku istnienia niepustej kolejki procesów zwi azanej ze zmienn a C
wznowienie pierwszego z nich; proces wraca do monitora i kontynuuje obliczenia od
pierwszej instrukcji za instrukcj a wait.
Operacje wait i signal mog a byc wykonywane tylko przez procedury monitorowe.
Programowanie współbiezne i rozproszone – czesc IV, c Marcin Szpyrka 2008/09
6
393671560.003.png 393671560.004.png
Monitory
– Z jednym monitorem moze byc zwi azanych kilka kolejek zawieszonych procesów.
Zawieszony proces moze byc wznowiony wył acznie przez inny proces wykonuj acy
procedure monitorow a.
– Operacja signal(C)oznacza sygnalizuje, ze zaszło C w efekcie czego pierwszy z
zawieszonych procesów zostanie wznowiony. Operacja ta jest bezpamieciowa – jesli
zaden proces nie jest wstrzymany w kolejce do C, to jest ona ignorowana.
– Wymaga sie, by wznowiony proces zaczynał sie wykonywac natychmiast po instrukcji
signal. Daje to wznowionemu procesowi wyzszy priorytet niz procesom, które dopiero
musz a wejsc do monitora.
– Rodzaj monitora, w którym operacja signal moze byc wył acznie ostatni a instrukcj a
procedury monitorowej nazywa sie monitorem ograniczonym. W takim przypadku proces
wznawiaj acy inny definitywnie opuszcza monitor.
Programowanie współbiezne i rozproszone – czesc IV, c Marcin Szpyrka 2008/09
7
Obiekty chronione
– Obiekt chroniony w jezyku Ada jest odpowiednikiem monitora.
– Obiekt chroniony, podobnie jak monitor, reguluje dostep do współdzielonych zmiennych
poprzez zdefiniowane operacje: funkcje procedury i wejscia.
– Funkcje pozwalaj a tylko na odczyt danych współdzielonych, natomiast procedury
i wejscia umozliwiaj a czytanie i modyfikacje.
– Wejscia tym rózni a sie od procedur, ze posiadaj a bariery (wyrazenia logiczne). Tresc
wejscia moze byc wykonana tylko wtedy, gdy warunek jest spełniony. W przeciwnym
przypadku zadanie wywołuj ace jest wstawiane do kolejki zwi azanej z wejsciem, gdzie
czeka az bariera osi agnie wartosc True.
Programowanie współbiezne i rozproszone – czesc IV, c Marcin Szpyrka 2008/09
8
393671560.005.png
Obiekty chronione
Zasady rz adz ace dostepem do obiektu chronionego mozna opisac nastepuj aco:
– Zadanie wywołuj ace procedure lub funkcje wchodzi do obiektu chronionego, realizowana
jest tresc podprogramu, po czym zadanie opuszcza obiekt.
– Zadanie wywołuj ace wejscie wchodzi do obiektu chronionego. Jesli bariera jest spełniona,
to realizowana jest tresc wejscia, nastepnie zadanie opuszcza obiekt. Jesli nie, to zadanie
umieszczane jest w kolejce zwi azanej z t a barier a, gdzie oczekuje na spełnienie warunku.
– Po zrealizowaniu kazdej procedury lub wejscia ponownie obliczane s a bariery przy
wejsciach z niepustymi kolejkami zada n. Jesli któras z barier osi agnie wartosc True, to
pierwsze zadanie wraca do obiektu chronionego i wykonywana jest tresc wejscia, po czym
zadanie opuszcza obiekt.
Programowanie współbiezne i rozproszone – czesc IV, c Marcin Szpyrka 2008/09
9
Obiekty chronione – przykład
protected SharedVariable is -- specyfikacja
procedure Read(X: out integer);
-- operacje chronione
procedure Write(X: in integer);
private -- czesc prywatna
V: integer := 0;
end ;
protectedbody SharedVariable is -- implementacja
procedure Read(X: out integer) is
begin
X := V;
end ;
procedure Write(X: in integer) is
begin
V := X;
end ;
end ;
protectedtype SharedVariable is ... -- typ chroniony
Definicja obiektu chronionego składa sie z dwóch czesci: specyfikacji i implementacji.
Specyfikacja dzielona jest na czesc widoczn a i prywatn a. Czesc prywatna zawiera ukryte
współdzielone dane (moze zawierac równiez prywatne podprogramy i wejscia).
W czesci implementacyjnej nie wolno deklarowac zmiennych.
Programowanie współbiezne i rozproszone – czesc IV, c Marcin Szpyrka 2008/09
10
393671560.006.png

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin