Algorithme du cache
Un algorithme de cache est un algorithme utilisé pour gérer un cache ou un groupe de données. Lorsque la mémoire cache est pleine, il décide quel élément doit être supprimé de la mémoire cache. Le terme "taux de réussite" décrit la fréquence à laquelle une demande peut être traitée à partir du cache. Le terme latence décrit la durée pendant laquelle un élément mis en cache peut être obtenu. Les alorithmes du cache sont un compromis entre le taux de réussite et la latence.
- L'algorithme de mise en cache le plus efficace serait de toujours rejeter les informations qui ne seront plus nécessaires le plus longtemps à l'avenir. Ce résultat optimal est appelé l'algorithme optimal de Belady ou l'algorithme de clairvoyance. Comme il est généralement impossible de prédire jusqu'à quand les informations seront nécessaires dans l'avenir, cette méthode n'est généralement pas applicable 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 avec le minimum optimal.
- Les moins récemment utilisés (LRU) : supprime d'abord les articles les moins récemment utilisés. Cet algorithme nécessite de garder une trace de ce qui a été utilisé et à quel moment. Cela coûte cher si l'on veut s'assurer que l'algorithme élimine toujours l'article 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 "Le moins récemment utilisé" en fonction des bits d'âge. Dans cette 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 dont les membres comprennent : 2Q de Theodore Johnson et Dennis Shasha et LRU/K de Pat O'Neil, Betty O'Neil et Gerhard Weikum.
- Le plus récemment utilisé (MRU) : Cet algorithme supprime d'abord les éléments les plus récemment utilisés. Ce mécanisme de mise en cache est couramment utilisé pour les caches de la mémoire des bases de données.
- Pseudo-LRU (PLRU) : Il y a certains cas où la LRU est très difficile à mettre en œuvre. Dans ces cas, il peut suffire de savoir que, dans la plupart des cas, l'un des éléments les moins récemment utilisés est supprimé. L'algorithme PLRU peut être utilisé dans ce cas, car il n'a besoin que d'un bit par élément de cache pour fonctionner.
- Ensemble associatif bidirectionnel : pour les caches CPU à grande vitesse où même le PLRU est trop lent. L'adresse d'un nouvel élément est utilisée pour calculer l'un des deux emplacements possibles dans le cache où il est autorisé à aller. Le LRU des deux est éliminé. Cela nécessite un bit par paire de lignes de cache, pour indiquer lequel des deux a été le moins récemment utilisé.
- Direct-mapped cache : pour les caches CPU les plus rapides où même les caches associatifs bidirectionnels sont trop lents. L'adresse du nouvel élément est utilisée pour calculer le seul endroit du cache où il est autorisé à aller. Tout ce qui était là avant est jeté.
- Le moins fréquemment utilisé (LFU) : LFU compte le nombre de fois qu'un article est nécessaire. Ceux qui sont utilisés le moins souvent sont d'abord jetés.
- Adaptive Replacement Cache (ARC) : équilibre constamment entre LRU et LFU, pour améliorer le résultat combiné.
- Algorithme de mise en cache de la multiplicité des files d'attente (MQ) : (par Y. Zhou J.F. Philbin et Kai Li).
Autres éléments à prendre en compte :
- Articles de coût différent : conservez les articles qui sont chers à obtenir, par exemple ceux qui prennent beaucoup de temps à obtenir.
- Les objets occupant plus de place dans la mémoire cache : Si les objets ont des tailles différentes, la mémoire cache peut vouloir jeter un grand objet pour en stocker plusieurs plus petits.
- Les articles qui expirent avec le temps : Certains caches conservent des informations qui expirent (par exemple, un cache de nouvelles, un cache DNS ou un cache de navigateur web). L'ordinateur peut se débarrasser des éléments parce qu'ils sont expirés. En fonction de la taille du cache, aucun autre algorithme de mise en cache n'est nécessaire pour éliminer les éléments.
Divers algorithmes existent également pour maintenir la cohérence du cache. Cela ne s'applique qu'aux situations où plusieurs caches indépendants sont utilisés pour les mêmes données (par exemple, plusieurs serveurs de base de données mettant à jour le même fichier de données partagé).
Quels emplacements de mémoire peuvent être mis en cache par quels emplacements de cache
Questions et réponses
Q : Qu'est-ce qu'un algorithme de cache ?
R : Un algorithme de cache est un algorithme utilisé pour gérer un cache ou un groupe de données. Il décide quel élément doit être supprimé du cache lorsqu'il est plein.
Q : Qu'est-ce que le taux de réussite ?
R : Le taux de réussite décrit la fréquence à laquelle une requête peut être servie à partir du cache.
Q : Que décrit la latence ?
R : La latence décrit pendant combien de temps un élément mis en cache peut être obtenu.
Q : Qu'est-ce que l'algorithme optimal de Belady ?
R : L'algorithme optimal de Belady, également connu sous le nom d'algorithme clairvoyant, est un algorithme de mise en cache efficace qui écarte toujours les informations qui ne seront pas nécessaires pendant la plus longue période à venir. Ce résultat ne peut généralement pas être mis en œuvre dans la pratique car il nécessite de prédire ce qui sera nécessaire dans un avenir lointain.
Q : Comment fonctionne le système LRU (Least Recently Used) ?
R : LRU supprime d'abord les éléments les moins récemment utilisés et nécessite de garder la trace de ce qui a été utilisé quand en utilisant des "bits d'âge" pour chaque ligne de cache et en recherchant laquelle a été utilisée le moins récemment en fonction des bits d'âge. Chaque fois qu'une ligne de cache est utilisée, les âges de toutes les autres lignes de cache sont modifiés en conséquence.
Q : Comment fonctionne la fonction Most Recently Used (MRU) ?
R : Le MRU supprime en premier les éléments les plus récemment utilisés. Ce mécanisme de mise en cache est couramment utilisé pour les caches de mémoire des bases de données.
Q : Quels autres algorithmes existent pour maintenir la cohérence du cache ?
R : Il existe divers algorithmes pour maintenir la cohérence du cache lorsque plusieurs caches indépendants sont utilisés pour des données partagées, par exemple lorsque plusieurs serveurs de bases de données mettent à jour un seul fichier de données partagé.
