plik

Systemy operacyjne

– notatki do wykładu

2. Procesy i wątki.

2.1 Proces.

Proces -

program (kod binarny) w czasie wykonania; wykonanie przebiega sekwencyjnie (wyjątek:

procesy wielowątkowe – patrz niżej).



Procesy wykonują się współbieżnie (ale niekoniecznie równolegle – podział czasu)



Stany procesu:

nowy: proces został utworzony

wykonywany: są wykonywane instrukcje procesu

oczekujący: proces czeka na wystąpienie zdarzenia

- gotowy: proces czeka na przydzielenie procesora

zakończony: proces zakończył wykonanie

Reprezentacja procesu w systemie (zawartość bloku kontrolnego procesu):
- stan procesu
- identyfikator (unikalny numer

– w UNIX’ie – PID)

licznik rozkazów

- rejestry procesora
-

wskaźnik do kolejki procesów

informacje o pamięci zajętej przez proces

wykaz otwartych (używanych plików)

Tworzenie procesu:
-

za pomocą funkcji systemowej (np. fork() w UNIX)

proces utworzony przez inny proces (macierzysty, ew. rodzic) nazywamy potomnym.

potomek uzyskuje nową pulę zasobów lub korzysta z zasobów rodzica (mniejsze przeciążenie
systemu).

Zakończenie procesu:
-

po ostatniej instrukcji.

specjalna funkcją (np. exit() w UNIX)

na żądania rodzica ( abort() )

niekiedy: zakończenie kaskadowe: po zakończeniu rodzica kończone są procesy potomne.

2.2 Wątek

Wątek sterowania (tzw. lekki proces): sekwencja instrukcji; tradycyjnie proces = jeden wątek
sterowania, jednak czasami (w niektórych systemach) w przestrzeni adresowej procesu dopuszcza
więcej wykonywanych współbieżnie wątków sterowania.
-

wątek ma te same podst. cechy co proces (stany, możliwość tworzenia wątków potomnych,
korzystania z urządzeń zewn. itd...)

między wątkami tego samego procesu nie ma ochrony pamięci.

analogia: maszyna-procesy == proces-

wątki

Systemy operacyjne

– notatki do wykładu

elementy wątku i procesu:

Wątek

Proces

licznik rozkazów

przestrzeń adresowa

stos

otwarte pliki, semafory

rejestry procesora

zmienne globalne

lista wątków potomnych

lista proc. potomnych

Trady

cyjny proces (ciężki) jest równoważny zadaniu z jednym wątkiem

Jeżeli zadanie składa się z wielu wątków, to w czasie gdy jeden wątek jest zablokowany, może
się wykonywać inny wątek tego zadania; współpraca wielu wątków w jednym zadaniu pozwala
zwiększyć przepustowość i poprawić wydajność

Wątki umożliwiają połączenie równoległości z sekwencyjnym wykonaniem:

(1) model dyspozytor-pracownik

(2) model zespołu

(3) model potoku

Wątki statyczne/dynamiczne:
-

struktura wątków procesu jest ustalona (w kodzie źr. procesu) lub też proces może dowolnie

tworzyć/usuwać swoje wątki

Implementacja wątków w systemie operacyjnym:



Pakiet wątków : zbiór elementarnych działań na wątkach dostępnych w systemie (np. procedur
bibliotecznych.



Implementacja wątków w przestrzeni użytkownika:

jądro nie wie o wątkach, widzi tylko jednowątkowe procesy

zaleta1: można używać wątków w systemie, który ich nie implementuje (np. pierwotnie UNIX)

możliwe szybkie przełączanie wątków – tylko przeładowania wsk. stosu i instrukcji oraz
rejestrów (najszybsze działania w syst. komputerowym).

zaleta2:każdy proces może używać własnego alg. planowania dla swoich wątków.

problem1: przy blokowanych odwołaniach wątków do systemu – proces nie może oddać
sterowania systemowi, musi czekać na swoje wątki. Używa się kodu sprawdzającego (and.
jacket

) czy odwołania wątków będą blokować.  a wątków używa się głownie w zadaniach z

blokującymi odwołaniami, gdzie mają poprawić wydajność...

problem2: nie ma wywłaszczania, wątki muszą same oddawać sterowanie procedurze
wykonawczej procesu.



Implementacja wątków w jądrze:

system wykonawczy jest częścią jądra

Systemy operacyjne

– notatki do wykładu

jądro zakłada tablicę wątków dla każdego procesu

wszystkie funkcje mogące blokować mają postać odwołań do systemu

gdy wątek czka, jądro wybiera następny – wydajność!

wada: koszt odwołań do systemu (czas!)



Ogólne problemy (najtrudniejsze do implementacji) z wątkami:

obsługa przerwań (sygnałów)

niewznawialne procedury systemowe

3. Procesy - zagadnienia planowania

3.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)
-

procesy zorientowane na we-

wy (1): spędzają więcej czasu wykonując operacje we-wy niż

obl

iczenia; wiele krótkich odcinków czasu zapotrzebowania na CPU

ł. fazy procesora

ęstość fazy procesora

Systemy operacyjne

– notatki do wykładu

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

3.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 na

jkró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):

n+1



i=0

a(1-a)

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.)

Systemy operacyjne

– notatki do wykładu



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.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



Prz

ykł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.

Systemy operacyjne

– notatki do wykładu

ŁOSZENIA

SYSTEMOWE (RR)

INTERAKCYJNE (RR)

...

WSADOWE (FCFS)

CPU

PRIORYTETOWE

WYW

ŁASZCZAJĄCE

(+ ew. postarzanie)



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 =



(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)