Téma 4. Plánování procesů a synchronizace

Operační systémy a sítě

Petr Štěpán, K13133 KN-E-129 [email protected]

Téma 4. Plánování procesů a synchronizace

A4B33OSS

Plánovače v OS

• Krátkodobý plánovač (operační plánovač, dispečer):

– Základní správa procesoru/ů – Vybírá proces, který poběží na uvolněném procesoru přiděluje procesu procesor (CPU) – vyvoláván velmi často, musí být extrémně rychlý

• Střednědobý plánovač (taktický plánovač)

– Úzce spolupracuje se správou hlavní paměti – Taktika využívání omezené kapacity FAP při multitaskingu – Vybírá, který proces je možno zařadit mezi odložené procesy  • uvolní tím prostor zabíraný procesem ve FAP

– Vybírá, kterému odloženému procesu lze znovu přidělit prostor ve FAP

• Dlouhodobý plánovač (strategický plánovač, job scheduler)

– Vybírá, který požadavek na výpočet lze zařadit mezi procesy, a definuje tak stupeň multiprogramování – Je volán zřídka (jednotky až desítky sekund), nemusí být rychlý • V interaktivních systémech (typu Windows) se prakticky nepoužívá a degeneruje na přímé předání práce krátkodobému plánovači

A4B33OSS

Plánování procesů a synchronizace

2

Středně dobý plánovač - swapping

• Běžící proces musí mít alespoň pro aktuální části svého LAP přidělen prostor ve FAP – jinak by nemohl pracovat

• I když se používá princip virtuální paměti

– příliš mnoho procesů ve FAP (alespoň částečně) snižuje výkonnost systému • jednotlivé procesy obdrží malý prostor ve FAP a aktuální úsek LAP ve FAP se jim vyměňuje příliš často (problém „výprasku“ )

• OS musí paměťový prostor některých procesů odložit – takové procesy nemohou běžet – odložení – swap-out, okopírování na disk – obnova – swap-in, zavedení do FAP

• Přibývají tak další dva stavy procesů

– odložený čekající – čeká na nějakou událost a, i kdyby byl v paměti, stejně by nebyl schopen běhu – odložený připravený – nechybí mu nic kromě místa v paměti

A4B33OSS


3

Sedmistavový diagram procesů Nový

Start

Dlouhodobé plánování Start

Krátkodobé plánování (dispečer)

Odlož (není místo v paměti)

Odložený připravený

Obnov

Běž Připravený

Událost nastala

Událost nastala

Ukončený

Preempce

Odlož

Odložený čekající

Běžící

Konec

Obnov Čekající

n ej k Če

st o l dá a u

Odlož

Uvažujeme odložené (suspendované) procesy

Střednědobé plánování

A4B33OSS


4

Plánovač CPU (dispečer) a typy plánování • Dispečer pracuje s procesy, které jsou v hlavní paměti a jsou schopné běhu, tj. připravené (ready) • Existují 2 typy plánování

– nepreemptivní plánování (plánování bez předbíhání, někdy také kooperativní plánování), kdy procesu schopnému dalšího běhu procesor není „násilně“ odnímán

• Používá se zpravidla jen v „uzavřených systémech“, kde jsou předem známy všechny procesy a jejich vlastnosti. Navíc musí být naprogramovány tak, aby samy uvolňovaly procesor ve prospěch procesů ostatních

– preemptivní plánování (plánování s předbíháním), kdy procesu schopnému dalšího běhu může být procesor odňat i „bez jeho souhlasu“ (tedy kdykoliv)

• Plánovač rozhoduje (vstupuje do hry) v okamžiku, kdy některý proces: 1. přechází ze stavu běžící do stavu čekající nebo končí 2. přechází ze stavu čekající do stavu připravený 3. přechází ze stavu běžící do stavu připravený

• První dva případy se vyskytují v obou typech plánování • Poslední je charakteristický pro plánování preemptivní A4B33OSS


5

Kriteria krátkodobého plánování •

Uživatelsky orientovaná

– – – –

čas odezvy

•

doba od vzniku požadavku do reakce na něj

•

doba od vzniku procesu do jeho dokončení

•

požadavek dodržení stanoveného času dokončení

•

Úloha by měla být dokončena za zhruba stejnou dobu bez ohledu na celkovou zátěž systému Je-li systém vytížen, prodloužení odezvy by mělo být rovnoměrně rozděleno mezi procesy

doba obrátky

konečná lhůta (deadline) předvídatelnost

•

•

Systémově orientovaná

– – – –

A4B33OSS

průchodnost

•

počet procesů dokončených za jednotku času

•

relativní čas procesoru věnovaný aplikačním procesům

•

každý proces by měl dostat svůj čas (ne „hladovění“ či „stárnutí“)

•

systémové prostředky (periferie, hlavní paměť) by měly být zatěžovány v čase rovnoměrně

využití procesoru spravedlivost

vyvažování zátěže systémových prostředků


6

Plánovací algoritmy • Ukážeme plánování: – – – – –

FCFS SPN (SJF) SRT cyklické zpětnovazební

(First-Come First-Served) (Shortest Process Next) (Shortest Remaining Time) (Round-Robin) (Feedback)

• Příklad

– používaný v tomto textu pro ilustraci algoritmů Proces

Čas příchodu

A B C D E

0 2 4 6 8

Potřebný čas (délka CPU dávky) 3 6 4 5 2

• Chování se ilustruje tzv. Ganttovými diagramy A4B33OSS


7

– – – –

Plánování FCFS

FCFS = First Come First Served – prostá fronta FIFO Nejjednodušší nepreemptivní plánování Nově příchozí proces se zařadí na konec fronty Průměrné čekání může být velmi dlouhé wTAvg  0  1  5  7  10  4,6

– Příklad:

5

0

1

2

3

4

5

6

7

8

9 10 11 12 13 14 15 16 17 18 19 20

A B C D E

– Průměrné čekání bychom mohli zredukovat: • Např. v čase 9 je procesor volný a máme na výběr procesy C, D a E 0

0 1 7  9 1 TAvg   3,6 5

w

1

2

3

4

5

6

7

8

9 10 11 12 13 14 15 16 17 18 19 20

A B C D E

A4B33OSS


8

Vlastnosti FCFS

• FCFS je primitivní nepreemptivní plánovací postup • Průměrná doba čekání wTAvg silně závisí na pořadí přicházejících dávek • Krátké procesy, které se připravily po dlouhém procesu, vytváří tzv. konvojový efekt – Všechny procesy čekají, až skončí dlouhý proces • Pro krátkodobé plánování se FCFS samostatně fakticky nepoužívá. – Používá se pouze jako složka složitějších plánovacích postupů

A4B33OSS


9

Plánování SPN

• SPN = Shortest Process Next (nejkratší proces jako příští); též nazýváno SJF = Shortest Job First

– Opět nepreemptivní – Vybírá se připravený proces s nejkratší příští dávkou CPU – Krátké procesy předbíhají delší, nebezpečí stárnutí dlouhých procesů – Je-li kritériem kvality plánování průměrná doba čekání, je SPN optimálním algoritmem, což se dá exaktně dokázat

• Příklad: 0

1

2

3

4

5

6

7

8

9 10 11 12 13 14 15 16 17 18 19 20

A B C D E

TAvg 

w

A4B33OSS


0 1 7  9 1  3,6 5

10

Plánování SRT

• SRT = Shortest Remaining Time (nejkratší zbývající čas)

– Preemptivní varianta SPN – CPU dostane proces, který potřebuje nejméně času do svého ukončení – Jestliže existuje proces, kterému zbývá k jeho dokončení čas kratší, než je čas zbývající do skončení procesu běžícího, dojde k preempci • Může existovat procesů se stejným zbývajícím časem, a pak je nutno použít jakési „arbitrážní pravidlo“

• Příklad: 0

1

2

3

4

5

6

7

8

9 10 11 12 13 14 15 16 17 18 19 20

A B C D E

A4B33OSS

w

T Avg =


0 +1+0 +9+0 =2,0 5

11

Motivace plánování CPU • Maximálního využití CPU se dosáhne uplatněním multiprogramování • Jak ? • Běh procesu = cykly alternujících dávek – [: CPU dávka, I/O dávka :] • CPU dávka se může v čase překrývat s I/O dávkami dalších procesů

A4B33OSS


12

Typický histogram délek CPU dávek

Frekvence

100

80

60

40

20

0 0

A4B33OSS

4


8

Délka CPU dávky [ms]

12

13

Odhad délky příští dávky CPU procesu

• Délka příští dávky CPU skutečného procesu je známa jen ve velmi speciálních případech – Délka dávky se odhaduje na základě nedávné historie procesu – Nejčastěji se používá tzv. exponenciální průměrování

• Exponenciální průměrování – – – – –

A4B33OSS

tn … skutečná délka n-té dávky CPU τn+1 … odhad délky příští dávky CPU α, 0 ≤ α ≤1 … parametr vlivu historie τn+1 = αtn + (1 − α)τn Příklad: • α = 0,5 • τn+1 = 0,5tn + 0,5τn = = 0,5(tn + τn) • τ0 se volí jako průměrná délka CPU dávky v systému nebo se odvodí z typu nejčastějších programů


τ0=8, α=0,5

14

Prioritní plánování (1) • Každému procesu je přiřazeno prioritní číslo

– Prioritní číslo – preference procesu při výběru procesu, kterému má být přiřazena CPU – CPU se přiděluje procesu s nejvyšší prioritou – Nejvyšší prioritě obvykle odpovídá (obvykle) nejnižší prioritní číslo • Ve Windows je to obráceně

• Existují se opět dvě varianty: – Nepreemptivní

• Jakmile se vybranému procesu procesor předá, procesor mu nebude odňat, dokud se jeho CPU dávka nedokončí

– Preemptivní

• Jakmile se ve frontě připravených objeví proces s prioritou vyšší, než je priorita právě běžícího procesu, nový proces předběhne právě běžící proces a odejme mu procesor

• SPN i SRT jsou vlastně případy prioritního plánování – Prioritou je predikovaná délka příští CPU dávky – SPN je nepreemptivní prioritní plánování – SRT je preemptivní prioritní plánování

A4B33OSS


15

Prioritní plánování (2) • Problém stárnutí (starvation): – Procesy s nízkou prioritou nikdy nepoběží; nikdy na ně nepřijde řada • Údajně: Když po řadě let vypínali v roce 1973 na M.I.T. svůj IBM 7094 (jeden z největších strojů své doby), našli proces s nízkou prioritou, který čekal od roku 1967. • Řešení problému stárnutí: zrání procesů (aging) – Je nutno dovolit, aby se procesu zvyšovala priorita na základě jeho historie a doby setrvávání ve frontě připravených • Během čekání na procesor se priorita procesu zvyšuje

A4B33OSS


16

Cyklické plánování • Cyklická obsluha (Round-robin) – RR • Z principu preemptivní plánování • Každý proces dostává CPU periodicky na malý časový úsek, tzv. časové kvantum, délky q (~ desítky ms) – V „čistém“ RR se uvažuje shodná priorita všech procesů – Po vyčerpání kvanta je běžícímu procesu odňato CPU ve prospěch nejstaršího procesu ve frontě připravených a dosud běžící proces se zařazuje na konec této fronty – Je-li ve frontě připravených procesů n procesů, pak každý proces získává 1/n-tinu doby CPU – Žádný proces nedostane 2 kvanta za sebou (samozřejmě pokud není jediný připravený) – Žádný proces nečeká na přidělení CPU déle než (n−1)q časových jednotek A4B33OSS


17

Cyklické plánování (2) • Efektivita silně závisí na velikosti kvanta – Veliké kvantum – blíží se chování FCFS

• Procesy dokončí svoji CPU dávku dříve, než jim vyprší kvantum.

– Malé kvantum => časté přepínání kontextu => značná režie

• Typicky

– Dosahuje se průměrné doby obrátky delší oproti plánování SRT – Výrazně lepší je čas odezvy – Průměrná doba obrátky se může zlepšit, pokud většina procesů se době q ukončí – Empirické pravidlo pro stanovení q: cca 80% procesů by nemělo vyčerpat kvantum

Příklad:

0

1

2

3

4

5

6

7

8

9 10 11 12 13 14 15 16 17 18 19 20

A B C D E A4B33OSS


18

Zpětnovazební plánování • Základní problém:

– Neznáme předem časy, které budou procesy potřebovat

• Východisko:

– Penalizace procesů, které běžely dlouho

• Řešení:

– Dojde-li k preempci přečerpáním časového kvanta, procesu se snižuje priorita – Implementace pomocí víceúrovňových front • pro každou prioritu jedna

– Nad každou frontou samostatně běží algoritmus určitého typu plánování • obvykle RR s různými kvanty a FCFS pro frontu s nejnižší prioritou

A4B33OSS


19

Víceúrovňové fronty - Windows Připravení procesu Preempce vyčerpáním kvanta

Fronta priorita 0

Fronta priorita 1

Aktivace

Aktivace

Opuštění fronty připravených

Procesor

Procesor


↓ ↓ ↓ Preempce vyčerpáním kvanta

Fronta priorita n

Aktivace

Procesor


– Proces opouštějící procesor kvůli vyčerpání časového kvanta je přeřazen do fronty s nižší prioritou – Fronty s nižší prioritou mohou mít delší kvanta – Problém stárnutí ve frontě s nejnižší prioritou • Řeší se pomocí zrání (aging) – v jistých časových intervalech (~ 101 s) se zvyšuje procesům priorita, a tak se přemísťují do „vyšších“ front A4B33OSS


20

O(1) plánovač – Linux 2.6-2.6.23 • •

O(1) - rychlost plánovače nezávisí na počtu běžících procesů – je rychlý a deterministický Dvě sady víceúrovňových front – Na začátku první sada obsahuje připravené procesy, druhá je prázdná – Při vyčerpání časového kvanta je proces přeřazen do druhé sady front do nové úrovně – Vzbuzené procesy jsou zařazovány podle toho, zda ještě nevyužily celé svoje časové kvantum do aktivní sady front, nebo do druhé sady front – Pokud je první sada prázdná, dojde k prohození první a druhé sady front procesů

•

Heuristika pro odhad interaktivních procesů a jejich udržování na nejvyšších prioritách s odpovídajícími časovými kvanty

A4B33OSS


21

Zcela férový plánovač • •

• • •

Linux od verze 2.6.23 (Completely Fair Scheduler) Nepoužívá fronty, ale jednu strukturu, která udržuje všechny procesy uspořádané podle délky již spotřebovaného času – čím méně proces spotřeboval strojového času, tím větší má nárok na přidělení procesoru Pro rychlou implementaci se používá vyvážený binární červeno-černý strom, zaručující složitost úměrnou log(n) počtu procesů Nepotřebuje složité heuristiky pro detekci interaktivních procesů Jediný parametr je časové kvantum: – pro uživatelské PC se volí menší pro větší – pro serverové počítače větší kvantu omezuje režii s přepínáním procesů a tím zvyšuje propustnost serveru

•

Žádný proces nemůže zestárnout, všechny procesy mají stejné podmínky

A4B33OSS


22

Plánování v multiprocesorech • Přiřazování procesů (vláken) procesorům: – Architektura „master/slave“ • Klíčové funkce jádra běží vždy na jednom konkrétním procesoru • Master odpovídá za plánování • Slave žádá o služby mastera • Nevýhoda: dedikace – Přetížený master se stává úzkým místem systému – Symetrický multiprocesing (SMP) • Všechny procesory jsou si navzájem rovny • Funkce jádra mohou běžet na kterémkoliv procesoru – SMP vyžaduje podporu vláken v jádře • Proces musí být dělen na vlákna, aby SMP byl účinný – Aplikace je sada vláken pracujících paralelně do společného adresního prostoru – Vlákno běží nezávisle na ostatních vláknech svého procesu – Vlákna běžící na různých procesorech dramaticky zvyšují účinnost systému A4B33OSS


23

Symetrický multiprocesing (SMP) • Dvě řešení: – Jedna společná fronta pro všechny procesory – Každý procesor svojí frontu a migrace procesů mezi procesory • Jedna společná (globální) fronta pro všechna vlákna – Fronta „napájí“ společnou sadu procesorů • Fronta může být víceúrovňová dle priorit

– Každý procesor si sám vyhledává příští vlákno

• Přesněji: instance plánovače běžící na procesoru si je sama vyhledává ...

– Problémy

– Jedna centrální fronta připravených sledů vyžaduje používání vzájemného vylučování v jádře

• Kritické místo v okamžiku, kdy si hledá práci více procesorů • Předběhnutá (přerušená) vlákna nebudou nutně pokračovat na stejném procesoru – nelze proto plně využívat cache paměti procesorů

• Každý procesor svoji frontu – Heuristická pravidla, kdy frontu změnit • SMP používáno ve

– Windows, Linux, Mac OS X, Solaris, BSD4.4

A4B33OSS


24

Poznámky k plánování v multiprocesorech • Používají se různá (heuristická) pravidla (i při globální frontě): – Afinita vlákna k CPU – použij procesor, kde vlákno již běželo (možná, že v cache CPU budou ještě údaje z minulého běhu) – Použij nejméně využívaný procesor • Mnohdy značně složité – při malém počtu procesorů (≤ 4) může přílišná snaha o optimalizaci plánování vést až k poklesu výkonu systému • Tedy aspoň v tom smyslu, že výkon systému neporoste lineárně s počtem procesorů – při velkém počtu procesorů dojde naopak k „nasycení“, neboť plánovač se musí věnovat rozhodování velmi často (končí CPU dávky na mnoha procesorech) • Režie tak neúměrně roste A4B33OSS


25

Systémy reálného času (RT) • Obvykle malé systémy se specializovaným použitím – Často vestavěné (embedded)

• Správná funkce systému závisí nejen na logickém (či numerickém) výsledku ale i na čase, kdy bude výsledek získán – Správně určený výsledek dodaný pozdě je k ničemu

• Úlohy a procesy reagují na události pocházející zvenčí systému a navenek dodávají své výsledky – Nastávají v „reálném čase“ a potřebná reakce musí být včasná

• Příklady – – – – – –

A4B33OSS

Řízení laboratorních či průmyslových systémů Robotika Řízení letového provozu Telekomunikační aplikace (digitální ústředny) Vojenské systémy velení a řízení ... Plánování procesů a synchronizace

26

Charakteristiky OS RT • Determinismus – Operace jsou prováděny ve fixovaných, předem určených časech nebo časových intervalech – Reakce na přerušení musí proběhnout tak, aby systém byl schopen obsluhy všech požadavků v požadovaném čase (včetně vnořených přerušení) • Uživatelské řízení – Uživatel (návrhář systému) specifikuje: • Priority • Práva procesů • Co musí vždy zůstat v paměti • Spolehlivost – Degradace chování může mít katastrofální důsledky • Zabezpečení – Schopnost systému zachovat v případě chyby aspoň částečnou funkcionalitu a udržet maximální množství dat A4B33OSS


27

Požadavky na OS RT • Extrémně rychlé přepínání mezi procesy či vlákny • OS musí být malý • Multiprogramování s meziprocesními komunikačními nástroji – semafory, signály, události  • Speciální souborové systémy s velkou rychlostí – RAM disky, souvislé soubory • Plánování založené na prioritách – Pozor: preempce je ale časově náročná • Minimalizace časových úseků, kdy je vypnut přerušovací systém • Zvláštní hardwarové vybavení – hlídací časovače (watch-dog timers) a alarmy

A4B33OSS


28

Plánování CPU v RT systémech • Tabulkou řízené statické plánování

– Určuje pevně, kdy bude který proces spuštěn tak, aby včas skončil – Nejčastější případ v uzavřených systémech s předem známými procesy a jejich vlastnostmi

• Preemptivní plánování se statickými prioritami

– Používá klasický prioritní plánovač s fixními prioritami • Může být problematické kvůli velké režii spojené s preempcí

• Dynamické plánování

– Za běhu určuje proveditelnost (splnitelnost požadavků) – V tzv. přísných RT systémech (Hard real-time systems) téměř nepoužitelné vlivem velké režie • Hard real-time systems musí přísně zaručovat dokončení časově kritických procesů do předepsaného termínu

A4B33OSS


29

Periodické plánování dle konečného termínu • Procesům jde zejména o včasné dokončení v rámci zadané periody běžících procesů – Např. v daných intervalech je třeba vzorkovat napětí z čidel • O každém procesu je znám – Potřebný čas (horní hranice délky CPU dávky) – Termín začátku a nejzazšího konce každého běhu periodicky spouštěného procesu • Předpoklady (zjednodušení) – Termín dokončení je identický s počátkem následující periody – Požadavky na systémové prostředky (či potřebu čekání na jejich přidělení) budeme ignorovat

A4B33OSS


30

Příklad 1 • 3 periodické procesy Proces Perioda pi A 30 B 40 C 50

A4B33OSS

Procesní čas Ti 10 15 5

Ti /pi 0,333 0,375 0,100


31

Plánovatelnost v periodických úlohách • Relativní využití strojového času Ti – Proces i využije poměrnou část ri  celkového pi strojového času, kde Ti je procesní čas a pi je jeho perioda N

N

Ti – Celkové využití je r   ri   i 1 i 1 pi – Aby vše mohlo pracovat musí platit (fyzikální podmínka plánovatelnosti) r  • Náš Příklad 1

A4B33OSS

N

Ti 1  i 1 pi

3

T i 10 15 5 r =∑ = + + =0,808 < 1 i=1 pi 30 40 50 Plánování procesů a synchronizace

32

Plánování RMS • •

Algoritmus RMS = Rate Monotonic Scheduling Statické priority – Prioi ≈ pi (kratší perioda = menší číslo ~ vyšší priorita) • Používá se pro procesy s následujícími vlastnostmi – Periodický proces musí skončit během své periody – Procesy jsou vzájemně nezávislé – Každý běh procesu (CPU dávka) spotřebuje konstantní čas – Předpokládá se, že preempce nastává okamžitě (bez režie) • Poznatek – Plánování je úspěšné, pokud se všechny procesy stihnou v době odpovídající periodě procesu s nejdelší periodou A4B33OSS


33

Plánování EDF •

EDF = Earliest Deadline First

–

•

Dynamické priority

–

•

Plánovač vede seznam připravených procesů uspořádaný podle požadovaných časů dokončení a spustí vždy ten s nejbližším požadovaným termínem dokončení

Použitelné i v následujících situacích

– –

•

Upřednostňuje proces s nejbližším termínem dokončení

Vlastnosti

– – –

A4B33OSS

Procesy nemusí být přísně periodické ani nemusí mít konstantní dobu běhu Pokud preempce nastává okamžitě, pak při plánování periodických procesů lze dodržet dokončovací termíny i při vytížení téměř 100% Algoritmus není analyticky plně prozkoumán Následky přetížení nejsou známy a nejsou předvídatelné Není známo chování v případech, kdy dokončovací termín a perioda jsou různé Plánování procesů a synchronizace

34

Příklad 1 (pokračování) Proces

Perioda pi

Procesní čas Ti

A

30

10

B

40

15

C

50

5

r=0,808

• Oba algoritmy fungují

– Dokonce chvílemi zbývá volný čas k běhu nějakého procesu „na pozadí“

A4B33OSS


35

Příklad 2

• Opět 3 periodické procesy Proces

Perioda pi

Procesní čas Ti

Ti /pi

Suma

A B

30 40

15 15

0,500 0,375

R = 0,975 < 1

C

50

5

0,100

A4B33OSS


Plánovatelné

36

Plánování RMS podrobněji • Dobře analyticky zpracovaný algoritmus zaručující dodržení termínů dokončení, pokud při N procesech platí (postačující podmínka) [Liu & Layland 1973]: N

Ti r N i 1 pi lim N

N 

A4B33OSS



N



N





N

N

2

0,828427

3

0,779763

4

0,756828

5

0,743491

10

0,717734

20

0,705298

2 1 ;



2  1  ln 2  0.693147


N



2 1

37

Plánování RMS podrobněji (2) • Jak je to s použitelností RMS?

P A B C

i 1 2 3

pi 7 8 10

Ti 2 3 1

T i /p i 0,286 0,375 0,100

Σ(T i /p i ) 0,286 0,661 0,761

P A B C

i 1 2 3

pi 6 8 10

Ti 2 3 1

T i /p i 0,333 0,375 0,100

Σ(T i /p i ) 0,333 0,708 0,808

P i p i T i T i /p i Σ(T i /p i ) A 1 4 B 2 5 C 3 6

1 0,250 0,250 1 0,200 0,450 3 0,500 0,950

P A B C

Ti 1 2 7

i 1 2 3

pi 4 5 20

A4B33OSS

T i /p i 0,250 0,400 0,350

Σ(T i /p i ) 0,250 0,650 1,000

0

1

1

0

2

1

1

1

0

2

1

0

3

3

1

7

1

9

1

8

1

10

2

9

2

11

2

10

2

11

2

6

2

5

1

8

1

6

5

4

7

3

2

3

6

5

4

3

2

2

2

3

5

4

3

2

2

2

2

2

4

3

2

1

1

2

1

1

3

3(3 2  1)  0,7797

Havárie - P 3 nestihnut

6

2

7

2

8

3

9

1

10

3


11

2

12

2

13

1

14

3

15

3

16

2

17

1

18

2

19

3

20

3

38

Plánování RMS podrobněji (3)

• Lehoczky, Sha & Ding [1989] podrobili RMS analýze znovu. Výsledek:



– Mějme procesy Pi , i  1 N pi  pi1 , i  1 N – Soustřeďme se na procesy 1...i, (i=1...N) a určeme vždy i

Wi (t )   T j  t / p j  , Li (t )  Wi (t ) / t , j 1

Li  min{0t Ti } Li (t ), L  max{1i N } Li

 1

Wi(t) reprezentuje kumulativní potřeby procesů P1 ... Pi v časovém úseku [0, t]

t   4, 5, 8,10,12,13 A4B33OSS


39

Plánování RMS podrobněji (4)

• Příklady použití uvedené teorie – RMS zhavaruje i 1 2 3

p i T i T i /p i Σ(T i /p i ) 4 1 0,250 0,250 5 1 0,200 0,450 6 3 0,500 0,950

L i (4) 0,250 0,500 1,250

L i (5) 0,400 0,600 1,200

L i (6) 0,333 0,667 1,167

Li 0,250 0,500 1,167

L i (5) 0,400 0,800 2,200

L i (8) L i (10) L i (12) L i (15) L i (16) L i (20) Li L 0,250 0,300 0,250 0,267 0,250 0,250 0,250 0,750 0,700 0,750 0,667 0,750 0,650 0,650 1,000 1,625 1,400 1,333 1,133 1,188 1,000 1,000

L 1,167

– RMS bude funkční i 1 2 3

A4B33OSS

p i T i T i /p i Σ(T i /p i ) 4 1 0,250 0,250 5 2 0,400 0,650 20 7 0,350 1,000

L i (4) 0,250 0,750 2,500


40

Problém synchronizace vláken • Souběžný přístup ke sdíleným datům může způsobit jejich nekonzistenci – nutná koordinace procesů

• Synchronizace běhu procesů – Čekání na událost vyvolanou jiným procesem

• Komunikace mezi procesy (IPC = Inter-process Communication) – Výměna informací (zpráv) – Způsob synchronizace, koordinace různých aktivit

• Sdílení prostředků – problém soupeření či souběhu (race condition) – – – – –

Procesy používají a modifikují sdílená data Operace zápisu musí být vzájemně výlučné Operace zápisu musí být vzájemně výlučné s operacemi čtení Operace čtení (bez modifikace) mohou být realizovány souběžně Pro zabezpečení integrity dat se používají kritické sekce

A4B33OSS


41

Synchronizace vláken

A4B33OSS


42

Úloha Producent-Konzument • Ilustrační příklad – Producent generuje data do vyrovnávací paměti s konečnou kapacitou (bounded-buffer problem) a konzument z této paměti data odebírá • V podstatě jde o implementaci komunikačního kanálu typu „roura“

– Zavedeme celočíselnou proměnnou count, která bude čítat položky v poli. Na počátku je count = 0 – Pokud je v poli místo, producent vloží položku do pole a inkrementuje count – Pokud je v poli nějaká položka, konzument při jejím vyjmutí dekrementuje count b[0]

b[1] out↑

b[2]

b[3]

b[4] in↑

...

b[0] in ... privátní proměnná producenta out ... privátní proměnná konzumenta A4B33OSS

b[k-1]

b[1]

b[2] in↑


b[3]

b[4] out↑

...

b[k-1]

43

Kód „Producent-Konzument“ Sdílená data: #define BUF_SZ = 20 typedef struct { … } item; item buffer[BUF_SZ]; int count = 0; Producent:

Konzument:

void producer() { int in = 0; item nextProduced; while (1) { /* Vygeneruj novou položku do proměnné nextProduced */ while (count == BUF_SZ); /* nedělej nic */ buffer[in] = nextProduced; in = (in + 1) % BUF_SZ; count++; } }

void consumer() { int out = 0; item nextConsumed; while (1) { while (count == 0) ; /* nedělej nic */ nextConsumed = buffer[out]; out = (out + 1) % BUF_SZ; count--; /* Zpracuj položku z proměnné nextConsumed */ } }

• Je to korektní řešení? A4B33OSS


44

Problém soupeření (race condition) • count++ bude obvykle implementováno takto: P1: registr0 ← count move count,D0 P2: registr0 ← registr0 + 1 add D0,#1 P3: count ← registr0 move D0,count • count-- bude obdobně implementováno jako: K1: registr1 ← count move count,D1 K2: registr1 ← registr1 – 1 sub D1,#1 K3: count ← registr1 move D1,count • Vlivem Murphyho zákonů, může nastat následující posloupnost prokládání producenta a konzumenta (nechť na počátku count = 3) Interval

Běží

Akce

Výsledek

P1 P2

producent producent

registr1 ← count registr1 ← registr1 + 1

registr1 = 3 registr1 = 4

K1 K2

konzument konzument

registr2 ← count registr2 ← registr2 - 1

registr2 = 3 registr2 = 2

P3

producent

count ← registr1

count = 4

K3

konzument

count ← registr2

count = 2

A4B33OSS


• Na konci může být count == 2 nebo 4, ale programátor zřejmě chtěl mít 3 (což se většinou podaří) • Je to důsledkem nepředvídatelného prokládání procesů/vláken vlivem možné preempce

45

Kritická sekce

• Problém lze formulovat obecně:

– Jistý čas se proces zabývá svými obvyklými činnostmi a jistou část své aktivity věnuje sdíleným prostředkům. – Část kódu programu, kde se přistupuje ke sdílenému prostředku, se nazývá kritická sekce procesu vzhledem k tomuto sdílenému prostředku (nebo také sdružená s tímto prostředkem).

• Je potřeba zajistit, aby v kritické sekci sdružené s jistým prostředkem, se nacházel nejvýše jeden proces

– Pokud se nám podaří zajistit, aby žádné dva procesy nebyly současně ve svých kritických sekcích sdružených s uvažovaným sdíleným prostředkem, pak je problém soupeření vyřešen.

• Modelové prostředí pro řešení problému kritické sekce

– Předpokládá se, že každý z procesů běží nenulovou rychlostí – Řešení nesmí záviset na relativních rychlostech procesů

A4B33OSS


46

Požadavky na řešení problému kritických sekcí 1. Vzájemné vyloučení – podmínka bezpečnosti (Mutual Exclusion) – Pokud proces Pi je ve své kritické sekci, pak žádný další proces nesmí být ve své kritické sekci sdružené s týmž prostředkem

2. Trvalost postupu – podmínka živosti (Progress) – Jestliže žádný proces neprovádí svoji kritickou sekci sdruženou s jistým zdrojem a existuje alespoň jeden proces, který si přeje vstoupit do kritické sekce sdružené se tímto zdrojem, pak výběr procesu, který do takové kritické sekce vstoupí, se nesmí odkládat nekonečně dlouho.

3. Konečné čekání – podmínka spravedlivosti (Fairness) – Proces smí čekat na povolení vstupu do kritické sekce jen konečnou dobu. – Musí existovat omezení počtu, kolikrát může být povolen vstup do kritické sekce sdružené se jistým prostředkem jiným procesům než procesu požadujícímu vstup v době mezi vydáním žádosti a jejím uspokojením.

A4B33OSS


47

Možnosti řešení problému kritických sekcí

• Základní struktura procesu s kritickou sekcí do {

enter_cs(); critical section leave_cs (); non-critical section } while (TRUE);

A4B33OSS

Klíčem k řešení celého problému kritických sekcí je korektní implementace funkcí enter_cs() a leave_cs().


48

• •

Řešení na aplikační úrovni (1) Vzájemné vyloučení s aktivním čekáním Zamykací proměnné –

Kritickou sekci „ochráníme" sdílenou zamykací proměnnou přidruženou ke sdílenému prostředku (iniciálně = 0). •

–

Před vstupem do kritické sekce proces testuje tuto proměnnou a, je-li nulová, nastaví ji na 1 a vstoupí do kritické sekce. Neměla-li proměnná hodnotu 0, proces čeká ve smyčce (aktivní čekání – busy waiting). •

–

A4B33OSS

while(lock != 0); /* Nedělej nic a čekej */ lock = 1

Při opouštění kritické sekce proces tuto proměnnou opět nuluje •

– –

proměnná lock

lock = 0;

Nevyřešili jsme však nic: souběh jsme přenesli na zamykací proměnnou Myšlenka zamykacích proměnných však není zcela chybná


49

Řešení na aplikační úrovni (2)

• Striktní střídání dvou procesů nebo vláken

– Zaveďme proměnnou turn, jejíž hodnota určuje, který z procesů smí vstoupit do kritické sekce. Je-li turn == 0, do kritické sekce může P0, je-li == 1, pak P1.

A4B33OSS

P0

P1

while(TRUE) { while(turn!=0); /* čekej */ critical_section(); turn = 1; noncritical_section(); }

while(TRUE) { while(turn!=1); /* čekej */ critical_section(); turn = 0; noncritical_section(); }


50

Řešení na aplikační úrovni (3)

• Petersonovo řešení střídání dvou procesů nebo vláken

– Řešení pro dva procesy Pi (i = 0, 1) – dvě globální proměnné: int turn;

boolean interest[2];

• Proměnná turn udává, který z procesů je na řadě při přístupu do kritické sekce • V poli interest procesy indikují svůj zájem vstoupit do kritické sekce; interest[i] == TRUE znamená, že Pi tuto potřebu má – Prvky pole interest nejsou sdílenými proměnnými

j = 1 – i; interest[i] = TRUE; turn = j; while (interest[j] && turn == j) ; /* čekání */ /* KRITICKÁ SEKCE interest[i] = FALSE;

/*

NEKRITICKÁ ČÁST PROCESU

*/

*/

• Náš proces bude čekat jen pokud druhý proces je na řadě a současně má zájem do kritické sekce vstoupit

• Všechna řešení na aplikační úrovni obsahují aktivní čekání, nebo používají funkci sleep/usleep

A4B33OSS


51

Hardwarová podpora pro synchronizaci • Zamykací proměnné rozumné, avšak je nutná atomicita • Jednoprocesorové systémy mohou vypnout přerušení – Při vypnutém přerušení nemůže dojít k preempci

• Nelze použít na aplikační úrovni (vypnutí přerušení je privilegovaná akce)

– Nelze jednoduše použít pro víceprocesorové systémy • Který procesor přijímá a obsluhuje přerušení?

• Moderní systémy nabízejí speciální nedělitelné (atomické) instrukce

– Tyto instrukce mezi paměťovými cykly „nepustí“ sběrnici pro jiný procesor – Instrukce TestAndSet atomicky přečte obsah adresované buňky a bezprostředně poté změní její obsah (tas – MC68k, tsl – Intel) – Instrukce Swap (xchg) atomicky prohodí obsah registru procesoru a adresované buňky – Např. IA32/64 (I586+) nabízí i další atomické instrukce • Prefix „LOCK“ pro celou řadu instrukcí typu read-modify-write (např. ADD, AND, … s cílovým operandem v paměti)

A4B33OSS


52

Hardwarová podpora pro synchronizaci (2)

• Příklad použití instrukce tas – Motorola 68000 enter_cs: tas lock bnz enter_cs ret

// Kopíruj lock do CPU a nastav lock na 1 // Byl-li lock nenulový, vrať se na testování // Byl nulový – návrat a vstup do kritické sekce

leave_cs: mov lock, #0 ret

// Vynuluj lock a odemkni kritickou sekci

• Příklad použití instrukce xchg – IA32 enter_cs: mov xchg jnz

EAX, #1 lock, EAX enter_cs

// 1 do registru EAX // Instrukce xchg lock, EAX atomicky prohodí // obsah registru EAX s obsahem lock. // Byl-li původní obsah proměnné lock nenulový, // skok na opakované testování = aktivní čekání // Nebyl – návrat a vstup do kritické sekce

lock, #0

// Vynuluj lock a odemkni tak kritickou sekci

ret

leave_cs: mov ret

A4B33OSS


53

Synchronizace bez aktivního čekání

• Aktivní čekání mrhá strojovým časem

– Může způsobit i nefunkčnost při rozdílných prioritách procesů • Např. vysokoprioritní producent zaplní pole, začne aktivně čekat a nedovolí konzumentovi odebrat položku (samozřejmě to závisí na metodě plánování procesů a na to navazující dynamicky se měnící priority)

• Blokování pomocí systémových atomických primitiv – sleep() – wakeup(process)

místo aktivního čekání – proces se zablokuje probuzení spolupracujícího procesu při opouštění kritické sekce

void producer() { while (1) { /* Vygeneruj položku do proměnné nextProduced */ if (count == BUFFER_SIZE) sleep(); // Je-li pole plné, zablokuj se buffer[in] = nextProduced; in = (in + 1) % BUFFER_SIZE; count++ ; if (count == 1) wakeup(consumer); // Bylo-li pole prázdné, probuď konzumenta } } void consumer() { while (1) { if (count == 0) sleep(); // Je-li pole prázdné, zablokuj se nextConsumed = buffer[out]; out = (out + 1) % BUFFER_SIZE; count-- ; if (count == BUFFER_SIZE-1) wakeup(producer); // Bylo-li pole plné, probuď producenta /* Zpracuj položku z proměnné nextConsumed */ } }

Výše uvedené řešení obsahuje chybu, oba dva procesy se mohou zaseknout. Najdete ji? A4B33OSS


54

Synchronizace bez aktivního čekání (2) • Předešlý kód není řešením: – Zůstalo konkurenční soupeření – count je opět sdílenou proměnnou • Konzument přečetl count == 0 a než zavolá sleep(), je mu odňat procesor • Producent vloží do pole položku a count == 1, načež se pokusí se probudit konzumenta, který ale ještě nespí! • Po znovuspuštění se konzument domnívá, že pole je prázdné a volá sleep() • Po čase producent zaplní pole a rovněž zavolá sleep() – spí oba! – Příčinou této situace je ztráta budícího signálu • Lepší řešení: – Jednině OS umí uspat a vzbudit procesy – Semafory A4B33OSS


55

Semafory

• Obecný synchronizační nástroj (Edsger Dijkstra, NL, [1930−2002]) • Semafor S – Systémem spravovaný objekt – Základní vlastností je celočíselná proměnná (obecný semafor) • Též čítající semafor

– Binární semafor (mutex) = zámek – hodnota 0 nebo 1

• Dvě standardní atomické operace nad semaforem – wait(S) – signal(S)

[někdy nazývaná acquire() nebo down(), původně P (proberen)] [někdy nazývaná release() nebo up(), původně V (vrhogen)]

• Sémantika těchto operací: wait(S) { while (S <= 0) S--; }

signal(S) {

; // čekej

S++; // Čeká-li proces před // semaforem, pusť ho dál }

• Tato sémantika stále obsahuje aktivní čekání • Skutečná implementace však aktivní čekání obchází tím, že spolupracuje s plánovačem CPU, což umožňuje blokovat a reaktivovat procesy (vlákna)

A4B33OSS


56

Implementace a užití semaforů • Implementace musí zaručit:

– Žádné dva procesy nebudou provádět operace wait() a signal() se stejným semaforem současně

• Implementace semaforu je problémem kritické sekce

– Operace wait() a post() musí být atomické – Aktivní čekání není plně eliminováno, je ale přesunuto z aplikační úrovně (kde mohou být kritické sekce dlouhé) do úrovně jádra OS pro implementaci atomicity operací se semafory

• Užití: mutex mtx;

A4B33OSS

// Volání systému o vytvoření semaforu, // inicializován na hodnotu 1 wait(mtx); // Volání akce nad semaforem, která může // proces zablokovat Critical_Section; post(mtx); // Volání akce nad semaforem, která může // ukončit blokování procesu čekajícího // „před“ semaforem


57

Implementace semaforů • Struktura semaforu

typedef struct { int value; struct process *list; } semaphore;

// „Hodnota“ semaforu // Fronta procesů stojících „před semaforem“

• Operace nad semaforem jsou pak implementovány jako nedělitelné s touto sémantikou void wait(semaphore S) { S.value= S.value - 1; if (S.value < 0) block(S.list); } void post(semaphore S) { S.value= S.value + 1 if (S.value <= 0) { if(S.list != NULL) { ... wakeup(P); } } }

A4B33OSS

// Je-li třeba, zablokuj volající proces a zařaď ho // do fronty před semaforem (S.list)

// Je-li fronta neprázdná // vyjmi proces P z čela fronty // a probuď P


58

Implementace semaforů (2) • Záporná hodnota S.value udává, kolik procesů „stojí“ před semaforem • Fronty před semaforem: Vždy FIFO – Nejlépe bez uvažování priorit procesů, jinak vzniká problém se stárnutím • Operace wait(S) a post(S) musí být vykonány atomicky – OS na jednom procesoru nemá problém, OS rozhoduje o přepnutí procesu – Více jader • problém i pro OS • Jádro bude používat atomické instrukce či jiný odpovídající hardwarový mechanismus na synchronizaci skutečného paralelizmu • Instrukce xchg, tas, či prefix lock musí umět zamknout sběrnici proti přístupu jiných jader, či zamknout a aktualizovat cache systémem cache snooping A4B33OSS


59

Producent-Konzument se semafory • Tři semafory

– mutex s iniciální hodnotou 1 – pro vzájemné vyloučení při přístupu do sdílené paměti – used – počet položek v poli – inicializován na hodnotu 0 – free – počet volných položek – inicializován na hodnotu BUF_SZ

void producer() { while (1) { /* Vygeneruj položku do proměnné nextProduced */ wait(free); wait(mutex); buffer [in] = nextProduced; in = (in + 1) % BUF_SZ; post(mutex); post(used); } } void consumer() { while (1) { wait(used); wait(mutex); nextConsumed = buffer[out]; out = (out + 1) % BUF_SZ; post(mutex); post(free); /* Zpracuj položku z proměnné nextConsumed */ } }

A4B33OSS


60

To je dnes vše.

Otázky?

A4B33OSS

61

Téma 4. Plánování procesů a synchronizace

Recommend Documents