Pasiuna sa Operating System
Hoy Habr! Gusto nako nga dad-on sa imong atensyon ang usa ka serye sa mga artikulo-paghubad sa usa ka makapaikag nga literatura sa akong opinyon - OSTEP. Gihisgutan sa kini nga materyal nga lawom ang trabaho sa mga operating system nga sama sa unix, nga mao, pagtrabaho kauban ang mga proseso, lainlaing mga scheduler, memorya, ug uban pang parehas nga mga sangkap nga naglangkob sa usa ka modernong OS. Makita nimo ang orihinal sa tanang materyales dinhi . Palihug timan-i nga ang paghubad gihimo nga dili propesyonal (medyo gawasnon), apan nanghinaut ko nga akong gihuptan ang kinatibuk-ang kahulugan.
Ang trabaho sa lab sa kini nga hilisgutan makita dinhi:
Ubang mga bahin:
Mahimo usab nimo tan-awon ang akong channel sa =)
Pasiuna sa Scheduler
Ang esensya sa problema: Giunsa paghimo ang usa ka palisiya sa scheduler
Sa unsang paagi ang nagpahiping mga gambalay sa palisiya sa scheduler gidisenyo? Unsa ang kinahanglan nga hinungdanon nga mga pangagpas? Unsang mga sukatan ang hinungdanon? Unsa nga sukaranan nga mga teknik ang gigamit sa sayo nga mga sistema sa kompyuter?
Mga Assumption sa Workload
Sa dili pa hisgotan ang posible nga mga palisiya, maghimo una kita og pipila ka pagpayano sa mga digression bahin sa mga proseso nga nagdagan sa sistema, nga gitawag nga kolektibo. kabug-at sa trabaho. Ang pagpasabot sa workload usa ka kritikal nga bahin sa pagtukod og mga polisiya, ug kon mas daghan ang imong nahibal-an mahitungod sa workload, mas maayo ang polisiya nga imong masulat.
Himoon nato ang mosunod nga mga pangagpas mahitungod sa mga proseso nga nagdagan sa sistema, usahay gitawag usab trabaho (mga buluhaton). Hapit tanan niini nga mga pangagpas dili realistiko, apan gikinahanglan alang sa pagpalambo sa panghunahuna.
- Ang matag buluhaton nagdagan sa parehas nga oras,
- Ang tanan nga mga buluhaton gitakda sa dungan,
- Ang gi-assign nga buluhaton molihok hangtod sa pagkompleto niini,
- Ang tanan nga mga buluhaton naggamit lamang sa CPU,
- Ang oras sa pagdagan sa matag buluhaton nahibal-an.
Mga Sukatan sa Scheduler
Dugang pa sa pipila ka mga pangagpas mahitungod sa load, laing himan sa pagtandi sa lain-laing mga polisiya sa pag-iskedyul gikinahanglan: scheduler metrics. Ang metric usa lang ka sukod sa usa ka butang. Adunay daghang mga sukatan nga magamit aron itandi ang mga scheduler.
Pananglitan, mogamit kami usa ka metric nga gitawag oras sa pag-usab (oras sa pag-usab). Ang oras sa turnaround sa buluhaton gihubit ingon ang kalainan tali sa oras sa pagkompleto sa buluhaton ug ang oras sa pag-abot sa buluhaton sa sistema.
Tturnaround=Tcompletion-Tarrival
Tungod kay among gihunahuna nga ang tanan nga mga buluhaton moabut sa parehas nga oras, unya Ta = 0 ug sa ingon Tt = Tc. Kini nga bili natural nga mausab kung usbon nato ang mga pangagpas sa ibabaw.
Laing metric - pagkamatarong (pagkamatarong, pagkamatinud-anon). Ang pagka-produktibo ug kaangayan kanunay nga magkasumpaki nga mga kinaiya sa pagplano. Pananglitan, ang scheduler mahimong mag-optimize sa performance, apan sa gasto sa paghulat alang sa ubang mga buluhaton nga modagan, sa ingon pagkunhod sa kaangayan.
FIRST IN FIRST OUT (FIFO)
Ang labing sukaranan nga algorithm nga mahimo natong ipatuman gitawag nga FIFO o unang nisulod (in), unang gisilbi (gawas). Kini nga algorithm adunay daghang mga bentaha: kini dali kaayo nga ipatuman ug kini mohaum sa tanan namong mga pangagpas ug maayo ang pagbuhat sa trabaho.
Atong tan-awon ang usa ka yano nga pananglitan. Ingnon ta nga 3 ka buluhaton ang dungan nga gitakda. Apan atong hunahunaon nga ang buluhaton A miabut sa usa ka gamay nga sayo kay sa tanan nga uban, mao nga kini makita sa execution listahan sa sayo pa kay sa uban, sama sa B paryente sa C. Atong hunahunaon nga ang matag usa kanila ipatuman sulod sa 10 segundos. Unsa ang kasagaran nga oras aron makompleto kini nga mga buluhaton sa kini nga kaso?
Pinaagi sa pag-ihap sa mga kantidad - 10 + 20 + 30 ug pagbahin sa 3, makuha namon ang kasagaran nga oras sa pagpatuman sa programa nga katumbas sa 20 segundos.
Karon atong sulayan nga usbon ang atong mga pangagpas. Sa partikular, ang assumption 1 ug sa ingon dili na nato isipon nga ang matag buluhaton nagkinahanglan sa samang gidugayon sa panahon sa pagpatuman. Unsaon pagpahigayon sa FIFO karong panahona?
Ingon sa nahibal-an, ang lainlaing mga oras sa pagpatuman sa buluhaton adunay negatibo nga epekto sa pagka-produktibo sa FIFO algorithm. Ibutang nato nga ang buluhaton A mokabat ug 100 ka segundos aron makompleto, samtang ang B ug C molungtad pa ug 10 ka segundos matag usa.
Ingon sa makita gikan sa numero, ang kasagaran nga oras alang sa sistema mahimong (100 + 110 + 120) / 3 = 110. Kini nga epekto gitawag epekto sa convoy, kung ang pipila ka mga mubu nga mga konsumedor sa usa ka kapanguhaan maglinya pagkahuman sa usa ka bug-at nga konsumedor. Sama sa linya sa grocery kung adunay usa ka kustomer sa imong atubangan nga puno sa kariton. Ang labing maayo nga solusyon sa problema mao ang pagsulay sa pag-usab sa cash register o pagrelaks ug pagginhawa og lawom.
Pinamubo nga Trabaho Una
Posible ba nga masulbad ang parehas nga kahimtang sa mga proseso sa bug-at nga timbang? Sigurado. Ang laing matang sa pagplano gitawagPinamubo nga Trabaho Una (SJF). Ang algorithm niini medyo primitive usab - sama sa gipasabut sa ngalan, ang pinakamubo nga mga buluhaton una nga ilunsad, sunod-sunod.
Sa kini nga pananglitan, ang resulta sa pagpadagan sa parehas nga mga proseso mahimong usa ka pag-uswag sa kasagaran nga oras sa pag-usab sa programa ug kini mahimong katumbas sa 50 imbis nga 110, nga halos 2 ka beses nga mas maayo.
Busa, alang sa gihatag nga pangagpas nga ang tanan nga mga buluhaton moabut sa parehas nga oras, ang SJF algorithm ingon ang labing kamalaumon nga algorithm. Bisan pa, ang among mga pangagpas ingon dili realistiko. Niining higayona atong usbon ang pangagpas 2 ug niining higayona hunahunaa nga ang mga buluhaton mahimong anaa sa bisan unsang oras, ug dili tanan sa samang higayon. Unsang mga problema ang mahimong mosangpot niini?
Hunahunaa nga ang buluhaton A (100c) moabut una ug magsugod sa pagpatuman. Sa t=10, ang mga buluhaton B ug C moabot, ang matag usa niini mokabat ug 10 segundos. Mao nga ang kasagaran nga oras sa pagpatuman mao ang (100+(110-10)+(120-10))3 = 103. Unsa ang mahimo sa scheduler aron mapauswag kini?
Pinamubo nga Panahon sa Pagkompleto Una (STCF)
Aron mapauswag ang sitwasyon, atong gilaktawan ang pangagpas 3 nga ang programa gilusad ug nagpadagan hangtod sa pagkompleto. Dugang pa, magkinahanglan kami og suporta sa hardware ug, ingon sa imong pagtag-an, among gamiton timer aron mabalda ang usa ka buluhaton nga nagdagan ug pagbalhin sa konteksto. Sa ingon, ang scheduler makahimo sa usa ka butang sa takna nga mga buluhaton B, C moabut - mohunong sa pagpatuman sa buluhaton A ug ibutang ang mga buluhaton B ug C ngadto sa pagproseso ug, human sa ilang pagkompleto, magpadayon sa pagpatuman sa proseso A. Ang maong scheduler gitawag STCFo Preemptive nga Trabaho Una.
Ang resulta niini nga tigplano mao ang mosunod nga resulta: ((120-0)+(20-10)+(30-10))/3=50. Sa ingon, ang ingon nga usa ka scheduler mahimong labi ka kamalaumon alang sa among mga buluhaton.
Sukatan nga Panahon sa Pagtubag
Busa, kung nahibal-an nato ang oras sa pagdagan sa mga buluhaton ug nga kini nga mga buluhaton naggamit lamang sa CPU, ang STCF mao ang pinakamaayo nga solusyon. Ug kausa sa unang mga panahon, kini nga mga algorithm nagtrabaho nga maayo. Bisan pa, ang tiggamit karon naggugol sa kadaghanan sa iyang oras sa terminal ug nagpaabut sa usa ka produktibo nga interactive nga kasinatian. Sa ingon natawo ang usa ka bag-ong sukatan - tubag sa Panahon (tubag).
Ang oras sa pagtubag gikalkula ingon sa mosunod:
Tresponse=TfirstrunβTarrival
Busa, alang sa miaging pananglitan, ang oras sa pagtubag mahimong: A=0, B=0, C=10 (abg=3,33).
Ug kini nahimo nga ang STCF algorithm dili kaayo maayo sa usa ka sitwasyon diin ang 3 nga mga buluhaton moabut sa samang higayon - kini kinahanglan nga maghulat hangtud nga ang gagmay nga mga buluhaton hingpit nga mahuman. Busa ang algorithm maayo alang sa turnaround time metric, apan dili maayo alang sa interactivity metric. Hunahunaa kung naglingkod ka sa usa ka terminal nga naningkamot sa pag-type sa mga karakter sa usa ka editor ug kinahanglan nga maghulat labaw pa sa 10 segundos tungod kay ang uban nga buluhaton nagkuha sa CPU. Dili kaayo nindot.
Mao nga nag-atubang kami sa lain nga problema - unsaon paghimo ang usa ka scheduler nga sensitibo sa oras sa pagtubag?
Round Robins
Usa ka algorithm ang gihimo aron masulbad kini nga problema Round Robins (RR). Ang sukaranan nga ideya yano ra: imbes nga magpadagan sa mga buluhaton hangtod makompleto, among daganon ang buluhaton sa usa ka piho nga yugto sa panahon (gitawag nga usa ka time slice) ug dayon mobalhin sa lain nga buluhaton gikan sa pila. Gisubli sa algorithm ang trabaho niini hangtod mahuman ang tanan nga buluhaton. Sa kini nga kaso, ang oras sa pagdagan sa programa kinahanglan nga usa ka multiple sa oras nga pagkahuman ang timer makabalda sa proseso. Pananglitan, kung ang usa ka timer makabalda sa usa ka proseso matag x=10ms, nan ang gidak-on sa window sa pagpatuman sa proseso kinahanglan nga usa ka multiple sa 10 ug mahimong 10,20 o x*10.
Atong tan-awon ang usa ka pananglitan: Ang mga buluhaton sa ABC dungan nga moabut sa sistema ug ang matag usa kanila gusto nga modagan sa 5 segundos. Ang SJF algorithm mokompleto sa matag buluhaton sa dili pa magsugod sa lain. Sa kasukwahi, ang RR algorithm nga adunay launch window = 1s moagi sa mga buluhaton sama sa mosunod (Fig. 4.3):
(SJF Pag-usab (Bad for Response Time)
(Round Robin (Maayo Alang sa Oras sa Pagtubag)
Ang kasagaran nga oras sa pagtubag alang sa RR algorithm mao ang (0+1+2)/3=1, samtang para sa SJF (0+5+10)/3=5.
Makataronganon ang paghunahuna nga ang window window usa ka importante kaayo nga parametro para sa RR; ang mas gamay niini, mas taas ang oras sa pagtubag. Bisan pa, dili nimo kini himuon nga gamay ra, tungod kay ang oras sa pagbalhin sa konteksto adunay papel usab sa kinatibuk-ang pasundayag. Sa ingon, ang pagpili sa oras sa bintana sa pagpatuman gitakda sa arkitekto sa OS ug nagdepende sa mga buluhaton nga giplano nga ipatuman niini. Ang pagbalhin sa konteksto dili lamang ang operasyon sa serbisyo nga nag-usik sa oras - ang nagdagan nga programa naglihok sa daghang uban pang mga butang, pananglitan, lainlaing mga cache, ug sa matag switch kinahanglan nga i-save ug ibalik kini nga palibot, nga mahimo usab nga daghang mga butang. panahon.
Ang RR usa ka maayo nga scheduler kung naghisgot lang kami bahin sa sukatan sa oras sa pagtubag. Apan sa unsang paagi molihok ang sukatan sa oras sa pagbalhin sa buluhaton sa kini nga algorithm? Hunahunaa ang pananglitan sa ibabaw, kung ang oras sa pag-opera sa A, B, C = 5s ug moabut sa parehas nga oras. Ang Buluhaton A matapos sa 13, B sa 14, C sa 15s ug ang kasagaran nga oras sa pag-turnover kay 14s. Busa, ang RR mao ang pinakagrabe nga algorithm alang sa turnover metric.
Sa mas kinatibuk-ang termino, ang bisan unsang RR-type nga algorithm patas; kini nagbahin sa oras sa CPU nga parehas sa tanan nga mga proseso. Ug sa ingon, kini nga mga sukatan kanunay nga magkasumpaki sa usag usa.
Sa ingon, kami adunay daghang magkalainlain nga mga algorithm ug sa parehas nga oras adunay nahabilin nga daghang mga pangagpas - nga nahibal-an ang oras sa buluhaton ug nga ang buluhaton naggamit lamang sa CPU.
Pagsagol sa I/O
Una sa tanan, atong tangtangon ang pangagpas 4 nga ang proseso naggamit lamang sa CPU; natural, dili kini ang kaso ug ang mga proseso maka-access sa ubang kagamitan.
Sa higayon nga ang bisan unsang proseso mangayo ug operasyon sa I/O, ang proseso mosulod sa gibabagan nga estado, nga maghulat nga makompleto ang I/O. Kung ang I/O gipadala sa hard drive, nan ang ingon nga operasyon mahimoβg molungtad hangtod sa pipila ka ms o mas dugay pa, ug ang processor mahimong walay pulos niining higayona. Atol niini nga panahon, ang scheduler mahimong okupar sa processor sa bisan unsa nga lain nga proseso. Ang sunod nga desisyon nga himuon sa scheduler mao kung kanus-a makompleto sa proseso ang I/O niini. Kung mahitabo kini, mahitabo ang usa ka interrupt ug ibutang sa OS ang proseso nga nagtawag sa I / O sa andam nga kahimtang.
Atong tan-awon ang usa ka pananglitan sa daghang mga problema. Ang matag usa kanila nanginahanglan 50ms sa oras sa CPU. Bisan pa, ang una maka-access sa I/O matag 10ms (nga ipatuman usab matag 10ms). Ug ang proseso B naggamit lang ug 50ms processor nga walay I/O.
Niini nga pananglitan atong gamiton ang STCF scheduler. Sa unsang paagi molihok ang scheduler kung ang usa ka proseso sama sa A gilansad niini? Buhaton niya ang mga musunud: una niya hingpit nga buhaton ang proseso A, ug dayon iproseso ang B.
Ang tradisyonal nga pamaagi sa pagsulbad niini nga problema mao ang pagtagad sa matag 10 ms subtask sa proseso A isip usa ka bulag nga buluhaton. Busa, sa pagsugod sa STJF algorithm, ang pagpili tali sa 50 ms nga buluhaton ug usa ka 10 ms nga buluhaton klaro. Unya, kung makompleto na ang subtask A, ang proseso B ug I/O ilunsad. Human makompleto ang I/O, naandan na nga sugdan pag-usab ang 10ms process A imbes nga proseso B. Niining paagiha, posible nga ipatuman ang overlap, diin ang CPU gigamit sa laing proseso samtang ang una naghulat sa I/O. Ug ingon nga resulta, ang sistema mas maayo nga gigamit - sa higayon nga ang mga interactive nga proseso naghulat alang sa I / O, ang ubang mga proseso mahimong ipatuman sa processor.
Wala na ang Oracle
Karon atong sulayan nga mawala ang pangagpas nga nahibal-an na ang oras sa pagdagan sa buluhaton. Kini sa kasagaran ang pinakagrabe ug labing dili realistiko nga pangagpas sa tibuok listahan. Sa tinuud, sa kasagaran nga ordinaryo nga OS, ang OS mismo sa kasagaran gamay ra ang nahibal-an bahin sa oras sa pagpatuman sa mga buluhaton, busa unsaon nimo paghimo ang usa ka scheduler nga wala nahibal-an kung unsa kadugay ang buluhaton aron mapatuman? Tingali mahimo natong gamiton ang pipila ka mga prinsipyo sa RR aron masulbad kini nga problema?
Ang resulta
Gitan-aw namo ang mga batakang ideya sa pag-iskedyul sa buluhaton ug gitan-aw ang 2 ka pamilya sa mga scheduler. Ang una magsugod sa pinakamubo nga buluhaton una ug sa ingon nagdugang sa turnaround nga oras, samtang ang ikaduha gibahin tali sa tanan nga mga buluhaton nga parehas, nagdugang sa oras sa pagtubag. Ang duha ka mga algorithm dili maayo diin ang mga algorithm sa laing pamilya maayo. Gitan-aw usab namon kung giunsa ang parehas nga paggamit sa CPU ug I / O makapauswag sa pasundayag, apan wala masulbad ang problema sa OS clairvoyance. Ug sa sunod nga leksyon atong tan-awon ang usa ka tigplano nga nagtan-aw sa dayon nga nangagi ug naningkamot sa pagtagna sa umaabot. Ug kini gitawag nga multi-level feedback queue.
Source: www.habr.com