Orriak ordezteko algoritmoak

Orriak ordezteko algoritmoak informatikako memoria kudeaketaren arloan, memoria fisikoa beteta dagoela, orri (prozesu zati) berri bat memoriara sartu behar denean, zein orri kanporatu behar den erabakitzeko prozedurak dira.

Sarrera

Orri hutsegitea (ikusi orrikatze) ematen denean, sistema eragileak memoriatik zein orri kendu behar duen erabaki behar du. Orriak okupatzen duen orri markoan egikaritzen ari den prozesu baten orria kargatzeko. Atera behar den orriaren edukia memorian egon den bitartean aldatu egin bada (irudiko M bit-a), orria disko gogorrean idatziko da, bertan dagoen kopia eguneratzeko; aldaketarik egon ez bada, ez dago zertan diskoan berriz idatzi beharrik.

Orri taularen sarrera

Sistemaren errendimendua hobetzeko orri hutsegitea gertatzen denean, kanporatzeko aukeratzen den orria gutxien erabili dena izatea komenigarria da (sarritan erabiltzen den bat ateratzen bada, berehala berriz kargatu behar izango baita). Ondoren aipatuko ditugu ordezkatu beharreko orria aukeratzeko algoritmo batzuk.

Helburuak

Ordezkapen politika edo algoritmo baten helburu honako hauek dira:

• Orri hutsegiteen kopurua minimizatzea
• Inplementatzeko erraztasuna

Algoritmo optimoa

Ordezkapen algoritmo optimo batean, aukeratutako orri biktima denbora gehien erreferentziatu gabe egongo litzatekeena da.

Zoritxarrez, etorkizunean egingo diren erreferentziak kalkulatzea zeintzuk diren jakinezina denez, praktikan ordezkapen algoritmoak aurreko memoria erreferentziatan oinarrituko dira, programen ingurutasun espazialaren propietatean oinarrituz.

Bigarren aukera

Erreferentziatuak izan diren eta izan ez diren orrien arteko bereizketa egiten da. Ordena zehatz bat jarraituz, lehen orria biktima bezala aukeratuko litzateke, baina erreferentziatua izan bada, memorian mantentzen da erreferentziatu gabea bezala markatu ondoren. Hurrengo orri hutsegitean, edo honetan bertan denak erreferentziatu badira, orri biktima izateko hautagai izango da, berriro ere erreferentziatzen ez bada.

Erreferentziabit bat beharko da, R bita, marko bakoitzeko, orria erreferentziatzen denean hardwarez aktibatzen dena. Bigarren aukeraren politika erlojuaren algoritmoaren bitartez inplementa daiteke: markoak ordena zirkular batean antolatzen dira, marko baterako erakusle bat izanik. Hutsegite bat gertatzean, dagokion R bita zeroan badago orri hori aukeratzen da, bestela R zeron jarri eta hurrengora joango da biktima aurkitu arte.

FIFO

Orri biktima bezala kargatuta denbora gehien daramana aukeratzen da. Inplementazioa FIFO ilara baten bidez egin daiteke, ilara orri bat kargatzen den bakoitzean eguneratuko delarik. Beste aukera bat da orria kargatu den ticka gordetzen duen erregistro baten arabera biktima aukeratzea; erregistroa eguneratuko da erlojuaren etenenaren arreta errutinaren bidez, honela FIFOrako hurbilpen bat inplementatuz.

Ingurutasun irizpideak kontuan hartzen ez direnez, oro har ez dira emaitza onak lortzen, eta gainera Beladyren anomalia deritzan arazoa ematen da: sistemaren marko kopurua handitzean printzipioz memoria gehiago izanik orri hutsegite gutxiago izatea espero beharko litzateke, baina zenbait erreferentzia sekuentziekin eta ordezkapen algoritmo batzuetan alderantzizkoa gerta daiteke (orri hutsegite gehiago emango dira); hona adibidez ondoko sekuentzia,

1 2 3 4 1 2 5 1 2 3 4 5

memoriako orri marko kopurua handitzean eta FIFO politika jarraituz, orri hutsegite gehiago gertatzen dira 4 memoria marko daudenean 3 daudenean baino.

LRU politika

Erreferentzien ingurutasuna dela eta (orri baterako erreferentzia gertatzeko aukera gehiago dago denbora laburrean erreferentziatua izan bada), orri biktima aukeratuko da erreferentziatu gabe denbora gehien daramana. Honek memoria erreferentzia bakoitzeko kargatutako orrien informazioa eguneratu behar dela suposatzen du, FIFOn ez bezala kasu horretan informazioa orria kargatzean soilik eguneratu behar baita. Ezaugarri hau izateagatik LRU pila algoritmoa dela esaten da. Pila algoritmoek propietate hau dute: erreferentzia sekuentzia bat emanik, eta memoria marko gehiagoko memoria batera aldatzean, erreferentzia kopuru bat pasa eta gero, marko gutxiagoko kasuan memorian dauden orriak memorian mantenduko dira ere marko gehiagoko kasuan. Beste hitzetan, honek suposatzen du orri hutsegiteen tasa ez dela inoiz handituko memoriaren tamaina handitzen denean. Pila algoritmoek Beladyren anomalia ekiditen dute.

LRU algoritmoaren inplementazioa nahiko konplexua da hardwarearen laguntza behar du eta. Bi mekanismo daude hardware hori eraikitzerakoan:

• Orrien lista kateatu bat manten dezala, azken erreferentziaren arabera ordenatuta, erreferentzia bakoitzean eguneratu beharko da.
• Erreferentzien kontagailu bat manten daiteke, kontagailu horren balioa orri bakoitzeko dagoen erregistro batean gordeko delarik erreferentzia bakoitzean.

Bi kasu hauen inplementazioa nahiko astuna da, eta horregatik LRU algoritmorako hurbilpenak erabili ohi dira. Errazena erreferentzia gertatu den erlojuaren ticka gordetzea da erreferentzia propioa gorde beharrean. Horretarako erreferentzia bit bat behar da marko bakoitzeko; bit horren bidez erlojuaren arreta errutinak jakingo du zein orrik erreferentziatu diren azkeneko tickean eta azken erreferentziaren tickaren erregistroa eguneratuko du, erregistro hau softwarearen bidez inplementatu daitekeelarik. Aldaketa honekin zehaztasuna galtzen da erreferentzien ordenatik denboraren araberako ordena batera aldatzen delako (tick berdin bateko erreferentziak ez daude ordenatuta).

NFU politika

NFU algoritmoan (oso maiz ez erreferentziatutako orria), kontuan hartzen da ea denbora tarte batean (tick batean adibidez) orria erreferentziatua izan den ala ez. Orri bakoitza erreferentziatua izan den denbora tarte kopurua kontatzen da, biktima kontu txikienekoa izango delarik.

Orri bakoitzeko ondoko laguntza beharko da: erreferentzia bakoitzarekin aktibatzen den R bita eta kontagailua bat. Erloju tick bakoitzean, eta orri bakoitzeko, R bita aktibatuta badago kontagailua inkrementatzen da. LRUrekin konparatuz, NFUn kontagailuak maiztasun txikiagoz inkrementatzen dira, eta beraz software bidez inplementa daiteke.

Erreferentziak ahazten ez direla da NFUko eragozpen nagusiena, programaren orrien ingurutasuna ez baitu kontuan hartzen, eta beraz iraganean asko erabili izan diren orriak gelditu ohi dira beti memorian une horretan asko erabiltzen direnek kontagailuan balio txikiagoak dituztelako hasieran.

NRU

Orri biktima berriki ez erreferentziatutako bat izango da.

Bi bit mantentzen dira hardwarez orri bakoitzeko:

• R edo erreferentzia bita. Orria irakurri edo bertan idazten denean bita 1 egoeran jartzen du hardwareak.

• M edo aldatze bita (orri garbiaren bita). Orrian idazten denean bita 1 egoeran jartzen du hardwareak.

Orri bat kargatzen denean, bere R eta M bitak zeron jartzen dira. Orri baten R bita aktibatzen da erreferentziatu egiten denean, M bita, berriz, erreferentzia hori idazketa bada. Periodikoki (erloju tick bakoitzeko adib.), R bit guztiak zerora jartzen dira.

Bit hauen arabera, lau orri mota bereizten dira biktima aukeratzeari begira:

Taldea	R	M	Deskribapena
0	0	0	Irakurri gabe, aldatu gabe
1	0	1	Irakurri gabe, aldatuta
2	1	0	Irakurrita, aldatu gabe
3	1	1	Irakurrita, aldatuta

Ordena horretan bilatzen da orri biktima, eta kategoria berdin baten barruan aukera ausaz egin daiteke.

Arazo bat dago: orri guztien R bita zeron jartzen denez, oso maiz erreferentziatzen ari diren orriak ere biktima bezala aukeratzeko arriskua dago hori egin eta hurrengo unetan.

Zahartze algoritmoa

NFUren hobekuntza gisa, ahazteko (edo zahartzeko) parametro bat ezar daiteke iraganeko erreferentzien kalterako.

Zahartze algoritmoa inplementatzeko mekanismo bat ondokoa izan daiteke: kontagailuak bit bat eskuinerantz desplazatu daitezke erloju tick bakoitzean, R bita ezkerretik sartuz. Modu honen bidez azkeneko tickean erreferentziatutako orri bat memorian mantenduko da erreferentziatu izan ez den beste baten gainetik.

Ikus,Gainera

• Alegiazko memoria
• Memoria kudeaketa taula
• Orrikatze
• Orrikatze taula
• Working set

Erreferentziak

• Deitel , H.M.: Sistemas Operativos. 2ª ed. Addison Wesley Iberoamericana. 1993.
• Tanenbaum, A.S.: Sistemas operativos. Diseño e implementación. Prentice Hall 1998.

Kanpo estekak

• (Ingelesez) Orriak ordezkatzeko oinarriak
• (Ingelesez) Orriak ordezkatzeko algoritmoak

• Datuak: Q1330967