Hoʻolauna i nā ʻōnaehana hana
E Habr! Makemake wau e lawe i kou manaʻo i kahi ʻatikala-unuhi o kahi palapala hoihoi i koʻu manaʻo - OSTEP. Kūkākūkā hohonu kēia mea i ka hana o nā ʻōnaehana hana unix-like, ʻo ia hoʻi, ka hana me nā kaʻina hana, nā mea hoʻonohonoho like ʻole, ka hoʻomanaʻo, a me nā mea like ʻē aʻe i kūkulu i kahi OS hou. Hiki iā ʻoe ke ʻike i ke kumu o nā mea a pau ma aneʻi . E ʻoluʻolu e hoʻomaopopo ʻoe ua hana ʻia ka unuhi me ka ʻole o ka ʻoihana (me ke kūʻokoʻa), akā ke manaʻo nei au ua paʻa ka manaʻo nui.
Hiki ke loaʻa ka hana lab ma kēia kumuhana ma aneʻi:
Nā ʻāpana ʻē aʻe:
Hiki iā ʻoe ke nānā i kaʻu channel ma =)
Introduction to Scheduler
ʻO ke kumu o ka pilikia: Pehea e hoʻomohala ai i kahi kulekele hoʻonohonoho
Pehea e hoʻolālā ʻia ai nā ʻōnaehana kulekele hoʻonohonoho kumu? He aha nā manaʻo nui e pono ai? He aha nā mea nui? He aha nā ʻenehana kumu i hoʻohana ʻia i nā ʻōnaehana helu mua?
Nā Manaʻo Kau Hana
Ma mua o ke kūkākūkā ʻana i nā kulekele hiki, e hana mua kākou i kekahi mau hoʻokaʻawale maʻalahi e pili ana i nā kaʻina hana e holo ana i ka ʻōnaehana, i kapa ʻia i hui pū ʻia. kaumaha hana. ʻO ka wehewehe ʻana i ka haʻahaʻa hana he ʻāpana koʻikoʻi ia o nā kulekele kūkulu hale, a ʻoi aku ka nui o kou ʻike e pili ana i ka hana, ʻoi aku ka maikaʻi o ke kulekele hiki iā ʻoe ke kākau.
E hana kākou i kēia mau manaʻo e pili ana i nā kaʻina hana i loko o ka ʻōnaehana, i kapa ʻia kekahi manawa hana (nā hana). ʻAʻole kūpono kēia mau manaʻo a pau, akā pono no ka ulu ʻana o ka manaʻo.
- Holo kēlā me kēia hana no ka manawa like,
- Hoʻonohonoho ʻia nā hana a pau i ka manawa like,
- Hana ʻia ka hana i hāʻawi ʻia a hiki i ka pau ʻana,
- Hoʻohana nā hana a pau i ka CPU wale nō,
- ʻIke ʻia ka manawa holo o kēlā me kēia hana.
Nā Ana Hoʻonohonoho
Ma waho aʻe o kekahi mau manaʻo e pili ana i ka ukana, pono kekahi mea hana no ka hoʻohālikelike ʻana i nā kulekele hoʻonohonoho like ʻole: nā metric scheduler. ʻO ka metric kahi ana o kekahi mea. Aia kekahi mau metric i hiki ke hoʻohana ʻia e hoʻohālikelike i nā mea hoʻonohonoho.
No ka laʻana, e hoʻohana mākou i kahi metric i kapa ʻia manawa huli (ka manawa huli). Ua wehewehe ʻia ka manawa hoʻohuli hana ma ke ʻano he ʻokoʻa ma waena o ka manawa hoʻopau hana a me ka manawa hōʻea hana ma ka ʻōnaehana.
Tturnaround=Tcompletion−Tarrival
No ka mea, ua manao makou ua hiki mai na hana a pau i ka manawa hookahi, alaila Ta=0 a pela Tt=Tc. E loli maoli kēia waiwai ke hoʻololi mākou i nā manaʻo i luna.
ʻO kekahi metric - pololei (fairness, honesty). ʻO ka huahana a me ka pololei ke kū'ē pinepine i nā hiʻohiʻona i ka hoʻolālā. No ka laʻana, hiki i ka mea hoʻonohonoho ke hoʻokō i ka hana, akā ma ke kumukūʻai o ke kali ʻana i nā hana ʻē aʻe e holo, pēlā e hōʻemi ai i ka pono.
MUA I KA MUA I PUKA (FIFO)
ʻO ka algorithm maʻamau i hiki iā mākou ke hoʻokō i kapa ʻia ʻo FIFO a i ʻole hele mua (i loko), lawelawe mua (waho). He nui nā pono o kēia algorithm: he maʻalahi loa ia e hoʻokō a kūpono i kā mākou mau manaʻo āpau a hana maikaʻi i ka hana.
E nānā kākou i kahi laʻana maʻalahi. E ʻōlelo kākou ua hoʻonohonoho ʻia nā hana 3 i ka manawa like. Akā, e noʻonoʻo kākou ua hiki mai ka hana A ma mua o nā mea ʻē aʻe, no laila e ʻike ʻia ma ka papa inoa hoʻokō ma mua o nā mea ʻē aʻe, e like me B pili iā C. E manaʻo mākou e hoʻokō ʻia kēlā me kēia o lākou no 10 kekona. He aha ka manawa maʻamau e hoʻopau ai i kēia mau hana ma kēia hihia?
Ma ka helu ʻana i nā waiwai - 10 + 20 + 30 a me ka puʻunaue ʻana i ka 3, loaʻa iā mākou ka manawa hoʻokō o ka papahana e like me 20 kekona.
I kēia manawa e ho'āʻo kāua e hoʻololi i kā mākou mau manaʻo. Ma keʻano, manaʻo 1 a no laila ʻaʻole mākou e manaʻo hou e lawe kēlā me kēia hana i ka manawa like e hoʻokō ai. Pehea e hana ai ka FIFO i kēia manawa?
E like me ka mea i ʻike ʻia, ʻokoʻa nā manawa hoʻokō hana i ka hopena maikaʻi ʻole i ka huahana o ka FIFO algorithm. E noʻonoʻo kākou he 100 kekona ke hoʻopau ʻana o ka hana A, ʻoiai ʻo B a me C he 10 kekona.
E like me ka mea i ʻike ʻia ma ke kiʻi, ʻo ka manawa maʻamau no ka ʻōnaehana (100+110+120)/3=110. Kapa ʻia kēia hopena hopena convoy, i ka wā e laina ai kekahi mau mea kūʻai aku no ka wā pōkole ma hope o ka mea kūʻai kaumaha. Ua like ia me ka laina ma ka hale kūʻai ke loaʻa kahi mea kūʻai i mua ou me kahi kaʻa piha. ʻO ka hopena maikaʻi loa i ka pilikia e hoʻāʻo e hoʻololi i ka waihona kālā a hoʻomaha paha a hanu hohonu.
ʻO ka hana pōkole loa
Hiki paha ke hoʻoponopono i kahi kūlana like me nā kaʻina kaumaha kaumaha? ʻOiaʻiʻo. Ua kapa ʻia kekahi ʻano hoʻolālāʻO ka hana pōkole loa (SJF). He mea kahiko loa kona algorithm - e like me ka inoa, e hoʻomaka mua ʻia nā hana pōkole loa, kēlā me kēia.
Ma kēia hiʻohiʻona, ʻo ka hopena o ka holo ʻana i nā kaʻina like e hoʻomaikaʻi i ka manawa hoʻololi o ka papahana a ua like ia me 50 ma kahi o 110, ʻaneʻane 2 manawa ʻoi aku ka maikaʻi.
No laila, no ka manaʻo i hāʻawi ʻia e hiki mai nā hana āpau i ka manawa like, ʻo ka SJF algorithm ka mea ʻoi loa ka algorithm. Eia naʻe, ʻaʻole ʻike maoli kā mākou mau manaʻo. I kēia manawa, hoʻololi mākou i ka manaʻo 2 a i kēia manawa e noʻonoʻo e hiki ke loaʻa nā hana i kēlā me kēia manawa, ʻaʻole i ka manawa like. He aha nā pilikia e hiki ke alakaʻi i kēia?
E noʻonoʻo kākou ua hiki mua ka hana A (100c) a hoʻomaka e hoʻokō ʻia. Ma ka t=10, hiki mai nā hana B a me C, he 10 kekona ka lōʻihi o kēlā me kēia. No laila, ʻo ka manawa hoʻokō maʻamau (100+(110-10)+(120-10))3 = 103. He aha ka mea hiki i ka mea hoʻonohonoho ke hana e hoʻomaikaʻi i kēia?
ʻO ka manawa pōkole loa i ka hoʻopau mua ʻana (STCF)
I mea e hoʻomaikaʻi ai i ke kūlana, haʻalele mākou i ka manaʻo 3 ua hoʻomaka ka papahana a holo a hiki i ka pau ʻana. Eia hou, pono mākou i ke kākoʻo ʻenehana a, e like me kāu e manaʻo ai, e hoʻohana mākou ʻano manawa e hoopau i ka hana holo a hoʻololi pōʻaiapili. No laila, hiki i ka mea hoʻonohonoho ke hana i kekahi mea i ka manawa e hiki mai ai nā hana B, C - ho'ōki i ka hoʻokō ʻana i ka hana A a hoʻokomo i nā hana B a me C i ka hana ʻana a, ma hope o ka pau ʻana, e hoʻomau i ka hoʻokō ʻana i ke kaʻina hana A. STCFai ole ia, ʻO ka hana mua.
ʻO ka hopena o kēia mea hoʻolālā ka hopena penei: ((120-0)+(20-10)+(30-10))/3=50. No laila, ʻoi aku ka maikaʻi o ia mea hoʻonohonoho no kā mākou mau hana.
Manawa Pane Metric
No laila, inā ʻike mākou i ka manawa holo o nā hana a hoʻohana wale kēia mau hana i ka CPU, ʻo STCF ka hopena maikaʻi loa. A i ka wā mua, ua hana maikaʻi kēia mau algorithm. Eia nō naʻe, ke hoʻohana nei ka mea hoʻohana i ka hapa nui o kona manawa ma ke kikowaena a ke manaʻo nei i kahi ʻike pili pono. No laila ua hānau ʻia kahi metric hou - manawa pane (pane).
Ua helu ʻia ka manawa pane penei:
Tresponse=Tfirstrun−Tarrival
No laila, no ka laʻana mua, ʻo ka manawa pane: A=0, B=0, C=10 (abg=3,33).
A ua ʻike ʻia ʻaʻole maikaʻi loa ka STCF algorithm i kahi kūlana e hiki mai ai nā hana 3 i ka manawa like - pono ia e kali a pau nā hana liʻiliʻi. No laila maikaʻi ka algorithm no ka metric manawa huli, akā maikaʻi ʻole no ka metric interactivity. E noʻonoʻo ʻoe inā ʻoe e noho ana ma kahi pahu e hoʻāʻo nei e paʻi i nā huaʻōlelo i loko o kahi mea hoʻoponopono a e kali ʻoi aku ma mua o 10 kekona no ka mea e lawe ana kekahi hana ʻē aʻe i ka CPU. ʻAʻole ʻoluʻolu loa.
No laila ke alo nei mākou i kahi pilikia ʻē aʻe - pehea e hiki ai iā mākou ke kūkulu i kahi mea hoʻonohonoho e maʻalahi i ka manawa pane?
ʻO Robin Robin
Ua kūkulu ʻia kahi algorithm e hoʻoponopono i kēia pilikia ʻO Robin Robin (RR). He mea maʻalahi ka manaʻo kumu: ma kahi o ka holo ʻana i nā hana a hiki i ka pau ʻana, e holo mākou i ka hana no kekahi manawa (i kapa ʻia he ʻāpana manawa) a laila hoʻololi i kahi hana ʻē aʻe mai ka pila. Hoʻopau ka algorithm i kāna hana a hiki i ka pau ʻana o nā hana a pau. I kēia hihia, ʻo ka manawa holo o ka papahana he mau manawa ma hope o ka manawa e hoʻopau ai ke kaʻina hana. No ka laʻana, inā hoʻopau ka manawa i ke kaʻina hana i kēlā me kēia x=10ms, a laila ʻo ka nui o ka puka makani hoʻokō kaʻina he 10 a he 10,20 a i ʻole x*10.
E nānā kākou i kekahi laʻana: Hiki mai nā hana ABC i ka manawa like i ka ʻōnaehana a makemake kēlā me kēia o lākou e holo no 5 kekona. E hoʻopau ka SJF algorithm i kēlā me kēia hana ma mua o ka hoʻomaka ʻana i kekahi. I ka hoʻokaʻawale ʻana, e hele ka RR algorithm me ka puka makani hoʻomaka = 1s i nā hana penei (Fig. 4.3):
(SJF Hou (He ino no ka manawa pane)
(Round Robin (maikaʻi no ka manawa pane)
ʻO ka manawa pane maʻamau no ka RR algorithm he (0+1+2)/3=1, ʻoiai no ka SJF (0+5+10)/3=5.
Maikaʻi ka manaʻo he mea koʻikoʻi ka puka makani manawa no RR; ʻo ka liʻiliʻi, ʻoi aku ka kiʻekiʻe o ka manawa pane. Eia naʻe, ʻaʻole pono ʻoe e liʻiliʻi loa, no ka mea, e pāʻani pū ana ka manawa hoʻololi pōʻaiapili i ka hana holoʻokoʻa. No laila, ua hoʻonohonoho ʻia ke koho o ka manawa puka makani e ka OS architect a hilinaʻi i nā hana i hoʻolālā ʻia e hoʻokō ʻia i loko. ʻO ka hoʻololi ʻana i ka pōʻaiapili ʻaʻole wale ka hana lawelawe e hoʻopau i ka manawa - ke holo nei ka papahana holo i nā mea ʻē aʻe he nui, no ka laʻana, nā huna huna like ʻole, a me kēlā me kēia hoʻololi e pono ai e mālama a hoʻihoʻi i kēia kaiapuni, hiki ke lawe i nā mea he nui. manawa.
He mea hoʻonohonoho maikaʻi ʻo RR inā mākou e kamaʻilio e pili ana i ka metric manawa pane. Akā, pehea e hana ai ka metric manawa huli hana me kēia algorithm? E noʻonoʻo i ka laʻana ma luna, i ka manawa hana o A, B, C = 5s a hiki i ka manawa like. E pau ana ka hana A ma 13, B ma 14, C ma 15s a he 14s ka awelika o ka manawa huli. No laila, ʻo RR ka algorithm maikaʻi loa no ka metric turnover.
Ma nā ʻōlelo maʻamau, kūpono kēlā me kēia RR-type algorithm; e puʻunaue like i ka manawa CPU ma waena o nā kaʻina hana. A no laila, hakakā mau kēia mau ana me kekahi.
No laila, loaʻa iā mākou nā algorithms like ʻole a i ka manawa like aia kekahi mau manaʻo i koe - ʻike ʻia ka manawa hana a hoʻohana wale ka hana i ka CPU.
Ka hui ʻana me I/O
ʻO ka mea mua, e wehe i ka manaʻo 4 e hoʻohana wale ana ke kaʻina hana i ka CPU; maʻamau, ʻaʻole kēia ka hihia a hiki i nā kaʻina ke komo i nā mea hana ʻē aʻe.
I ka manawa e noi ai kekahi kaʻina hana i kahi hana I/O, komo ke kaʻina hana i ka mokuʻāina i hoʻopaʻa ʻia, e kali ana i ka pau ʻana o ka I/O. Inā hoʻouna ʻia ʻo I/O i ka paʻa paʻa, a laila hiki ke lawe ʻia kēlā hana i kekahi mau ms a i ʻole ka lōʻihi, a ʻo ka mea hana i kēia manawa. I kēia manawa, hiki i ka mea hoʻonohonoho ke hoʻopaʻa i ke kaʻina hana me nā kaʻina hana ʻē aʻe. ʻO ka hoʻoholo aʻe e hana ai ka mea hoʻonohonoho i ka wā e hoʻopau ai ke kaʻina hana i kāna I/O. Ke hana ʻia kēia, e hoʻopau ʻia a hoʻokomo ka OS i ke kaʻina hana i kapa ʻia ka I/O i loko o ke kūlana mākaukau.
E nānā kākou i kekahi laʻana o kekahi mau hana. Pono kēlā me kēia o lākou i 50ms o ka manawa CPU. Eia naʻe, hiki i ka mea mua ke komo i ka I/O i kēlā me kēia 10ms (e hoʻokō ʻia i kēlā me kēia 10ms). A hoʻohana wale ke kaʻina B i kahi kaʻina hana 50ms me ka ʻole o I/O.
Ma kēia hiʻohiʻona e hoʻohana mākou i ka mea hoʻonohonoho STCF. Pehea e hana ai ka mea hoʻonohonoho inā hoʻomaka ʻia kahi kaʻina hana e like me A? E hana ʻo ia i kēia: ʻo ka mua e hana pono ʻo ia i ke kaʻina A, a laila kaʻina B.
ʻO ke ala kuʻuna e hoʻoponopono ai i kēia pilikia, ʻo ia ke mālama i kēlā me kēia 10 ms subtask o ke kaʻina A ma ke ʻano he hana kaʻawale. No laila, i ka hoʻomaka ʻana me ka STJF algorithm, ʻike ʻia ka koho ma waena o kahi hana 50 ms a me kahi hana 10 ms. A laila, ke pau ka subtask A, e hoʻomaka ke kaʻina hana B a me I/O. Ma hope o ka pau ʻana o ka I / O, he mea maʻamau ia e hoʻomaka hou i ke kaʻina 10ms A ma mua o ke kaʻina B. Ma kēia ala, hiki ke hoʻokō i ka overlap, kahi e hoʻohana ʻia ai ka CPU e kekahi kaʻina hana ʻoiai ke kali nei ka mea mua i ka I/O. A ʻo ka hopena, ʻoi aku ka maikaʻi o ka hoʻohana ʻana i ka ʻōnaehana - i ka manawa ke kali nei nā kaʻina hana pili no I/O, hiki ke hoʻokō ʻia nā kaʻina hana ʻē aʻe ma ka processor.
ʻAʻole hou ka Oracle
I kēia manawa e hoʻāʻo kākou e kāpae i ka manaʻo ua ʻike ʻia ka manawa holo o ka hana. ʻO kēia ka manaʻo maikaʻi ʻole a pololei ʻole ma ka papa inoa holoʻokoʻa. ʻO ka ʻoiaʻiʻo, i ka OS maʻamau maʻamau, ʻike liʻiliʻi ka OS ponoʻī e pili ana i ka manawa hoʻokō o nā hana, no laila pehea ʻoe e kūkulu ai i kahi mea hoʻonohonoho me ka ʻike ʻole i ka lōʻihi o ka hana e hoʻokō ai? Hiki paha iā mākou ke hoʻohana i kekahi mau loina RR e hoʻoponopono i kēia pilikia?
ʻO ka hopena
Ua nānā mākou i nā manaʻo kumu o ka hoʻonohonoho hana a nānā i nā ʻohana 2 o nā mea hoʻonohonoho. Hoʻomaka ka mea mua i ka hana pōkole ma mua a pēlā e hoʻonui ai i ka manawa huli, aʻo ka lua e haehae ʻia ma waena o nā hana āpau, e hoʻonui ana i ka manawa pane. He maikaʻi nā algorithm ʻelua kahi i maikaʻi ai nā algorithms o ka ʻohana ʻē aʻe. Ua nānā pū mākou i ka hoʻohana like ʻana o ka CPU a me I/O hiki ke hoʻomaikaʻi i ka hana, akā ʻaʻole i hoʻoponopono i ka pilikia me OS clairvoyance. A ma ka haʻawina aʻe, e nānā mākou i kahi mea hoʻolālā e nānā i ka wā i hala koke a hoʻāʻo e wānana i ka wā e hiki mai ana. A ua kapa ʻia ʻo ia ka pila manaʻo multi-level.
Source: www.habr.com