Úvod do operačných systémov
Čau Habr! Chcel by som vám dať do pozornosti sériu článkov-prekladov jednej podľa mňa zaujímavej literatúry - OSTEP. Tento materiál pomerne hlboko rozoberá prácu operačných systémov podobných unixu, konkrétne prácu s procesmi, rôznymi plánovačmi, pamäťou a inými podobnými komponentmi, ktoré tvoria moderný OS. Originál všetkých materiálov si môžete pozrieť tu . Upozorňujem, že preklad bol urobený neprofesionálne (celkom voľne), ale dúfam, že som zachoval všeobecný význam.
Laboratórne práce na túto tému nájdete tu:
Ďalšie časti:
Môžete sa tiež pozrieť na môj kanál na =)
Úvod do Plánovača
Podstata problému: Ako vytvoriť politiku plánovača
Ako by mali byť navrhnuté základné rámce politiky plánovača? Aké by mali byť kľúčové predpoklady? Aké metriky sú dôležité? Aké základné techniky sa používali v prvých výpočtových systémoch?
Predpoklady pracovného zaťaženia
Pred diskusiou o možných politikách najprv urobme niekoľko zjednodušujúcich odbočiek o procesoch bežiacich v systéme, ktoré sa súhrnne nazývajú pracovná záťaž. Definovanie pracovného zaťaženia je kritickou súčasťou vytvárania politík a čím viac viete o pracovnom zaťažení, tým lepšiu politiku môžete napísať.
Urobme si nasledujúce predpoklady o procesoch bežiacich v systéme, niekedy aj tzv pracovných miest (úlohy). Takmer všetky tieto predpoklady nie sú reálne, ale sú nevyhnutné pre rozvoj myslenia.
- Každá úloha beží rovnako dlho,
- Všetky úlohy sú nastavené súčasne,
- Zadaná úloha funguje až do jej dokončenia,
- Všetky úlohy využívajú iba CPU,
- Doba trvania každej úlohy je známa.
Metriky plánovača
Okrem niektorých predpokladov o zaťažení je potrebný ďalší nástroj na porovnávanie rôznych plánovacích politík: metriky plánovača. Metrika je len miera niečoho. Existuje množstvo metrík, ktoré možno použiť na porovnanie plánovačov.
Použijeme napríklad metriku tzv doba obratu (doba obratu). Čas obrátky úlohy je definovaný ako rozdiel medzi časom dokončenia úlohy a časom príchodu úlohy do systému.
Tturnaround=Tcompletion-tarrival
Keďže sme predpokladali, že všetky úlohy prišli v rovnakom čase, potom Ta=0 a teda Tt=Tc. Táto hodnota sa prirodzene zmení, keď zmeníme vyššie uvedené predpoklady.
Ďalšia metrika - spravodlivosť (spravodlivosť, čestnosť). Produktivita a spravodlivosť sú často protichodné charakteristiky plánovania. Plánovač môže napríklad optimalizovať výkon, ale za cenu čakania na spustenie iných úloh, čím sa zníži spravodlivosť.
PRVÝ VO FIRST OUT (FIFO)
Najzákladnejší algoritmus, ktorý vieme implementovať, sa nazýva FIFO resp kto prvý príde (vstúpi), prvý melie (odíde). Tento algoritmus má niekoľko výhod: je veľmi jednoduchý na implementáciu a vyhovuje všetkým našim predpokladom a robí svoju prácu celkom dobre.
Pozrime sa na jednoduchý príklad. Povedzme, že boli nastavené 3 úlohy súčasne. Predpokladajme však, že úloha A prišla o niečo skôr ako všetky ostatné, takže sa objaví v zozname vykonávania skôr ako ostatné, rovnako ako B vzhľadom na C. Predpokladajme, že každá z nich bude vykonaná na 10 sekúnd. Aký bude priemerný čas na splnenie týchto úloh v tomto prípade?
Spočítaním hodnôt - 10+20+30 a delením 3 dostaneme priemerný čas vykonávania programu rovný 20 sekundám.
Teraz skúsme zmeniť naše predpoklady. Najmä predpoklad 1, a preto už nebudeme predpokladať, že vykonanie každej úlohy trvá rovnako dlho. Ako si FIFO povedie tentoraz?
Ako sa ukazuje, rôzne časy vykonávania úloh majú extrémne negatívny vplyv na produktivitu algoritmu FIFO. Predpokladajme, že dokončenie úlohy A bude trvať 100 sekúnd, zatiaľ čo úloha B a C bude stále trvať 10 sekúnd.
Ako je možné vidieť z obrázku, priemerný čas pre systém bude (100+110+120)/3=110. Tento efekt sa nazýva konvojový efekt, keď niektorí krátkodobí spotrebitelia zdroja budú stáť v rade za veľkým spotrebiteľom. Je to ako pri rade v potravinách, keď je pred vami zákazník s plným košíkom. Najlepším riešením problému je skúsiť vymeniť pokladňu alebo sa uvoľniť a zhlboka dýchať.
Najprv najkratšia práca
Je možné nejako vyriešiť podobnú situáciu s ťažkými procesmi? určite. Ďalším typom plánovania je tzvNajprv najkratšia práca (SJF). Jeho algoritmus je tiež dosť primitívny - ako už názov napovedá, najkratšie úlohy sa budú spúšťať jedna po druhej.
V tomto príklade bude výsledkom spustenia rovnakých procesov zlepšenie priemerného času obrátky programu a bude sa rovnať 50 namiesto 110, čo je takmer 2 krát lepšie.
Za daného predpokladu, že všetky úlohy prichádzajú v rovnakom čase, sa teda algoritmus SJF javí ako najoptimálnejší algoritmus. Naše predpoklady sa však stále nezdajú reálne. Tentokrát zmeníme predpoklad 2 a tentoraz si predstavíme, že úlohy môžu byť prítomné kedykoľvek a nie všetky v rovnakom čase. K akým problémom to môže viesť?
Predstavme si, že úloha A (100c) príde prvá a začne sa vykonávať. V čase t=10 prichádzajú úlohy B a C, z ktorých každá bude trvať 10 sekúnd. Priemerný čas vykonávania je teda (100+(110-10)+(120-10))3 = 103. Čo by mohol plánovač urobiť, aby to zlepšil?
Najkratší čas do dokončenia ako prvý (STCF)
V záujme zlepšenia situácie vynechávame predpoklad 3, že program je spustený a beží až do dokončenia. Okrem toho budeme potrebovať hardvérovú podporu a ako asi tušíte, budeme ju využívať časomerač na prerušenie spustenej úlohy a prepínanie kontextu. Plánovač teda môže v momente príchodu úloh B, C niečo urobiť - zastaviť vykonávanie úlohy A a dať úlohy B a C do spracovania a po ich dokončení pokračovať v vykonávaní procesu A. Takýto plánovač sa nazýva STCFalebo Preventívna práca na prvom mieste.
Výsledkom tohto plánovača bude nasledujúci výsledok: ((120-0)+(20-10)+(30-10))/3=50. Takto sa takýto plánovač stáva ešte optimálnejším pre naše úlohy.
Metrický čas odozvy
Ak teda poznáme dobu behu úloh a že tieto úlohy využívajú iba CPU, STCF bude najlepším riešením. A kedysi v raných dobách tieto algoritmy fungovali celkom dobre. Používateľka však teraz trávi väčšinu času pri termináli a očakáva produktívny interaktívny zážitok. Tak sa zrodila nová metrika - Doba odozvy (odpoveď).
Čas odozvy sa vypočíta takto:
Tresponse=Tfirstrun-Tarrival
V predchádzajúcom príklade teda bude čas odozvy: A=0, B=0, C=10 (abg=3,33).
A ukázalo sa, že algoritmus STCF nie je taký dobrý v situácii, keď prídu 3 úlohy súčasne - bude musieť počkať, kým budú malé úlohy úplne dokončené. Algoritmus je teda dobrý pre metriku doby obratu, ale zlý pre metriku interaktivity. Predstavte si, že by ste sedeli pri termináli a pokúšali sa zadať znaky do editora a museli by ste čakať viac ako 10 sekúnd, pretože CPU zaberala iná úloha. Nie je to veľmi príjemné.
Takže stojíme pred ďalším problémom – ako môžeme zostaviť plánovač, ktorý je citlivý na čas odozvy?
Okrúhly Robin
Na vyriešenie tohto problému bol vyvinutý algoritmus Okrúhly Robin (RR). Základná myšlienka je celkom jednoduchá: namiesto spúšťania úloh, kým nie sú dokončené, spustíme úlohu určitý čas (nazývaný časový úsek) a potom prejdeme na inú úlohu z frontu. Algoritmus opakuje svoju prácu, kým nie sú dokončené všetky úlohy. V tomto prípade musí byť čas chodu programu násobkom času, po ktorom časovač preruší proces. Napríklad, ak časovač preruší proces každých x=10ms, potom by veľkosť okna vykonávania procesu mala byť násobkom 10 a byť 10,20 alebo x*10.
Pozrime sa na príklad: Úlohy ABC prichádzajú súčasne do systému a každá z nich chce bežať 5 sekúnd. Algoritmus SJF dokončí každú úlohu pred spustením ďalšej. Naproti tomu algoritmus RR so spúšťacím oknom = 1s prejde úlohami nasledovne (obr. 4.3):
(Opäť SJF (zlý čas odozvy)
(Round Robin (dobré pre čas odozvy)
Priemerný čas odozvy pre algoritmus RR je (0+1+2)/3=1, zatiaľ čo pre SJF (0+5+10)/3=5.
Je logické predpokladať, že časové okno je pre RR veľmi dôležitým parametrom, čím je menšie, tým je čas odozvy vyšší. Nemali by ste ho však príliš zmenšovať, pretože čas prepínania kontextu bude tiež hrať úlohu v celkovom výkone. Výber času okna vykonávania teda nastavuje architekt OS a závisí od úloh, ktoré sa v ňom plánujú vykonať. Prepínanie kontextu nie je jedinou operáciou služby, ktorá mrhá časom – spustený program operuje s množstvom iných vecí, napríklad s rôznymi vyrovnávacími pamäťami a pri každom prepnutí je potrebné toto prostredie uložiť a obnoviť, čo môže tiež zabrať veľa čas.
RR je skvelý plánovač, ak by sme hovorili len o metrike času odozvy. Ale ako sa bude správať metrika času obrátky úlohy s týmto algoritmom? Zoberme si vyššie uvedený príklad, keď prevádzkový čas A, B, C = 5 s a dorazí v rovnakom čase. Úloha A skončí o 13, B o 14, C o 15 s a priemerný čas obrátky bude 14 s. RR je teda najhorší algoritmus pre metriku obratu.
Všeobecnejšie povedané, každý algoritmus typu RR je spravodlivý; rozdeľuje čas CPU rovnomerne medzi všetky procesy. A teda tieto metriky sú neustále v konflikte.
Máme teda niekoľko kontrastných algoritmov a zároveň stále zostáva niekoľko predpokladov - že je známy čas úlohy a že úloha využíva iba CPU.
Miešanie s I/O
Najprv odstránime predpoklad 4, že proces používa iba CPU; prirodzene to tak nie je a procesy môžu pristupovať k iným zariadeniam.
V momente, keď akýkoľvek proces požaduje I/O operáciu, proces vstúpi do zablokovaného stavu a čaká na dokončenie I/O. Ak sa I/O odošle na pevný disk, takáto operácia môže trvať niekoľko ms alebo dlhšie a procesor bude v tejto chvíli nečinný. Počas tejto doby môže plánovač zamestnať procesor akýmkoľvek iným procesom. Ďalšie rozhodnutie, ktoré bude musieť plánovač urobiť, je, kedy proces dokončí svoje I/O. Keď sa to stane, dôjde k prerušeniu a operačný systém uvedie proces, ktorý volal I/O, do stavu pripravenosti.
Pozrime sa na príklad niekoľkých problémov. Každý z nich vyžaduje 50 ms času CPU. Prvý z nich však bude pristupovať k I/O každých 10 ms (čo sa tiež vykoná každých 10 ms). A proces B jednoducho používa 50 ms procesor bez I/O.
V tomto príklade použijeme plánovač STCF. Ako sa bude plánovač správať, ak sa na ňom spustí proces ako A? Urobí nasledovné: najprv kompletne vypracuje proces A a potom proces B.
Tradičným prístupom k riešeniu tohto problému je považovať každú 10 ms podúlohu procesu A za samostatnú úlohu. Pri spustení s algoritmom STJF je teda zrejmá voľba medzi 50 ms úlohou a 10 ms úlohou. Potom, keď sa dokončí podúloha A, spustí sa proces B a I/O. Po dokončení I/O bude zvykom opäť spustiť 10 ms proces A namiesto procesu B. Týmto spôsobom je možné implementovať overlap, kedy CPU využíva iný proces, zatiaľ čo prvý čaká na I/O. A vďaka tomu je systém lepšie vyťažený – v momente, keď interaktívne procesy čakajú na I/O, môžu byť na procesore vykonávané ďalšie procesy.
Oracle už nie je
Teraz sa skúsme zbaviť predpokladu, že je známy čas chodu úlohy. Toto je vo všeobecnosti najhorší a najnerealistickejší predpoklad z celého zoznamu. V skutočnosti, v priemernom bežnom OS, samotný OS zvyčajne vie veľmi málo o čase vykonávania úloh, tak ako potom môžete vytvoriť plánovač bez toho, aby ste vedeli, ako dlho bude úloha trvať? Možno by sme mohli použiť niektoré princípy RR na vyriešenie tohto problému?
Celkový
Pozreli sme sa na základné myšlienky plánovania úloh a pozreli sme sa na 2 rodiny plánovačov. Prvý spúšťa najkratšiu úlohu ako prvý a tým zvyšuje čas obrátky, zatiaľ čo druhý je rovnomerne rozdelený medzi všetky úlohy, čím sa zvyšuje čas odozvy. Oba algoritmy sú zlé tam, kde sú algoritmy druhej rodiny dobré. Pozreli sme sa tiež na to, ako môže paralelné použitie CPU a I/O zlepšiť výkon, ale nevyriešili sme problém s jasnovidnosťou OS. A v ďalšej lekcii sa pozrieme na plánovač, ktorý sa pozerá do bezprostrednej minulosti a snaží sa predpovedať budúcnosť. A nazýva sa to viacúrovňový front spätnej väzby.
Zdroj: hab.com