Fampidirana ny Rafitra fiasana
Hey Habr! Te-hitondra ny sainao andian-dahatsoratra aho - fandikana literatiora iray mahaliana araka ny hevitro - OSTEP. Ity fitaovana ity dia miresaka lalina momba ny asan'ny rafitra miasa toy ny unix, izany hoe, miasa miaraka amin'ireo dingana, fandaharam-potoana isan-karazany, fitadidiana ary singa mitovy amin'izany izay mandrafitra OS maoderina. Hitanao eto ny tany am-boalohany amin'ny fitaovana rehetra . Azafady, mariho fa ny fandikan-teny dia natao tamin'ny fomba tsy matihanina (tena malalaka), saingy manantena aho fa nitazona ny dikany ankapobeny.
Ny asa laboratoara momba ity lohahevitra ity dia azo jerena eto:
Fizarana hafa:
Azonao atao ihany koa ny mijery ny fantsona ao amin'ny =)
Fampidirana ny scheduler
Ny fototry ny olana: Ahoana ny fomba famolavolana ny politikan'ny fandaharam-potoana
Ahoana no tokony handrafetana ny rafitra ara-politikan'ny fandaharam-potoana fototra? Inona no tokony ho vinavina fototra? Inona no metrika manan-danja? Inona no teknika fototra nampiasaina tamin'ny rafitra informatika tany am-boalohany?
Fiheverana enta-mavesatra
Alohan'ny hifanakalozan-kevitra momba ny politika azo atao, andeha aloha hanao fanatsorana vitsivitsy momba ireo dingana mandeha ao amin'ny rafitra, izay antsoina hoe asan'izy. Ny famaritana ny enta-mavesatry ny asa dia ampahany manan-danja amin'ny politikan'ny fanorenana, ary arakaraka ny ahafantaranao ny enta-mavesatry ny asa no hahatsara kokoa ny politika azonao soratana.
Andeha hataontsika ireto vinavina manaraka ireto momba ireo dingana mandeha ao amin'ny rafitra, antsoina koa hoe indraindray asa (asa). Saika tsy mitombina avokoa ireo vinavina ireo, fa ilaina amin’ny fampivelarana ny fisainana.
- Ny asa tsirairay dia mandeha amin'ny fotoana mitovy,
- Ny asa rehetra dia napetraka miaraka,
- Ny asa nomena dia miasa mandra-pahavitan'izany,
- Ny asa rehetra dia mampiasa CPU ihany,
- Ny fotoana fampandehanana ny asa tsirairay dia fantatra.
Metrics scheduler
Ho fanampin'ny vinavina sasany momba ny enta-mavesatra, ilaina ny fitaovana iray hafa hampitahana ny politikan'ny fandaharam-potoana samihafa: metrikan'ny fandaharam-potoana. Ny metric dia fandrefesana zavatra fotsiny. Misy metrika maromaro azo ampiasaina hampitahana ny mpandrindra.
Ohatra, hampiasa metric antsoina hoe fotoana fanodinana (fotoana fanodinana). Ny fotoan'ny fampandehanan-draharaha dia faritana ho ny fahasamihafan'ny fotoana fahavitan'ny asa sy ny fotoana fahatongavan'ny asa ao amin'ny rafitra.
Tturnaround=Tcompletion−Tarrival
Koa satria noheverinay fa tonga tamin'ny fotoana iray ny asa rehetra, dia Ta = 0 ary Tt = Tc. Hiova ho azy io sanda io rehefa ovaintsika ireo vinavina etsy ambony.
Metrika hafa - rariny (fahamarinana, fahamarinana). Ny vokatra sy ny fahamendrehana dia matetika mifanohitra amin'ny drafitra. Ohatra, ny mpandrindra dia mety hanatsara ny fampisehoana, fa amin'ny vidin'ny fiandrasana asa hafa hamitana, ka mampihena ny rariny.
FIRST IN FIRST OUT (FIFO)
Ny algorithm fototra indrindra azontsika ampiharina dia antsoina hoe FIFO na tonga voalohany (miditra), manompo voalohany (mivoaka). Ity algorithm ity dia manana tombony maro: tena mora ampiharina ary mifanaraka amin'ny hevitsika rehetra ary mahavita tsara ny asa.
Andeha isika hijery ohatra tsotra. Andeha atao hoe asa 3 no napetraka miaraka. Fa andeha hatao hoe tonga aloha kely noho ny hafa rehetra ny asa A, ka ho hita ao amin'ny lisitry ny famonoana alohan'ny hafa izany, toy ny B raha oharina amin'i C. Aoka hatao hoe hovonoina mandritra ny 10 segondra ny tsirairay amin'izy ireo. Inona no ho salanisan'ny fotoana hanatanterahana ireo asa ireo amin'ity tranga ity?
Amin'ny fanisana ny soatoavina - 10 + 20 + 30 ary mizara amin'ny 3, dia mahazo ny salan'isa famonoana programa mitovy amin'ny 20 segondra.
Andeha isika izao hiezaka hanova ny fiheverantsika. Indrindra indrindra, ny fiheverana 1 ary noho izany dia tsy hihevitra intsony isika fa mitovy ny fotoana hanatanterahana ny asa tsirairay. Ahoana no hataon’ny FIFO amin’ity indray mitoraka ity?
Raha ny fandehany fa ny fotoana fanatanterahana asa samihafa dia misy fiantraikany ratsy be amin'ny famokarana ny algorithm FIFO. Andeha hatao hoe haharitra 100 segondra ny asa A, raha mbola maharitra 10 segondra ny B sy C.
Araka ny hita amin'ny sary, ny salan'isa fotoana ho an'ny rafitra dia ho (100+110+120)/3=110. Ity vokatra ity dia antsoina hoe vokatry ny convoy, rehefa milahatra aorian'ny mpanjifa mavesatra ny mpanjifa sasany amin'ny fotoana fohy. Tahaka ny filaharana eo amin'ny fivarotana enta-madinika rehefa misy mpanjifa eo anoloanao miaraka amin'ny sarety feno. Ny vahaolana tsara indrindra amin'ny olana dia ny manandrana manova ny rejisitra na miala sasatra ary miaina lalina.
Asa fohy indrindra aloha
Azo atao ve ny mamaha toe-javatra mitovy amin'izany amin'ny dingana mavesatra? Azo antoka. Karazana drafitra iray hafa no antsoinaAsa fohy indrindra aloha (SJF). Ny algorithm-ny ihany koa dia tena primitive - araka ny dikan'ny anarana, ny asa fohy indrindra dia hatomboka voalohany, tsirairay avy.
Amin'ity ohatra ity, ny vokatry ny fampandehanana ireo dingana mitovy amin'izany dia ho fanatsarana ny salan'isan'ny fandaharam-potoana fanodinana ary hitovy amin'ny 50 tsy 110, izay efa ho in-2 tsara kokoa.
Noho izany, ho an'ny fiheverana nomena fa tonga amin'ny fotoana mitovy ny asa rehetra, ny algorithm SJF dia toa ny algorithm tsara indrindra. Na izany aza, toa mbola tsy mitombina ny fiheverantsika. Amin'ity indray mitoraka ity dia manova ny fiheverana 2 isika ary amin'ity indray mitoraka ity dia alaivo sary an-tsaina fa mety hisy ny asa amin'ny fotoana rehetra, fa tsy amin'ny fotoana iray ihany. Inona no olana mety hitarika izany?
Andeha hojerentsika fa ny asa A (100c) dia tonga aloha ary manomboka tanterahina. Amin'ny t=10, tonga ny asa B sy C, izay haharitra 10 segondra ny tsirairay. Noho izany ny salan'isan'ny fotoana famonoana dia (100+(110-10)+(120-10))3 = 103. Inona no azon'ny mpandrindra mba hanatsarana izany?
Fotoana fohy indrindra amin'ny fahavitana voalohany (STCF)
Mba hanatsarana ny toe-javatra, dia avelantsika ny eritreritra 3 fa ny fandaharana dia natomboka ary mandeha mandra-pahavitan'ny. Ho fanampin'izay, mila fanohanana fitaovana izahay ary, araka ny mety ho eritreretinao, dia hampiasainay fameram-potoana hanapaka asa mihazakazaka ary context switching. Noho izany, ny mpandrindra dia afaka manao zavatra amin'ny fotoana hahatongavan'ny asa B, C - atsaharo ny fanatanterahana ny asa A ary apetraho amin'ny fanodinana ny asa B sy C ary, aorian'ny fahavitan'izy ireo, dia manohy manatanteraka ny dingana A. Ny mpandrindra toy izany dia antsoina hoe STCFna Asa aloha.
Ny vokatr'ity planner ity dia izao vokatra manaraka izao: ((120-0)+(20-10)+(30-10))/3=50. Noho izany, ny fandaharam-potoana toy izany dia lasa tsara kokoa ho an'ny asantsika.
Fotoana mamaly metrika
Noho izany, raha fantatsika ny fotoana fampandehanan'ny asa ary ireo asa ireo dia mampiasa CPU fotsiny, dia ny STCF no vahaolana tsara indrindra. Ary indray mandeha tamin'ny fotoana voalohany dia niasa tsara ireo algorithm ireo. Na izany aza, ny mpampiasa izao dia mandany ny ankamaroan'ny fotoanany ao amin'ny terminal ary manantena traikefa interactive mamokatra. Noho izany dia nisy metric vaovao teraka - fotoana famaliana (valiny).
Kajy toy izao manaraka izao ny fotoana famaliana:
Tresponse=Tfirstrun−Tarrival
Noho izany, ho an'ny ohatra teo aloha, ny fotoana famaliana dia: A=0, B=0, C=10 (abg=3,33).
Ary hita fa ny algorithm STCF dia tsy dia tsara loatra amin'ny toe-javatra misy asa 3 tonga amin'ny fotoana mitovy - tsy maintsy miandry mandra-pahavitan'ny asa kely. Noho izany, ny algorithm dia tsara ho an'ny metrikan'ny fotoana fihodinana, fa ratsy ho an'ny metrika interactivity. Alaivo sary an-tsaina raha mipetraka eo amin'ny terminal ianao manandrana manoratra tarehintsoratra ao anaty tonian-dahatsoratra ary mila miandry 10 segondra mahery satria misy asa hafa mandray ny CPU. Tsy dia mahafinaritra.
Noho izany dia miatrika olana hafa isika - ahoana no ahafahantsika manamboatra fandaharam-potoana izay mora amin'ny fotoana famaliana?
Robin Round
Nisy algorithm novolavolaina hamahana ity olana ity Robin Round (RR). Ny hevitra fototra dia tena tsotra: raha tokony hanatanteraka asa mandra-pahavitan'izy ireo, dia hanatanteraka ilay asa mandritra ny fe-potoana iray (antsoina hoe tapa-potoana) ary avy eo dia mifindra amin'ny asa hafa avy amin'ny filaharana. Ny algorithm dia mamerina ny asany mandra-pahavitan'ny asa rehetra. Amin'ity tranga ity, ny fotoana fampandehanan'ny fandaharana dia tsy maintsy ho maromaro amin'ny fotoana izay hanakanan'ny fameram-potoana ny dingana. Ohatra, raha misy fameram-potoana manapaka ny dingana iray isaky ny x=10ms, dia tokony ho maromaro amin'ny 10 ny haben'ny varavarankelin'ny fanatanterahana ny dingana ary ho 10,20 na x*10.
Andeha hojerentsika ohatra: Ny asa ABC dia tonga miaraka amin'ny rafitra ary ny tsirairay amin'izy ireo dia te-hihazakazaka mandritra ny 5 segondra. Ny algorithm SJF dia hamita ny asa tsirairay alohan'ny hanombohana asa iray hafa. Mifanohitra amin'izany kosa, ny algorithm RR miaraka amin'ny varavarankely fanombohana = 1s dia handeha amin'ny asa toy izao manaraka izao (sary 4.3):
(SJF indray (ratsy amin'ny fotoana famaliana)
(Round Robin (tsara ho an'ny fotoana famaliana)
Ny salan'isan'ny fotoana valiny ho an'ny algorithm RR dia (0+1+2)/3=1, raha ho an'ny SJF (0+5+10)/3=5.
Lojika ny fiheverana fa ny varavarankelin'ny fotoana dia tena zava-dehibe ho an'ny RR; ny kely kokoa dia ny avo kokoa ny fotoana valiny. Na izany aza, tsy tokony hataonao kely loatra izany, satria ny fotoana fifandimbiasan'ny contexte dia handray anjara amin'ny fampisehoana ankapobeny ihany koa. Noho izany, ny safidy ny fotoana varavarankely famonoana dia napetraky ny OS architect ary miankina amin'ny asa izay kasaina hotanterahina ao. Ny fiovan'ny contexte dia tsy ny serivisy serivisy ihany no mandany fotoana - ny programa mihazakazaka dia miasa amin'ny zavatra maro hafa, ohatra, ny cache isan-karazany, ary isaky ny mifamadika dia ilaina ny mamonjy sy mamerina io tontolo io, izay mety haka be dia be. fotoana.
RR dia fandaharam-potoana tsara raha tsy miresaka afa-tsy ny metrikan'ny fotoana famaliana isika. Ahoana anefa no hitondran'ny metrikan'ny fotoana fanodinana asa miaraka amin'ity algorithm ity? Diniho ny ohatra etsy ambony, rehefa tonga amin'ny fotoana mitovy ny fotoana fiasan'ny A, B, C = 5s. Ny asa A dia hifarana amin'ny 13, B amin'ny 14, C amin'ny 15s ary ny salan'isan'ny fotoana fihodinana dia 14s. Noho izany, RR no algorithm ratsy indrindra ho an'ny metric turnover.
Amin'ny teny ankapobeny, ny algorithm RR-karazana rehetra dia ara-drariny; mizara ny fotoana CPU mitovy amin'ny dingana rehetra. Ary noho izany dia mifanipaka hatrany ireo metrika ireo.
Noho izany, manana algorithm maro mifanipaka isika ary miaraka amin'izay koa dia mbola misy vinavina maromaro tavela - fa fantatra ny fotoanan'ny asa ary ny CPU ihany no ampiasain'ilay asa.
Mifangaro amin'ny I/O
Voalohany indrindra, andao esorina ny fiheverana 4 fa ny processeur ihany no mampiasa azy; mazava ho azy fa tsy izany no izy ary afaka miditra amin'ny fitaovana hafa ny dingana.
Raha vao misy dingana mangataka fandidiana I/O, dia miditra amin'ny fanjakana voasakana ny dingana, miandry ny fahavitan'ny I/O. Raha alefa any amin'ny kapila mafy ny I/O, dia mety haharitra hatramin'ny ms maromaro na mihoatra ny fandidiana toy izany, ary tsy miasa ny processeur amin'izao fotoana izao. Mandritra io fotoana io, ny mpandrindra dia afaka mibodo ny processeur amin'ny dingana hafa. Ny fanapahan-kevitra manaraka tokony horaisin'ny mpandrindra dia ny fotoana hahavitan'ny dingana ny I/O azy. Rehefa mitranga izany dia hisy fiatoana hitranga ary ny OS dia hametraka ny dingana antsoina hoe I/O ho amin'ny fanjakana vonona.
Andeha isika hijery ohatra amin'ny olana maro. Ny tsirairay amin'izy ireo dia mitaky 50ms amin'ny fotoana CPU. Na izany aza, ny voalohany dia miditra amin'ny I/O isaky ny 10ms (izay hotanterahina isaky ny 10ms ihany koa). Ary ny process B dia mampiasa processeur 50ms tsy misy I/O.
Amin'ity ohatra ity dia hampiasa ny fandaharam-potoana STCF isika. Hanao ahoana ny fitondran-tenan'ny mpandrindra raha misy dingana toa an'i A atomboka ao? Izy no hanao izao manaraka izao: voalohany dia hanatanteraka tanteraka ny dingana A, ary avy eo ny dingana B.
Ny fomba nentim-paharazana hamahana ity olana ity dia ny fandraisana isaky ny 10 ms subtask amin'ny dingana A ho toy ny asa manokana. Noho izany, rehefa manomboka amin'ny algorithm STJF, dia miharihary ny safidy eo amin'ny asa 50 ms sy ny asa 10 ms. Avy eo, rehefa vita ny subtask A, dia hatomboka ny dingana B sy I/O. Rehefa vita ny I/O, dia mahazatra ny manomboka ny dingana 10ms A indray fa tsy ny dingana B. Amin'izany fomba izany dia azo atao ny mampihatra ny fifandimbiasana, izay ampiasain'ny processeur amin'ny dingana hafa raha ny voalohany dia miandry ny I/O. Ary vokatr'izany, ny rafitra dia ampiasaina tsara kokoa - amin'izao fotoana izao rehefa miandry ny I/O ny fizotran'ny interactive, dia azo tanterahina amin'ny processeur ny dingana hafa.
Tsy misy intsony ny Oracle
Ankehitriny andeha isika hanaisotra ny fiheverana fa fantatra ny fotoana fandehan'ny asa. Amin'ny ankapobeny dia io no fiheverana ratsy indrindra sy tsy mitombina indrindra amin'ny lisitra manontolo. Raha ny marina, ao amin'ny OS mahazatra mahazatra, ny OS mihitsy dia tsy mahafantatra firy momba ny fotoana hanatanterahana ny asa, koa ahoana no ahafahanao manangana fandaharam-potoana nefa tsy fantatrao hoe hafiriana no hanatanteraka ny asa? Angamba afaka mampiasa fitsipika RR isika hamahana ity olana ity?
Ny vokany
Nijery ireo hevitra fototra momba ny fandaharam-potoana izahay ary nijery fianakaviana 2 mpandrindra. Ny voalohany dia manomboka ny asa fohy indrindra aloha ary noho izany dia mampitombo ny fotoana fihodinana, raha ny faharoa dia rovitra mitovy amin'ny asa rehetra, mampitombo ny fotoana mamaly. Samy ratsy ireo algorithms izay tsara ny algorithm an'ny fianakaviana hafa. Nijery ihany koa izahay hoe ahoana no ahafahan'ny fampiasana mifanitsy amin'ny CPU sy I/O manatsara ny fampisehoana, saingy tsy namaha ny olana amin'ny OS clairvoyance. Ary amin'ny lesona manaraka dia hijery planner iray izay mijery ny lasa eo no ho eo isika ary manandrana maminavina ny ho avy. Ary antsoina hoe filaharana fanehoan-kevitra maromaro.
Source: www.habr.com