AP6, IN6 Plánování v operačních systémech

(Správa a plánování činnosti procesorů. Systémy souborů. Správa a plánování činnosti V/V zařízení)

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.

• 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í

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 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

• 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

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á

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)

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

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.

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.

• 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.

• 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)

• 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

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.

• 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

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?)

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

SSTF - Shortest Seek Time First

• obdoba SJF, hrozí stárnutí
• optimální z hlediska minimalizace seek time

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

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.

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.

• 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

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).

Takhle nějak to vypadá, software se v našem případě = OS

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í - 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í

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í)

• Jaká metoda planování disku se používá v jednotlivých systémech souborů?

FI:PB152 Operační systémy doc. Ing. Jan Staudek, CSc.
FI:PA150 Principy operačních systémů doc. Ing. Jan Staudek, CSc.

Úloha OS, prostředky počítače, představa virtuálního počítače - od Helenky :) (PDF) Operační systémy z FIT VUT (PDF) FCFS Na ČWUT wiki Plánování práce procesorů (PDF)

zdroj: Jan Staudek, skripta PB152 Operační systémy, 07_planovani.pdf
další texty: http://www.kai.vslib.cz/~kolar/os/old/part04.html

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