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 =)
Plangintza: Maila Anitzeko Iritzi Ilara
Hitzaldi honetan, hurbilketa ospetsuenetako bat garatzeko arazoei buruz hitz egingo dugu
plangintza, deitzen dena Maila anitzeko iritzi-ilara (MLFQ). MLFQ programatzailea 1962an deskribatu zuen lehen aldiz Fernando J. CorbatΓ³k izeneko sistema batean
Denbora partekatzeko sistema bateragarria (CTSS). Lan hauek (geroko lanak barne
Multics) Turing sarirako izendatu zuten gero. Antolatzailea zen
ondoren, jadanik aurki daitekeen itxura hobetu eta eskuratu zuen
sistema moderno batzuk.
MLFQ algoritmoa gainjarritako oinarrizko 2 problema ebazten saiatzen da.
Lehenik eta behin, erantzun-denbora optimizatzen saiatzen da, aurreko hitzaldian aipatu genuen bezala, ilararen buruan hasteko metodoaren bidez optimizatzen dena.
zeregin laburrak. Hala ere, sistema eragileak ez daki zenbat denbora iraungo duen prozesu hau edo hura, eta hau
SJF, STCF algoritmoen funtzionamendurako beharrezkoak diren ezagutzak. Bigarrenik, MLFQ saiatzen ari da
sistema erabiltzaileei erantzuteko (adibidez, eserita daudenentzat eta
pantailari begira, zeregina noiz amaituko zain dagoen bitartean) eta horrela denbora gutxitu
erantzuna. Zoritxarrez, RR bezalako algoritmoek erantzun denbora murrizten dute, baina
eragin txarra dute erantzun denboraren metrikan. Hortik gure arazoa: Nola diseinatu
ezer jakin gabe gure eskakizunak beteko dituen programatzailea
prozesuaren izaera orokorrean? Nola ikas ditzake planifikatzaileak zereginen ezaugarriak,
zein abiarazten duen eta horrela planifikazio-erabaki hobeak hartzeko?
Arazoaren funtsa: nola planifikatu zereginen ezarpena ezagutza perfekturik gabe?
Nola diseinatu aldi berean erantzun denbora murrizten duen programatzaile bat
zeregin interaktiboetarako eta, aldi berean, erantzute-denbora gutxitzen du jakin gabe
ataza exekutatzeko denboraren ezagutza?
Oharra: aurreko gertakarietatik ikastea
MLFQ ilaratik ikasten duen sistema baten adibide bikaina da
iraganeko gertaerak etorkizuna iragartzeko. Horrelako planteamenduak askotan izaten dira
OSan aurkitzen da (Eta informatikaren beste adar asko, adarrak barne
hardware iragarpenak eta cache-algoritmoak). Antzeko ibilaldiak
atazek jokabide-faseak dituztenean eta, beraz, aurreikusgarriak direnean abiarazten dira.
Hala ere, kontuz ibili behar da teknika honekin, iragarpenak oso errazak direlako.
oker egon daiteke eta sistema baino erabaki okerragoak hartzera eraman dezake
batere ezagutzarik gabe egongo litzateke.
MLFQ: Oinarrizko Arauak
Demagun MLFQ algoritmoaren oinarrizko arauak. Eta algoritmo honen inplementazioen arren
hainbat daude, oinarrizko planteamenduak antzekoak dira.
Kontuan hartuko dugun ezarpenean, MLFQk hainbat izango ditu
ilara bereiziak, eta horietako bakoitzak lehentasun ezberdina izango du. Edonoiz,
exekutatzeko prest dagoen zeregin bat ilara batean dago. MLFQ lehentasunak erabiltzen ditu,
exekuziorako zein zeregin exekutatu erabakitzeko, hau da. goi-mailako zeregina
lehentasuna (lehentasun handiena duen ilararen zeregina) lehenengoan abiaraziko da
ilara.
Jakina, ilara jakin batean zeregin bat baino gehiago egon daiteke, beraz
beraz, lehentasun bera izango dute. Kasu honetan, mekanismoa erabiliko da
Zeregin horien artean abiarazteko plangintzarako RR.
Horrela, MLFQrako oinarrizko bi arauetara iristen gara:
- 1. Araua: Lehentasuna (A) > Lehentasuna (B) bada, A zeregina abiaraziko da (B ez da)
- 2. araua: lehentasuna (A) = Lehentasuna (B) bada, A&B RR erabiliz hasten dira
Aurrekoan oinarrituta, MLFQ bat planifikatzeko funtsezko elementuak hauek dira
lehentasunak dira. Bakoitzari lehentasun finko bat eman beharrean
zeregina, MLFQ-k bere lehentasuna aldatzen du behatutako portaeraren arabera.
Adibidez, zeregin bat CPUan etengabe irteten bada teklatuaren sarreraren zain dagoen bitartean,
MLFQ-k prozesuaren lehentasuna altua mantenduko du, horrela
prozesu interaktiboak funtzionatu beharko luke. Bada, aitzitik, zeregina etengabe eta
PUZa intentsiboa da denbora luzez, MLFQ-k behera egingo du
lehentasuna. Horrela, MLFQk prozesuen portaera aztertuko du martxan dauden unean.
eta jokabideak erabiltzea.
Marraz dezagun uneren batean ilarak nolakoak izan daitezkeenaren adibide bat
denbora eta gero honelako zerbait lortzen duzu:
Eskema honetan, A eta B 2 prozesu lehentasun handiena duten ilaran daude. Prozesua
C erdian dago nonbait, eta D prozesua ilararen amaieran dago. Aurrekoaren arabera
MLFQ algoritmoaren deskribapenak, planifikatzaileak altueneko zereginak soilik exekutatuko ditu
RRaren araberako lehentasuna, eta C, D zereginak lanik gabe egongo dira.
Jakina, argazki estatiko batek ez du MLFQ funtzionatzen duen irudi osoa emango.
Garrantzitsua da denboran zehar irudia nola aldatzen den ulertzea.
1. Saiakera: Nola aldatu lehentasuna
Une honetan, MLFQ-k lehentasun-maila nola aldatuko duen erabaki behar duzu
zeregina (eta, beraz, zereginak ilaran duen posizioa) bere bizitza-zikloan zehar. Izan ere
hau beharrezkoa da lan-fluxua kontuan edukitzeko: kopuru jakin bat
exekutatzeko denbora laburreko zeregin interaktiboak (eta, beraz, maiz askatzea
CPU) eta CPUa lan-denbora guztia erabiltzen duten hainbat lan luze, berriz
horrelako zereginetarako erantzun denbora ez da garrantzitsua. Eta horrela lehen saiakera egin dezakezu
inplementatu MLFQ algoritmoa arau hauekin:
- 3. Araua: Zeregin bat sisteman sartzen denean, altuena duen ilaran jartzen da
- lehentasuna.
- Rule4a: Zeregin batek bere denbora-leiho osoa erabiltzen badu, orduan
- lehentasuna jaitsi egiten da.
- Rule4b: Zeregin batek PUZa askatzen badu bere denbora-leihoa iraungi baino lehen, orduan
- lehentasun berdinarekin jarraitzen du.
1. adibidea: iraupen luzeko zeregin bakarra
Adibide honetan ikus dezakezun bezala, onarpenean zeregina altuena da
lehentasuna. 10 ms-ko denbora-leiho baten ondoren, prozesua lehenetsiko da.
programatzailea. Hurrengo denbora-leihoaren ondoren, zeregina azkenik mailara jaitsiko da
sistemako lehentasun txikiena, non geratzen den.
2. adibidea: zeregin labur bat entregatu
Ikus dezagun orain MLFQ SJFra hurbiltzen saiatuko den adibide bat. Horretan
adibidez, bi zeregin: A, etengabe irauten duen zeregina dena
CPU eta B okupatzea, lan interaktibo laburra dena. Demagun
B zeregina iritsi zenerako A jadanik denbora luzez zebilela martxan.
Grafiko honek eszenatokiaren emaitzak erakusten ditu. A ataza, edozein zeregin bezala,
CPU erabiltzea behealdean zegoen. B ataza T=100 unean iritsiko da eta egingo du
lehentasun handieneko ilaran jarrita. Bere funtzionamendu denbora laburra denez, orduan
azken ilarara iritsi baino lehen osatuko da.
Adibide honetatik, algoritmoaren helburu nagusia ulertu beharko zenuke: algoritmoak ez duenez
zeregin luzea edo laburra badaki, gero lehenik eta behin zeregin hori bere gain hartzen du
laburra eta lehentasun handiena ematen dio. Benetan lan laburra bada, orduan
azkar osatuko da, bestela lan luzea bada, poliki-poliki mugituko da
lehentasuna behera eta laster frogatuko du benetan ez duen zeregin luzea dela
erantzuna eskatzen du.
3. adibidea: Zer gertatzen da I/O?
Ikus dezagun orain I/O adibide bat. 4b arauan dioen bezala,
prozesu batek prozesadorea askatzen badu bere prozesadorearen denbora guztiz erabili gabe,
orduan lehentasun maila berean geratzen da. Arau honen asmoa nahiko sinplea da
- lan interaktiboak I/O eragiketa asko egiten baditu, adibidez, zain
erabiltzailearen teklak edo sagua sakatuta, zeregin horrek prozesadorea askatuko du
esleitutako leihoaren aurretik. Ez genuke horrelako lehentasunezko zeregina baztertu nahi,
eta horrela maila berean geratuko da.
Adibide honek algoritmoak prozesu horiekin nola funtzionatuko duen erakusten du - B lan interaktiboa, exekutatu baino 1 ms baino lehen CPU behar duena.
I/O prozesua eta A lan luzea, CPUa denbora guztian erabiltzen duena.
MLFQ-k B prozesuari lehentasun handiena ematen dio jarraitzen duen heinean
askatu CPUa. B zeregin interaktiboa bada, orduan algoritmoa iritsi da kasu honetan
bere helburua zeregin interaktiboak azkar martxan jartzea da.
Arazoak egungo MLFQ algoritmoarekin
Aurreko adibideetan, MLFQ-ren oinarrizko bertsioa eraiki dugu. Eta badirudi berak
ondo eta zuzen egiten du bere lana, CPU denbora nahiko banatuz
zeregin luzeak eta lan laburrak edo sarbide handiak dituzten zereginak ahalbidetuz
I/Ora azkar prozesatzeko. Zoritxarrez, ikuspegi honek hainbat ditu
arazo larriak.
Lehenik eta behin, gosearen arazoa: sistemak interaktibo asko baditu
zereginak, orduan prozesadorearen denbora guztia kontsumituko dute eta, beraz, bakar bat ere ez denbora luzez
zeregina ezin izango da exekutatu (gosez hiltzen ari dira).
Bigarrenik, erabiltzaile adimendunek beren programak idatzi ditzakete horrela
programatzailea engainatu. Iruzurra behartzeko zerbait egitean datza
programatzailea prozesuari CPU denbora gehiago emateko. Hori algoritmoa
Goian deskribatutako erasoen aurrean nahiko zaurgarria da: denbora-leihoa ia baino lehen
baino gehiago, I/O eragiketa bat egin behar duzu (batzuei, edozein fitxategiri ere)
eta horrela askatu CPUa. Jokabide horrek berdin jarraitzeko aukera emango dizu
ilarak berak eta berriro CPU denboraren ehuneko handiagoa lortzen du. Egiten baduzu
hau zuzena da (adibidez, exekutatu leihoaren denboraren % 99 CPUa askatu aurretik),
zeregin horrek prozesadorea monopolizatu besterik ez du egin.
Azkenik, programa batek bere portaera alda dezake denboran zehar. Zeregin horiek
CPU erabiltzen duten interaktibo bihur daiteke. Gure adibidean, antzekoa
atazek ez dute planifikatzailearengandik tratamendu egokia jasoko, beste batzuek egingo luketen moduan
(hasierako) zeregin interaktiboak.
Entzuleei galdera: zer eraso egin litezke mundu modernoan planifikatzailearen kontra?
2. saiakera: lehentasuna handitu
Saia gaitezen arauak aldatzen eta ea arazoak ekiditen ditugun
gosea. Zer egin dezakegu erlazionatutako hori ziurtatzeko
CPU-zereginek bere denbora lortuko dute (nahiz eta luzea ez izan).
Arazoaren irtenbide sinple gisa, aldian-aldian iradoki dezakezu
sisteman horrelako zeregin guztien lehentasuna igotzea. Modu asko daude
hori lortzeko, saia gaitezen adibide gisa zerbait sinplea ezartzen: itzuli
zeregin guztiei berehala ematen zaie lehentasunik handiena, horregatik arau berria:
- 5. araua: S aldi baten ondoren, sistemako zeregin guztiak ilararik altuenera eraman.
Gure arau berriak bi arazo konpontzen ditu aldi berean. Lehenik eta behin, prozesuak
gosez hilko ez dela bermatuta: ilararik handieneko zereginak partekatuko dira
prozesadorearen denbora RR algoritmoaren arabera eta horrela prozesu guztiek jasoko dute
CPU denbora. Bigarrenik, aurretik erabilitako prozesuren bat bada
prozesadorea bakarrik bihurtzen da interaktibo, altuena duen ilaran geratuko da
lehentasuna gorenaren lehentasuna behin-behineko gehikuntza jaso ondoren.
Demagun adibide bat. Egoera honetan, kontuan hartu prozesu bat erabiliz
CPU eta bi prozesu interaktibo labur. Irudiaren ezkerraldean, irudiak lehentasunezko bultzadarik gabeko portaera erakusten du, eta, beraz, lan luzeko zeregina gosetzen hasten da bi zeregin interaktibo sistemara iristen direnean. Eskuineko irudian, 50ms behin lehentasunezko gehikuntza egiten da eta horrela prozesu guztiek prozesadorearen denbora jasoko dutela bermatuta dago eta aldian-aldian abiaraziko dira. Kasu honetan 50ms hartzen da adibide gisa, errealitatean kopuru hori zertxobait handiagoa da.
Bistakoa da S igoera-denbora periodikoa gehitzeak dakarrena
galdera logikoa: zer balio ezarri behar da? Omenduetako bat
John Ousterhout sistemen ingeniariek sistemen antzeko kantitateak voo-doo gisa aipatzen zituzten
etengabe, nolabait magia beltza behar baitzuten zuzenerako
esposizio. Eta, zoritxarrez, S-k badu halako kutsua. Balioa ere ezartzen baduzu
handiak - zeregin luzeak gosez hiltzen hasiko dira. Eta balioa baxuegia ezartzen baduzu,
Zeregin interaktiboek ez dute CPU denbora egokia jasoko.
3. saiakera: Kontabilitate hobea
Orain beste arazo bat dugu konpontzeko: nola ez
gure programatzailea iruzur egiteko baimena eman? Aukera horren errudunak dira
4a, 4b arauak lan bati lehentasuna mantentzea ahalbidetzen diote prozesadorea askatuz
emandako epea amaitu baino lehen. Nola egin aurre?
Kasu honetan irtenbidea PUZaren denboraren kontabilitatea hobea dela kontsidera daiteke
MLFQ maila. Programak erabilitako denbora ahaztu beharrean
prozesadorea emandako epean, kontuan hartu eta gorde behar da. Ondoren
prozesuak emandako denbora agortu du, hurrengora jaitsi behar da
lehentasun maila. Orain ez du axola nola prozesuak bere denbora erabiliko duen - nola
etengabe prozesadorean edo dei batzuetan konputatzen. Horrela,
4. araua forma honetan berridatzi behar da:
- 4. araua: Zeregin batek uneko ilaran esleitutako denbora agortu ondoren (PUZa zenbat aldiz askatu duen kontuan hartu gabe), zeregin horren lehentasuna murrizten da (ilaran behera egiten du).
Ikus dezagun adibide bat:
Β»
Irudiak erakusten du zer gertatzen den programatzaileari engainatzen saiatzen bazara
aurreko 4a arauekin balitz, 4b izango litzateke ezkerreko emaitza. Berri zoriontsuak
araua da emaitza eskuinean dagoela. Babesa baino lehen, edozein prozesuk I/O deitu dezake amaitu aurretik eta
horrela, PUZa nagusitu, babesa gaitu ondoren, portaera edozein dela ere
I/O, oraindik ilaran behera mugituko da eta, beraz, ezin izango du zintzotasunez egin
CPU baliabideak hartu.
MLFQ eta beste gai batzuk hobetzea
Aurreko hobekuntzekin, arazo berriak sortzen dira: nagusietako bat
Galderak - nola parametrizatu halako programatzaile bat? Horiek. Zenbat izan beharko luke
ilarak? Zein izan behar du ilararen barruan programaren leihoaren tamaina? Nola
programa sarritan lehenetsi behar da gosea saihesteko eta
programaren jokabide aldaketa kontuan hartzeko? Galdera horiei dagokienez, ez dago sinplerik
erantzun eta kargarekin eta ondorengo konfigurazioarekin bakarrik esperimentatzen du
programatzaileak oreka on bat ekar dezake.
Adibidez, MLFQ inplementazio gehienek desberdinak esleitzeko aukera ematen dute
ilara ezberdinetarako denbora tarteak. Lehentasun handiko ilarak izan ohi dira
tarte laburrak. Ilara hauek zeregin interaktiboz osatuta daude,
hauen artean aldatzea nahiko sentikorra da eta 10 edo gutxiago beharko luke
anderea. Aitzitik, lehentasun baxuko ilarak exekuzio luzeko zereginak erabiltzen dituzte
CPU. Eta kasu honetan, denbora tarte luzeak oso ondo moldatzen dira (100 ms).
Adibide honetan lehentasun handiko 2. ilaran funtzionatu zuten 20 zeregin daude
ms, 10 ms-ko leihoetan banatuta. 40 ms erdiko ilaran (20 ms leihoan) eta lehentasun baxuan
ilararen denbora-leihoa 40 ms-koa bihurtu zen, non zereginak bere lana amaitu zuten.
Solaris OS sisteman MLFQ inplementatzea denbora partekatutako programatzaileen klase bat da.
Antolatzaileak behar den bezala definitzen duten taula multzo bat emango du
aldatu prozesuaren lehentasuna bere bizitzan zehar, zein tamaina izan behar duen
esleitutako leihoa eta zereginen lehentasunak zenbat aldiz igo behar dituzun. Administratzailea
sistemek taula honekin elkarreragin dezakete eta programatzaileak portaera eragin dezake
bestela. Lehenespenez, taula honek 60 ilara ditu pixkanaka handituz
leihoaren tamaina 20 ms (lehentasun handia) ehunka ms (lehentasun txikiena) eta
halaber, segundoko behin zeregin guztiak areagotuz.
Beste MLFQ planifikatzaileek ez dute taularik edo zehatzik erabiltzen
kapitulu honetan deskribatzen diren arauak, aitzitik, lehentasunak erabiliz kalkulatzen dituzte
formula matematikoak. Adibidez, FreeBSD programatzaileak formula bat erabiltzen du
uneko zereginen lehentasuna kalkulatuz prozesua zenbaterainokoa den
CPUa erabili zuen. Gainera, PUZaren erabilera denborarekin usteltzen da, eta horrela
Beraz, lehentasunaren igoera goian azaldutakoa baino zertxobait desberdina da. Hau egia da
desintegrazio algoritmoak deitzen dira. 7.1 bertsiotik aurrera, FreeBSD-k ULE programatzailea erabiltzen du.
Azkenik, planifikatzaile askok beste ezaugarri batzuk dituzte. Adibidez, batzuk
programatzaileek sistema eragilearen funtzionamendurako maila gorenak gordetzen dituzte eta horrela
Horrela, erabiltzaile-prozesu batek ezin du lehentasun handiena lortu
sistema. Sistema batzuek laguntzeko aholkuak emateko aukera ematen dute
planifikatzaileak lehentasunak behar bezala ezar ditzake. Adibidez, komandoa erabiliz politak
zeregin baten lehentasuna handitu edo txikitu dezakezu eta horrela handitu edo
programak CPU denborarako dituen aukerak murriztu.
MLFQ: Laburpena
MLFQ izeneko plangintza-ikuspegia deskribatu dugu. Bere izena
funtzionamendu-printzipioan ondorioztatu da - hainbat ilara ditu eta feedbacka erabiltzen du
zeregin bati lehentasuna emateko.
Arauen azken forma hau izango da:
- 1. araua: Lehentasuna (A) > Lehentasuna (B) bada, A zeregina exekutatuko da (B ez)
- 2. araua: Lehentasuna(A) = Lehentasuna(B), A&B RR erabiliz hasten dira
- 3. araua: Zeregin bat sisteman sartzen denean, lehentasun handieneko ilaran jartzen da.
- 4. araua: Zeregin batek uneko ilaran esleitutako denbora agortu ondoren (PUZa zenbat aldiz askatu duen kontuan hartu gabe), zeregin horren lehentasuna murrizten da (ilaran behera egiten du).
- 5. araua: S aldi baten ondoren, sistemako zeregin guztiak ilararik altuenera eraman.
MLFQ interesgarria da honako arrazoi honengatik - buruz ezagutza eskatu beharrean
zereginaren izaera aldez aurretik, algoritmoak zereginaren iraganeko portaera ikasten du eta multzoak
lehentasunak horren arabera. Horrela, bi aulkitan aldi berean esertzen saiatzen da - zeregin txikietarako (SJF, STCF) errendimendua lortzen eta luzeak zintzotasunez exekutatzen.
CPU kargatzeko lanak. Hori dela eta, sistema askok, BSD eta haien deribatuak barne,
Solaris, Windows, Mac-ek algoritmo moduren bat erabiltzen dute programatzaile gisa
MLFQ oinarri gisa.
Material osagarriak:
- (informatika)
Iturria: www.habr.com