Sistema Eragileen Sarrera
Aupa Habr! Nire ustez, literatura interesgarri baten artikulu-itzulpen sorta bat ekarri nahi dizuet - OSTEP. Material honek unix antzeko sistema eragileen lana sakonki eztabaidatzen du, hots, sistema eragile modernoa osatzen duten prozesuekin, hainbat programatzailerekin, memoriarekin eta antzeko beste osagaiekin lan egitea. Material guztien jatorrizkoa hemen ikus dezakezu . Kontuan izan itzulpena modu profesionalik gabe egin dela (nahiko askatasunez), baina espero dut esanahi orokorra mantendu dudala.
Gai honi buruzko laborategiko lanak hemen aurki daitezke:
Beste zati batzuk:
Nire kanala ere ikus dezakezu hemen =)
Scheduler-en sarrera
Arazoaren funtsa: nola garatu programatzaile-politika
Nola diseinatu behar dira azpian dauden programatzaileen politika-esparruak? Zeintzuk izan behar dira funtsezko hipotesiak? Zein neurri dira garrantzitsuak? Zein oinarrizko teknika erabiltzen ziren lehen informatika-sistemetan?
Lan-kargaren hipotesiak
Politika posibleei buruz eztabaidatu aurretik, egin ditzagun sisteman martxan dauden prozesuei buruzko digresio sinplifikatzaile batzuk, kolektiboki deitzen direnak. lan karga. Lan-karga zehaztea politika eraikitzeko atal kritikoa da, eta zenbat eta gehiago jakin lan-kargari buruz, orduan eta hobeto idatzi dezakezu politika.
Egin ditzagun hurrengo hipotesiak sisteman exekutatzen diren prozesuei buruz, batzuetan ere deituak lanpostu (zereginak). Suposizio horiek ia guztiak ez dira errealistak, baina beharrezkoak dira pentsamenduaren garapenerako.
- Zeregin bakoitza denbora-tarte berean exekutatzen da,
- Zeregin guztiak aldi berean ezartzen dira,
- Esleitutako zereginak amaitu arte funtzionatzen du,
- Zeregin guztiek CPU soilik erabiltzen dute,
- Zeregin bakoitzaren exekuzio-denbora ezagutzen da.
Planifikatzailearen neurketak
Kargaren inguruko hipotesi batzuez gain, planifikazio-politika desberdinak alderatzeko beste tresna bat behar da: programatzaileen neurketak. Metrika zerbaiten neurri bat besterik ez da. Programatzaileak alderatzeko erabil daitezkeen zenbait neurketa daude.
Adibidez, izeneko metrika bat erabiliko dugu buelta emateko denbora (erantzuteko denbora). Zereginaren buelta-denbora sisteman zereginak amaitzeko denboraren eta ataza iristeko denboraren arteko aldea bezala definitzen da.
Tturnaround=Tbukatzea−Iritsiera
Zeregin guztiak aldi berean iristen zirela suposatu genuenez, orduan Ta=0 eta, beraz, Tt=Tc. Balio hori berez aldatuko da goiko hipotesiak aldatzen ditugunean.
Beste metrika bat - zuzentasuna (zuzentasuna, zintzotasuna). Produktibitatea eta zuzentasuna plangintzan ezaugarri kontrajarriak izan ohi dira. Esaterako, programatzaileak errendimendua optimiza dezake, baina beste zeregin batzuk exekutatzen zain egotearen kostuarekin, eta horrela zuzentasuna murriztuz.
LEHENENGOA LEHENENGOA (FIFO)
Ezar dezakegun algoritmorik oinarrizkoena FIFO edo deitzen da lehen etorri (sartzen), lehen zerbitzatu (kanpora). Algoritmo honek hainbat abantaila ditu: inplementatzeko oso erraza da eta gure hipotesi guztietara egokitzen da eta nahiko ondo egiten du lana.
Ikus dezagun adibide sinple bat. Demagun 3 zeregin ezarri zirela aldi berean. Baina demagun A zeregina beste guztiak baino apur bat lehenago iritsi zela, beraz, exekuzio-zerrendan besteak baino lehenago agertuko da, B C-ren aldean bezala. Demagun horietako bakoitza 10 segundoz exekutatu egingo dela. Zein izango da kasu honetan zeregin horiek burutzeko batez besteko denbora?
Balioak - 10 + 20 + 30 zenbatuta eta 3z zatituz, programaren batez besteko exekuzio denbora 20 segundokoa izango da.
Orain saia gaitezen gure hipotesiak aldatzen. Bereziki, 1. suposizioa eta, beraz, ez dugu gehiago suposatuko zeregin bakoitzak exekutatzeko denbora berdina behar duela. Nola jokatuko du FIFOk oraingoan?
Ikusten denez, zereginen exekuzio denbora ezberdinek eragin oso negatiboa dute FIFO algoritmoaren produktibitatean. Demagun A zereginak 100 segundo beharko dituela burutzeko, eta B eta C-k, berriz, 10 segundo beharko dituzte.
Irudian ikusten denez, sistemaren batez besteko denbora (100+110+120)/3=110 izango da. Efektu horri deitzen zaio konboi efektua, baliabide baten epe laburreko kontsumitzaile batzuk kontsumitzaile handi baten atzetik ilaran jartzen direnean. Janari dendako lerroa bezalakoa da zure aurrean bezero bat gurdi betearekin dagoenean. Arazoari irtenbiderik onena kutxa erregistratzailea aldatzen saiatzea edo erlaxatzea eta arnasa sakon hartzea da.
Lan laburrena Lehenik
Posible al da prozesu astunekin antzeko egoera bat nolabait konpontzea? Zalantzarik gabe. Beste plangintza mota bat deitzen zaioLan laburrena Lehenik (SJF). Bere algoritmoa ere nahiko primitiboa da - izenak dioen bezala, zeregin laburrenak abiaraziko dira lehenengo, bata bestearen atzetik.
Adibide honetan, prozesu berdinak exekutatzearen emaitza programaren batez besteko eboluzio denboraren hobekuntza izango da eta berdina izango da. 50 110 beharrean, ia 2 aldiz hobea da.
Hortaz, zeregin guztiak aldi berean iristen direlako emandako hipotesirako, SJF algoritmoa algoritmorik optimoena dela dirudi. Hala ere, gure hipotesiak oraindik ez dirudi errealistak. Oraingoan 2. hipotesia aldatuko dugu eta oraingoan imajinatu zereginak edozein unetan egon daitezkeela, eta ez guztiak aldi berean. Zein arazo ekar ditzake horrek?
Imajina dezagun A ataza (100c) lehenengo iristen dela eta exekutatzen hasten dela. t=10ean, B eta C zereginak iristen dira, eta horietako bakoitzak 10 segundo beharko ditu. Beraz, batez besteko exekuzio-denbora (100+(110-10)+(120-10))3 = 103 da. Zer egin lezake programatzaileak hau hobetzeko?
Amaitzeko denborarik laburrena lehena (STCF)
Egoera hobetzeko, 3. hipotesia alde batera uzten dugu programa martxan jarri eta amaitu arte martxan dagoela. Horrez gain, hardware-laguntza beharko dugu eta, uste duzuen bezala, erabiliko dugu tenporizadorea martxan dagoen zeregin bat eteteko eta testuinguru-aldaketa. Horrela, programatzaileak zerbait egin dezake B, C zereginak iristen diren unean - A ataza exekutatzen utzi eta B eta C zereginak prozesatzen jarri eta, amaitu ondoren, A prozesua exekutatzen jarraitu. Antolatzaile horri deitzen zaio. STCFedo Prebentzio lana Lehenik.
Planifikatzaile honen emaitza emaitza hau izango da: ((120-0)+(20-10)+(30-10))/3=50. Horrela, halako programatzaile bat are optimoagoa bihurtzen da gure zereginetarako.
Erantzun-denbora metrikoa
Horrela, zereginen exekuzio-denbora ezagutzen badugu eta zeregin hauek CPU soilik erabiltzen dutela, STCF izango da irtenbiderik onena. Eta lehen garaietan, algoritmo hauek nahiko ondo funtzionatu zuten. Hala ere, erabiltzaileak orain terminalean ematen du denbora gehiena eta esperientzia interaktibo produktiboa espero du. Horrela metrika berri bat jaio zen - erantzun denbora (erantzuna).
Erantzun denbora honela kalkulatzen da:
Tresponse=Tfirstrun−Tarrival
Horrela, aurreko adibiderako, erantzun denbora hau izango da: A=0, B=0, C=10 (abg=3,33).
Eta ematen du STCF algoritmoa ez dela hain ona 3 ataza aldi berean iristen diren egoera batean - zeregin txikiak guztiz amaitu arte itxaron beharko du. Beraz, algoritmoa ona da erantzun-denboraren metrikarako, baina txarra interaktibitatearen metrikarako. Imajinatu terminal batean eserita egongo zinela editore batean karaktereak idazten saiatzen eta 10 segundo baino gehiago itxaron beharko zenuke beste zeregin batzuk CPUa hartzen ari zelako. Ez da oso atsegina.
Beraz, beste arazo baten aurrean gaude: nola eraiki dezakegu erantzun denborarekin sentikorra den programatzaile bat?
Round Robin
Problema hau konpontzeko algoritmo bat garatu zen Round Robin (RR). Oinarrizko ideia nahiko sinplea da: zereginak amaitu arte exekutatu beharrean, denbora-tarte jakin batean (denbora zati bat deitzen dena) exekutatu eta gero ilaratik beste zeregin batera aldatuko dugu. Algoritmoak bere lana errepikatzen du zeregin guztiak amaitu arte. Kasu honetan, programaren exekuzio-denbora denboraren multiplo bat izan behar da eta horren ondoren tenporizadoreak prozesua eten egingo du. Adibidez, tenporizadore batek x=10ms behin prozesu bat eteten badu, orduan prozesuaren exekuzio-leihoaren tamaina 10eko multiploa izan behar da eta 10,20 edo x*10 izan behar du.
Ikus dezagun adibide bat: ABC zereginak aldi berean iristen dira sistemara eta horietako bakoitzak 5 segundoz exekutatu nahi du. SJF algoritmoak zeregin bakoitza osatuko du beste bat hasi aurretik. Aitzitik, abiarazte-leihoa = 1s duen RR algoritmoak honela egingo ditu zereginak (4.3. irudia):
(SJF Berriz (Erantzun denborarako txarra)
(Round Robin (Erantzun denborarako ona)
RR algoritmoaren batez besteko erantzun-denbora (0+1+2)/3=1 da, SJFrako (0+5+10)/3=5, berriz.
Logikoa da denbora-leihoa oso parametro garrantzitsua dela RRrentzat; zenbat eta txikiagoa izan, orduan eta erantzun denbora handiagoa izango da. Dena den, ez zenuke txikiegia egin behar, testuingurua aldatzeko denborak ere eragina izango baitu errendimendu orokorrean. Horrela, exekuzio-leihoaren denbora aukeratzea OS arkitektoak ezartzen du eta bertan exekutatu nahi diren zereginen araberakoa da. Testuingurua aldatzea ez da denbora galtzen duen zerbitzu-eragiketa bakarra - exekutatzen ari den programak beste gauza askotan funtzionatzen du, adibidez, hainbat cachetan, eta etengailu bakoitzarekin ingurune hau gorde eta berreskuratu behar da, eta horrek ere asko hartu dezake. denbora.
RR programatzaile bikaina da erantzun-denboraren metrikoari buruz bakarrik hitz egiten bagenu. Baina nola jokatuko du zereginen buelta-denboraren metrika algoritmo honekin? Demagun goiko adibidea, A, B, C-ren funtzionamendu-denbora = 5s eta aldi berean iristen denean. A ataza 13etan amaituko da, B 14an, C 15 s-etan eta batez besteko erantzun-denbora 14 s-koa izango da. Beraz, RR da fakturazio-metrikorako algoritmorik txarrena.
Termino orokorragoetan, RR motako edozein algoritmo bidezkoa da; CPU denbora prozesu guztien artean berdin banatzen du. Eta horrela, metrika hauek etengabe gatazkan daude elkarren artean.
Horrela, hainbat algoritmo kontrastatu ditugu eta, aldi berean, oraindik hainbat suposizio geratzen dira: ataza-denbora ezagutzen dela eta zereginak CPUa soilik erabiltzen duela.
I/O-rekin nahastea
Lehenik eta behin, kendu dezagun prozesuak CPUa soilik erabiltzen duela dioen 4. hipotesia; jakina, hori ez da horrela eta prozesuek beste ekipamendu batzuetara sar daitezke.
Edozein prozesuk I/O eragiketa bat eskatzen duen momentuan, prozesua blokeatutako egoeran sartzen da, I/O amaitu arte zain. I/O disko gogorrera bidaltzen bada, eragiketa horrek zenbait ms edo gehiago iraun dezake, eta prozesadorea inaktibo egongo da une honetan. Denbora horretan, programatzaileak prozesadorea beste edozein prozesurekin okupatu dezake. Antolatzaileak hartu beharko duen hurrengo erabakia da prozesua noiz amaituko duen bere I/O. Hori gertatzen denean, eten bat gertatuko da eta OSak I/O deitu duen prozesua prest egoeran jarriko du.
Ikus dezagun hainbat zereginen adibide bat. Horietako bakoitzak 50 ms-ko CPU denbora behar du. Dena den, lehenengoa 10ms behin sartuko da I/O (hori ere 10ms behin exekutatuko da). Eta B prozesuak 50 ms-ko prozesadore bat besterik ez du erabiltzen I/O gabe.
Adibide honetan STCF programatzailea erabiliko dugu. Nola jokatuko du programatzaileak bertan A bezalako prozesu bat abiarazten bada? Honako hau egingo du: lehenengo A prozesua guztiz landuko du, eta gero B prozesua.
Arazo hau konpontzeko ohiko ikuspegia A prozesuaren 10 ms-ko azpiataza bakoitza zeregin bereizi gisa tratatzea da. Horrela, STJF algoritmoarekin hastean, 50 ms-ko zereginaren eta 10 ms-ko zereginaren arteko aukera nabaria da. Ondoren, A azpiataza amaitzen denean, B prozesua eta I/O abiaraziko dira. I/O-a amaitu ondoren, ohikoa izango da 10 ms-ko A prozesua berriro abiaraztea B prozesuaren ordez. Modu honetan, gainjartzea posible da, non CPUa beste prozesu batek erabiltzen duen lehena zain dagoen bitartean. I/O. Eta, ondorioz, sistema hobeto erabiltzen da - prozesu interaktiboak I/O-ren zain dauden momentuan, beste prozesu batzuk exekutatu daitezke prozesadorean.
Oraclea ez da gehiago
Orain saia gaitezen zereginaren exekuzio-denbora ezaguna den suposizioa kentzen. Hau da, oro har, zerrenda osoko hipotesirik txarrena eta irrealena. Izan ere, batez besteko sistema eragile arruntean, sistema eragileak berak normalean ezer gutxi daki zereginen exekuzio-denborari buruz, beraz, nola eraiki dezakezu programatzaile bat zereginak zenbat denbora beharko duen exekutatzeko jakin gabe? Agian RR printzipio batzuk erabil genitzake arazo hau konpontzeko?
Guztira
Zereginen programazioaren oinarrizko ideiak aztertu ditugu eta 2 programatzaile-familia aztertu ditugu. Lehenengoak zeregin laburrena hasten du lehenik eta, horrela, erantzute-denbora handitzen du, bigarrenak, berriz, zeregin guztien artean berdin zatitzen du, erantzun-denbora handituz. Bi algoritmoak txarrak dira non beste familiako algoritmoak onak diren. PUZaren eta I/O-ren erabilera paraleloak errendimendua nola hobetu dezakeen ere aztertu dugu, baina ez dugu konpondu OS argitasunarekin arazoa. Eta hurrengo ikasgaian iragan hurbilari begiratu eta etorkizuna iragartzen saiatzen den planifikatzaile bati begiratuko diogu. Eta maila anitzeko feedback-ilara deitzen zaio.
Iturria: www.habr.com