Belady'nin anormalliğini anlayamıyorum

Question

Dolayısıyla, Belady'nin Anomalisi bir FIFO sayfa değiştirme ilkesi kullanıldığında daha fazla sayfa alanı eklerken daha fazla sayfa hatası alacağımızı belirtir.

Sezgilerim, daha fazla sayfa alanı ekledikçe daha az veya en fazla sayıda sayfa hatası gerektiğini söylüyor. Biz daha fazla sayfa alanı ekleme, bir boru gibi bir FIFO kuyruğuna düşünürseniz

boru büyük yapım gibidir:

Yani

____ 
O____O size 4 

________ 
O________O size 8 

, neden daha fazla sayfa hataları olsun ki? Sezgim, daha uzun bir boru ile, sayfa hataları oluşturmaya biraz daha uzun zaman alacağınızı söylüyor (böylece, sonsuz bir boruda sayfa hataları olmaz) ve daha sonra çok sayıda sayfa hatasına sahip olursunuz. genellikle daha küçük bir boru ile.

Neden benim mantığım yanlıştır?

Answer 1

FIFO kullanırken, sayfa sayısını artırmak bazı erişim düzenlerindeki hata oranını artırabilir, çünkü daha fazla sayfanız olduğunda, son istenen sayfalar FIFO kuyruğunun altında daha uzun kalabilir.

"3" Burada wikipedia örneğinde istendiğini üçüncü kez düşünün: http://en.wikipedia.org/wiki/Belady%27s_anomaly

Sayfa hataları bir "f" ile işaretlenmiştir.

1:

Page Requests 3 2 1 0 3 2 4 3 2 1 0 4 
Newest Page  3f 2f 1f 0f 3f 2f 4f 4 4 1f 0f 0 
        3 2 1 0 3 2 2 2 4 1 1 
Oldest Page    3 2 1 0 3 3 3 2 4 4 

2: (daha az sayfa ile birlikte) Birinci örnekte

Page Requests 3 2 1 0 3 2 4 3 2 1 0 4 
Newest Page  3f 2f 1f 0f 0 0 4f 3f 2f 1f 0f 4f 
        3 2 1 1 1 0 4 3 2 1 0 
          3 2 2 2 1 0 4 3 2 1 
Oldest Page     3 3 3 2 1 0 4 3 2 

, 9 sayfa hataları vardır.

İkinci örnekte (daha fazla sayfa ile), 10 sayfa hatası var.

FIFO kullanırken, önbellek boyutunu artırmak öğelerin kaldırıldığı sırayı değiştirir. bazı vakalarında, arıza oranını artırabilir.

Belady Anomalisi, önbellek boyutuna göre hata oranlarının genel eğilimi hakkında bir şey ifade etmemektedir. Öyleyse, mantığınız (önbelleği bir boru olarak görüntülemeyle ilgili), genel durumda yanlış değildir.

Özetle

: Belady en Anomali daha büyük önbellek boyutları önbellekte öğeler daha büyük önbellek boyutlarını neden olmak amacıyla, daha sonra küçük önbellek boyutlarından daha FIFO kuyruğunda çıkarılmasına neden gerçeğinden yola çıkarlar mümkün olduğuna işaret Belirli bir (ve muhtemelen nadir) erişim modeli altında daha yüksek bir hata oranına sahip olmak.

Answer 2

Belady anomalisi, yalnızca şu anda yönlendirilmekte olan sayfa ana bellekten en son kaldırılan sayfa olduğunda, FIFO düzeninde gerçekleşir. Sadece bu durumda, daha fazla sayfa alanı artırmanıza rağmen, daha fazla sayfa hatasına sahip olursunuz.o overgeneralized çünkü

Answer 3

Bu ifade yanlıştır:

Belady anomalisi bir FIFO sayfa değiştirme politikasını kullanırken fazla sayfa alanı eklerken, daha fazla sayfa hataları

gerekecek belirten

Düzeltilmiş bir sürümü:

"Belady's Anomaly, daha fazla sayfa alanı eklerken FIFO sayfa değiştirme ilkesi kullanıldığında, bazı bellek erişim desenleri aslında daha fazla sayfa hatalarıyla sonuçlanacaktır. " Başka bir deyişle, anormalliğin gözlenip gözlemlenmediği, gerçek bellek erişim düzenine bağlıdır.

Answer 4

Sayfa değiştirme algoritmasında ortaya çıkan anormallik, yığın algoritmasını takip etmemektedir. Çerçevelerin daha az olduğu sayfaların, çerçeveler daha fazla olduğunda sayfaların bir alt kümesi olması gerekir. Sayfa çerçevesinin artmasıyla, daha önce mevcut olan sayfa çerçeveleri Orada FIFO bazen rastgele sayfa değiştirme, ancak LRU veya optimal değil.