Hordhaca Nidaamyada Hawlgelinta
Haye Habr! Waxaan jeclaan lahaa inaan kuu soo bandhigo maqaallo taxane ah - tarjumaad hal suugaan oo xiiso leh fikradayda - OSTEP. Qalabkani wuxuu si qoto dheer uga hadlayaa shaqada nidaamyada hawlgalka ee u eg, kuwaas oo ah, la shaqeynta hababka, jadwalayaasha kala duwan, xusuusta, iyo qaybaha kale ee la midka ah ee ka kooban OS casriga ah. Waxaad ku arki kartaa asalka dhammaan agabka halkan . Fadlan ogow in tarjumaada loo sameeyay si aan xirfad lahayn (si xor ah), laakiin waxaan rajeynayaa inaan sii wado macnaha guud.
Shaqada shaybaadhka ee mawduucan waxaa laga heli karaa halkan:
Qaybaha kale:
Waxa kale oo aad ka hubin kartaa kanaalkayga =)
Hordhaca Jadwalka
Nuxurka dhibaatada: Sida loo horumariyo siyaasadda jadwalka
Sidee loo qaabeynayaa qaab-dhismeedka siyaasadda jadwalaha hoose? Maxay noqonayaan fikradaha muhiimka ah? Waa maxay cabbirada muhiimka ah? Waa maxay farsamooyinka aasaasiga ah ee loo isticmaalay hababka kombuyuutarada hore?
Malo awaalka culayska shaqada
Kahor intaanan ka doodin siyaasadaha suurtagalka ah, aynu marka hore samayno dhawr fududaynta habraacyada nidaamka, kuwaas oo si wadajir ah loogu yeero. culayska shaqada. Qeexidda culayska shaqadu waa qayb muhiim ah oo ka mid ah siyaasadaha dhisitaanka, iyo marka aad wax badan ka ogaato culayska shaqada, waxa sii wanagsan siyaasadda aad qori karto.
Aynu ka samayno male-awaalka soo socda ee ku saabsan hababka ku socda nidaamka, mararka qaarkood sidoo kale loo yaqaan shaqo (hawlaha). Ku dhawaad ββdhammaan malo-awaaladaasi maaha kuwo xaqiiqo ah, laakiin waxay lagama maarmaan u yihiin horumarinta fikirka.
- Hawl kastaa waxay socotaa waqti isku mid ah,
- Dhammaan hawlaha waxa loo dejiyay isku mar,
- Hawsha loo igmaday way shaqaysaa ilaa ay ka dhammaato.
- Dhammaan hawlaha waxay isticmaalaan CPU kaliya,
- Waa la og yahay wakhtiga hawl kasta.
Qiyaasaha Jadwalka
Marka lagu daro qiyaasaha qaar ee ku saabsan culeyska, qalab kale oo lagu barbar dhigo siyaasadaha jadwalka kala duwan ayaa loo baahan yahay: jaangooyooyinka jadwalka. Halbeeggu waa qiyaas wax uun. Waxaa jira tiro cabbirro ah oo loo isticmaali karo in lagu barbar dhigo jadwalayaasha.
Tusaale ahaan, waxaan isticmaali doonaa mitir la yiraahdo waqtiga soo celinta (waqtiga soo celinta). Wakhtiga soo celinta hawsha waxa lagu qeexaa faraqa u dhexeeya wakhtiga dhamaystirka hawsha iyo wakhtiga shaqada ee nidaamka.
Tturnaround=Dhamaystir-Tarrival
Tan iyo markii aan u maleynay in dhammaan hawlaha ay yimaadeen isku mar, ka dibna Ta=0 iyo sidaas Tt=Tc. Qiimahani si dabiici ah ayuu isu beddeli doonaa marka aan beddelno fikradaha kor ku xusan.
Halbeeg kale - caddaalad (cadaalad, daacadnimo). Wax soo saarka iyo cadaaladu inta badan waa astaamo iska soo horjeeda marka la qorsheynayo. Tusaale ahaan, jadwaleeyaha ayaa laga yaabaa inuu hagaajiyo waxqabadka, laakiin kharashka sugitaanka hawlo kale si ay u socdaan, sidaas darteed hoos u dhigista caddaaladda.
KOWAAD MARKA HORE (FIFO)
Algorithm-ka ugu aasaasiga ah ee aan fulin karno waxaa loo yaqaan FIFO ama marka hore soo gal, marka hore loo adeego (bixi). Algorithm-kani wuxuu leeyahay faa'iidooyin dhowr ah: aad bay u fududahay in la hirgeliyo waxayna ku habboon tahay dhammaan fikradahayaga waxayna si fiican u qabataa shaqada.
Aynu eegno tusaale fudud. Aynu nidhaahno 3 hawlood ayaa isku mar la dhigay. Laakiin aan ka soo qaadno in hawsha A ay timid wax yar ka hor dhammaan kuwa kale, sidaas darteed waxay ka muuqan doontaa liiska fulinta ka hor kuwa kale, sida B marka loo eego C. Aynu ka qaadno in mid kasta oo iyaga ka mid ah la fulin doono 10 ilbiriqsi. Waa maxay celceliska wakhtiga lagu dhammayn karo hawlahan kiiskan?
Tirinta qiimaha - 10 + 20 + 30 iyo qaybinta 3, waxaan heleynaa celceliska waqtiga fulinta barnaamijka oo u dhigma 20 ilbiriqsi.
Hadda aan isku dayno inaan beddelno malo-awaalkayaga. Gaar ahaan, malo-awaalka 1 iyo sidaas awgeed ma qaadan doonno in hawl kasta ay qaadato waqti isku mid ah si loo fuliyo. Sidee FIFO u fulin doontaa wakhtigan?
Sida ay soo baxday, waqtiyada fulinta hawlaha kala duwan ayaa saameyn xun ku leh wax soo saarka FIFO algorithm. Aynu ka soo qaadno in hawsha A ay qaadan doonto 100 ilbiriqsi si ay u dhamaystirto, halka B iyo C ay wali qaadan doonaan 10 ilbiriqsi midkiiba.
Sida ka muuqata shaxanka, celceliska wakhtiga nidaamku wuxuu noqonayaa (100+110+120)/3=110. Saamayntan ayaa loo yaqaan saamaynta kolonyada, marka qaar ka mid ah macaamiisha muddada-gaaban ee kheyraadka ay saf u galaan ka dib macaamiil culus. Waxay la mid tahay khadka dukaanka raashinka marka uu macaamiil kaa hor yimaado oo sita gaadhi buuxa. Xalka ugu fiican ee dhibku waa in aad isku daydo in aad beddesho diiwaanka lacagta caddaanka ah ama aad nasato oo aad si qoto dheer u neefsato.
Shaqada Ugu Gaaban First
Suurtagal ma tahay in si uun loo xalliyo xaalad la mid ah hababka miisaanka culus? Hubaal. Nooc kale oo qorshayn ayaa loo yaqaanShaqada Ugu Gaaban First (SJF). Algorithm-keeda sidoo kale waa mid asal ah - sida magacu tilmaamayo, hawlaha ugu gaaban ayaa la bilaabi doonaa marka hore, midba midka kale ka dib.
Tusaalahan, natiijada socodsiinta habab isku mid ah waxay noqon doontaa hagaajinta celceliska wakhtiga barnaamijka oo waxay la mid noqon doontaa 50 halkii 110, taas oo ku dhawaad ββ2 jeer ka wanaagsan.
Sidaa awgeed, malo-awaalka ah in dhammaan hawluhu ay isku mar yimaadaan, algorithm-ka SJF wuxuu u muuqdaa inuu yahay algorithm ugu wanaagsan. Si kastaba ha ahaatee, malahayadu wali uma muuqdaan kuwo dhab ah. Markan waxaynu bedelaynaa malo-awaalka 2 oo wakhtigan qiyaasi in hawluhu ay joogi karaan wakhti kasta, oo aanay dhammaan isku mar joogi karin. Dhibaato noocee ah ayay tani keeni kartaa?
Aynu qiyaasno in hawsha A (100c) ay marka hore timaaddo oo ay bilowdo in la fuliyo. At t=10, hawlaha B iyo C ayaa imanaya, mid kastaa wuxuu qaadan doonaa 10 ilbiriqsi. Markaa celceliska wakhtiga fulinta waa (100+(110-10)+(120-10))3 = 103. Muxuu samayn karaa jadwalku si uu tan u hagaajiyo?
Wakhtiga Ugu Gaaban ee Dhamaystirka Ugu Horeeya (STCF)
Si aan xaaladda u wanaajino, waxaan meesha ka saaraynaa malo-awaalka 3 ee ah in barnaamijka la bilaabay oo uu socdo ilaa la dhammaystiro. Intaa waxaa dheer, waxaan u baahan doonaa taageero hardware iyo, sida aad malayn karto, waanu isticmaali doonaa saacad in la joojiyo hawl socota iyo beddelka macnaha guud. Sidaas awgeed, jadwaleeyaha ayaa wax qaban kara wakhtigan xaadirka ah hawlaha B, C yimaado - jooji fulinta hawsha A oo geli hawlaha B iyo C si ay u habeeyaan iyo, ka dib marka ay dhammeeyaan, sii wadaan fulinta nidaamka A. Jadwalaha noocan oo kale ah ayaa loo yaqaan. STCFama Shaqada Kahortagga Horta.
Natiijadu waxay noqon doontaa natiijada soo socota: ((120-0)+(20-10)+(30-10))/3=50. Sidaas awgeed, jadwaleeyaha noocan oo kale ah wuxuu noqdaa mid aad ugu habboon hawlaheenna.
Waqtiga Jawaabta Metric
Sidaa darteed, haddii aan ogaano wakhtiga ay socdaan hawlaha iyo in hawlahani ay isticmaalaan CPU kaliya, STCF ayaa noqon doonta xalka ugu fiican. Iyo hal mar wakhtiyadii hore, algorithms-yadani waxay si fiican u shaqeeyeen. Si kastaba ha noqotee, isticmaaluhu hadda waxay ku qaataan inta badan waqtigeeda terminaalka waxayna filayaan khibrad is dhexgalka wax soo saar leh. Sidaas awgeed cabbir cusub ayaa ku dhashay - waqtiga jawaabta (jawaab).
Waqtiga jawaabta waxaa loo xisaabiyaa sida soo socota:
Tresponse=Tfirstrun-Tarrival
Haddaba, tusaalihii hore, wakhtiga jawaabtu wuxuu noqon doonaa: A=0, B=0, C=10 (abg=3,33).
Oo waxay soo baxday in algorithm-ka STCF uusan ku fiicneyn xaalad ay 3 hawlood isku mar yimaadaan - waa inay sugaan ilaa hawlaha yaryar ay dhammaystiraan. Markaa algorithmisku wuxuu u fiican yahay mitirka wakhtiga jeedinta, laakiin wuxuu u xun yahay cabbirka isdhexgalka. Bal qiyaas haddii aad fadhido terminal isku day inaad ku qorto jilayaasha tafatiraha oo aad sugto in ka badan 10 ilbiriqsi sababtoo ah hawl kale ayaa qaadanaysay CPU. Aad uma faraxsana.
Markaa dhibaato kale ayaa ina soo food saartay - sideen u dhisi karnaa jadwal u nugul wakhtiga jawaabta?
Robin Round
Algorithm ayaa la sameeyay si loo xalliyo dhibaatadan Robin Round (RR). Fikradda aasaasiga ah waa mid sahlan: halkii aan ka shaqeyn lahayn hawlaha ilaa ay dhammeeyaan, waxaan ku socodsiin doonaa hawsha wakhti go'an (oo loo yaqaan 'time slice) ka dibna u beddelo hawl kale oo ka soo baxa safka. Algorithm waxay ku celisaa shaqadeeda ilaa dhammaan hawlaha la dhammeeyo. Xaaladdan oo kale, wakhtiga socodsiinta barnaamijku waa inuu noqdaa mid isku dhufasho ah oo wakhtiga ka dib saacaduhu carqaladayn doono hawsha. Tusaale ahaan, haddii uu saacaduhu carqaladeeyo habka x=10ms kasta, markaa cabbirka daaqadda fulinta habsocodka waa in uu noqdaa dhowr jeer oo 10 ah oo uu noqdo 10,20 ama x*10.
Aan eegno tusaale: Hawlaha ABC waxay ku yimaadaan isku mar nidaamka oo mid kasta oo iyaga ka mid ah wuxuu rabaa inuu socdo 5 ilbiriqsi. Algorithmamka SJF ayaa dhamaystiri doona hawl kasta ka hor inta aanu mid kale bilaabin. Taas bedelkeeda, algorithm-ka RR ee daaqada furitaanka = 1s ayaa u mari doona hawlaha sida soo socota (Jaantus. 4.3):
(SJF Mar labaad (Bad for Response Time)
(Round Robin (Waqtiga Jawaabta Wacan)
Celceliska wakhtiga jawaabta ee algorithm RR waa (0+1+2)/3=1, halka SJF (0+5+10)/3=5.
Waa macquul in la qiyaaso in daaqada wakhtigu uu yahay halbeeg aad u muhiim ah RR; inta yar ee uu yahay, waa uu sarreeyaa wakhtiga jawaabta. Si kastaba ha ahaatee, waa inaadan ka dhigin mid aad u yar, sababtoo ah wakhtiga beddelka macnaha guud wuxuu sidoo kale door ka ciyaari doonaa waxqabadka guud. Sidaa darteed, doorashada wakhtiga daaqada fulinta waxaa dejiya naqshadeeyaha OS waxayna kuxirantahay hawlaha la qorsheeyay in lagu fuliyo. Beddelka macnaha guud ma aha oo kaliya hawlgalka adeegga ee wakhtiga luminaya - barnaamijka socodsiinta wuxuu ku shaqeeyaa waxyaabo kale oo badan, tusaale ahaan, kaydyo kala duwan, iyadoo beddel kasta loo baahan yahay in la badbaadiyo oo dib loo soo celiyo deegaankan, taas oo sidoo kale qaadan karta wax badan. waqti.
RR waa jadwal weyn haddii aan ka hadlaynay kaliya cabbirka waqtiga jawaabta. Laakin sidee bay hawsha cabbirka wakhtiga beddelka u dhaqmaysaa algorithmamkan? Tixgeli tusaalaha kore, marka wakhtiga shaqada ee A, B, C = 5s oo ay timaado isku mar. Hawsha A waxa ay ku dhamaan doontaa 13, B at 14, C at 15s iyo celceliska wakhtiga soo celinta waxa uu noqon doonaa 14s. Markaa, RR waa algorithm-ka ugu xun ee cabbirka wareegtada.
Erayada guud ee dheeraadka ah, nooc kasta oo RR-algorithm ah waa cadaalad; waxay u qaybisaa wakhtiga CPU si siman dhammaan hababka. Oo sidaas daraaddeed, cabbiradani waxay si joogto ah iskaga hor imanayaan midba midka kale.
Sidaa darteed, waxaan haynaa dhowr algorithms isbarbardhiga isla mar ahaantaana waxaa haray fikrado dhowr ah - in waqtiga shaqada la yaqaan iyo in hawshu kaliya isticmaasho CPU.
Isku dhafka I/O
Ugu horreyntii, aan ka saarno malo-awaalka 4 in geeddi-socodku kaliya isticmaalo CPU; dabiiciyan, tani maahan kiiska oo hababku waxay heli karaan qalab kale.
Isla marka uu hab-socod kasta codsado hawlgalka I/O, nidaamku waxa uu galaa gobolka xanniban, isaga oo sugaya in I/O uu dhammaystiro. Haddii I/O loo soo diro darawalka adag, markaas hawlgalkan oo kale wuxuu qaadan karaa ilaa dhowr ms ama ka badan, processor-kuna wuxuu noqon doonaa mid caajis ah xilligan. Inta lagu jiro wakhtigan, jadwalku wuxuu ku mashquulin karaa processor-ka hab kasta oo kale. Go'aanka soo socda ee jadwalaha ayaa ah inuu gaaro waa marka nidaamku dhammeeyo I/O. Marka tani dhacdo, hakad ayaa imaan doonta OS-gu wuxuu gelin doonaa nidaamka u yeeray I/O xaalad diyaar ah.
Aynu eegno tusaale dhowr hawlood ah. Mid kasta oo iyaga ka mid ah wuxuu u baahan yahay 50ms oo waqti CPU ah. Si kastaba ha ahaatee, kan ugu horreeya wuxuu geli doonaa I/O 10 ms kasta (kaas oo sidoo kale la fulin doono 10 ms kasta). Habka B wuxuu si fudud u adeegsadaa processor 50ms ah oo aan lahayn I/O.
Tusaalahan waxaan isticmaali doonaa jadwalka STCF. Sidee jadwalku u dhaqmayaa haddii habsocod sida A oo kale ah lagu bilaabo? Waxa uu samayn doonaa waxa soo socda: marka hore waxa uu si buuxda u shaqayn doonaa habka A, ka dibna habka B.
Habka soo jireenka ah ee lagu xalliyo dhibaatadan waa in 10 ms kasta oo hawl-hoosaad ee habka A loola dhaqmo sidii hawl gaar ah. Haddaba, marka laga bilaabo algorithm-ka STJF, doorashada u dhaxaysa hawsha 50 ms iyo hawsha 10 ms waa caddahay. Kadib, marka shaqada-hoosaadka A la dhammeeyo, habka B iyo I/O ayaa la bilaabayaa. Ka dib marka I/O la dhammeeyo, waxaa caado noqon doonta in mar kale la bilaabo habka 10ms A halkii laga isticmaali lahaa habka B. Sidan, waxaa suurtagal ah in la hirgeliyo isku-dhafka, halkaasoo CPU-ga loo isticmaalo hab kale iyadoo kan ugu horreeya uu sugayo I/O Natiijo ahaan, nidaamka si fiican ayaa looga faa'iidaysan karaa - hadda marka hababka isdhexgalka ay sugayaan I / O, habab kale ayaa lagu fulin karaa processor-ka.
Oracle hadda ma jiro
Hadda aan isku dayno inaan meesha ka saarno malo-awaalka ah in la og yahay wakhtiga hawsha hawsha. Tani guud ahaan waa mala-awaalka ugu xun uguna macquulsan ee liiska oo dhan. Dhab ahaantii, celceliska OS-ga caadiga ah, OS laftiisa ayaa inta badan wax yar ka og wakhtiga fulinta hawlaha, markaa sidee ayaad u dhisi kartaa jadwaliye adigoon ogeyn inta ay hawsha qaadan doonto si loo fuliyo? Ma laga yaabaa inaan isticmaalno qaar ka mid ah mabaadi'da RR si loo xalliyo dhibaatadan?
Natiijada
Waxaan eegnay fikradaha aasaasiga ah ee jadwalka hawsha waxaananu eegnay 2 qoys oo jadwalayaal ah. Midda hore waxay ku bilaabataa hawsha ugu gaaban marka hore oo sidaas awgeed waxay kordhisaa wakhtiga ka-soo-jeedinta, halka ta labaadna ay si siman u kala qaybiso dhammaan hawlaha, kordhinta wakhtiga jawaabta. Labada algorithms way xun yihiin halka algorithms ee qoyska kale ay ku fiican yihiin. Waxaan sidoo kale eegnay sida isbarbar-dhigga isticmaalka CPU iyo I/O ay u hagaajin karaan waxqabadka, laakiin ma xallin dhibaatada OS clairvoyance. Casharka soo socdana waxaynu ku eegi doonaa qorsheeye oo eegaya waayihii dhowaa iskuna daya inuu saadaaliyo mustaqbalka. Waxaana loo yaqaan safka jawaab celinta heerar badan.
Source: www.habr.com