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 =)
Kupanga: Foleni ya Maoni ya Ngazi nyingi
Katika hotuba hii, tutazungumzia kuhusu matatizo ya kuendeleza mojawapo ya mbinu maarufu zaidi
kupanga, ambayo inaitwa Foleni ya Maoni ya Ngazi nyingi (MLFQ). Ratiba ya MLFQ ilielezewa kwa mara ya kwanza mnamo 1962 na Fernando J. CorbatΓ³ katika mfumo unaoitwa.
Mfumo Sambamba wa Kugawana Wakati (CTSS). Kazi hizi (pamoja na kazi ya baadaye
Multics) baadaye waliteuliwa kwa Tuzo ya Turing. Mratibu alikuwa
iliboresha na kupata mwonekano ambao unaweza kupatikana tayari ndani
baadhi ya mifumo ya kisasa.
Algorithm ya MLFQ inajaribu kutatua shida 2 za kimsingi zinazoingiliana.
Kwanza, inajaribu kuongeza muda wa kurejea, ambao, kama tulivyojadili katika muhadhara uliopita, unaboreshwa na njia ya kuanzia kwenye kichwa cha foleni zaidi.
kazi fupi. Hata hivyo, OS haijui muda gani hii au mchakato huo utaendelea, na hii
maarifa muhimu kwa ajili ya uendeshaji wa SJF, STCF algorithms. Pili, MLFQ inajaribu
fanya mfumo kuwa msikivu kwa watumiaji (kwa mfano, kwa wale wanaokaa na
tazama skrini ukisubiri kazi ikamilike) na hivyo kupunguza muda
majibu. Kwa bahati mbaya, algoriti kama RR huboresha wakati wa majibu, lakini sana
kuwa na athari mbaya kwenye kipimo cha muda wa kubadilisha. Kwa hivyo shida yetu: Jinsi ya kuunda
kipanga ratiba ambacho kitakidhi mahitaji yetu na wakati huo huo hajui chochote juu yake
asili ya mchakato kwa ujumla? Mpangaji anawezaje kujifunza sifa za kazi,
ambayo inazindua na hivyo kufanya maamuzi bora ya ratiba?
Kiini cha tatizo: Jinsi ya kupanga mipangilio ya kazi bila ujuzi kamili?
Jinsi ya kuunda kipanga ratiba ambacho kinapunguza wakati wa kujibu wakati huo huo
kwa kazi zinazoingiliana na wakati huo huo hupunguza wakati wa kugeuza bila kujua
ujuzi wa muda wa utekelezaji wa kazi?
Kumbuka: kujifunza kutoka kwa matukio ya awali
Foleni ya MLFQ ni mfano bora wa mfumo ambao umefunzwa
matukio ya zamani kutabiri yajayo. Mbinu kama hizo mara nyingi
inayopatikana katika OS (Na matawi mengine mengi ya sayansi ya kompyuta, pamoja na matawi
utabiri wa vifaa na algorithms ya caching). Matembezi sawa
anzisha wakati kazi zina awamu za tabia na kwa hivyo zinaweza kutabirika.
Hata hivyo, unapaswa kuwa makini na mbinu hii kwa sababu utabiri ni rahisi sana
inaweza kugeuka kuwa mbaya na kusababisha mfumo kufanya maamuzi mabaya kuliko
ingekuwa bila maarifa hata kidogo.
MLFQ: Kanuni za Msingi
Hebu tuangalie sheria za msingi za algorithm ya MLFQ. Na ingawa utekelezaji wa algorithm hii
Kuna kadhaa, mbinu za msingi ni sawa.
Katika utekelezaji ambao tutazingatia, MLFQ itakuwa na kadhaa
foleni tofauti, ambayo kila moja itakuwa na kipaumbele tofauti. Wakati wowote,
kazi iliyo tayari kutekelezwa iko kwenye foleni moja. MLFQ hutumia vipaumbele,
kuamua ni kazi gani ya kutekeleza kwa ajili ya utekelezaji, i.e. kazi na ya juu
kipaumbele (kazi kutoka kwa foleni yenye kipaumbele cha juu zaidi) itazinduliwa mara ya kwanza
foleni.
Bila shaka, kunaweza kuwa na kazi zaidi ya moja katika foleni fulani, hivyo
hivyo watakuwa na kipaumbele sawa. Katika kesi hii, utaratibu utatumika
RR kwa upangaji wa uzinduzi kati ya kazi hizi.
Kwa hivyo tunafikia sheria mbili za msingi za MLFQ:
- Kanuni ya 1: Ikiwa kipaumbele(A) > Kipaumbele(B), kazi A itaendeshwa (B haitafanya)
- Kanuni ya2: Ikiwa kipaumbele(A) = Kipaumbele(B), A&B imeanza kutumia RR
Kulingana na hapo juu, vipengele muhimu vya kupanga MLFQ ni
ni vipaumbele. Badala ya kutoa kipaumbele maalum kwa kila mmoja
kazi, MLFQ inabadilisha kipaumbele chake kulingana na tabia inayozingatiwa.
Kwa mfano, ikiwa kazi itasitishwa kila wakati kwenye CPU wakati wa kusubiri uingizaji wa kibodi,
MLFQ itaweka kipaumbele cha mchakato kuwa juu kwa sababu ndivyo hivyo
mchakato wa mwingiliano unapaswa kufanya kazi. Ikiwa, kinyume chake, kazi ni mara kwa mara na
ni CPU kubwa kwa muda mrefu, MLFQ itaishusha
kipaumbele. Kwa hivyo, MLFQ itasoma tabia ya michakato wakati inaendesha.
na kutumia tabia.
Hebu tuchore mfano wa jinsi foleni zinaweza kuonekana wakati fulani
wakati na kisha unapata kitu kama hiki:
Katika mpango huu, michakato 2 A na B iko kwenye foleni iliyopewa kipaumbele cha juu zaidi. Mchakato
C iko mahali fulani katikati, na mchakato wa D uko mwisho kabisa wa foleni. Kulingana na hapo juu
Kulingana na maelezo ya algorithm ya MLFQ, mpangaji ratiba atafanya kazi na za juu zaidi
kipaumbele kulingana na RR, na kazi C, D itakuwa nje ya kazi.
Kwa kawaida, snapshot tuli haitatoa picha kamili ya jinsi MLFQ inavyofanya kazi.
Ni muhimu kuelewa hasa jinsi picha inabadilika kwa muda.
Jaribio la 1: Jinsi ya kubadilisha kipaumbele
Katika hatua hii, unahitaji kuamua jinsi MLFQ itabadilisha kiwango cha kipaumbele
kazi (na hivyo nafasi ya kazi kwenye foleni) wakati wa mzunguko wa maisha yake. Kwa
hii ni muhimu kukumbuka mtiririko wa kazi: kiasi fulani
kazi zinazoingiliana na muda mfupi wa kukimbia (na hivyo kutolewa mara kwa mara
CPU) na kazi kadhaa ndefu ambazo hutumia CPU wakati wao wote wa kufanya kazi, wakati
wakati wa kujibu kwa kazi kama hizo sio muhimu. Na hivyo unaweza kufanya jaribio la kwanza
tekeleza algorithm ya MLFQ na sheria zifuatazo:
- Kanuni ya 3: Wakati kazi inapoingia kwenye mfumo, inawekwa kwenye foleni na ya juu zaidi
- kipaumbele.
- Kanuni4a: Ikiwa kazi hutumia dirisha lake la wakati wote, basi
- kipaumbele kinashushwa.
- Rule4b: Ikiwa Task itaachilia CPU kabla ya muda wa dirisha kuisha, basi itafanyika
- inabaki na kipaumbele sawa.
Mfano 1: Kazi moja ya muda mrefu
Kama unaweza kuona katika mfano huu, kazi ya uandikishaji imewekwa na ya juu zaidi
kipaumbele. Baada ya kidirisha cha muda cha 10ms, mchakato unashushwa katika kipaumbele.
mpanga ratiba. Baada ya dirisha la wakati ujao, kazi hatimaye imeshushwa hadi
kipaumbele cha chini kabisa katika mfumo, ambapo kinabaki.
Mfano 2: Imewasilisha kazi fupi
Sasa hebu tuone mfano wa jinsi MLFQ itajaribu kukaribia SJF. Katika hilo
kwa mfano, kazi mbili: A, ambayo ni kazi ya muda mrefu daima
kuchukua CPU na B, ambayo ni kazi fupi inayoingiliana. Tuseme
kwamba A tayari alikuwa amefanya kazi kwa muda wakati kazi B ilipofika.
Grafu hii inaonyesha matokeo ya kisa. Kazi A, kama kazi yoyote,
kutumia CPU ilikuwa chini kabisa. Kazi B itafika kwa wakati T=100 na itafika
kuwekwa kwenye foleni ya kipaumbele cha juu zaidi. Kwa kuwa muda wa kukimbia ni mfupi,
itakamilika kabla ya kufikia foleni ya mwisho.
Kutoka kwa mfano huu, unapaswa kuelewa lengo kuu la algorithm: kwani algorithm haifanyi
anajua kazi ndefu au fupi, basi kwanza kabisa anafikiria kuwa kazi hiyo
fupi na kuipa kipaumbele cha juu zaidi. Ikiwa hii ni kazi fupi sana, basi
itatekeleza haraka, vinginevyo ikiwa ni kazi ndefu itasonga polepole
kipaumbele chini na hivi karibuni itathibitisha kuwa yeye ni kazi ndefu ambayo haifanyi
inahitaji majibu.
Mfano 3: Vipi kuhusu I/O?
Sasa hebu tuangalie mfano wa I/O. Kama ilivyoelezwa katika kanuni ya 4b,
ikiwa mchakato utatoa kichakataji bila kutumia wakati wake wa kichakataji kikamilifu,
basi inabaki katika kiwango kile kile cha kipaumbele. Kusudi la sheria hii ni rahisi sana
- ikiwa kazi ya maingiliano hufanya shughuli nyingi za I / O, kwa mfano, kusubiri
kutoka kwa vibonye vya mtumiaji au panya, kazi kama hiyo itafungua processor
kabla ya dirisha lililowekwa. Hatungependa kuacha kazi ya kipaumbele kama hii,
na hivyo itabaki katika kiwango kile kile.
Mfano huu unaonyesha jinsi algorithm ingefanya kazi na michakato kama hii - kazi inayoingiliana B, ambayo inahitaji tu CPU kwa 1ms kabla ya kutekeleza.
Mchakato wa I/O na kazi ndefu A, ambayo hutumia CPU wakati wote.
MLFQ huweka mchakato B katika kipaumbele cha juu zaidi unapoendelea
kutolewa kwa CPU. Ikiwa B ni kazi ya maingiliano, basi algorithm katika kesi hii imefikia
madhumuni yake ni kuzindua kazi maingiliano haraka.
Matatizo na algorithm ya sasa ya MLFQ
Katika mifano iliyopita, tumeunda toleo la msingi la MLFQ. Na inaonekana kwamba yeye
hufanya kazi yake vizuri na kwa haki, inasambaza wakati wa CPU kwa usawa kati
kazi ndefu na kuruhusu kazi fupi au kazi zinazofikiwa kwa wingi
fanyia kazi I/O haraka. Kwa bahati mbaya, mbinu hii ina kadhaa
matatizo makubwa.
Kwanza, tatizo la njaa: ikiwa mfumo una mwingiliano mwingi
kazi, zitatumia wakati wote wa CPU na kwa hivyo sio muda mrefu
kazi hiyo haitapata nafasi ya kutekelezwa (wana njaa).
Pili, watumiaji mahiri wangeweza kuandika programu zao ili
mpumbavu mpanga ratiba. Udanganyifu upo katika kufanya jambo ili kulazimisha
Kipanga ratiba kinaupa mchakato muda zaidi wa CPU. Algorithm hiyo
ilivyoelezwa hapo juu ni hatari kabisa kwa mashambulizi hayo: kabla ya dirisha la wakati ni kivitendo
zaidi, unahitaji kufanya operesheni ya I / O (kwa wengine, haijalishi ni faili gani)
na hivyo kufungua CPU. Tabia kama hiyo itawawezesha kukaa sawa
foleni yenyewe na tena kupata asilimia kubwa ya muda wa CPU. Ikifanyika
hii ni sahihi (kwa mfano, tekeleza 99% ya muda wa dirisha kabla ya kutoa CPU),
kazi kama hiyo inaweza tu kuhodhi processor.
Hatimaye, programu inaweza kubadilisha tabia yake baada ya muda. Kazi hizo
iliyotumia CPU inaweza kuingiliana. Katika mfano wetu, sawa
kazi hazitapokea matibabu ifaayo kutoka kwa mpanga ratiba, kama wengine wangepokea
(asili) kazi za mwingiliano.
Swali kwa watazamaji: ni mashambulizi gani kwa mpangaji yanaweza kufanywa katika ulimwengu wa kisasa?
Jaribio la 2: Ongeza kipaumbele
Wacha tujaribu kubadilisha sheria na tuone ikiwa tunaweza kuzuia shida nazo
njaa. Tunaweza kufanya nini ili kuhakikisha kuwa inahusiana
Kazi za CPU zitapata wakati wao (hata kama sio muda mrefu).
Kama suluhisho rahisi kwa shida, unaweza kupendekeza mara kwa mara
kuongeza kipaumbele cha kazi zote hizo katika mfumo. Kuna njia nyingi
ili kufikia hili, hebu jaribu kutekeleza kitu rahisi kama mfano: tafsiri
kazi zote mara moja kwa kipaumbele cha juu, kwa hivyo sheria mpya:
- Kanuni ya 5: Baada ya kipindi fulani S, hamishia kazi zote kwenye mfumo hadi kwenye foleni ya juu zaidi.
Sheria yetu mpya hutatua matatizo mawili mara moja. Kwanza, taratibu
umehakikishiwa kutokufa kwa njaa: majukumu katika foleni ya juu zaidi yatashirikiwa
wakati wa processor kulingana na algorithm ya RR na kwa hivyo michakato yote itapokea
muda wa processor. Pili, kama baadhi ya mchakato kwamba awali kutumika
tu processor inakuwa maingiliano, itabaki kwenye foleni na ya juu zaidi
kipaumbele baada ya kupokea nyongeza kwa kipaumbele cha juu mara moja.
Fikiria mfano mmoja. Katika hali hii, fikiria mchakato mmoja kutumia
CPU na michakato miwili inayoingiliana, fupi. Kwa upande wa kushoto katika takwimu, takwimu inaonyesha tabia bila kuongeza kipaumbele, na hivyo kazi ya muda mrefu huanza kufa njaa baada ya kazi mbili za maingiliano kufika kwenye mfumo. Katika mchoro ulio kulia, kila milisekunde 50 ongezeko la kipaumbele hufanywa na kwa hivyo michakato yote inahakikishiwa kupokea muda wa kichakataji na itaanzishwa mara kwa mara. 50ms katika kesi hii inachukuliwa kama mfano, kwa kweli nambari hii ni ya juu zaidi.
Ni dhahiri kwamba kuongezwa kwa muda wa kupanda mara kwa mara S husababisha
swali la kimantiki: ni thamani gani inapaswa kuwekwa? Mmoja wa wanaostahili
wahandisi wa mifumo John Ousterhout walitaja idadi sawa katika mifumo kama voo-doo
mara kwa mara, kwani kwa namna fulani walihitaji uchawi mweusi kwa sahihi
kuwemo hatarini. Na, kwa bahati mbaya, S ina ladha kama hiyo. Ukiweka thamani pia
kazi kubwa - ndefu zitakufa njaa. Na ikiwa utaiweka chini sana,
kazi zinazoingiliana hazitapokea wakati unaofaa wa CPU.
Jaribio la 3: Uhasibu Bora
Sasa tuna shida moja zaidi ya kutatua: jinsi sivyo
kuruhusu kudanganya mpangilio wetu? Wahalifu wa uwezekano huu ni
sheria 4a, 4b zinazoruhusu kazi kuweka kipaumbele chake kwa kufungia kichakataji
kabla ya kuisha kwa muda uliopangwa. Jinsi ya kukabiliana nayo?
Suluhisho katika kesi hii inaweza kuchukuliwa kuwa uhasibu bora wa wakati wa CPU kwa kila mmoja
Kiwango cha MLFQ. Badala ya kusahau wakati programu ilitumia
processor kwa muda uliopangwa, inapaswa kuzingatiwa na kuokolewa. Baada ya
mchakato umetumia muda wake uliopangwa, unapaswa kushushwa hadi mwingine
kiwango cha kipaumbele. Sasa haijalishi jinsi mchakato utatumia wakati wake - jinsi gani
kompyuta kila mara kwenye kichakataji au kama idadi ya simu. Hivyo,
sheria ya 4 inapaswa kuandikwa tena kama ifuatavyo:
- Kanuni ya 4: Baada ya kazi kutumia muda wake uliowekwa kwenye foleni ya sasa (bila kujali ni mara ngapi iliachilia CPU), kipaumbele cha kazi kama hiyo hupunguzwa (husogea chini ya foleni).
Hebu tuangalie mfano:
Β»
Takwimu inaonyesha kile kinachotokea ikiwa utajaribu kumdanganya mpangaji, kama
ikiwa ingekuwa na sheria za awali 4a, 4b ingekuwa matokeo upande wa kushoto. Na mpya
sheria ni matokeo ni upande wa kulia. Kabla ya ulinzi, mchakato wowote unaweza kupiga simu I/O kabla ya kukamilika na
hivyo kutawala CPU, baada ya kuwezesha ulinzi, bila kujali tabia
I/O, bado atashuka kwenye foleni na hivyo hataweza kufanya bila uaminifu
kuchukua rasilimali za CPU.
Kuboresha MLFQ na masuala mengine
Pamoja na maboresho hapo juu, matatizo mapya hutokea: moja ya kuu
Maswali - jinsi ya kuweka mpangilio wa mpangilio kama huo? Wale. Kiasi gani kinapaswa kuwa
foleni? Je, ukubwa wa dirisha la programu ndani ya foleni unapaswa kuwa ngapi? Vipi
Kipaumbele cha programu kinapaswa kuongezwa mara nyingi ili kuzuia njaa na
kuzingatia mabadiliko katika tabia ya programu? Hakuna jibu rahisi kwa maswali haya
jibu na majaribio tu na mizigo na usanidi unaofuata
mpangaji anaweza kusababisha usawa fulani wa kuridhisha.
Kwa mfano, utekelezaji mwingi wa MLFQ hukuruhusu kugawa tofauti
nafasi za muda kwa foleni tofauti. Foleni za kipaumbele cha juu ni kawaida
vipindi vifupi. Foleni hizi zinajumuisha kazi shirikishi,
kubadili kati ya ambayo ni nyeti kabisa na inapaswa kuchukua 10 au chini
ms. Kinyume chake, foleni za kipaumbele cha chini zinajumuisha kazi za muda mrefu zinazotumia
CPU. Na katika kesi hii, vipindi vya muda mrefu vinafaa sana (100ms).
Katika mfano huu kuna kazi 2 ambazo zilifanya kazi katika foleni ya 20 ya kipaumbele
ms imegawanywa katika madirisha 10 ms. 40ms katika foleni ya kati (dirisha la ms 20) na katika foleni ya kipaumbele cha chini
dirisha la muda wa foleni likawa 40ms ambapo kazi zilikamilisha kazi yao.
Utekelezaji wa MLFQ katika Mfumo wa Uendeshaji wa Solaris ni darasa la wapanga ratiba walioshirikiwa wakati.
Kipanga ratiba kitatoa seti ya majedwali ambayo yanafafanua hasa jinsi inavyopaswa
kubadilisha kipaumbele cha mchakato katika kipindi cha maisha yake, ni nini kinapaswa kuwa ukubwa
dirisha lililotengwa na ni mara ngapi unahitaji kuongeza vipaumbele vya kazi. Msimamizi
mfumo unaweza kuingiliana na jedwali hili na kufanya mpangaji afanye kazi
tofauti. Kwa chaguo-msingi, jedwali hili lina foleni 60 na ongezeko la taratibu
ukubwa wa dirisha kutoka 20ms (kipaumbele cha juu) hadi mia kadhaa ms (kipaumbele cha chini), na
pia kwa nyongeza ya kazi zote mara moja kwa sekunde.
Wapangaji ratiba wengine wa MLFQ hawatumii jedwali au mahususi yoyote
sheria ambazo zimeelezewa katika hotuba hii, kinyume chake, zinahesabu vipaumbele kwa kutumia
fomula za hisabati. Kwa mfano, kipanga ratiba katika FreeBSD hutumia fomula ya
kuhesabu kipaumbele cha kazi ya sasa kulingana na kiasi gani cha mchakato
alitumia CPU. Kwa kuongeza, matumizi ya CPU huoza kwa muda, na hivyo
Kwa hivyo, kuongezeka kwa kipaumbele hutokea tofauti na ilivyoelezwa hapo juu. Hii ni kweli
inayoitwa algorithms ya kuoza. Kuanzia toleo la 7.1, FreeBSD hutumia kipanga ratiba cha ULE.
Hatimaye, wapangaji wengi wana vipengele vingine. Kwa mfano, baadhi
wapangaji huhifadhi viwango vya juu zaidi vya uendeshaji wa mfumo wa uendeshaji na hivyo
Kwa hivyo, hakuna mchakato wa mtumiaji unaweza kupokea kipaumbele cha juu zaidi
mfumo. Mifumo mingine hukuruhusu kutoa ushauri wa kusaidia
mpangaji anaweza kuweka vipaumbele kwa usahihi. Kwa mfano, kwa kutumia amri nzuri
unaweza kuongeza au kupunguza kipaumbele cha kazi na hivyo kuongeza au kupunguza
punguza uwezekano wa programu kwa wakati wa CPU.
MLFQ: Muhtasari
Tumeelezea mbinu ya kupanga inayoitwa MLFQ. Jina lake
imefungwa katika kanuni ya uendeshaji - ina foleni kadhaa na hutumia maoni
kutanguliza kazi.
Fomu ya mwisho ya sheria itakuwa kama ifuatavyo:
- Kanuni ya 1: Ikiwa kipaumbele(A) > Kipaumbele(B), kazi A itaendeshwa (B haitafanya)
- Kanuni ya 2: Ikiwa kipaumbele(A) = Kipaumbele(B), A&B imeanza kutumia RR
- Kanuni ya 3: Kazi inapoingia kwenye mfumo, inawekwa kwenye foleni ya kipaumbele cha juu.
- Kanuni ya 4: Baada ya kazi kutumia muda wake uliowekwa kwenye foleni ya sasa (bila kujali ni mara ngapi iliachilia CPU), kipaumbele cha kazi kama hiyo hupunguzwa (husogea chini ya foleni).
- Kanuni ya 5: Baada ya kipindi fulani S, hamishia kazi zote kwenye mfumo hadi kwenye foleni ya juu zaidi.
MLFQ inavutia kwa sababu ifuatayo - badala ya kuhitaji maarifa kuhusu
asili ya kazi mapema, algorithm hujifunza tabia ya zamani ya kazi na seti
vipaumbele ipasavyo. Kwa hivyo, anajaribu kukaa kwenye viti viwili mara moja - kufikia tija kwa kazi ndogo (SJF, STCF) na kukimbia kwa muda mrefu kwa uaminifu,
Kazi za kupakia CPU. Kwa hivyo, mifumo mingi, pamoja na BSD na derivatives zao,
Solaris, Windows, Mac hutumia aina fulani ya algorithm kama kipanga ratiba
MLFQ kama msingi.
Vifaa vya ziada:
- (kompyuta)
Chanzo: mapenzi.com