Ú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 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 telegram =)

Plánování: Víceúrovňová fronta zpětné vazby

V této přednášce budeme hovořit o problémech vývoje jednoho z nejznámějších přístupů k
plánování, které se nazývá Víceúrovňová fronta zpětné vazby (MLFQ). Plánovač MLFQ byl poprvé popsán v roce 1962 Fernandem J. Corbató v systému tzv
Kompatibilní systém sdílení času (CTSS). Tyto práce (včetně pozdějších prací na
Multics) byli následně nominováni na Turingovu cenu. Plánovač byl
následně vylepšil a získal vzhled, který lze nalézt již v
některé moderní systémy.

Algoritmus MLFQ se snaží vyřešit 2 základní překrývající se problémy.
Za prvé, se snaží optimalizovat dobu obratu, která, jak jsme probrali v minulé přednášce, je optimalizována metodou spouštění v čele fronty nejvíce
krátké úkoly. OS však neví, jak dlouho poběží ten či onen proces a toto
potřebné znalosti pro práci s algoritmy SJF, STCF. Za druhé, MLFQ se snaží
aby byl systém citlivý pro uživatele (například pro ty, kteří sedí a
zírání na obrazovku při čekání na dokončení úkolu) a tím minimalizovat čas
Odezva. Algoritmy jako RR bohužel zkracují dobu odezvy, ale
mít špatný vliv na metriku doby obratu. Proto náš problém: Jak navrhovat
plánovač, který bude splňovat naše požadavky, aniž bychom o čemkoli věděli
povaha procesu obecně? Jak se může plánovač naučit vlastnosti úkolů,
které spouští, a tím lépe rozhodovat o plánování?

Podstata problému: Jak naplánovat zadání úkolů bez dokonalé znalosti?
Jak navrhnout plánovač, který současně minimalizuje dobu odezvy
pro interaktivní úkoly a zároveň minimalizuje dobu obrátky bez vědomí
znalost doby provádění úkolu?

Poznámka: poučení z předchozích akcí

Fronta MLFQ je vynikajícím příkladem systému, který je trénován
minulé události k předpovídání budoucnosti. Podobné přístupy jsou často
nalezené v OS (A v mnoha dalších odvětvích informatiky, včetně odvětví
hardwarové predikce a cachovací algoritmy). Podobné výlety
spustit, když úkoly mají behaviorální fáze a jsou tedy předvídatelné.
S touto technikou je však třeba být opatrný, protože předpovědi jsou velmi snadné.
se může ukázat jako nesprávné a vést systém k horším rozhodnutím než
byl by úplně bez znalostí.

MLFQ: Základní pravidla

Zvažte základní pravidla algoritmu MLFQ. A i když implementace tohoto algoritmu
existuje několik, základní přístupy jsou podobné.
V implementaci, kterou budeme zvažovat, bude mít MLFQ několik
samostatné fronty, z nichž každá bude mít jinou prioritu. kdykoliv,
úkol připravený k provedení je v jedné frontě. MLFQ používá priority,
rozhodnout, který úkol spustit k provedení, tzn. úkol s vyšší
priorita (úloha z fronty s nejvyšší prioritou) bude spuštěna jako první
fronta.
Samozřejmě může být v konkrétní frontě více než jeden úkol, takže
takže budou mít stejnou prioritu. V tomto případě bude použit mechanismus
RR pro plánování startu mezi těmito úkoly.
Dostáváme se tedy ke dvěma základním pravidlům pro MLFQ:

Pravidlo 1: Pokud priorita(A) > Priorita(B), úloha A poběží (B ne)
Pravidlo 2: Pokud priorita(A) = Priorita(B), A&B jsou spuštěny pomocí RR

Na základě výše uvedeného jsou klíčové prvky plánování MLFQ
jsou priority. Namísto toho, abychom každému dali pevnou prioritu
úkolu, MLFQ mění svou prioritu v závislosti na pozorovaném chování.
Pokud se například úloha neustále ukončuje na CPU při čekání na vstup z klávesnice,
MLFQ udrží prioritu procesu vysokou, protože je to tak
Interaktivní proces by měl fungovat. Pokud je naopak úkolem neustále a
je dlouhodobě náročný na CPU, MLFQ jej sníží
prioritou. MLFQ tedy bude studovat chování procesů v době, kdy běží.
a používat chování.
Pojďme si nakreslit příklad, jak by mohly fronty v určitém okamžiku vypadat
čas a pak dostanete něco takového:

V tomto schématu jsou 2 procesy A a B ve frontě s nejvyšší prioritou. Proces
C je někde uprostřed a proces D je na samém konci fronty. Podle výše uvedeného
Podle popisů algoritmu MLFQ bude plánovač provádět úkoly pouze s nejvyšším
priorita dle RR, a úkoly C, D budou bez práce.
Statický snímek přirozeně neposkytne úplný obrázek o tom, jak MLFQ funguje.
Je důležité přesně pochopit, jak se obrázek v průběhu času mění.

Pokus 1: Jak změnit prioritu

V tomto okamžiku se musíte rozhodnout, jak MLFQ změní úroveň priority
úkolu (a tím i pozice úkolu ve frontě) během jeho životního cyklu. Pro
z toho musíte mít na paměti pracovní postup: určité množství
interaktivní úlohy s krátkou dobou běhu (a tedy častým uvolňováním
CPU) a několik dlouhých úkolů, které využívají CPU celou svou pracovní dobu
doba odezvy u takových úkolů není důležitá. A tak můžete udělat první pokus
implementujte algoritmus MLFQ s následujícími pravidly:

Pravidlo 3: Když úkol vstoupí do systému, zařadí se do fronty s nejvyšší
přednost.
Pravidlo 4a: Pokud úkol využívá celé své časové okno, pak ano
priorita je snížena.
Pravidlo 4b: Pokud úloha uvolní CPU před vypršením časového okna, pak ano
zůstává se stejnou prioritou.

Příklad 1: Jeden dlouhodobý úkol

Jak vidíte na tomto příkladu, úkol při přijetí je nastaven na nejvyšší
přednost. Po 10 ms časovém okně je priorita procesu snížena.
plánovač. Po dalším časovém okně je úloha konečně snížena na nižší verzi
nejnižší prioritu v systému, kde zůstává.

Příklad 2: Dodán krátký úkol

Nyní se podívejme na příklad, jak se MLFQ pokusí přiblížit SJF. V tomto
například dva úkoly: A, což je neustále dlouhodobý úkol
zabírá CPU a B, což je krátký interaktivní úkol. Předpokládat
že A už nějakou dobu běžel, než přišel úkol B.

Tento graf ukazuje výsledky scénáře. Úkol A, jako každý jiný úkol,
pomocí CPU bylo úplně dole. Úkol B přijde v čase T=100 a bude
zařazeny do fronty s nejvyšší prioritou. Vzhledem k tomu, že provozní doba je krátká,
dokončí se dříve, než dosáhne poslední fronty.

Z tohoto příkladu byste měli pochopit hlavní cíl algoritmu: protože algoritmus ne
zná dlouhý nebo krátký úkol, pak nejprve předpokládá, že úkol
krátký a dává mu nejvyšší prioritu. Pokud je to opravdu krátký úkol, tak
bude se provádět rychle, jinak pokud je to dlouhý úkol, bude se pohybovat pomalu
v prioritě dolů a brzy prokáže, že je to skutečně dlouhý úkol, který ne
vyžaduje odpověď.

Příklad 3: A co I/O?

Nyní se podívejme na příklad I/O. Jak je uvedeno v pravidle 4b,
pokud proces uvolní procesor, aniž by plně využil jeho čas procesoru,
pak zůstane na stejné úrovni priority. Smysl tohoto pravidla je poměrně jednoduchý.
- pokud interaktivní úloha provádí velké množství I/O, například čeká na
od uživatelské klávesy nebo stisknutí myši, takový úkol uvolní procesor
před přiděleným oknem. Neradi bychom vynechali takový prioritní úkol,
a tak zůstane na stejné úrovni.

Tento příklad ukazuje, jak by algoritmus pracoval s takovými procesy - interaktivní úloha B, která potřebuje CPU pouze 1 ms před provedením
I/O proces a dlouhá úloha A, která neustále využívá CPU.
MLFQ udržuje proces B na nejvyšší prioritě, jak pokračuje
uvolněte CPU. Pokud B je interaktivní úloha, pak algoritmus v tomto případě dosáhl
jeho účelem je rychlé spouštění interaktivních úloh.

Problémy se současným algoritmem MLFQ

V předchozích příkladech jsme sestavili základní verzi MLFQ. A zdá se, že on
dělá svou práci dobře a spravedlivě a spravedlivě rozděluje čas CPU mezi
dlouhé úkoly a umožňují krátké úkoly nebo úkoly, ke kterým je velký přístup
na I/O pro rychlé zpracování. Bohužel tento přístup obsahuje několik
vážné problémy.
Za prvé, Problém hladu: v případě, že systém bude mít mnoho interaktivních
úlohy, budou spotřebovávat veškerý čas CPU, a tedy ani jeden dlouhý
úkol nebude možné provést (hladoví).

Za druhéchytří uživatelé mohli psát své programy tak, aby
oklamat plánovače. Podvod spočívá v tom, že se něco dělá za účelem vynucení
plánovač dát procesu více času CPU. Algoritmus, že
popsaný výše je poměrně zranitelný vůči podobným útokům: před časovým oknem je prakticky
musíte provést I/O operaci (pro některé, bez ohledu na to, který soubor)
a tím uvolnit CPU. Takové chování vám umožní zůstat ve stejném
samotnou frontu a opět získat větší procento CPU času. Pokud je hotovo
je to správné (např. spustit 99 % času okna před uvolněním CPU),
takový úkol může jednoduše monopolizovat procesor.

Konečně, program může měnit své chování v průběhu času. Ty úkoly
který používal CPU se může stát interaktivní. V našem příkladu podobně
úkoly nebudou od plánovače náležitě ošetřeny, jako by to udělali ostatní
(původní) interaktivní úkoly.

Otázka pro publikum: jaké útoky na plánovač by mohly být provedeny v moderním světě?

Pokus 2: Zvyšte prioritu

Zkusme změnit pravidla a uvidíme, jestli se můžeme vyhnout problémům s
hladovění. Co můžeme udělat, abychom zajistili, že souvisí
Úlohy CPU dostanou svůj čas (i když ne dlouho).
Jako jednoduché řešení problému můžete pravidelně navrhovat
zvýšit prioritu všech takových úloh v systému. Existuje mnoho způsobů
abychom toho dosáhli, zkusme jako příklad implementovat něco jednoduchého: přeložit
všechny úkoly najednou s nejvyšší prioritou, proto nové pravidlo:

Rule5: Po určité době S přesunout všechny úkoly v systému do nejvyšší fronty.

Naše nové pravidlo řeší dva problémy najednou. Za prvé, procesy
zaručeně neumře hlady: úkoly v nejvyšší frontě se budou sdílet
čas procesoru podle algoritmu RR a tím všechny procesy obdrží
čas procesoru. Za druhé, pokud nějaký proces, který dříve používal
pouze procesor se stane interaktivním, zůstane ve frontě s nejvyšším
prioritu po obdržení zvýšení na nejvyšší prioritu jednou.
Zvažte příklad. V tomto scénáři zvažte použití jednoho procesu

CPU a dva interaktivní, krátké procesy. Obrázek vlevo na obrázku ukazuje chování bez zvýšení priority, a tak dlouho běžící úloha začne hladovět po příchodu dvou interaktivních úloh do systému. Na obrázku vpravo je každých 50 ms provedeno zvýšení priority, a tak je zaručeno, že všechny procesy obdrží procesorový čas a budou pravidelně spouštěny. 50 ms je v tomto případě bráno jako příklad, ve skutečnosti je toto číslo poněkud vyšší.
Je zřejmé, že přičtení periodické doby náběhu S vede k
logická otázka: jakou hodnotu nastavit? Jeden ze zasloužených
systémoví inženýři John Ousterhout označovali podobné veličiny v systémech jako voo-doo
konstantní, protože nějakým způsobem vyžadovaly černou magii pro správné
vystavení. A bohužel S má takovou příchuť. Pokud nastavíte hodnotu také
velké - dlouhé úkoly budou hladovět. A pokud to nastavíte příliš nízko,
interaktivní úlohy nebudou dostávat správný čas procesoru.

Pokus 3: Lepší účetnictví

Nyní musíme vyřešit ještě jeden problém: jak ne
dovolit podvádět náš plánovač? Viníci této možnosti jsou
pravidla 4a, 4b, která umožňují úloze zachovat si prioritu uvolněním procesoru
před uplynutím stanoveného času. Jak se s tím vypořádat?
Za řešení lze v tomto případě považovat lepší účtování CPU času na každém
úroveň MLFQ. Místo toho, abyste zapomněli na čas, který program použil
procesor pro přidělený interval, měli byste jej vzít v úvahu a uložit. Po
proces vyčerpal svůj přidělený čas, měl by být degradován na další
úroveň priority. Nyní nezáleží na tom, jak proces využije svůj čas – jak
neustále počítá na procesoru nebo jako sadu volání. Tím pádem,
pravidlo 4 by mělo být přepsáno takto:

Rule4: Poté, co úloha vyčerpá svůj přidělený čas v aktuální frontě (bez ohledu na to, kolikrát uvolnila CPU), priorita takové úlohy se sníží (postoupí ve frontě dolů).

Podívejme se na příklad:
»

Obrázek ukazuje, co se stane, když se pokusíte oklamat plánovač
pokud by to bylo s předchozími pravidly 4a, 4b by byl výsledek vlevo. S novým
pravidlo je, že výsledek je vpravo. Před ochranou mohl jakýkoli proces volat I/O před dokončením a
tak ovládnou CPU, po povolení ochrany, bez ohledu na chování
I/O, bude stále klesat ve frontě, a tak nebude moci nepoctivě
převzít prostředky CPU.

Zlepšení MLFQ a další problémy

S výše uvedenými vylepšeními vyvstávají nové problémy: jeden z hlavních
otázky - jak parametrizovat takový plánovač? Tito. Kolik by mělo být
fronty? Jaká by měla být velikost okna programu ve frontě? Jak
program by měl být často upřednostňován, aby se zabránilo hladovění a
vzít v úvahu změnu v chování programu? Na tyto otázky není nic jednoduchého
odezvy a pouze experimentuje se zátěží a následnou konfigurací
plánovač může vést k určité uspokojivé rovnováze.

Například většina implementací MLFQ umožňuje přiřadit různé
časové úseky pro různé fronty. Fronty s vysokou prioritou jsou obvykle
jsou předepsány krátké intervaly. Tyto fronty se skládají z interaktivních úkolů,
přepínání mezi nimi je poměrně citlivé a mělo by trvat 10 nebo méně
slečna. Naproti tomu fronty s nízkou prioritou se skládají z dlouho běžících úloh, které používají
PROCESOR. A v tomto případě velmi dobře sedí dlouhé časové intervaly (100 ms).

V tomto příkladu existují 2 úlohy, které pracovaly ve frontě s vysokou prioritou 20
ms, rozdělené do oken po 10 ms. 40 ms ve střední frontě (okno 20 ms) a v nízké prioritě
časové okno fronty bylo 40 ms, kde úkoly dokončily svou práci.

Implementace MLFQ v OS Solaris je třída plánovačů pro sdílení času.
Plánovač poskytne sadu tabulek, které definují přesně tak, jak by měly
změnit prioritu procesu v průběhu jeho životnosti, jaká by měla být velikost
okno, které má být přiděleno, a jak často zvyšovat priority úkolů. Správce
systém může interagovat s touto tabulkou a přimět plánovač, aby se choval
jinak. Ve výchozím nastavení má tato tabulka 60 front s postupným nárůstem
velikost okna od 20 ms (vysoká priorita) do několika stovek ms (nejnižší priorita) a
také s boostem všech úkolů jednou za sekundu.

Jiné plánovače MLFQ nepoužívají tabulku ani nic specifického
pravidla, která jsou popsána v této kapitole, naopak počítají priority pomocí
matematické vzorce. Například plánovač ve FreeBSD používá vzorec pro
výpočet aktuální priority úkolu na základě toho, jak moc proces probíhá
používal CPU. Navíc využití CPU časem hnije a tím pádem
Zvyšování priority tedy probíhá poněkud jinak, než je popsáno výše. To je pravda
tzv. decay algoritmy. Od verze 7.1 používá FreeBSD plánovač ULE.

Konečně, mnoho plánovačů má další funkce. Například některé
plánovače rezervují vyšší úrovně pro provoz operačního systému a tím
Žádný uživatelský proces tedy nemůže získat nejvyšší prioritu
Systém. Některé systémy umožňují poskytovat rady, které vám pomohou
plánovač správně stanovit priority. Například pomocí příkazu pěkný
můžete zvýšit nebo snížit prioritu úkolu a tím zvýšit nebo snížit
snížit šance programu na čas CPU.

MLFQ: Shrnutí

Popsali jsme plánovací přístup nazvaný MLFQ. Jeho jméno
uzavřený v principu fungování - má několik front a využívá zpětnou vazbu
upřednostnit úkol.
Konečná podoba pravidel bude následující:

Rule1: Pokud priorita(A) > Priorita(B), úloha A se spustí (B ne)
Rule2: Pokud priorita(A) = Priorita(B), A&B se spustí pomocí RR
Rule3: Když úloha vstoupí do systému, je umístěna do fronty s nejvyšší prioritou.
Rule4: Poté, co úloha vyčerpá svůj přidělený čas v aktuální frontě (bez ohledu na to, kolikrát uvolnila CPU), priorita takové úlohy se sníží (postoupí ve frontě dolů).
Rule5: Po určité době S přesunout všechny úkoly v systému do nejvyšší fronty.

MLFQ je zajímavé z následujícího důvodu – místo toho, aby vyžadovalo znalosti o
povaze úlohy předem, algoritmus se učí minulé chování úlohy a sad
priority podle toho. Snaží se tedy sedět na dvou židlích najednou – dosáhnout produktivity u malých úkolů (SJF, STCF) a poctivě běhat dlouho,
Úlohy zatěžující CPU. Proto mnoho systémů, včetně BSD a jejich derivátů,
Solaris, Windows, Mac používají jako plánovač nějakou formu algoritmu
MLFQ jako základ.

Další materiály:

Zdroj: www.habr.com

Operační systémy: Tři snadné kusy. Část 5: Plánování: Víceúrovňová fronta zpětné vazby (překlad)