Strona główna

Unikanie impasów w systemach procesów wspóŁbieżnych robert Wójcik


Pobieranie 64.84 Kb.
Data18.06.2016
Rozmiar64.84 Kb.



UNIKANIE IMPASÓW W SYSTEMACH PROCESÓW WSPÓŁBIEŻNYCH

Robert Wójcik
Instytut Cybernetyki Technicznej

Politechniki Wrocławskiej

1. Impasy w systemach procesów współbieżnych
2. Klasyczne algorytmy unikania impasów
3. Podsumowanie

Systemy współbieżnych procesów sekwencyjnych
z wzajemnym wykluczaniem

Założenia:


  • wzajemne wykluczanie w dostępie do wspólnych zasobów,

  • jednostkowe żądania zasobowe,

  • przetrzymywanie zasobu aż do momentu rezerwacji kolejnego zasobu,

  • występowanie ograniczeń zasobowych.

Przykłady.


P1 = (o1,r1) (o2,r2) (o3,r3) - proces sekwencyjny nr 1.
P2 = (o4,r4) (o5,r3) (o6,r2) - proces sekwencyjny nr 2.
Przy założeniu jednostkowych pojemności zasobów

w systemie może pojawić się stan blokady:


P1 - zakończył operację (o2,r2),

P2 - zakończył operację (o5,r3).





S
ystem EGP (Elastyczne Gniazdo Produkcyjne)

Niech


ZP = { Pi | i =1,...,n }
zbiór zadań (procesów) realizowanych w systemie EGP.
Każdy proces ma postać:
Pi = (o1,W) (o2,M1) (o3,M2) (o4,W) (o5,M3) .

Stan blokady w systemie:


P1 - zakończył (o3,M2),

P2 - zakończył (o2,M1),

P3 - zakończył (o1,W).
Pojemności zasobów: W, M1, M2, M3 równe 1.



Stan systemu procesów
Niech

R = { ri | i = 1,...,m } - zbiór zasobów,

c(ri) - liczba jednostek zasobu ri .
OP = { oi | i = 1,...,L } - zbiór operacji realizowanych

przez procesy.


Stan systemu: S = [ s(1),...,s(i),...,s(L) ] ,
gdzie s(i) - liczba procesów realizujących

operację oi  OP.


Dla systemu EGP: S = [ s(1), s(2), s(3), s(4), s(5) ] .


Stan początkowy: S0 = [0,0,0,0,0] .

Stan blokady: Sb = [1,1,1,0,0] .



Przestrzeń stanów - zbiór stanów osiągalnych ze stanu

początkowego S0 = [0,...,0] .


Stan blokady (impasu) – stan, w którym istnieje zbiór procesów, dla których nie można już wykonać żadnego przydziału zasobowego.
Stany niebezpieczne - stany, z których po skończonej

sekwencji przydziałów osiągany jest stan blokady.


Stany zabronione - stany niebezpieczne lub

stany blokady.


Można pokazać, że w przypadku systemu EGP możliwe są 22 stany z czego 2 są stanami niedozwolonymi (jeden stan niebezpieczny i jeden stan blokady całkowitej).

Przestrzeń stanów systemu EGP


Złożoność obliczeniowa problemu
Problem unikania impasów sprowadza się do wykrywa­nia i eliminacji stanów zabronionych.
W ogólnym przypadku jest to problem trudny oblicze­niowo (NP-zupełny).


Stan badań


  • Rozwiązania (algorytmy) opracowane dla ogólnego przypadku oparte są na warunkach wystarczających dla unikania blokad, tzn. mogą odrzucać niektóre stany poprawne.




  • Przy uwzględnieniu pewnych dodatkowych założeń można podać warunki wystarczające i konieczne dla unikania blokad (stanowią podstawę algorytmów maksymalnie dopuszczających).


Klasyczne algorytmy unikania impasów



  1. Algorytm oparty na koncepcji „wszystko albo nic”.




  1. Algorytm bankiera.




  1. Algorytm oparty na koncepcji stref synchronizacji.




  1. Algorytm wykorzystujący graf żądań zasobowych.


Kryteria oceny algorytmów


  • Liczba elementów przestrzeni stanów akceptowalnych.




  • Złożoność obliczeniowa.


Algorytm „wszystko albo nic”

Ai - zbiór zasobów wykorzystywanych przez proces Pi .



Reguła alokacji zasobów
Proces Pi może rozpocząć wykonywanie operacji jeżeli

zarezerwuje wszystkie zasoby należące do zbioru Ai .

Złożoność obliczeniowa testu: O(m) ,
gdzie m = |R| - liczba zasobów.

Przykładowe protokoły:




  1. Algorytm Dekkera - synchronizacja dwóch procesów.

  2. Algorytm Pettersona – synchronizacja dwóch procesów

  3. Algorytm Dijkstry - synchronizacja n procesów.

Literatura:


Raynal M., Algorithms for Mutual Exclusion, The MIT

Press Cambridge, Massachusetts, 1986.


Stany akceptowalne - algorytm „wszystko albo nic”


Algorytm bankiera
c(ri) - liczba jednostek zasobu ri ,

mA(ri,Pj) - maksymalna liczba jednostek zasobu ri

wykorzystywana przez proces Pj .
Reguła alokacji zasobów
Proces Pj może zarezerwować żądane zasoby, jeżeli w wyniku

rezerwacji pojawi się stan, w którym zbiór aktywnych procesów można uporządkować w taki sposób, aby możliwe było spełnienie maksymalnych żądań zasobowych procesów.

Przykład. Jeden zasób w systemie: c(r) = 10. Maksymalne

żądania procesów: mA(r,P1) = 8, mA(r,P2) = 6


Stan odrzucany | Stan akceptowany

|

P1 - żąda 5 jednostek | P1 - żąda 4 jednostki



P2 - żąda 3 jednostki | P2 - żąda 5 jednostek

Bankier - wolne 2 jednostki | Bankier - wolna 1 jednostka

Złożoność obliczeniowa testu: O(mn2) ,
gdzie m - liczba zasobów, n - liczba procesów.

Literatura:


Peterson L., Silberschatz A., Operating Systems Concepts,

Addison-Wesley, Amsterdam, 1983.


W przypadku systemu EGP pojemności zasobów

W, M1, M2, M3 są równe 1.
Maksymalne żądania zasobowe procesów, dotyczące każdego zasobu są więc równe 1.
W klasycznym algorytmie Bankiera zakłada się, że w dowolnym stanie proces pi może zgłosić maksymalne żądania zasobowe dotyczące każdego zasobu, który wykorzystuje w programie.
Podczas podejmowania decyzji o przydziale zasobowym nie jest brana pod uwagę informacja o strukturze sekwencyjnych programów, a jedynie informacja o maksymalnych żądaniach zasobowych występujących w całym programie.
Stąd w danym stanie systemu uwzględnia się możliwość zażądania przez proces wszystkich zasobów wykorzystywanych w całym programie w maksymalnych ilościach, w tym nawet tych zasobów, które były wykorzystywane na już zrealizowanych etapach programu sekwencyjnego.
W takim przypadku stan
Si = [ s(1), s(2), s(3), s(4), s(5) ] = [1, 1, 0, 0, 0]
( W, M1, M2, W, M3)
zostanie uznany przez klasyczny algorytm Bankiera za niebezpieczny, gdyż proces realizujący operację s(2) korzysta z zasobu M1 i teoretycznie może zażądać każdego z potrzebnych mu w programie zasobów, tj. W, M1, M2, M3. Podobnie proces realizujący operację s(1) korzysta z zasobu W i teoretycznie może zażądać każdego z potrzebnych mu w programie zasobów, tj. W, M1, M2, M3. W przypadku, gdy pojemności zasobów są równe jeden żadne z tych żądań nie może być spełnione.

Podobna sytuacja zachodzi w przypadku stanu


Sj = [ s(1), s(2), s(3), s(4), s(5) ] = [1, 0, 0, 0, 1].
Dla procesu, realizującego operację s(5) nie jest uwzględniana informacja o tym, że proces ten kończy program i dlatego w stanie Sj Bankier przyjmuje, że w kolejnym kroku proces może żądać przydziału zasobów W, M1, M2, M3, podobnie jak proces realizujący operację s(1). Stąd stan ten zostanie uznany przez klasyczny algorytm Bankiera za niebezpieczny.
W ogólnym przypadku, w systemach, w których pojemności wszystkich zasobów są równe 1 klasyczny algorytm Bankiera będzie zawsze dopuszczał w jednym programie sekwencyjnym do realizacji tylko jeden proces, tj. będzie dopuszczał alokacje zasobów zgodnie z regułą „wszystko albo nic”.
W przypadku programów sekwencyjnych znana jest struktura programów i może ona być uwzględniona podczas wykonywania alokacji zasobowych.
Proponowana modyfikacja polega na uwzględnianiu w każdym stanie systemu maksymalnych żądań zasobowych procesów tylko w ramach niezrealizowanych fragmentów ich programów sekwencyjnych, a nie tak jak w klasycznym algorytmie Bankiera zawsze żądań zasobowych dotyczących całego programu realizowanego przez proces.
W tym podejściu nadal stan
Si = [ s(1), s(2), s(3), s(4), s(5) ] = [1, 1, 0, 0, 0]
zostanie uznany za niebezpieczny i odrzucony. Jednak już stan
Sj = [ s(1), s(2), s(3), s(4), s(5) ] = [1, 0, 0, 0, 1]
zostanie uznany za bezpieczny (otrzymaną przestrzeń stanów dopuszczalnych pokazano na kolejnym rysunku).

Stany akceptowalne – zmodyfikowany

algorytm bankiera



Algorytm strefowy
RS - zbiór zasobów, z których każdy wykorzystywany jest przez

co najmniej dwie operacje (zasoby powtarzalne),


RU - zbiór zasobów, z których każdy wykorzystywany jest przez

tylko jedną operację (zasoby niepowtarzalne),


OS - zbiór operacji korzystających z zasobów RS,
OU - zbiór operacji korzystających z zasobów RU.

Strefa synchronizacji - ciąg operacji tego samego rodzaju,

tzn. operacji klasy OS lub OU.


Zbiór stref: Z = ZS  ZU & ZS  ZU =  , gdzie
ZS - zbiór stref złożonych z operacji OS (s. powtarzalne),
ZU - zbiór stref złożonych z operacji OU (s. niepowtarzalne).
Dla systemu EGP:
Pi = (o1,W) (o2,M1) (o3,M2) (o4,W) (o5,M3) ,
RS = { W } , RU = { M1, M2, M3 } ,

OS = { o1, o4 } , OU = { o2, o3, o5 } ,

ZS = { z1, z3 } , ZU = { z2, z4 } ,
| o1 | o2 o3 | o4 | o5 | - podział na strefy .

z1 z2 z3 z4

S U S U


Algorytm strefowy

Reguły alokacji zasobów
Proces Pi może wykonać operację oj w strefie powtarzalnej

zaZS, jeżeli równocześnie spełnione są warunki:




  • żądany zasób jest dostępny ,




  • każdy zasób, wykorzystywany przez operacje następujące po oj w strefie za, posiada co najmniej jedną wolną jednostkę,




  • w strefie niepowtarzalnej zbZU, następującej po strefie powtarzalnej zaZS, istnieje operacja korzystająca z zasobu posiadającego co najmniej jedną wolną jednostkę.

Proces Pi może wykonać operację oj w strefie niepowtarzalnej

zbZU, jeżeli żądany zasób jest dostępny.

Złożoność obliczeniowa testu: O(L) ,


gdzie L - liczba operacji realizowanych przez procesy.

Literatura:


Banaszak Z., Krogh B., Deadlock Avoidance in Flexible

Manufacturing Systems ... , IEEE Trans. On Rob. and Automation, 1990, Vol.6, No.6.

Stany akceptowalne - algorytm strefowy


Algorytm grafowy
G = (R, E) - graf żądań zasobowych, gdzie
R = { ri | i = 1,...,m } - zbiór zasobów,
L - liczba operacji,
E = { (x,y) |  k{1,...,L-1} (ok ,ri) & (ok+1 ,rj) &

& (x = ri) & (y = rj) } - zbiór krawędzi.


W przypadku systemu EGP:
Pi = (o1,W) (o2,M1) (o3,M2) (o4,W) (o5,M3),
R = { W, M1, M2, M3 }.
Graf żądań zasobowych


H - zbiór zasobów należących do cyklu

o najmniejszej „pojemności”,


c(ri) - liczba jednostek zasobu ri,
c(H) =  c(ri) & ri H - pojemność „minimalnego” cyklu.
Dla systemu EGP: H = { W, M1, M2 } & c(H) = 3.

Algorytm grafowy
c(H) - pojemność „minimalnego” cyklu,
d(S) - liczba procesów (zadań) realizowanych

w systemie w stanie S.


Reguła alokacji zasobów
W stanie Sk przydział zasobu do procesu jest

dozwolony, jeżeli w osiąganym stanie Sk+1 spełniony

jest warunek

d(Sk+1)  c(H) - 1 .


W przypadku systemu EGP: d(Sk+1)  2.
Złożoność obliczeniowa testu: O(1) .

Literatura:


Peterson L., Silberschatz A., Operating Systems Concepts,

Addison-Wesley, Amsterdam, 1983.


Fanti M.P., Maione B., Mascolo S., Turchiano B.,

Event Based Feedback Control for Deadlock Avoidance

in Flexible Production Systems, IEEE Trans. On Rob. and

Automation, 1997, Vol.13, No.3.



Stany akceptowalne - algorytm grafowy


Podsumowanie



  1. Przedstawione algorytmy oparte są na warunkach wystarczających dla unikania blokad i dlatego mogą odrzucać niektóre stany bezpieczne.




  1. W przypadku systemu EGP najwięcej stanów akceptuje algorytm strefowy (17 stanów z ogólnej liczby 20 stanów bezpiecznych), następnie algorytm grafowy - 15 stanów, algorytm bankiera - 10 stanów, oraz algorytm „wszystko albo nic” - 6 stanów.




  1. Jeżeli liczba operacji realizowanych przez procesy jest niewielka oraz nie ulega zmianie w czasie działania systemu, to można wyznaczyć całą przestrzeń stanów bezpiecznych w trybie off-line.




  1. W celu zwiększenia liczby stanów akceptowalnych można stosować test „kaskadowy” złożony ze znanych algorytmów uporządkowanych według pewnego klucza (np. rosnącej złożoności obliczeniowej). W przypadku, gdy określony algorytm odrzuci badany stan wykorzystywany jest kolejny test.




©snauka.pl 2016
wyślij wiadomość