Uvod u operativne sisteme
Hej Habr! Skrećem vam pažnju na seriju članaka-prevoda jedne po meni zanimljive literature - OSTEP. U ovom materijalu se prilično duboko raspravlja o radu operativnih sistema sličnih unixu, odnosno radu sa procesima, raznim planerima, memorijom i drugim sličnim komponentama koje čine moderni OS. Original svih materijala možete pogledati ovdje . Napominjemo da je prevod urađen neprofesionalno (prilično slobodno), ali se nadam da sam zadržao opšte značenje.
Laboratorijski rad na ovu temu možete pronaći ovdje:
Ostali dijelovi:
Takođe možete pogledati moj kanal na =)
Uvod u Scheduler
Suština problema: Kako razviti politiku planera
Kako treba osmisliti temeljne okvire politike planera? Koje bi trebale biti ključne pretpostavke? Koje su metrike važne? Koje su osnovne tehnike korišćene u ranim računarskim sistemima?
Pretpostavke radnog opterećenja
Prije diskusije o mogućim politikama, hajde da prvo napravimo nekoliko pojednostavljenih digresija o procesima koji se pokreću u sistemu, koji se zajednički nazivaju opterećenje. Definiranje radnog opterećenja je kritičan dio izgradnje politika, i što više znate o radnom opterećenju, to bolje politike možete napisati.
Hajde da napravimo sljedeće pretpostavke o procesima koji se pokreću u sistemu, koji se ponekad nazivaju radna mjesta (zadaci). Gotovo sve ove pretpostavke nisu realne, ali su neophodne za razvoj misli.
- Svaki zadatak radi isto vrijeme,
- Svi zadaci se postavljaju istovremeno,
- Dodijeljeni zadatak radi do njegovog završetka,
- Svi zadaci koriste samo CPU,
- Vrijeme rada svakog zadatka je poznato.
metrika planera
Pored nekih pretpostavki o opterećenju, potreban je još jedan alat za poređenje različitih politika planiranja: metrika planera. metrika je samo neka mjera nečega. Postoji niz metrika koje se mogu koristiti za poređenje planera.
Na primjer, koristit ćemo metriku tzv vrijeme preokreta (vrijeme obrta). Vrijeme obrade zadatka definira se kao razlika između vremena završetka zadatka i vremena dolaska zadatka u sistem.
Tturnaround=Tcompletion−Tarrival
Pošto smo pretpostavili da su svi zadaci stigli u isto vrijeme, tada je Ta=0 i time Tt=Tc. Ova vrijednost će se prirodno promijeniti kada promijenimo gornje pretpostavke.
Još jedna metrika - pravednost (pravednost, poštenje). Produktivnost i pravičnost su često suprotne karakteristike u planiranju. Na primjer, planer može optimizirati performanse, ali po cijenu čekanja da se drugi zadaci pokrenu, čime se smanjuje pravičnost.
PRVI ULAZIO PRVI OUT (FIFO)
Najosnovniji algoritam koji možemo implementirati zove se FIFO ili prvi dolazi (ulazi), prvi servira (izlazi). Ovaj algoritam ima nekoliko prednosti: vrlo je jednostavan za implementaciju i uklapa se u sve naše pretpostavke i radi posao prilično dobro.
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 listi izvršenja ranije od ostalih, baš kao B u odnosu na C. Pretpostavimo da će se svaki od njih izvršiti 10 sekundi. Koliko će biti prosječno vrijeme za obavljanje ovih zadataka u ovom slučaju?
Prebrojavanjem vrijednosti - 10+20+30 i dijeljenjem sa 3, dobijamo prosječno vrijeme izvršavanja programa jednako 20 sekundi.
Pokušajmo sada promijeniti naše pretpostavke. Konkretno, pretpostavka 1 i stoga više nećemo pretpostavljati da je svakom zadatku potrebno isto vrijeme za izvršenje. Kako će se FIFO ponašati ovog puta?
Kako se ispostavilo, različita vremena izvršavanja zadataka imaju izuzetno negativan uticaj na produktivnost FIFO algoritma. Pretpostavimo da će zadatku A biti potrebno 100 sekundi da se završi, dok će B i C i dalje trebati po 10 sekundi.
Kao što se može vidjeti sa slike, prosječno vrijeme za sistem će biti (100+110+120)/3=110. Ovaj efekat se zove efekat konvoja, kada će neki kratkoročni potrošači resursa stajati u redu za velikim potrošačem. To je kao u redu u trgovini kada je ispred vas mušterija s punom kolicima. Najbolje rješenje problema je pokušati promijeniti kasu ili se opustiti i duboko disati.
Najkraći posao prvi
Je li moguće nekako riješiti sličnu situaciju sa teškim procesima? Svakako. Druga vrsta planiranja se zoveNajkraći posao prvi (SJF). Njegov algoritam je također prilično primitivan - kao što ime govori, najkraći zadaci će se pokretati prvi, jedan za drugim.
U ovom primjeru, rezultat pokretanja istih procesa će biti poboljšanje u prosječnom vremenu obrta programa i ono će biti jednako 50 umjesto 110, što je skoro 2 puta bolje.
Dakle, za datu pretpostavku da svi zadaci stižu u isto vrijeme, SJF algoritam se čini najoptimalnijim algoritamom. Međutim, naše pretpostavke i dalje ne izgledaju realno. Ovaj put mijenjamo pretpostavku 2 i ovaj put zamislimo da zadaci mogu biti prisutni u bilo kojem trenutku, a ne svi istovremeno. Do kojih problema to može dovesti?
Zamislimo da zadatak A (100c) stigne prvi i počne da se izvršava. U t=10 stižu zadaci B i C, od kojih će svaki trajati 10 sekundi. Dakle, prosečno vreme izvršenja je (100+(110-10)+(120-10))3 = 103. Šta bi planer mogao da uradi da ovo poboljša?
Najkraće vrijeme do prvog završetka (STCF)
Da bismo poboljšali situaciju, izostavljamo pretpostavku 3 da je program pokrenut i da traje do završetka. Osim toga, trebat će nam hardverska podrška i, kao što možete pretpostaviti, koristit ćemo je timer da biste prekinuli pokrenuti zadatak i prebacivanje konteksta. Dakle, planer može učiniti nešto u trenutku kada zadaci B, C stignu - zaustaviti izvršavanje zadatka A i staviti zadatke B i C u obradu i, nakon njihovog završetka, nastaviti izvršavanje procesa A. Takav planer se zove STCFili Preventivni posao prvo.
Rezultat ovog planera će biti sljedeći rezultat: ((120-0)+(20-10)+(30-10))/3=50. Dakle, takav planer postaje još optimalniji za naše zadatke.
Metričko vrijeme odziva
Dakle, ako znamo vrijeme izvršavanja zadataka i da ti zadaci koriste samo CPU, STCF će biti najbolje rješenje. I jednom u ranim vremenima, ovi algoritmi su 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 odziva se izračunava na sljedeći način:
Tresponse=Tfirstrun−Tarrival
Dakle, za prethodni primjer, vrijeme odgovora će biti: A=0, B=0, C=10 (abg=3,33).
I ispostavilo se da STCF algoritam nije tako dobar u situaciji kada 3 zadatka stižu u isto vrijeme - morat će pričekati dok se mali zadaci potpuno ne završe. Dakle, algoritam je dobar za metriku vremena obrta, 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 je neki drugi zadatak zauzimao CPU. Nije baš prijatno.
Dakle, suočeni smo sa drugim problemom - kako možemo napraviti planer koji je osjetljiv na vrijeme odgovora?
Round Robins
Razvijen je algoritam za rješavanje ovog problema Round Robins (RR). Osnovna ideja je prilično jednostavna: umjesto pokretanja zadataka dok se ne završe, mi ćemo pokrenuti zadatak u određenom vremenskom periodu (koji se naziva 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 ovom slučaju, vrijeme rada programa mora biti višestruko od vremena nakon kojeg će tajmer prekinuti proces. Na primjer, ako tajmer prekida proces svakih x=10ms, tada bi veličina prozora za izvršavanje procesa trebala biti višestruka od 10 i biti 10,20 ili x*10.
Pogledajmo primjer: ABC zadaci stižu istovremeno u sistem i svaki od njih želi da se pokrene 5 sekundi. SJF algoritam će završiti svaki zadatak prije nego što započne drugi. Nasuprot tome, RR algoritam sa prozorom za lansiranje = 1s će proći kroz zadatke kako slijedi (slika 4.3):
(SJF opet (loše za vrijeme odziva)
(Round Robin (dobro za vrijeme odgovora)
Prosečno vreme 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 okvir vrlo važan parametar za RR; što je manji, to je vrijeme odgovora veće. Međutim, ne biste ga trebali činiti premalim, jer će vrijeme promjene konteksta također igrati ulogu u ukupnim performansama. Dakle, izbor vremena izvršavanja prozora postavlja arhitekta OS-a i zavisi od zadataka koji se planiraju u njemu izvršiti. Prebacivanje konteksta nije jedina servisna operacija koja gubi vrijeme - pokrenuti program radi na puno drugih stvari, na primjer, razne keš memorije, a sa svakim prekidačem potrebno je sačuvati i vratiti ovo okruženje, što također može potrajati vrijeme.
RR je odličan planer ako govorimo samo o metrici vremena odgovora. Ali kako će se metrika vremena preokreta zadatka ponašati s ovim algoritmom? Razmotrimo gornji primjer, kada je vrijeme rada A, B, C = 5s i dolazi u isto vrijeme. Zadatak A će se završiti u 13, B u 14, C u 15 sekundi, a prosječno vrijeme preokreta će biti 14 sekundi. Dakle, RR je najgori algoritam za metriku prometa.
Općenito govoreći, bilo koji algoritam tipa RR je fer; dijeli CPU vrijeme na sve procese. I stoga, ove metrike su u stalnom sukobu jedna s drugom.
Dakle, imamo nekoliko suprotstavljenih algoritama, a istovremeno ostaje još nekoliko pretpostavki - da je vrijeme zadatka poznato i da zadatak koristi samo CPU.
Miješanje sa I/O
Prije svega, otklonimo 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 pošalje na tvrdi disk, tada takva operacija može potrajati do nekoliko ms ili duže, a procesor će u ovom trenutku biti neaktivan. Tokom ovog vremena, planer može zauzeti procesor bilo kojim drugim procesom. Sljedeća odluka koju će planer morati donijeti je kada će proces završiti svoj I/O. Kada se to dogodi, doći će do prekida i OS će proces koji je pozvao I/O staviti u stanje spremnosti.
Pogledajmo primjer nekoliko zadataka. Svaki od njih zahtijeva 50ms CPU vremena. Međutim, prvi će pristupiti I/O svakih 10ms (koji će se također izvršavati svakih 10ms). A proces B jednostavno koristi procesor od 50 ms bez I/O.
U ovom primjeru ćemo koristiti STCF planer. Kako će se ponašati planer ako se na njemu pokrene proces poput A? On će učiniti sljedeće: prvo će u potpunosti razraditi proces A, a zatim proces B.
Tradicionalni pristup rješavanju ovog problema je da se svaki podzadatak od 10 ms procesa A tretira kao poseban zadatak. Dakle, kada se počne sa STJF algoritmom, izbor između zadatka od 50 ms i zadatka od 10 ms je očigledan. Zatim, kada je podzadatak A završen, proces B i I/O će biti pokrenuti. Nakon što se I/O završi, biće uobičajeno da se ponovo pokrene 10ms proces A umjesto procesa B. Na ovaj način moguće je implementirati preklapanje, gdje CPU koristi drugi proces dok prvi čeka na I/O. I kao rezultat, sistem je bolje iskorišćen – u trenutku kada interaktivni procesi čekaju na I/O, drugi procesi se mogu izvršiti na procesoru.
Oracle više ne postoji
Sada pokušajmo da se riješimo pretpostavke da je vrijeme izvršavanja zadatka poznato. Ovo je općenito najgora i najnerealnija pretpostavka na cijeloj listi. 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 napraviti planer, a da ne znate koliko dugo će zadatku biti potrebno da se izvrši? Možda bismo mogli koristiti neke RR principe da riješimo ovaj problem?
Rezultat
Pogledali smo osnovne ideje planiranja zadataka i pogledali 2 porodice planera. Prvi prvi započinje najkraći zadatak i time povećava vrijeme preokreta, dok se drugi jednako razdire između svih zadataka, povećavajući vrijeme odgovora. Oba algoritma su loša tamo gdje su algoritmi druge porodice dobri. Također smo pogledali kako paralelna upotreba CPU-a i I/O-a može poboljšati performanse, ali nismo riješili problem sa vidovitošću OS-a. A u sledećoj lekciji ćemo pogledati planera koji gleda u neposrednu prošlost i pokušava da predvidi budućnost. I to se zove red za povratne informacije na više nivoa.
izvor: www.habr.com