Uvod v operacijske sisteme
Hej Habr! Rad bi vam predstavil serijo člankov-prevodov ene po mojem mnenju zanimive literature - OSTEP. To gradivo precej poglobljeno obravnava delo operacijskih sistemov, podobnih unixu, in sicer delo s procesi, različnimi načrtovalci, pomnilnikom in drugimi podobnimi komponentami, ki sestavljajo sodoben OS. Original vseh materialov si lahko ogledate tukaj . Upoštevajte, da je prevod narejen neprofesionalno (precej svobodno), vendar upam, da sem ohranil splošni pomen.
Laboratorijske naloge na to temo najdete tukaj:
Drugi deli:
Ogledate si lahko tudi moj kanal na =)
Uvod v razporejevalnik
Bistvo problema: Kako razviti politiko razporejevalnika
Kako naj bodo zasnovani temeljni okviri politik razporejevalnika? Katere bi morale biti ključne predpostavke? Katere meritve so pomembne? Katere osnovne tehnike so bile uporabljene v zgodnjih računalniških sistemih?
Predpostavke o delovni obremenitvi
Preden razpravljamo o možnih politikah, najprej naredimo nekaj poenostavljenih digresij o procesih, ki se izvajajo v sistemu, ki se skupaj imenujejo delovna obremenitev. Opredelitev delovne obremenitve je kritičen del gradnje pravilnikov in več kot veste o delovni obremenitvi, boljši pravilnik lahko napišete.
Naredimo naslednje predpostavke o procesih, ki se izvajajo v sistemu, včasih tudi imenovani delovna mesta (naloge). Skoraj vse te predpostavke niso realne, so pa nujne za razvoj misli.
- Vsaka naloga se izvaja enako dolgo,
- Vse naloge so postavljene hkrati,
- Dodeljena naloga dela do zaključka,
- Vse naloge uporabljajo samo CPE,
- Čas izvajanja posamezne naloge je znan.
Meritve razporejevalnika
Poleg nekaterih predpostavk o obremenitvi je potrebno še eno orodje za primerjavo različnih politik razporejanja: meritve razporejevalnika. Merilo je le nekaj merila nečesa. Obstaja več meritev, ki jih je mogoče uporabiti za primerjavo razporejevalcev.
Na primer, uporabili bomo metriko, imenovano čas preobrata (čas obrabe). Obdelovalni čas naloge je definiran kot razlika med časom dokončanja naloge in časom prihoda naloge v sistem.
Tturnaround=Tcompletion-Tarrival
Ker smo predpostavili, da so vse naloge prispele istočasno, potem je Ta=0 in s tem Tt=Tc. Ta vrednost se bo seveda spremenila, ko bomo spremenili zgornje predpostavke.
Druga metrika - pravičnost (pravičnost, poštenost). Produktivnost in pravičnost sta pogosto nasprotujoči si lastnosti pri načrtovanju. Na primer, razporejevalnik lahko optimizira zmogljivost, vendar za ceno čakanja na izvajanje drugih nalog, s čimer se zmanjša pravičnost.
FIRST IN FIRST OUT (FIFO)
Najosnovnejši algoritem, ki ga lahko implementiramo se imenuje FIFO oz prvi pride (vstopi), prvi melje (ven). Ta algoritem ima več prednosti: zelo enostaven je za implementacijo in ustreza vsem našim predpostavkam ter precej dobro opravi delo.
Poglejmo preprost primer. Recimo, da so bile hkrati postavljene 3 naloge. Toda predpostavimo, da je naloga A prispela malo prej kot vse ostale, zato se bo pojavila na seznamu izvajanja prej kot druge, tako kot B glede na C. Predpostavimo, da se bo vsaka od njih izvajala 10 sekund. Kakšen bo povprečni čas za dokončanje teh nalog v tem primeru?
S štetjem vrednosti - 10+20+30 in deljenjem s 3 dobimo povprečni čas izvajanja programa, ki je enak 20 sekundam.
Zdaj pa poskusimo spremeniti naše predpostavke. Predvsem predpostavka 1, zato ne bomo več predvidevali, da vsaka naloga za izvedbo potrebuje enako količino časa. Kako se bo tokrat obnesel FIFO?
Kot se je izkazalo, različni časi izvajanja nalog izjemno negativno vplivajo na produktivnost algoritma FIFO. Predpostavimo, da bo opravilo A trajalo 100 sekund, medtem ko bosta opravili B in C še vedno potrebovali po 10 sekund.
Kot je razvidno iz slike, bo povprečni čas za sistem (100+110+120)/3=110. Ta učinek se imenuje učinek konvoja, ko bodo nekateri kratkoročni porabniki vira stali v čakalni vrsti za velikim porabnikom. To je kot vrsta v trgovini, ko je pred vami stranka s polnim vozičkom. Najboljša rešitev težave je, da poskusite zamenjati blagajno ali pa se sprostite in globoko dihajte.
Najprej najkrajša naloga
Ali je mogoče podobno situacijo nekako rešiti s težkimi procesi? Vsekakor. Druga vrsta načrtovanja se imenujeNajprej najkrajša naloga (SJF). Njegov algoritem je tudi precej primitiven - kot že ime pove, se bodo najprej zagnale najkrajše naloge, ena za drugo.
V tem primeru bo rezultat izvajanja istih procesov izboljšanje povprečnega časa izvajanja programa in bo enak 50 namesto 110, kar je skoraj 2-krat bolje.
Tako se ob dani predpostavki, da vse naloge prispejo istočasno, zdi algoritem SJF najbolj optimalen algoritem. Vendar se naše domneve še vedno ne zdijo realne. Tokrat spremenimo predpostavko 2 in si tokrat predstavljamo, da so lahko naloge prisotne kadarkoli in ne vse hkrati. Do kakšnih težav lahko to privede?
Predstavljajmo si, da naloga A (100c) prispe prva in se začne izvajati. Pri t=10 prideta nalogi B in C, od katerih bo vsaka trajala 10 sekund. Torej je povprečni čas izvajanja (100+(110-10)+(120-10))3 = 103. Kaj bi lahko razporejevalnik naredil, da bi to izboljšal?
Najkrajši čas do dokončanja (STCF)
Da bi izboljšali situacijo, smo izpustili predpostavko 3, da je program zagnan in teče do zaključka. Poleg tega bomo potrebovali strojno podporo in, kot morda ugibate, jo bomo uporabili časomer za prekinitev tekočega opravila in preklapljanje konteksta. Tako lahko razporejevalnik v trenutku, ko pridejo opravili B, C, naredi nekaj - preneha z izvajanjem opravila A in da nalogi B in C v obdelavo ter po njunem zaključku nadaljuje z izvajanjem procesa A. Tak razporejevalnik imenujemo STCFali Najprej preventivno delo.
Rezultat tega planerja bo naslednji rezultat: ((120-0)+(20-10)+(30-10))/3=50. Tako postane tak planer še bolj optimalen za naša opravila.
Metrični odzivni čas
Če torej poznamo čas izvajanja nalog in ta opravila uporabljajo samo CPE, bo STCF najboljša rešitev. In nekoč v zgodnjih časih so ti algoritmi delovali precej dobro. Vendar uporabnik zdaj večino časa preživi na terminalu in pričakuje produktivno interaktivno izkušnjo. Tako se je rodila nova metrika - odzivni čas (odgovor).
Odzivni čas se izračuna na naslednji način:
Response=Tfirstrun-Tarrival
Tako bo za prejšnji primer odzivni čas: A=0, B=0, C=10 (abg=3,33).
In izkazalo se je, da algoritem STCF ni tako dober v situaciji, ko prispejo 3 naloge hkrati - treba bo počakati, da bodo majhne naloge v celoti dokončane. Torej je algoritem dober za metriko časa preobrata, vendar slab za metriko interaktivnosti. Predstavljajte si, da bi sedeli za terminalom in poskušali vnašati znake v urejevalnik in bi morali čakati več kot 10 sekund, ker je neka druga naloga prevzela CPE. Ni ravno prijetno.
Torej se soočamo z drugo težavo - kako lahko zgradimo razporejevalnik, ki je občutljiv na odzivni čas?
round Robin
Za rešitev tega problema je bil razvit algoritem round Robin (RR). Osnovna ideja je povsem preprosta: namesto izvajanja nalog, dokler niso dokončana, bomo opravilo izvajali določeno časovno obdobje (imenovano časovna rezina) in nato preklopili na drugo opravilo iz čakalne vrste. Algoritem ponavlja svoje delo, dokler niso opravljene vse naloge. V tem primeru mora biti čas delovanja programa večkratnik časa, po katerem bo časovnik prekinil proces. Na primer, če časovnik prekine proces vsakih x=10 ms, mora biti velikost okna za izvajanje procesa večkratnik 10 in mora biti 10,20, 10 ali x*XNUMX.
Poglejmo primer: naloge ABC pridejo v sistem istočasno in vsaka želi delovati 5 sekund. Algoritem SJF bo dokončal vsako nalogo, preden bo začel drugo. Nasprotno pa bo algoritem RR z zagonskim oknom = 1 s opravil naloge, kot sledi (slika 4.3):
(Spet SJF (slabo za odzivni čas)
(Robin Robin (dobro za odzivni čas)
Povprečni odzivni čas za algoritem RR je (0+1+2)/3=1, medtem ko za SJF (0+5+10)/3=5.
Logično je domnevati, da je časovno okno zelo pomemben parameter za RR; manjše kot je, daljši je odzivni čas. Vendar ga ne smete narediti premajhnega, saj bo čas preklapljanja konteksta prav tako igral vlogo pri splošni zmogljivosti. Tako izbiro časa izvajalnega okna nastavi arhitekt OS in je odvisna od nalog, ki se bodo v njem izvajale. Preklapljanje konteksta ni edina servisna operacija, ki izgublja čas - delujoči program deluje še na kup drugih stvareh, na primer raznih predpomnilnikih, in z vsakim preklopom je treba to okolje shraniti in obnoviti, kar lahko vzame tudi veliko čas.
RR je odličen razporejevalnik, če govorimo le o metriki odzivnega časa. Toda kako se bo s tem algoritmom obnašala metrika časa izvedbe naloge? Razmislite o zgornjem primeru, ko je čas delovanja A, B, C = 5 s in prispejo istočasno. Naloga A se bo končala ob 13, B ob 14, C ob 15 s in povprečni čas izvedbe bo 14 s. Tako je RR najslabši algoritem za metriko prometa.
Bolj splošno povedano, vsak algoritem tipa RR je pravičen; čas procesorja enakomerno porazdeli med vse procese. In tako so te metrike nenehno v nasprotju med seboj.
Tako imamo več kontrastnih algoritmov, hkrati pa še vedno ostaja več predpostavk - da je čas opravila znan in da opravilo uporablja samo CPE.
Mešanje z I/O
Najprej odstranimo predpostavko 4, da proces uporablja samo CPE; seveda temu ni tako in procesi lahko dostopajo do druge opreme.
V trenutku, ko kateri koli proces zahteva V/I operacijo, proces preide v blokirano stanje in čaka na dokončanje V/I. Če je I/O poslan na trdi disk, potem lahko takšna operacija traja do nekaj ms ali več, procesor pa bo v tem trenutku miroval. V tem času lahko planer zasede procesor s katerim koli drugim procesom. Naslednja odločitev, ki jo mora razporejevalnik sprejeti, je, kdaj bo proces zaključil svoj V/I. Ko se to zgodi, bo prišlo do prekinitve in OS bo prestavil proces, ki je poklical V/I, v stanje pripravljenosti.
Poglejmo primer več problemov. Vsak od njih zahteva 50 ms procesorskega časa. Vendar bo prvi dostopal do V/I vsakih 10 ms (ki se bo prav tako izvajal vsakih 10 ms). In proces B preprosto uporablja 50ms procesor brez V/I.
V tem primeru bomo uporabili razporejevalnik STCF. Kako se bo razporejevalnik obnašal, če se na njem zažene proces, kot je A? Naredil bo naslednje: najprej bo v celoti izdelal proces A, nato pa proces B.
Tradicionalni pristop k reševanju tega problema je obravnavanje vsake 10-ms podopravila procesa A kot ločene naloge. Tako je pri zagonu z algoritmom STJF izbira med nalogo 50 ms in nalogo 10 ms očitna. Potem, ko je podnaloga A končana, se bosta zagnala proces B in V/I. Po končanem V/I bo običajno znova zagnati 10 ms proces A namesto procesa B. Na ta način je mogoče izvesti prekrivanje, kjer CPE uporablja drug proces, medtem ko prvi čaka na I/O. In posledično je sistem bolje izkoriščen – v trenutku, ko interaktivni procesi čakajo na V/I, se lahko na procesorju izvajajo drugi procesi.
Oraklja ni več
Zdaj pa se poskusimo znebiti predpostavke, da je čas izvajanja naloge znan. To je na splošno najslabša in najbolj nerealna predpostavka na celotnem seznamu. Pravzaprav v povprečnem običajnem operacijskem sistemu operacijski sistem običajno ve zelo malo o času izvajanja nalog, kako torej lahko sestavite razporejevalnik, ne da bi vedeli, kako dolgo bo trajalo izvajanje naloge? Morda bi lahko za rešitev tega problema uporabili nekaj načel RR?
Skupaj
Ogledali smo si osnovne zamisli o razporejanju opravil in si ogledali 2 družini razporejevalcev. Prvi najprej začne najkrajšo nalogo in s tem poveča čas obtoka, drugi pa je enakomerno razpet med vsemi nalogami in poveča odzivni čas. Oba algoritma sta slaba tam, kjer so algoritmi druge družine dobri. Preučili smo tudi, kako lahko vzporedna uporaba CPE in I/O izboljša zmogljivost, vendar nismo rešili težave z OS clairvoyance. In v naslednji lekciji si bomo ogledali planer, ki gleda v neposredno preteklost in poskuša napovedati prihodnost. Imenuje se večnivojska povratna vrsta.
Vir: www.habr.com