Kenyelletso ea Litsamaiso tsa Ts'ebetso
Hey Habr! Ke kopa ho u hlokomelisa letoto la lihlooho-liphetolelo tsa lingoliloeng tse thahasellisang ka maikutlo a ka - OSTEP. Sengoliloeng sena se tšohla ka botebo mosebetsi oa lits'ebetso tse ts'oanang tsa unix, e leng, ts'ebetso ka lits'ebetso, li-schedule tse fapaneng, memori le likarolo tse ling tse tšoanang tse etsang OS ea sejoale-joale. U ka bona ea mantlha ea lisebelisoa tsohle mona . Ka kopo hlokomela hore phetolelo e entsoe ka mokhoa o sa sebetseng (ka bolokolohi), empa ke tšepa hore ke bolokile moelelo o akaretsang.
Mosebetsi oa Lab tabeng ena o ka fumanoa mona:
Likarolo tse ling:
U ka boela ua sheba mocha oa ka ho =)
Selelekela ho Mohlophisi
Moko oa bothata: Mokhoa oa ho theha leano la kemiso
Merero ea motheo ea leano la kemiso e lokela ho raloa joang? Likhopolo tsa bohlokoa e lokela ho ba life? Ke metrics efe ea bohlokoa? Ke mekhoa efe ea mantlha e neng e sebelisoa litsamaisong tsa pele tsa likhomphutha?
Maikutlo a Mosebetsi
Pele re buisana ka maano a ka bang teng, a re qaleng ka ho etsa likhakanyo tse 'maloa tse nolofatsang mabapi le lits'ebetso tse sebetsang tsamaisong, tse bitsoang ka kakaretso. boima ba mosebetsi. Ho hlalosa mosebetsi ke karolo ea bohlokoa ea maano a kaho, 'me ha u ntse u tseba haholoanyane ka boima ba mosebetsi, ho ntlafatsa pholisi eo u ka e ngolang.
Ha re etseng maikutlo a latelang mabapi le lits'ebetso tse sebetsang tsamaisong, ka linako tse ling hape li bitsoa sa jobs (mesebetsi). Hoo e ka bang mehopolo ena kaofela ha se ntho ea sebele, empa e hlokahala bakeng sa nts'etsopele ea monahano.
- Mosebetsi o mong le o mong o nka nako e lekanang,
- Mesebetsi eohle e behiloe ka nako e le 'ngoe,
- Mosebetsi oo a o abetsoeng o sebetsa ho fihlela o phethoa,
- Mesebetsi eohle e sebelisa CPU feela,
- Nako ea ho sebetsa ea mosebetsi o mong le o mong oa tsebahala.
Melemo ea Kemiso
Ntle le menahano e meng mabapi le mojaro, sesebelisoa se seng sa ho bapisa maano a fapaneng a kemiso sea hlokahala: metrics ea kemiso. Metric ke tekanyo e itseng feela ea ntho e itseng. Ho na le metrics e mengata e ka sebelisoang ho bapisa bahlophisi.
Ka mohlala, re tla sebelisa metric e bitsoang nako ea phetoho (nako ea phetoho). Nako ea ho fetola mosebetsi e hlalosoa e le phapang pakeng tsa nako ea ho phethela mosebetsi le nako ea ho fihla ha mosebetsi tsamaisong.
Tturnaround=Qetellong−Tarrival
Kaha re ne re nka hore mesebetsi eohle e fihlile ka nako e le 'ngoe, joale Ta=0' me kahoo Tt=Tc. Boleng bona bo tla fetoha ka tlhaho ha re fetola maikutlo a ka holimo.
Metric e 'ngoe - ho hloka toka ( toka, botshepehi). Hangata tlhahiso le toka ke litšobotsi tse hanyetsanang moralong. Ka mohlala, mohlophisi a ka ntlafatsa ts'ebetso, empa ka litšenyehelo tsa ho emela hore mesebetsi e meng e sebetse, kahoo e fokotsa toka.
PELE HO PELE (FIFO)
Algorithm ea mantlha eo re ka e sebelisang e bitsoa FIFO kapa ho tla pele (ho kena), ho sebeletsoa pele (ho tsoa). Algorithm ena e na le melemo e mengata: e bonolo haholo ho e sebelisa ebile e lumellana le mehopolo eohle ea rona mme e etsa mosebetsi hantle.
A re shebeng mohlala o bonolo. Ha re re mesebetsi e 3 e ne e behiloe ka nako e le 'ngoe. Empa ha re nke hore mosebetsi oa A o fihlile pejana ho feta tse ling kaofela, kahoo o tla hlaha lethathamong la ho bolaoa pele ho tse ling, joalo ka B e amanang le C. A re nke hore e mong le e mong oa bona o tla etsoa ka metsotsoana e 10. Nako e tloaelehileng ea ho qeta mesebetsi ee e tla ba efe tabeng ee?
Ka ho bala litekanyetso - 10+20+30 le ho arola ka 3, re fumana nako e tloaelehileng ea ts'ebetso ea lenaneo e lekanang le metsotsoana e 20.
Joale ha re lekeng ho fetola maikutlo a rona. Haholo-holo, monahano oa 1 mme ka hona re ke ke ra hlola re nka hore mosebetsi o mong le o mong o nka nako e lekanang ho e phetha. FIFO e tla sebetsa joang nakong ee?
Kamoo ho bonahalang kateng, linako tse fapaneng tsa ho phethahatsa mesebetsi li na le phello e mpe haholo tlhahisong ea algorithm ea FIFO. Ha re nke hore mosebetsi oa A o tla nka metsotsoana e 100 ho qeta, ha B le C li ntse li tla nka metsotsoana e 10 e 'ngoe le e 'ngoe.
Joalokaha ho ka bonoa setšoantšong, nako e tloaelehileng ea tsamaiso e tla ba (100+110+120)/3=110. Phello ena e bitsoa phello ea convoy, ha bareki ba bang ba nako e khuts'oane ba sesebelisoa ba tla koloka kamora moreki ea boima. Ho tšoana le mola lebenkeleng la korosari ha ho na le moreki ka pel'a hao ea nang le kariki e tletseng. Tharollo e molemohali ea bothata ke ho leka ho fetola ngoliso ea chelete kapa ho phomola le ho hema ka botebo.
Mosebetsi o Mokhuts'oanyane Pele
Na hoa khoneha ho rarolla boemo bo tšoanang ka mekhoa ea boima bo boima ka tsela e itseng? Ka sebele. Mofuta o mong oa moralo o bitsoaMosebetsi o Mokhuts'oanyane Pele (SJF). Algorithm ea eona le eona ke ea khale haholo - joalo ka ha lebitso le bolela, mesebetsi e khuts'oane e tla qalisoa pele, ka mor'a e 'ngoe.
Mohlaleng ona, sephetho sa ho tsamaisa lits'ebetso tse ts'oanang e tla ba ntlafatso ea nako e tloaelehileng ea ho fetolela lenaneo mme e tla lekana le 50 sebakeng sa 110, e leng hoo e ka bang makhetlo a 2 ho feta.
Kahoo, bakeng sa maikutlo a fanoeng a hore mesebetsi eohle e fihla ka nako e le 'ngoe, algorithm ea SJF e bonahala e le eona e nepahetseng ka ho fetisisa. Leha ho le joalo, mehopolo ea rōna e ntse e bonahala e sa utloahale. Lekhetlong lena re fetola maikutlo a 2 mme lekhetlong lena re nahana hore mesebetsi e ka ba teng ka nako efe kapa efe, eseng kaofela ka nako e le 'ngoe. See se ka baka mathata afe?
Ha re nahane hore mosebetsi A (100c) o fihla pele mme o qala ho phethoa. Ho t=10, mesebetsi ea B le C ea fihla, e 'ngoe le e 'ngoe ea tsona e tla nka metsotsoana e 10. Kahoo nako e tloaelehileng ea ho phethahatsa ke (100+(110-10)+(120-10))3 = 103. Mohlophisi o ne a ka etsa eng ho ntlafatsa see?
Nako e Khutšoanyane ea ho Qetela Pele (STCF)
E le ho ntlafatsa boemo, re siea maikutlo a 3 a hore lenaneo le qalisoa 'me le sebetsa ho fihlela le phethoa. Ho phaella moo, re tla hloka tšehetso ea hardware, 'me, joalokaha u ka nahana, re tla e sebelisa selekanyi ho sitisa mosebetsi o mathang le ho fetola maemo. Kahoo, mohlophisi a ka etsa ho hong ka nako eo mesebetsi ea B, C e fihlang - emisa ho etsa mosebetsi oa A ebe o kenya mesebetsi ea B le C ts'ebetsong, 'me ka mor'a hore e phethe, tsoela pele ho phethahatsa A. Mohlophisi ea joalo o bitsoa STCFkapa Mosebetsi oa Pele oa Pele.
Sephetho sa moralo ona e tla ba sephetho se latelang: ((120-0)+(20-10)+(30-10))/3=50. Kahoo, kemiso e joalo e ba ea loketseng le ho feta bakeng sa mesebetsi ea rona.
Nako ea Karabelo ea Metric
Kahoo, haeba re tseba nako ea ho sebetsa ea mesebetsi le hore mesebetsi ena e sebelisa CPU feela, STCF e tla ba tharollo e molemohali. 'Me hang linakong tsa pele, li-algorithms tsena li ne li sebetsa hantle haholo. Leha ho le joalo, mosebelisi hona joale o qeta boholo ba nako ea hae a le setsing sa polokelo mme o lebelletse boiphihlelo bo monate ba ho sebelisana. Kahoo metric e ncha e ile ea hlaha - nako ea karabo (karabo).
Nako ea karabo e baloa ka tsela e latelang:
Tresponse=Tfirstrun−Tarrival
Kahoo, bakeng sa mohlala o fetileng, nako ea karabo e tla ba: A=0, B=0, C=10 (abg=3,33).
'Me ho hlaha hore algorithm ea STCF ha e ntle hakaalo boemong boo mesebetsi ea 3 e fihlang ka nako e le' ngoe - e tla tlameha ho ema ho fihlela mesebetsi e nyenyane e phethoa ka ho feletseng. Kahoo algorithm e ntle bakeng sa metric ea nako ea phetoho, empa e mpe bakeng sa metric ea interactivity. Ak'u nahane haeba u ne u lutse setulong u leka ho thaepa litlhaku ho mohlophisi 'me u tlameha ho ema metsotsoana e fetang 10 hobane mosebetsi o mong o ne o nka CPU. Ha e monate haholo.
Kahoo re tobane le bothata bo bong - re ka theha moralo oa kemiso o tsotellang nako ea karabo joang?
Round Robins
Ho ile ha etsoa algorithm ho rarolla bothata bona Round Robins (RR). Mohopolo oa mantlha o bonolo haholo: sebakeng sa ho tsamaisa mesebetsi ho fihlela e phethoa, re tla tsamaisa mosebetsi ka nako e itseng (e bitsoang selae sa nako) ebe re fetohela mosebetsing o mong ho tloha moleng. Algorithm e pheta mosebetsi oa eona ho fihlela mesebetsi eohle e phethiloe. Tabeng ena, nako ea ho sebetsa ea lenaneo e tlameha ho ba makhetlo a mangata ka mor'a moo nako e tla sitisa ts'ebetso. Ka mohlala, haeba sebali sa nako se sitisa tšebetso e 'ngoe le e 'ngoe x=10ms, joale boholo ba fensetere ea ts'ebetso e lokela ho ba makhetlo a 10 'me e be 10,20 kapa x*10.
Ha re shebeng mohlala: Mesebetsi ea ABC e fihla ka nako e le 'ngoe tsamaisong' me e 'ngoe le e' ngoe ea tsona e batla ho matha metsotsoana e 5. Algorithm ea SJF e tla phethela mosebetsi o mong le o mong ho fihlela o phethoa pele o qala o mong. Ka lehlakoreng le leng, algorithm ea RR e nang le fensetere ea ho qala = 1s e tla feta mesebetsing ka tsela e latelang (Setšoantšo sa 4.3):
(SJF Hape (Hampe bakeng sa Nako ea Karabo)
(Round Robin (Hantle Bakeng sa Nako ea Karabo)
Karolelano ea nako ea karabo bakeng sa algorithm ea RR ke (0+1+2)/3=1, ha e le bakeng sa SJF (0+5+10)/3=5.
Hoa utloahala ho nahana hore fensetere ea nako ke parameter ea bohlokoa haholo bakeng sa RR; ha e nyane, nako ea karabo e phahame. Leha ho le joalo, ha ua lokela ho e etsa e nyane haholo, kaha nako ea ho fetola maemo le eona e tla phetha karolo ea ts'ebetso ka kakaretso. Kahoo, khetho ea nako ea fensetere ea ts'ebetso e behiloe ke moetsi oa meralo ea OS mme e itšetlehile ka mesebetsi e reriloeng ho etsoa ho eona. Ho fetola maemo ha se eona feela ts'ebetso ea ts'ebeletso e senyang nako - lenaneo le sebetsang le sebetsa linthong tse ling tse ngata, mohlala, li-cache tse fapa-fapaneng, 'me ka phetoho e' ngoe le e 'ngoe ho hlokahala ho boloka le ho tsosolosa tikoloho ena, e ka boela ea nka nako e ngata. nako.
RR ke kemiso e ntle haeba re ne re bua feela ka metric ea nako ea karabelo. Empa metric ea nako ea ho fetola mosebetsi e tla sebetsa joang ka algorithm ee? Nahana ka mohlala o ka holimo, ha nako ea ts'ebetso ea A, B, C = 5s 'me e fihla ka nako e le' ngoe. Mosebetsi A o tla fela ka 13, B ka 14, C ka 15s mme nako e tloaelehileng ea ho fetola e tla ba 14s. Kahoo, RR ke algorithm e mpe ka ho fetisisa bakeng sa metric ea phetoho.
Ka mantsoe a akaretsang, algorithm efe kapa efe ea mofuta oa RR e lokile; e arola nako ea CPU ka ho lekana lipakeng tsa lits'ebetso tsohle. Ka hona, metrics ena e lula e hanyetsana.
Kahoo, re na le li-algorithms tse fapaneng tse fapaneng 'me ka nako e ts'oanang ho ntse ho e-na le mehopolo e mengata e setseng - hore nako ea mosebetsi e tsejoa le hore mosebetsi o sebelisa CPU feela.
Ho kopanya le I/O
Pele ho tsohle, ha re tloseng monahano oa 4 oa hore ts'ebetso e sebelisa CPU feela; ka tlhaho, ha ho joalo mme lits'ebetso li ka fihlella lisebelisoa tse ling.
Hang ha ts'ebetso leha e le efe e kopa ts'ebetso ea I / O, ts'ebetso e kena sebakeng se koetsoeng, e emetse hore I / O e phethe. Haeba I / O e romelloa ho hard drive, joale ts'ebetso e joalo e ka nka ho fihlela ho ms tse 'maloa kapa nako e telele,' me processor e tla be e sa sebetse ka nako ena. Ka nako ena, kemiso e ka nka processor ka ts'ebetso efe kapa efe. Qeto e latelang eo mohlophisi a tla tlameha ho e etsa ke ha ts'ebetso e tla phethela I/O ea eona. Ha sena se etsahala, ho tla ba le tšitiso 'me OS e tla beha ts'ebetso e bitsitseng I / O boemong bo loketseng.
Ha re shebeng mohlala oa mesebetsi e mengata. E 'ngoe le e' ngoe ea tsona e hloka 50ms ea nako ea CPU. Leha ho le joalo, oa pele o tla fumana I/O ho 10ms e 'ngoe le e 'ngoe (e tla etsoa hape ka 10ms e 'ngoe le e 'ngoe). Mme process B e sebelisa processor ea 50ms ntle le I/O.
Mohlaleng ona re tla sebelisa kemiso ea STCF. Sehlophisi se tla itšoara joang haeba ts'ebetso e kang A e qalisoa ho eona? O tla etsa tse latelang: pele o tla sebetsa ka botlalo mokhoa oa A, ebe o sebetsa B.
Mokhoa o tloaelehileng oa ho rarolla bothata bona ke ho tšoara mosebetsi o mong le o mong oa 10 ms oa mokhoa oa A e le mosebetsi o arohaneng. Kahoo, ha u qala ka algorithm ea STJF, khetho pakeng tsa mosebetsi oa 50 ms le mosebetsi oa 10 ms e totobetse. Joale, ha mosebetsi o monyane A o phethiloe, tšebetso ea B le I/O e tla hlahisoa. Ka mor'a hore I / O e phethe, e tla ba tloaelo ho qala ts'ebetso ea 10ms A hape sebakeng sa B. Ka tsela ena, hoa khoneha ho kenya ts'ebetsong ho kopana, moo CPU e sebelisoang ke ts'ebetso e 'ngoe ha ea pele e emetse. I/O. 'Me ka lebaka leo, tsamaiso e sebelisoa hamolemo - ka nako eo mekhoa e kopanetsoeng e emetse I / O, mekhoa e meng e ka etsoa ho processor.
Oracle ha e sa le eo
Joale a re lekeng ho tlosa maikutlo a hore nako ea ho sebetsa ea mosebetsi e tsejoa. Ka kakaretso ena ke maikutlo a mabe ka ho fetesisa le a sa utloahaleng lethathamong lohle. Ha e le hantle, ho OS e tloaelehileng, OS ka boeona hangata e tseba ho fokolang haholo ka nako ea ts'ebetso ea mesebetsi, joale u ka haha mohlophisi joang ntle le ho tseba hore na mosebetsi o tla nka nako e kae ho e phetha? Mohlomong re ka sebelisa melao-motheo ea RR ho rarolla bothata bona?
Phello
Re ile ra sheba mehopolo ea mantlha ea kemiso ea mosebetsi mme ra sheba malapa a 2 a bahlophisi. Ea pele e qala mosebetsi o mokhutšoanyane ka ho fetisisa pele 'me kahoo e eketsa nako ea ho fetola, ha ea bobeli e arotsoe pakeng tsa mesebetsi eohle ka ho lekana, e eketsa nako ea ho arabela. Li-algorithms ka bobeli li mpe moo li-algorithms tsa lelapa le leng li leng ntle. Re boetse re shebile hore na tšebeliso e tšoanang ea CPU le I/O e ka ntlafatsa ts'ebetso joang, empa ha ea ka ea rarolla bothata ka OS clairvoyance. 'Me thutong e latelang re tla sheba moralo o shebang se etsahetseng haufinyane mme o leka ho bolela bokamoso. 'Me e bitsoa "multi-level feedback queue".
Source: www.habr.com