Koordynacja procesów

Sekcje krytyczne

• interpretacja przetwarzania współbieżnego dla pojedynczego CPU: proces rozpoczyna się przed zakończeniem poprzedniego

•  możliwy konflikt przy operacjach na danych dzielonych (np. nawet instrukcja x:=x=1 to 3 instrukcje (mov AX,x; inc AX; mov x,AX) procesora...

• Wniosek: każdy z procesów ma (może mieć) segment kodu nazywany sekcją krytyczną (SK). SK procesów podlegają wzajemnemu wykluczaniu się w czasie.

• Cechy rozwiązania problemu SK:

- wzajemne wyłączanie SK

- ograniczone (skończone) czekanie na wejście do SK

• postęp: kandydują tylko procesy zgłaszające chęć wejścia do SK

• np.(ogólna struktura procesu i przykładowe rozwiązanie):

repeat

while x<>0 do nic (sekcja wejściowa)

<SK> (SK)

x:=1 (sekcja wyjściowa)

<reszta kodu procesu>

until false (narzucone naprzemienne (czyli nie spełniające warunku postępu) wykonanie SK dla 2(może być więcej) procesów)

• Poprawne rozwiązanie dla 2 procesów:

var flaga: array[o..1] of Boolean

numer: 0..1

repeat

flaga[i]:=TRUE (chcę wejść)

numer:=j (założenie, że drugi chce wejść)

while (flaga[j] AND numer:=j)do nic

<SK>

flaga[i]:=FALSE

<reszta kodu procesu>

until false (bez zmiennej numer możliwe byłoby ustawienie obu flag przez procesy w dwóch kolejnych instrukcjach procesora (po pechowym przełączeniu kontekstu) i wieczne ich zapętlenie...)

4.2 Semafory

• Semafor ogólne popularne rozwiązanie problemu SK i synchronizacji

• Semafor s to zmienna całkowita dostępna po inicjacji za pomocą tylko 2 operacji:

- czekaj(s): while s <= 0 do nic; s := s-1;

- sygnalizuj(s): s := s+1;

• Interpretacja s: ilość wolnych zasobów; w tym przypadku zasobem jest SK

• Operacje na semaforach są NIEPODZIELNE! Implementacja:

- na pojedynczym CPU – zablokowanie przerwań na czas operacji

- w systemie wieloprocesorowym instrukcja procesora TEST&SET

• Użycie:

s:=1

repeat

czekaj(s)

<SK>

sygnalizuj(s)

<reszta kodu procesu>

until false

• Zastosowanie przy synchronizacji (np. gdy operacja1 musi się wykonać po operacji2):

s:=0

1proces: 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”

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:

P0: 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 {P0, 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 P0 .

 (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_i  Z_j : krawędź zamówienia

• krawędzie Z_j  P_i : 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  p, usuwamy p  z

• zwolnienie zasobu : usuwamy krawędź

• Blokada:

• jeżeli w grafie nie ma cyklu: nie ma blokady.

• jeżeli jest cykl a zasoby są pojedyncze to jest blokada

• jeżlei jest cykl a zasoby są wielokrotne, to może być blokada

• Postępowanie z blokadami:

• zapewnić że nigdy ich nie będzie (odp. protokół przydziału zasobów)

• pozwalać na wejście w blokadę i potem ją usuwać

• zignorować i założyć, że nie wystąpią (np. UNIX i większość popularnych s.o).

Zapobieganie i unikanie blokad.

• Zapobiec spełnieniu jednego z 4 warunków koniecznych wystąpienia blokady:

• wzajemne wyłącznie: na ogół niemożliwe; niektóre zasoby są z definicji niepodzielne (drukarka, plik do pisania...)

• Przetrzymywanie - trzeba zagwarantować, że gdy proces żąda zasobu, to nie posiada innych zasobów: pozwalać na zamówienie tylko gdy zwolni wszystkie posiadane (problem: głodzenie i nieefektywne wykorzystanie zasobów).

• Można wymagać, by proces zamawiał i dostawał wszystkie swoje zasoby zanim rozpocznie działanie lub żądał zasobów wtedy, gdy nie posiada żadnych innych - niskie wykorzystanie zasobów, możliwość zagłodzenia

• Brak wywłaszczeń: jeśli proces będący w posiadaniu zasobów żąda zasobu, którego nie można natychmiast przydzielić, to musi zwolnić wszystkie posiadane zasoby - Wywłaszczone zasoby dodaje się do listy zasobów, na które czeka proces

• Cykliczne czekanie: narzuca się uporządkowanie całkowite wszystkich typów zasobów i wymaga, by proces zamawiał zasoby we wzrastającym porządku ich numerów (metoda wyklucza powstawanie cykli)

 powyższe metody zawsze ograniczają przepustowość systemu...

• Unikanie blokad:

• Wymaga, by system posiadał pewną informację o przyszłym zapotrzebowaniu na zasoby

• W najprostszym modelu wymaga się, by proces deklarował maksymalną liczbę zasobów każdego typu, których będzie potrzebował

• Algorytm unikania blokady dynamicznie bada stan przydziału zasobów, by zapewnić, że nigdy nie dojdzie do cyklicznego oczekiwania

• Stan systemu jest określony przez liczbę dostępnych i przydzielonych zasobów oraz przez maksymalne zapotrzebowanie procesów.

• Stan bezpieczny - kiedy proces żąda dostępnego zasobu, system musi ustalić, czy natychmiastowy przydział zasobu zachowa bezpieczny stan systemu

• System jest w stanie bezpiecznym, gdy istnieje bezpieczna sekwencja <P1 , P2 , ..., Pn > : bezpieczna, jeśli dla każdego P i jego potencjalne zapotrzebowanie na zasoby można zaspokoić przez bieżąco dostępne zasoby oraz zasoby będące w posiadaniu procesów Pk , gdzie k < i.

• Jeśli system jest w stanie bezpiecznym to nie ma blokady

• Jeśli system nie jest w stanie bezpiecznym to istnieje możliwość blokady. Można unikać blokady zapewniając, że system nigdy wejdzie do stanu niebezpiecznego.

• Algorytm unikania korzystający z grafu przydziału zasobów: (dla zasobów pojedynczych):

• wprowadzamy krawędzie deklaracji (zapotrzebowania) – rysowane linią przerywaną)

• szukamy pętli w grafie (złożoność O(n²) )

• jeśli jest pętla – nie przydzielamy zasobu.

• Algorytm unikania (dla zasobów wielokrotnych – tzw. alg. bankiera. Por. A Silbershatz i.in. Podstawy syst. operacyjnych rozdz. 6.4.1 str. 208.):

• Każdy proces musi a priori złożyć maskymalne zapotrzebowanie na zasoby

• Proces żądający zasobu być może będzie musiał czekać, mimo że zasób jest dostępny..

• Gdy proces dostanie wszystkie potrzebne zasoby, to zwróci je w skończonym czasie

• Po zamówieniu przez proces zasobów system ustala czy ich przydzielenie prowadzi do stanu bezpiecznego.

Założenia:

n – liczba procesów

m – liczba typów zasobów

int Dostępne[m] – liczba zasobów określonego typu (np. Dostępne[3]=5 to 5 zasobów typu 3)

int Maks[n][m] – maksymalne żądania procesów

int Przydzielone[n][m] – przydzielone zasoby

int Potrzebne[n][m] – potrzebne zasoby (z tym, że Potrzebne[i][j]=Maks[i][j]-Przydzielone[i][j])

int Zamówienia[n][m] – aktualne zamówienia procesu.

Algorytm:

1. Jeśli Zamówienia[i] <= Potrzebne[i] to wykonaj krok 2. Wpp błąd – proces przekroczył deklarowane zapotrzebowanie.

2. Jeśli Zamówienia[i] <= Dostępne wykonaj krok 3. Wpp proces i musi czekać.

3. System próbuje przydzielić żądane zasoby procesowi i zmieniając stan systemu w następujący sposób:
   Dostępne = Dostępne – Zamówienia[i]

Przydzielone[i] = Przydzielone[i] + Zamówienia[i]

Potrzebne[i] = Potrzebne[i] – Zamówienia[i]

 Jeśli stan po zmianie jest bezpieczny, transakcja dochodzi do skutku. Jeśli nie – proces i musi czekać...

Algorytm bezpieczeństwa:

1. int Praca[m]; int Koniec[n]

2. Praca = Dostępne; Koniec[i] = FALSE dla wszystkich i

3. Znajdujemy i takie że Koniec[i]=FALSE oraz Potrzebne[i] <= Praca; Jeśli nie ma takiego i  do kroku 5.

4. Praca = Praca + Przydzielone[i]; Koniec[i] = TRUE; przejdź do kroku 2.

5. Jeśli Koniec[i] = TRUE dla wszystkich i, to system jest w stanie bezpiecznym...

 Koszt stwierdzenia czy system jest bezp. = m x n²

Wykrywanie i wychodzenie z blokady.

• W systemach bez zapobiegania i unikania musi być:

• alg. wykrywania blokady (najczęściej: poszukiwanie cykli w grafie)

• alg. wychodzenia z blokady

• Kiedy wywoływać algorytm wykrywania blokady:

• gdy nie można natychmiast przydzielić zasobu

• raz na ustalony czas (np. 10 min)

• gdy obciążenie procesora spada poniżej ~40% (blokada dławi przepustowość systemu)

• Wychodzenie z blokady (sposoby):

• Powiadomienie operatora (rozwiązuje problem ręcznie)

• Usunięcie procesu(ów) uczestniczących w blokadzie

 całej pętli (znaczny koszt, utrata częściowych wyników)

 kolejno (wywołanie szukania cykli po każdym usunięciu)

- różne kryteria wyboru ofiary (priorytet, typ, posiadane zasoby...)

• Wywłaszczanie z zasobów (potrzebna gwarancja że nie będzie głodzenia – np. wywłaszczenie możliwe max. k razy)

• Ogólnie (bsługa blokad):

• zapobieganie, unikanie, wykrywanie, usuwania

• We współczesnych systemach: - podział zasobów na klasy:

• do klas stosujemy zapobieganie cyklom

• w obrębie klas:

- zasoby wewnętrzne (bloki kontr. itp...)  uporządkowanie zasobów

- pamięć głowna 

- urządzenie i pliki  unikanie blokad