Gabatarwa zuwa Tsarukan Ayyuka

Hai Habr! Ina so in kawo muku jerin labarai-fassarar wallafe-wallafe guda ɗaya mai ban sha'awa a ra'ayina - OSTEP. Wannan abu yayi magana sosai game da aikin tsarin aiki-kamar unix, wato, aiki tare da matakai, masu tsarawa daban-daban, ƙwaƙwalwar ajiya, da sauran abubuwa makamantan waɗanda suka haɗa da OS na zamani. Kuna iya ganin asalin duk kayan anan a nan. Da fatan za a lura cewa fassarar an yi ta ne ba da ƙwararru ba (da yardar rai), amma ina fata na riƙe ma'anar gaba ɗaya.

Ana iya samun aikin Lab akan wannan batu a nan:

Sauran sassa:

Hakanan zaka iya duba tashar ta a sakon waya =)

Tsare-tsare: jerin gwano na Ba da amsa-Mataki masu yawa

A cikin wannan lacca, za mu yi magana game da matsalolin haɓaka ɗaya daga cikin shahararrun hanyoyin zuwa
tsarawa, wanda ake kira Queue Mai-Mataki Mai Girma (MLFQ). Fernando J. Corbató ya fara bayyana mai tsara tsarin MLFQ a cikin 1962 a cikin tsarin da ake kira.
Tsarin Raba Lokaci Mai jituwa (CTSS). Waɗannan ayyukan (ciki har da aiki daga baya
Multics) daga baya an zaɓi su don lambar yabo ta Turing. Mai tsara jadawalin ya kasance
daga baya ya inganta kuma ya sami kamannin da za a iya samu a ciki
wasu tsarin zamani.

Algorithm na MLFQ yana ƙoƙarin warware mahimman matsaloli guda 2 masu haɗuwa.
Da fari dai, yana ƙoƙarin inganta lokacin juyawa, wanda, kamar yadda muka tattauna a cikin laccar da ta gabata, an inganta shi ta hanyar farawa daga shugaban jerin gwano mafi kyau.
gajerun ayyuka. Koyaya, OS bai san tsawon lokacin da wannan ko wancan tsari zai gudana ba, kuma wannan
ilimin da ake buƙata don aikin SJF, STCF algorithms. Na biyu, MLFQ yayi kokari
sanya tsarin ya zama mai karɓa ga masu amfani (misali, ga waɗanda ke zaune da
kallon allon yayin jiran aikin don kammala) don haka rage girman lokaci
amsa. Abin takaici, algorithms kamar RR suna rage lokacin amsawa, amma
suna da mummunan tasiri akan ma'aunin lokacin juyawa. Saboda haka matsalarmu: Yadda ake tsarawa
mai tsara jadawalin da zai cika bukatunmu ba tare da sanin komai ba
yanayin tsarin, gaba ɗaya? Ta yaya mai tsara jadawalin zai koyi halayen ayyuka,
wanda yake ƙaddamarwa kuma don haka ya yanke shawarar tsara jadawalin mafi kyau?

Asalin matsalar: Yadda za a tsara saitin ayyuka ba tare da cikakken sani ba?
Yadda za a ƙirƙira jadawali wanda ke rage lokacin amsa lokaci guda
don ayyuka masu hulɗa kuma a lokaci guda yana rage girman lokacin juyawa ba tare da sani ba
sanin lokacin aiwatar da aiki?

Lura: koyo daga abubuwan da suka faru a baya

Layin MLFQ kyakkyawan misali ne na tsarin da aka horar da shi
abubuwan da suka faru a baya don hasashen makomar gaba. Irin waɗannan hanyoyin suna sau da yawa
samu a cikin OS (Da sauran rassa da yawa a cikin ilimin kwamfuta, gami da rassa
Hasashen hardware da caching algorithms). Makamantan yawo
kunna lokacin da ayyuka suna da matakan ɗabi'a kuma ana iya iya faɗi.
Duk da haka, ya kamata ku yi hankali da wannan fasaha saboda tsinkaya yana da sauƙi
na iya zama ba daidai ba kuma ya jagoranci tsarin don yanke shawara mafi muni fiye da
zai kasance maras ilimi kwata-kwata.

MLFQ: Dokokin Asali

Yi la'akari da ƙa'idodi na asali na MLFQ algorithm. Kuma ko da yake aiwatar da wannan algorithm
akwai da yawa, asali hanyoyin suna kama.
A cikin aiwatarwa da za mu yi la'akari, MLFQ zai sami da yawa
layuka daban-daban, kowannensu zai sami fifiko daban-daban. A kowane lokaci,
Aikin da aka shirya don aiwatarwa yana cikin layi ɗaya. MLFQ yana amfani da abubuwan fifiko,
don yanke shawarar aikin da za a gudanar don aiwatarwa, watau. aiki tare da mafi girma
fifiko (wani aiki daga jerin gwano tare da fifiko mafi girma) za a ƙaddamar da shi a farkon
jerin gwano.
Tabbas, ana iya samun aiki fiye da ɗaya a cikin wani layi na musamman, don haka
don haka za su sami fifiko iri ɗaya. A wannan yanayin, za a yi amfani da injin
RR don ƙaddamar da tsarawa tsakanin waɗannan ayyuka.
Don haka mun isa ƙa'idodi guda biyu na MLFQ:

Dokar 1: Idan fifiko (A)> fifiko (B), aikin A zai gudana (B ba zai yi ba)
Dokar 2: Idan fifiko (A) = fifiko (B), A&B an fara amfani da RR

Dangane da abubuwan da ke sama, mahimman abubuwa don tsara MLFQ sune
sune fifiko. Maimakon ba da takamaiman fifiko ga kowane
aiki, MLFQ yana canza fifikonsa dangane da halin da aka lura.
Misali, idan aiki akai-akai yana barin CPU yayin jiran shigar da madannai,
MLFQ zai ci gaba da fifikon tsarin saboda haka ne
m tsari ya kamata aiki. Idan, akasin haka, aikin yana da kullun kuma
CPU mai ƙarfi ne na dogon lokaci, MLFQ zai rage shi
fifiko. Don haka, MLFQ za ta yi nazarin halayen matakai a lokacin da suke gudana.
da amfani da halaye.
Bari mu zana misalin yadda jerin gwano za su yi kama a wani lokaci
lokaci sannan ku sami wani abu kamar haka:

A cikin wannan makirci, matakai 2 A da B suna cikin layi tare da fifiko mafi girma. Tsari
C yana wani wuri a tsakiya, kuma tsarin D yana a ƙarshen jerin gwano. Bisa ga abin da ke sama
kwatancin MLFQ algorithm, mai tsara jadawalin zai aiwatar da ayyuka tare da mafi girma kawai
fifiko bisa ga RR, da ayyuka C, D ba zai yi aiki ba.
A dabi'a, hoto mai tsayi ba zai ba da cikakken hoto na yadda MLFQ ke aiki ba.
Yana da mahimmanci a fahimci ainihin yadda hoton ke canzawa akan lokaci.

Ƙoƙari 1: Yadda ake canza fifiko

A wannan gaba, kuna buƙatar yanke shawarar yadda MLFQ zai canza matakin fifiko
aiki (da haka matsayin aikin a cikin jerin gwano) a lokacin zagayowar rayuwarsa. Domin
na wannan, kana buƙatar ka tuna da aikin aiki: wani adadi
ayyuka masu mu'amala tare da gajeriyar lokutan gudu (kuma don haka sau da yawa saki
CPU) da ayyuka masu tsayi da yawa waɗanda ke amfani da CPU duk lokacin aikin su, yayin
lokacin amsawa don irin waɗannan ayyuka ba shi da mahimmanci. Kuma don haka za ku iya yin ƙoƙari na farko
aiwatar da MLFQ algorithm tare da dokoki masu zuwa:

Dokar 3: Lokacin da aiki ya shiga tsarin, an sanya shi a cikin layi tare da mafi girma
fifiko.
Rule4a: Idan aiki yana amfani da taga gabaɗayan sa, to
an rage fifiko.
Rule4b: Idan Aiki ya saki CPU kafin taga lokacinsa ya ƙare, to
ya kasance tare da fifiko iri ɗaya.

Misali 1: Aiki guda ɗaya mai tsayi

Kamar yadda kuke gani a cikin wannan misalin, an saita aikin a shigar da mafi girma
fifiko. Bayan taga lokaci na 10ms, tsarin yana raguwa da fifiko.
mai tsarawa. Bayan taga na gaba, aikin yana ƙarshe rage zuwa
mafi ƙarancin fifiko a cikin tsarin, inda ya kasance.

Misali 2: Dauki ɗan gajeren aiki

Yanzu bari mu ga misali na yadda MLFQ zai yi ƙoƙarin kusanci SJF. A cikin haka
misali, ayyuka guda biyu: A, wanda aiki ne mai tsayin daka kullum
shagaltar da CPU da B, wanda ɗan gajeren aiki ne na mu'amala. A ce
cewa A ya riga ya yi aiki na ɗan lokaci a lokacin aikin B ya zo.

Wannan jadawali yana nuna sakamakon yanayin. Aiki A, kamar kowane aiki,
amfani da CPU ya kasance a ƙasa sosai. Task B zai zo a lokacin T=100 kuma zai
sanya a cikin mafi girman fifikon layi. Tunda lokacin gudu yayi gajere,
zai kammala kafin ya kai layin karshe.

Daga wannan misalin, ya kamata ku fahimci babban burin algorithm: tun da algorithm ba ya
ya san aiki mai tsawo ko gajere, sannan da farko ya dauka cewa aikin
gajere kuma yana ba shi fifiko mafi girma. Idan da gaske ne ɗan gajeren aiki, to
zai aiwatar da sauri, in ba haka ba idan aiki ne mai tsawo zai motsa a hankali
a cikin fifiko ƙasa kuma nan ba da jimawa ba za ta tabbatar da cewa lallai ita aiki ce mai tsayi da ba ta yi ba
yana bukatar amsa.

Misali 3: I/O fa?

Yanzu bari mu kalli misalin I/O. Kamar yadda aka fada a cikin doka ta 4b,
Idan tsari ya saki processor ba tare da amfani da duk lokacin aikin sa ba,
sannan ya kasance a matakin fifiko iri daya. Manufar wannan doka kyakkyawa ce mai sauƙi.
- idan aikin hulɗa yana yin I/O da yawa, alal misali, jira
daga maɓallan maɓalli ko linzamin kwamfuta, irin wannan aikin zai 'yantar da mai sarrafawa
kafin taga da aka ware. Ba za mu so mu bar irin wannan aikin fifiko ba,
kuma ta haka za ta kasance a matakin daya.

Wannan misalin yana nuna yadda algorithm zai yi aiki tare da irin waɗannan hanyoyin - aiki mai hulɗa B, wanda kawai ke buƙatar CPU don 1ms kafin aiwatarwa.
Tsarin I/O da dogon aiki A, wanda ke amfani da CPU koyaushe.
MLFQ yana kiyaye tsari na B a mafi fifiko yayin da yake ci gaba
saki CPU. Idan B aiki ne mai hulɗa, to, algorithm a cikin wannan yanayin ya kai
Manufarsa ita ce kaddamar da ayyuka masu mu'amala da sauri.

Matsaloli tare da algorithm na MLFQ na yanzu

A cikin misalan da suka gabata, mun gina ainihin sigar MLFQ. Kuma ga alama shi
yayi aikinsa da kyau kuma cikin adalci, yana rarraba lokacin CPU daidai tsakanin
ayyuka masu tsawo da ƙyale gajerun ayyuka ko ayyuka waɗanda ake isa ga su sosai
zuwa I/O don aiwatarwa da sauri. Abin takaici, wannan hanyar ta ƙunshi da yawa
matsaloli masu tsanani.
Da fari dai, Matsalar yunwa: idan tsarin zai kasance da yawa m
ayyuka, za su cinye duk lokacin CPU don haka ba tsawon lokaci ɗaya ba
aikin ba zai sami damar aiwatar da su ba (suna fama da yunwa).

Na biyu, masu amfani da wayo za su iya rubuta shirye-shiryen su don haka
yaudarar mai tsarawa. Yaudara ta ta'allaka ne a yin wani abu don tilastawa
mai tsarawa don ba da tsarin ƙarin lokacin CPU. Algorithm cewa
wanda aka bayyana a sama yana da rauni sosai ga irin waɗannan hare-haren: kafin taga lokaci a zahiri
ya ƙare, kuna buƙatar yin aikin I/O (ga wasu, ko da wane fayil)
don haka yantar da CPU. Irin wannan hali zai ba ku damar zama a cikin guda ɗaya
jerin gwanon kanta kuma ya sake samun yawan adadin lokacin CPU. Idan aka yi
wannan daidai ne (misali gudu 99% na lokacin taga kafin sakin CPU),
Irin wannan aikin zai iya ɗaukar nauyin sarrafawa kawai.

A ƙarshe, shirin na iya canza halayensa akan lokaci. Wadancan ayyuka
wanda yayi amfani da CPU zai iya zama mai mu'amala. A cikin misalinmu, kama
ayyuka ba za su sami ingantaccen magani daga mai tsarawa ba, kamar yadda wasu za su yi
(na asali) ayyuka masu mu'amala.

Tambaya ga masu sauraro: wane hare-hare a kan mai tsara tsarin za a iya yi a cikin zamani na zamani?

Ƙoƙari 2: Ƙara fifiko

Bari mu yi ƙoƙari mu canza dokoki kuma mu ga ko za mu iya guje wa matsaloli tare da
yunwa. Me za mu iya yi don tabbatar da wannan alaƙa
Ayyukan CPU za su sami lokacinsu (ko da ba dogon lokaci ba).
A matsayin mafita mai sauƙi ga matsalar, zaku iya ba da shawarar lokaci-lokaci
ƙara fifikon duk irin waɗannan ayyuka a cikin tsarin. Akwai hanyoyi da yawa
don cimma wannan, bari mu yi ƙoƙarin aiwatar da wani abu mai sauƙi a matsayin misali: fassara
duk ayyuka a lokaci ɗaya zuwa mafi fifiko, don haka sabuwar doka:

Dokar5: Bayan wasu lokuta S, canja wurin duk ayyuka a cikin tsarin zuwa mafi girman layi.

Sabuwar dokar mu tana magance matsaloli biyu lokaci guda. Na farko, hanyoyin
tabbacin ba za a ji yunwa ba: ayyuka a cikin mafi girman layi za su raba
processor lokaci bisa ga RR algorithm kuma ta haka ne duk matakai za su samu
CPU lokaci. Na biyu, idan wasu tsari da aka yi amfani da su a baya
kawai processor ya zama m, zai kasance a cikin jerin gwano tare da mafi girma
fifiko bayan karɓar haɓaka zuwa mafi girman fifiko sau ɗaya.
Ka yi la'akari da misali. A cikin wannan yanayin, yi la'akari da tsari guda ta amfani da

CPU da biyu m, gajerun matakai. A gefen hagu a cikin adadi, adadi yana nuna hali ba tare da haɓaka fifiko ba, don haka aikin mai tsawo yana farawa da yunwa bayan ayyuka biyu masu hulɗa sun zo kan tsarin. A cikin adadi a hannun dama, kowane 50ms ana yin haɓaka fifiko kuma don haka ana ba da tabbacin duk matakai don karɓar lokacin sarrafawa kuma za a fara lokaci-lokaci. 50ms a cikin wannan yanayin ana ɗaukar shi azaman misali, a zahiri wannan lambar ta ɗan fi girma.
A bayyane yake cewa ƙari na lokaci-lokaci tashin lokaci S yana kaiwa zuwa
tambaya mai ma'ana: menene darajar ya kamata a saita? Daya daga cikin wadanda suka cancanta
Injiniyoyin tsarin John Ousterhout sun yi magana game da adadi iri ɗaya a cikin tsarin kamar voo-doo
akai-akai, tun da sun ta wata hanya suna buƙatar baƙar sihiri don daidai
bayyana. Kuma, rashin alheri, S yana da irin wannan dandano. Idan kun saita ƙimar kuma
manyan - dogon ayyuka za su ji yunwa. Kuma idan kun saita darajar da ƙasa sosai.
ayyuka masu mu'amala ba za su sami lokacin CPU da ya dace ba.

Ƙoƙari Na Uku: Ingantattun Lissafi

Yanzu muna da ƙarin matsala guda ɗaya don warwarewa: yadda ba za a yi ba
bari mu yaudari mai tsara tsarin mu? Masu laifin wannan yiwuwar su ne
dokokin 4a, 4b waɗanda ke ba da damar aiki don ci gaba da fifikonsa ta hanyar 'yantar da na'ura
kafin cikar lokacin da aka ware. Yadda za a magance shi?
Maganin a cikin wannan yanayin ana iya la'akari da mafi kyawun lissafin lokacin CPU akan kowane
Babban darajar MLFQ. Maimakon manta lokacin da shirin ya yi amfani da shi
processor don tazarar da aka ware, yakamata kuyi la'akari da adana shi. Bayan
tsarin ya yi amfani da lokacin da aka ba shi, ya kamata a rage shi zuwa na gaba
matakin fifiko. Yanzu ba kome ba yadda tsarin zai yi amfani da lokacinsa - ta yaya
yin lissafi akai-akai akan processor ko azaman saitin kira. Don haka,
a sake rubuta doka ta 4 kamar haka:

Dokar4: Bayan wani aiki ya yi amfani da lokacin da aka keɓe shi a cikin jerin gwano na yanzu (ba tare da la'akari da sau nawa ya 'yantar da CPU ba), fifikon irin wannan aikin yana raguwa (yana motsa ƙasa).

Bari mu kalli misali:
»

Adadin ya nuna abin da zai faru idan kuna ƙoƙarin yaudarar mai tsarawa kamar
idan ya kasance tare da dokokin da suka gabata 4a, 4b zai zama sakamakon hagu. Da sabo
mulkin shine sakamakon yana kan dama. Kafin karewa, kowane tsari zai iya kiran I/O kafin kammalawa da
don haka mamaye CPU, bayan ba da damar kariya, ba tare da la’akari da halayen ba
I/O, har yanzu zai sauka a cikin jerin gwano don haka ba zai iya yin rashin gaskiya ba
kwace albarkatun CPU.

Inganta MLFQ da sauran batutuwa

Tare da haɓakawa na sama, sababbin matsaloli sun taso: ɗaya daga cikin manyan
tambayoyi - yadda za a parameterize irin wannan tsarawa? Wadancan. Nawa ya kamata ya zama
jerin gwano? Menene ya kamata girman taga shirin a cikin jerin gwano? Yaya
sau da yawa ya kamata a ba da fifikon shirin don guje wa yunwa da kuma
don la'akari da canjin halayen shirin? Ga waɗannan tambayoyin, babu mai sauƙi
amsa kuma kawai gwaje-gwaje tare da lodi da daidaitawa na gaba
mai tsarawa na iya haifar da ma'auni mai gamsarwa.

Misali, yawancin aiwatarwa na MLFQ suna ba ku damar sanya daban-daban
ramukan lokaci don layukan daban-daban. Yawancin layukan fifiko suna yawanci
gajeriyar tazara. Waɗannan layukan sun ƙunshi ayyuka masu hulɗa,
canzawa tsakanin wanda yake da matukar damuwa kuma yakamata ya ɗauki 10 ko ƙasa da haka
ms. Sabanin haka, ƙananan layukan da ba su da fifiko sun ƙunshi ayyuka masu tsawo waɗanda suke amfani da su
CPU. Kuma a wannan yanayin, tazarar lokaci mai tsawo ya dace sosai (100ms).

A cikin wannan misali, akwai ayyuka 2 waɗanda suka yi aiki a cikin babban fifikon layukan 20
ms ya kasu kashi 10ms windows. 40ms a tsakiyar layi (taga 20ms) kuma a cikin ƙananan fifikon layukan
taga lokacin layin ya zama 40ms inda ayyukan suka kammala aikinsu.

Aiwatar da MLFQ a cikin Solaris OS rukuni ne na masu tsara lokacin raba lokaci.
Mai tsara jadawalin zai samar da saitin tebur waɗanda ke ayyana daidai yadda ya kamata
canza fifikon tsarin a tsawon rayuwarsa, abin da ya kamata ya zama girman
taga da za a keɓe da kuma sau nawa za a ɗaga manyan abubuwan da aka fi dacewa da ɗawainiya. Mai gudanarwa
tsarin zai iya yin hulɗa tare da wannan tebur kuma ya sa mai tsarawa ya nuna hali
daban. Ta hanyar tsoho, wannan tebur yana da jerin gwano 60 tare da karuwa a hankali
Girman taga daga 20ms (babban fifiko) zuwa ɗaruruwan ms (mafi ƙarancin fifiko), da
Hakanan tare da haɓaka duk ayyuka sau ɗaya a sakan daya.

Sauran masu tsara tsarin MLFQ ba sa amfani da tebur ko kowane takamaiman
Dokokin da aka bayyana a cikin wannan babi, akasin haka, suna lissafin abubuwan da suka fi dacewa ta amfani da su
dabarun lissafi. Misali, mai tsarawa a cikin FreeBSD yana amfani da dabara don
ƙididdige fifikon aikin yanzu bisa nawa tsarin
amfani da CPU. Bugu da ƙari, amfani da CPU yana lalatawa akan lokaci, don haka
Don haka, haɓaka fifiko ya ɗan bambanta da yadda aka kwatanta a sama. Wannan gaskiya ne
ake kira lalata algorithms. Dangane da sigar 7.1, FreeBSD yana amfani da mai tsara UL.

A ƙarshe, yawancin masu tsarawa suna da wasu siffofi. Misali, wasu
masu tsara jadawalin tanadi mafi girma matakan don aiki na tsarin aiki da haka
Don haka, babu wani tsari na mai amfani da zai iya samun fifiko mafi girma a ciki
tsarin. Wasu tsarin suna ba ku damar ba da shawara don taimakawa
mai tsarawa don ba da fifiko daidai. Misali, ta amfani da umarnin nice
za ku iya ƙara ko rage fifikon aiki don haka ƙara ko raguwa
rage damar shirin don lokacin CPU.

MLFQ: Takaitawa

Mun bayyana tsarin tsari mai suna MLFQ. Sunansa
Ƙarshe a cikin ka'idar aiki - yana da layi da yawa kuma yana amfani da ra'ayi
don ba da fifiko ga aiki.
Tsarin ƙarshe na ƙa'idodin zai kasance kamar haka:

Dokar1: Idan fifiko (A)> fifiko (B), aikin A zai gudana (B ba zai yi ba)
Dokar2: Idan fifiko (A) = fifiko (B), A&B an fara amfani da RR
Dokar3: Lokacin da wani aiki ya shiga cikin tsarin, an sanya shi a cikin layi mafi fifiko.
Dokar4: Bayan wani aiki ya yi amfani da lokacin da aka keɓe shi a cikin jerin gwano na yanzu (ba tare da la'akari da sau nawa ya 'yantar da CPU ba), fifikon irin wannan aikin yana raguwa (yana motsa ƙasa).
Dokar5: Bayan wasu lokuta S, canja wurin duk ayyuka a cikin tsarin zuwa mafi girman layi.

MLFQ yana da ban sha'awa don dalilai masu zuwa - maimakon neman ilimi game da
yanayin aikin a gaba, algorithm ya koyi halin da ya gabata na aikin kuma ya saita
abubuwan fifiko daidai da haka. Don haka, yana ƙoƙari ya zauna a kan kujeru biyu lokaci guda - don cimma nasarar aiwatar da ƙananan ayyuka (SJF, STCF) kuma da gaske yana gudanar da dogon lokaci,
Ayyuka masu ɗaukar nauyin CPU. Saboda haka, yawancin tsarin, ciki har da BSD da abubuwan da suka samo asali,
Solaris, Windows, Mac suna amfani da wasu nau'ikan algorithm azaman mai tsarawa
MLFQ azaman tushe.

Materialsarin kayan:

source: www.habr.com

Tsarukan Aiki: Guda Sau Uku. Sashe na 5: Tsara: Tsare-tsare: jerin gwano na ba da amsa mai matakai (fassara)