Sayfalama için geliştirilmiş bir çok çözüm yöntemi var . Bu
yöntemlerden bir tanesi en uzun zaman periyodunu kullanmayan sayfayı yer
değiştirmek .Harcanan zamana değmesi için bazı uygun donanım gerektirir .
Optimal algoritmanın iyi bir yaklaşımı incelemede taban olmalıdır ki
son birkaç bilginin muhtemelen bir sonraki birkaç bilgide kullanılmasıyla
birlikte sayfalar yoğun bir şekilde kullanılmış olur . Diğer taraftan devir
için kullanılmayan sayfalar belki de uzun zaman kullanılmadan kalacak ve
uzun bir süre bekleyecek . Bu fikir gerçekleşmesi mümkün olan bir algoritmayı
önerir : bir sayfa yanlış olduğunda , en uzun zaman için kullanılmayan sayfaya
atılacak . Bu stratejiye LRU(Least recently used) paging(sayfalama) denir .
Bellek girişlerinde , gelecek geçmişe çok benzer . Bu yüzden , en uzun süre kullanılmayacak sayfayı seçmek yerine , en uzun süre kulanılan bir sayfayı seçmeye izin verilir .LRU(Least recently used) algoritması , belirli bir sayfanın ne zaman ve ne kadar kullanılacağını çözmeye çalışır . Son zamanlarda aktif olmayan ve yakın zaman diliminde de aktif olmayacağı umulan bir sayfa seçilebilir .
Görünüşe bakılırsa , referans tablosunda sayfaların depolanması için pahalı
olmasından dolayı bu algoritma hızlı ve verimli değildir . LRU ' yu tamamlamak için
en çok kullanılan sayfanın önündekiyle ve en çok kullanılan sayfanın arkasındakiyle,
bellekte bütün sayfaların bir linklenmiş listesinin devam ettirilmesi gerekir . Her
bellek tahsisinde listeyi update etmek zordur . Listede bir sayfa bulmak , silmek ve
öndeki sayfaya geçmek çok zaman alır . Her ikisi de özel donanıma ihtiyaç duyar ya da
biz yazılımda daha ucuz bir yaklaşım bulmalıyız .
Her instruction'da linklenmiş bir liste aramak ya da idare etmek
donanımda bile çok yavaştır. Bunar rağmen özel donanımla birlikte LRU
tanımlamak için başka yollar vardır. En kolay birinci yola bakalim:
Bu metod her
bir instruction'dan sonra otomatik olarak artan 64 bitlik bir sayaca
ihtiyaç duyar. Ayrıca her sayfa kayıt tablosunda sayacı içermek için
büyük, yeterli bir alana sahip olmalıdır. Her bellek referansından
sonra, C'nin şimdiki değeri referans edilmesi için sayfa kayıt
tablosunda tutulmalıdır. Sayfa yanlış olduğunda işletim sistemi en
küçüğü bulmak için sayfa tablosunda bütün sayaçları inceler. Bu sayfa
en az kullanılandır. Şimdi ikincil donanım LRU algoritmasına bakalim. N
sayfadan oluşan çerçeveli bir makina için LRU donanımı hepsinin en başı
sıfır olan NxN bitlik bir matriste tutulur. Sayfa çerçevesi k referans
edilmesine rağmen, birinci donanım 1 için k satırının bütün bitlerini
yerleştirir. Sonra sıfır için k r bütün bitlerini yerleştirir. Hangi
anda olursa olsun, ikilik değeri en küçük olan satır en az
kullanılandır, bir sonraki düşük değerli satır bir sonraki az
kullanılandır, vs.. Bu algoritma dört sayfalı çerçeveler ve referans
edilen sayfalar için aşağıda verilmiştir.