Je ne comprends pas L'anomalie de Belady
L'anomalie de Belady indique donc que lorsque vous utilisez une politique de remplacement de page FIFO, lorsque vous ajoutez plus d'espace de page, nous aurons plus de défauts de page.
Mon intuition dit que nous devrions moins ou tout au plus, le même nombre de fautes de page que nous ajoutons plus d'espace de page.
Si nous pensons à une file D'attente FIFO comme un tuyau, ajouter plus d'espace de page est comme rendre le tuyau plus grand:
____
O____O size 4
________
O________O size 8
Alors, pourquoi auriez-vous plus de défauts de page? Mon intuition dit qu'avec un tuyau plus long, vous prendriez un peu plus de temps pour commencer avoir des défauts de page (donc, avec un tuyau infini, vous n'auriez pas de défauts de page) et vous auriez autant de défauts de page et aussi souvent qu'avec un tuyau plus petit.
Quel est le problème avec mon raisonnement?
5 réponses
La raison pour laquelle lorsque vous utilisez FIFO, augmenter le nombre de pages peut augmenter le taux d'erreur dans certains modèles d'accès, est que lorsque vous avez plus de pages, les pages récemment demandées peuvent rester plus longtemps au bas de la file D'attente FIFO.
Considérons la troisième fois que "3" est demandé dans l'exemple de wikipedia ici: http://en.wikipedia.org/wiki/Belady%27s_anomaly
Les défauts de Page sont marqués d'un "f".
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:
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
Dans le premier exemple (avec moins de pages), il y a 9 défauts de page.
Dans le deuxième exemple (avec plus de pages), il y a 10 défauts de page.
Lorsque vous utilisez FIFO, l'augmentation de la taille du cache modifie l'ordre dans lequel les éléments sont supprimés. Qui dans certains cas, peut augmenter le taux de défaut.
L'anomalie de Belady n'indique rien sur la tendance générale des taux de défaut en ce qui concerne la taille du cache. Donc, votre raisonnement (sur la visualisation du cache comme un tuyau), dans le cas général est pas mal.
En résumé: L'anomalie de Belady souligne qu'il est possible d'exploiter le fait que des tailles de cache plus grandes peuvent provoquer des éléments du cache dans la file D'attente FIFO plus tard que des tailles de cache plus petites, afin de provoquer un taux d'erreur plus élevé sous un modèle d'accès particulier (et peut-être rare).
Cette déclaration est fausse car elle est surgénéralisée :
L'anomalie de Belady indique que lorsque vous utilisez une stratégie de remplacement de page FIFO, lorsque vous ajoutez plus d'espace de page, nous aurons plus de défauts de page
Ceci est une version corrigée:
" L'anomalie de Belady indique que lorsque vous utilisez une stratégie de remplacement de page FIFO, lorsque vous ajoutez plus d'espace de page, Certains modèles d'accès à la mémoire entraîneront en fait plus de défauts de page."
En d'autres termes... si l'anomalie est observée dépend de la mémoire d'accès.
L'anomalie de Belady se produit dans l'algorithme de remplacement de page ne pas suivre l'algorithme de pile.C'est-à-dire que les pages lorsque les cadres étaient moins devraient être un sous-ensemble de pages lorsque les cadres sont plus.En augmentant le cadre de page, les cadres de page qui étaient présents avant doivent être là.Cela peut se produire dans FIFO parfois, même le remplacement de page aléatoire, mais pas LRU ou optimale.
En bref à propos de L'anomalie de Belady, nous pouvons dire "ajouter plus de cadres peut causer plus de défauts de page".
L'anomalie de Belady se produit dans un schéma FIFO uniquement lorsque la page qui est actuellement référencée est la page qui a été supprimée en dernier de la mémoire principale. seulement dans ce cas, même si vous augmentez plus d'espace de page, vous aurez plus de défauts de page.