Anomalie de Belady
- Anomalie de Belady
-
L'anomalie de Belady est une anomalie de comportement observée en informatique pour l'algorithme de remplacement des lignes de cache FIFO. Augmenter le nombre de voies de la mémoire cache peut accroître le taux de défauts de cache. Ce phénomène n'est pas spécifique aux mémoires caches N-associatives mais est général à toutes les applications où l'algorithme Fifo est utilisé. Par exemple, dans les mémoires cache de haut niveau (gestion de pages…), ce phénomène est également observable.
Histoire
Jusqu'en 1970, il était communément admis qu'une augmentation du nombre de voies améliorait la performance de l'algorithme de remplacement Fifo. László Bélády démontra que le résultat est opposé pour certaines situations atypiques et remit ainsi en question l'efficacité de cet algorithme. De nos jours, des algorithmes pseudo-LRU ou LRU lui sont préférés.
Principe
Prenons l'exemple d'une mémoire cache associative de degré 3 et d'une seconde de degré 4. Comparons leurs résultats pour la séquence : 3 2 1 0 3 2 4 3 2 1 0 4. On suppose que ces lignes sont mappées sur le même ensemble.
| Voies |
3 |
2 |
1 |
0 |
3 |
2 |
4 |
3 |
2 |
1 |
0 |
4 |
| Voie 1 |
3 |
3 |
3 |
0 |
0 |
0 |
4 |
4 |
4 |
4 |
4 |
4 |
| Voie 2 |
|
2 |
2 |
2 |
3 |
3 |
3 |
3 |
3 |
1 |
1 |
1 |
| Voie 3 |
|
|
1 |
1 |
1 |
2 |
2 |
2 |
2 |
2 |
0 |
0 |
| Voies accédées |
3 |
2 |
1 |
0 |
3 |
2 |
4 |
3 |
2 |
1 |
0 |
4 |
| Voie 1 |
3 |
3 |
3 |
3 |
3 |
3 |
4 |
4 |
4 |
4 |
0 |
0 |
| Voie 2 |
|
2 |
2 |
2 |
2 |
2 |
2 |
3 |
3 |
3 |
3 |
4 |
| Voie 3 |
|
|
1 |
1 |
1 |
1 |
1 |
1 |
2 |
2 |
2 |
2 |
| Voie 4 |
|
|
|
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
| (en rouge les défauts de cache) |
Nous voyons ainsi que nous obtenons 9 défauts de cache pour 3 voies et 10 pour 4 voies. Le résultat est contraire à l'intuition première, d'où le nom d'anomalie de Belady. Bien évidemment ce genre de situations n'est pas la plus courante et l'algorithme Fifo présente un comportement normal pour la majorité des séquences. Néanmoins, cela a entravé le développement de l'algorithme Fifo dans l'industrie et a justifié aux yeux de nombreuses personnes son remplacement par des algorithmes plus efficaces (LRU, pseudo-LRU…) mais également par une politique aléatoire…
Lien externe
Wikimedia Foundation.
2010.
Contenu soumis à la licence CC-BY-SA. Source : Article Anomalie de Belady de Wikipédia en français (auteurs)
Regardez d'autres dictionnaires:
Anomalie De Belady — L anomalie de Belady est une anomalie de comportement observée en informatique pour l algorithme de remplacement des lignes de cache Fifo. Augmenter le nombre de voies de la mémoire cache peut accroître le taux de défauts de cache. Ce phénomène n … Wikipédia en Français
Anomalie de belady — L anomalie de Belady est une anomalie de comportement observée en informatique pour l algorithme de remplacement des lignes de cache Fifo. Augmenter le nombre de voies de la mémoire cache peut accroître le taux de défauts de cache. Ce phénomène n … Wikipédia en Français
Belady-Anomalie — FIFO Anomalie (Belady‘s Anomalie) bezeichnet ein in der Informatik auftretendes Phänomen, das bei Anwendung der FIFO Ersetzungsstrategie für Virtuelle Speicherverwaltung in Computer Systemen auftreten kann. Erklärung Man spricht von einer FIFO… … Deutsch Wikipedia
FIFO-Anomalie — (Belady s Anomalie) bezeichnet ein in der Informatik auftretendes Phänomen, das bei Anwendung der FIFO Ersetzungsstrategie für Virtuelle Speicherverwaltung in Computer Systemen auftreten kann. Erklärung Man spricht von einer FIFO Anomalie, wenn… … Deutsch Wikipedia
Memoire virtuelle — Mémoire virtuelle En informatique, le mécanisme de mémoire virtuelle a été mis au point dans les années 1960. Il est basé sur l utilisation d une mémoire de masse (type disque dur ou anciennement un tambour), pour le but, entre autres, de… … Wikipédia en Français
Mémoire Virtuelle — En informatique, le mécanisme de mémoire virtuelle a été mis au point dans les années 1960. Il est basé sur l utilisation d une mémoire de masse (type disque dur ou anciennement un tambour), pour le but, entre autres, de permettre à des… … Wikipédia en Français
Mémoire virtuelle — Schéma de principe de la mémoire virtuelle En informatique, le mécanisme de mémoire virtuelle, ou swap, a été mis au point dans les années 1960. Il repose sur l utilisation d une mémoire de masse (type disque dur ou anciennement un tambour), dans … Wikipédia en Français
Pagination (informatique) — Mémoire virtuelle En informatique, le mécanisme de mémoire virtuelle a été mis au point dans les années 1960. Il est basé sur l utilisation d une mémoire de masse (type disque dur ou anciennement un tambour), pour le but, entre autres, de… … Wikipédia en Français
Fifo — First in, first out Pour les articles homonymes, voir FIFO. Algorithmes d ordonnancement EDF • Rate monotonic • Round robin … Wikipédia en Français
First In, First Out — Pour les articles homonymes, voir FIFO. Algorithmes d ordonnancement EDF • Rate monotonic • Round robin … Wikipédia en Français
