Uvod u operacijske sustave
Hej Habr! Predstavljam vam seriju članaka-prijevoda jedne po meni zanimljive literature - OSTEP. Ovaj materijal prilično duboko raspravlja o radu operativnih sustava nalik unixu, naime o radu s procesima, raznim planerima, memorijom i drugim sličnim komponentama koje čine moderan OS. Izvornike svih materijala možete vidjeti ovdje . Napominjem da je prijevod urađen neprofesionalno (sasvim slobodno), ali se nadam da sam zadržao opći smisao.
Laboratorijske radove iz ove teme možete pronaći ovdje:
Ostali dijelovi:
Također možete pogledati moj kanal na =)
Uvod u Planer
Bit problema: Kako razviti politiku rasporeda
Kako bi trebali biti dizajnirani temeljni okviri politike raspoređivača? Koje bi trebale biti ključne pretpostavke? Koja su mjerila važna? Koje su se osnovne tehnike koristile u ranim računalnim sustavima?
Pretpostavke o radnom opterećenju
Prije rasprave o mogućim politikama, napravimo nekoliko pojednostavljenih digresija o procesima koji se izvode u sustavu, a koji se zajednički nazivaju radno opterećenje. Definiranje radnog opterećenja kritični je dio izrade politika, a što više znate o radnom opterećenju, bolju politiku možete napisati.
Napravimo sljedeće pretpostavke o procesima koji se izvode u sustavu, ponekad se također nazivaju poslovi (zadaci). Gotovo sve ove pretpostavke nisu realne, ali su neophodne za razvoj misli.
- Svaki zadatak traje isto vrijeme,
- Svi zadaci se postavljaju istovremeno,
- Dodijeljeni zadatak radi do završetka,
- Svi zadaci koriste samo CPU,
- Poznato je vrijeme izvođenja svakog zadatka.
Metrike planera
Uz neke pretpostavke o opterećenju, potreban je još jedan alat za usporedbu različitih pravila raspoređivanja: metrika raspoređivača. Mjerni podatak je samo neka mjera nečega. Postoji niz metrika koje se mogu koristiti za usporedbu planera.
Na primjer, koristit ćemo metriku tzv Vrijeme obrade (Vrijeme obrade). Vrijeme obrade zadatka definirano je kao razlika između vremena završetka zadatka i vremena dolaska zadatka u sustav.
Tturnaround=Tcompletion-Tarrival
Budući da smo pretpostavili da su svi zadaci stigli u isto vrijeme, tada je Ta=0, a time i Tt=Tc. Ova vrijednost će se prirodno promijeniti kada promijenimo gornje pretpostavke.
Još jedna metrika - poštenje (pravednost, poštenje). Produktivnost i pravednost često su suprotne karakteristike u planiranju. Na primjer, planer može optimizirati performanse, ali po cijenu čekanja da se drugi zadaci pokrenu, čime se smanjuje pravednost.
PRVI UĐE PRVI IZLAZI (FIFO)
Najosnovniji algoritam koji možemo implementirati zove se FIFO ili prvi došao (ušao), prvi poslužen (izašao). Ovaj algoritam ima nekoliko prednosti: vrlo ga je lako implementirati i odgovara svim našim pretpostavkama te prilično dobro obavlja posao.
Pogledajmo jednostavan primjer. Recimo da su 3 zadatka postavljena istovremeno. Ali pretpostavimo da je zadatak A stigao malo ranije od svih ostalih, pa će se pojaviti na popisu izvršenja ranije od ostalih, baš kao i B u odnosu na C. Pretpostavimo da će svaki od njih biti izvršen 10 sekundi. Koje će biti prosječno vrijeme za obavljanje ovih zadataka u ovom slučaju?
Brojanjem vrijednosti - 10+20+30 i dijeljenjem s 3, dobivamo prosječno vrijeme izvršenja programa jednako 20 sekundi.
Pokušajmo sada promijeniti naše pretpostavke. Konkretno, pretpostavka 1 i stoga više nećemo pretpostavljati da je za izvršenje svakog zadatka potrebno isto vrijeme. Kako će se ovaj put pokazati FIFO?
Kako se pokazalo, različita vremena izvršenja zadatka imaju izrazito negativan utjecaj na produktivnost FIFO algoritma. Pretpostavimo da će zadatku A trebati 100 sekundi da se izvrši, dok će B i C ipak trebati po 10 sekundi.
Kao što se može vidjeti sa slike, prosječno vrijeme za sustav bit će (100+110+120)/3=110. Ovaj efekt se zove učinak konvoja, kada će neki kratkoročni potrošači resursa stati u red nakon velikog potrošača. To je kao red u trgovini kada ispred vas stoji kupac s punim kolicima. Najbolje rješenje problema je pokušati promijeniti kasu ili se opustiti i duboko disati.
Prvo najkraći posao
Je li moguće nekako riješiti sličnu situaciju s teškim procesima? Sigurno. Druga vrsta planiranja je tzvPrvo najkraći posao (SJF). Njegov algoritam je također prilično primitivan - kao što ime implicira, najkraći zadaci će se pokrenuti prvi, jedan za drugim.
U ovom primjeru, rezultat pokretanja istih procesa bit će poboljšanje prosječnog vremena obrade programa i ono će biti jednako 50 umjesto 110, što je gotovo 2 puta bolje.
Dakle, za zadanu pretpostavku da svi zadaci stižu u isto vrijeme, SJF algoritam se čini najoptimalnijim algoritmom. Međutim, naše se pretpostavke još uvijek ne čine realnima. Ovaj put mijenjamo pretpostavku 2 i ovaj put zamislimo da zadaci mogu biti prisutni u bilo koje vrijeme, a ne svi u isto vrijeme. Do kakvih problema to može dovesti?
Zamislimo da zadatak A (100c) prvi stigne i počne se izvršavati. U t=10 stižu zadaci B i C od kojih će svaki trajati 10 sekundi. Dakle, prosječno vrijeme izvršenja je (100+(110-10)+(120-10))3 = 103. Što bi planer mogao učiniti da to poboljša?
Prvo najkraće vrijeme do završetka (STCF)
Kako bismo poboljšali situaciju, izostavljamo pretpostavku 3 da je program pokrenut i radi do završetka. Osim toga, trebat ćemo hardversku podršku i, kao što pretpostavljate, koristit ćemo je brojač prekinuti zadatak koji se izvodi i prebacivanje konteksta. Dakle, planer može u trenutku dolaska zadataka B, C učiniti nešto - zaustaviti izvršavanje zadatka A i staviti zadatke B i C u obradu te po njihovom završetku nastaviti s izvršavanjem procesa A. Takav planer se zove STCFili Preventivni posao prvi.
Rezultat ovog planera bit će sljedeći rezultat: ((120-0)+(20-10)+(30-10))/3=50. Stoga takav planer postaje još optimalniji za naše zadatke.
Metričko vrijeme odziva
Dakle, ako znamo vrijeme izvođenja zadataka i da ti zadaci koriste samo CPU, STCF će biti najbolje rješenje. I jednom u ranim vremenima, ti su algoritmi radili prilično dobro. Međutim, korisnik sada većinu svog vremena provodi na terminalu i očekuje produktivno interaktivno iskustvo. Tako je rođena nova metrika - vrijeme odziva (odgovor).
Vrijeme odgovora izračunava se na sljedeći način:
Response=Tfirstrun−Tarrival
Dakle, za prethodni primjer, vrijeme odgovora će biti: A=0, B=0, C=10 (abg=3,33).
I pokazalo se da STCF algoritam nije tako dobar u situaciji kada stignu 3 zadatka u isto vrijeme - morat će pričekati dok se mali zadaci potpuno ne izvrše. Dakle, algoritam je dobar za metriku vremena obrade, ali loš za metriku interaktivnosti. Zamislite da sjedite za terminalom i pokušavate upisati znakove u editor i morate čekati više od 10 sekundi jer neki drugi zadatak zauzima CPU. Nije baš ugodno.
Dakle, suočeni smo s još jednim problemom - kako možemo izgraditi planer koji je osjetljiv na vrijeme odziva?
Razigravanje
Za rješavanje ovog problema razvijen je algoritam Razigravanje (RR). Osnovna ideja je vrlo jednostavna: umjesto izvršavanja zadataka dok se ne dovrše, pokrenut ćemo zadatak određeno vremensko razdoblje (zvano vremenski odsječak), a zatim se prebaciti na drugi zadatak iz reda čekanja. Algoritam ponavlja svoj rad dok se svi zadaci ne završe. U tom slučaju vrijeme izvođenja programa mora biti višekratnik vremena nakon kojeg će tajmer prekinuti proces. Na primjer, ako mjerač vremena prekine proces svakih x=10 ms, tada bi veličina prozora izvršenja procesa trebala biti višekratnik broja 10 i biti 10,20, 10 ili x*XNUMX.
Pogledajmo primjer: ABC zadaci stižu istovremeno u sustav i svaki od njih želi se izvoditi 5 sekundi. SJF algoritam dovršit će svaki zadatak prije pokretanja drugog. Nasuprot tome, RR algoritam s prozorom pokretanja = 1 s proći će kroz zadatke kako slijedi (Sl. 4.3):
(Opet SJF (loše za vrijeme odziva)
(Round Robin (dobro za vrijeme odziva)
Prosječno vrijeme odziva za RR algoritam je (0+1+2)/3=1, dok je za SJF (0+5+10)/3=5.
Logično je pretpostaviti da je vremenski prozor vrlo važan parametar za RR; što je on manji, to je vrijeme odziva veće. Međutim, ne biste ga trebali učiniti premalim jer će vrijeme promjene konteksta također igrati ulogu u ukupnoj izvedbi. Dakle, odabir vremena prozora izvršavanja postavlja OS arhitekt i ovisi o zadacima koji se planiraju izvršiti u njemu. Prebacivanje konteksta nije jedina servisna operacija koja gubi vrijeme - pokrenuti program radi na puno drugih stvari, na primjer, razne predmemorije, a sa svakim prebacivanjem potrebno je spremiti i vratiti ovo okruženje, što također može oduzeti puno vrijeme.
RR je izvrstan planer ako govorimo samo o metrici vremena odziva. Ali kako će se metrika vremena izvršenja zadatka ponašati s ovim algoritmom? Razmotrite gornji primjer, kada je vrijeme rada A, B, C = 5 s i stižu u isto vrijeme. Zadatak A završit će u 13, B u 14, C u 15 s, a prosječno vrijeme obrade bit će 14 s. Stoga je RR najlošiji algoritam za metriku prometa.
Općenitije rečeno, bilo koji algoritam tipa RR je pošten; on jednako dijeli CPU vrijeme između svih procesa. Zbog toga se ove metrike stalno međusobno sukobljavaju.
Dakle, imamo nekoliko suprotnih algoritama, au isto vrijeme ostaje još nekoliko pretpostavki - da je vrijeme zadatka poznato i da zadatak koristi samo CPU.
Miješanje s I/O
Prije svega, uklonimo pretpostavku 4 da proces koristi samo CPU; naravno, to nije slučaj i procesi mogu pristupiti drugoj opremi.
U trenutku kada bilo koji proces zatraži I/O operaciju, proces ulazi u blokirano stanje, čekajući da se I/O završi. Ako se I/O šalje na tvrdi disk, tada takva operacija može trajati do nekoliko ms ili dulje, a procesor će u ovom trenutku biti u stanju mirovanja. Za to vrijeme planer može zauzeti procesor bilo kojim drugim procesom. Sljedeća odluka koju planer mora donijeti je kada će proces završiti svoj I/O. Kada se to dogodi, dogodit će se prekid i OS će proces koji je pozvao I/O staviti u stanje pripravnosti.
Pogledajmo primjer nekoliko zadataka. Svaki od njih zahtijeva 50 ms CPU vremena. Međutim, prvi će pristupati I/O svakih 10 ms (koji će se također izvršavati svakih 10 ms). A proces B jednostavno koristi procesor od 50 ms bez I/O.
U ovom primjeru koristit ćemo STCF planer. Kako će se planer ponašati ako se na njemu pokrene proces poput A? Učinit će sljedeće: prvo će u potpunosti razraditi proces A, a zatim proces B.
Tradicionalni pristup rješavanju ovog problema je tretiranje svakog podzadatka od 10 ms procesa A kao zasebnog zadatka. Dakle, kada se počinje sa STJF algoritmom, očit je izbor između zadatka od 50 ms i zadatka od 10 ms. Zatim, kada se podzadatak A završi, pokrenut će se proces B i I/O. Nakon završetka I/O-a, uobičajeno je da se ponovno pokrene proces A od 10 ms umjesto procesa B. Na ovaj način moguće je implementirati preklapanje, gdje CPU koristi drugi proces dok prvi čeka na I/O. Kao rezultat toga, sustav je bolje iskorišten - u trenutku kada interaktivni procesi čekaju I/O, drugi procesi se mogu izvršavati na procesoru.
Oraclea više nema
Pokušajmo se sada osloboditi pretpostavke da je vrijeme izvođenja zadatka poznato. Ovo je općenito najgora i najnerealnija pretpostavka na cijelom popisu. U stvari, u prosječnom običnom OS-u, sam OS obično zna vrlo malo o vremenu izvršavanja zadataka, pa kako onda možete izgraditi planer bez znanja koliko dugo će zadatak trebati da se izvrši? Možda bismo mogli upotrijebiti neke RR principe da riješimo ovaj problem?
Ukupan
Pogledali smo osnovne ideje raspoređivanja zadataka i pogledali 2 obitelji planera. Prvi prvi pokreće najkraći zadatak i time povećava vrijeme obrade, dok je drugi ravnomjerno raspoređen između svih zadataka, povećavajući vrijeme odgovora. Oba algoritma su loša tamo gdje su algoritmi druge obitelji dobri. Također smo pogledali kako paralelna upotreba CPU-a i I/O-a može poboljšati performanse, ali nismo riješili problem s OS vidovitošću. A u sljedećoj lekciji ćemo pogledati planer koji gleda u neposrednu prošlost i pokušava predvidjeti budućnost. I to se zove višerazinski red povratnih informacija.
Izvor: www.habr.com