Simulating LRU in Software
Eğer donanım kullanılabilir/yeterli değilse ne yapmalı?
Önceki LRU algoritmaları gerçekçi olmalarına rağmen , özel bir donanıma gereksinim duyarlar ve bir makina için sistem tasarlayan ancak bu donanıma sahip olmayan bir işletim sistemi tasarımcısı için az kullanılan bir yöntemdir. Onun yerine yazılımda gerçekleştirilecek bir çözüme ihtiyaç vardır.
Bu probleme bir çözüm olasılığı Not Frequently Used ya da NFU algoritması olabilir. Bu algoritma, başlangıçta sıfır atanmak üzere, her sayfayla ilişkilendirilmiş bir program sayacına ihtiyaç duyar. Her saat kesmesinde (clock interrupt) işletim sistemi bellekteki tüm sayfaları tarar. Her sayfa için, ya 0 ya da 1 olan R biti program sayacına eklenir. Aslında program sayaclarının yaptığı temel şey, her bir sayfanın kaç kere referans edildiği bilgisini tutmaktır. Bir sayfa hatası oluştuğunda, en düşük sayaç değiştirme için seçilir
NFU'ya dair ana problem, hiçbir şeyi unutmamasıdır. Örneğin, bir çoklu- geçiş (multipass) derleyicide, geçiş 1'de yoğun olarak kullanılan sayfalar, diğer geçişlerde hala yüksek bir sayaç değerine sahip olacaklardır. Aslında, eğer geçiş 1, diğer tüm geçişlerdekinden daha uzun koşturulursa, sonraki geçişler için kodu barındıran diğer sayfalar her zaman ilk geçişten daha düşük bir sayaç değerine sahip olacaklardır. Keza, işletim sisteminin daha fazla kullanılmayacak sayfalar yerine kullanılabilir nitelikte olan sayfaları sileceği aşikardır.
Neyse ki, NFU'da yapılan küçük bir değişiklik sayesinde, LRU'yu simüle etmek oldukça kolay bir hale gelmiştir. Yapılan modifiye iki kısımdan oluşur. İlk olarak, R biti eklenmeden hemen önce, her sayaç 1 bit sağa ötelenir. İkinci adım olarak da, R biti rightmost bit yerine leftmost'a eklenir. Aşağıdaki şekil aging olarak bilinen modifiye edilmiş algoritmanın nasıl çalıştığını gösterir. İlk saat anından sonra, 0- 5 arasındaki sayfaların 1,0,1,0,1 ve 1 değerlerine sahip olduğunu düşünelim (yani sıraya göre, 0. sayfa 1, 1. sayfa 0, 2. sayfa 1, vs..). Diğer bir deyişle, 0 ve 1 anları arasında, 0, 2, 4 ve 5 sayfaları referans edilmiştir ve diğerleri 0 kalırken, R bitlerini 1 olarak atamışlardır. Altı uygun sayaç ötelendikten ve R bitleri sola eklendikten sonra, sayaçlar Şekil (a)'da gösterilen değerleri alacaklardır. Diğer sütunlar, bundan sonraki dört saat anından (clock tick) sonra, altı sayacın durumunu göstermektedir.
Herhangi bir sayfa hatasıyla karşılaşıldığı zaman, sayacı en düşük olan sayfa kaldırılır. Örneğin dört saat anı boyunca referans edilmeyen bir sayfa, sayacında dört sıfır barındırırken, üç seferdir referans edilmeyen sayfadan daha düşük bir sayaç değerine sahip olacaktır.
Bu algoritma, LRU'dan iki kısımda ayrılır. Örneğin Şekil(e)'de gösterilen 3 ve 5. sayfaları göz önüne alalım; her ikisi de aynı öncelikle olmak üzere iki saat anı için referans edilmişler. LRU'ya göre, eğer bir sayfa değiştirilecekse ikisinden birini seçmeliyiz. Ancak sorun şu ki; an 1 ve an 2 arasındaki aralıkta hangisinin en son referans edildiğini bilmiyoruz. Her an aralığı için bir bit kaydetmekle de, referansları erken ayırdetme hakkından feragat etmiş oluyoruz. Bu örnekte yapabileceğimiz tek şey; 5. sayfa iki saat anı önce referans edildiği için sayfa 3'ü silmek.
LRU ile aging arasındaki diğer fark ise, aging'de sayaçların sınırlı sayıda bite sahip olmasıdır (bizim örneğimizde 8 bit). Örneğin her iki sayacın da 0 değerine sahip olduklarını düşünelim. Yapabileceğimiz tek şey, rastgele olarak bir tanesini seçmektir. Gerçekte, uygun bir durumda, bu sayfalardan biri 9 saat anı önce referans edilmişken, diğeri 1000 saat anı önce referans edilmiş olabilir. Bu durumu ayırdetmek için yapabileceğimiz hiçbir şey yoktur. Pratikte, yine de 8 bit genelde eğer bir saat anı 20 milisaniye civarındaysa yeterli olabilir. Eğer bir sayfa 160 milisaniye boyunca referans edilmemişse muhtemelen o kadar da önemli değildir.