Scenariusz do ćwiczeń 3
Procesy - problematyka zastoju, szeregowanie

Spis treści

• Problematyka zastoju
  • Zapobieganie zastojowi
  • Unikanie zastoju
  • Wykrywanie zastoju
• Strategie szeregowania - ogólnie

Bibliografia

• Silberschatz, Galvin, rozdz. 7

Problematyka zastoju

Zastój (blokada)

Każdy proces w zbiorze procesów czeka na zdarzenie, które może być spowodowane tylko przez inny proces z tego samego zbioru (zdarzeniem może być przydział lub zwolnienie zasobu). to znaczy, że j.dro Linuksa jest wielowej.ciowe? Podaj scenariusze, które ilustruj. jak może doj.ć do opisywanych sytuacji demonstruj.cych tę cechę j.dra.Z

Przykłady:

• W systemie są dwie stacje taśmowe; każdy z procesów P1 i P2 ma jedną taśmę i czeka na drugą.
• Semafory A i B mają wartość 1:

  P0: wait(A); wait(B);
  P1: wait(B); wait(A);

Model systemu

• Różne typy zasobów: Z₁, Z₂, ..., Z_m; W_i jednostek zasobu Z_i; cykle CPU, pamięć, urządzenia wejścia-wyjścia.
• Każdy proces korzysta z zasobu według schematu:

  zamówienie; użycie; zwolnienie

Charakterystyka zastoju

Zastój może powstać wtw, gdy w systemie są spełnione równocześnie cztery warunki:

1. Wzajemne wykluczanie: tylko jeden proces może używać zasobu w danym czasie.
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. Brak wywłaszczania: zasoby nie podlegają wywłaszczaniu.
4. Cykliczne oczekiwanie: istnieje zbiór czekających procesów {P₀, P₁, ..., P_n}, takich że P₀ czeka na zasób przetrzymywany przez P₁, P₁ czeka na zasób przetrzymywany przez P₂, ..., P_n czeka na zasób przetrzymywany przez P₀.

Warunek 4 implikuje 2, więc podane warunki nie są niezależne.

Graf przydziału zasobów

Jest to graf skierowany o zbiorze wierzchołków W i krawędzi K:

• W składa się z dwóch podzbiorów: P={P₁, .., P_n} - procesy; Z={Z₁, ..., Z_m} - typy zasobów.
• Krawędź żądania - skierowana krawędź P_i -> Z_k.
• Krawędź przydziału - skierowana krawędź Z_k -> P_i.

Przykład grafu przydziału zasobów bez cyklu.

Przykład grafu przydziału zasobów z cyklem.

• Jeśli graf nie zawiera cyklu, to nie ma zastoju.
• Jeśli graf zawiera cykl, to:
  • jeśli zasoby są w jednym egzemplarzu, to zastój;
  • jeśli zasoby są w wielu egzemplarzach, to istnieje możliwość zastoju.

Metody postępowania z zastojem

• Zapewnić, że system nigdy nie wejdzie w stan zastoju (zapobieganie, unikanie).
• Pozwolić na wejście systemu w stan zastoju, po czym go usunąć.
• Zignorować problem i udawać, że system nigdy nie wejdzie w stan zastoju; stosowane przez większość systemów operacyjnych, w tym Unix.

Zapobieganie zastojowi

Należy zapobiec jednemu z warunków koniecznych wystąpienia zastoju:

1. Wzajemne wykluczanie: nie jest wymagane dla zasobów dzielonych; musi zachodzić dla zasobów niepodzielnych.
2. Przetrzymywanie i oczekiwanie: trzeba zagwarantować, że gdy proces żąda zasobu, to nie posiada innych 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.
3. Brak wywłaszczania:
   • 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 proces czeka.
   • Proces zostaje wznowiony, gdy będzie mógł odzyskać posiadane wcześniej zasoby oraz otrzymać nowo żądany zasób.
4. Cykliczne oczekiwanie: 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.

Unikanie zastoju

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 zastoju dynamicznie bada stan przydziału zasobów, by zapewnić, że nigdy nie dojdzie do cyklicznego oczekiwania.
• Stan przydziału zasobów 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 procesów.
• Sekwencja <P₁, P₂, ..., P_n> jest 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 P_k, gdzie k < i.
• Jeśli system jest w stanie bezpiecznym, to nie ma zastoju,
• Jeśli system nie jest w stanie bezpiecznym, to istnieje możliwość powstanai zastoju.
• Można unikać zastoju zapewniając, że system NIGDY nie wejdzie do stanu niebezpiecznego.

Algorytm korzystający z grafu przydziału zasobów

• Dla zasobów występujących pojedynczo.
• Krawędź deklaracji P_i -> Z_k wskazuje, że proces P_i może zażądać zasobu Z_k; reprezentowana linią przerywaną.
• Krawędź deklaracji przechodzi na krawędź żądania, gdy proces zażąda zasobu.
• W chwili zwolnienia zasobu krawędź przydziału przchodzi na krawędź deklaracji.
• Trzeba a priori zadeklarować zapotrzebowanie na zasoby.
• Koszt algorytmu szukania cyklu w grafie zasobów: n².

Algorytm bankiera

• Dla zasobów wielokrotnych.
• Każdy proces musi a priori złożyć maksymalne zapotrzebowanie na zasoby.
• Proces żądający zasobu być może będzie musiał czekać, mimo że zasób jest dotępny.
• Gdy proces dostanie wszystkie potrzebne zasoby, to zwróci je w skończonym czasie.
• Koszt stwierdzania, czy stan jest bezpieczny: m x n².

Szczegóły algorytmu bankiera

Struktury danych:

• Dostępne: wektor o długości m, określający liczbę dostępnych zasobów każdego typu. Dostępne[j]=k oznacza, że jest dostępnych k egzemplarzy zasobu typu Z_j.
• Maksymalne: Macierz o wymiarach n x m, definiująca maksymalne żądania każdego procesu. Jeśli Maksymalne[i,j]=k, to proces P_i może zamówić co najwyżej k egzemplarzy zasobu typu Z_j.
• Przydzielone: Macierz o wymiarach n x m, definiująca liczbę zasobów poszczególnych typów, przydzielonych do każdego z procesów. Gdy Przydzielone[i,j]=k, wówczas proces P_i ma przydzielonych k egzemplarzy zasobu typu Z_j.
• Potrzebne: Macierz o wymiarach n x m, przechowująca pozostałe do spełnienia zamówienia każdego z procesów. Element Potrzebne[i,j]=k oznacza, że do zakończenia swojej pracy proces P_i może jeszcze potrzebować k dodatkowych egzemplarzy zasobu typu Z_j. Zauważmy, że

     Potrzebne[i,j] = Maksymalne[i,j] - Przydzielone[i,j]
  

Wprowadźmy następującą notację: jeśli X jest macierzą n x m, to X_i oznacza i-ty wiersz macierzy.

Algorytm bezpieczeństwa

1. Niech Roboczy i Końcowy oznaczają wektory o długości odpowiednio m i n.

      Roboczy := Dostępne; Końcowy[i] := false dla i=1,2, ..., n
   

2. Znajdujemy i takie, że zachodzą równocześnie dwa warunki:

      Końcowy[i] = false
      Potrzebnei <= Roboczy
   

   Jeśli takie i nie istnieje, to wykonujemy krok 4.

3. Wykonujemy:

      Roboczy := Roboczy + Przydzielonei;
      Końcowy[i] := true
   

   Tu następuje skok do punktu 2.

4. Jeśli Końcowy[i]=true dla wszystkich i, to system jest w stanie bezpiecznym.

Algorytm zamawiania zasobów

Niech Zamówienia_i oznacza wektor zamówień dla procesu P_i. Jeśli Zamówienia_i[j]=k, to proces P_i potrzebuje k egzemplarzy zasobu typu Z_j. Kiedy proces P_i wykonuje zamówienie, wtedy są podejmowane następujące działania:

1. Jeśli Zamówienia_i <= Potrzebne_i, to wykonaj krok 2. W przeciwnym razie zgłoś sytuację błędną, ponieważ proces przekroczył deklarowane maksimum.
2. Jeśli Zamówienia_i <= Dostępne, to wykonaj krok 3. W przeciwnym razie proces P_i musi czekać, ponieważ zasoby są niedostępne.
3. System próbuje przydzielić żądane zasoby procesowi P_i, zmieniając stan w następujący sposób:

      Dostępne := Dostępne - Zamówieniai;
      Przydzielonei := Przydzielonei + Zamówieniai;
      Potrzebnei := Potrzebnei - Zamówieniai;
   

   Jeśli stan wynikający z przydziału zasobów jest bezpieczny, to transakcja dochodzi do skutku i proces P_i otrzymuje zamawiane zasoby, wpp proces musi czekać oraz jest przywracany poprzedni stan przydziału zasobów.

Ćwiczenie 1

W pewnym systemie z czterema typami zasobów, A, B, C i D, działa równocześnie pięć procesów, P1, P2, ..., P5. W pewnej chwili stan systemu ze względu na przydział zasobów jest następujący:

• Jaka jest bieżąca zawartość macierzy Potrzebne?
• Czy system jest w stanie bezpiecznym?
• Jaka będzie reakcja bankiera na następujące żądanie zgłoszone przez proces P3: (0,1,0,0)?

Rozwiązanie

• Bieżąca zawartość macierzy Potrzebne:



	Potrzebne
	A   B   C   D
P1	0   0   0   0
P2	0   7   5   0
P3	6   6   2   2
P4	2   0   0   2
P5	0   3   2   0



• System jest w stanie bezpiecznym. Uzasadnienie:

(P1, P4, P5, P2, P3) jest bezpieczną sekwencją procesów.




	Przydzielone	Potrzebne		Dostępne
	A   B   C   D	A   B   C   D		A   B   C   D
P1	0   0   1   2	0   0   0   0	P1	2   1   0   0
P2	2   0   0   0	0   7   5   0	P4	2   1   1   2
P3	0   0   3   4	6   6   2   2	P5	4   4   6   6
P4	2   3   5   4	2   0   0   2	P2	4   7   9   8
P5	0   3   3   2	0   3   2   0	P3	6   7   9   8
				6  7  12  12



• Reakcja bankiera na żądanie (0,1,0,0) zgłoszone przez proces P3:

(1) Sprawdzamy, czy (0,1,0,0) <= Potrzebne₃:
(0,1,0,0) <= (6,6,2,2), OK

(2) Sprawdzamy, czy (0,1,0,0) <= Dostępne:
(0,1,0,0) <= (2,1,0,0), OK

(3) Próbny przydział:
Dostępne := (2,1,0,0) - (0,1,0,0) = (2,0,0,0)
Przydzielone₃ := (0,0,3,4) + (0,1,0,0) = (0,1,3,4)
Potrzebne₃ := (6,6,2,2) - (0,1,0,0) = (6,5,2,2)


(4) Sprawdzamy, czy stan otrzymany w wyniku próbnego przydziału zasobów jest bezpieczny:

	Przydzielone	Potrzebne		Dostępne
	A   B   C   D	A   B   C   D		A   B   C   D
P1	0   0   1   2	0   0   0   0	P1	2   0   0   0
P2	2   0   0   0	0   7   5   0	P4	2   0   1   2
P3	0   1   3   4	6   5   2   2	P5	4   3   6   6
P4	2   3   5   4	2   0   0   2		4   6   9   8
P5	0   3   3   2	0   3   2   0




Wniosek: żądanie nie zostanie zrealizowane, chociaż potrzebne procesowi P3 zasoby są dostępne.

Ćwiczenie 2

W pewnym systemie z czterema typami zasobów, A, B, C i D, działa równocześnie pięć procesów, P0, P1, ..., P4. W pewnej chwili stan systemu ze względu na przydział zasobów jest następujący:

• Jaka jest bieżąca zawartość macierzy Potrzebne?
• Czy system jest w stanie bezpiecznym?
• Jaka będzie reakcja bankiera na następujące żądanie zgłoszone przez proces P1: (0,4,2)?

Wykrywanie zastoju

• Dopuszcza się wejście systemu w stan zastoju.
• Algorytm wykrywania zastoju.
• Algorytm wychodzenia z zastoju.

Zasoby pojedyncze

• Utrzymuje się graf oczekiwań: węzły odpowiadają procesom, P_i -> P_k jeśli P_i czeka na zasób będący w posiadaniu P_k.
• Okresowo wykonuje się algorytm szukania cyklu w grafie.
• Koszt algorytmu: n², gdzie n - liczba wierzchołków.

Zasoby wielokrotne

• Podobny do algorytmu bankiera.
• Koszt algorytmu wykrywania blokady: m x n².

Jak stosować algorytm wykrywania blokady:

• Kiedy i jak często wykonywać: zależy od tego, jak często może wystąpić zastój i jak wiele procesów obejmie.
• Jeśli wykonuje się algorytm w dowolnych chwilach, to w grafie może powstać wiele cykli. Wskazanie sprawcy zastoju wśród wielu zablokowanych procesów może być niewykonalne.

Wychodzenie z zastoju

• Zakończenie procesu:
  • zakończ wszystkie zablokowane procesy,
  • kończ procesy pojedynczo, aż do wyeliminowania zastoju,
  • jak wybrać proces do zakończenia:
    • priorytet procesu,
    • jak długo proces wykonywał obliczenia i ile potrzebuje czasu do zakończenia
    • zasoby używane przez proces,
    • zasoby potrzebne procesowi do zakończenia,
    • ile procesów trzeba zakończyć,
    • czy proces jest interakcyjny, czy wsadowy.
• Wywłaszczanie zasobów:
  • wybór ofiary,
  • wycofanie procesu do pewnego bezpiecznego stanu i późniejsze jego wznowienie z tego stanu,
  • głodzenie procesu - pewien proces może być stale wybierany jako ofiara; uwzględnić liczbę wycofań przy ocenie kosztów.

Łączenie metod postępowania z zastojem

Strategie szeregowania - ogólnie

Ćwiczenie 3

Wykaż, że strategia SJF (ang. Shortest Job First) jest optymalna w klasie strategii bez wywłaszczania ze względu na średni czas obrotu dla ustalonego zbioru procesów.

Dla uproszczenia można założyć, że zadania nie wykonują operacji wejścia-wyjścia.

Rozwiązanie

Dany jest zbiór procesów p1, p2, ..., pn, z czasami wykonania t1, t2, ..., tn. Wykazać, że średni czas obrotu jest minimalizowany przez wykonanie ich w kolejności od najkrótszego do najdłuższego.

Założyć dowolną kolejność wykonania, w której pi wykonuje się przed pj, ale ti > tj. Następnie pokazać, że jeśli zamienimy miejscami pi z pj, to średni czas obrotu zmaleje.

UWAGA: Wariant strategii SJF, w którym stosuje się wywłaszczanie, nosi nazwę SRTF (ang. Shortest Remaining Time First) - zadanie, które się wykonuje może zostać wywłaszczone przez nowy proces przybyły do kolejki procesów gotowych, jeśli pozostały do wykonania czas dla tego nowego procesu jest krótszy niż dla aktualnie wykonywanego procesu.

Ćwiczenie 4

Strategia PS (ang. Processor Sharing) to strategia RR z kwantem równym 0. Jest to oczywiście strategia nierealizowalna w praktyce. Jeśli w danym przedziale czasu długości t liczy się równocześnie n procesów, to każdy z nich dostaje dokładnie t/n czasu procesora.

W pewnym systemie jednoprocesorowym na wykonanie czekają następujące procesy (pierwsza liczba to czas przybycia, a druga - zapotrzebowanie na CPU):

  P1: 0,10;  P2: 0,5; P3: 0,4; P4: 6,8; P5: 6,3

Jaki jest średni czas obrotu procesu dla strategii szeregowania PS?

Rozwiązanie

Średnie czasy obrotu dla poszczególnych procesów:

  P1:30; P2:20; P3:16; P4:24; P5:14;

Średni czas obrotu dla wszystkich procesów:

  (30 + 20 + 16 + 24 + 14)/5 = 104/5 = 20.8

Ćwiczenie 5

W kolejce procesów gotowych do wykonania czekają procesy P1 .. P4. Zapotrzebowanie na CPU każdego z tych procesów wynosi 10. Jaki będzie średni czas obrotu dla tej grupy procesów, przy strategii szeregowania:

1. PS (RR z kwantem=0),
2. RR z kwantem równym np. 5 (lub innej wartości pośredniej)
3. FCFS (RR z kwantem równym nieskończoność)

Wyciągnij wnioski z tego przykładu.

Rozwiązanie

Dla PS: 4*40/4 = 160/4 = 40 Dla RR z kwantem = 5: (25+30+35+40)/4 = 130/4 = 32.5 Dla FCFS: (10+20+30+40)/4 = 100/4 = 25

Dla procesów o podobnym charakterze obliczeniowym strategia najprostsza w sensie implementacji (czyli FCFS) jest najlepsza (bo zapewnia krótki średni czas obrotu). Jej dodatkową zaletą jest minimalny narzut na przełączanie kontekstu).

Wykonać analogiczne obliczenia dla następującego zestawu procesów (kolejność procesów odpowiada ich kolejności w kolejce procesów gotowych):

P1: 100, P2:10, P3:10, P4:10