Operační systémy pro mobilní zařízení (OSMZ)
Týden III. (22.2.-26.2.2021)
Před námi je problematika spojená s plánovači procesů a později jejich implementace v rámci online úkolů.
Plánovač procesů řeší výběr, kterému z čekajících a připravených pro běh procesu bude přidělen procesor a proces tak poběží. Výběr je závislý na prioritách jednotlivých procesů a algoritmu, kterým výběr provedeme (přehled nejznámějších algoritmů).
Pokud operační systém musí čekat, až mu proces nabídne přeplánování procesoru speciálním voláním služby operačního systému, případně skončí či je zablokovaný, pak se jedná o nepreemptivní plánování. Takový systém není schopen si vynutit přepnutí a spoléhá pouze na spolupráci aplikačních programů. Tento typ plánovače se používal např. u Windows 3.1 a v dnešní době kromě velmi speciální aplikací nebývá využit. Je-li operační systém schopen naopak kdykoliv procesu odebrat procesor, tj. drží si absolutní kontrolu nad počítačem a všemi prostředky, které procesům přiděluje, jedná se o preemptivní plánování. K přepnutí dochází zpravidla po uplynutí časového kvanta určeného pro běh procesu a je vyvoláno přerušením od systémového časovače (PIT nebo HPET). Shrnutí rozdílů obou přístupu. V rámci druhé části cvičení budeme implementovat plánovací algoritmy Round-Robin a Lottery Scheduling.
Round-Robin (RR) je jeden z nejstarších a velmi často implementovaných plánovacích algoritmů. Spuštěnému procesu je přiděleno určité kvantum času, po který může být proces zpracováván na procesoru. Po uběhnutí tohoto času (řešeno časovačem) je proces odstaven a na místo něj je spuštěn jiný. Algoritmus předpokládá konstantní prioritu všech procesů, které plánuje.
Lottery Scheduling (LS) je typ pravděpodobnostního plánovacího algoritmu. Každému procesu je přiřazen určitý počet losů a plánovač při každém přepnutí losuje náhodný tiket na základě kterého vybere příští proces, kterému přidělí dané kvantum času. Jakmile tomuto procesu vyprší jeho kvantum, losuje se znovu. Distribuce losů nemusí být jednotná; procesy s větším počtem losů mají relativně vyšší šanci na výběr a tím pádem i vyšší prioritu. Tento plánovací algoritmus inherentně řeší problém hladovění. Poskytnutí každému procesu alespoň jeden los zaručuje, že má nenulovou pravděpodobnost, že bude vybrán.
PREZENTACE
LITERATURA
Andrew S. Tanenbaum - Moderní operační systémy. 4. vydání:
- kap. 2.4 Plánování procesů (str. 149 - 167)
- kap. 8.1.4 Plánování na víceprocesorových systémech (str. 539 - 545)
- kap. 10.3.4 Plánování v Linuxu (str. 746 - 750)
BONUS MATERIÁLY
Simulátor chování různých plánovacích algoritmů
Článek o návrhu plánovače pro sondu Mars 2020
Shrnutí plánovacích algoritmů - CPU Scheduling a Scheduling and CPU Scheduling.
OTÁZKY
Po přečtení výše uvedených textů byste měli být schopni odpovědět na další otázky z okruhů ke zkoušce, konkrétně:
- Vysvětlete pojem multitasking, preemptivní a nepreemptivní plánování.
- K čemu slouží plánovač procesů, jaké jsou jeho očekávané vlastnosti/strategie.
- Stručně vysvětlete plánovací algoritmus Round-Robin (RR), výhody/nevýhody.
- Stručně vysvětlete plánovací algoritmus Lottery Scheduling (LS), výhody/nevýhody.