‹#›/37
PB153
OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ
Plánování CPU
07

‹#›/37

lMultiprogramování zvyšuje využití CPU
lPokud jeden proces čeká na dokončení I/O operace může jiný proces CPU využít
lNejlepšího výsledku dosáhneme při vhodné kombinaci procesů orientovaných na I/O a na využití CPU
MULTIPROGRAMOVÁNÍ
PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ

‹#›/37

lProces obvykle střídá části využívající CPU a části vyžadující I/O.
lPři zahájení I/O je proces zařazen mezi procesy čekající na událost.
lTeprve při ukončení I/O operace se proces opět dostává mezi procesy „připravené“.
STŘÍDÁNÍ VYUŽITÍ CPU A I/O
PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ
wait for I/O
wait for I/O
wait for I/O
load store
add store
read from file
store increment
index
write to file
load store
add store
read from file
CPU burst
I/O burst
CPU burst
CPU burst
I/O burst
I/O burst

‹#›/37

HISTOGRAM DOBY VYUŽITÍ CPU
PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ
160
140
120
100
80
60
40
20
0
8
16
24
32
40
burst duration (miliseconds)

‹#›/37

STAVY PROCESU
PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ
new
terminated
ready
running
waiting
admitted
interrupt
exit
I/O or event completion
I/O or event wait
scheduler dispatch

‹#›/37

lKrátkodobý plánovač – dispečer
●Vybírá proces, kterému bude přidělen CPU
●Vybírá jeden z procesů, které jsou zavedeny operační paměti a které jsou „připravené“
●Plánovací rozhodnutí může vydat v okamžiku, kdy proces:
●1. přechází ze stavu běžící do stavu čekající
●2. přechází ze stavu běžící do stavu připravený
●3. přechází ze stavu čekající do stavu připravený
●4. končí
●Případy 1 a 4 se označují jako nepreemptivní plánování (plánování bez předbíhání)
●Případy 2 a 3 se označují jako preemptivní plánování (plánování s předbíháním)
PLÁNOVÁNÍ CPU
PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ

‹#›/37

lVýstupní modul krátkodobého plánovače nebo plánovač sám, který předává procesor procesu vybranému
krátkodobým plánovačem
lPředání zahrnuje:
●přepnutí kontextu
●přepnutí režimu procesoru na uživatelský režim
●skok na odpovídající místo v uživatelském programu pro opětovné pokračování v běhu procesu
lDispečerské zpoždění (Dispatch latency)
●Doba, kterou potřebuje dispečer pro pozastavení běhu jednoho procesu a start běhu jiného procesu
DISPEČER
PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ

‹#›/37

lVyužití CPU [maximalizace]
●cílem je udržení CPU v kontinuální užitečné činnosti
lPropustnost [maximalizace]
●počet procesů, které dokončí svůj běh za jednotku času
lDoba obrátky [minimalizace]
●doba potřebná pro provedení konkrétního procesu
lDoba čekání [minimalizace]
●doba, po kterou proces čekal ve frontě „připravených“ procesů
lDoba odpovědi [minimalizace]
●doba, která uplyne od okamžiku zadání požadavku do doby první reakce (první odpovědi, nikoli
poskytnutí plného výstupu)
KRITÉRIA PLÁNOVÁNÍ [A OPTIMALIZACE]
PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ

‹#›/37

lAlgoritmus „Kdo dřív přijde, ten dřív mele“ (First Come, First Served), FCFS
lMáme 3 procesy P1 (vyžaduje 24 dávek CPU), P2 (vyžaduje 3 dávky CPU), P3 (vyžaduje 3 dávky CPU)
lProcesy vznikly v pořadí: P1, P2, P3
lGanttovo schématické vyjádření plánu:
l
l
l
l
lDoby čekání: P1 = 0, P2 = 24, P3 = 27
lPrůměrná doba čekání: (0+24+27)/3 = 17
ALGORITMUS FCFS
PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ
P1
P2
P3
24
27
30
0

‹#›/37

ANIMACE ALGORITMU FCFS
PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ

‹#›/37

lVarianta jiná: procesy vznikly v pořadí P2, P3, P1
lGanttovo schématické vyjádření plánu:
l
l
l
lDoby čekání: P2 = 0, P3 = 3, P1 = 6
lPrůměrná doba čekání: (6+0+3)/3 = 3
lTo je mnohem lepší výsledek než v předchozím případě, i když se jedná o stejné procesy a stejný
plánovací algoritmus
lKrátké procesy následující po dlouhém procesu ovlivňuje „konvojový efekt“
ALGORITMUS FCFS (2)
PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ
Textové pole: P1
P1
P3
P2
6
3
Textové pole: 30
30
Textové pole: 0
0

‹#›/37

ANIMACE ALGORITMU FCFS (2)
PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ

‹#›/37

lAlgoritmus Shortest-Job-First
lMusíme znát délku příštího požadavku na dávku CPU pro každý proces
lVybírá se proces s nejkratším požadavkem na CPU
lDvě varianty:
●nepreemptivní, bez předbíhání
●jakmile se CPU předá vybranému procesu, tento nemůže být předběhnut žádným jiným procesem, dokud
přidělenou dávku CPU nedokončí
●preemptivní, s předbíháním
●jakmile se ve frontě připravených procesů objeví proces s délkou dávky CPU kratší než je doba
zbývající k dokončení dávky právě běžícího procesu, je právě běžící proces ve využívání CPU
předběhnut novým procesem
●tato varianta se rovněž nazývá Shortest-Remaining-Time-First (SRTF)
lSJF je optimální algoritmus (pro danou množinu procesů dává minimální průměrnou dobu čekání)
ALGORITMUS SJF
PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ

‹#›/37

lProces Doba příchodu Délka dávky CPU
●P1 0.0 7
●P2 2.0 4
●P3 4.0 1
●P4 5.0 4
lGanttovo schématické vyjádření plánu:
l
l
l
l
lPrůměrná doba čekání: (0+6+3+7)/4 = 4
PŘÍKLAD NEPREEMPTIVNÍHO ALGORITMU SJF
PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ
Textové pole: P1
P1
P3
P2
Textové pole: 7
7
Textové pole: 3
3
Textové pole: 16
16
Textové pole: 0
0
Textové pole: P4
P4
Textové pole: 8
8
12

‹#›/37

ANIMACE: PŘÍKLAD NEPREEMPTIVNÍHO ALGORITMU SJF
PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ

‹#›/37

lProces Doba příchodu Délka dávky CPU
●P1 0.0 7
●P2 2.0 4
●P3 4.0 1
●P4 5.0 4
lGanttovo schématické vyjádření plánu:
l
l
l
lPrůměrná délka čekání: (9+1+0+2)/4 = 3
PŘÍKLAD PREEMPTIVNÍHO ALGORITMU SJF
PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ
P1
P3
P2
4
2
Textové pole: 11
11
Textové pole: 0
0
Textové pole: P4
P4
Textové pole: 5
5
Textové pole: 7
7
Textové pole: P2
P2
Textové pole: P1
P1
16

‹#›/37

ANIMACE: PŘÍKLAD PREEMPTIVNÍHO ALGORITMU SJF
PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ

‹#›/37

lDélku příští dávky CPU procesu neznáme, můžeme ji pouze odhadovat
lTo můžeme udělat na základě historie
●Musíme znát délky předchozích dávek CPU
●Použijeme exponenciální průměrování:
●
●
URČENÍ DÉLKY PŘÍŠTÍ DÁVKY CPU PROCESU
PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ

‹#›/37

lα = 0 (historii nebereme v úvahu)
●τn+1 = τn
lα = 1 (budoucí odhad = skutečná minulá hodnota)
●τn+1 = tn
lKdyž formuli rozvineme, dostaneme
 τn+1=α tn + (1- α)αtn-1+ … + (1- α)i αtn-i + … + (1- α)nt0
lα a (1- α) jsou <= 1,
lKaždý další člen výrazu má na výslednou hodnotu menší vliv než jeho předchůdce
PŘÍKLAD
PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ

‹#›/37

lS každým procesem je spojeno prioritní číslo
●prioritní číslo – preference procesu pro výběr příště běžícího procesu
●CPU se přiděluje procesu s největší prioritou
●nejvyšší prioritě obvykle odpovídá nejnižší prioritní číslo J
lOpět dvě varianty
●nepreemptivní, bez předbíhání
●jakmile proces získá přístup k CPU nemůže být předběhnut jiným procesem dokud dávku neukončí
●preemptivní, s předbíháním
●jakmile se ve frontě připravených procesů objeví proces s vyšší prioritou než je priorita běžícího
procesu, je běžící proces předběhnut
lSJF je prioritní plánování, prioritou je předpokládaná délka příští CPU dávky
lstárnutí
●procesy s nižší prioritou se nemusí nikdy provést
●řešení: zrání – priorita se s postupem času zvyšuje
PRIORITNÍ PLÁNOVÁNÍ
PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ

‹#›/37

lKaždý proces dostává CPU na malou jednotku času – časové kvantum
●Desítky až stovky ms
lPo uplynutí této doby je běžící proces předběhnut nejstarším procesem ve frontě připravených
procesů a zařazuje se na konec této fronty
lJe-li ve frontě připravených procesů n procesů a časové kvantum je q, pak každý proces získává 1/n
doby CPU, najednou nejvýše q časových jednotek
lŽádný proces nečeká na přidělení CPU déle než (n-1)q časových jednotek
lVýkonnostní hodnocení
●q velké → ekvivalent FIFO
●q malé  → velká režie; v praxi musí být q musí být dostatečně velké s ohledem na režii přepínání
kontextu
ROUND ROBIN (RR)
PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ

‹#›/37

lProces Délka dávky CPU
●P1 53
●P2 17
●P3 68
●P4 24
lGanttovo schématické vyjádření plánu:
l
l
lTypicky se dosahuje delší průměrné doby obrátky než při plánování SJF, avšak doba odpovědi je
výrazně nižší
PŘÍKLAD RR S ČASOVÝM KVANTEM = 20
PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ
P1
P2
P3
P4
P1
P3
P4
P1
P3
P3
0
20
37
57
77
97
117
121
134
154
162

‹#›/37

ANIMACE ROUND ROBIN
PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ

‹#›/37

ČASOVÉ KVANTUM A DOBA PŘEPNUTÍ KONTEXTU
PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ
lPříklad: doba přepnutí kontextu = 0,01
lZtráty související s režií OS při q = 12, 6 a 1 jsou 0,08; 0,16 a 1 %
0
0
0
10
10
6
6
7
8
9
10
5
4
3
2
1
process time = 10
quantum
context switches
12
0
6
1
1
9

‹#›/37

lDoba obrátky se mění se změnou délky časového kvanta
DOBA OBRÁTKY
PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ
time quantum
1
2
3
4
5
6
7
9.0
9.5
10.0
10.5
11.0
11.5
12.0
12.5
process
time
P1
P2
P3
P4
6
3
1
7

‹#›/37

lFronta „připravených“ procesů nemusí být jediná
●procesy můžeme dělit na interaktivní, dávkové, apod.
●pro každou frontu můžeme použít jiný plánovací algoritmus
FRONTA PROCESŮ
PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ
system processes
interactive processes
interactive editing processes
batch processes
student processes
highest priority
lowest priority

‹#›/37

lPlánovací algoritmus je součástí jádra OS
lSkládá se ze 2 funkcí
●schedule() – plánování procesů
●do_timer() – aktualizuje informace o procesech (spotřebovaný čas v uživatelském režimu, v režimu
jádra, priority apod.)
lČasové kvantum je 1/100 sekundy
lPlánovací algoritmus byl předmětem vývoje
PŘÍKLAD: LINUX
PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ

‹#›/37

lPlánovací algoritmus
●4 kategorie procesů z hlediska plánování
●SCHED_FIFO
●SCHED_RR
●SCHED_OTHER
●SCHED_BATCH
●první dva typy jsou procesy se zvláštními nároky na plánování (soft real time), mají přednost před
ostatními procesy a může je vytvářet pouze root
●procesy SCHED_FIFO jsou plánovány metodou FIFO
●Běží dokud není předběhnut, blokován I/O nebo se vzdá procesoru
●procesy SCHED_RR jsou plánovány metodou RR
●Upravené SCHED_FIFO s časovým kvantem podle sched_rr_get_interval()
●procesy SCHED_FIFO a SCHED_RR mají přirazenu prioritu (1-99), při plánování jsou vybírány procesy
s vyšší prioritou, plánovací algoritmu je preemptivní
PŘÍKLAD: LINUX (2)
PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ

‹#›/37

lPlánovací algoritmus – pokračování
●do SCHED_OTHER patří všechny klasické timesharingové procesy
●v rámci SCHED_OTHER jsou procesy plánovány na základě dynamických priorit
●tzv. hodnota nice
●priorita je 0
●zvyšována při stárnutí procesu
●neadministrátorský proces může jen zhoršit prioritu
●resp. od jádra 2.6.12 limit RLIMIT_RTPRIO
●procesy se stejnou prioritou jsou plánovaný pomocí RR
PŘÍKLAD: LINUX (3)
PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ

‹#›/37

lPlánovací algoritmus
●Do jádra 2.4 algoritmus procházející globální
(pro všechny procesory) frontu a hledající vhodný proces (složitost O(n) kde n počet čekajících
procesů)
●Od jádra 2.6 (resp 2.5) nový, tzv. O(1) algoritmus, fronty procesů per-CPU
●Od 2.6.23 nahrazen algoritmem CFS (completely fair scheduler), který pro seznamy procesů používá
červeno-černý strom. Výběr procesu pro běh na procesoru v konstantním čase, jeho znovuvložení
O(log n).
PŘÍKLAD: LINUX (4)
PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ

‹#›/37

PŘÍKLAD: LINUX (5)
PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ
System Calls Related to Scheduling
System Call
Description
nice( )
Change the priority of a conventional process.
getpriority( )
Get the maximum priority of a group of conventional processes.
setpriority( )
Set the priority of a group of conventional processes.
sched_getscheduler( )
Get the scheduling policy of a process.
sched_setscheduler( )
Set the scheduling policy and priority of a process.
sched_getparam( )
Get the scheduling priority of a process.
sched_setparam( )
Set the priority of a process.
sched_yield( )
Relinquish the processor voluntarily without blocking.
sched_get_ priority_min( )
Get the minimum priority value for a policy.
sched_get_ priority_max( )
Get the maximum priority value for a policy.
sched_rr_get_interval( )
Get the time quantum value for the Round Robin policy.

‹#›/37

lZ pohledu Win32:
●procesy při vytvoření přiděleny do jedné z následujících tříd
●Idle
●Below Normal
●Normal
●Above Normal
●High
●Realtime
●Vlákna dále mají relativní prioritu v rámci třídy, do které patří
●Idle
●Lowest
●Below_Normal
●Normal
●Above_Normal
●Highest
●Time_Critical
PŘÍKLAD: WIN32 (1)
PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ

‹#›/37

lPřehled priorit ve Win32
PŘÍKLAD: WIN32 (3)
PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ

real-time
high
above normal
normal
below normal
idle priority
 time-critical
31
15
15
15
15
 15
 highest
26
15
12
10
8
 6
 above normal
25
14
11
9
7
 5
 normal
24
13
10
8
6
 4
 below normal
23
12
9
7
5
 3
 lowest
22
11
8
6
4
 2
 idle
 16
 1
 1
 1
 1
 1

‹#›/37

lPlánovací algoritmu ve Windows 2000
●plánuje vlákna, ne procesy
●vlákna mají priority 0 až 31
l
PŘÍKLAD: WIN32/W2K (2)
PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ
31
16
15
1
0
i
16 „real-time“ levels
15 variable levels
Used by zero page thread
Used by idle thread(s)

‹#›/37

lGet/SetPriorityClass
lGet/SetThreadPriority – relativní vůči základní prioritě procesu
lGet/SetProcessAffinityMask
lSetThreadAffinityMask – musí být podmožinou masky procesu
lSetThreadIdealProcessor – preferovaný procesor
lGet/SetProcessPriorityBoost
lSuspend/ResumeThread
PŘÍKLAD: WIN32 (4)
PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ

‹#›/37

lPlánovací algoritmus je řízen především prioritami
●32 front (FIFO seznamů) vláken, která jsou „připravena“
●pro každou úroveň priority jedna fronta
●fronty jsou společné pro všechny procesory
●když je vlákno „připraveno“
●buď běží okamžitě
●nebo je umístěno na konec fronty „připravených“ procesů ve své prioritě
●na jednoprocesorovém stroji vždy běží vlákno s nejvyšší prioritou
lV rámci jedné prioritní skupiny se plánuje algoritmem round-robin pomocí časových kvant
l
PŘÍKLAD: WIN32 (5)
PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ

‹#›/37
Výukovou pomůcku zpracovalo
Servisní středisko pro e-learning na MU
http://is.muni.cz/stech/
PB 153 OPERAČNÍ SYSTÉMY A JEJICH ROZHRANÍ