He Kupu Whakataki ki nga Pūnaha Whakahaere
Hei Habr! E hiahia ana ahau ki te kawe mai ki a koe he raupapa tuhinga-whakamaoritanga o tetahi tuhinga whakamere ki taku whakaaro - OSTEP. Ka tino matapakihia e tenei rauemi nga mahi o nga punaha whakahaere rite-unix, ara, te mahi me nga tikanga, nga momo kaihōtaka, mahara, me etahi atu waahanga rite e hanga ana i te OS hou. Ka taea e koe te kite i te taketake o nga rawa katoa i konei . Kia mahara ko te whakamaoritanga he mea kore noa (he tino kore noa), engari ko taku tumanako ka mau tonu te tikanga whanui.
Ko nga mahi taiwhanga mo tenei kaupapa ka kitea i konei:
Ko etahi atu waahanga:
Ka taea hoki e koe te tirotiro i taku hongere i =)
Te Whakamahere: Te Tutira Whakahoki Taumata-maha
I tenei kauhau, ka korero tatou mo nga raruraru o te whakawhanake i tetahi o nga huarahi tino rongonui
whakamahere, e kiia nei Tūtira Urupare Taumata-maha (MLFQ). I te tuatahi i whakaahuatia te kaiwhakariterite MLFQ i te tau 1962 e Fernando J. Corbató i roto i te punaha e kiia nei
Pūnaha Tiri-wā Hototahi (CTSS). Ko enei mahi (tae atu ki nga mahi a muri ake nei
Multics) i muri mai ka tohua mo te Tohu Turing. Ko te kaihōtaka
i muri mai ka pai ake ka whiwhi i te ahua ka kitea i roto
etahi punaha hou.
Ko te MLFQ algorithm e ngana ana ki te whakaoti rapanga inaki taketake e 2.
Tuatahi, ka ngana ki te arotau i te wa hurihanga, ko ta matou i korero ai i te kauhau o mua, ka whakatikahia e te tikanga timata i te upoko o te rarangi te nuinga.
nga mahi poto. Heoi, kaore te OS e mohio kia pehea te roa o te whakahaere o tetahi mahinga, a ko tenei
matauranga e tika ana mo te mahi o SJF, STCF algorithms. Tuarua, MLFQ ngana
kia aro te punaha ki nga kaiwhakamahi (hei tauira, mo te hunga e noho ana me te
te titiro ki te mata i te wa e tatari ana kia oti te mahi) me te whakaiti i te waa
whakautu. Engari, ko nga algorithms rite RR te whakaiti i te wa whakautu, engari
he painga kino ki te inenga wa huri. No reira to maatau raruraru: Me pehea te hoahoa
he kaihōtaka ka tutuki i a maatau whakaritenga me te kore e mohio ki tetahi mea
te ahua o te tukanga, i te nuinga? Me pehea e ako ai te kaiwhakariterite i nga ahuatanga o nga mahi,
e whakarewahia ana, na reira ka pai ake te whakatau whakaritenga?
Ko te tino o te raruraru: Me pehea te whakamahere i te whakatakotoranga o nga mahi me te kore e tino mohio?
Me pehea te hoahoa i tetahi kaihōtaka ka whakaiti i te wa whakautu
mo nga mahi tauwhitiwhiti me te wa ano ka whakaiti i te wa hurihuri me te kore mohio
te mohio ki te wa mahi mahi?
Tuhipoka: ako mai i nga kaupapa o mua
Ko te rarangi MLFQ he tauira pai mo te punaha e ako ana
nga kaupapa o mua ki te matapae i nga wa kei te heke mai. He maha nga huarahi penei
kitea i roto i te OS (Me te maha atu o nga peka i roto i te pūtaiao rorohiko, tae atu ki nga manga
matapae taputapu me te keteroki hātepe). He rite nga haerenga
ka keu ina he wahanga whanonga nga mahi, na reira ka matapaetia.
Heoi, kia tupato tetahi ki tenei tikanga, no te mea he tino ngawari nga matapae.
ka puta he he ka arahi i te punaha ki te whakatau i te kino atu
kare rawa he matauranga.
MLFQ: Ture Taketake
Whakaarohia nga ture taketake o te MLFQ algorithm. A ahakoa nga whakatinanatanga o tenei algorithm
he maha, he rite tonu nga huarahi taketake.
I roto i te whakatinanatanga ka whakaarohia e matou, he maha nga MLFQ
nga rarangi motuhake, he rereke te kaupapa matua o ia rarangi. I nga wa katoa,
ko te mahi kua reri mo te mahi kei roto i te rarangi kotahi. Ka whakamahi a MLFQ i nga kaupapa matua,
ki te whakatau ko tehea mahi hei whakahaere mo te mahi, i.e. mahi ki runga ake
Ko te kaupapa matua (he mahi mai i te rarangi me te tino kaupapa matua) ka whakarewahia i te tuatahi
tūtira.
Ko te tikanga, ka nui ake i te kotahi nga mahi i roto i tetahi rarangi, na
no reira ka rite tonu te kaupapa matua. I tenei keehi, ka whakamahia te miihini
RR mo te whakamahere whakarewatanga i roto i enei mahi.
No reira ka tae matou ki nga ture matua e rua mo te MLFQ:
- Ture1: Mena ko te kaupapa matua(A) > Manaakitanga(B), ka haere te mahi A (kare a B)
- Ture2: Mena ko te kaupapa matua(A) = Ko te kaupapa matua(B), ka timata a A&B ki te whakamahi i te RR
I runga i nga korero o runga ake nei, ko nga waahanga matua mo te whakamahere MLFQ ko
he kaupapa matua. Engari i te whakatakoto i te kaupapa matua ki ia tangata
mahi, ka huri te MLFQ i tana kaupapa matua i runga i te whanonga i kitea.
Hei tauira, mena ka mutu te mahi i runga i te PTM i te wa e tatari ana mo te whakauru papapātuhi,
Ma te MLFQ e noho matua te tukanga na te mea ka pera
me mahi te tukanga taunekeneke. Ki te, i runga i te anga ke, ko te mahi tonu me
he PTM kaha mo te wa roa, ka whakahekehia e MLFQ
he kaupapa matua. No reira, ka ako a MLFQ i te whanonga o nga tukanga i te wa e rere ana.
me te whakamahi whanonga.
Me tuhi he tauira mo te ahua o nga rarangi i etahi wa
te wa ka whiwhi koe i tetahi mea penei:
I roto i tenei kaupapa, e 2 nga tukanga A me B kei te rarangi me te tino kaupapa matua. Tukanga
Ko C kei waenganui, ko te tukanga D kei te pito rawa o te rarangi. E ai ki nga korero o runga ake nei
Ko nga whakaahuatanga o te MLFQ algorithm, ka mahia e te kaiwhakariterite nga mahi me te teitei
Ko te kaupapa matua e ai ki a RR, ka mutu nga mahi C, D.
Ko te tikanga, karekau he whakaahua pateko e whakaatu te ahua o te mahi a MLFQ.
He mea nui kia marama te ahua o te huringa o te pikitia i roto i te waa.
Nganatanga 1: Me pehea te whakarereke i te kaupapa matua
I tenei wa, me whakatau koe me pehea te whakarereke a MLFQ i te taumata matua
mahi (a ko te tuunga o te mahi i roto i te rarangi) i roto i tona huringa ora. Mo
o tenei, me mahara koe ki te rerenga mahi: he nui
mahi pāhekoheko me ngā wā whakahaere poto (me te tuku auau
CPU) me te maha o nga mahi roa e whakamahi ana i te PTM i o raatau wa mahi katoa, ahakoa
Ko te wa whakautu mo enei mahi ehara i te mea nui. Na ka taea e koe te ngana tuatahi
whakatinana i te MLFQ algorithm me nga ture e whai ake nei:
- Ture3: Ka uru mai tetahi mahi ki te punaha, ka tuu ki te rarangi teitei
- kaupapa matua.
- Ture4a: Mēnā ka whakamahia e tētahi tūmahi tōna matapihi wā katoa, kātahi
- ka whakahekehia te kaupapa matua.
- Ture4b: Mēnā ka tukuna e tētahi Tūmahi te PTM i mua i te paunga o tōna wā matapihi, kātahi ka tukuna
- ka noho tonu ki te kaupapa matua.
Tauira 1: Kotahi te mahi roa
Ka taea e koe te kite i tenei tauira, ko te mahi i te whakaurunga kua whakaritea me te teitei
kaupapa matua. Whai muri i te matapihi o te 10ms, ka whakahekehia te tukanga hei kaupapa matua
kaihōtaka. Whai muri i te matapihi e whai ake nei, ka heke te mahi ki
te kaupapa matua iti rawa i roto i te punaha, kei te noho tonu.
Tauira 2: I kohia he mahi poto
Inaianei kia kite tatou i tetahi tauira o te huarahi ka ngana a MLFQ ki te whakatata atu ki a SJF. I roto i tera
hei tauira, e rua nga mahi: A, he mahi roa i nga wa katoa
e noho ana i te PTM me te B, he mahi whakawhitiwhiti poto. Whakaaro
kua roa ke a A e oma ana i te taenga mai o te mahi B.
Ko tenei kauwhata e whakaatu ana i nga hua o te tauari. Tūmahi A, pērā i ngā mahi katoa,
te whakamahi i te PTM i raro rawa. Ka tae mai a Tūmahi B i te wā T=100 ka tae
ka whakanohoia ki te rarangi matua teitei. I te mea he poto te wa rere,
ka oti i mua i te taenga ki te rarangi whakamutunga.
Mai i tenei tauira, me mohio koe ki te kaupapa matua o te algorithm: na te mea kaore te algorithm
e mohio ana ki te mahi roa, ki te mahi poto ranei, katahi ka whakaaro ia ko te mahi
poto me te hoatu i te kaupapa matua. Mena he mahi poto tenei, na
ka tere te mahi, ki te kore he mahi roa ka ata haere
ka heke iho te kaupapa matua, a ka tata nei ka whakaatu he mahi roa ia kaore e mahi
me whakautu.
Tauira 3: Me pehea te I/O?
Inaianei ka titiro tatou ki tetahi tauira I/O. E ai ki te ture 4b,
ki te tukuna e tetahi tukanga te tukatuka me te kore e tino whakamahi i tona wa tukatuka,
ka noho tonu ki te taumata o te kaupapa matua. He tino ngawari te tikanga o tenei ture.
- mena he maha nga I/O te mahi tauwhitiwhiti, hei tauira, tatari mo
mai i te taviri a te kaiwhakamahi, te pehi kiore ranei, ma te mahi pera ka wetekina te tukatuka
i mua i te matapihi kua tohua. E kore matou e pai ki te whakaheke i te kaupapa matua o taua mahi,
na reira ka noho tonu ki te taumata kotahi.
Ko tenei tauira e whakaatu ana me pehea te mahi a te algorithm me enei momo tukanga - mahi tauwhitiwhiti B, me te PTM anake mo te 1ms i mua i te mahi.
Ko te tukanga I/O me te mahi roa a Job A, e whakapau katoa ana ki te whakamahi i te PTM.
Ko te MLFQ e pupuri ana i te tukanga B hei kaupapa matua na te mea kei te haere tonu
tuku te PTM. Mēnā he mahi pāhekoheko a B, kua tae te hātepe i tēnei take
Ko to whainga kia tere te whakahaere i nga mahi tauwhitiwhiti.
He raru ki te MLFQ algorithm o naianei
I nga tauira o mua, kua hangaia e matou he putanga taketake o MLFQ. A te ahua nei ko ia
he pai, he tika hoki tana mahi, ka tohatoha i te wa PTM i waenga
nga mahi roa me te tuku i nga mahi poto, i nga mahi ranei ka kaha te uru atu
ki I/O kia tere te tukatuka. Kia aroha mai, he maha nga huarahi kei roto
raruraru nui.
Tuatahi, te raruraru o te hiakai: mena he maha nga taunekeneke a te punaha
nga mahi, katahi ka pau katoa nga wa tukatuka, na reira karekau he kotahi mo te wa roa
e kore e whai waahi te mahi kia mahia (kei te hiakai).
Tuarua, ka taea e nga kaiwhakamahi atamai te tuhi i a raatau kaupapa kia penei ai
whakapohehe i te kaihōtaka. Ko te tinihanga kei te mahi i tetahi mea kia kaha ai
kaihōtaka kia nui ake te wa PTM i te tukanga. Ko te algorithm e
Ko nga korero i runga ake nei he tino whakaraerae ki nga whakaeke rite: i mua i te wa e tata ana te matapihi
ka mutu, me mahi koe i tetahi mahi I/O (ki etahi, ahakoa he aha te konae)
a na reira ka wetekina te PTM. Ko taua whanonga ka taea e koe te noho tonu
te tūtira ake ka whiwhi ano i te ōrau nui ake o te wā PTM. Mena kua oti
he tika tenei (hei tauira, whakahaere 99% o te wa matapihi i mua i te tuku i te PTM),
ka taea e taua mahi te whakapouri noa i te tukatuka.
Ka mutu, ka taea e te kaupapa te whakarereke i tana whanonga i roto i te waa. Ko aua mahi
Ko te mea i whakamahia te PTM ka taea te tauwhitiwhiti. I roto i to tatou tauira, rite
e kore nga mahi e whiwhi maimoatanga tika mai i te kaiwhakariterite, pera i etahi atu
(tuatahi) mahi tauwhitiwhiti.
He patai ki te hunga whakarongo: he aha nga whakaeke ki runga i te kaitakataka ka taea te mahi i roto i te ao hou?
Nganatanga 2: Te whakanui ake i te kaupapa matua
Me ngana ki te whakarereke i nga ture ka kite mena ka taea e tatou te karo i nga raru
matekai. He aha ta tatou e mahi hei whakarite i te hono
Ko nga mahi CPU ka whai wa (ahakoa kaore i te roa).
Hei otinga ngawari ki te raru, ka taea e koe te whakaaro i ia wa
whakanuia te kaupapa matua o aua tumahi katoa i roto i te punaha. He maha nga huarahi
ki te whakatutuki i tenei, me ngana ki te whakatinana i tetahi mea ngawari hei tauira: whakamaori
nga mahi katoa i te wa kotahi ki te tino kaupapa matua, no reira te ture hou:
- Ture5: Whai muri i etahi wa S, whakawhitia nga mahi katoa o te punaha ki te rarangi teitei.
Ka whakatauhia e ta maatau ture hou nga raru e rua i te wa kotahi. Tuatahi, ko nga tukanga
e kore e hiakai: ka tohatoha nga mahi i te rarangi teitei
Te wa PTM kia rite ki te RR algorithm a na reira ka whiwhi nga tukanga katoa
wā pūtukatuka. Tuarua, ki te etahi tukanga i whakamahia i mua
ko te pūtukatuka anake ka tauwhitiwhiti, ka noho tonu ki te tūtira me te teitei
te kaupapa matua i muri i te whiwhi i te whakanui ki te kaupapa matua kotahi.
A hi‘o na i te hoê hi‘oraa. I tenei ahuatanga, whakaarohia he mahinga kotahi ma te whakamahi
PTM me nga tukanga whakawhitiwhiti e rua, poto. Kei te taha maui o te ahua, ka whakaatu te ahua i te whanonga kaore he whakanui i te kaupapa matua, na reira ka timata te mahi roa ki te hiakai i muri i te taenga mai o nga mahi tauwhitiwhiti e rua ki te punaha. I roto i te ahua kei te taha matau, ia 50ms ka piki ake te kaupapa matua, na reira ka whakamanahia nga tukanga katoa kia whiwhi wa tukatuka ka timatahia i ia wa. Ko te 50ms i roto i tenei keehi ka tangohia hei tauira, i roto i te pono he ahua teitei ake tenei tau.
E kitea ana ko te taapiri o te wa pikinga S ka arahi ki
pātai arorau: he aha te uara me whakatakoto? Ko tetahi o nga tino tika
Ko nga miihini punaha a John Ousterhout i korero ki nga rahinga rite i roto i nga punaha hei voo-doo
tonu, no te mea i etahi ara e hiahia ana ratou ki te makutu pango mo te tika
whakaatu. A, ko te mea kino, he ahua pera a S. Mena ka whakatauhia e koe te uara
nui - ka matekai nga mahi roa. A, ki te mea ka iti rawa koe,
Ko nga mahi tauwhitiwhiti ka kore e whiwhi i te waa CPU tika.
Nganatanga 3: Pai ake te Kaute
Inaianei kei a matou tetahi atu raruraru hei whakaoti: me pehea e kore ai
tukua ki te tinihanga i to tatou kaihōtaka? Ko te hunga hara mo tenei tupono ko
ture 4a, 4b e tuku ana i te mahi ki te pupuri i tana kaupapa matua ma te whakawātea i te pūtukatuka
i mua i te paunga o te wa i whakaritea. Me pehea te mahi ki a ia?
Ko te otinga i tenei keehi ka taea te whakaaro he pai ake te kaute mo te wa PTM mo ia
taumata MLFQ. Engari o wareware i te wa i whakamahia e te kaupapa
pūtukatuka mo te waahi kua tohua, me whai whakaaro koe me te penapena. I muri
kua pau te wa i whakaritea e te tukanga, me heke ki te waa e whai ake nei
taumata matua. Inaianei kaore he aha me pehea te wa e whakamahia ai e te tukanga - me pehea
te rorohiko i nga wa katoa i runga i te tukatuka, hei huinga waea ranei. No reira,
ture 4 me tuhi ano kia penei:
- Ture4: I muri i te paunga o te wa mahi i te rarangi o naianei (ahakoa te maha o nga wa i wetekina ai te PTM), ka whakahekehia te kaupapa matua o taua mahi (ka neke ki raro i te rarangi).
Kia titiro tatou ki tetahi tauira:
»
Ko te ahua e whakaatu ana ka aha mena ka ngana koe ki te tinihanga i te kaihōtaka penei
mena kei nga ture o mua 4a, ko te 4b te hua kei te taha maui. Me te hou
ko te ture ko te hua kei te taha matau. I mua i te whakamarutanga, ka taea e tetahi tukanga te waea atu ki a I/O i mua i te otinga
na reira te nuinga o te PTM, i muri i taea te tiaki, ahakoa o te whanonga
I/O, ka heke tonu ia ki te rarangi, na reira e kore e taea te mahi he
tango i nga rauemi CPU.
Te whakapai ake i te MLFQ me etahi atu take
Na nga whakapainga i runga ake nei, ka ara ake nga raru hou: tetahi o nga mea matua
nga patai - me pehea te whakarite i te raarangi penei? Ko era. Kia pehea te nui
tūtira? He aha te rahi o te matapihi hotaka i roto i te rarangi? Pehea
He maha nga wa e tika ai te kaupapa matua kia kore ai e matekai
ki te whai whakaaro ki te huringa o te whanonga o te kaupapa? Ki enei patai, kaore he mea ngawari
whakautu me nga whakamatautau anake me nga kawenga me te whirihoranga o muri
Ka taea e te kaihōtaka te arahi ki etahi toenga pai.
Hei tauira, ko te nuinga o nga whakatinanatanga MLFQ ka taea e koe te tautapa rereke
mokamoka wa mo nga rarangi rereke. Ko te nuinga o nga rarangi matua
wā poto. Ko enei rarangi ko nga mahi tauwhitiwhiti,
Ko te huri i waenga he tino tairongo, me 10 iti iho ranei
ms. Engari, ko nga rarangi kaupapa-iti ko nga mahi roa e whakamahi ana
PTM. A, i roto i tenei take, he pai rawa atu nga wa roa (100ms).
I tenei tauira e 2 nga mahi i mahi i te rarangi matua 20
ms kua wehea ki nga matapihi 10ms. 40ms kei te rarangi waenga (20ms matapihi) me te rarangi matua iti
Ko te matapihi wa tūtira kua 40ms i oti ai a raatau mahi.
Ko te whakatinanatanga o te MLFQ i roto i te Solaris OS he karaehe o nga kaiwhakariterite-waahi.
Ka whakaratohia e te kaihōtaka he huinga ripanga e whakaatu tika ana me pehea
ka huri te kaupapa matua o te tukanga i te roanga o tona oranga, me pehea te rahi
matapihi hei tohatoha me te maha o nga wa ki te whakaara i nga kaupapa matua. Kaiwhakahaere
Ka taea e nga punaha te pahekoheko me tenei ripanga me te mahi a te kaihōtaka
rerekē. Ma te taunoa, e 60 nga rarangi o tenei ripanga me te piki haere
te rahi o te matapihi mai i te 20ms (ko te kaupapa matua) ki te maha rau ms (te kaupapa matua iti), a
me te whakanui i nga mahi katoa kotahi mo ia hekona.
Ko etahi atu kaiwhakarite MLFQ kaore i te whakamahi i te tepu, i tetahi mea motuhake ranei
nga ture e whakaahuatia ana i roto i tenei upoko, i runga i te anga ke, ka tatau ratou kaupapa matua te whakamahi
tātai pāngarau. Hei tauira, ka whakamahia e te kaihōtaka i FreeBSD he tauira mo
te tātai i te kaupapa matua o nāianei i runga i te nui o te hātepe
whakamahia te PTM. I tua atu, ka pirau te whakamahinga CPU i te wa, a na reira
No reira, he rereke te pikinga o te kaupapa matua i te korero i runga ake nei. He pono tenei
e kiia ana ko te pirau algorithms. Mai i te putanga 7.1, kua whakamahia e FreeBSD te ULE scheduler.
Ka mutu, he maha nga kaiwhakatakoto kaupapa kei etahi atu ahuatanga. Hei tauira, etahi
Ka rahuihia e nga kaiwhakarite nga taumata teitei ake mo te mahi o te punaha whakahaere me te penei
No reira, karekau he tukanga kaiwhakamahi e uru ki te kaupapa matua
pūnaha. Ko etahi punaha ka taea e koe te tuku tohutohu hei awhina
ka taea e te mahere te whakarite tika i nga kaupapa matua. Hei tauira, te whakamahi i te whakahau nehenehe
ka taea e koe te whakanui ake, te whakaheke ranei i te kaupapa matua o tetahi mahi, na reira ka piki ake ranei
whakaitihia nga tupono o te kaupapa mo te wa PTM.
MLFQ: Whakarāpopototanga
Kua whakaahuatia e matou he huarahi whakamahere e kiia nei ko MLFQ. Tona ingoa
ka mutu i roto i te kaupapa o te mahi - he maha nga rarangi me te whakamahi urupare
ki te whakatau i te kaupapa matua.
Ko te ahua whakamutunga o nga ture e whai ake nei:
- Ture1: Ki te kaupapa matua(A) > Manaakitanga(B), ka haere te mahi A (kaore a B)
- Ture2: Mena ko te kaupapa matua(A) = Ko te kaupapa matua(B), ka timatahia a A&B ki te whakamahi i te RR
- Ture3: Ka uru mai tetahi mahi ki te punaha, ka tuu ki te rarangi matua teitei.
- Ture4: I muri i te paunga o te wa mahi i te rarangi o naianei (ahakoa te maha o nga wa i wetekina ai te PTM), ka whakahekehia te kaupapa matua o taua mahi (ka neke ki raro i te rarangi).
- Ture5: Whai muri i etahi wa S, whakawhitia nga mahi katoa o te punaha ki te rarangi teitei.
He rawe te MLFQ mo te take e whai ake nei - hei utu mo te rapu matauranga mo
te ahua o te mahi i mua, ka ako te algorithm i te whanonga o mua o te mahi me nga huinga
nga kaupapa matua i runga i tera. No reira, ka ngana ia ki te noho ki runga i nga tuuru e rua i te wa kotahi - ki te whakatutuki i nga hua mo nga mahi iti (SJF, STCF) me te pono o te oma roa,
Nga mahi uta CPU. No reira, he maha nga punaha, tae atu ki te BSD me o raatau hua,
Ka whakamahia e Solaris, Windows, Mac etahi ahua o te algorithm hei kaiwhakarite
MLFQ hei turanga.
Rauemi taapiri:
- (rorohiko)
Source: will.com