Orriak ordezkatzeko algoritmoak

Orriak ordezkatzeko 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.

Optimalitasun printzipoa

Algoritmorik hoberena baina ezarri ezina. Honen arabera, orri hutsegitea dagoenean hutsik dagoen orri markorik ez badago, etorkizunean beranduen erabiliko den orria atera behar da memoriatik. Oso sinplea da, baina sistema eragileak ez du aurrerantzean zeintzuk orri erabiliko diren jakiterik. Argi dago algoritmorik egokiena optimalitasun honetara gehien hurbiltzen dena izango dela.

NRU (oraintsu erabili ez den orriaren ordezkapena)

Sistema eragileak zeintzuk orri erabiltzen diren jakin dezan, orri bakoitzak informazio hori biltzen duten bi bit dauzka (ikusi taula):

• 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 bita1 egoeran jartzen du hardwareak.

1 egoeran dagoen bitak horrela jarraituko du sistema eragileak 0 egoeran jarri arte (normalki 20 milisegundoro).

NRU algoritmoaren arabera, prozesu bat martxan jartzen denean bere orri guztien M eta R bitak 0 egoeran jartzen dira eta irakurketa/idazketa eragiketen arabera aldatuko dira. Oraintsu erabili ez diren orriak bereizteko, sistemak aldizka (erloju etendura bakoitzean, adibidez) R bita 0 egoeran jartzen du. Orri hutsegitea gertatzen denean sistema eragileak orri guztiak aztertu eta R eta M biten balioen arabera lau ataletan sailkatzen ditu:

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

Honela 0 taldeko orrien artean orri bat zoriz hautatuta, diskora eramango da eta honen orri markoan memorian sartu beharreko orria kargatuko da. 0 taldean ez balego orririk, 1 taldera joko litzateke eta honela goranzko hurrenkera. Algoritmo hau erabiliz memoriaren kudeaketa egokia lortzen da.

FIFO (hartzeko lehena ateratzeko lehena ordezkapena=

Algoritmo honek memorian dauden orri guztien zerrendarekin ilara bat sortzen du; ilara honen lehen elementua uneko orrietatik lehendabizi kargatu den orria izango da eta azken elementua memorian duela gutxi kargatu denarena. Orri hutsegitea gertatzen denean, ilarako lehen orria ilaratik (eta memoriatik) desagertu egingo da eta memorian bere lekuan kargatu den orria ilarako azken elementu bezala txertatzen da.

Badaude teknika honen aldakuntza batzuk:

• Orrialde zaharrena kendu aurretik bere R eta M bitak aztertu eta 0 taldekoa bada diskora eraman; baina hala ez balitz, ilarako hurrengo osagaia aztertzen da eta horrela elkarren segidan. Hau eginez, maiz erabiltzen diren orri zaharrak memoriatik ateratzeko arriskua gutxitu egiten da.
• Bigarren aukera. Orri zaharrenak R bita 0 egoeran badu diskora pasatzen da, baina 1 egoera badu, 0 egoeran jarri ondoren ilarako azken lekuan jartzen da eta ilarako hurrengo osagaiak aztertzen jarraitzen da.
• Erlojuaren araberako ordezkatzea. Algoritmo honek zerrenda zirkularra eraikitzen du eta erakusle berezi batek (erlojuaren orratza) orririk zaharrena erakusten du. Orri hutsegitea dagoenean, erakusleak adierazten duen orriaren R bita 0 egoeran badago, orri hori diskora eramaten da, bere markoan orri berria kargatu eta erakusleak zerrendako hurrengo osagaia erakusten duelarik; baina 1 egoeran badago, 0 egoeran jartzen da eta erakusleak zerrendako hurrengo osagaia erakusten du, prozesu honekin R bita 0 egoeran duen orria aurkitu arte jarraituz.

LRU (duela denbora gehien erabili den orriaren ordezkapena)

LRU algoritmoaren arabera orri hutsegitea gertatzen denean, denbora gehienez erabili gabe egon den orria memoriatik kanporatzen da (orain arte gertatu dena aurrerantzean ere gertatuko dela suposatzen baitu sistemak).

LRU-ren inplementazioa

Hau aurrera eramateko, memorian dauden orriei buruzko informazioa duen kateaturiko zerrenda osatu behar da, zerrenda honetako lehen osagaia duela gutxi erabili den orria eta azken osagaia, duela denbora gehien erabili dena direlarik. Zerrenda hau memoriako eragiketa bakoitzaren ondoren eguneratu behar da eta eragiketa honek denbora asko eskatzen du; hori dela eta, hardware berezia (garestia) edo software bidezko hurbilketa erabili behar da.

Hardwarean inplementatuz, n bit dituen K kontagailua behar da. Kontagailu honen balioari 1 gehitzen zaio automatikoki memoria atzipen baten ondoren eta atzitutako orriaren orri taularen sarreran idazten da K-ren uneko balio gordeko da (taula honetako osagaia bakoitzak balio hori gordetzeko eremua izan behar baitu). Orri hutsegitea gertatzen denean, sistema eragileak orrien taulako kontagailu guztiak aztertuko ditu eta balio txikiena duen orria izango da kanporatu beharrekoa.

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 loturak

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