Ú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 =)
Plánovanie: Viacúrovňový front spätnej väzby
V tejto prednáške si povieme o problémoch vývoja jedného z najznámejších prístupov k
plánovanie, ktoré je tzv Viacúrovňový front spätnej väzby (MLFQ). Plánovač MLFQ prvýkrát opísal v roku 1962 Fernando J. Corbató v systéme tzv
Kompatibilný systém zdieľania času (CTSS). Tieto práce (vrátane neskorších prác na
Multics) boli následne nominovaní na Turingovu cenu. Plánovač bol
následne vylepšený a získal vzhľad, ktorý možno nájsť už v
niektoré moderné systémy.
Algoritmus MLFQ sa snaží vyriešiť 2 základné prekrývajúce sa problémy.
Po prvé, sa snaží optimalizovať čas obrátky, ktorý, ako sme hovorili v predchádzajúcej prednáške, je optimalizovaný metódou začínania na čele frontu najviac
krátke úlohy. OS však nevie, ako dlho bude prebiehať ten či onen proces a toto
potrebné znalosti pre obsluhu algoritmov SJF, STCF. Za druhé, MLFQ skúša
aby systém reagoval na používateľov (napríklad pre tých, ktorí sedia a
hľadieť na obrazovku pri čakaní na splnenie úlohy) a tým minimalizovať čas
odpoveď. Algoritmy ako RR bohužiaľ znižujú čas odozvy, ale
majú zlý vplyv na metriku doby obratu. Preto náš problém: Ako navrhnúť
plánovač, ktorý bude spĺňať naše požiadavky a zároveň o ničom nevie
povaha procesu vo všeobecnosti? Ako sa môže plánovač naučiť vlastnosti úloh,
ktoré spúšťa, a tak robiť lepšie rozhodnutia o plánovaní?
Podstata problému: Ako naplánovať stanovenie úloh bez dokonalých znalostí?
Ako navrhnúť plánovač, ktorý súčasne minimalizuje čas odozvy
pre interaktívne úlohy a zároveň minimalizuje dobu obrátky bez toho, aby ste o tom vedeli
znalosť času vykonávania úlohy?
Poznámka: poučenie z predchádzajúcich udalostí
Front MLFQ je vynikajúcim príkladom systému, ktorý je trénovaný
minulé udalosti na predpovedanie budúcnosti. Takéto prístupy sú často
nachádza v OS (A v mnohých ďalších odvetviach informatiky vrátane odborov
hardvérové predpovede a algoritmy ukladania do vyrovnávacej pamäte). Podobné túry
spúšťač, keď úlohy majú behaviorálne fázy a sú teda predvídateľné.
Pri tejto technike by ste však mali byť opatrní, pretože predpovede sú veľmi jednoduché.
sa môže ukázať ako nesprávne a viesť systém k horším rozhodnutiam ako
bol by úplne bez vedomostí.
MLFQ: Základné pravidlá
Zvážte základné pravidlá algoritmu MLFQ. A hoci implementácie tohto algoritmu
je ich viacero, základné prístupy sú podobné.
V implementácii, ktorú budeme uvažovať, bude mať MLFQ niekoľko
samostatné fronty, z ktorých každý bude mať inú prioritu. kedykoľvek,
úloha pripravená na vykonanie je v jednom rade. MLFQ používa priority,
rozhodnúť, ktorú úlohu spustiť na vykonanie, t.j. úloha s vyšším
priorita (úloha z frontu s najvyššou prioritou) sa spustí ako prvá
fronte.
Samozrejme, v konkrétnom fronte môže byť viac úloh, takže
takže budú mať rovnakú prioritu. V tomto prípade sa použije mechanizmus
RR pre plánovanie spustenia medzi týmito úlohami.
Dostávame sa teda k dvom základným pravidlám pre MLFQ:
- Pravidlo 1: Ak priorita (A) > Priorita (B), úloha A sa spustí (B nebude)
- Pravidlo 2: Ak priorita(A) = Priorita(B), A&B sa spúšťajú pomocou RR
Na základe vyššie uvedeného sú kľúčové prvky plánovania MLFQ
sú priority. Namiesto toho, aby sme každému dali pevnú prioritu
úloha, MLFQ mení svoju prioritu v závislosti od pozorovaného správania.
Napríklad, ak sa úloha neustále ukončuje na CPU počas čakania na vstup z klávesnice,
MLFQ udrží vysokú prioritu procesov, pretože je to tak
interaktívny proces by mal fungovať. Ak je naopak úlohou neustále a
je dlhodobo náročný na CPU, MLFQ ho zníži
prioritou. MLFQ teda bude študovať správanie procesov v čase, keď bežia.
a používať správanie.
Uveďme si príklad toho, ako môžu fronty v určitom okamihu vyzerať
čas a potom dostanete niečo takéto:
V tejto schéme sú 2 procesy A a B vo fronte s najvyššou prioritou. Proces
C je niekde v strede a proces D je na samom konci frontu. Podľa vyššie uvedeného
popisy algoritmu MLFQ, plánovač vykoná iba úlohy s najvyššou hodnotou
priorita podľa RR, a úlohy C, D budú bez prac.
Prirodzene, statická snímka neposkytuje úplný obraz o tom, ako MLFQ funguje.
Je dôležité presne pochopiť, ako sa obraz mení v priebehu času.
Pokus 1: Ako zmeniť prioritu
V tomto bode sa musíte rozhodnúť, ako MLFQ zmení úroveň priority
úlohu (a tým aj pozíciu úlohy vo fronte) počas jej životného cyklu. Pre
z toho musíte mať na pamäti pracovný postup: určité množstvo
interaktívne úlohy s krátkymi časmi (a teda častým uvoľňovaním
CPU) a niekoľko dlho bežiacich úloh, ktoré využívajú CPU celý svoj pracovný čas
čas odozvy na takéto úlohy nie je dôležitý. A tak môžete urobiť prvý pokus
implementujte algoritmus MLFQ s nasledujúcimi pravidlami:
- Pravidlo 3: Keď úloha vstúpi do systému, zaradí sa do frontu s najvyššou
- prioritou.
- Pravidlo 4a: Ak úloha využíva celé svoje časové okno, potom ju
- priorita je znížená.
- Pravidlo 4b: Ak úloha uvoľní CPU pred uplynutím časového okna, potom to urobí
- zostáva s rovnakou prioritou.
Príklad 1: Jedna dlhotrvajúca úloha
Ako vidíte na tomto príklade, úloha pri prijímaní je nastavená na najvyššiu
prioritou. Po 10 ms časovom okne sa priorita procesu zníži.
plánovač. Po ďalšom časovom okne je úloha konečne znížená na
najnižšiu prioritu v systéme, kde zostáva.
Príklad 2: Zobral krátku úlohu
Teraz sa pozrime na príklad, ako sa MLFQ pokúsi priblížiť k SJF. V tom
napríklad dve úlohy: A, čo je nepretržite dlhotrvajúca úloha
zaberá CPU a B, čo je krátka interaktívna úloha. Predpokladajme
že A už nejaký čas bežal, keď prišla úloha B.
Tento graf zobrazuje výsledky scenára. Úloha A, ako každá úloha,
pomocou CPU bol úplne dole. Úloha B príde v čase T=100 a bude
umiestnené vo fronte s najvyššou prioritou. Keďže prevádzkový čas je krátky,
dokončí sa skôr, ako dosiahne posledný rad.
Z tohto príkladu by ste mali pochopiť hlavný cieľ algoritmu: pretože algoritmus nie
pozná dlhú alebo krátku úlohu, potom najskôr predpokladá, že úloha
krátky a dáva mu najvyššiu prioritu. Ak je to naozaj krátka úloha, tak
vykoná sa rýchlo, inak ak je to dlhá úloha, bude sa pohybovať pomaly
v priorite nadol a čoskoro dokáže, že je to skutočne dlhá úloha, ktorá nie
vyžaduje odpoveď.
Príklad 3: A čo I/O?
Teraz sa pozrime na príklad I/O. Ako je uvedené v pravidle 4b,
ak proces uvoľní procesor bez úplného využitia jeho procesorového času,
potom zostáva na rovnakej úrovni priority. Zámer tohto pravidla je pomerne jednoduchý.
- ak interaktívna úloha vykonáva veľa I/O, napríklad čaká
od stlačenia klávesov používateľa alebo myši, takáto úloha uvoľní procesor
pred prideleným oknom. Neradi by sme vynechali takúto prioritnú úlohu,
a teda zostane na rovnakej úrovni.
Tento príklad ukazuje, ako by algoritmus pracoval s takýmito procesmi - interaktívna úloha B, ktorá potrebuje CPU iba 1 ms pred vykonaním
I/O proces a dlhá úloha A, ktorá neustále využíva CPU.
MLFQ udržiava proces B na najvyššej priorite, ako aj naďalej
uvoľnite CPU. Ak B je interaktívna úloha, potom algoritmus v tomto prípade dosiahol
Vaším cieľom je rýchlo spúšťať interaktívne úlohy.
Problémy so súčasným algoritmom MLFQ
V predchádzajúcich príkladoch sme vytvorili základnú verziu MLFQ. A zdá sa, že on
robí svoju prácu dobre a spravodlivo, pričom medzi seba spravodlivo rozdeľuje čas CPU
dlhé úlohy a umožňujúce krátke úlohy alebo úlohy, ku ktorým je veľký prístup
na I/O na rýchle spracovanie. Bohužiaľ, tento prístup obsahuje niekoľko
vážne problémy.
Po prvé, Problém hladu: ak systém bude mať veľa interaktívnych
úlohy, spotrebujú celý čas procesora a teda ani jeden dlhý
úlohu nebude možné vykonať (hladujú).
Za druhéšikovní používatelia mohli písať svoje programy tak,
oklamať plánovača. Klamstvo spočíva v tom, že robíte niečo s cieľom prinútiť
plánovač, aby mal proces viac času CPU. Algoritmus, ktorý
popísaný vyššie je dosť zraniteľný voči takýmto útokom: pred časovým oknom je prakticky
musíte vykonať vstupno-výstupnú operáciu (pre niektoré, bez ohľadu na to, ktorý súbor)
a tým uvoľniť CPU. Takéto správanie vám umožní zostať v tom istom
samotnú frontu a opäť získate väčšie percento času CPU. Ak je hotovo
je to správne (napr. spustiť 99 % času okna pred uvoľnením CPU),
takáto úloha môže jednoducho monopolizovať procesor.
Nakoniec, program môže časom zmeniť svoje správanie. Tie úlohy
ktoré využívali CPU sa môžu stať interaktívnymi. V našom príklade podobne
úlohy nebudú od plánovača správne spracované, ako by to urobili iné
(pôvodné) interaktívne úlohy.
Otázka pre publikum: aké útoky na plánovač by mohli byť vykonané v modernom svete?
Pokus 2: Zvýšte prioritu
Skúsme zmeniť pravidlá a uvidíme, či sa môžeme vyhnúť problémom s
hladovanie. Čo môžeme urobiť, aby sme zabezpečili, že to súvisí
Úlohy CPU dostanú svoj čas (aj keď nie dlhý).
Ako jednoduché riešenie problému môžete pravidelne navrhovať
zvýšiť prioritu všetkých takýchto úloh v systéme. Spôsobov je veľa
aby sme to dosiahli, skúsme implementovať niečo jednoduché ako príklad: preložiť
všetky úlohy naraz s najvyššou prioritou, preto nové pravidlo:
- Pravidlo5: Po určitom čase S presuňte všetky úlohy v systéme do najvyššieho poradia.
Naše nové pravidlo rieši dva problémy naraz. Po prvé, procesy
zaručene neumrie od hladu: úlohy v najvyššom rade sa budú zdieľať
čas procesora podľa algoritmu RR a teda všetky procesy dostanú
čas procesora. Po druhé, ak nejaký proces, ktorý predtým použitý
iba procesor sa stane interaktívnym, zostane vo fronte s najvyšším
prioritu po získaní zvýšenia na najvyššiu prioritu raz.
Zvážte príklad. V tomto scenári zvážte použitie jedného procesu
CPU a dva interaktívne krátke procesy. Obrázok vľavo na obrázku ukazuje správanie bez zvýšenia priority, a teda dlho bežiaca úloha začne hladovať po príchode dvoch interaktívnych úloh do systému. Na obrázku vpravo sa každých 50 ms vykoná zvýšenie priority a tým je zaručené, že všetky procesy dostanú procesorový čas a budú sa pravidelne spúšťať. 50 ms sa v tomto prípade berie ako príklad, v skutočnosti je toto číslo o niečo vyššie.
Je zrejmé, že pridanie periodickej doby nábehu S vedie k
logická otázka: akú hodnotu treba nastaviť? Jeden zo zaslúžených
systémoví inžinieri John Ousterhout označovali podobné množstvá v systémoch ako voo-doo
konštantný, pretože nejakým spôsobom vyžadovali čiernu mágiu pre správne
vystavenie. A, bohužiaľ, S má takú príchuť. Ak nastavíte aj hodnotu
veľké - dlhé úlohy budú hladovať. A ak ho nastavíte príliš nízko,
interaktívne úlohy nedostanú správny čas procesora.
Pokus 3: Lepšie účtovníctvo
Teraz musíme vyriešiť ešte jeden problém: ako nie
dovoliť oklamať náš plánovač? Ľudia, ktorí sú zodpovední za túto možnosť, sú
pravidlá 4a, 4b, ktoré umožňujú úlohe zachovať si svoju prioritu uvoľnením procesora
pred uplynutím určeného času. Ako sa s tým vysporiadať?
Za riešenie v tomto prípade možno považovať lepšie účtovanie CPU času na každom
úroveň MLFQ. Namiesto toho, aby ste zabudli na čas, ktorý program použil
procesor pre pridelený interval, mali by ste ho vziať do úvahy a uložiť. Po
proces vyčerpal svoj pridelený čas, mal by byť preradený na ďalší
úroveň priority. Teraz nezáleží na tom, ako proces využije svoj čas - ako
neustále počítajúce na procesore alebo ako súbor hovorov. teda
pravidlo 4 by sa malo prepísať takto:
- Pravidlo4: Po tom, čo úloha vyčerpá svoj pridelený čas v aktuálnom fronte (bez ohľadu na to, koľkokrát uvoľnila CPU), priorita takejto úlohy sa zníži (presunie sa vo fronte nadol).
Pozrime sa na príklad:
»
Obrázok ukazuje, čo sa stane, ak sa pokúsite oklamať plánovač
ak by to bolo s predchádzajúcimi pravidlami 4a, 4b by bol výsledok vľavo. S novým
pravidlom je, že výsledok je vpravo. Pred ochranou mohol akýkoľvek proces volať I/O pred dokončením a
tak dominujú CPU, po povolení ochrany, bez ohľadu na správanie
I/O, bude stále klesať vo fronte, a teda nebude môcť nečestne
prevziať prostriedky CPU.
Zlepšenie MLFQ a ďalšie problémy
S vyššie uvedenými vylepšeniami vznikajú nové problémy: jeden z hlavných
otázky - ako parametrizovať takýto plánovač? Tie. Koľko by malo byť
fronty? Aká by mala byť veľkosť okna programu v rámci frontu? Ako
program by sa mal často uprednostňovať, aby sa zabránilo hladovaniu a
vziať do úvahy zmenu v správaní programu? Na tieto otázky nie je nič jednoduché
odozvy a len experimentuje so záťažou a následnou konfiguráciou
plánovač môže viesť k určitej uspokojivej rovnováhe.
Napríklad väčšina implementácií MLFQ vám umožňuje priradiť rôzne
časové úseky pre rôzne fronty. Zvyčajne sú fronty s vysokou prioritou
krátke intervaly. Tieto fronty pozostávajú z interaktívnych úloh,
prepínanie medzi ktorými je dosť citlivé a malo by trvať 10 alebo menej
pani. Naproti tomu fronty s nízkou prioritou pozostávajú z dlho prebiehajúcich úloh, ktoré používajú
CPU. A v tomto prípade veľmi dobre sedia dlhé časové intervaly (100 ms).
V tomto príklade sú 2 úlohy, ktoré pracovali vo fronte 20 s vysokou prioritou
ms rozdelené do 10 ms okien. 40 ms v strednom fronte (20 ms okno) a vo fronte s nízkou prioritou
časové okno fronty bolo 40 ms, kde úlohy dokončili svoju prácu.
Implementácia MLFQ v operačnom systéme Solaris je trieda časovo zdieľaných plánovačov.
Plánovač poskytne sadu tabuliek, ktoré presne definujú, ako by mal
zmeniť prioritu procesu v priebehu jeho životnosti, aká by mala byť veľkosť
okno, ktoré sa má prideliť, a ako často zvyšovať priority úloh. správca
systém môže interagovať s touto tabuľkou a prinútiť plánovač správať sa
inak. Štandardne má táto tabuľka 60 frontov s postupným zvyšovaním
veľkosť okna od 20 ms (vysoká priorita) do niekoľkých stoviek ms (najnižšia priorita) a
aj so zosilnením všetkých úloh raz za sekundu.
Iné plánovače MLFQ nepoužívajú tabuľku ani nič špecifické
pravidlá, ktoré sú popísané v tejto kapitole, naopak vypočítavajú priority pomocou
matematické vzorce. Napríklad plánovač vo FreeBSD používa vzorec pre
výpočet aktuálnej priority úlohy na základe toho, do akej miery je proces
použil CPU. Navyše využitie CPU časom hnije, a teda
Zvýšenie priority je teda trochu iné, ako je opísané vyššie. Toto je pravda
nazývané algoritmy rozpadu. Od verzie 7.1 používa FreeBSD plánovač ULE.
Napokon, veľa plánovačov má ďalšie funkcie. Napríklad niektoré
plánovače rezervujú vyššie úrovne pre prevádzku operačného systému a tým
Žiadny používateľský proces teda nemôže získať najvyššiu prioritu
systém. Niektoré systémy vám umožňujú radiť, aby ste pomohli
plánovač správne uprednostniť. Napríklad pomocou príkazu pekný
môžete zvýšiť alebo znížiť prioritu úlohy a tým zvýšiť alebo znížiť
znížiť šance programu na čas CPU.
MLFQ: Zhrnutie
Opísali sme plánovací prístup nazývaný MLFQ. Jeho meno
uzavretý v princípe fungovania – má niekoľko frontov a využíva spätnú väzbu
uprednostniť úlohu.
Konečná podoba pravidiel bude nasledovná:
- Pravidlo1: Ak priorita(A) > Priorita(B), úloha A sa spustí (B sa nespustí)
- Pravidlo2: Ak priorita(A) = Priorita(B), A&B sa spustia pomocou RR
- Pravidlo3: Keď úloha vstúpi do systému, zaradí sa do frontu s najvyššou prioritou.
- Pravidlo4: Po tom, čo úloha vyčerpá svoj pridelený čas v aktuálnom fronte (bez ohľadu na to, koľkokrát uvoľnila CPU), priorita takejto úlohy sa zníži (presunie sa vo fronte nadol).
- Pravidlo5: Po určitom čase S presuňte všetky úlohy v systéme do najvyššieho poradia.
MLFQ je zaujímavé z nasledujúceho dôvodu - namiesto toho, aby vyžadovalo znalosti o
charakter úlohy vopred, algoritmus sa naučí predchádzajúce správanie úlohy a sady
priority. Snaží sa teda sedieť na dvoch stoličkách naraz – dosahovať výkon pri malých úlohách (SJF, STCF) a poctivo behať dlhé,
Úlohy zaťažujúce CPU. Preto mnohé systémy, vrátane BSD a ich derivátov,
Solaris, Windows, Mac používajú ako plánovač nejakú formu algoritmu
MLFQ ako základ.
Dodatočné materiály:
- (výpočtový)
Zdroj: hab.com