====== AP6, IN6 Plánování v operačních systémech ======
===== Zadání =====
(Správa a plánování činnosti procesorů. Systémy souborů. Správa a plánování činnosti V/V zařízení)
===== Správa a plánování činnosti procesorů =====
Procesorů je ve výpočetních systémech téměř vždy méně, než procesů, OS musí rozhodnout, který proces dostane přidělen čas procesoru a na jak dlouho.
Cílem je dosažení maximálního využití CPU (v dnešní době všech jejich jader) pomocí multithreadingu (současný běh více procesů).
Běh programu se vyznačuje střídáním dávek instrukcí, a čekání na I/O. Čekání na I/O se využije pro zpracovávání instrukcí jiného procesu.
==== Typy plánování ====
* Krátkodobé - "Dispečer" - vybírá mezi procesy, které jsou "ready" ty, které se budou aktuálně zpracovávat na CPU.
* Střednědobé - Cykluje mezi procesy, které jsou "ready", "blocked", "ready suspended" a "blocked suspended" - tedy stará se vlastně o swapování na disk při nedostatku fyzické paměti.
* Dlouhodobé - Využívá se při spouštění nového procesu, vybírá, která úloha bude spuštěna. Význam hlavně při dávkovém zpracování
=== Dispečer - plánovač CPU ===
Vybírá mezi procesy, které sídlí v hlavní paměti ty, které jsou připravené k běhu – ready
Plánovací rozhodnutí vydává dispečer v okamžiku, kdy proces:
* vzniká a řadí se mezi připravené procesy
* přechází ze stavu //běžící// do stavu //čekající//
* přechází ze stavu //čekající// do stavu //připravený//
* končí
Z rozhodnutí dispečera může nastat, že proces přechází ze stavu //běžící// do stavu //připravený//
**Nepreemptivní** plánování (bez předbíhání)
* provádí se po dokončení připraveného plánu
* proces se musí procesoru sám vzdát - výhoda - nebude přerušen v kritické sekci, nevýhoda - pokud se zasekne, zablokuje celý OS
* jakmile se CPU předá vybranému procesu, tento nemůže být předběhnut žádným jiným procesem, dokud nedokončí dávku CPU
**Preemptivní** plánování (s předbíháním)
* provádí se v okamžiku změny stavu některého z procesů
* OS může procesu odebrat procesor, má nad ním kontrolu
* jakmile se ve frontě připravených objeví proces s prioritou vyšší než je priorita právě běžícího procesu, právě běžící proces je ve využívání CPU předběhnut novým procesem
**algoritmus předání**
* přepnutí kontextu z kontextu OS na kontext procesu
* vč. přepnutí režimu procesoru na uživatelský režim
* finále předání – skok na odpovídající místo v uživatelském programu pro restart procesu (určuje obraz čítače instrukcí v [[http://cs.wikipedia.org/wiki/Process_control_block|PCB]])
**dispečerské zpoždění** = doba, kterou potřebuje OS pro pozastavení běhu jednoho procesu a pro start běhu jiného procesu
==== Kritéria optimálního plánování ====
* maximální **využití procesoru** - cílem je udržení CPU v kontinuální užitečné činnosti
* maximální **propustnost** - cílem je maximalizace počtu procesů, které dokončí svůj běh za určitý čas
* minimální **doba provedení** - doba běhu procesu + doba pobytu mezi "ready"
* minimální **doba čekání** - kdo čeká na procesor a drží svoje zdroje je příčinou neefektivního využíváni
* minimální **doba odpovědi** - doba, která uplyne od zadání požadavku do první reakce (nemusí být úplná odpověď)
* **spravedlivost** - každý proces dostane spravedlivý podíl času
==== Plánovací algoritmus First Come First Serve ====
Jednoduchý algoritmus plánování bez předbíhání (nepreemptivní). Procesy se řadí ve FIFO frontě, jakmile se uvolní procesor, první proces ve frontě je přiřazen procesoru. Předchozí proces se zařadí na konec fronty jakmile se dostane opět do stavu "ready".
* jednoduchý na implementaci
* průměrná doba čekání může být dlouhá
* //konvojový// efekt - podobně jako před celnicí vznikaly konvoje kamionů, které čekají na odbavení (které trvá dlouho ~ procesy trvající dlouho) brání osobním autům (krátké procesy) aby přejely přes hranice...
* pro krátkodobé plánování se prakticky nepoužívá
==== Prioritní plánovací algoritmus ====
Procesům přiřazeny priority (p), plánovač vždy preferuje procesy s vyšší p. Preemptivní (procesor je procesu s nízkou p odebrán a přiřazen procesu s vyšší) i nepreemptivní (procesor není vzat procesu, dokud neskončí dávku) varianta. Procesy seskupeny do prioritních tříd.
* problém stárnutí (hladovění) procesů - proces s nízkou p může čekat dlouho (až nekonečeně), řešení: zrání procesů (procesům se zvyšuje priorita po čase)
==== Plánovací algoritmus Shortest Job First ====
Z čekajících procesů vybírá ten s nejkratší dávkou pro CPU. Ta je ovšem dopředu známa jenom velmi zřídka, proto se používá //exponenciální průměrování// na základě historie velikostí dávek procesu.
Požívá se jak preemptivní (pokud je ve frontě proces, který by běžel méně, než stávající proces je stávajícímu procesu procesor odebrán), tak nepreemptivní varianta.
* SJF je optimální algoritmus pro požadavek nejkratší čekací doby
* dlouhé procesy mohou stárnout
==== Exponenciální průměrování ====
Vypočítává odhady pro délku trvání procesu na základě předchozího chování programu.
Používá se parametr vlivu historie - říká jak moc má algoritmus přihlížet na historii běhu programu.
==== Plánovací algoritmus Round Robin ====
Preemptivní algoritmus plánování s FIFO frontou. Proces na CPU dostane **časové kvantum** //**q**// (délky desítky až stovky ms), po vypršení je zařazen na konec fronty kde je //**n**// procesů.
* efektivita silně závisí na velikosti //**q**// .
* + žádný proces nečeká déle než //**(n-1)q**// časových jednotek.
===== Systémy souborů =====
* Soubor je pojmenovaná kolekce souvisejících informací
* Soubor je logická paměťová jednotka operačním systémem zobrazovaná do fyzického paměťového zařízení
**Systém souborů** je součást operačního systému (ale nemusí být plně implementovaný v jádru OS!), který řeší správu sdílených zdrojů na vnějších pamětech.
==== Cíle systému souborů ====
* poskytuje vhodný systém pojmenování souborů
* poskytuje jednotnou podporu IO pro vnější paměti různých typů
* poskytuje standardizovanou sestavu postupů/programů na IO rozhraní
* poskytuje záruku validnosti dat v souborech
* optimalizuje výkon
* minimalizuje, až odstraňuje, riziko ztráty či poškození dat
* poskytuje podporu IO a řízení přístupu násobným uživatelům
* podporuje systém správy (např. archivaci)
==== Operace se souborem ====
* Create soubor
* Write záznam
* Read záznam v souboru
* File Seek - určení pracovní pozice v souboru
* Delete záznam v souboru
* Open - vyhledání záznamu o souboru v adresáři a přesunutí tohoto záznamu do operační paměti počítače do tabulky otevřených souborů
* Close - přesunutí záznamu o souboru z tabulky zpět do adresářové struktury disku
==== Zamykání souborů ====
Záleží na druhu OS, jestli soubor zamkne a ovlivní tím dalšího přístupu k souboru
Rozlišují se dva druhy zámků
• sdílený (shared) - všechny procesy mohou ze souboru číst, ale žádný nesmí zapisovat
• výlučný (exclusive) - k souboru může přistupovat výhradně jeden proces.
==== Přístupové metody k souborům ====
* Sekvenční přístup - čtení záznamu po záznamu, nelze přeskakovat záznamy, např. magnetická páska
* Přímý přístup - záznamy lze zpřístupňovat v jakémkoliv pořadí
**doba přístupu** (seek time) je dána:
* dobou vystavení - na válec se stopu s adresovaným sektorem
* dobou rotačního zpoždění - dodatečná doba do průchodu adresového sektoru pod čtecí/zápisovou hlavu
minimalizace doby vystavení
* doba vystavení je ekvivalentní vystavovací vzdálenosti
* problém řeší **správné plánování** přístupu na disk
==== Plánování činnosti disku ====
//Toto plánování je pravděpodobně jen pro disky s kruhovitým tvarem. Např. flash paměti mají přístup mnohem rychlejší a používají jiné metody(protože se netočí, ale jsou adresovány přímo?)//
== ==
{{:home:prog:os_planovani_fcfs.jpg|příklad plánování FCFS}}
**FCFS - First come, first served**
* (kdo dřív příjde ten dřív mele (data:D))
* podobně jako u plánování procesů, první kdo si řekne o čtení čte, ostatní čekají ve frontě.
* neefektivní, protože hlava může překonávat velké vzdálenosti
== ==
{{:home:prog:os_planovani_sstf.jpg|příklad plánování SSTF}}
**SSTF - Shortest Seek Time First**
* obdoba SJF, hrozí stárnutí
* optimální z hlediska minimalizace seek time
== ==
{{:home:prog:os_planovani_scan.jpg|příklad plánováni SCAN}}**SCAN (někdy také výtah)**
Funguje podobně jako výtah, který nemá tlačítko pro přivolání - jezdí od okraje do středu a zpět a vyřizuje požadavky podle pořadí zpřístupňovaných stop
== ==
{{:home:prog:os_planovani_cscan.jpg|příklad plánování C-SCAN}}
**C-SCAN**
Jednosměrný výtah - obdoba SCAN, ale požadavky jsou vyřizovány pouze po jedné cestě dle pořadí zpřístupňovaných stop, zpět se vrací bez vyřizování požadavků. Průměrné doby čekání jsou tak rozloženy rovnoměrněji.
== ==
{{:home:prog:os_planovani_clook.jpg|příklad plánování C-LOOK}}**C-LOOK**
Varianta C-SCAN, raménko se opakovaně pohybuje z kraje směrem ke středu a zpět a vrací se po dosažení posledního požadavku v tomto směru bez vyřizování požadavků a požadavky vyřizuje podle pořadí zpřístupňovaných stop.
==== Volba strategie plánování disku ====
* SSTF je přirozený
* SCAN a C-SCAN jsou vhodnější pro vysoce zatěžované disky
* výkon jednotlivých metod závisí na počtu a typu požadavků
* Plánovací algoritmus by měl být naprogramován jako samostatný modul, aby bylo možné algoritmus zaměňovat
* Často bývá implicitní volba SSTF nebo C-LOOK
===== Správa a plánování činnosti V/V zařízení =====
Základní představa - k počítači máme připojeny různé I/O(=V/V) zařízení a musíme ošetřit organizaci přístup k těmto zařízením(aby se například 2 procesy netiskly data na tiskárně ve stejnou chvíli).
{{:home:prog:os_schema_io.png|}}
Takhle nějak to vypadá, software se v našem případě = OS
==== Techniky provádění I/O: ====
**polling(vyzývání)**
programovaný I/O, činné čekání, synchronní operace
busy-wait - OS čeká aktivně na uvolnění I/O, nedělá nic jiného, než že zjišťuje stav I/O zařízení - zdržuje procesor.
Někdy se také používá polling tak, že procesor počítá a vždy po určitém čase zkontroluje pollované zařízení zda už je ready, pokud ne, tak se vrátí k počítání - zdržuje méně.
**přerušení**
* programovaný I/O, asynchronní
* označován jako interrupt, IRQ ve smyslu hardwarového přerušení
* reakce na signál od zařízení, které jím upozorňuje procesor (respektive ovladač zařízení v OS), že potřebuje obsloužit. Procesor při příchodu přerušení přestane provádět současný výpočet, uloží část svého stavu a začne vykonávat obsluhu přerušení.
**DMA (direct memory access)**
náhrada programovaného I/O, není využíván procesor, ale speciální DMA řadič
typicky pro velké toky dat (dnes už všechny HDD)
Příklad: zobrazení videa - proces potřebuje data v paměti, aby je mohl dekódovat+zobrazit, procesor ale data do paměti nepřenáší - řekne DMA řadiči, že data potřebuje v paměti, DMA se postará o jejich přenos, po dokončení přenosu informuje procesor pomocí přerušení a procesor řeší ve spolupráci s grafickou kartou jejich zobrazení.
==== blokující/neblokující I/O:====
*blokující - proces čeká na ukončení (nevyhovující), snadné použití
*neblokující - řízení procesu se vrací bez prodlení, buffered I/O, implementace pomocí vláken
*asynchronní - proces souběžně s I/O, konec I/O hlášeno přerušeními, složité použití
====IO subsystémy v jádru====
Dle druhu OS, nemusí být přítomny všechny
**plánování (I/O plánovače)**
* slouží pouze pro zvýšení výkonu (na rozdíl od plánovače procesů není nezbytný)
* některé řadiče mají vestavěný plánovač (SATA NCQ, SCSI, ...)
* CFQ = Completely Fair Queuing - obdoba round robin
**buffering** - zařízení A generuje data rychleji, než je zařízení B zvládne zpracovat, data pak uložíme do bufferu, a B si čte dle potřeby. I naopak(B generuje pomaleji, ale A potřebuje souvislý zdroj - nagenerejume do bufferu a A pak přečte)
**caching** - kopie(pouze kopie!) dat uložena v rychlé paměti - k dosažení vysokého výkonu.
**spooling**
V daném okamžiku může vstupně výstupní zařízení provádět jen jednu úlohu, požadavky do fronty. Pro realizaci fronty požadavků (úloh) je většinou využit souborový systém s přímým přistupem (disk, ramdisk). Např. tiskárna, magnetická páska
**rezervace** - exklusivní přístup k zařízení pro proces, nutná ochrana proti uváznutí)
===== Co byste ještě měli znát? =====
* Jaká metoda planování disku se používá v jednotlivých systémech souborů?
===== Předměty =====
[[https://is.muni.cz/auth/predmety/predmet.pl?id=427665|FI:PB152]] Operační systémy doc. Ing. Jan Staudek, CSc.
[[https://is.muni.cz/auth/predmety/predmet.pl?id=455015;|FI:PA150]] Principy operačních systémů doc. Ing. Jan Staudek, CSc.
===== Kam dál =====
[[ http://school.lynn.cz/statnice/OS.pdf | Úloha OS, prostředky počítače, představa virtuálního počítače - od Helenky :) (PDF)]]
[[ http://www.fit.vutbr.cz/study/courses/IOS/public/prednasky/ios-prednaska-05.pdf | Operační systémy z FIT VUT (PDF)]]
[[http://student.cvut.cz/cwut/index.php/Procesy,_vlákna,_jejich_plánování_a_přidělování_procesoru#First_Come_First_Served_.28FCFS.29 | FCFS Na ČWUT wiki]]
[[http://labe.felk.cvut.cz/vyuka/X33OSA/Tema-06-Planovani.pdf | Plánování práce procesorů (PDF)]]
===== Zdroje =====
zdroj: Jan Staudek, skripta [[http://www.fi.muni.cz/usr/staudek/vyuka/opsys/PB152.xhtml|PB152 Operační systémy]], 07_planovani.pdf
další texty: [[http://www.kai.vslib.cz/~kolar/os/old/part04.html]]
===== Vypracoval =====
Základ vložil: Musil Marek
dopracuje: Marek Babák do 19.6.08
99%, z mé strany hotovo, pokud máte něco k doplnění, upřesnění, opravení, tak to tam rovnou napište
~~DISCUSSION~~