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 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 á símskeyti =)

Kynning á tímaáætlun

Kjarni vandans: Hvernig á að þróa tímaáætlunarstefnu
Hvernig ætti að hanna undirliggjandi áætlunarstefnuramma? Hverjar ættu að vera helstu forsendurnar? Hvaða mælikvarðar eru mikilvægir? Hvaða grunntækni var notuð í fyrstu tölvukerfum?

Forsendur vinnuálags

Áður en við ræðum mögulegar stefnur skulum við fyrst gera nokkrar einfaldar útrásir um ferla sem keyra í kerfinu, sem eru sameiginlega kölluð vinnuálag. Skilgreining á vinnuálagi er mikilvægur hluti af stefnumótun og því meira sem þú veist um vinnuálagið, því betri er stefnan sem þú getur skrifað.

Við skulum gefa okkur eftirfarandi forsendur um ferla sem keyra í kerfinu, stundum einnig kölluð störf (verkefni). Næstum allar þessar forsendur eru ekki raunhæfar en nauðsynlegar fyrir þróun hugsunar.

Hvert verkefni keyrir í sama tíma,
Öll verkefni eru sett samtímis,
Úthlutað verkefni virkar þar til því er lokið,
Öll verkefni nota aðeins CPU,
Gangtími hvers verkefnis er þekktur.

Tímasetningarmælingar

Til viðbótar við nokkrar forsendur um álagið, þarf annað tól til að bera saman mismunandi tímasetningarstefnur: tímaáætlunarmælingar. Mælikvarði er bara einhver mælikvarði á eitthvað. Það er fjöldi mælikvarða sem hægt er að nota til að bera saman tímasetningar.

Til dæmis munum við nota mæligildi sem kallast afgreiðslutími (afgreiðslutími). Afgreiðslutími verks er skilgreindur sem munurinn á verklokatíma og komutíma verkefna í kerfinu.

Tturnaround=Tcompletion-Turrival

Þar sem við gerðum ráð fyrir að öll verkefnin kæmu á sama tíma, þá Ta=0 og þar með Tt=Tc. Þetta gildi mun náttúrulega breytast þegar við breytum ofangreindum forsendum.

Annar mælikvarði - sanngirni (sanngirni, heiðarleiki). Framleiðni og sanngirni eru oft andstæð einkenni í áætlanagerð. Til dæmis getur tímaáætlunarmaðurinn hámarkað frammistöðu, en á kostnað þess að bíða eftir að önnur verkefni fari í gang og dregur þannig úr sanngirni.

FYRST inn FYRST ÚT (FIFO)

Grunnalgrímið sem við getum innleitt er kallað FIFO eða fyrstur kemur (inn), fyrstur fær (út). Þetta reiknirit hefur nokkra kosti: það er mjög auðvelt í framkvæmd og það passar við allar forsendur okkar og gerir verkið nokkuð vel.

Við skulum líta á einfalt dæmi. Segjum að 3 verkefni hafi verið sett samtímis. En gefum okkur að verkefni A hafi komið aðeins fyrr en öll hin, þannig að það mun birtast í framkvæmdalistanum fyrr en hin, alveg eins og B miðað við C. Gerum ráð fyrir að hvert þeirra verði framkvæmt í 10 sekúndur. Hver verður meðaltíminn til að klára þessi verkefni í þessu tilfelli?

Með því að telja gildin - 10+20+30 og deila með 3 fáum við meðalframkvæmdartíma forritsins sem jafngildir 20 sekúndum.
Nú skulum við reyna að breyta forsendum okkar. Sérstaklega forsenda 1 og þar með munum við ekki lengur gera ráð fyrir að hvert verkefni taki jafn langan tíma að framkvæma. Hvernig mun FIFO standa sig að þessu sinni?

Eins og það kemur í ljós hafa mismunandi framkvæmdartímar afar neikvæð áhrif á framleiðni FIFO reikniritsins. Gerum ráð fyrir að verkefni A taki 100 sekúndur að klára en B og C taki enn 10 sekúndur hvort.

Eins og sést á myndinni verður meðaltími kerfisins (100+110+120)/3=110. Þessi áhrif eru kölluð bílalest áhrif, þegar sumir skammtímaneytendur auðlindar munu standa í biðröð á eftir stórneytanda. Þetta er eins og röðin í matvöruversluninni þegar það er viðskiptavinur fyrir framan þig með fulla körfu. Besta lausnin á vandanum er að reyna að skipta um sjóðvél eða slaka á og anda djúpt.

Stysta starfið fyrst

Er hægt að leysa svipaða stöðu á einhvern hátt með þungavigtarferlum? Svo sannarlega. Önnur tegund skipulags er kölluðStysta starfið fyrst (SJF). Reiknirit þess er líka frekar frumstætt - eins og nafnið gefur til kynna verða stystu verkefnin sett af stað fyrst, hvert á eftir öðru.

Í þessu dæmi mun niðurstaðan af því að keyra sömu ferla vera framför á meðalafgreiðslutíma forritsins og hann verður jöfn 50 í stað 110, sem er næstum 2 sinnum betra.

Þannig að miðað við þá forsendu að öll verkefni berist á sama tíma virðist SJF reiknirit vera besta reikniritið. Hins vegar virðast forsendur okkar enn ekki raunhæfar. Að þessu sinni breytum við forsendu 2 og ímyndum okkur að verkefni geti verið til staðar hvenær sem er og ekki öll á sama tíma. Hvaða vandamál getur þetta leitt til?

Ímyndum okkur að verkefni A (100c) komi fyrst og byrjar að framkvæma. Við t=10 koma verkefni B og C sem hvert um sig tekur 10 sekúndur. Þannig að meðalframkvæmdartími er (100+(110-10)+(120-10))3 = 103. Hvað gæti tímaáætlunarmaðurinn gert til að bæta þetta?

Stysti tími til að ljúka fyrst (STCF)

Til að bæta ástandið sleppum við forsendu 3 um að forritið sé ræst og keyrt þar til því lýkur. Að auki munum við þurfa vélbúnaðarstuðning og, eins og þú gætir giska á, munum við nota tímamælir að trufla hlaupandi verkefni og samhengisskipti. Þannig getur tímaáætlunarmaðurinn gert eitthvað á því augnabliki sem verkefni B, C koma - hætt að framkvæma verkefni A og sett verkefni B og C í vinnslu og, eftir að þeim er lokið, haldið áfram að keyra ferli A. Slíkur tímaáætlun er kallaður STCFeða Fyrirbyggjandi starf fyrst.

Niðurstaða þessa skipuleggjanda verður eftirfarandi niðurstaða: ((120-0)+(20-10)+(30-10))/3=50. Þannig verður slíkur tímaáætlun enn ákjósanlegri fyrir verkefni okkar.

Mælikvarði viðbragðstími

Þannig, ef við þekkjum keyrslutíma verkefnanna og að þessi verkefni nota aðeins CPU, þá mun STCF vera besta lausnin. Og einu sinni á fyrstu tímum virkuðu þessi reiknirit nokkuð vel. Hins vegar eyðir notandinn mestum tíma sínum í flugstöðinni og býst við afkastamikilli gagnvirkri upplifun. Þannig fæddist nýr mælikvarði - viðbragðstími (svar).

Viðbragðstíminn er reiknaður sem hér segir:

Tresponse=Tfirstrun−Tarrival

Þannig, fyrir fyrra dæmið, verður viðbragðstíminn: A=0, B=0, C=10 (abg=3,33).

Og það kemur í ljós að STCF reikniritið er ekki svo gott í aðstæðum þar sem 3 verkefni koma á sama tíma - það verður að bíða þar til litlu verkefnin eru alveg kláruð. Þannig að reikniritið er gott fyrir afgreiðslutímamælinguna, en slæmt fyrir gagnvirknimælinguna. Ímyndaðu þér ef þú værir að sitja við flugstöð að reyna að slá inn stafi í ritil og þurfa að bíða í meira en 10 sekúndur vegna þess að eitthvað annað verkefni var að taka upp CPU. Það er ekki mjög notalegt.

Svo við stöndum frammi fyrir öðru vandamáli - hvernig getum við byggt upp tímaáætlun sem er viðkvæm fyrir viðbragðstíma?

Round Robin

Reiknirit var þróað til að leysa þetta vandamál Round Robin (RR). Grunnhugmyndin er frekar einföld: í stað þess að keyra verkefni þar til þeim er lokið munum við keyra verkefnið í ákveðinn tíma (kallað tímasneið) og síðan skipta yfir í annað verkefni úr röðinni. Reikniritið endurtekur vinnu sína þar til öllum verkefnum er lokið. Í þessu tilviki verður keyrslutími forritsins að vera margfeldi af tímanum eftir að tímamælirinn truflar ferlið. Til dæmis, ef tímamælir truflar ferli á x=10 ms fresti, þá ætti stærð vinnslugluggans að vera margfeldi af 10 og vera 10,20 eða x*10.

Lítum á dæmi: ABC verkefni berast samtímis í kerfið og hvert þeirra vill keyra í 5 sekúndur. SJF reikniritið mun klára hvert verkefni áður en annað er byrjað. Aftur á móti mun RR reikniritið með ræsingarglugga = 1s fara í gegnum verkefnin sem hér segir (Mynd 4.3):

(SJF aftur (slæmt fyrir viðbragðstíma)

(Round Robin (Gott fyrir viðbragðstíma)

Meðalviðbragðstími fyrir RR reiknirit er (0+1+2)/3=1, en fyrir SJF (0+5+10)/3=5.

Það er rökrétt að gera ráð fyrir að tímaglugginn sé mjög mikilvægur breytu fyrir RR; því minni sem hann er, því hærri er viðbragðstíminn. Hins vegar ættir þú ekki að gera það of lítið, þar sem samhengisskiptatími mun einnig gegna hlutverki í heildarframmistöðu. Þannig er val á framkvæmdargluggatíma stillt af OS arkitektinum og fer eftir verkefnum sem fyrirhugað er að framkvæma í honum. Skiptasamhengi er ekki eina þjónustuaðgerðin sem eyðir tíma - forritið sem er í gangi vinnur á mörgum öðrum hlutum, til dæmis ýmsum skyndiminni, og með hverjum rofa er nauðsynlegt að vista og endurheimta þetta umhverfi, sem getur líka tekið mikið af tíma.

RR er frábær tímaáætlun ef við værum aðeins að tala um svartímamælinguna. En hvernig mun mælikvarðinn fyrir afgreiðslutíma verkefna haga sér með þessu reikniriti? Lítum á dæmið hér að ofan, þegar notkunartími A, B, C = 5s og kemur á sama tíma. Verkefni A lýkur klukkan 13, B klukkan 14, C klukkan 15 og meðalafgreiðslutími verður 14 sekúndur. Þannig er RR versta reikniritið fyrir veltumælinguna.

Í almennari skilmálum er hvaða RR-gerð reiknirit sem er sanngjarnt; það skiptir CPU tímanum jafnt á milli allra ferla. Og þar með stangast þessar mælikvarðar stöðugt innbyrðis.

Þannig höfum við nokkra andstæða reiknirit og á sama tíma eru enn nokkrar forsendur eftir - að verktíminn sé þekktur og að verkefnið noti aðeins örgjörvann.

Blöndun við I/O

Í fyrsta lagi skulum við fjarlægja forsendu 4 um að ferlið notar aðeins örgjörvann; náttúrulega er þetta ekki raunin og ferlar geta fengið aðgang að öðrum búnaði.

Um leið og eitthvert ferli biður um I/O aðgerð fer ferlið í læst ástand og bíður eftir að I/O ljúki. Ef I/O er sent á harða diskinn, þá getur slík aðgerð tekið allt að nokkrar ms eða lengur og örgjörvinn verður aðgerðalaus á þessari stundu. Á þessum tíma getur tímaáætlunarmaðurinn tekið örgjörvann með hvaða öðru ferli sem er. Næsta ákvörðun sem tímaáætlunarmaðurinn þarf að taka er hvenær ferlið lýkur I/O. Þegar þetta gerist mun truflun eiga sér stað og stýrikerfið mun setja ferlið sem kallaði I/O í tilbúið ástand.

Við skulum skoða dæmi um nokkur vandamál. Hver þeirra krefst 50ms af CPU tíma. Hins vegar mun sá fyrsti fá aðgang að I/O á 10 ms fresti (sem verður einnig keyrt á 10 ms fresti). Og ferli B notar einfaldlega 50ms örgjörva án I/O.

Í þessu dæmi munum við nota STCF tímaáætlun. Hvernig mun tímaáætlunarmaðurinn haga sér ef ferli eins og A er sett af stað á honum? Hann mun gera eftirfarandi: fyrst mun hann vinna algjörlega úr ferli A og síðan ferli B.

Hin hefðbundna nálgun til að leysa þetta vandamál er að meðhöndla hvert 10 ms undirverk í ferli A sem sérstakt verkefni. Þannig að þegar byrjað er á STJF reikniritinu er valið á milli 50 ms verkefni og 10 ms verkefni augljóst. Síðan, þegar undirverkefni A er lokið, verður ferli B og I/O ræst. Eftir að I/O lýkur er venjan að hefja 10ms ferli A aftur í stað ferli B. Þannig er hægt að útfæra skörun, þar sem örgjörvinn er notaður af öðru ferli á meðan sá fyrsti bíður eftir I/O. Og fyrir vikið nýtist kerfið betur - á því augnabliki sem gagnvirkir ferlar bíða eftir I/O er hægt að keyra önnur ferli á örgjörvanum.

The Oracle er ekki lengur

Nú skulum við reyna að losna við þá forsendu að keyrslutími verkefnisins sé þekktur. Þetta er almennt versta og óraunhæfasta forsendan á öllum listanum. Reyndar, í venjulegu stýrikerfi að meðaltali, veit stýrikerfið sjálft yfirleitt mjög lítið um framkvæmdartíma verkefna, svo hvernig geturðu þá byggt upp tímaáætlun án þess að vita hversu langan tíma verkefnið tekur að framkvæma? Kannski gætum við notað einhverjar RR meginreglur til að leysa þetta vandamál?

Samtals

Við skoðuðum grunnhugmyndir um verkefnaáætlun og skoðuðum 2 fjölskyldur tímaáætlunarmanna. Sá fyrsti byrjar fyrst á stysta verkefninu og eykur þannig afgreiðslutímann, en sá síðari rífur jafnt á milli allra verkefna og eykur viðbragðstímann. Bæði reikniritin eru slæm þar sem reiknirit hinnar fjölskyldunnar eru góð. Við skoðuðum líka hvernig samhliða notkun örgjörva og I/O getur bætt afköst, en leystum ekki vandamálið með skyggni stýrikerfisins. Og í næstu lexíu munum við skoða skipuleggjanda sem lítur inn í næstu fortíð og reynir að spá fyrir um framtíðina. Og það er kallað multi-level feedback queue.

Heimild: www.habr.com

Stýrikerfi: Þrjú auðveld stykki. Hluti 4: Kynning á tímaáætluninni (þýðing)