Procesy - zagadnienia planowania

1 Planowanie

Planowanie – przydział procesora gwarantujący jego optymalne wykorzystanie (np. gdy proces czeka na urządzenie we-wy; sterowanie przechodzi do następnego.

• procesy oczekują na przydział procesora w kolejkach (kolejka: lista bloków kontrolnych procesów)

• kolejka zadań: procesy nowoutworzone i czekające na pamięć

• kolejka procesów gotowych: czekających na przydział procesora

• kolejki urządzeń: procesy oczekujące na przydział urządzenia

• za szeregowanie (wybór z kolejek) procesów odpowiada planista (scheduler – proces systemowy)

• planista długoterminowy: wybiera procesy z kolejki zadań (zredukowany w niektórych systemach); działa co sek/min.

• planista krótkoterminowy: wybiera z kolejki pr. gotowych; działa co ms.

• czasem planista odpowiada za wymianę (swapping) czyli czasowe usuwanie zadania w całości z pamięci głównej do pomocniczej

• Decyzję podejmuje się gdy proces:

1. przechodzi ze stanu wykonywany do stanu oczekujący

2. przechodzi ze stanu wykonywany do stanu gotowy

3. przechodzi ze stanu oczekujący do stanu gotowy

4. kończy się

• Sterowanie do procesu wybranego przez planistę przekazuje dyspozytor (dispatcher):

• przechowuje stan (kontekst) bieżącego procesu.

• przełącza kontekst (rejestry, itd...)

• przełącza system w tryb użytkownika

• wykonuje skok do adresu z bloku kontrolnego

• opóźnienie wnoszone przez dyspozytora: 1-100ms (zależne od wsparcia sprzetowego)

Życie procesu: dwie fazy (cykliczne) : 1. procesora, 2. we-wy (oczekiwania na urządzenie)

• p

  

  
  rocesy zorientowane na we-wy (1): spędzają więcej czasu wykonując operacje we-wy niż obliczenia; wiele krótkich odcinków czasu zapotrzebowania na CPU

• zorientowane na procesor (2): spędzają więcej czasu wykonując obliczenia; kilka bardzo długich odcinków czasu zapotrzebowania na CPU

Kryteria planowania (różne możliwości - maxymalizacja, minimalizacja):

• max wykorzystania procesora (najlepiej 40-90%)

• max przepustowości – liczba procesów kończonych w jedn. czasu)

• min czasu przetwarzania procesu (od utworzenia do zakończenia)

• min czasu oczekiwania w kolejkach (to kryterium będziemy stosować)

• min czasu odpowiedzi procesu (w syst. interaktywnych)

 będziemy minimalizować średni czas oczekiwania w kolejkach

2 Algorytmy planowania

FCFS (First Come First Served)

• przydział czasu w kolejności zgłaszania się procesów

• najprostsza implementacja (kolejka FIFO)

• brak wywłaszczania

• kłopotliwy w systemach z podziałem czasu

• przykład:

• Procesy i ich zapotrzebowanie na CPU: P1 (24), P2 (3), P3 (3)

• Jeżeli procesy przybyły w kolejności P1, P2, P3: · czas oczekiwania: P1 = 0, P2 = 24, P3 = 27 · średni czas oczekiwania: (0 + 24 + 27)/3 = 17.

• Jeżeli procesy przybyły w kolejnooeci P2, P3, P1: · czas oczekiwania: P1 = 6, P2 = 0, P3 = 3 · średni czas oczekiwania: (6 + 0 + 3)/3 = 3

• efekt: krótkie procesy są wstrzymywane przez długie

• zalety: sprawiedliwy, niski narzut systemowy

• wady: długi oeredni czas oczekiwania i wariancja czasu oczekiwania, nieakceptowalny w systemach z podziałem czasu

SJF (Shortest Job First)

• Algorytm wiąże z każdym procesem długość jego najbliższej fazy procesora. Procesor jest przydzielany najkrótszemu.

• Przy równych fazach procesora mamy FCFS

• SJF jest optymalny (dowód: umieszczenie krótkiego przed długim bardziej zmniejsza czas oczekiwania krótkiego niż zwiększa długiego)

• SJF może być:

• niewywłaszczający

• wywłaszczający (gdy dł. fazy nowego jest krótsza niż to, co zostało aktualnie wykonywanemu procesowi)

• Problem: jak oszacować dł przyszłej fazy procesora?

• planista długoterminowy może wymagać jego zadeklarowani od procesów (zadania maj ą predefiniowany czas fazy); krótkoterminowy nie może (wielkie opóźnienia)

• częste rozwiązania: dł. następnej fazy (t_n+1)= średnia wykładnicza długości n faz poprzednich (założenie: dł fazy jest zależna od długości poprzednich faz):

t_n+1 = _i=0ⁿ a(1-a)ⁱ t_n-i gdzie a<1.

• powyższe rozwiązania jest adaptacyjne (dostosowuje się gdy zapotrzebowanie procesu ulega zmianie)

Planowanie Priorytetowe:

• szczególnym przypadkiem jest SJF ( w którym priorytet = 1/(dł nast. fazy procesora) ).

• zwykle priorytet określa jednak liczba całkowita np. z przedziału [0,7] czy [0,4096] – niższa wartość = wyższy priorytet.

• problem: proces o niskim priorytecie może się nigdy nie wykonać (w jednym z przemysłowych systemów IBM proces czekał na wykonanie od 1967 do 1973...); rozwiązanie: postarzanie procesów (zmniejszenie priorytetu o 1 np. co 10 min.)

• może być wywłaszczające (ale niekoniecznie)

• określenie priorytetu:

- zewnętrznie (przez funkcję systemową)

- wewn. przez deklarację samego procesu (na podstawie np. wymagań: pamięć, procesor etc...)

Planowanie Rotacyjne (Round Robin - RR, pol. karuzelowe)

• ustala się kwant czasu (~10-100 ms)

• kolejka procesów jest traktowana jak cykliczna FIFO

• algorytm przegląda kolejkę i kolejno przydziela każdemu kwant czasu (jeśli proces się w nim nie zakończy – wraca do kolejki, a długość jego fazy procesora zmniejsza się o kwant czasu).

• algorytm jest wywłaszczający

• gdy jest N procesów a kwant czasu wynosi Q, max. czas oczekiwania może wynieść (N-1)Q

• efekty:

- gdy Q rośnie nieograniczenie; planowanie rotacyjne  FCFS

- gdy Q zmierza do 0 zachodzi dzielenie procesora – każdy proces dysponuje procesorem o prędkości 1/N rzeczywistego.

• - a propos: podobny efekt dają tzw. procesory peryferyjne – z np. 10 zestawami rejestrów; na każde zadanie. Procesor peryf. wykonuje po 1 rozkazie każdego zadania. Zysk: procesor jest szybszy od pamięci – całość nie jest 10x wolniejsza...)

• Aspekty wydajnościowe:

- wskazany jest długi kwant czasu w porównaniu z przełączaniem kontekstu (wpp zła wydajność)

- reguła doświadczalna: kwant czasu powinien być dłuższy niż 80% faz procesora dla optymalnej wydajności.

3 Struktura kolejek w systemie operacyjnym (planowanie wielopoziomowe).

• Kolejka procesów gotowych jest podzielona na odrębne kolejki; przykładowo (najprościej):

- procesów piewszoplanowych (systemowe, interakcyjne)

- procesów drugoplanowych (wsadowe)

• Każda kolejka ma własny algorytm szeregowania

• Przykład:

- procesy piewszoplanowe - strategia karuzelowa (RR)

- procesy drugoplanowe - FIFO

• Szeregowanie pomiędzy kolejkami:

- Ustalone, np. obsługuj najpierw wszystkie procesy pierwszoplanowe, potem drugoplanowe; możliwość zagłodzenia

- Kwant czasu: każda kolejka otrzymuje ustaloną część czasu CPU do podziału pomiędzy swoje procesy, np. 80% dla pierwszoplanowych z RR, 20% dla drugoplanowych z FCFS

- Procesy mogą się przemieszczać pomiędzy kolejkami

• Parametry planisty systemowego:

- liczba kolejek

- algorytm szeregowania dla każdej kolejki

- metoda awansu/degradacji procesów (do kolejki o odpowiednio niższym/wyższym priorytecie)

- metoda wybierania kolejki dla nowego procesu

• Przykład: proces zużywający dużo czasu procesora (np. cały kwant w RR) przechodzi do kolejki o niższym priorytecie, ale dłuższym kwancie. Na najniższym poziomie: FCFS. Procesy interakcyjne i zorientowane na we-wy będą pozostawać w kolejkach o wyższym priorytecie, a procesy zorientowane obliczeniowo - w kolejkach o niższym priorytecie.

• Wnioski z symulacji, teorii, praktyki:

- rozkład faz jest na ogół w rzeczywistych systemach wykładniczy

- jeśli średnia długość kolejki = n, średni czas obsługi = T, tempo przybywania nowych
procesów = , to n = T (tw. Little’a; stosuje się ogólnie do stabilnych systemów kolejkowych)

• Systemy wieloprocesorowe:

- dzielenie (osobna kolejka i algorytm dla każdego procesora) lub...

- wspólna kolejka:

- każdy procesor sam wybiera proces do wykonania

- jeden procesor przydziela procesy do procesorów

(tzw. wieloprzetwarzanie asymetryczne)