Valid HTML 4.01!

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

Spis treści


Bibliografia


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:

Model systemu

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 {P0, P1, ..., Pn}, takich że P0 czeka na zasób przetrzymywany przez P1, P1 czeka na zasób przetrzymywany przez P2, ..., Pn czeka na zasób przetrzymywany przez P0.

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:

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

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

Metody postępowania z zastojem


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:
  3. Brak wywłaszczania:
  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:

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

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

Algorytm bankiera

Szczegóły algorytmu bankiera

Struktury danych:

Wprowadźmy następującą notację: jeśli X jest macierzą n x m, to Xi 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ówieniai oznacza wektor zamówień dla procesu Pi. Jeśli Zamówieniai[j]=k, to proces Pi potrzebuje k egzemplarzy zasobu typu Zj. Kiedy proces Pi wykonuje zamówienie, wtedy są podejmowane następujące działania:

  1. Jeśli Zamówieniai <= Potrzebnei, to wykonaj krok 2. W przeciwnym razie zgłoś sytuację błędną, ponieważ proces przekroczył deklarowane maksimum.
  2. Jeśli Zamówieniai <= Dostępne, to wykonaj krok 3. W przeciwnym razie proces Pi musi czekać, ponieważ zasoby są niedostępne.
  3. System próbuje przydzielić żądane zasoby procesowi Pi, 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 Pi 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:

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

Rozwiązanie

Ć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:

  Przydzielone Maksymalne Dostępne
  A   B   C A   B   C A   B   C
P0 0   0   1 0   0   1 0   5   2
P1 1   0   0 1   7   5  
P2 1   3   5 2  6  10  
P3 0   6   3 0   6   5  
P4 0   0   1 0   6   5  

Wykrywanie zastoju

Zasoby pojedyncze

Zasoby wielokrotne

Jak stosować algorytm wykrywania blokady:

Wychodzenie z zastoju

Łą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

©Janina Mincer-Daszkiewicz