Belady's Anomaly/ Distance String
Yıllar boyunca, teorik prensiplerden yola çıkılarak sayfa değiştirmeleri algoritmalarında (modeling page replacement) çeşitli çalışmalar yapıldı. Bu belgede bu yöntemlerden ikisi olan Belady's Anomalyy ve The Distance String üzerinde durulmuştur.
Genellikle, hafızanın sahip olduğu çerçeveler ne kadar fazlaysa, bir programın alacağı sayfa hatalarının da o oranda düşük olduğu zannedilir. Ancak şaşırtıcı bir biçimde, bu durum her zaman böyle olmaz. Belady Et Al (1969), FIFO'nun dört sayfa çerçevesiyle üç sayfaya göre daha fazla sayfa hatası oluşturduğunu keşfetti. Bu garip durum Belady's Anomaly olarak bilinmektedir.
Aşağıdaki figürde 0'dan 4'e kadar numaralandırılmış beş sanal sayfa
görülmektedir. Sayfalar aşağıdaki sırayla referans edilmiştir:
0 1 2 3 0 1 4 0 1 2 3 4
Şekil (a)'da üç sayfa çerçevesinin nasıl dokuz sayfa hatasına yol açtığı gösteriliyor. Şekil (b)'de beş sayfa çerçevesine karşılık on sayfa hatası alıyoruz.
Yığın (stack) algoritmalarında, referans edilen katarı (string), gerçek sayfa numaraları yerine, daha soyut biçimde temsil etmek yaygın kullanılan bir yöntemdir. Bundan böyle, sayfa referansı, referans edilen sayfanın yığının başından itibaren ne kadar uzaklıkta olduğunu gösterecektir. Örneğin aşağıdaki şekilde, son sütündaki sayfa 1'e yapılan bir referans , aslında yığının başından 3 uzaklıktaki bir sayfaya referans etmektir (çünkü sayfa 1, referans edilen sayfadan 3 önceki kısımda yer alıyordu ). Henüz referans edilmeyen sayfalar, keza henüz yığında olmayan sayfalar (henüz M'de olmayanlar) için uzaklık sonsuz olarak belirlenir. Şekil 2'nin altında katarların uzaklıkları verilmiştir.
Katarın uzaklığının sadece referans edilen katara bağlı olmadığına dikkat edin, aynı zamanda sayfalama algoritması da bu konuda etkendir. Farklı bir sayfalama algoritması, aynı katar referansı olmasına rağmen, hangi sayfanin tahliye edileceği konusunda değişik bir sonuç verebilir. Sonuç olarak farklı bir yığın dizilimine ihtiyaç duyulur.
Katar mesafesinin istatistiği, algoritmanın performansına çok büyük etkilerde bulunur. Şekil 3 (a)'da, uydurma bir katar için (d), girişlerin yoğunluk fonksiyonunu görüyoruz. Katardaki girişlerin çoğu 1 ile k arasındadır. K sayfa çerçevesine sahip bir bellekte daha az sayfa hatası olacağı aşikardır.