1

Systemy operacyjne

Zarządzanie procesami

Wykład 3

2

Planowanie procesów

 Celem wieloprogramowania jest jak najlepsze

wykorzystanie procesora - powinien on zawsze

wykonywać jakiś proces. W systemie

jednoprocesorowym może być tylko jeden proces

aktywny. Wszystkie pozostałe procesy muszą czekać do

czasu, aż procesor będzie wolny i będzie można

przydzielić go jednemu z nich. Zapewnienie

najwyższej przepustowości procesora (liczba procesów

kończonych w jednostce czasu) wymaga planowania

przydziału procesora dla kolejnych procesów.

 W podziale czasu przełączanie procesora do

procesów powinno następować tak często, aby każdy z

wykonywanych programów mógł współpracować z

użytkownikami w sposób interaktywny.

3

Kolejki planowania (1)

 Wchodzące do systemu procesy trafiają do
kolejki zadań - zbioru wszystkich procesów
systemu – i oczekują na przydział PAO.
 Kolejka procesów gotowych - zbiór wszystkich
procesów, które oczekują w już w PAO i są gotowe.
 Kolejki do urządzeń - zbiór procesów
oczekujących na konkretne urządzenie WE/WY.

4

Kolejki planowania (2)

5

Kolejki planowania (3)

Po przydzieleniu procesowi procesora może

wystąpić jedno z następujących zdarzeń:

 proces może zamówić operację WE/WY, wskutek
czego trafia do kolejki procesów oczekujących na
WE/WY,

 proces może utworzyć nowy proces i oczekiwać
na jego zakończenie,

 w wyniku przerwania proces może zostać
przymusowo usunięty z procesora z powrotem do
kolejki procesów gotowych.

6

Kolejki planowania (4)

Planowanie procesów ilustruje diagram

kolejek na kolejnym slajdzie.

Każdy prostokąt przedstawia kolejkę,
kółka to zasoby obsługujące kolejki,
strzałki wskazują kierunek przepływu procesów w
systemie.

7

Kolejki planowania (5)

8

Planiści (1)

Wyboru gotowego procesu do

wykonania dokonuje proces
systemowy zwany planistą
(scheduler).

Planowanie jest podstawową funkcją

S.O. Prawie wszystkie zasoby
komputera przydzielane są wg
jakiegoś planu.

9

Planiści (2)

 planista krótkoterminowy (planista
przydziału procesora) - wybiera jeden proces,
który ma być wykonywany jako następny i
przydziela mu procesor.

 planista długoterminowy (planista zadań) -
wybiera procesy przechowywane w pamięci
masowej (dysk) i ładuje je do pamięci, do kolejki
zadań (kolejki procesów gotowych);

10

Planiści (3)

 planista krótkoterminowy musi bardzo często

wybierać nowy proces dla procesora

(milisekundy). Ten planista musi być bardzo

szybki (gdyż może podejmować działanie nawet

raz na 10 milisekund).

 planista długoterminowy działa o wiele

rzadziej (sekundy, minuty) i może być wolniejszy;

planista długoterminowy nadzoruje stopień

wieloprogramowości (liczba procesów w pamięci).

11

Planiści (4)

Procesy można podzielić na:

• procesy ograniczone przez WE/WY: większość czasu
spędzają na wykonywaniu operacji WE/WY;
• procesy ograniczone przez dostęp do procesora.

Wniosek:

Planista długoterminowy musi dobrać

mieszankę procesów.  

Planista długoterminowy może być w niektórych

systemach nieobecny lub mocno zredukowany. Np. systemy z
podziałem czasu często nie mają żadnego planisty
długoterminowego i umieszczają każdy nowy proces w pamięci
pod opieką planisty krótkoterminowego.

12

Planista pośredni

W niektórych SO z podziałem czasu może
występować pośredni poziom planowania i planista
pośredni (średnioterminowy).

Dokonuje on wymiany procesu poprzez wysyłanie go
z pamięci operacyjnej na zewnątrz i ponowne
wprowadzenie.

Cel: lepszy dobór procesów w pamięci operacyjnej
lub
zwolnienie miejsca w pamięci, gdy żądania pamięci
przekraczają jej bieżący obszar.

13

Uzupełnienie diagramu kolejek

o planowanie

średnioterminowe

14

Przełączanie kontekstu

 gdy CPU przełącza się do innego procesu to

system musi przechować stan starego procesu i

załadować przechowywany stan nowego procesu;

nazywa się to przełączaniem kontekstu ;

 czas przełączania kontekstu jest obciążeniem dla

systemu, które nie jest związane z żadną użyteczną

pracą ;

 czas ten zależy w dużym stopniu od możliwości

sprzętu.

15

Program koordynujący

Program koordynujący (dispatcher) jest

modułem systemu, który faktycznie

przekazuje sterowanie procesora do procesu

wybranego przez krótkoterminowego

planistę. Do obowiązków programu

koordynacyjnego należy:

• przełączanie kontekstu;
• przełączanie do trybu użytkownika;
• wykonanie skoku do odpowiedniego adresu

w programie użytkowym w celu wznowienia

działania programu.

16

Przydział procesora

Decyzje o przydziale procesora mogą zapadać gdy:
• proces przechodzi ze stanu wykonania do czekania

(np. zamówienie na WE/WY),

• proces zakończył działanie,
• proces przeszedł od stanu wykonania do stanu

gotowości (np. wskutek wystąpienia przerwania),

• proces przeszedł ze stanu czekania do stanu

gotowości (np. po zakończeniu operacji WE/WY).

Jeśli planowanie odbywa się tylko w dwu pierwszych

przypadkach to jest to

niewywłaszczeniowy

schemat planowania. W przeciwnym razie mówimy
o

wywłaszczeniowym

schemacie planowania.

17

Algorytmy planowania -

kryteria

Kryteria wyboru algorytmów planowania:

-

wykorzystanie procesora

(w rzeczywistym systemie 40-90%),

-

przepustowość

(liczba procesów kończonych w jednostce czasu) może wynosić od

jednego procesu na godzinę do 10 procesów na 1 sekundę,

-

czas cyklu przetwarzania

(liczony od nadejścia procesu do systemu do zakończenia

procesu = czekanie na wejście do pamięci+ czekanie w kolejce procesów gotowych

do wykonania+ wykonywanie procesu przez procesor + wykonywanie operacji

WE/WY),

-

czas oczekiwania

(procesu w kolejce procesów gotowych). Algorytm planowania nie

ma wpływu na czas w którym proces działa lub wykonuje operacje wejścia-wyjścia.

Oddziałuje tylko na czas spędzany przez proces w kolejce procesów gotowych do

wykonania. Dlatego rozważa się czas oczekiwania każdego procesu.

-

czas odpowiedzi

(reakcji)- ile czasu upływa od przedłożenia zamówienia do

rozpoczęcia pierwszej odpowiedzi.

?

18

Dąży się do maksymalizacji

wykorzystania procesora i
zwiększenia przepustowości oraz

do minimalizacji czasu cyklu

przetwarzania, oczekiwania i
odpowiedzi

19

Przykładowe algorytmy

planowania przydziału

procesora

20

Algorytm -pierwszy nadszedł - pierwszy

obsłużony FCFS (First-Come, First-Served),
realizacja za pomocą kolejki FIFO.

Algorytm jest niewywłaszczający.

Po objęciu kontroli nad procesorem proces

utrzymuje ją do czasu, aż sam zwolni procesor
wskutek zakończenia swego działania albo
wskutek żądania operacji We-Wy.

Metoda charakteryzuje się długim średnim

czasem oczekiwania.

21

Najpierw najkrótsze zadanie (proces) SJF

(Shortest-Job-First). Algorytm ten wiąże z
każdym procesem długość jego najbliższej
z przyszłych faz procesora.

Ponieważ nie można poznać długości następnej fazy procesora

trzeba ją przybliżyć. Przyjmuje się założenie, że długość
następnej fazy procesora będzie podobna do długości faz
poprzednich.

Algorytm SJF może być wywłaszczający lub

niewywłaszczający.

22

Planowanie priorytetowe - każdy proces otrzymuje

priorytet (np. z przedziału 0-7 czy 0-4095).

Procesor przydziela się temu procesowi, którego

priorytet jest najwyższy.

Problemem jest nieskończone blokowanie

[1]

Rozwiązaniem może być „postarzanie” procesów

czyli podwyższanie priorytetów procesów długo

oczekujących w systemie np. co kilkanaście minut.

Planowanie priorytetowe może być wywłaszczające

lub niewywłaszczające.

[1]

W 1973 r. W MIT, w wycofanym z eksploatacji IBM 7094 wykryto

nisko priorytetowy proces przedłożony do wykonania w 1967 i nie

wykonany.

23

W planowaniu rotacyjnym (round-robin)- ustala

się kwant czasu (rzędu 10-100 milisekund).

Planista przegląda kolejkę procesów gotowych

do wykonania i każdemu procesowi przydziela

odcinek czasu nie dłuższy od 1 kwantu czasu.

Kolejka procesów gotowych do wykonania traktowana

jest jak kolejka cykliczna.

Algorytm jest wywłaszczający

.

Algorytm zaprojektowano specjalnie dla

systemów z podziałem czasu. Średni czas

oczekiwania często bywa dość długi.

24

Różnorodność algorytmów planowania powoduje,

iż potrzebne są metody pomagające wybierać
właściwe algorytmy.

W metodach analitycznych stosuje się analizę

matematyczną do określania zachowania
algorytmu.

Metody symulacyjne pozwalają określić

zachowanie algorytmu dzięki naśladowaniu jego
działania na reprezentatywnych próbkach
procesów oraz gromadzeniu charakteryzujących
go wyników obliczeń statystycznych.

25

Planowanie w systemach

wieloprocesorowych

Systemy heterogeniczne
• Każdy z procesorów ma własną kolejkę procesów

gotowych i własny algorytm planowania.

Systemy homogeniczne
• Używa się wspólnej kolejki procesów gotowych.

Procesy otrzymują dowolny z dostępnych

procesorów.

• Planowanie może być wtedy zorganizowane na

dwa sposoby:

• - każdy procesor sam planuje swoje działanie,
• - jeden procesor spełnia rolę planisty pozostałych

procesorów (wieloprzetwarzanie asymetryczne).