Në këtë artikull përshkruhen disa nga algoritmet e zevendesimit te faqeve, bazuar në kohën kur janë përdorë më së fundmi.
Algoritmi i zëvendësimit të faqes më pak të përdorur kohët e fundit
Memoria virtuale ka dy bite që ndihmojnë sistemin e shfrytëzimit të mbledhë material se cila faqe është e referensuar dhe cila jo. Biti R caktohet për faqet të cilat janë të referensuara. Biti M i vendoset faqeve të cilat janë modifikuar. Këto dite ndodhen ne çdo element të tabelës se faqeve. Është e rëndësishme të mbahet mend se këto bite duhen updatuar ne çdo referensim memorieje, kështu që këto bite përcaktohen nga hardware. Pasi një bit është vendosur me vlerën 1, ai qendon i tille derisa sistemi i shfrytëzimit e ripërcakton atë me vlerën 0 ne software.
Nqs hardware nuk ka këto bite, atëherë mund të simulohet si meposhte: kur nis një proçes të gjitha faqet e tij shënohen që nuk janë ne memorie. Sapo të referensohemi tek një faqe do të ndodhe një gabim faqeje. Sistemi i shfrytëzimit cakton bitin R të tabelave të tij, ndryshon elementin e tabelës duke shënjuar ne këtë mënyrë ne faqen e duhur, cakton mënyrën Read Only dhe rinis ekzekutimin e instruksionit.
Nqs faqja duhet modifikuar, atëherë ndodh përsëri një gabim ne faqe, duke bere të mundur që sistemi i shfrytëzimit të modifikoje bitin M duke bere të mundur aksesimin Read/Write.
Algoritmi “jo i përdorur kohet e fundit” , NRU (not recently used)
Ky algoritem në mënyrë implicite largon një faqe e cila nuk është referensuar për një interval të fiksuar kohe ( psh 20 msec). NRU nuk largon një faqe e cila është duke u përdorë shpesh. Avantazhet e këtij algoritmi janë thjeshtësia në kuptim, efecient në implementim si dhe jep një performancë e cila nuk është optimale, por
është e mirë.
Algoritmi i faqes më pak të përdorur kohët e fundit, LRU (least recently used)
Nder algoritmet e zevendesimit te faqeve, LRU është një përafrim i mirë i algoritmit optimal. Ky algoritëm bazohet në faktin statistikor që tregon se kur një faqe është përdorur shumë kohet e fundit, ai do përdoret përsëri në të ardhmen. Me të njëjtën logjike, një faqe që nuk është përdorë kohet e fundit, nuk do duhet shumë dhe në të ardhmen. Për këtë kjo faqe meriton të largohet.
Megjithëse ky algoritëm nuk duket i pamundur për tu realizuar, është shumë i shtrenjte në kosto. Për të implementuar këtë algoritëm, duhet të mirëmbahet një listë e lidhur e të gjitha faqeve në memorie. Në fillim të kësaj liste do jenë faqet e përdorura më pak. Vështirësia qëndron në faktin se duhet updatuar në çdo referensim memorieje. Është një veprim i vështirë gjetja e një faqeje në liste, fshirja e saj dhe më pas spostimi i saj në fillim të listës.
Ka disa mënyra implementimi i këtij algoritmi duke përdorë hardware të veçantë. Mënyra më e thjeshte kërkon një hardware me një numërator C 64 bitësh i cili automatikisht rritet pas çdo instruksioni.
Gjithashtu çdo tabelë faqeje duhet të ketë një fushë që mund të mbaje këtë numërator. Pas çdo reference, vlera e numëratorit C ruhet në tabelën e faqeve për faqen të cilën referenson. Kur ndodh një gabim faqeje, sistemi i shfrytëzimit kërkon të gjithë numëratoret në tabelën e faqeve dhe gjen numëratorin më të vogël. Faqja të ciles i përket ky numërator do jete faqja më pak e përdorur kohet e fundit.
Bazuar në librin Modern Operating Systems, me autor A.Tanenbaum