Ćwiczenia 9: Szeregowanie procesów

Zadanie

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 przydziału 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
  • Jaka jest bieżąca wartość macierzy Potrzebne?
  • Czy system jest w stanie bezpiecznym?
  • Jak system zareaguje na żądanie (0, 1, 0,0) zgłoszone przez proces P3?

Rozwiązanie

  • Macierz Potrzebne jest różnicą macierzy Maksymalne i Przydzielone. Zatem aktualna wartość macierzy Potrzebne to:

    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, bo (P1, P4, P5, P2, P3) jest bezpiecznym ciągiem procesów w tym stanie. Możemy się o tym przekonać symulując przydział zasobów potrzebnych poszczególnym procesom:
    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
  • Gdy proces P3 zgłosi żądanie (0,1,0,0), to bankier dokona przydziału próbnego i sprawdzi, czy tak otrzymany stan 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

    Zatem żądanie nie zostanie zrealizowane, choć zasoby potrzebne procesowi P3 są dostępne.

Zadanie

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

Przydzielone Maksymalne Dostępne
A B C A B C A B C
P1 0 0 1 0 0 1 0 5 3
P2 1 0 0 1 7 5
P3 1 3 5 2 6 10
P4 0 6 3 0 6 5
P5 0 0 1 0 6 5
  • Jaka jest bieżąca wartość macierzy Potrzebne?
  • Czy system jest w stanie bezpiecznym?
  • Jak system zareaguje na żądanie (0, 4, 2) zgłoszone przez proces P2?

Rozwiązanie

Analogicznie do poprzedniego zadania.

Zadanie

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

Rozwiązanie

Bez straty ogólności rozwiązania przyjmijmy, że procesy są ponumerowane zgodnie z rosnącymi czasami zapotrzebowania na kolejną fazę procesora, tzn. ti <= tj dla i < j, gdzie ti jest czasem trwania kolejnej fazy dla procesu Pi.

Rozpatrzymy teraz dowolną kolejność wykonania procesów, w której istnieje 1 <= i < n takie, że
Pi+1 wykonuje się przed Pi. Zamiana miejscami tych procesów powoduje zmianę czasów zakończenia jedynie procesu Pi oraz Pi+1. Proces Pi kończy się teraz o ti+1 wcześniej niż poprzednio, a proces Pi+1 o ti później. Zatem suma czasów obrotów wszystkich procesów zmienia się o ti - ti+1 <= 0. Średni czas obrotu jest więc teraz nie gorszy niż poprzednio.

Widać zatem, że możemy zawsze zlikwidować "inwersję" w ciągu procesów nie pogarszając średniego czasu obrotu zadania. Wynika z tego, że przydział procesora w kolejności wzrastających numerów procesów jest nie gorszy niż jakakolwiek inna kolejność. Czyli SJF jest optymalny.

Zadanie

W pewnym systemie jednoprocesorowym na wykonanie czekają następujące procesy:

Proces Czas przybycia 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 PS?

Rozwiązanie

Do chwili 6 wykonują się procesy P1, P2 i P3 i każdy wykorzystuje procesor przez 2 jednostki czasu.
Następnie działają wszystkie procesy aż do zakończenie procesu P3, co nastąpi w chwili 16. Do tego czasu każdy proces wykorzysta procesor przez kolejne 2 jednostki czasu. W chwili 20 skończą się procesy P2 i P5. Pozostałe procesy P1 i P4 potrzebują jeszcze 5 jednostek czasu procesora, skończą się więc w chwili 30. Otrzymujemy zatem:

Proces Czas przybycia Czas zakończenia Czas obrotu
P1 0 30 30
P2 0 20 20
P3 0 16 16
P4 6 30 24
P5 6 20 14

Średni czas obrotu wynosi 104/5 = 20,8

Zadanie

W pewnym systemie jednoprocesorowym na wykonanie czekają cztery procesy. Zapotrzebowanie na CPU każdego z nich wynosi 10. Jaki będzie średni czas obrotu dla tej grupy procesów przy strategiach szeregowania:

  • PS (RR z kwantem = 0)
  • RR z kwantem = 5
  • FCFS (RR z kwantem równym nieskończoność)

Wyciągnij wnioski z tego przykładu.

Rozwiązanie

  • PS: wszystkie procesy kończą się w chwili 40, więc średni czas obrotu wynosi 40.
  • RR z kwantem 5: Ostatni proces skończy się w chwili 40, poprzedni 5 jednostek czasu wcześniej, itd.
    Zatem średni czas obrotu = (40+35+30+25)/4 = 32,5
  • FCFS: Pierwszy proces skończy się w chwili 10, następne będą się kończyć co 10 jednostek czasu. Zatem średni czas obrotu = (10+20+30+40)/4 = 25.

Okazuje się zatem, że dla procesów o podobnym charakterze obliczeniowym, które nie wymagają szybkiego czasu reakcji, najprostsza implementacyjnie strategia FCFS daje także najlepszy czas obrotu! W dodatku narzut na przełączanie kontekstu jest tu najmniejszy.

Zadanie

Studenci rejestrujący się na pewien przedmiot muszą uzyskać zgodę prowadzącego i opłacić czesne. Oba te wymagania można wypełniać niezależnie od siebie w różnych miejscach kampusu. Limit miejsc wynosi 20 osób i przestrzega go zarówno prowadzący, jak i sekcja finansowa. Przypuśćmy, że opisany powyżej system rejestracji spowodował, że 19 studentów zarejestrowało się na przedmiot bez problemu, a o ostatnie miejsce rywalizuje dwóch studentów, z których jeden opłacił już czesne, ale nie uzyskał jeszcze zgody prowadzącego, a drugi uzyskał zgodę prowadzącego, ale nie opłacił czesnego. Który z warunków koniecznych powstawania zakleszczenia usuwa każde z następujących rozwiązań problemu:

  • Zwiększa się limit miejsc do 21 i obydwaj studenci uczestniczą w zajęciach
  • Ostatnie 20-te miejsce przyznaje się jeszcze innemu studentowi
  • Uznaje się, że bardziej istotny jest fakt opłacenia czesnego i miejsce na zajęciach otrzymuje student, który dokonał płatności

Rozwiązanie

W tym zadaniu dwóch feralnych studentów gra rolę procesów ubiegających się o dwa zasoby: miejsce na liście prowadzącego oraz miejsce na liście w sekcji finansowej. Zasoby te są niepodzielne.

  • zwiększenie limitu, to tak naprawdę usunięcie niepodzielności obu zasobów. Z jednego egzemplarza każdego zasobu robią się dwa egzemplarze i zakleszczenie znika
  • znika warunek braku wywłaszczeń - zabieramy procesom przydzielone zasoby
  • tutaj nie ma przetrzymywania i oczekiwania. Student, który dokonał płatności nie oczekuje już na żaden inny zasób

Zadanie

Pewien bankier dysponuje kwotą 100 000 zł. Udziela on kredytu dwóm kredytobiorcom - każdemu po 50 000 zł. Po pewnym czasie obaj kredytobiorcy informują bankiera, że potrzebują jeszcze po 10 000 zł na dokończenie interestów i wtedy dopiero będą mogli oddać dług. Bankier radzi sobie z tym zakleszczeniem pożyczając potrzebną gotówkę z innego źródła i przekazując ją kredytobiorcom (zwiększając oprocentowanie kredytu:-). Który z warunków koniecznych powstawania zakleszczeń został usunięty przez bankiera?