#algorithme #code

Les “cache remplacement policies” ou “cache algorithms” sont des algorithmes utilisés pour la gestion du cache.

Le cache est de la mémoire à accès rapide permettant d’accélérer les programmes. Cependant, dès que le cache est plein, il faut supprimer des paires clé-valeur, en essayant de conserver les plus utiles, c’est à dire les plus susceptibles d’être réutilisées par la suite. Cela permet d’augmenter le hit rate (proportion de fois où la clé recherchée est présente dans le cache)

Les principales cache eviction policies sont : - Random Replacement (RR), utilisé dans certains processeurs ARM - First In First Out (FIFO), une queue - Last In First Out (LIFO), une stack - Least Recently Used (LRU): la valeur accédée depuis le plus longtemps est retirée (parfois en approximation) - Most Recently Used (MRU): la valeur ajoutée en dernière est la première à être retirée (rarement utilisé) - Least Frequently Used: la valeur accédée le moins souvent (avec un compteur pour chaque accès)