pwir7-print.pdf

Programowanie współbiezne i rozproszone – czesc VII

Marcin Szpyrka

Katedra Automatyki

Akademia Górniczo-Hutnicza w Krakowie

2008/09

Programowanie współbiezne i rozproszone – czesc VII, c Marcin Szpyrka 2008/09

Wzajemne wykluczanie – opis problemu (przypomnienie)

– Nalezy zsynchronizowac n procesów, z których kazdy w niesko nczonej petli na przemian

zajmuje sie własnym algorytmem i wykonuje sekcje krytyczn a. Zsynchronizowac nalezy

je w taki sposób, aby wykonanie sekcji krytycznych jakichkolwiek dwóch lub wiecej

procesów nie pokrywało sie w czasie.

– Proces moze zatrzymac sie w swojej sekcji lokalnej, ale nie moze zatrzymac sie ani

zapetlic, podczas wykonywania swoich protokołów (wejsciowego i wyjsciowego) ani

sekcji krytycznej.

– W programie nie moze wyst apic blokada – jesli kilka procesów próbuje wejsc do swoich

sekcji krytycznych, to jednemu musi sie to w ko ncu udac.

– Zaden z procesów nie moze zostac zagłodzony – jesli proces zgłasza zamiar wejscia do

sekcji krytycznej przez rozpoczecie wykonania protokołu wstepnego, to w ko ncu musi

osi agn ac cel.

– Przy braku rywalizacji o sekcje krytyczn a pojedynczy proces, który chce wejsc do swojej

sekcji krytycznej, wejdzie do niej natychmiast.

Programowanie współbiezne i rozproszone – czesc VII, c Marcin Szpyrka 2008/09

Wzajemne wykluczanie – algorytm centralnego serwera

– Rozwi azanie problemu polega na stworzeniu serwera (koordynatora), który udziela

pozostałym procesom pozwolenia na wejscie do sekcji krytycznej.

– Proces, który chce wejsc do zasobu dzielonego, wysyła do serwera komunikat

z zamówieniem i oczekuje na odpowiedz, czesto traktowan a jako otrzymanie zetonu

daj acego prawo do wejscia.

– Jezeli sekcja krytyczna jest pusta serwer natychmiast wysyła procesowi zeton, a proces

moze wejsc do sekcji krytycznej.

– Jezeli zeton jest w posiadaniu innego procesu, to proces zamawiaj acy jest ustawiany w

kolejce serwera.

– Po wyjsciu z sekcji krytycznej kazdy z procesów zwraca zeton serwerowi.

– Serwer udostepnia wejscie do sekcji, procesom znajduj acym sie w kolejce, kieruj ac sie

priorytetem najstarszego wpisu. Pozwolenie na wejscie uzyskuje proces, który ustawi sie

w kolejce najwczesniej.

– UWAGA: W systemie takim awaria serwera, przez który przechodz a wszystkie operacje,

moze byc bardzo niebezpieczna dla całego systemu.

Programowanie współbiezne i rozproszone – czesc VII, c Marcin Szpyrka 2008/09

Algorytm centralnego serwera

serwer

kolejka

sekcjakrytyczna

wejście

zamówienie

żetonu

zwrot

żetonu

przekazanie

żetonu

Na rysunku a) widac sytuacje, w której w sekcji krytycznej znajduje sie proces P3 (jest w

posiadaniu zetonu), proces P4 wysłał juz zamówienie zetonu do serwera wczesniej, natomiast

proces P2 wysyła własnie zamówienie na zeton. Kolejny krok algorytmu pokazuje zachowanie

sie poszczególnych procesów oraz zetonu. Proces P2 ustawił sie w kolejce lokalnej serwera,

zeton został zwrócony i natychmiast zostanie przekazany procesowi zamawiaj acemu

najwczesniej, tzn. procesowi P4.

Programowanie współbiezne i rozproszone – czesc VII, c Marcin Szpyrka 2008/09

Zegary logiczne

– W systemie rozproszonym utrzymywanie pojecia globalnego czasu jest zadaniem

trudnym, gdyz kazdy procesor posługuje sie własnym lokalnym zegarem. Rozwi azania

wymagaj a wówczas dwa problemy: Jak synchronizowac te lokalne zegary z zegarami

ﬁzycznymi swiata rzeczywistego? Jak wzajemnie synchronizowac te zegary?

– W wielu zastosowaniach wystarczy wzajemna spójnosc róznych zegarów, ich zgodnosc z

czasem rzeczywistych jest nieistotna. W tym kontekscie mówimy o zegarach logicznych.

– Kazdy komputer zwieksza swój zegar (moze to byc zwykła zmienna) o jedn a jednostke po

kazdej wykonanej operacji. Gdy otrzyma komunikat ostemplowany przez nadawce czasem

pózniejszym niz pokazuje logiczny zegar, oznacza to, ze zegar ten sie spóznia w stosunku

do zegara nadawcy i logiczny zegar odbiorcy trzeba przestawic na czas co najmniej o jedn a

jednostke pózniejszy niz czas nadania komunikatu. W ten sposób nastepstwo zdarze n

widzianych przez jeden komputer bedzie zgodne ze wskazaniami jego logicznego zegara.

Dla kazdych dwóch zdarze n w systemie bedzie mozna ustalic, które było wczesniej, pod

warunkiem, ze komputery, na których zaszły te zdarzenia, komunikowały sie bezposrednio

lub posrednio. Jesli zas nie komunikowały sie, to zaden komputer w systemie nie wie o

zajsciu obu tych zdarze n, ich kolejnosc dla nikogo nie jest zatem wazna.

Programowanie współbiezne i rozproszone – czesc VII, c Marcin Szpyrka 2008/09

Wzajemne wykluczanie – algorytm Lamporta

– Algorytm Lamporta zakłada, ze wszystkie procesy w systemie posiadaj a lokaln a kolejke

przechowuj ac a wszystkie komunikaty z adania.

– Proces, który chce wejsc do sekcji krytycznej, tworzy komunikat zamów, który jest

wysyłany do innych procesów, a takze jest umieszczany w lokalnej kolejce. Przy wysłaniu

komunikatu, dodawany jest do niego numer, zawieraj acy informacje, z którego procesu

wysłano komunikat oraz znacznik czasu.

– Proces odbieraj acy komunikat zamów, natychmiast wysyła odpowiedz ze znacznikiem

czasu, a przybyłe z adanie umieszcza w swojej kolejce.

– Proces wysyłaj acy komunikat zamów, bedzie mógł wejsc do sekcji krytycznej, jezeli jego

komunikat bedzie znajdował sie na pocz atku kolejki procesu wysyłaj acego oraz gdy jego

komunikat zostanie odebrany przez inne procesy, a otrzymana odpowiedz bedzie miała

wiekszy znacznik czasu od znacznika czasu z adania.

– Po opuszczeniu sekcji krytycznej proces usuwa własny numer z kolejki i zawiadamia

wszystkie inne procesy w systemie o zwolnieniu zasobu dzielonego. Wówczas procesy

otrzymuj ace komunikat zwalniaj acy usuwaj a z kolejki z adanie z numerem procesu

opuszczaj acego sekcje.

– UWAGA: Stosowanie tego rozwi azania jest ograniczone ze wzgledu koniecznosc

przesyłania zbyt duzej liczby komunikatów w systemie. Algorytm Lamporta, przy

załozeniu, ze w systemie jest n procesów, wymaga wymiany 3(n 1)komunikatów.

Programowanie współbiezne i rozproszone – czesc VII, c Marcin Szpyrka 2008/09

Algorytm Lamporta

P3[5]

P1[9]

P2[11]

P1[9]

P3[5]

P1[9]

P2[11]

P3[5]

P1[9]

P2[11]

W sytuacji pierwszej kazdy z procesów wysyła zamówienie ze znacznikiem czasu do kazdego z

procesów w systemie, a swój znacznik ustawia w lokalnej kolejce. Nastepnie dokonywana jest

klasyﬁkacja zamówie n od wszystkich procesów i w lokalnej kolejce s a ustawiane poszczególne

zamówienia, a proces z najmniejszym znacznikiem uzyskuje dostep do sekcji krytycznej po

otrzymaniu odpowiedzi od innych procesów. Przy opuszczaniu zasobu dzielonego proces

wysyła komunikaty zwalniaj ace do pozostałych procesów w celu umozliwienia im wejscia do

sekcji.

Programowanie współbiezne i rozproszone – czesc VII, c Marcin Szpyrka 2008/09

Wzajemne wykluczanie – algorytm Ricarta i Agrawali

– Kazdy proces chc acy wejsc do sekcji krytycznej, rozsyła komunikat do wszystkich

procesów w systemie i moze wejsc do sekcji, gdy dostanie odpowiedz od pozostałych

procesów. Wysyłane komunikaty zawieraj a znacznik czasu i identyﬁkator nadawcy.

– Przyjmuje sie, ze: istnieje jedna sekcja krytyczna, wszystkie procesy znaj a wzajemnie

swoje adresy, wszystkie komunikaty zostan a w ko ncu dostarczone i kazdy proces

utrzymuje swój zegar logiczny (znacznik czasu).

– Proces, który otrzymał od innego procesu komunikat zamawiaj acy wejscie do sekcji,

odpowiada pozytywnie, jezeli sam wczesniej nie czeka na dostep. Jezeli proces wysłał

wczesniej prosbe i jeszcze nie uzyskał wszystkich odpowiedzi, to o tym kto pierwszy

wykona sekcje krytyczn a decyduje czas wysłania prósb:

– jezeli zapytywany proces wysłał swoja prosbe pózniej, to odpowiada pozytywnie;

– jezeli prosby zostały wysłane w tym samym momencie, to o kolejnosci decyduj a priorytety;

– w kazdym innym przypadku zapytywany proces wstrzymuje sie z odpowiedzi a, az do chwili, gdy

sam sko nczy wykonywac swoj a sekcje krytyczn a – wówczas odpowiada pozytywnie wszystkim,

którym jeszcze nie odpowiedział.

– Wejscie do sekcji krytycznej moze nast apic tylko wówczas gdy proces wysyłaj acy z adanie

otrzyma od kazdego innego procesu odpowiedz. Gdy proces wykonał swoje zadania

w sekcji krytycznej, moze j a opuscic, informuj ac jednoczesnie o swym kroku procesy,

których z adania przetrzymuje w lokalnej kolejce.

Programowanie współbiezne i rozproszone – czesc VII, c Marcin Szpyrka 2008/09

Algorytm Ricarta i Agrawali

Powyzsza ilustracja przedstawia sytuacje, w której współbiezne zamówienie wejscia do sekcji

krytycznej wysyłaj a procesy P1 i P2. Proces P3 w przypadku otrzymania zamówienia odpowie

natychmiast (nie jest zainteresowany wejsciem do zasobu dzielonego w danej chwili). Proces

P2 odbieraj ac komunikat zamówienie od procesu P1 stwierdzi, ze jego własne zamówienie ma

znacznik czasu mniejszy niz zamówienie procesu P1 i nie udzieli odpowiedzi. Proces P1

otrzymuj ac komunikat od procesu P2 z mniejszym znacznikiem czasu, odpowie natychmiast,

umozliwiaj ac wejscie do sekcji procesowi P2. W momencie opuszczenia sekcji krytycznej,

proces P2 wysyła odpowiedz do procesu P1, umozliwiaj ac mu wejscie do sekcji.

UWAGA: Awaria dowolnego procesu uniemozliwia działanie algorytmu.

Programowanie współbiezne i rozproszone – czesc VII, c Marcin Szpyrka 2008/09

Wzajemne wykluczanie – algorytm Le Lanna

– Realizacja wzajemnego wykluczania pomiedzy procesami odbywa sie w oparciu

o pierscie n logiczny zbudowany z procesów znajduj acych sie w systemie. Kazdy proces

ma swój adres, a komunikaty (i zeton) s a przekazywane w jednym ustalonym kierunku,

wokół całego pierscienia.

– Proces otrzymuj ac zeton od s asiada wchodzi do sekcji (jezeli tego z adał), a wychodz ac

z sekcji przekazuje go do s asiada zgodnie z kierunkiem poruszania sie komunikatów

w pierscieniu.

– Jezeli proces jest zainteresowany korzystaniem z zasobu dzielonego, przekazuje zeton

natychmiast po jego otrzymaniu. W sytuacji w której zaden z procesów nie jest

zainteresowany korzystaniem z zasobu, zeton kr azy bez przerwy w pierscieniu.

– UWAGA: Awaria jednego z procesów w systemie moze spowodowac awarie całego

systemu. Naprawa takiej usterki polega wówczas na usunieciu uszkodzonego procesu

z systemu. Moze zaistniec sytuacja, ze uszkodzeniu ulegnie proces, który w danej chwili

przechowywał zeton. Wówczas po upewnieniu sie, ze proces rzeczywiscie uległ awarii

zwołuje sie elekcje, która wybiera proces do regeneracji zetonu.

Programowanie współbiezne i rozproszone – czesc VII, c Marcin Szpyrka 2008/09

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: