Utangulizi wa Mifumo ya Uendeshaji
Habari Habr! Ningependa kukuletea msururu wa vifungu-tafsiri za fasihi moja ya kupendeza kwa maoni yangu - OSTEP. Nyenzo hii inajadili kwa undani kazi ya mifumo ya uendeshaji kama unix, yaani, kufanya kazi na michakato, wapangaji ratiba mbalimbali, kumbukumbu, na vipengele vingine vinavyofanana vinavyounda OS ya kisasa. Unaweza kuona asili ya nyenzo zote hapa . Tafadhali kumbuka kuwa tafsiri ilifanywa bila taaluma (kwa uhuru kabisa), lakini natumai nilihifadhi maana ya jumla.
Kazi ya maabara juu ya mada hii inaweza kupatikana hapa:
Sehemu zingine:
Unaweza pia kuangalia kituo changu kwa =)
Utangulizi wa Mratibu
Kiini cha shida: Jinsi ya kuunda sera ya mpangilio
Je, mifumo ya msingi ya sera ya mratibu inapaswa kutengenezwa vipi? Mawazo muhimu yanapaswa kuwa nini? Je, ni vipimo gani muhimu? Je! ni mbinu gani za kimsingi zilizotumiwa katika mifumo ya mapema ya kompyuta?
Mawazo ya mzigo wa kazi
Kabla ya kujadili sera zinazowezekana, hebu kwanza tufanye maamuzi machache ya kurahisisha kuhusu michakato inayoendeshwa katika mfumo, ambayo kwa pamoja inaitwa. mzigo wa kazi. Kufafanua mzigo wa kazi ni sehemu muhimu ya sera za ujenzi, na kadri unavyojua zaidi kuhusu mzigo wa kazi, ndivyo sera unavyoweza kuandika.
Hebu tufanye mawazo yafuatayo kuhusu taratibu zinazoendesha katika mfumo, wakati mwingine pia huitwa ajira (kazi). Takriban mawazo haya yote sio ya kweli, lakini ni muhimu kwa maendeleo ya mawazo.
- Kila kazi inaendeshwa kwa muda sawa,
- Kazi zote zimewekwa kwa wakati mmoja,
- Kazi iliyokabidhiwa inafanya kazi hadi kukamilika kwake,
- Kazi zote hutumia CPU pekee,
- Wakati wa kukimbia wa kila kazi unajulikana.
Vipimo vya Mratibu
Kando na baadhi ya mawazo kuhusu mzigo, zana nyingine ya kulinganisha sera tofauti za kuratibu inahitajika: vipimo vya kiratibu. Kipimo ni kipimo fulani tu cha kitu. Kuna idadi ya vipimo vinavyoweza kutumika kulinganisha vipanga ratiba.
Kwa mfano, tutatumia kipimo kinachoitwa muda wa kurejea (wakati wa mabadiliko). Muda wa kubadilisha kazi unafafanuliwa kama tofauti kati ya muda wa kukamilisha kazi na muda wa kuwasili kwa kazi katika mfumo.
Tturnaround=Ukamilishaji-Tarrival
Kwa kuwa tulidhani kwamba kazi zote zilifika kwa wakati mmoja, basi Ta=0 na hivyo Tt=Tc. Thamani hii itabadilika kwa kawaida tunapobadilisha mawazo hapo juu.
Kipimo kingine - Haki (haki, uaminifu). Tija na haki mara nyingi ni sifa zinazopingana katika kupanga. Kwa mfano, mpangaji ratiba anaweza kuongeza utendakazi, lakini kwa gharama ya kusubiri kazi zingine ziendeshwe, na hivyo kupunguza haki.
KWANZA KWA KWANZA (FIFO)
Algorithm ya msingi zaidi ambayo tunaweza kutekeleza inaitwa FIFO au kwanza njoo (ndani), kwanza alipewa (nje). Algorithm hii ina faida kadhaa: ni rahisi sana kutekeleza na inafaa mawazo yetu yote na hufanya kazi vizuri kabisa.
Hebu tuangalie mfano rahisi. Wacha tuseme kazi 3 ziliwekwa wakati huo huo. Lakini hebu tuchukulie kwamba kazi A ilifika mapema zaidi kuliko wengine wote, kwa hiyo itaonekana kwenye orodha ya utekelezaji mapema zaidi kuliko wengine, kama vile B jamaa na C. Hebu tuchukue kwamba kila mmoja wao atatekelezwa kwa sekunde 10. Je, ni muda gani wa wastani wa kukamilisha kazi hizi katika kesi hii?
Kwa kuhesabu maadili - 10+20+30 na kugawanya na 3, tunapata muda wa wastani wa utekelezaji wa programu sawa na sekunde 20.
Sasa hebu tujaribu kubadilisha mawazo yetu. Hasa, dhana ya 1 na kwa hivyo hatutafikiria tena kuwa kila kazi inachukua muda sawa wa kutekeleza. FIFO itafanyaje wakati huu?
Kama inavyotokea, nyakati tofauti za utekelezaji wa kazi zina athari mbaya sana kwenye tija ya algoriti ya FIFO. Wacha tuchukue kuwa kazi A itachukua sekunde 100 kukamilika, wakati B na C bado zitachukua sekunde 10 kila moja.
Kama inavyoonekana kutoka kwa takwimu, muda wa wastani wa mfumo utakuwa (100+110+120)/3=110. Athari hii inaitwa athari ya msafara, wakati watumiaji wengine wa muda mfupi wa rasilimali watapanga foleni baada ya mtumiaji mzito. Ni kama mstari kwenye duka la mboga wakati kuna mteja mbele yako na mkokoteni kamili. Suluhisho bora kwa tatizo ni kujaribu kubadilisha rejista ya fedha au kupumzika na kupumua kwa undani.
Kazi Fupi Kwanza
Inawezekana kwa namna fulani kutatua hali kama hiyo na michakato ya uzani mzito? Hakika. Aina nyingine ya kupanga inaitwaKazi Fupi Kwanza (SJF). Algorithm yake pia ni ya zamani - kama jina linamaanisha, kazi fupi zaidi zitazinduliwa kwanza, moja baada ya nyingine.
Katika mfano huu, matokeo ya kuendesha michakato sawa yatakuwa uboreshaji wa wastani wa muda wa utekelezaji wa programu na itakuwa sawa na 50 badala ya 110, ambayo ni karibu mara 2 bora.
Kwa hivyo, kwa dhana iliyotolewa kwamba kazi zote zinafika kwa wakati mmoja, algorithm ya SJF inaonekana kuwa algorithm bora zaidi. Hata hivyo, mawazo yetu bado hayaonekani kuwa ya kweli. Wakati huu tunabadilisha dhana 2 na wakati huu fikiria kwamba kazi zinaweza kuwepo wakati wowote, na sio zote kwa wakati mmoja. Je, hii inaweza kusababisha matatizo gani?
Hebu fikiria kwamba kazi A (100c) inakuja kwanza na kuanza kutekelezwa. Kwa t=10, kazi B na C hufika, ambayo kila moja itachukua sekunde 10. Kwa hivyo muda wa wastani wa utekelezaji ni (100+(110-10)+(120-10))3 = 103. Mpangaji ratiba angeweza kufanya nini ili kuboresha hili?
Muda Mfupi Zaidi wa Kukamilisha Kwanza (STCF)
Ili kuboresha hali hii, tunaacha dhana ya 3 kwamba programu imezinduliwa na itaendeshwa hadi kukamilika. Kwa kuongeza, tutahitaji usaidizi wa vifaa na, kama unavyoweza kudhani, tutatumia kipima muda kukatiza kazi inayoendesha na kubadilisha muktadha. Kwa hivyo, mpanga ratiba anaweza kufanya jambo wakati kazi B, C zinapofika - kuacha kutekeleza kazi A na kuweka kazi B na C katika usindikaji na, baada ya kukamilika kwao, kuendelea kutekeleza mchakato A. Mpangaji ratiba kama huyo anaitwa STCFau Kazi ya mapema kwanza.
Matokeo ya mpangaji huyu yatakuwa matokeo yafuatayo: ((120-0)+(20-10)+(30-10))/3=50. Kwa hivyo, mpangilio kama huo unakuwa bora zaidi kwa kazi zetu.
Muda wa Majibu ya Metric
Kwa hivyo, ikiwa tunajua wakati wa kufanya kazi na kwamba kazi hizi hutumia CPU pekee, STCF itakuwa suluhisho bora. Na mara moja katika nyakati za mapema, algorithms hizi zilifanya kazi vizuri. Hata hivyo, mtumiaji sasa anatumia muda wake mwingi kwenye terminal na anatarajia matumizi maingiliano yenye tija. Kwa hivyo metriki mpya ilizaliwa - wakati wa majibu (majibu).
Muda wa majibu umehesabiwa kama ifuatavyo:
Tresponse=Tfirstrun−Tarrival
Kwa hivyo, kwa mfano uliopita, wakati wa kujibu utakuwa: A=0, B=0, C=10 (abg=3,33).
Na inageuka kuwa algorithm ya STCF si nzuri sana katika hali ambapo kazi 3 zinafika kwa wakati mmoja - itabidi kusubiri mpaka kazi ndogo zimekamilika kabisa. Kwa hivyo algoriti ni nzuri kwa kipimo cha wakati wa kubadilisha, lakini ni mbaya kwa metriki ya mwingiliano. Fikiria ikiwa ulikuwa umekaa kwenye terminal kujaribu kuchapa herufi kwenye kihariri na kulazimika kungoja zaidi ya sekunde 10 kwa sababu kazi nyingine ilikuwa inachukua CPU. Haipendezi sana.
Kwa hivyo tunakabiliwa na shida nyingine - tunawezaje kuunda kipanga ratiba ambacho ni nyeti kwa wakati wa majibu?
Mzunguko wa Robin
Algorithm iliundwa ili kutatua tatizo hili Mzunguko wa Robin (RR). Wazo la msingi ni rahisi sana: badala ya kuendesha kazi hadi kukamilika, tutaendesha kazi kwa muda fulani (kinachoitwa kipande cha wakati) na kisha kubadili kazi nyingine kutoka kwenye foleni. Algorithm inarudia kazi yake hadi kazi zote zimekamilika. Katika kesi hii, muda wa uendeshaji wa programu lazima uwe mara nyingi baada ya hapo kipima saa kitakatiza mchakato. Kwa mfano, ikiwa kipima muda kitakatiza mchakato kila x=10ms, basi ukubwa wa dirisha la utekelezaji wa mchakato unapaswa kuwa kizidisho cha 10 na kuwa 10,20 au x*10.
Wacha tuangalie mfano: Kazi za ABC hufika wakati huo huo kwenye mfumo na kila moja inataka kukimbia kwa sekunde 5. Kanuni ya SJF itakamilisha kila kazi kabla ya kuanza nyingine. Kinyume chake, algorithm ya RR yenye dirisha la uzinduzi = 1s itapitia kazi zifuatazo (Mchoro 4.3):
(SJF Tena (Mbaya kwa Wakati wa Kujibu)
(Round Robin (Nzuri kwa Wakati wa Kujibu)
Muda wa wastani wa majibu kwa algoriti ya RR ni (0+1+2)/3=1, huku kwa SJF (0+5+10)/3=5.
Ni busara kudhani kuwa dirisha la wakati ni kigezo muhimu sana cha RR; jinsi kilivyo ndogo, ndivyo muda wa majibu unavyoongezeka. Walakini, haupaswi kuifanya kuwa ndogo sana, kwani wakati wa kubadilisha muktadha pia utachukua jukumu katika utendaji wa jumla. Kwa hivyo, uchaguzi wa muda wa dirisha wa utekelezaji umewekwa na mbunifu wa OS na inategemea kazi ambazo zimepangwa kutekelezwa ndani yake. Kubadilisha muktadha sio operesheni pekee ya huduma ambayo hupoteza wakati - programu inayoendesha inafanya kazi kwa vitu vingine vingi, kwa mfano, kashe kadhaa, na kwa kila swichi ni muhimu kuokoa na kurejesha mazingira haya, ambayo yanaweza pia kuchukua mengi. wakati.
RR ni kipanga ratiba bora ikiwa tulikuwa tunazungumza tu kuhusu kipimo cha muda wa majibu. Lakini je, metriki ya saa ya kugeuza kazi itafanyaje na kanuni hii? Fikiria mfano hapo juu, wakati wakati wa uendeshaji wa A, B, C = 5s na ufikie wakati huo huo. Kazi A itaisha saa 13, B saa 14, C saa 15 na wastani wa muda wa kurejea utakuwa sekunde 14. Kwa hivyo, RR ndio kanuni mbaya zaidi ya metriki ya mauzo.
Kwa maneno ya jumla zaidi, algorithm yoyote ya aina ya RR ni sawa; inagawanya wakati wa CPU kwa usawa kati ya michakato yote. Na kwa hivyo, vipimo hivi vinagongana kila wakati.
Kwa hivyo, tuna algorithms kadhaa tofauti na wakati huo huo bado kuna mawazo kadhaa yaliyobaki - kwamba wakati wa kazi unajulikana na kwamba kazi hiyo hutumia CPU tu.
Kuchanganya na I/O
Kwanza kabisa, hebu tuondoe dhana ya 4 kwamba mchakato hutumia CPU pekee; kwa kawaida, hii sivyo na taratibu zinaweza kufikia vifaa vingine.
Wakati mchakato wowote unapoomba operesheni ya I/O, mchakato huingia katika hali iliyozuiwa, ikingoja I/O ikamilike. Ikiwa I/O inatumwa kwa gari ngumu, basi operesheni kama hiyo inaweza kuchukua hadi ms kadhaa au zaidi, na processor itakuwa bila kazi wakati huu. Wakati huu, mpangaji anaweza kuchukua processor na mchakato mwingine wowote. Uamuzi unaofuata ambao mratibu atalazimika kufanya ni wakati mchakato utakapokamilisha I/O yake. Wakati hii itatokea, usumbufu utatokea na OS itaweka mchakato ulioita I/O katika hali tayari.
Hebu tuangalie mfano wa matatizo kadhaa. Kila moja yao inahitaji 50ms ya wakati wa CPU. Hata hivyo, ya kwanza itafikia I/O kila milisekunde (ambayo pia itatekelezwa kila milisekunde 10). Na mchakato B hutumia kichakataji cha 10ms bila I/O.
Katika mfano huu tutatumia mpangilio wa STCF. Mratibu atafanyaje ikiwa mchakato kama A utazinduliwa juu yake? Atafanya yafuatayo: kwanza atashughulikia kabisa mchakato A, na kisha kusindika B.
Mbinu ya jadi ya kutatua tatizo hili ni kutibu kila kazi ndogo ya ms 10 ya mchakato A kama kazi tofauti. Kwa hivyo, wakati wa kuanza na algorithm ya STJF, chaguo kati ya kazi ya 50 ms na 10 ms ni dhahiri. Kisha, jukumu dogo A litakapokamilika, mchakato wa B na I/O utazinduliwa. Baada ya I/O kukamilika, itakuwa ni desturi kuanza mchakato wa 10ms A tena badala ya mchakato B. Kwa njia hii, inawezekana kutekeleza mwingiliano, ambapo CPU inatumiwa na mchakato mwingine wakati wa kwanza unasubiri. I/O. Na kwa sababu hiyo, mfumo unatumiwa vyema zaidi - kwa sasa wakati michakato ya mwingiliano inangojea I/O, michakato mingine inaweza kutekelezwa kwenye kichakataji.
Oracle haipo tena
Sasa hebu jaribu kuondokana na dhana kwamba wakati wa uendeshaji wa kazi unajulikana. Hii kwa ujumla ni dhana mbaya na isiyo ya kweli katika orodha nzima. Kwa kweli, katika OS ya kawaida ya kawaida, OS yenyewe kawaida haijui kidogo sana juu ya wakati wa utekelezaji wa kazi, kwa hivyo unawezaje kuunda mpangilio bila kujua ni muda gani kazi itachukua kutekeleza? Labda tunaweza kutumia kanuni za RR kutatua tatizo hili?
Jumla ya
Tuliangalia mawazo ya kimsingi ya upangaji kazi na tukaangalia familia 2 za wapanga ratiba. Ya kwanza huanza kazi fupi zaidi kwanza na hivyo huongeza muda wa kugeuza, wakati ya pili imevunjwa kati ya kazi zote kwa usawa, na kuongeza muda wa majibu. Algorithms zote mbili ni mbaya ambapo algoriti za familia nyingine ni nzuri. Pia tuliangalia jinsi matumizi sambamba ya CPU na I/O yanaweza kuboresha utendakazi, lakini hatukutatua tatizo na uwazi wa OS. Na katika somo linalofuata tutaangalia mpangaji anayeangalia siku za nyuma na kujaribu kutabiri yajayo. Na inaitwa foleni ya maoni ya ngazi nyingi.
Chanzo: mapenzi.com