L’algorithme de Bélády
L’algorithme de mise en cache le plus efficace serait de toujours rejeter les informations qui ne seront pas nécessaires le plus longtemps à l’avenir. Ce résultat optimal est appelé algorithme optimal de Bélády / politique de remplacement simplement optimale ou algorithme de clairvoyant. Comme il est généralement impossible de prédire dans quelle mesure les informations seront nécessaires à l’avenir, cela n’est généralement pas réalisable dans la pratique. Le minimum pratique ne peut être calculé qu’après expérimentation, et on peut comparer l’efficacité de l’algorithme de cache réellement choisi.
Au moment où un défaut de page se produit, un ensemble de pages est en mémoire. Dans l’exemple, la séquence de ‘5’, ‘0’, ‘1’ est accessible par la Trame 1, la Trame 2, la Trame 3 respectivement. Ensuite, lorsque « 2 » est accédé, il remplace la valeur « 5 », qui se trouve dans la trame 1 car elle prédit que la valeur « 5 » ne sera pas accessible dans un proche avenir. Comme un système d’exploitation à usage général réel ne peut pas réellement prédire quand « 5 » sera accessible, l’algorithme de Bélády ne peut pas être implémenté sur un tel système.
First in first out (FIFO)Edit
En utilisant cet algorithme, le cache se comporte de la même manière qu’une file d’attente FIFO. Le cache expulse les blocs dans l’ordre dans lequel ils ont été ajoutés, sans égard à la fréquence ou au nombre de fois où ils ont été consultés auparavant.
Last in first out (LIFO) ou First in last out (FILO)Edit
En utilisant cet algorithme, le cache se comporte de la même manière qu’une pile et exactement à l’opposé d’une file d’attente FIFO. Le cache expulse d’abord le bloc ajouté le plus récemment sans tenir compte de la fréquence ou du nombre de fois où il a été consulté auparavant.
Édition des éléments les moins récemment utilisés (LRU)
Supprime d’abord les éléments les moins récemment utilisés. Cet algorithme nécessite de garder une trace de ce qui a été utilisé quand, ce qui est coûteux si l’on veut s’assurer que l’algorithme rejette toujours l’élément le moins récemment utilisé. Les implémentations générales de cette technique nécessitent de conserver des « bits d’âge » pour les lignes de cache et de suivre la ligne de cache « La moins récemment utilisée » en fonction des bits d’âge. Dans une telle implémentation, chaque fois qu’une ligne de cache est utilisée, l’âge de toutes les autres lignes de cache change. LRU est en fait une famille d’algorithmes de mise en cache avec des membres dont 2Q de Theodore Johnson et Dennis Shasha, et LRU/K de Pat O’Neil, Betty O’Neil et Gerhard Weikum.
La séquence d’accès pour l’exemple ci-dessous est A B C D E D F.
Dans l’exemple ci-dessus, une fois qu’un B C D est installé dans les blocs avec des numéros de séquence (Incrément 1 pour chaque nouvel accès) et lorsqu’on accède à E, c’est une erreur et il doit être installé dans l’un des blocs. Selon l’algorithme LRU, comme A a le rang le plus bas (A(0)), E remplacera A.
À l’avant-dernière étape, on accède à D et donc le numéro de séquence est mis à jour.
LRU, comme beaucoup d’autres politiques de remplacement, peut être caractérisé en utilisant un champ de transition d’état dans un espace vectoriel, qui décide des changements d’état de cache dynamique similaires à la façon dont un champ électromagnétique détermine le mouvement d’une particule chargée placée dans celui-ci.
Time aware least recently used (TLRU)Edit
Le Time aware Least Recently Used (TLRU) est une variante de LRU conçue pour la situation où le contenu stocké dans le cache a une durée de vie valide. L’algorithme convient aux applications de cache réseau, telles que les réseaux centrés sur l’information (ICN), les réseaux de diffusion de contenu (CDN) et les réseaux distribués en général. TLRU introduit un nouveau terme : TTU (Time to Use). TTU est un horodatage d’un contenu / page qui stipule le temps d’utilisation du contenu en fonction de la localité du contenu et de l’annonce de l’éditeur de contenu. En raison de cet horodatage basé sur la localité, TTU fournit plus de contrôle à l’administrateur local pour réguler le stockage réseau.Dans l’algorithme TLRU, lorsqu’un élément de contenu arrive, un nœud de cache calcule la valeur TTU locale en fonction de la valeur TTU attribuée par l’éditeur de contenu. La valeur TTU locale est calculée à l’aide d’une fonction définie localement. Une fois la valeur TTU locale calculée, le remplacement du contenu est effectué sur un sous-ensemble du contenu total stocké dans le nœud de cache. Le TLRU garantit que le contenu moins populaire et de petite durée de vie doit être remplacé par le contenu entrant.
Édition la plus récemment utilisée (MRU)
Rejette d’abord, contrairement à LRU, les éléments les plus récemment utilisés. Dans les résultats présentés lors de la 11e conférence du VLDB, Chou et DeWitt ont noté que « Lorsqu’un fichier est analysé à plusieurs reprises dans un modèle de référence, MRU est le meilleur algorithme de remplacement. »Par la suite, d’autres chercheurs présents à la 22e conférence du VLDB ont noté que pour les modèles d’accès aléatoire et les analyses répétées sur de grands ensembles de données (parfois appelés modèles d’accès cycliques), les algorithmes de cache MRU ont plus de succès que LRU en raison de leur tendance à conserver des données plus anciennes. Les algorithmes MRU sont les plus utiles dans les situations où plus un élément est ancien, plus il est susceptible d’être consulté.
La séquence d’accès pour l’exemple ci-dessous est A B C D E C D B.
Ici, A B C D sont placés dans le cache car il y a encore de l’espace disponible. Au 5ème accès E, on voit que le bloc qui contenait D est maintenant remplacé par E car ce bloc a été utilisé le plus récemment. Un autre accès à C et à l’accès suivant à D, C est remplacé comme c’était le bloc auquel on accédait juste avant D et ainsi de suite.
Pseudo-LRU(PLRU)Edit
Pour les caches CPU à grande associativité (généralement >4 voies), le coût d’implémentation de LRU devient prohibitif. Dans de nombreux caches de CPU, un schéma qui rejette presque toujours l’un des éléments les moins récemment utilisés est suffisant, de sorte que de nombreux concepteurs de CPU choisissent un algorithme PLRU qui n’a besoin que d’un bit par élément de cache pour fonctionner.Le PLRU a généralement un rapport d’erreur légèrement pire, une latence légèrement meilleure, utilise un peu moins de puissance que le LRU et des frais généraux inférieurs par rapport au LRU.
L’exemple suivant montre comment les Bits fonctionnent comme un arbre binaire de pointeurs de 1 bit qui pointent vers le sous-arbre le moins récemment utilisé. Suivre la chaîne de pointeur vers le nœud feuille identifie le candidat de remplacement. Lors d’un accès, tous les pointeurs de la chaîne du nœud feuille de la voie d’accès au nœud racine sont définis pour pointer vers un sous-arbre qui ne contient pas la voie d’accès.
La séquence d’accès est A B C D E.
Le principe ici est simple à comprendre si l’on ne regarde que les pointeurs de flèches. Lorsqu’il y a un accès à une valeur, disons « A », et que nous ne la trouvons pas dans le cache, nous la chargeons de la mémoire et la plaçons au bloc où pointent actuellement les flèches, allant de haut en bas. Après avoir placé ce bloc, nous retournons ces mêmes flèches pour qu’elles pointent dans le sens opposé. Dans l’exemple ci-dessus, nous voyons comment « A » a été placé, suivi de « B », « C et « D ». Ensuite, lorsque le cache est devenu plein, ‘E’ a remplacé ‘A’ parce que c’était là que les flèches pointaient à ce moment-là, et les flèches qui menaient à ‘A’ ont été retournées pour pointer dans la direction opposée. Les flèches ont ensuite conduit à ‘B’, qui sera le bloc remplacé lors de la prochaine erreur de cache.
Random replacement (RR)Edit
Sélectionne aléatoirement un élément candidat et le rejette pour faire de la place si nécessaire. Cet algorithme ne nécessite pas de conserver d’informations sur l’historique d’accès. Pour sa simplicité, il a été utilisé dans les processeurs ARM. Il admet une simulation stochastique efficace.
La séquence d’accès pour l’exemple ci-dessous est un B C D E B D F
Édition LRU segmentée (SLRU)
Le cache SLRU est divisé en deux segments, un segment probatoire et un segment protégé. Les lignes de chaque segment sont ordonnées du plus au moins récemment accédées. Les données des échecs sont ajoutées au cache à l’extrémité la plus récemment consultée du segment probatoire. Les accès sont supprimés de l’endroit où ils résident actuellement et ajoutés à l’extrémité la plus récemment consultée du segment protégé. Les lignes du segment protégé ont ainsi été accédées au moins deux fois. Le segment protégé est fini, de sorte que la migration d’une ligne du segment probatoire vers le segment protégé peut forcer la migration de la ligne LRU dans le segment protégé vers l’extrémité la plus récemment utilisée (MRU) du segment probatoire, donnant à cette ligne une autre chance d’être accessible avant d’être remplacée. La limite de taille du segment protégé est un paramètre SLRU qui varie en fonction des modèles de charge de travail d’E/S. Chaque fois que des données doivent être supprimées du cache, des lignes sont obtenues à partir de l’extrémité LRU du segment probatoire.
Édition la moins utilisée (LFU)
Compte la fréquence à laquelle un élément est nécessaire. Ceux qui sont utilisés le moins souvent sont jetés en premier. Cela fonctionne de manière très similaire à LRU, sauf qu’au lieu de stocker la valeur de la date à laquelle un bloc a été accédé récemment, nous stockons la valeur du nombre de fois où il a été accédé. Donc bien sûr, lors de l’exécution d’une séquence d’accès, nous remplacerons un bloc qui a été utilisé le moins de fois de notre cache. Par exemple, si A a été utilisé (consulté) 5 fois et B a été utilisé 3 fois et d’autres C et D ont été utilisés 10 fois chacun, nous remplacerons B.
Édition la moins utilisée récemment (LFRU)
Le schéma de remplacement de cache la moins utilisée récemment (LFRU) combine les avantages des schémas LFU et LRU. LFRU convient aux applications de cache « en réseau », telles que les réseaux centrés sur l’information (ICN), les réseaux de diffusion de contenu (CDN) et les réseaux distribués en général. Dans LFRU, le cache est divisé en deux partitions appelées partitions privilégiées et non privilégiées. La partition privilégiée peut être définie comme une partition protégée. Si le contenu est très populaire, il est poussé dans la partition privilégiée. Le remplacement de la partition privilégiée se fait comme suit: LFRU expulse le contenu de la partition non privilégiée, pousse le contenu de la partition privilégiée vers la partition non privilégiée et insère enfin du nouveau contenu dans la partition privilégiée. Dans la procédure ci-dessus, le LRU est utilisé pour la partition privilégiée et un schéma LFU approximatif (ALFU) est utilisé pour la partition non privilégiée, d’où l’abréviation LFRU.
L’idée de base est de filtrer les contenus populaires localement avec le schéma ALFU et de pousser les contenus populaires vers l’une des partitions privilégiées.
LFU avec vieillissement dynamique (LFUDA)Modifier
Une variante appelée LFU avec vieillissement dynamique (LFUDA) qui utilise le vieillissement dynamique pour s’adapter aux changements dans l’ensemble des objets populaires. Il ajoute un facteur d’âge du cache au nombre de références lorsqu’un nouvel objet est ajouté au cache ou lorsqu’un objet existant est re-référencé. LFUDA incrémente l’âge du cache lors de l’expulsion des blocs en le définissant sur la valeur de clé de l’objet expulsé. Ainsi, l’âge du cache est toujours inférieur ou égal à la valeur de clé minimale dans le cache. Supposons qu’un objet ait été fréquemment consulté dans le passé et qu’il devienne maintenant impopulaire, il restera longtemps dans le cache, empêchant ainsi les objets nouvellement ou moins populaires de le remplacer. Ce vieillissement dynamique est donc introduit pour réduire le nombre de tels objets, les rendant ainsi éligibles au remplacement. L’avantage de LFUDA est qu’il réduit la pollution du cache causée par LFU lorsque les tailles de cache sont très petites. Lorsque les tailles de cache sont importantes, peu de décisions de remplacement sont suffisantes et la pollution du cache ne sera pas un problème.
Low inter-reference recency set (LIRS) Edit
LIRS est un algorithme de remplacement de page avec une performance améliorée par rapport à LRU et à de nombreux autres algorithmes de remplacement plus récents. Ceci est réalisé en utilisant la distance de réutilisation comme mesure pour classer dynamiquement les pages consultées afin de prendre une décision de remplacement. Les RIL répondent efficacement aux limites de la LRU en utilisant la récence pour évaluer la récence entre références (TRI) pour prendre une décision de remplacement.
Dans la figure ci-dessus, « x » représente qu’un bloc est accessible à l’instant t. Supposons que si le bloc A1 est accédé au temps 1, la récence deviendra 0 car il s’agit du premier bloc accédé et IRR sera 1 car il prédit que A1 sera à nouveau accédé au temps 3. Dans le temps 2 depuis l’accès à A4, la récence deviendra 0 pour A4 et 1 pour A1 car A4 est l’objet le plus récemment consulté et IRR deviendra 4 et il continuera. Au temps 10, l’algorithme LIRS aura deux ensembles LIR set={A1, A2} et HIR set={A3, A4, A5}. Maintenant, au moment 10, s’il y a accès à A4, un manque se produit. L’algorithme LIRS expulsera désormais A5 au lieu de A2 en raison de sa plus grande récence.
CLOCK-ProEdit
L’algorithme LRU ne peut pas être directement implémenté dans le chemin critique des systèmes informatiques, tels que les systèmes d’exploitation, en raison de sa surcharge élevée. Une approximation de LRU, appelée HORLOGE est couramment utilisée pour la mise en œuvre. De même, CLOCK-Pro est une approximation des LIR pour une implémentation à faible coût dans les systèmes. CLOCK-Pro est sous le cadre d’HORLOGE de base, mais a trois mérites distincts majeurs. Tout d’abord, CLOCK-Pro a trois « aiguilles d’horloge » contrairement à une structure simple d’HORLOGE où une seule « aiguille » est utilisée. Avec les trois aiguilles, CLOCK-Pro est capable de mesurer la distance de réutilisation des accès aux données de manière approximative. Deuxièmement, tous les avantages des RIL sont conservés, tels que l’expulsion rapide d’éléments de données à accès unique et / ou à faible localité. Troisièmement, la complexité du CLOCK-Pro est la même que celle de CLOCK, il est donc facile à mettre en œuvre à faible coût. L’implémentation de remplacement du cache tampon dans la version actuelle de Linux est une combinaison de LRU et CLOCK-Pro.
Édition du cache de remplacement adaptatif (ARC)
Équilibre constamment entre LRU et LFU, pour améliorer le résultat combiné. ARC améliore le SLRU en utilisant les informations sur les éléments de cache récemment expulsés pour ajuster dynamiquement la taille du segment protégé et du segment probatoire afin de tirer le meilleur parti de l’espace de cache disponible. L’algorithme de remplacement adaptatif est expliqué avec l’exemple.
AdaptiveClimb(AC)Edit
Utilise le hit /miss récent pour ajuster le saut où, dans climb any hit, la position d’un emplacement bascule vers le haut, et dans LRU hit, la position du hit vers le haut. Ainsi, bénéficiant de l’optimalité de la montée lorsque le programme est dans une portée fixe, et de l’adaptation rapide à une nouvelle portée, comme le fait LRU. Prend également en charge le partage de cache entre les cœurs en libérant des extras lorsque les références se trouvent dans la partie supérieure du cache.
Clock with adaptive replacement (CAR)Edit
Combine les avantages du cache de remplacement adaptatif (ARC) et de l’HORLOGE. La VOITURE a des performances comparables à l’ARC et surpasse considérablement les LRU et l’HORLOGE. Comme ARC, CAR est auto-tuning et ne nécessite aucun paramètre magique spécifié par l’utilisateur. Il utilise 4 listes doublement chaînées : deux horloges T1 et T2 et deux listes LRU simples B1 et B2. L’horloge T1 stocke les pages basées sur « récence » ou « utilité à court terme » tandis que T2 stocke les pages avec « fréquence » ou « utilité à long terme ». T1 et T2 contiennent les pages qui se trouvent dans le cache, tandis que B1 et B2 contiennent des pages qui ont récemment été expulsées de T1 et T2 respectivement. L’algorithme essaie de maintenir la taille de ces listes B1≈T2 et B2≈T1. De nouvelles pages sont insérées dans T1 ou T2. S’il y a un coup dans la taille B1 de T1 est augmenté et de même s’il y a un coup dans la taille B2 de T1 est diminué. La règle d’adaptation utilisée a le même principe que celle d’ARC, investir davantage dans des listes qui donneront plus de visites lorsque plus de pages y seront ajoutées.
Édition Multi-files d’attente (MQ)
L’algorithme multi-files d’attente ou MQ a été développé pour améliorer les performances du cache tampon de deuxième niveau pour, par exemple, un cache tampon de serveur. Il est introduit dans un article de Zhou, Philbin et Li. Le cache MQ contient un nombre m de files d’attente LRU: Q0, Q1,…, Qm-1. Ici, la valeur de m représente une hiérarchie basée sur la durée de vie de tous les blocs de cette file d’attente particulière. Par exemple, si j > i, les blocs de Qj auront une durée de vie plus longue que ceux de Qi. En plus de ceux-ci, il existe un autre tampon d’historique Qout, une file d’attente qui maintient une liste de tous les identifiants de bloc ainsi que leurs fréquences d’accès. Lorsque Qout est plein, l’identifiant le plus ancien est expulsé. Les blocs restent dans les files d’attente LRU pendant une durée de vie donnée, qui est définie dynamiquement par l’algorithme MQ comme étant la distance temporelle maximale entre deux accès au même fichier ou le nombre de blocs de cache, selon le plus grand. Si un bloc n’a pas été référencé au cours de sa durée de vie, il est rétrogradé de Qi à Qi−1 ou expulsé du cache s’il est en Q0. Chaque file d’attente a également un nombre d’accès maximal ; si un bloc de la file d’attente Qi est accédé plus de 2i fois, ce bloc est promu Qi + 1 jusqu’à ce qu’il soit accédé plus de 2i + 1 fois ou que sa durée de vie expire. Dans une file d’attente donnée, les blocs sont classés en fonction de la récence d’accès, selon LRU.
On peut voir sur la Fig. comment les files d’attente m LRU sont placées dans le cache. Voir aussi de la Fig. comment le Qout stocke les identifiants de bloc et leurs fréquences d’accès correspondantes. a a été placé dans Q0 car il n’a été consulté qu’une seule fois récemment et nous pouvons vérifier dans Qout comment b et c ont été placés dans Q1 et Q2 respectivement car leurs fréquences d’accès sont 2 et 4. La file d’attente dans laquelle un bloc est placé dépend de la fréquence d’accès (f) comme log2(f). Lorsque le cache est plein, le premier bloc à être expulsé sera la tête de Q0 dans ce cas a. Si a est accédé une fois de plus, il passera à Q1 en dessous de b.
Sacoche: Algorithme de mise en cache basé sur un conteneur pour les objets compoundsedit
Sacoche est un mécanisme de mise en cache flash basé sur un conteneur qui identifie les conteneurs divergents (hétérogènes) où les blocs qui y sont détenus ont des modèles d’accès très variables. Pannier utilise une structure de file d’attente de survie basée sur une file d’attente prioritaire pour classer les conteneurs en fonction de leur temps de survie, qui est proportionnel aux données en direct dans le conteneur. Pannier est construit sur la base de LRU segmenté (S2LRU), qui sépare les données chaudes et froides. La sacoche utilise également un contrôleur de rétroaction en plusieurs étapes pour étrangler les écritures du flash afin d’assurer la durée de vie du flash.