Kynning á stýrikerfum
Halló, Habr! Mig langar að kynna þér röð greina-þýðinga á einni bókmenntum sem er áhugaverð að mínu mati - OSTEP. Þetta efni skoðar nokkuð djúpt vinnu unix-líkra stýrikerfa, nefnilega vinnu með ferlum, ýmsum tímaáætlunum, minni og öðrum álíka íhlutum sem mynda nútíma stýrikerfi. Þú getur séð frumrit allra efnis hér . Vinsamlegast athugaðu að þýðingin var gerð ófagmannlega (alveg frjálslega), en ég vona að ég hafi haldið almennri merkingu.
Vinnustofur um þetta efni má finna hér:
Aðrir hlutar:
Þú getur líka skoðað rásina mína á =)
Skipulagning: Multi-Level Feedback Queue
Í þessum fyrirlestri munum við tala um vandamálin við að þróa eina af frægustu aðferðum við
skipulagsmál, sem kallað er Multi-Level Feedback Biðröð (MLFQ). MLFQ tímaáætluninni var fyrst lýst árið 1962 af Fernando J. Corbató í kerfi sem kallast
Samhæft tímadeilingarkerfi (CTSS). Þessi verk (þar á meðal síðari vinnu við
Multics) voru í kjölfarið tilnefndir til Turing verðlaunanna. Skipuleggjandinn var
batnaði í kjölfarið og fékk það útlit sem þegar er að finna í
sum nútíma kerfi.
MLFQ reikniritið reynir að leysa 2 grundvallarvandamál sem skarast.
Í fyrsta lagi, það reynir að hámarka afgreiðslutímann, sem, eins og við ræddum í fyrri fyrirlestri, er fínstilltur með þeirri aðferð að byrja sem mest í byrjun biðröðarinnar
stutt verkefni. Hins vegar veit stýrikerfið ekki hversu lengi tiltekið ferli mun keyra, og þetta
nauðsynleg þekking fyrir rekstur SJF, STCF reikniritanna. Í öðru lagi, MLFQ er að reyna
gera kerfið móttækilegt fyrir notendur (til dæmis fyrir þá sem sitja og
stara á skjáinn og bíða eftir að verkefninu ljúki) og lágmarka þannig tíma
svar. Því miður bæta reiknirit eins og RR viðbragðstíma, en ákaflega
hafa slæm áhrif á afgreiðslutíma mælikvarða. Þess vegna vandamál okkar: Hvernig á að hanna
tímaáætlun sem mun uppfylla kröfur okkar án þess að vita neitt um
eðli ferlisins almennt? Hvernig getur tímaáætlunarmaðurinn lært eiginleika verkefna,
sem hún setur af stað og taka þannig betri skipulagsákvarðanir?
Kjarni vandans: Hvernig á að skipuleggja uppsetningu verkefna án fullkominnar þekkingar?
Hvernig á að hanna tímaáætlun sem samtímis lágmarkar viðbragðstíma
fyrir gagnvirk verkefni og lágmarkar um leið afgreiðslutíma án þess að vita
þekkingu á framkvæmdartíma verkefna?
Athugið: við lærum af fyrri atburðum
MLFQ biðröð er frábært dæmi um kerfi sem lærir af
fyrri atburði til að spá fyrir um framtíðina. Svipaðar aðferðir eru oft
finnast í OS (Og mörgum öðrum greinum tölvunarfræði, þar á meðal útibúum
vélbúnaðarspár og skyndiminni reiknirit). Svipaðar ferðir
koma af stað þegar verkefni hafa hegðunarfasa og eru því fyrirsjáanleg.
Hins vegar ættir þú að vera varkár með þessa tækni vegna þess að spár eru mjög auðveldar
getur reynst rangt og leitt til þess að kerfið tekur verri ákvarðanir en
væri alls þekkingarlaus.
MLFQ: Grunnreglur
Við skulum skoða grunnreglur MLFQ reikniritsins. Og þó útfærslur þessa reiknirit
Það eru nokkrir, grunnaðferðirnar eru svipaðar.
Í útfærslunni sem við munum skoða mun MLFQ hafa nokkra
aðskildar biðraðir, sem hver um sig mun hafa mismunandi forgang. Hvenær sem er,
verkefni tilbúið til framkvæmdar er í einni biðröð. MLFQ notar forgangsröðun,
að ákveða hvaða verkefni á að keyra til framkvæmda, þ.e. verkefni með hærra
forgangur (verkefni úr röðinni með hæsta forgang) verður ræst fyrst
biðröð.
Auðvitað geta verið fleiri en eitt verkefni í tiltekinni biðröð, svo
þannig að þeir munu hafa sama forgang. Í þessu tilviki verður vélbúnaðurinn notaður
RR til að skipuleggja hlaup meðal þessara verkefna.
Þannig komumst við að tveimur grundvallarreglum fyrir MLFQ:
- Regla 1: Ef forgangur (A) > Forgangur (B) verður verkefni A sett af stað (B mun ekki)
- Regla 2: Ef forgangur (A) = Forgangur (B), er A&B byrjað með því að nota RR
Byggt á ofangreindu eru lykilatriðin í skipulagningu MLFQ
eru forgangsverkefni. Í stað þess að gefa hverjum og einum fastan forgang
verkefni, breytir MLFQ forgangi eftir þeirri hegðun sem sést.
Til dæmis, ef verkefni er stöðugt að kasta vinnu í örgjörvann á meðan beðið er eftir innslætti lyklaborðs,
MLFQ mun halda forgangi ferlisins ofarlega því það er hvernig
gagnvirkt ferli ætti að virka. Ef þvert á móti er verkefnið stöðugt og
notar CPU mikið yfir langan tíma, MLFQ mun lækka það
forgangsverkefni. Þannig mun MLFQ rannsaka hegðun ferla á meðan þeir eru í gangi
og nota hegðun.
Tökum dæmi um hvernig biðraðir gætu litið út einhvern tíma
tíma og þá færðu eitthvað á þessa leið:
Í þessu kerfi eru 2 ferli A og B í forgangsröðinni. Ferli
C er einhvers staðar í miðjunni og ferli D er aftast í röðinni. Samkvæmt ofangreindu
Samkvæmt lýsingunum á MLFQ reikniritinu mun tímaáætlunarmaðurinn framkvæma verkefni aðeins með hæsta
forgang samkvæmt RR, og verkefni C, D verða án vinnu.
Auðvitað gefur kyrrstæð skyndimynd ekki heildarmynd af því hvernig MLFQ virkar.
Það er mikilvægt að skilja nákvæmlega hvernig myndin breytist með tímanum.
Tilraun 1: Hvernig á að breyta forgangi
Á þessum tímapunkti þarftu að ákveða hvernig MLFQ mun breyta forgangsstigi
verkefni (og þar með staða verkefnisins í biðröðinni) eftir því sem líður á lífsferilinn. Fyrir
þetta er nauðsynlegt til að hafa verkflæðið í huga: ákveðna upphæð
gagnvirk verkefni með stuttum keyrslutíma (og þar með tíð losun
CPU) og nokkur langvarandi verkefni sem nota CPU allan sinn vinnutíma, á meðan
Viðbragðstími er ekki mikilvægur fyrir slík verkefni. Og þannig geturðu gert þína fyrstu tilraun
innleiða MLFQ reikniritið með eftirfarandi reglum:
- Regla 3: Þegar verkefni kemur inn í kerfið er það sett í röðina með hæsta
- forgang.
- Regla4a: Ef verkefni notar allan þann tíma sem því er úthlutað, þá er það
- forgangur er skertur.
- Regla4b: Ef verkefni sleppir örgjörvanum áður en tímagluggi hans rennur út, þá er það
- áfram með sama forgang.
Dæmi 1: Eitt langvarandi verkefni
Eins og sést á þessu dæmi er inntökuverkefni sett með hæstv
forgang. Eftir 10 ms tíma er ferlið lækkað í forgangi
skipuleggjandi. Eftir næsta tímaglugga er verkefnið loksins lækkað í
lægsta forgang í kerfinu, þar sem hann er áfram.
Dæmi 2: Skilaði stutt verkefni
Nú skulum við sjá dæmi um hvernig MLFQ mun reyna að nálgast SJF. Í því
dæmi, tvö verkefni: A, sem er langvarandi verkefni stöðugt
hernema CPU og B, sem er stutt gagnvirkt verkefni. Geri ráð fyrir
að A hafi þegar verið að vinna í nokkurn tíma þegar verkefni B kom.
Þetta línurit sýnir niðurstöður atburðarásarinnar. Verkefni A, eins og öll verkefni,
Örgjörvanotkun var neðst. Verkefni B kemur á tíma T=100 og mun
settur í fremstu forgangsröð. Þar sem rekstrartími þess er stuttur, þá
það mun klárast áður en komið er í síðustu röðina.
Út frá þessu dæmi ætti að skilja meginmarkmið reikniritsins: þar sem reikniritið gerir það ekki
veit hvort verkefni er langt eða stutt, þá gerir hann fyrst og fremst ráð fyrir því að verkefnið
stutt og gefur því hæsta forgang. Ef þetta er mjög stutt verkefni, þá
það mun klárast fljótt, annars ef það er langt verk mun það fara hægt
forgangsröðun niður og mun fljótlega sanna að hún er sannarlega langt verkefni sem gerir það ekki
krefst svars.
Dæmi 3: Hvað með I/O?
Nú skulum við skoða I/O dæmi. Eins og fram kemur í reglu 4b,
ef ferli sleppir örgjörvanum án þess að nota allan örgjörvatímann,
þá helst það á sama forgangsstigi. Tilgangur þessarar reglu er frekar einfaldur
- ef gagnvirka starfið framkvæmir margar I/O aðgerðir, til dæmis bið
frá notandalyklinum eða músarpressum mun slíkt verkefni losa um örgjörvann
fyrir úthlutaðan glugga. Við viljum ekki lækka forgang slíks verkefnis,
og þannig mun það haldast á sama stigi.
Þetta dæmi sýnir hvernig reikniritið mun virka með slíkum ferlum - gagnvirkt starf B, sem þarf aðeins örgjörva í 1ms áður en það er keyrt
I/O ferli og langvarandi Job A, sem eyðir öllum sínum tíma í að nota örgjörvann.
MLFQ heldur ferli B í hæsta forgangi vegna þess að það heldur áfram
slepptu CPU. Ef B er gagnvirkt verkefni, þá hefur reikniritið náð
Markmið þitt er að keyra gagnvirk verkefni hratt.
Vandamál með núverandi MLFQ reiknirit
Í fyrri dæmunum byggðum við grunnútgáfu af MLFQ. Og svo virðist sem hann
gerir starf sitt vel og heiðarlega, dreifir CPU tíma þokkalega á milli
löng verkefni og leyfa stutt eða stór verkefni
vinna á I/O fljótt. Því miður inniheldur þessi aðferð nokkrar
alvarleg vandamál.
Í fyrsta lagi, vandamálið við hungur: ef kerfið hefur marga gagnvirka
verkefni, þá munu þau eyða öllum örgjörvatímanum og þar með ekki einn í langan tíma
ekki verður hægt að framkvæma verkefnið (þeir eru að svelta).
Í öðru lagi, gátu klárir notendur skrifað forritin sín þannig að
blekkja tímaáætlunarmanninn. Blekking felst í því að gera eitthvað til að þvinga
Tímaáætlunin gefur ferlinu meiri CPU tíma. Reiknirit það
sem lýst er hér að ofan er nokkuð viðkvæmt fyrir svipuðum árásum: áður en tímaglugginn er nánast
lokið, þú þarft að framkvæma I/O aðgerð (fyrir suma, sama hvaða skrá)
og losa þannig um CPU. Slík hegðun mun leyfa þér að vera í sama ástandi
biðröðina sjálfa og aftur fá stærra hlutfall af CPU tíma. Ef þú gerir
þetta er rétt (til dæmis, keyrðu 99% af gluggatímanum áður en þú sleppir örgjörvanum),
slíkt verkefni getur einfaldlega einokað örgjörvann.
Að lokum getur forrit breytt hegðun sinni með tímanum. Þau verkefni
sem notaði CPU getur orðið gagnvirkt. Í okkar dæmi, svipað
verkefni munu ekki fá þá meðferð sem þau eiga skilið frá tímaáætlunaraðilanum eins og aðrir myndu
(fyrstu) gagnvirk verkefni.
Spurning til áhorfenda: hvaða árásir á tímaáætlun gætu verið gerðar í nútíma heimi?
Tilraun 2: Aukinn forgangur
Við skulum reyna að breyta reglunum og sjá hvort við getum forðast vandamál með
fastandi. Hvað getum við gert til að tryggja að tengt
Örgjörvaverkefni munu fá sinn tíma (jafnvel þó ekki lengi).
Sem einföld lausn á vandamálinu geturðu lagt til reglulega
hækka forgang allra slíkra verkefna í kerfinu. Það eru margar leiðir
Til að ná þessu skulum við reyna að útfæra eitthvað einfalt sem dæmi: þýða
öll verkefni eru strax sett í hæsta forgang, þess vegna er nýja reglan:
- Regla5: Eftir ákveðið tímabil S, færðu öll verkefni í kerfinu í hæstu röðina.
Nýja reglan okkar leysir tvö vandamál í einu. Í fyrsta lagi ferlarnir
er tryggt að svelta ekki: Verkefnum sem eru í hæsta forgangi verður skipt
CPU tími samkvæmt RR reikniritinu og þar með munu allir ferlar fá
CPU tími. Í öðru lagi, ef einhver aðferð sem áður var notuð
aðeins örgjörvinn verður gagnvirkur, hann verður áfram í röðinni með hæsta
forgang eftir að hafa fengið einskiptisauka forgang til hæstv.
Við skulum líta á dæmi. Í þessari atburðarás skaltu íhuga eitt ferli sem notar
Örgjörvi og tveir gagnvirkir, stuttir ferlar. Vinstra megin á myndinni sýnir myndin hegðunina án forgangskynningar og þannig byrjar langvarandi verkefnið að svelta eftir að tvö gagnvirk verkefni koma inn í kerfið. Á myndinni til hægri er forgangsaukning framkvæmd á 50 ms fresti og því er tryggt að öll ferli fái örgjörvatíma og verður ræst reglulega. 50ms í þessu tilfelli er tekið sem dæmi; í raun er þessi tala aðeins hærri.
Augljóslega, að bæta við reglubundnum hækkunartíma S leiðir til
rökrétt spurning: hvaða gildi ætti að setja? Einn af þeim heiðruðu
kerfisfræðingarnir John Ousterhout kallaði slíkt magn í kerfum eins og vú-dú
stöðug, þar sem þeir þurftu á einhvern hátt svartagaldur til að rétta
sýna. Og því miður hefur S slíkan lykt. Ef þú stillir gildið líka
stór - löng verkefni munu byrja að svelta. Og ef þú stillir gildið of lágt,
Gagnvirk verkefni munu ekki fá réttan örgjörvatíma.
Tilraun 3: Betra bókhald
Nú höfum við annað vandamál að leysa: hvernig á ekki að gera það
leyfa tímaáætlunarmanninum okkar að blekkjast? Þeir sem eiga sök á þessum möguleika eru
reglur 4a, 4b, sem gera starf kleift að halda forgangi, sem losar um örgjörva
áður en tiltekinn tími rennur út. Hvernig á að bregðast við þessu?
Lausnin í þessu tilfelli getur talist betri bókhald á CPU tíma á hverjum
MLFQ stig. Í stað þess að gleyma tímanum sem forritið notaði
örgjörva fyrir úthlutað tímabil, ætti að taka tillit til þess og vista. Eftir
ferlið hefur notað sinn úthlutaða tíma, ætti að lækka það í það næsta
forgangsstig. Nú skiptir ekki máli hvernig ferlið mun nota tíma sinn - hvernig
stöðugt að reikna á örgjörvanum eða sem fjölda símtala. Þannig,
reglu 4 ætti að endurskrifa á eftirfarandi form:
- Regla4: Eftir að verkefni hefur notað úthlutaðan tíma í núverandi biðröð (sama hversu oft það losaði örgjörvann), er forgangur þess verks lækkaður (það færist niður í röðina).
Við skulum skoða dæmi:
»
Myndin sýnir hvað gerist ef þú reynir að blekkja tímaáætlunarmanninn, eins og
ef það væri með fyrri reglum 4a, 4b fengist niðurstaðan til vinstri. Gleðilegt nýtt
reglan er niðurstaðan til hægri. Fyrir vernd gæti hvaða ferli sem er hringt í I/O áður en því er lokið og
drottna þannig yfir CPU, eftir að hafa virkjað vernd, óháð hegðun
I/O, hann mun samt færa sig neðar í röðinni og mun því ekki geta óheiðarlega
taka yfir CPU auðlindir.
Bæta MLFQ og önnur vandamál
Með ofangreindum endurbótum koma ný vandamál: eitt helsta
Spurningar - hvernig á að stilla slíkan tímaáætlun? Þeir. Hversu mikið ætti það að vera
biðraðir? Hver ætti að vera stærð forritsgluggans í biðröðinni? Hvernig
Forgangur dagskrár ætti oft að aukast til að forðast hungur og
taka tillit til breyttrar hegðunar forrits? Það er ekkert einfalt svar við þessum spurningum
svar og aðeins tilraunir með álag og síðari uppsetningu
skipuleggjandi getur leitt til viðunandi jafnvægis.
Til dæmis leyfa flestar MLFQ útfærslur þér að úthluta mismunandi
tímabil fyrir mismunandi biðraðir. Hátt forgangsraðir venjulega
ávísað er stuttu millibili. Þessar biðraðir samanstanda af gagnvirkum verkefnum,
skipta á milli sem er frekar viðkvæmt og ætti að taka 10 eða minna
Fröken. Aftur á móti samanstanda lágforgangsraðir af langvinnum verkefnum sem nota
ÖRGJÖRVI. Og í þessu tilfelli passa löng tímabil mjög vel (100ms).
Í þessu dæmi eru 2 verkefni sem virkuðu í forgangsröð 20
ms, skipt í 10ms glugga. 40ms í miðröð (20ms gluggi) og í lágum forgangi
Biðraðartími gluggi varð 40ms þar sem verkefni kláruðu vinnu sína.
Solaris OS útfærslan á MLFQ er flokkur tímaskiptatímaritara.
Skipuleggjandinn mun útvega sett af töflum sem skilgreina nákvæmlega eins og það ætti að gera
forgangsröðun ferlisins breytist á lífsleiðinni, hver ætti að vera stærðin
úthlutað glugga og hversu oft þú þarft að hækka forgangsröðun verkefna. Stjórnandi
kerfi geta haft samskipti við þessa töflu og valdið því að tímaáætlunarmaðurinn hegðar sér
öðruvísi. Sjálfgefið er að þessi tafla hefur 60 biðraðir með hægfara aukningu
gluggastærð frá 20 ms (hár forgangur) til nokkur hundruð ms (lágur forgangur), og
einnig með aukningu á öllum verkefnum einu sinni á sekúndu.
Aðrir MLFQ skipuleggjendur nota ekki töflu eða neina sérstaka
reglum sem lýst er í þessum fyrirlestri, þvert á móti reikna þær forgangsröðun með því að nota
stærðfræðilegar formúlur. Til dæmis, FreeBSD tímaáætlun notar formúlu fyrir
reikna út núverandi forgang verkefnis út frá því hversu langt ferlið er
notaður CPU. Auk þess minnkar örgjörvanotkun með tímanum og svo
Þannig gerist aukinn forgangur með öðrum hætti en lýst er hér að ofan. Þetta er satt
kallaðir decay algrím. Frá útgáfu 7.1 hefur FreeBSD notað ULE tímaáætlunina.
Að lokum, margir tímasetningar hafa aðra eiginleika. Til dæmis, sumir
tímaáætlunarmenn panta hæstu stigin fyrir rekstur stýrikerfisins og þar með
Þannig getur ekkert notendaferli fengið hæsta forgang í
kerfi. Sum kerfi leyfa þér að gefa ráð til að hjálpa
skipuleggjandi getur forgangsraðað rétt. Til dæmis með því að nota skipunina gott
þú getur aukið eða minnkað forgang verkefnis og þannig aukið eða
draga úr líkum forritsins á að nota CPU tíma.
MLFQ: Samantekt
Við höfum lýst skipulagsnálgun sem kallast MLFQ. Nafn hans
fylgir meginreglunni um rekstur - það hefur nokkrar biðraðir og notar endurgjöf
að ákvarða forgang verkefna.
Endanleg form reglnanna verður sem hér segir:
- Regla1: Ef forgangur (A) > Forgangur (B) verður verkefni A ræst (B mun ekki)
- Regla2: Ef forgangur(A) = Forgangur(B), er A&B byrjað með því að nota RR
- Regla3: Þegar verkefni kemur inn í kerfið er það sett í biðröð með hæsta forgang.
- Regla4: Eftir að verkefni hefur notað úthlutaðan tíma í núverandi biðröð (sama hversu oft það losaði örgjörvann), er forgangur þess verks lækkaður (það færist niður í röðina).
- Regla5: Eftir ákveðið tímabil S, færðu öll verkefni í kerfinu í hæstu röðina.
MLFQ er áhugavert af eftirfarandi ástæðu - í stað þess að krefjast þekkingar um
eðli verkefnisins fyrirfram, reiknirit rannsakar fyrri hegðun verkefnisins og settanna
forgangsröðun í samræmi við það. Þannig reynir hann að sitja á tveimur stólum í einu - til að ná fram framleiðni fyrir lítil verkefni (SJF, STCF) og hlaupa heiðarlega lengi,
CPU-hleðsla störf. Þess vegna eru mörg kerfi, þar á meðal BSD og afleiður þeirra,
Solaris, Windows, Mac nota einhvers konar reiknirit sem tímaáætlun
MLFQ sem grunnlína.
Viðbótarefni:
- (tölvumál)
Heimild: www.habr.com