Table des matières
L’anomalie de László Bélády commence par un résultat qui ressemble encore à une erreur lorsque les élèves le calculent pour la première fois : la chaîne de référence de page 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5 produit neuf défauts de page avec trois trames de mémoire FIFO, puis dix défauts de page avec quatre.
Un emplacement supplémentaire fait manquer la machine plus souvent. Le bureau s’agrandit et le travailleur se dirige plusieurs fois vers le classeur.
Bélády, Robert A. Nelson et Gerald S. Shedler ont publié le résultat dans un article de 1969 des Communications de l’ACM intitulé « Une anomalie dans les caractéristiques spatio-temporelles de certains programmes exécutés dans une machine de radiomessagerie ». Le propre dossier de publication d’IBM décrit directement la surprise centrale : des expériences avaient révélé des cas où la diminution de la taille du magasin diminuait également la durée de fonctionnement.
C’est pourquoi l’anomalie a survécu à ses machines d’origine. Il ne s’agit pas seulement d’une curiosité de pagination de l’ère des mainframes. Il s’agit d’une petite et exacte démonstration qu’un système peut se détériorer après avoir reçu la ressource censée l’aider.
Ce que fait réellement FIFO
FIFO signifie premier entré, premier sorti. Dans un système de pagination, il supprime la page qui est restée en mémoire le plus longtemps, que cette page soit ou non sur le point d’être à nouveau nécessaire.
Imaginez un bureau avec trois emplacements pour dossiers. Chaque nouveau dossier atterrit sur le bureau. Lorsque le bureau est plein, le dossier le plus ancien est poussé dans une armoire pour faire de la place.
Cette règle est facile à comprendre et peu coûteuse à suivre. Il est également aveugle. Il se souvient de l’ordre d’arrivée, pas de l’utilité.
Donnez au bureau un quatrième emplacement et le bon sens dit que le travailleur devrait faire moins de déplacements au cabinet. L’exemple de Bélády montre le contraire. Le quatrième emplacement modifie l’ordre de vieillissement et FIFO finit par rejeter une page juste avant que le programme ne la demande à nouveau.
Pour les lecteurs qui réfléchissent à la pression de la mémoire moderne plutôt qu’aux anciennes machines de pagination, les guides de Gentil Geek sur ce que fait la RAM dans un PC et comment fonctionne le dimensionnement des fichiers d’échange Windows couvrent la version quotidienne de la même hiérarchie de vitesse : la mémoire rapide est précieuse et les échecs coûtent cher.
La corde de référence qui a brisé l’instinct
La célèbre démonstration utilise la chaîne de référence 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5. Avec trois trames sous FIFO, le système prend neuf fautes. Avec quatre images, il en faut dix.
Un défaut de page est le moment où la page demandée ne se trouve pas dans la mémoire rapide et doit être récupérée à partir d’un stockage plus lent. Dans les systèmes réels, le coût n’est pas simplement arithmétique. Il s’agit de retards, de trafic sur les disques ou sur le stockage, d’un travail bloqué et parfois d’une pause visible.
Les chiffres sont petits car l’exemple est conçu pour les tableaux noirs. Le résultat est important car il met à mal un réflexe fondamental de l’ingénierie : si une machine manque trop souvent, donnez-lui plus de place.
Ce réflexe est généralement correct lorsque la règle de remplacement possède la bonne propriété mathématique. FIFO ne l’a pas.
Pourquoi LRU évite l’anomalie
Les systèmes d’exploitation modernes n’utilisent généralement pas de simple FIFO pour la pagination. Ils utilisent des politiques façonnées par la récence, la fréquence et le coût, souvent par le biais d’approximations de type LRU plutôt que par le LRU exact des manuels.
LRU signifie le moins récemment utilisé. Il supprime la page qui est restée intacte le plus longtemps, ce qui est plus proche du comportement réel de nombreux programmes.
La raison profonde pour laquelle LRU est important ici est qu’il appartient à la famille des algorithmes de pile. Dans un algorithme de pile, les pages contenues dans une mémoire plus petite sont toujours contenues à l’intérieur des pages contenues dans une mémoire plus grande. Ajoutez un cadre et le plus petit ensemble ne sera pas réorganisé en un pire.
Cette propriété de confinement bloque l’anomalie de Bélády. FIFO n’en a pas, car l’ajout de mémoire modifie l’ordre de la file d’attente et peut changer quelle page deviendra la prochaine victime.
Les cours de systèmes d’exploitation enseignent encore cela car l’arithmétique est compacte et l’avertissement est permanent. Une politique peut être simple, rapide et plausible, mais néanmoins receler un piège caché.
L’homme derrière l’anomalie
László A. Bélády est né à Budapest en 1928 et a suivi une formation en génie mécanique et aéronautique avant de devenir l’une des premières figures de la recherche sur la mémoire virtuelle. La biographie de l’IEEE Computer Society énumère sa longue carrière chez IBM au centre de recherche Thomas J. Watson et ses rôles de direction ultérieurs au MCC et aux laboratoires de recherche Mitsubishi Electric.
Les archives orales de l’Institut Charles Babbage indiquent que Bélády a quitté la Hongrie après la révolution de 1956, a travaillé en Allemagne et en France, puis a rejoint IBM aux États-Unis en 1961. Au milieu des années 1960, il travaillait directement sur le stockage virtuel et le comportement des programmes.
Son nom était déjà associé à une autre idée majeure avant le document sur les anomalies. En 1966, il publie « Une étude des algorithmes de remplacement pour un ordinateur de stockage virtuel », le travail associé à la règle théorique de remplacement optimal souvent appelée MIN ou OPT de Bélády.
OPT supprime la page qui ne sera plus nécessaire pendant le plus longtemps. Aucun système d’exploitation réel ne peut l’implémenter parfaitement, car les programmes réels ne divulguent pas leurs références futures à l’avance, mais la règle donne aux chercheurs un étalon-or pour la comparaison.
Où se cache encore la leçon
Les machines d’aujourd’hui sont très éloignées des machines de radiomessagerie du journal de 1969. Le centre de recherche IBM Thomas J. Watson lui-même est devenu le siège social d’IBM Research en 1961, au début de l’ère qui a produit une grande partie de ces travaux sur la mémoire virtuelle.
Le compromis sous-jacent n’a pas disparu. Les caches réels des systèmes d’exploitation, des processeurs, des bases de données, des navigateurs et des systèmes de stockage utilisent souvent des approximations, car le suivi exact coûte du temps, de l’espace, de l’énergie ou des frais de verrouillage.
La récupération de mémoire Linux, par exemple, est construite autour de listes de style LRU et d’améliorations ultérieures, et non d’une liste littérale de manuel de chaque accès. La documentation du noyau Linux décrit toujours une infrastructure telle que le LRU inéluctable, car la véritable gestion de la mémoire est pleine de pages qui ne se comportent pas comme des exemples en classe.
Les systèmes de bases de données font des compromis similaires. Le gestionnaire de tampons de PostgreSQL est généralement expliqué par une politique de remplacement de type balayage d’horloge plutôt que par une pure liste LRU, car une faible surcharge est importante lorsque de nombreux processus touchent des tampons partagés.
Cela ne veut pas dire que chaque approximation produit l’anomalie de Bélády. Cela signifie que la garantie doit être gagnée. Une fois qu’un concepteur quitte le monde propre des algorithmes de pile, « plus de cache » n’est plus une preuve en soi.
Le problème des manuels scolaires qui refuse de prendre sa retraite
Chaque année, les élèves se réunissent selon la même séquence et comptent les ratés à la main. Le premier passage semble routinier. La deuxième passe semble fausse.
Trois images ne devraient pas en battre quatre. Le compteur de défauts de page indique que oui.
C’est là le pouvoir de l’exemple. Il compresse toute une discipline d’ingénierie en douze références et deux colonnes de notes : définir la politique, exécuter la charge de travail, mesurer le résultat et se méfier de toute réponse qui semblait évidente avant le début de la trace.
Bélády est décédé en 2021, mais l’anomalie reste l’un des pièges les plus propres de l’informatique. Ce soir, quelque part à l’intérieur d’une machine, un cache choisit ce qu’il faut oublier, et la différence entre un emplacement supplémentaire utile et un emplacement nuisible est toujours cachée dans la règle qui décide de ce qui part en premier.
