Systemy operacyjne

– notatki do wykładu

6

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

7

-

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

8

-

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

D

ł. fazy procesora

Cz

ęstość fazy procesora

1

2

Systemy operacyjne

– notatki do wykładu

9

-

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

t

n+1

=



i=0

n

a(1-a)

i

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

Systemy operacyjne

– notatki do wykładu

10



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

11

ZG

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



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)