95807

Sypiemy operacyjne - notatka do wyMadj

•    Zastosowanie przy synchronizacji (np. gdy operacjal musi się wykonać po operacji2): s:=0

1 proces:    op1;    2proces:    czekaj(s);

sygnalizuj(s);    op2:

•    Wada: s wymaga aktywnego czekania (czas procesora!!!)

-    rozwiązanie: po czekaj(s) proces jest blokowany i umieszczany w kolejce związanej z s

-    pobranie procesu z kolejki następuje po sygnalizuj(s)

-    wtedy semafor to rekord (zmienna całk. + lista procesów)

-    algorytm obsługi kolejki nie ma znaczenia dla procesora

•    Realizacja niepodzielności:

-    1 procesor: blokada przerwań na czas operacji

-    wiele procesorów: np. pojedyncza instrukcja procesora „test&set"

4.3 Blokady.

• Stan blokady: każdy proces w zbiorze procesów czeka na zdarzenie, które może być spowodowane tylko przez inny procesu z tego samego zbioru (zdarzeniem może być np. przydział lub zwolnienie zasobu), np.:

Semafory A i B mają wartość 1:

PO: wait(A); wait(B)

P1:wait(B);wait(A)

•    Przypadek szczególny: tzw. głodzenie - czekanie w nieskończoność pod semaforem - gdy np. zastosujemy kolejkę LIFO semafora.

•    Warunki powstania blokady:

1.    Wzajemne wyłączanie (co najmniej 1 zasób musi być niepodzielny)

2.    Przetrzymywanie i oczekiwanie (proces przetrzymujący co najmniej jeden zasób czeka na przydział dodatkowych zasobów będących w posiadaniu innych procesów).

3.    Nie ma wywłaszczania z zasobów.

4.    Cykliczne czekanie (istnieje zbiór czekających procesów {PO, P1, Pn }, takich że P 0 czeka na zasób przetrzymywany przez P1 . P1 czeka na zasób przetrzymywany przez P2 ..... P n czeka na zasób przetrzymywany przez PO .

-> (4 implikuje 2, więc podane warunki nie są niezależne)

•    Opis blokady:

-    zbiór procesów P, zasobów Z, .graf przydziału zasobów" - dwudzielny (krawędzie łączą wierzchołki należące do 2 rozdzielnych zbiorów - w tym przypadku zasobów i procesów) graf skierowany.

-    krawędzie P -» Z,: krawędź zamówienia

-    krawędzie Z, -> P_; : krawędź przydziału

•    Rysunek:

■    proces p -> kółko,

-    zasób z -» prostokąt

-    1 egzemplarz zasobu z -» kropka w prostokącie.

-    krawędź przydziału zaczyna się od kropki

•    Zdarzenia w systemie:

■    zamówienie z przez p : dodajemy krawędź p -> z

■    realizacja zamówienia : dodajemy krawędź z -Z p, usuwamy p -> z

-    zwolnienie zasobu : usuwamy krawędź

13