Úvod do operačních systémů
Čau Habr! Rád bych vás upozornil na sérii článků-překladů jedné dle mého názoru zajímavé literatury - OSTEP. Tento materiál poměrně hluboce pojednává o práci unixových operačních systémů, konkrétně o práci s procesy, různými plánovači, pamětí a dalšími podobnými součástmi, které tvoří moderní OS. Originál všech materiálů si můžete prohlédnout zde . Upozorňuji, že překlad byl proveden neprofesionálně (zcela volně), ale doufám, že jsem zachoval obecný význam.
Laboratorní práce na toto téma naleznete zde:
Ostatní části:
Můžete se také podívat na můj kanál na =)
Úvod do Plánovače
Podstata problému: Jak vytvořit politiku plánovače
Jak by měly být navrženy základní rámce zásad plánovače? Jaké by měly být klíčové předpoklady? Jaké metriky jsou důležité? Jaké základní techniky byly používány v raných počítačových systémech?
Předpoklady pracovní zátěže
Než probereme možné zásady, udělejme nejprve několik zjednodušujících odboček o procesech běžících v systému, které se souhrnně nazývají pracovní zátěž. Definování pracovní zátěže je kritickou součástí vytváření zásad a čím více o pracovní zátěži víte, tím lepší politiku můžete napsat.
Udělejme následující předpoklady o procesech běžících v systému, někdy také tzv pracovních míst (úkoly). Téměř všechny tyto předpoklady nejsou realistické, ale jsou nezbytné pro rozvoj myšlení.
- Každý úkol běží stejnou dobu,
- Všechny úkoly jsou nastaveny současně,
- Zadaný úkol funguje až do jeho dokončení,
- Všechny úlohy využívají pouze CPU,
- Doba běhu každé úlohy je známá.
Metriky plánovače
Kromě některých předpokladů o zatížení je potřeba další nástroj pro porovnávání různých plánovacích politik: metriky plánovače. Metrika je jen nějaká míra něčeho. Existuje řada metrik, které lze použít k porovnání plánovačů.
Použijeme například metriku tzv doba obratu (doba obratu). Doba obratu úlohy je definována jako rozdíl mezi časem dokončení úlohy a časem příchodu úlohy do systému.
Tturnaround=Tcompletion–tarrival
Protože jsme předpokládali, že všechny úkoly dorazily ve stejnou dobu, pak Ta=0 a tedy Tt=Tc. Tato hodnota se přirozeně změní, když změníme výše uvedené předpoklady.
Další metrika - spravedlnost (férovost, poctivost). Produktivita a spravedlnost jsou často protichůdnými vlastnostmi plánování. Plánovač může například optimalizovat výkon, ale za cenu čekání na spuštění jiných úloh, čímž se sníží spravedlnost.
FIRST IN FIRST OUT (FIFO)
Nejzákladnější algoritmus, který můžeme implementovat, se nazývá FIFO resp kdo dřív přijde (vstoupí), ten dřív mele (odchází). Tento algoritmus má několik výhod: je velmi snadno implementovatelný a vyhovuje všem našim předpokladům a dělá svou práci docela dobře.
Podívejme se na jednoduchý příklad. Řekněme, že byly nastaveny 3 úkoly současně. Předpokládejme ale, že úkol A dorazil o něco dříve než všechny ostatní, takže se objeví v seznamu provedení dříve než ostatní, stejně jako B vzhledem k C. Předpokládejme, že každý z nich bude proveden po dobu 10 sekund. Jaká bude průměrná doba na dokončení těchto úkolů v tomto případě?
Počítáním hodnot - 10+20+30 a dělením 3 dostaneme průměrnou dobu provádění programu rovnou 20 sekundám.
Nyní zkusme změnit naše předpoklady. Konkrétně předpoklad 1, a proto již nebudeme předpokládat, že provedení každé úlohy trvá stejně dlouho. Jak si FIFO povede tentokrát?
Jak se ukazuje, různé doby provádění úloh mají extrémně negativní dopad na produktivitu algoritmu FIFO. Předpokládejme, že dokončení úkolu A bude trvat 100 sekund, zatímco úkolu B a C bude stále trvat každý 10 sekund.
Jak je vidět z obrázku, průměrný čas pro systém bude (100+110+120)/3=110. Tento efekt se nazývá konvojový efekt, kdy někteří krátkodobí spotřebitelé zdroje budou stát ve frontě po velkém spotřebiteli. Je to jako fronta v potravinách, když před vámi stojí zákazník s plným vozíkem. Nejlepším řešením problému je zkusit vyměnit pokladnu nebo se uvolnit a zhluboka dýchat.
Nejdříve nejkratší práce
Je možné nějak řešit podobnou situaci u těžkých procesů? Rozhodně. Dalším typem plánování je tzvNejdříve nejkratší práce (SJF). Jeho algoritmus je také docela primitivní - jak název napovídá, nejkratší úlohy budou spouštěny jako první, jedna po druhé.
V tomto příkladu bude výsledkem spuštění stejných procesů zlepšení průměrné doby obratu programu a bude se rovnat 50 místo 110, což je téměř 2x lepší.
Za daného předpokladu, že všechny úlohy přicházejí ve stejnou dobu, se tedy algoritmus SJF jeví jako nejoptimálnější algoritmus. Naše předpoklady se však stále nezdají reálné. Tentokrát změníme předpoklad 2 a tentokrát si představíme, že úkoly mohou být přítomny kdykoli a ne všechny ve stejnou dobu. K jakým problémům to může vést?
Představme si, že jako první přijde úkol A (100c) a začne se provádět. V t=10 přijdou úkoly B a C, z nichž každý zabere 10 sekund. Průměrná doba provádění je tedy (100+(110-10)+(120-10))3 = 103. Co by mohl plánovač udělat, aby to zlepšil?
Nejkratší čas do dokončení jako první (STCF)
Pro zlepšení situace vynecháváme předpoklad 3, že program je spuštěn a běží až do dokončení. Navíc budeme potřebovat hardwarovou podporu a jak asi tušíte, budeme ji využívat časovač k přerušení probíhající úlohy a přepínání kontextu. Plánovač tedy může v okamžiku příchodu úkolů B, C něco udělat - zastavit provádění úkolu A a zařadit úkoly B a C do zpracování a po jejich dokončení pokračovat v provádění procesu A. Takový plánovač se nazývá STCFnebo Preemptivní práce na prvním místě.
Výsledkem tohoto plánovače bude následující výsledek: ((120-0)+(20-10)+(30-10))/3=50. Takový plánovač se tak stává ještě optimálnějším pro naše úkoly.
Metrická doba odezvy
Pokud tedy známe dobu běhu úloh a že tyto úlohy využívají pouze CPU, bude STCF nejlepším řešením. A kdysi v raných dobách tyto algoritmy fungovaly docela dobře. Uživatel však nyní tráví většinu času u terminálu a očekává produktivní interaktivní zážitek. Tak se zrodila nová metrika - Doba odezvy (Odezva).
Doba odezvy se vypočítá takto:
Tresponse=Tfirstrun-Tarrival
V předchozím příkladu tedy bude doba odezvy: A=0, B=0, C=10 (abg=3,33).
A ukazuje se, že algoritmus STCF není tak dobrý v situaci, kdy přijdou 3 úkoly současně - bude muset počkat, až budou malé úkoly zcela dokončeny. Algoritmus je tedy dobrý pro metriku doby obratu, ale špatný pro metriku interaktivity. Představte si, že byste seděli u terminálu a snažili se zadat znaky do editoru a museli byste čekat déle než 10 sekund, protože CPU zabírala jiná úloha. Není to moc příjemné.
Stojíme tedy před dalším problémem – jak můžeme sestavit plánovač, který je citlivý na dobu odezvy?
Round Robin
K vyřešení tohoto problému byl vyvinut algoritmus Round Robin (RR). Základní myšlenka je celkem jednoduchá: místo spouštění úloh, dokud nejsou dokončeny, spustíme úlohu po určitou dobu (tzv. časový úsek) a poté přepneme na jinou úlohu z fronty. Algoritmus opakuje svou práci, dokud nejsou dokončeny všechny úkoly. V tomto případě musí být doba běhu programu násobkem doby, po které časovač proces přeruší. Pokud například časovač přeruší proces každých x=10ms, pak by velikost okna provádění procesu měla být násobkem 10 a být 10,20 nebo x*10.
Podívejme se na příklad: Úlohy ABC přicházejí do systému současně a každá z nich chce běžet 5 sekund. Algoritmus SJF dokončí každý úkol před zahájením dalšího. Naproti tomu algoritmus RR se spouštěcím oknem = 1s projde úkoly následovně (obr. 4.3):
(Opět SJF (špatné pro dobu odezvy)
(Round Robin (dobré pro dobu odezvy)
Průměrná doba odezvy pro algoritmus RR je (0+1+2)/3=1, zatímco pro SJF (0+5+10)/3=5.
Je logické předpokládat, že časové okno je pro RR velmi důležitým parametrem, čím menší je, tím vyšší je doba odezvy. Neměli byste jej však příliš zkracovat, protože čas přepínání kontextu bude také hrát roli v celkovém výkonu. Volba doby provádění je tedy nastavena architektem OS a závisí na úlohách, které se v něm plánují provést. Přepínání kontextu není jedinou servisní operací, která plýtvá časem – běžící program operuje se spoustou dalších věcí, například s různými cache, a při každém přepnutí je nutné toto prostředí uložit a obnovit, což může také zabrat spoustu čas.
RR je skvělý plánovač, pokud bychom mluvili pouze o metrice doby odezvy. Ale jak se bude metrika doby obratu úlohy chovat s tímto algoritmem? Uvažujme výše uvedený příklad, kdy provozní doba A, B, C = 5s a dorazí ve stejnou dobu. Úkol A skončí ve 13, B ve 14, C v 15 s a průměrná doba vyřízení bude 14 s. RR je tedy nejhorším algoritmem pro metriku obratu.
Obecněji řečeno, jakýkoli algoritmus typu RR je spravedlivý; rozděluje čas CPU rovnoměrně mezi všechny procesy. Tyto metriky jsou tedy neustále v rozporu.
Máme tedy několik kontrastních algoritmů a zároveň stále zbývá několik předpokladů - že je znám čas úlohy a že úloha využívá pouze CPU.
Míchání s I/O
Nejprve odstraníme předpoklad 4, že proces používá pouze CPU; přirozeně tomu tak není a procesy mohou přistupovat k dalším zařízením.
V okamžiku, kdy jakýkoli proces požaduje I/O operaci, proces vstoupí do zablokovaného stavu a čeká na dokončení I/O. Pokud je I/O odeslán na pevný disk, může taková operace trvat několik ms nebo déle a procesor bude v tuto chvíli nečinný. Během této doby může plánovač zaměstnávat procesor jakýmkoli jiným procesem. Další rozhodnutí, které bude muset plánovač učinit, je, kdy proces dokončí svůj I/O. Když k tomu dojde, dojde k přerušení a operační systém uvede proces, který volal I/O, do stavu připravenosti.
Podívejme se na příklad několika problémů. Každý z nich vyžaduje 50 ms CPU času. První z nich však bude přistupovat k I/O každých 10 ms (což bude také provedeno každých 10 ms). A proces B jednoduše používá 50ms procesor bez I/O.
V tomto příkladu použijeme plánovač STCF. Jak se bude plánovač chovat, pokud je na něm spuštěn proces jako A? Udělá následující: nejprve kompletně vypracuje proces A a poté proces B.
Tradiční přístup k řešení tohoto problému je považovat každou 10 ms dílčí úlohu procesu A za samostatnou úlohu. Když tedy začínáme s algoritmem STJF, je zřejmá volba mezi úlohou 50 ms a úlohou 10 ms. Poté, když je dílčí úloha A dokončena, bude spuštěn proces B a I/O. Po dokončení I/O bude zvykem znovu spouštět 10ms proces A místo procesu B. Tímto způsobem je možné implementovat overlap, kdy CPU využívá jiný proces, zatímco první čeká na I/O. A díky tomu je systém lépe využitelný – v momentě, kdy interaktivní procesy čekají na I/O, lze na procesoru spouštět další procesy.
Oracle už není
Nyní se pokusme zbavit domněnky, že doba běhu úlohy je známá. Toto je obecně nejhorší a nejvíce nerealistický předpoklad z celého seznamu. Ve skutečnosti, v průměrném běžném OS, samotný OS obvykle ví velmi málo o době provádění úloh, tak jak potom můžete vytvořit plánovač, aniž byste věděli, jak dlouho bude úloha trvat? Možná bychom mohli použít některé principy RR k vyřešení tohoto problému?
Celkový
Podívali jsme se na základní myšlenky plánování úloh a podívali jsme se na 2 rodiny plánovačů. První spouští nejkratší úlohu jako první a tím prodlužuje dobu obrátky, zatímco druhá je rovnoměrně rozdělena mezi všechny úkoly, čímž se prodlužuje doba odezvy. Oba algoritmy jsou špatné tam, kde jsou algoritmy z druhé rodiny dobré. Podívali jsme se také na to, jak může paralelní použití CPU a I/O zlepšit výkon, ale nevyřešili jsme problém s jasnozřivostí OS. A v další lekci se podíváme na plánovač, který se dívá do bezprostřední minulosti a snaží se předpovídat budoucnost. A nazývá se to víceúrovňová fronta zpětné vazby.
Zdroj: www.habr.com