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 =)
Načrtovanje: večnivojska čakalna vrsta povratnih informacij
V tem predavanju bomo govorili o problemih razvoja enega najbolj znanih pristopov k
načrtovanje, ki se imenuje Čakalna vrsta za povratne informacije na več ravneh (MLFQ). Planer MLFQ je leta 1962 prvič opisal Fernando J. Corbató v sistemu, imenovanem
Združljiv sistem za delitev časa (CTSS). Ta dela (vključno s poznejšimi deli na
Multics) so bili pozneje nominirani za Turingovo nagrado. Razporejevalnik je bil
naknadno izboljšal in pridobil videz, ki ga najdemo že v
nekaj sodobnih sistemov.
Algoritem MLFQ poskuša rešiti 2 temeljni težavi, ki se prekrivata.
Prvič, skuša optimizirati čas obtoka, ki se, kot smo razpravljali v prejšnjem predavanju, optimizira z metodo začetka na čelu čakalne vrste
kratke naloge. Vendar OS ne ve, kako dolgo bo potekal ta ali oni proces, in to
potrebna znanja za delovanje algoritmov SJF, STCF. Drugič, poskuša MLFQ
narediti sistem odziven za uporabnike (na primer za tiste, ki sedijo in
strmenje v zaslon med čakanjem na dokončanje naloge) in tako skrajšajo čas
odgovor. Na žalost algoritmi, kot je RR, zmanjšajo odzivni čas, vendar
slabo vplivajo na meritev časa pretoka. Zato je naš problem: Kako oblikovati
planer, ki bo ustrezal našim zahtevam in hkrati o njem ne bo vedel ničesar
narava postopka na splošno? Kako se lahko načrtovalec nauči značilnosti nalog,
ki jih zažene in tako sprejema boljše odločitve glede razporejanja?
Bistvo problema: Kako načrtovati zastavljanje nalog brez popolnega znanja?
Kako oblikovati razporejevalnik, ki hkrati zmanjša odzivni čas
za interaktivne naloge in hkrati minimizira čas obtoka, ne da bi vedeli
poznavanje časa izvedbe naloge?
Opomba: učenje iz prejšnjih dogodkov
Čakalna vrsta MLFQ je odličen primer sistema, na katerem se učijo
preteklih dogodkov za napovedovanje prihodnosti. Takšni pristopi so pogosto
najdemo v OS (in mnogih drugih vejah računalništva, vključno z vejami
predvidevanja strojne opreme in algoritmi predpomnjenja). Podobni pohodi
sproži, ko imajo naloge vedenjske faze in so zato predvidljive.
Vendar je pri tej tehniki treba biti previden, saj so napovedi zelo enostavne.
se lahko izkaže za napačno in povzroči, da sistem sprejema slabše odločitve kot
bi bil sploh brez znanja.
MLFQ: Osnovna pravila
Razmislite o osnovnih pravilih algoritma MLFQ. In čeprav implementacije tega algoritma
jih je več, osnovni pristopi so podobni.
V izvedbi, ki jo bomo obravnavali, bo MLFQ imel več
ločene čakalne vrste, od katerih bo vsaka imela drugačno prioriteto. kadarkoli,
naloga, pripravljena za izvedbo, je v isti čakalni vrsti. MLFQ uporablja prioritete,
da se odloči, katero nalogo zagnati za izvedbo, tj. naloga z višjim
prioriteta (opravilo iz čakalne vrste z najvišjo prioriteto) bo zagnano kot prvo
čakalna vrsta.
Seveda je lahko v določeni čakalni vrsti več nalog, torej
tako da bodo imeli enako prednost. V tem primeru bo uporabljen mehanizem
RR za načrtovanje zagona med temi nalogami.
Tako pridemo do dveh osnovnih pravil za MLFQ:
- 1. pravilo: Če je prioriteta (A) > prioriteta (B), se bo opravilo A izvajalo (B ne bo)
- 2. pravilo: Če je prioriteta(A) = prednost(B), se A&B začneta z RR
Na podlagi zgoraj navedenega so ključni elementi za načrtovanje MLFQ
so prednostne naloge. Namesto da bi vsakemu dali določeno prednost
opravilo, MLFQ spremeni svojo prioriteto glede na opaženo vedenje.
Na primer, če se opravilo nenehno zapre v CPE, medtem ko čaka na vnos s tipkovnice,
MLFQ bo ohranil visoko prioriteto procesa, ker je tako
interaktivni proces bi moral delovati. Če je, nasprotno, naloga nenehno in
je CPE intenziven za daljše obdobje, ga bo MLFQ znižal
prednostna naloga. Tako bo MLFQ preučeval obnašanje procesov v času, ko se izvajajo.
in uporabo vedenja.
Narišimo primer, kako bi lahko izgledale čakalne vrste na neki točki
čas in potem dobite nekaj takega:
V tej shemi sta 2 procesa A in B v čakalni vrsti z najvišjo prioriteto. Proces
C je nekje na sredini, proces D pa čisto na koncu čakalne vrste. Glede na zgoraj navedeno
opisov algoritma MLFQ, bo razporejevalnik izvedel le naloge z najvišjo
prioriteta po RR, naloge C, D pa bodo brez dela.
Seveda statična slika ne bo dala popolne slike o delovanju MLFQ.
Pomembno je natančno razumeti, kako se slika skozi čas spreminja.
Poskus 1: Kako spremeniti prioriteto
Na tej točki se morate odločiti, kako bo MLFQ spremenil raven prioritete
opravilo (in s tem položaj opravila v čakalni vrsti) med njegovim življenjskim ciklom. Za
tega morate imeti v mislih potek dela: določeno količino
interaktivne naloge s kratkim časom izvajanja (in s tem pogostim izdajanjem
CPE) in več dolgotrajnih opravil, ki uporabljajo CPE ves svoj delovni čas, medtem ko
odzivni čas za takšne naloge ni pomemben. In tako lahko naredite prvi poskus
implementirajte algoritem MLFQ z naslednjimi pravili:
- 3. pravilo: Ko naloga vstopi v sistem, se uvrsti v čakalno vrsto z najvišjo
- prioriteta.
- Pravilo 4a: Če opravilo uporablja celotno časovno okno, potem ga
- prednost se zniža.
- Pravilo 4b: Če naloga sprosti CPE, preden poteče njeno časovno okno, potem
- ostaja z enako prioriteto.
1. primer: eno samo dolgotrajno opravilo
Kot lahko vidite v tem primeru, je naloga ob sprejemu postavljena z najvišjo
prioriteta. Po časovnem oknu 10 ms se proces zniža po prioriteti.
razporejevalnik. Po naslednjem časovnem oknu se naloga končno zniža na
najnižjo prioriteto v sistemu, kjer ostane.
Primer 2: Izbral kratko nalogo
Zdaj pa poglejmo primer, kako se bo MLFQ poskušal približati SJF. V tem
na primer dve nalogi: A, ki je dolgotrajna naloga, ki se nenehno izvaja
zasedejo CPE in B, kar je kratka interaktivna naloga. Recimo
da je A že deloval nekaj časa, ko je prispela naloga B.
Ta graf prikazuje rezultate scenarija. Naloga A, kot vsaka naloga,
uporaba procesorja je bila čisto na dnu. Naloga B bo prispela ob času T=100 in bo
postavljen v čakalno vrsto z najvišjo prioriteto. Ker je čas delovanja kratek,
dokončal se bo, preden bo dosegel zadnjo čakalno vrsto.
Iz tega primera bi morali razumeti glavni cilj algoritma: ker algoritem ne
pozna dolgo nalogo ali kratko, potem najprej predpostavi, da naloga
kratek in mu daje najvišjo prednost. Če je res kratka naloga, potem
opravilo se bo hitro, sicer pa, če gre za dolgo nalogo, se bo premikalo počasi
v prioriteti navzdol in bo kmalu dokazala, da je res dolga naloga, ki ne
zahteva odgovor.
Primer 3: Kaj pa I/O?
Zdaj pa poglejmo primer V/I. Kot je navedeno v pravilu 4b,
če proces sprosti procesor, ne da bi v celoti porabil svoj procesorski čas,
potem ostane na isti ravni prioritete. Namen tega pravila je precej preprost.
- če interaktivno opravilo izvaja veliko V/I, na primer čaka
od uporabnikovih pritiskov tipk ali miške, bo taka naloga sprostila procesor
pred dodeljenim oknom. Ne bi radi izpustili tako prednostne naloge,
in tako bo ostal na enaki ravni.
Ta primer prikazuje, kako bi algoritem deloval s takšnimi procesi – interaktivna naloga B, ki pred izvedbo potrebuje CPE le 1 ms
V/I proces in dolgo opravilo A, ki ves čas uporablja CPE.
MLFQ ohranja proces B na najvišji prioriteti, ko se nadaljuje
sprosti CPU. Če je B interaktivna naloga, potem je algoritem v tem primeru dosegel
njegov namen je hitro zagnati interaktivne naloge.
Težave s trenutnim algoritmom MLFQ
V prejšnjih primerih smo zgradili osnovno različico MLFQ. In zdi se, da on
opravlja svoje delo dobro in pošteno ter pravično porazdeli čas procesorja med
dolge naloge in omogočanje kratkih nalog ali nalog, ki so zelo dostopne
v I/O za hitro obdelavo. Na žalost ta pristop vsebuje več
resne težave.
Prvič, problem lakote: če bo sistem imel veliko interaktivnih
opravila, bodo porabili ves procesorski čas in s tem niti enega dolgega
naloga ne bo dobila možnosti za izvedbo (stradajo).
Drugič, bi pametni uporabniki lahko napisali svoje programe tako, da
preslepiti urnika. Prevara je v tem, da narediš nekaj, da bi prisilil
razporejevalnik, ki procesu zagotovi več CPU časa. Algoritem, ki
je precej ranljiv za takšne napade: pred časovnim oknom je praktično
konec, morate izvesti V/I operacijo (za nekatere, ne glede na datoteko)
in tako sprostite CPE. Takšno vedenje vam bo omogočilo, da ostanete v istem
samo čakalno vrsto in ponovno pridobite večji odstotek procesorskega časa. Če je narejeno
to je pravilno (npr. zaženite 99 % časa okna, preden sprostite CPE),
taka naloga lahko preprosto monopolizira procesor.
Končno lahko program sčasoma spremeni svoje vedenje. Te naloge
ki uporablja CPE, lahko postane interaktivna. V našem primeru podobno
naloge ne bodo prejele ustrezne obravnave s strani razporejevalnika, kot bi druge
(izvirne) interaktivne naloge.
Vprašanje občinstvu: kakšni napadi na razporejevalnik bi lahko bili izvedeni v sodobnem svetu?
2. poskus: Povečajte prednost
Poskusimo spremeniti pravila in poglejmo, ali se lahko izognemo težavam z
lakota. Kaj lahko storimo, da zagotovimo to povezavo
Naloge procesorja bodo dobile svoj čas (čeprav ne dolgo).
Kot preprosto rešitev težave lahko občasno predlagate
povečati prioriteto vseh tovrstnih nalog v sistemu. Načinov je veliko
da bi to dosegli, poskusimo na primer implementirati nekaj preprostega: prevedi
vse naloge naenkrat na najvišjo prioriteto, zato novo pravilo:
- Rule5: Po določenem času S prenese vse naloge v sistemu v najvišjo čakalno vrsto.
Naše novo pravilo rešuje dve težavi hkrati. Prvič, procesi
zagotovljeno, da ne boste stradali: naloge v najvišji čakalni vrsti si bodo delile
procesorskega časa po algoritmu RR in tako bodo vsi procesi prejeli
procesorski čas. Drugič, če je neki postopek, ki je bil prej uporabljen
samo procesor postane interaktiven, bo ostal v čakalni vrsti z najvišjo
prednost po enkratnem povečanju na najvišjo prioriteto.
Razmislite o primeru. V tem scenariju razmislite o uporabi enega postopka
CPU in dva interaktivna, kratka procesa. Slika na levi strani slike prikazuje vedenje brez pospeševanja prioritete, zato dolgotrajno opravilo začne stradati, potem ko v sistem prispeta dve interaktivni nalogi. Na sliki na desni se vsakih 50 ms poveča prioriteta, zato je zagotovljeno, da bodo vsi procesi prejeli procesorski čas in se bodo občasno zagnali. 50ms je v tem primeru vzeto kot primer, v resnici pa je ta številka nekoliko višja.
Očitno je, da dodajanje periodičnega časa vzpona S povzroči
logično vprašanje: kakšno vrednost je treba nastaviti? Eden od zasluženih
sistemski inženir John Ousterhout je podobne količine v sistemih označil za voo-doo
stalna, saj so na nek način za pravilno potrebovali črno magijo
izpostavljenost. In na žalost ima S takšen okus. Če nastavite tudi vrednost
velika - dolga opravila bodo stradala. In če ga nastavite prenizko,
interaktivne naloge ne bodo prejele ustreznega procesorskega časa.
3. poskus: boljše računovodstvo
Zdaj moramo rešiti še en problem: kako ne
dovolite goljufanje našega urnika? Krivci za to možnost so
pravila 4a, 4b, ki omogočata, da opravilo obdrži svojo prioriteto s sprostitvijo procesorja
pred iztekom dodeljenega časa. Kako ravnati s tem?
Rešitev v tem primeru se lahko šteje za boljše upoštevanje časa procesorja na vsakem
stopnja MLFQ. Namesto da bi pozabili čas, ki ga je program porabil
procesorja za dodeljeni interval, ga morate upoštevati in shraniti. Po
proces je porabil svoj dodeljeni čas, ga je treba znižati na naslednjega
prednostna stopnja. Zdaj ni pomembno, kako bo proces porabil svoj čas - kako
nenehno računanje na procesorju ali kot niz klicev. torej
pravilo 4 je treba prepisati na naslednji način:
- Rule4: Ko opravilo porabi svoj dodeljeni čas v trenutni čakalni vrsti (ne glede na to, kolikokrat je sprostilo CPE), se prioriteta takega opravila zmanjša (premakne se navzdol po čakalni vrsti).
Poglejmo primer:
»
Slika prikazuje, kaj se zgodi, če skušate pretentati razporejevalnik
če bi bilo s prejšnjimi pravili 4a, bi bil 4b rezultat na levi. Z novim
pravilo je, da je rezultat na desni. Pred zaščito lahko vsak proces kliče V/I pred zaključkom in
tako prevladujejo nad CPU, potem ko omogočijo zaščito, ne glede na vedenje
I/O, se bo vseeno spustil v čakalno vrsto in tako ne bo mogel nepošteno
prevzame vire procesorja.
Izboljšanje MLFQ in druge težave
Z zgornjimi izboljšavami se pojavijo nove težave: ena glavnih
vprašanja - kako parametrizirati tak planer? Tisti. Koliko bi moralo biti
čakalne vrste? Kakšna mora biti velikost programskega okna v čakalni vrsti? kako
programu je treba pogosto dati prednost, da bi se izognili stradanju in
upoštevati spremembo obnašanja programa? Na ta vprašanja ni preprostih
odziv in samo eksperimentiranje z obremenitvami in kasnejšo konfiguracijo
razporejevalnik lahko vodi do nekega zadovoljivega ravnovesja.
Na primer, večina implementacij MLFQ omogoča dodeljevanje različnih
časovne reže za različne čakalne vrste. Čakalne vrste z visoko prioriteto so običajno
kratkih intervalih. Te čakalne vrste so sestavljene iz interaktivnih nalog,
preklapljanje med katerima je precej občutljivo in bi moralo trajati 10 ali manj
gospa. V nasprotju s tem so čakalne vrste z nizko prioriteto sestavljene iz dolgotrajnih opravil, ki uporabljajo
procesor. In v tem primeru se dolgi časovni intervali zelo dobro ujemajo (100 ms).
V tem primeru sta 2 nalogi, ki sta delovali v čakalni vrsti z visoko prioriteto 20
ms razdeljen na okna po 10 ms. 40 ms v srednji čakalni vrsti (okno 20 ms) in v čakalni vrsti z nizko prioriteto
časovno okno čakalne vrste je postalo 40 ms, kjer so naloge dokončale svoje delo.
Implementacija MLFQ v OS Solaris je razred razporejevalcev časovne delitve.
Razporejevalnik bo zagotovil nabor tabel, ki natančno določajo, kako bi moral
prioriteta procesa se tekom njegove življenjske dobe spreminja, kakšna naj bo velikost
okno, ki ga je treba dodeliti, in kako pogosto dvigniti prednostne naloge. Administrator
sistem lahko komunicira s to tabelo in povzroči, da se razporejevalnik obnaša
drugače. Ta tabela ima privzeto 60 čakalnih vrst s postopnim povečevanjem
velikost okna od 20 ms (visoka prioriteta) do nekaj sto ms (najnižja prioriteta) in
tudi s povečanjem vseh opravil enkrat na sekundo.
Drugi razporejevalniki MLFQ ne uporabljajo tabele ali katerega koli posebnega
pravila, ki so opisana v tem poglavju, nasprotno, izračunajo prioritete z uporabo
matematične formule. Na primer, razporejevalnik v FreeBSD uporablja formulo za
izračun trenutne prednostne naloge glede na to, koliko proces
uporabljal CPU. Poleg tega se poraba procesorja sčasoma zmanjša in tako
Tako je povečanje prioritete nekoliko drugačno od zgoraj opisanega. To je resnica
imenovani algoritmi razpada. Od različice 7.1 FreeBSD uporablja razporejevalnik ULE.
Nenazadnje imajo številni načrtovalci še druge funkcije. Na primer, nekateri
planerji rezervirajo višje ravni za delovanje operacijskega sistema in s tem
Tako noben uporabniški proces ne more dobiti najvišje prioritete
sistem. Nekateri sistemi vam omogočajo dajanje nasvetov za pomoč
razporejevalnik, da pravilno določi prednost. Na primer z uporabo ukaza lepo
lahko povečate ali zmanjšate prioriteto naloge in s tem povečate ali zmanjšate
zmanjšajte možnosti programa za procesorski čas.
MLFQ: Povzetek
Opisali smo načrtovalski pristop, imenovan MLFQ. Njegovo ime
sklenjen v principu delovanja - ima več čakalnih vrst in uporablja povratne informacije
za določitev prioritete naloge.
Končna oblika pravil bo naslednja:
- Rule1: Če je prioriteta (A) > prioriteta (B), se bo opravilo A izvajalo (B ne bo)
- Rule2: Če je prioriteta(A) = prednost(B), se A&B zaženeta z RR
- Rule3: Ko naloga vstopi v sistem, je postavljena v čakalno vrsto z najvišjo prioriteto.
- Rule4: Ko opravilo porabi svoj dodeljeni čas v trenutni čakalni vrsti (ne glede na to, kolikokrat je sprostilo CPE), se prioriteta takega opravila zmanjša (premakne se navzdol po čakalni vrsti).
- Rule5: Po določenem času S prenese vse naloge v sistemu v najvišjo čakalno vrsto.
MLFQ je zanimiv iz naslednjega razloga - namesto da bi zahteval znanje o
naravo naloge vnaprej, se algoritem nauči preteklega vedenja naloge in nastavi
prednostne naloge. Tako skuša sedeti na dveh stolih hkrati - doseči uspešnost pri majhnih nalogah (SJF, STCF) in pošteno teči pri dolgih,
Opravila, ki obremenjujejo procesor. Zato mnogi sistemi, vključno z BSD in njihovimi izpeljankami,
Solaris, Windows, Mac uporabljajo neko obliko algoritma kot razporejevalnik
MLFQ kot izhodišče.
Dodatni materiali:
- (računalništvo)
Vir: www.habr.com