Intshayelelo kwiiNkqubo zokuSebenza
Hayi Habr! Ndingathanda ukuzisa ingqalelo yakho uluhlu lwamanqaku-iinguqulelo zoncwadi olulodwa olunomdla ngombono wam - i-OSTEP. Esi sixhobo sixoxa nzulu ngomsebenzi weenkqubo zokusebenza ezifana ne-unix, ezizezi, ukusebenza kunye neenkqubo, abacwangcisi abahlukeneyo, imemori, kunye namanye amacandelo afanayo enza i-OS yanamhlanje. Ungayibona imvelaphi yazo zonke izixhobo apha . Nceda uqaphele ukuba uguqulelo lwenziwe ngokungenamsebenzi (ngokukhululekileyo kakhulu), kodwa ndiyathemba ukuba ndiyigcinile intsingiselo ngokubanzi.
Umsebenzi waseLebhu ngalo mbandela unokufumaneka apha:
Amanye amalungu:
Ungajonga kwakhona itshaneli yam ku =)
Intshayelelo kuMcwangcisi
Undoqo wengxaki: Uqulunqwa njani umgaqo-nkqubo womcwangcisi
Ingaba izikhokelo zomgaqo-nkqubo womcwangcisi osisiseko kufuneka ziyilwe njani? Ziziphi iingqikelelo eziphambili? Zeziphi iimetrikhi ezibalulekileyo? Zeziphi iindlela ezisisiseko ezisetyenzisiweyo kwiinkqubo zekhompyutha zakuqala?
Iingqikelelo zomthwalo womsebenzi
Phambi kokuba sixoxe ngemigaqo-nkqubo enokwenzeka, masiqale senze uphambuko olumbalwa olulula malunga neenkqubo ezisebenza kwinkqubo, ezibizwa ngokudibeneyo. umthwalo womsebenzi. Ukuchaza umthwalo womsebenzi yinxalenye ebalulekileyo yemigaqo-nkqubo yokwakha, kwaye xa usazi ngakumbi malunga nomsebenzi, ngcono umgaqo-nkqubo onokuthi uwubhale.
Masenze ezi ngqikelelo zilandelayo malunga neenkqubo ezisebenza kwinkqubo, ngamanye amaxesha ikwabizwa ngokuba imisebenzi (imisebenzi). Phantse zonke ezi ngcinga aziyonyani, kodwa ziyimfuneko kuphuhliso lwengcinga.
- Umsebenzi ngamnye uqhuba ixesha elifanayo.
- Yonke imisebenzi isetwa ngaxeshanye,
- Umsebenzi owabelweyo usebenza de ugqitywe,
- Yonke imisebenzi isebenzisa kuphela i-CPU,
- Ixesha lokuqhuba komsebenzi ngamnye liyaziwa.
Iimetriki zoMcwangcisi
Ukongeza kwezinye iingqikelelo malunga nomthwalo, esinye isixhobo sokuthelekisa imigaqo-nkqubo eyahlukeneyo yokucwangcisa iyafuneka: iimethrikhi zomcwangcisi. I-metric ngumlinganiselo nje wento ethile. Kukho inani leemetriki ezinokusetyenziswa ukuthelekisa abacwangcisi.
Umzekelo, siya kusebenzisa i-metric ebizwa ngokuba ixesha lokuguqula (ixesha lokutshintsha). Ixesha lokuguqula umsebenzi lichazwa njengomahluko phakathi kwexesha lokugqitywa komsebenzi kunye nexesha lokufika komsebenzi kwinkqubo.
Tturnaround=Ukugqitywa−ITarrival
Okoko sicinge ukuba yonke imisebenzi ifike ngexesha elinye, emva koko u-Ta=0 kwaye ngaloo ndlela u-Tt=Tc. Eli xabiso liya kutshintsha ngokwemvelo xa sitshintsha ezi ngqikelelo zingentla.
Enye i-metric - ngokulinganayo (ubulungisa, ukunyaniseka). Imveliso kunye nobulungisa zihlala zichasa iimpawu ekucwangciseni. Ngokomzekelo, umcwangcisi unokwandisa ukusebenza, kodwa ngeendleko zokulinda eminye imisebenzi ukuba iqhube, ngaloo ndlela inciphisa ubulungisa.
OKOKUQALA KUQALA (FIFO)
Eyona algorithm isisiseko esinokuyiphumeza ibizwa ngokuba yiFIFO okanye kuqala yiza (ngaphakathi), kuqala inikezelwe (ngaphandle). Le algorithm ineenzuzo ezininzi: kulula kakhulu ukuyiphumeza kwaye ihambelana nazo zonke izinto esizicingelayo kwaye yenza umsebenzi kakuhle.
Makhe sijonge umzekelo olula. Masithi imisebenzi emi-3 yayisetwa ngaxeshanye. Kodwa makhe sicinge ukuba umsebenzi A ufikile kancinane kunabo bonke abanye, ngoko kuya kubonakala kuluhlu lokuphumeza ngaphambili kunabanye, njengoB uhlobene noC. Makhe sicinge ukuba ngamnye wabo uya kuphunyezwa imizuzwana eyi-10. Iyakuba lixesha elingakanani ukugqiba le misebenzi kule meko?
Ngokubala amaxabiso - 10+20+30 kunye nokwahlula ngo-3, sifumana umndilili wexesha lokwenziwa kwenkqubo elilingana nemizuzwana engama-20.
Ngoku makhe sizame ukutshintsha iingcinga zethu. Ngokukodwa, ukucinga 1 kwaye ngoko asisayi kuphinda sicinge ukuba umsebenzi ngamnye uthatha ixesha elifanayo lokuphumeza. Iza kwenza njani i-FIFO ngeli xesha?
Njengoko kuvela, amaxesha ahlukeneyo okwenziwa komsebenzi anempembelelo embi kakhulu kwimveliso ye-algorithm ye-FIFO. Masicinge ukuba umsebenzi A uyakuthatha imizuzwana eli-100 ukuwugqiba, ngelixa u-B no-C besaya kuthatha imizuzwana eli-10 inye.
Njengoko kunokubonwa kumfanekiso, ixesha eliqhelekileyo lenkqubo liya kuba (100+110+120)/3=110. Esi siphumo sibizwa ngokuba isiphumo convoy, xa abanye abathengi bexesha elifutshane besixhobo beza kufola emva komthengi onzima. Kufana nomgca kwivenkile yokutya xa kukho umthengi phambi kwakho ophethe inqwelo egcweleyo. Isisombululo esona sisombululo sengxaki kukuzama ukutshintsha irejista yemali okanye uphumle kwaye uphefumle ngokunzulu.
Umsebenzi oMfutshane kuqala
Ngaba kunokwenzeka ukuba ngandlela-thile ukusombulula imeko efanayo kunye neenkqubo ezinzima? Ngokuqinisekileyo. Olunye uhlobo lokucwangcisa lubizwa ngokubaUmsebenzi oMfutshane kuqala (SJF). I-algorithm yayo ikwayeyakudala - njengoko negama lisitsho, eyona misebenzi imfutshane iya kusungulwa kuqala, omnye emva komnye.
Kulo mzekelo, isiphumo sokuqhuba iinkqubo ezifanayo siya kuba luphuculo kwi-avareji yexesha lokuguqula inkqubo kwaye iyakulingana 50 endaweni yama-110, ephantse ibe ngama-2 amaxesha angcono.
Ngaloo ndlela, kwingcinga enikiweyo yokuba yonke imisebenzi ifika ngexesha elinye, i-algorithm ye-SJF ibonakala iyona ndlela iphezulu ye-algorithm. Nangona kunjalo, iingcinga zethu azikabonakali zisengqiqweni. Ngeli xesha sitshintsha ukucinga kwe-2 kwaye ngeli xesha sicinga ukuba imisebenzi ingaba khona nangaliphi na ixesha, kwaye kungekhona yonke ngexesha elinye. Zeziphi iingxaki oku kunokukhokelela kuzo?
Masicinge ukuba umsebenzi A (100c) ufika kuqala kwaye uqalise ukwenziwa. Ku-t=10, imisebenzi B no-C iyafika, nganye kuzo iza kuthatha imizuzwana eli-10. Ngoko ke umndilili wexesha lokwenziwa ngu (100+(110-10)+(120-10))3 = 103. Yintoni anokuyenza umcwangcisi ukuphucula oku?
Elona xesha lifutshane lokuQeda kuqala (STCF)
Ukuze kuphuculwe imeko, siyayishiya i-asumption 3 yokuba inkqubo iqalisiwe kwaye iqhuba ide igqitywe. Ukongeza, siya kufuna inkxaso yehardware kwaye, njengoko unokuqikelela, siya kusebenzisa ixesha ukuphazamisa umsebenzi oqhubayo kunye ukutshintsha umxholo. Ngaloo ndlela, umcwangcisi angenza into ngexesha imisebenzi B, C ifika - bayeke ukwenza umsebenzi A kwaye babeke imisebenzi B kunye no-C ekuqhubeni kwaye, emva kokugqitywa kwayo, baqhubeke beqhuba inkqubo A. Umcwangcisi onjalo ubizwa ngokuba ngumcwangcisi. STCFokanye Umsebenzi wokuQala kuqala.
Isiphumo somcwangcisi siya kuba sisiphumo esilandelayo: ((120-0)+(20-10)+(30-10))/3=50. Ke, umcwangcisi onjalo uba ngoyena ufanelekileyo ngakumbi kwimisebenzi yethu.
Ixesha leMetric yokuPhendula
Ke, ukuba siyalazi ixesha elisebenzayo lemisebenzi kwaye le misebenzi isebenzisa kuphela i-CPU, i-STCF iya kuba sisisombululo esihle. Kwaye kanye kumaxesha okuqala, ezi algorithms zasebenza kakuhle. Nangona kunjalo, umsebenzisi ngoku uchitha ixesha lakhe elininzi kwi-terminal kwaye ulindele amava okusebenzisana anemveliso. Ngaloo ndlela kwazalwa i-metric entsha - ixesha lokuphendula (impendulo).
Ixesha lokuphendula libalwa ngolu hlobo lulandelayo:
Tresponse=Tfirstrun−Tarrival
Ngaloo ndlela, kumzekelo wangaphambili, ixesha lokuphendula liya kuba: A=0, B=0, C=10 (abg=3,33).
Kwaye kuvela ukuba i-algorithm ye-STCF ayilungile kakhulu kwimeko apho imisebenzi emi-3 ifika ngexesha elifanayo - kuya kufuneka ilinde de imisebenzi encinci igqitywe ngokupheleleyo. Ke i-algorithm ilungile kwimetric yexesha lokuguqula, kodwa imbi kwimetriki yonxibelelwano. Khawucinge ukuba ubuhleli kwi-terminal uzama ukuchwetheza abalinganiswa kumhleli kwaye kufuneka ulinde ngaphezu kwemizuzwana ye-10 kuba omnye umsebenzi wawuthatha i-CPU. Akukho mnandi kakhulu.
Ke sijongene nenye ingxaki - singakha njani umcwangcisi onovakalelo kwixesha lokuphendula?
Ujikeleze uRobin
I-algorithm yaphuhliswa ukusombulula le ngxaki Ujikeleze uRobin (RR). Uluvo olusisiseko lulula kakhulu: endaweni yokuqhuba imisebenzi ide igqitywe, siya kuqhuba umsebenzi kangangexesha elithile (elibizwa ngokuba sisilayi sexesha) kwaye emva koko sitshintshele komnye umsebenzi ukusuka emgceni. I-algorithm iphinda umsebenzi wayo de yonke imisebenzi igqitywe. Kule meko, ixesha lokuqhuba leprogram kufuneka libe liphindaphinda lexesha emva kokuba isibali-xesha siyakuphazamisa inkqubo. Umzekelo, ukuba isibali-xesha siphazamisa inkqubo rhoqo x=10ms, ngoko ke ubungakanani befestile yophumezo lwenkqubo kufuneka buphindaphindwe ngo-10 kwaye ube ngu-10,20 okanye x*10.
Makhe sijonge umzekelo: Imisebenzi ye-ABC ifika ngaxeshanye kwisixokelelwano kwaye nganye kuzo ifuna ukubaleka imizuzwana emi-5. I-algorithm ye-SJF iya kugqiba umsebenzi ngamnye ngaphambi kokuqala omnye. Ngokwahlukileyo, i-algorithm ye-RR enefestile yokuqalisa = 1s iya kuhamba ngale misebenzi ilandelayo (umzobo 4.3):
(I-SJF Kwakhona (Ayilunganga Ixesha lokuphendula)
(Round Robin (Lilungile ixesha lokuphendula)
Umyinge wexesha lokuphendula kwi-algorithm yeRR ngu (0+1+2)/3=1, ngelixa i-SJF (0+5+10)/3=5.
Kusengqiqweni ukucinga ukuba ixesha lefestile yiparameter ebaluleke kakhulu yeRR; incinci, iphezulu ixesha lokuphendula. Nangona kunjalo, akufanele ulenze libe lincinci kakhulu, kuba ixesha lokutshintsha umxholo liya kudlala indima ekusebenzeni ngokubanzi. Ngaloo ndlela, ukhetho lwexesha lefestile yokubulawa lubekwe ngumakhi we-OS kwaye kuxhomekeke kwimisebenzi ecetywayo ukuba yenziwe kuyo. Ukutshintsha imeko akukuphela komsebenzi wenkonzo ochitha ixesha - inkqubo eqhubayo isebenza kwizinto ezininzi, umzekelo, ii-cache ezahlukeneyo, kunye nokutshintsha ngalunye kuyimfuneko ukugcina nokubuyisela le meko, enokuthi ithathe okuninzi. ixesha.
I-RR ngumcwangcisi omkhulu ukuba besithetha kuphela malunga nexesha lokuphendula metric. Kodwa ixesha lokutshintsha umsebenzi liya kuziphatha njani ngale algorithm? Cinga ngomzekelo ongentla, xa ixesha lokusebenza le-A, B, C = 5s kwaye lifike ngexesha elifanayo. Umsebenzi A uya kuphela ngo-13, B ngo-14, C ngo-15s kunye nexesha eliqhelekileyo lokujika liya kuba yi-14s. Ke, i-RR yeyona algorithm imbi yemetrikhi yentengiso.
Ngokwemigaqo ngokubanzi, nayiphi na i-algorithm yohlobo lwe-RR ilungile; yahlula ixesha le-CPU ngokulinganayo phakathi kwazo zonke iinkqubo. Kwaye ke, ezi metrics zihlala zingqubana enye kwenye.
Ke, sinee-algorithms ezahlukeneyo kwaye kwangaxeshanye kusekho iingcinga ezininzi ezishiyekileyo-ukuba ixesha lomsebenzi liyaziwa kwaye umsebenzi usebenzisa i-CPU kuphela.
Ukudibanisa ne-I/O
Okokuqala, masisuse ukucinga ukuba inkqubo isebenzisa kuphela i-CPU; ngokwemvelo, oku akunjalo kwaye iinkqubo zinokufikelela kwezinye izixhobo.
Umzuzwana nayiphi na inkqubo icela umsebenzi we-I / O, inkqubo ingena kwisimo esivaliweyo, ilindele ukuba i-I / O igqibe. Ukuba i-I / O ithunyelwe kwi-hard drive, ngoko umsebenzi onjalo unokuthatha ukuya kwii-ms ezininzi okanye ngaphezulu, kwaye iprosesa iya kuba ingasebenzi ngalo mzuzu. Ngeli xesha, umcwangcisi unokuthatha iprosesa nayo nayiphi na enye inkqubo. Isigqibo esilandelayo umcwangcisi ekuya kufuneka asenze kuxa inkqubo iya kugqiba i-I/O yayo. Xa oku kusenzeka, uphazamiseko luyakwenzeka kwaye i-OS iya kubeka inkqubo ebizwa ngokuba yi-I/O kwindawo ekulungeleyo.
Makhe sijonge kumzekelo wemisebenzi emininzi. Ngamnye kubo ufuna i-50ms yexesha le-CPU. Nangona kunjalo, owokuqala uya kufikelela kwi-I/O rhoqo nge-10ms (eya kwenziwa kwakhona rhoqo ngo-10ms). Kwaye inkqubo B isebenzisa ngokulula i-50ms iprosesa ngaphandle kwe-I/O.
Kulo mzekelo siza kusebenzisa umcwangcisi we-STCF. Uya kuziphatha njani umcwangcisi ukuba inkqubo efana no-A iqalisiwe kuyo? Uya kwenza oku kulandelayo: kuqala uya kusebenza ngokupheleleyo inkqubo A, aze aqhube uB.
Indlela eqhelekileyo yokusombulula le ngxaki kukuphatha umsebenzi ongaphantsi kwe-10 ms wenkqubo A njengomsebenzi owahlukileyo. Ngaloo ndlela, xa uqala nge-algorithm ye-STJF, ukhetho phakathi komsebenzi we-50 ms kunye nomsebenzi we-10 ms lucacile. Emva koko, xa umsebenzi ongaphantsi uA ugqityiwe, inkqubo B kunye ne-I/O iya kusungulwa. Emva kokuba i-I/O igqibezele, kuya kuba sisiko ukuqalisa inkqubo ye-10ms kwakhona endaweni yenkqubo B. Ngale ndlela, kunokwenzeka ukuphumeza ukugqithelana, apho i-CPU isetyenziswa yenye inkqubo ngelixa eyokuqala ilinde I/O. Kwaye ngenxa yoko, inkqubo isetyenziswe ngcono - okwangoku xa iinkqubo zokusebenzisana zilindele i-I / O, ezinye iinkqubo zinokwenziwa kwiprosesa.
I-Oracle ayisekho
Ngoku makhe sizame ukususa ukucinga ukuba ixesha lokuqhuba lomsebenzi liyaziwa. Le yeyona ngcinga imbi kakhulu nengekho ngqiqweni kulo lonke uluhlu. Ngapha koko, kumndilili we-OS eqhelekileyo, i-OS ngokwayo ihlala isazi kancinci malunga nexesha lokwenziwa kwemisebenzi, ungayakha njani ke umcwangcisi ngaphandle kokwazi ukuba umsebenzi uya kuthatha ixesha elingakanani ukuphumeza? Mhlawumbi sinokusebenzisa imigaqo yeRR ukusombulula le ngxaki?
Isiphumo
Sijonge iingcamango ezisisiseko zokucwangcisa umsebenzi kwaye sijonge kwiintsapho ezi-2 zabacwangcisi. Owokuqala uqala owona msebenzi umfutshane kuqala kwaye ngaloo ndlela ukwandisa ixesha lokuguqula, ngelixa owesibini ukrazulwa phakathi kwayo yonke imisebenzi ngokulinganayo, ukwandisa ixesha lokuphendula. Zombini i-algorithms zimbi apho i-algorithms yolunye usapho ilungile. Siphinde sajonga indlela ukusetyenziswa ngokuhambelanayo kwe-CPU kunye ne-I / O kunokuphucula ukusebenza, kodwa ayizange isombulule ingxaki nge-OS clairvoyance. Kwaye kwisifundo esilandelayo siza kujonga umcwangcisi ojonga kwixesha elidlulileyo kwaye uzama ukuqikelela ikamva. Kwaye kubizwa ngokuba ngumgca wempendulo wamanqanaba amaninzi.
umthombo: www.habr.com