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

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
příklad plánování SSTF

SSTF - Shortest Seek Time First

  • obdoba SJF, hrozí stárnutí
  • optimální z hlediska minimalizace seek time
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

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.

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

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

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

Kam dál

Zdroje

zdroj: Jan Staudek, skripta 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

Diskuze

, 2008/06/17 18:19

Nepatri ty algoritmy planovani pristupu na disk spise do systemu souboru? Podle me je tato otazka zamerena na planovani, a proto bych u systemu souboru nemluvil o tom co to je system souboru, ale spis bych tam popsal ty algoritmy FIFO,SSTF,SCAN …..
Je zde prece napsano neco jako: SYSTEM SOUBORU - nastroje pro manipulaci s daty na vnejsi pameti

, 2008/06/19 09:55

Tak jsem to našel ve skriptech k organizaci souboru a přepsal to sem, ještě promyslím co s těma obecnýma informacema.

, 2008/06/20 14:43

doplnil jsem u I/O DMA, polling, IRQ + subsystémy
rozepsal jsem to o něco víc než je to ve skriptech
odstranil jsem dle mého názoru irelevantní informace ve vztahu k plánování OS

, 2008/06/21 14:32

Neřekl bych, že proces=vlákno. Procesy mohou obsahovat více vláken. Jednolivé procesy mají svůj vlastní kontext (PC-program counter, zásobník…), zatímco vlákna jednoho procesu (viz vícevláknové aplikace) mají kontext společný…

, 2008/06/21 15:03

t.j. 1, opraveno

, 2008/06/21 20:19

Pekne spracovane. Drobnym nedostatkom je asi cast systemy suborov, tam si myslim, ze sa po nas chce nieco o FAT, NTFS apod.

, 2008/06/21 22:38

to je otázka… aplikovaní ji mají v otázce 12, tahle otázky zní vyloženě plánování v operačních systémech a podotázka je Systém souborů (takže logicky plánování systému souborů v operačních systémech) ale explicitně to tam uvedený není, takže se nebudu hádat, klidně se to naučte. :)

, 2010/06/03 12:43

btw doba pristupu disku k datam je access time nie seek time, doba pristupu(access time) = seek time + latency. Podla mna seek time je to vystavenie hlaviciek na spravnu stopu a latency je ta rotacna doba

You could leave a comment if you were logged in.
home/prog/ap6.txt · Poslední úprava: 2014/10/27 09:07 (upraveno mimo DokuWiki)
Nahoru
CC Attribution-Noncommercial-Share Alike 3.0 Unported
chimeric.de = chi`s home Valid CSS Driven by DokuWiki do yourself a favour and use a real browser - get firefox!! Recent changes RSS feed Valid XHTML 1.0