Nhanganyaya kune Operating Systems
Mhoro, Habr! Ndinoda kukupa pfungwa dzako nhevedzano yezvinyorwa-shanduro yeimwe bhuku inonakidza mumaonero angu - OSTEP. Ichi chinyorwa chinoongorora zvakadzama basa reunix-senge masisitimu anoshanda, anoti, kushanda nematanho, akasiyana marongero, ndangariro uye zvimwe zvakafanana zvinoumba OS yemazuva ano. Iwe unogona kuona yepakutanga yezvinhu zvese pano . Ndapota cherechedza kuti shanduro yakaitwa zvisina basa (zvakasununguka), asi ndinovimba kuti ndakachengeta zvazvinoreva.
Basa re laboratori panyaya iyi rinogona kuwanikwa pano:
Zvimwe zvikamu:
Unogonawo kutarisa chiteshi changu pa =)
Kuronga: Multi-Level Feedback Queue
Muhurukuro iyi tichataura nezvematambudziko ekugadzira imwe yenzira dzakakurumbira dzekuita
kuronga, kunonzi Multi-Level Feedback Queue (MLFQ). Iyo MLFQ scheduler yakatanga kutsanangurwa muna 1962 naFernando J. CorbatΓ³ muhurongwa hunonzi.
Inoenderana Nguva-Kugova System (CTSS). Aya mabasa (kusanganisira gare gare kushanda pa
Multics) vakazosarudzwa kuti vawane Turing Award. Murongi aive
akazovandudza uye akawana chitarisiko chinogona kuwanikwa kare mukati
mamwe maitiro emazuva ano.
Iyo MLFQ algorithm inoedza kugadzirisa 2 akakosha anopindirana matambudziko.
Kutanga, inoedza kugadzirisa nguva yekuchinja, iyo, sezvatakakurukura muhurukuro yapfuura, inogadziriswa nenzira yekutanga pakutanga kwemutsara zvakanyanya.
mabasa mapfupi. Nekudaro, iyo OS haizive kuti imwe nzira ichatora nguva yakareba sei, uye izvi
ruzivo rwakakosha rwekushanda kweSJF, STCF algorithms. Chechipiri, MLFQ iri kuedza
ita kuti sisitimu iite kune vashandisi (semuenzaniso, kune avo vanogara uye
tarisa pachiratidziro uchimirira kuti basa ripere) uye nokudaro kuderedza nguva
mhinduro. Nehurombo, maalgorithms seRR anovandudza nguva yekupindura, asi zvakanyanya
vane kukanganisa kwakashata pane yekuchinja nguva metric. Saka dambudziko redu: Maitiro ekugadzira
mugadziri anozozadzisa zvatinoda pasina chaanoziva nezvazvo
chimiro chemuitiro wacho? Mugadziri anogona sei kudzidza maitiro emabasa,
iyo yainotangisa uye nokudaro kuita sarudzo dziri nani dzekuronga?
Chinokosha chedambudziko: Nzira yekuronga sei kugadzirisa kwemabasa pasina ruzivo rwakakwana?
Magadzirirwo emugadziri anoderedza nguva yekupindura panguva imwe chete
kumabasa ekudyidzana uye panguva imwe chete inoderedza nguva yekuchinja pasina kuziva
ruzivo rwenguva yekuita basa?
Cherechedza: tinodzidza kubva pane zvakaitika kare
Mutsara weMLFQ muenzaniso wakanaka kwazvo wesystem inodzidza kubva
zviitiko zvakapfuura kufanotaura ramangwana. Nzira dzakafanana dzinowanzoitwa
inowanikwa muOS (Uye mamwe matavi mazhinji esainzi yekombuta, kusanganisira matavi
Hardware kufanotaura uye caching algorithms). Nzendo dzakafanana
zvinotangwa kana mabasa aine nhanho dzekuita uye nekudaro anogona kufanofungidzira.
Nekudaro, iwe unofanirwa kungwarira nehunyanzvi uhu nekuti kufanotaura kuri nyore kwazvo
inogona kuve isina kururama uye inotungamira sisitimu kuita sarudzo dzakaipa kupfuura
vangadai vasina ruzivo zvachose.
MLFQ: Basic Mitemo
Ngatitarisei mitemo yekutanga yeMLFQ algorithm. Uye kunyangwe kuita kweiyi algorithm
Kune akati wandei, maitiro ekutanga akafanana.
Mukuita kwatichange tichitarisa, MLFQ ichave iine akati wandei
mitsara yakasiyana, imwe neimwe ichange iine zvakakosha zvakasiyana. Chero nguva,
basa rakagadzirira kuitwa riri mumutsetse mumwe. MLFQ inoshandisa zvinokoshesa,
kusarudza kuti ibasa ripi rokumhanya kuti riitwe, i.e. basa nepamusoro
zvakakosha (basa rinobva pamutsetse rine hukuru hwepamusoro) richatangwa kutanga
mutsara.
Ehe, panogona kunge paine basa rinopfuura rimwe mumutsetse wakapihwa, saka
saka ivo vachava nekutanga kumwe chete. Muchiitiko ichi, iyo michina ichashandiswa
RR kuronga kumhanya pakati peaya mabasa.
Saka tinosvika pamitemo miviri yakakosha yeMLFQ:
- Mutemo1: Kana zvakakosha (A) > Kukosha (B), basa A richatangwa (B harisi)
- Mutemo2: Kana zvakakosha (A) = Kukosha (B), A&B inotangwa kushandisa RR
Kubva pane zviri pamusoro, zvinhu zvakakosha pakuronga MLFQ
ndizvo zvinokosha. Panzvimbo pekupa chinongedzo chekutanga kune chimwe nechimwe
basa, MLFQ inoshandura kukosha kwayo zvichienderana nehunhu hunocherechedzwa.
Semuenzaniso, kana basa richigara richikanda basa kuCPU uchimirira kupinza keyboard,
MLFQ inochengeta maitiro ekutanga akakwira nekuti ndizvo zvinoita
nzira yekudyidzana inofanira kushanda. Kana, pane zvinopesana, basa racho rinogara uye
inoshandisa CPU zvakanyanya kwenguva yakareba, MLFQ inoidzikisa
chinhu chinokosha. Saka, MLFQ ichadzidza maitiro emaitiro pavanenge vachimhanya
uye kushandisa maitiro.
Ngatitorei muenzaniso wekuti mitsetse ingaite sei pane imwe nguva
nguva uye wobva wawana chimwe chinhu chakadai:
Muchirongwa ichi, 2 maitiro A uye B ari mumutsara wepamusoro-soro. Process
C pane imwe nzvimbo pakati, uye maitiro D ari kumucheto chaiko kwemutsara. Maererano nepamusoro
Zvinoenderana nerondedzero yeMLFQ algorithm, iye anoronga achaita mabasa chete neakakwirira
zvakakosha maererano neRR, uye mabasa C, D achange asiri kushanda.
Sezvingatarisirwa, mufananidzo wakamira hauzope mufananidzo wakazara wekuti MLFQ inoshanda sei.
Izvo zvakakosha kuti unzwisise chaizvo kuti mufananidzo unochinja sei nekufamba kwenguva.
Kuedza 1: Maitiro ekuchinja zvakakosha
Panguva ino iwe unofanirwa kusarudza kuti MLFQ ichachinja sei danho rekutanga
mabasa (uye nokudaro chinzvimbo chebasa mumutsara) sezvarinofambira mberi kuburikidza nehupenyu hwaro. For
izvi zvinodiwa kuti urambe uchifunga nezvekufamba kwebasa: imwe mari
mabasa anopindirana ane nguva pfupi yekumhanya (uye nekudaro kuburitswa kazhinji
CPU) uye akati wandei-akareba mabasa anoshandisa iyo CPU nguva yavo yese yekushanda, uku
Nguva yekupindura haina kukosha kumabasa akadaro. Uye nenzira iyi unogona kuita yako yekutanga kuedza
shandisa iyo MLFQ algorithm nemitemo inotevera:
- Mutemo 3: Kana basa rapinda muhurongwa, rinoiswa mumutsetse nepamusoro-soro
- zvakakosha.
- Rule4a: Kana basa richishandisa iyo nguva yese hwindo yakagoverwa kwairi, saka ndizvo
- kukosha kunoderedzwa.
- Mutemo4b: Kana Task ikaburitsa CPU nguva yayo isati yapera, zvobva zvaita
- inoramba ichinyanya kukosha.
Muenzaniso 1: Basa rimwechete kwenguva refu
Sezvinoonekwa mumuenzaniso uyu, basa rekugamuchira rakaiswa nepamusoro-soro
zvakakosha. Mushure menguva yewindo re10ms, maitiro anoderedzwa pamberi
planner. Mushure menguva inotevera hwindo, basa racho rinopedzisira raderedzwa kusvika
yakaderera kukosha muhurongwa, kwainosara.
Muenzaniso 2: Akapa basa pfupi
Zvino ngationei muenzaniso wekuti MLFQ ichaedza sei kusvika kuSJF. Mune izvozvo
somuenzaniso, mabasa maviri: A, rinova basa rinotora nguva refu nguva dzose
kubata CPU uye B, inova ipfupi inopindirana basa. Ngatitii
kuti A akanga atoshanda kwenguva yakati panguva iyo basa B rakasvika.
Iyi girafu inoratidza mhedzisiro yechiitiko. Basa A, senge chero basa,
Kushandiswa kweCPU kwaive kuzasi chaiko. Basa B richasvika panguva T=100 uye richasvika
akaiswa pamutsetse wepamusoro-soro. Sezvo nguva yayo yekushanda ipfupi, saka
ichapedza isati yasvika pamutsetse wekupedzisira.
Kubva pamuenzaniso uyu, chinangwa chikuru chegorgorithm chinofanira kunzwisiswa: sezvo algorithm isingaiti
anoziva kana basa riri refu kana kuti pfupi, ipapo chokutanga anofunga kuti basa racho
pfupi uye inoipa iyo inonyanya kukosha. Kana iri riri basa pfupi chaizvo, ipapo
ichapedzwa nokukurumidza, kana zvisina kudaro kana iri basa rakareba, inofamba zvishoma nezvishoma
pamberi pasi uye achakurumidza kuratidza kuti ibasa rakareba risingaiti
inoda mhinduro.
Muenzaniso 3: Zvakadini neI/O?
Zvino ngatitarisei muenzaniso weI/O. Sezvakataurwa mumutemo 4b,
kana maitiro akaburitsa processor pasina kushandisa ese ayo processor nguva,
zvino inoramba iri padanho rekutanga. Chinangwa chemutemo uyu chiri nyore
- kana basa rinopindirana rinoita mabasa akawanda eI / O, somuenzaniso, kumirira
kubva pakiyi yemushandisi kana mbeva inotsikirira, basa rakadaro rinosunungura processor
pamberi pehwindo rakagoverwa. Hatidi kudzikisa kukosha kwebasa rakadai,
uye nokudaro zvicharamba zviri pamwero mumwe chete.
Uyu muenzaniso unoratidza kuti algorithm ichashanda sei nemaitiro akadaro - inopindirana basa B, inongoda CPU ye1ms isati yaitwa.
I/O process uye yakareba-inomhanya Job A, iyo inoshandisa nguva yayo yese ichishandisa CPU.
MLFQ inochengeta process B iri pamusoro pekutanga nekuti inoenderera
kusunungura CPU. Kana B iri basa rinopindirana, saka algorithm yakawana
Chinangwa chako ndechekumhanyisa mabasa ekudyidzana nekukurumidza.
Matambudziko neazvino MLFQ algorithm
Mumienzaniso yapfuura takavaka vhezheni yekutanga yeMLFQ. Uye zvinoita sokuti iye
inoita basa rayo nemazvo uye nekutendeseka, kugovera CPU nguva zvakaringana pakati
mabasa marefu uye kubvumira mabasa mapfupi kana epamusoro-soro
shanda paI/O nekukurumidza. Zvinosuruvarisa, nzira iyi ine zvakawanda
matambudziko akakomba.
Kutanga, dambudziko renzara: kana iyo system ine akawanda anopindirana
mabasa, ipapo ivo vanozopedza ese processor nguva uye nekudaro kwete imwe chete kwenguva yakareba
basa racho haringagoni kuitwa (vari kufa nenzara).
Chechipiri, vashandisi vakangwara vaigona kunyora mapurogiramu avo kuitira kuti
nyengedza murongi. Unyengeri huri pakuita chimwe chinhu chokumanikidza
Iyo scheduler inopa maitiro akawanda CPU nguva. Algorithm iyoyo
yakatsanangurwa pamusoro iri panjodzi yekurwiswa kwakafanana: nguva isati yasvika hwindo rinenge riripo
yapera, unofanirwa kuita I/O oparesheni (kune vamwe, zvisinei kuti faira ripi)
uye nokudaro kusunungura CPU. Maitiro akadai anozokutendera kuti ugare uri mumwechete
iyo mutsara pachayo uye zvakare uwane yakakura muzana yeCPU nguva. Kana ukadaro
izvi ndizvozvo (semuenzaniso, ita 99% yenguva yehwindo usati waburitsa CPU),
basa rakadaro rinogona kungoita monopolize processor.
Pakupedzisira, purogiramu inogona kuchinja maitiro ayo nekufamba kwenguva. Mabasa iwayo
iyo yakashandisa CPU inogona kupindirana. Mumuenzaniso wedu, zvakafanana
mabasa haagamuchire kurapwa kwaanofanirwa neanoronga kuita sezvaizoitwa nevamwe
(yekutanga) mabasa anopindirana.
Mubvunzo wevateereri: ndekupi kurwiswa kweanoronga kunogona kuitwa munyika yanhasi?
Kuedza 2: Kuwedzera kukosha
Ngatiedze kushandura mitemo uye tione kana tingadzivisa matambudziko nayo
kutsanya. Chii chatingaite kuti tive nechokwadi chekuti zvinoenderana
CPU mabasa achawana nguva yavo (kunyangwe isiri refu).
Semhinduro iri nyore kudambudziko, unogona kupa zano nguva nenguva
simudza kukosha kwemabasa ese akadaro muhurongwa. Kune nzira dzakawanda
Kuti tiite izvi, ngatiedzei kuita chimwe chinhu chiri nyore semuenzaniso: dudzira
mabasa ese anobva apihwa pekutanga, saka mutemo mutsva:
- Mutemo5: Mushure meimwe nguva S, fambisa mabasa ese ari muhurongwa kuenda kumutsara wepamusoro.
Mutemo wedu mutsva unogadzirisa matambudziko maviri panguva imwe chete. Kutanga, maitiro
vanovimbiswa kuti havafe nenzara: mabasa ari epamusoro-soro achakamurwa
CPU nguva zvinoenderana neRR algorithm uye nekudaro maitiro ese anogashira
CPU nguva. Chechipiri, kana imwe nzira yakamboshandiswa
chete processor inova inopindirana, icharamba iri mumutsara nepamusoro-soro
kukoshesa mushure mekugamuchira kuwedzera-kamwe kwekutanga kune yepamusoro-soro.
Ngatitarisei muenzaniso. Muchiitiko ichi, funga imwe nzira yekushandisa
CPU uye maviri anopindirana, mapfupi maitiro. Kuruboshwe mumufananidzo, chimiro chinoratidza maitiro pasina kusimudzirwa kwekutanga, uye nokudaro basa rinotora nguva refu rinotanga kufa nenzara mushure mokunge mabasa maviri anopindirana asvika muhurongwa. Mumufananidzo uri kurudyi, kuwedzera kwekutanga kunoitwa makumi mashanu ega ega uye nekudaro maitiro ese anovimbiswa kugamuchira CPU nguva uye anozotangwa nguva nenguva. 50ms mune iyi kesi inotorwa semuenzaniso; muchokwadi nhamba iyi yakakwira zvishoma.
Zviripachena, kuwedzera nguva yekuwedzera nguva S inotungamira kune
mubvunzo une musoro: chii chinokosha chinofanira kuiswa? Mumwe wevakakudzwa
masisitimu mainjiniya John Ousterhout akadana huwandu hwakadai mumasisitimu sevoo-doo
nguva dzose, sezvo ivo neimwe nzira vaida mashiripiti akashata nokuda kwechokwadi
kuratidza. Uye, zvinosuruvarisa, S ane kunhuhwirira kwakadaro. Kana iwe ukaisa kukosha zvakare
mabasa makuru - akareba achatanga kufa nenzara. Uye kana iwe ukaisa kukosha kwakanyanya kuderera,
Interactive mabasa haagamuchire yakakodzera CPU nguva.
Kuedza 3: Zvirinani Accounting
Iye zvino tine rimwe dambudziko rekugadzirisa: sei kusaita
bvumira kuti murongi wedu anyengedzwe? Vanhu vane mhosva yekugona uku ndivo
mitemo 4a, 4b, iyo inobvumira basa kuchengetedza zvakakosha, kusunungura purogiramu
nguva yakatarwa isati yapera. Ndoita sei neizvi?
Mhinduro mune iyi kesi inogona kutariswa iri nani accounting yeCPU nguva pane yega yega
MLFQ level. Panzvimbo pokukanganwa nguva iyo purogiramu yakashandiswa
processor yenguva yakagoverwa, inofanirwa kuverengerwa uye kuchengetwa. Mushure
iyo nzira yashandisa nguva yayakagoverwa, inofanirwa kudzikiswa kune inotevera
danho rekutanga. Zvino hazvina basa kuti maitiro achashandisa sei nguva yaro - sei
nguva dzose computing pane processor kana sehuwandu hwemafoni. Saka,
mutemo wechi4 unofanirwa kunyorwa zvakare kune inotevera fomu:
- Mutemo4: Mushure mekunge basa rashandisa nguva yaro yakagoverwa mumutsara wazvino (zvisinei kuti kangani kayakasunungura CPU), kukosha kwebasa iro kunodzikiswa (inodzika pasi pemutsara).
Ngatitarisei muenzaniso:
Β»
Nhamba yacho inoratidza zvinoitika kana ukaedza kunyengedza mugadziri, senge
dai yaive nemitemo yapfuura 4a, 4b mhedzisiro kuruboshwe yaizowanikwa. Happy itsva
mutemo ndiwo mugumisiro uri kurudyi. Pamberi pekuchengetedzwa, chero maitiro anogona kufonera I / O isati yapera uye
saka tonga CPU, mushure mekugonesa kuchengetedzwa, zvisinei nemaitiro
I/O, acharamba achifamba pasi mumutsetse uye nokudaro haazokwanisi kusatendeseka
tora CPU zviwanikwa.
Kuvandudza MLFQ nemamwe matambudziko
Nekuvandudzwa kuri pamusoro kunouya matambudziko matsva: chimwe chezvikuru
Mibvunzo - sei parameterize yakadaro scheduler? Avo. Inofanira kuva yakawanda sei
mitsara? Chii chinofanira kuva saizi yehwindo rechirongwa mukati memutsara? Sei
Hurongwa hwekutanga hunofanirwa kuwedzerwa kazhinji kudzivirira nzara uye
uchifunga nezvekuchinja kwemaitiro echirongwa? Hapana mhinduro iri nyore kumibvunzo iyi
mhinduro uye kungoyedza nemitoro uye inozotevera gadziriso
kuronga kunogona kutungamirira kune imwe chiyero chinogutsa.
Semuenzaniso, akawanda MLFQ mashandisirwo anotendera iwe kugovera zvakasiyana
nguva dzenguva dzemitsetse yakasiyana. Mitsetse yakakosha zvikuru kazhinji
nguva pfupi inotarwa. Mitsetse iyi ine mabasa anodyidzana,
kuchinja pakati pezvinonyanya kunzwisisika uye zvinofanirwa kutora gumi kana zvishoma
ms. Kusiyana neizvi, mitsetse yakaderera-inokoshesa inosanganisira mabasa akareba anoshandisa
CPU. Uye mune iyi kesi, nguva refu inopindirana inokodzera chaizvo (100ms).
Mumuenzaniso uyu pane mabasa maviri akashanda mumutsara wepamusoro 2
ms, yakakamurwa kuita 10ms windows. 40ms mumutsara wepakati (20ms hwindo) uye mune yakaderera pamberi
Hwindo renguva yemutsetse rakava 40ms apo mabasa aipedza basa ravo.
Iyo Solaris OS kuitiswa kweMLFQ ikirasi yevanoronga-kugovana nguva.
Murongi achapa seti yematafura anotsanangura chaizvo sezvaanofanira kuita
kukoshesa kwemaitiro kunoshanduka pamusoro pehupenyu hwayo, chii chinofanira kuva hukuru
hwindo rakagoverwa uye kangani iwe waunoda kusimudza zvekutanga basa. Administrator
masisitimu anogona kudyidzana netafura iyi uye kuita kuti mugadziri azvibate
zvakasiyana. Nekutadza, tafura iyi ine 60 mitsetse ine kuwedzera zvishoma nezvishoma
saizi yehwindo kubva pa20ms (yakanyanya kukosha) kusvika kumazana akati wandei ms (yakaderera kukosha), uye
zvakare nekuwedzerwa kwemabasa ese kamwe pasekondi.
Vamwe vanoronga MLFQ havashandise tafura kana chero chaiyo
mitemo inotsanangurwa muhurukuro iyi, pane zvinopesana, ivo vanoverenga zvakakosha vachishandisa
masvomhu formulas. Semuenzaniso, iyo FreeBSD scheduler inoshandisa formula ye
verenga kukosha kwezvino kwebasa zvichienderana nekuti chirongwa chacho chakareba sei
kushandisa CPU. Mukuwedzera, kushandiswa kweCPU kunoora nekufamba kwenguva, uye zvakadaro
Nokudaro, kuwedzera kwekutanga kunoitika zvakasiyana nezvakataurwa pamusoro apa. Ichi ichokwadi
inonzi decay algorithms. Kubva vhezheni 7.1, FreeBSD yashandisa iyo ULE scheduler.
Pakupedzisira, vazhinji vanoronga vane zvimwe zvinhu. Somuenzaniso, zvimwe
vanoronga vanochengeta mazinga epamusoro ekushanda kweiyo inoshanda sisitimu uye nekudaro
Saka, hapana maitiro emushandisi anogona kugamuchira yakanyanya kukosha mukati
system. Mamwe masisitimu anobvumidza iwe kupa zano rekubatsira
murongi anogona kuronga zvinhu zvinokosha nenzira yakarurama. Somuenzaniso, kushandisa murairo zvakanaka
unogona kuwedzera kana kuderedza kukosha kwebasa uye nokudaro kuwedzera kana
kuderedza mikana yepurogiramu yekushandisa CPU nguva.
MLFQ: Pfupiso
Takatsanangura nzira yekuronga inonzi MLFQ. Zita rake
yakavharirwa mumusimboti wekushanda - ine mitsetse yakawanda uye inoshandisa mhinduro
kuona kukosha kwebasa.
Iyo yekupedzisira fomu yemitemo ichave inotevera:
- Mutemo1: Kana zvakakosha (A) > Kukosha (B), basa A richatangwa (B harisi)
- Mutemo2: Kana zvakakosha(A) = Priority(B), A&B inotangwa kushandisa RR
- Mutemo3: Kana basa rapinda muhurongwa, rinoiswa mumutsara wepamusoro-soro.
- Mutemo4: Mushure mekunge basa rashandisa nguva yaro yakagoverwa mumutsara wazvino (zvisinei kuti kangani kayakasunungura CPU), kukosha kwebasa iro kunodzikiswa (inodzika pasi pemutsara).
- Mutemo5: Mushure meimwe nguva S, fambisa mabasa ese ari muhurongwa kuenda kumutsara wepamusoro.
MLFQ inonakidza nekuda kwechikonzero chinotevera - pachinzvimbo chekuda ruzivo nezve
chimiro chebasa pamberi, iyo algorithm inodzidza maitiro ekare ebasa uye seti
zvinokosha maererano. Nokudaro, anoedza kugara pazvigaro zviviri panguva imwe chete - kuti awane chibereko chemabasa maduku (SJF, STCF) uye nekutendeseka kumhanya kwenguva refu,
CPU-kurodha mabasa. Naizvozvo, masisitimu mazhinji, anosanganisira BSD uye zvinobva kwavari,
Solaris, Windows, Mac shandisa imwe nzira yealgorithm semugadziri
MLFQ sechinhu chekutanga.
Zvimwe zvinoshandiswa:
- (computa)
Source: www.habr.com