Алгоритъм за кеширане

Алгоритъмът на кеша е алгоритъм, използван за управление на кеш или група данни. Когато кешът е пълен, той решава кой елемент трябва да бъде изтрит от кеша. Думата hit rate (честота на попадане) описва колко често дадена заявка може да бъде обслужена от кеша. Терминът латентност описва за колко време може да се получи даден елемент от кеша. Алгоритмите за кеширане са компромис между степента на достигане и закъснението.

• Най-ефективният алгоритъм за кеширане би бил винаги да се изхвърля информацията, която няма да бъде необходима за най-дълъг период от време в бъдеще. Този оптимален резултат се нарича оптимален алгоритъм на Белади или алгоритъм на ясновидеца. Тъй като по принцип е невъзможно да се предвиди колко далеч в бъдещето ще бъде необходима информация, това обикновено не е приложимо на практика. Практическият минимум може да се изчисли само след експериментиране и да се сравни ефективността на действително избрания алгоритъм за кеширане с оптималния минимум.
• Най-малко използвани (LRU): първо се изтриват най-малко използваните елементи. Този алгоритъм изисква да се следи кога какво е било използвано. Това е скъпо, ако искаме да сме сигурни, че алгоритъмът винаги изхвърля най-малко използвания елемент. Общите имплементации на тази техника изискват да се съхраняват "битове на възрастта" за кеш-линиите и да се проследява "най-малко последно използваната" кеш-линия въз основа на битовете на възрастта. При такава реализация всеки път, когато се използва кеш-линия, възрастта на всички останали кеш-линии се променя. LRU всъщност е семейство от алгоритми за кеширане с членове, включващи: 2Q на Теодор Джонсън и Денис Шаша и LRU/K на Пат О'Нийл, Бети О'Нийл и Герхард Вайкум.
• Най-наскоро използвани (MRU): Този алгоритъм изтрива първо най-скоро използваните елементи. Този механизъм за кеширане обикновено се използва за кешове на паметта на бази данни.
• Pseudo-LRU (PLRU): Има някои случаи, в които е много трудно да се приложи LRU. В такива случаи може да е достатъчно да се знае, че в повечето случаи се изтрива един от най-малко използваните елементи. Там може да се използва алгоритъмът PLRU, тъй като той се нуждае само от един бит за всеки елемент от кеша, за да работи.

• Асоциативен 2-пътен набор: за високоскоростни процесорни кешове, при които дори PLRU е твърде бавен. Адресът на нов елемент се използва за изчисляване на едно от двете възможни места в кеша, където може да отиде. LRU от двете се изхвърля. Това изисква по един бит на двойка кеш-линии, за да се посочи кое от двете е било най-малко използвано.
• Direct-maped cache: за най-бързите кешове на процесора, при които дори 2-посочните асоциативни кешове са твърде бавни. Адресът на новия елемент се използва, за да се изчисли едно място в кеша, където е позволено да отиде. Всичко, което е било там преди, се изхвърля.
• Най-рядко използвани (LFU): LFU отчита колко често се налага дадено изделие. Тези, които се използват най-рядко, се изхвърлят първи.
• Адаптивна заместваща кеш памет (ARC): постоянно балансира между LRU и LFU, за да подобри комбинирания резултат.
• Алгоритъм за кеширане в няколко опашки (MQ): (от Y. Zhou J.F. Philbin и Kai Li).

Други неща, които трябва да вземете предвид:

• Елементи с различна цена: запазете елементите, които са скъпи за получаване, например тези, чието получаване отнема много време.
• Елементи, които заемат повече кеш: Ако елементите са с различни размери, кешът може да поиска да изхвърли голям елемент, за да съхрани няколко по-малки.
• Елементи, чийто срок на годност изтича с времето: Някои кешове съхраняват информация, чийто срок на годност изтича (напр. кеш за новини, DNS кеш или кеш на уеб браузър). Компютърът може да изхвърли елементи, тъй като срокът им е изтекъл. В зависимост от размера на кеша може да не е необходим допълнителен алгоритъм за изхвърляне на елементи.

Съществуват и различни алгоритми за поддържане на кохерентността на кеша. Това се отнася само за ситуации, при които се използват няколко независими кеша за едни и същи данни (например няколко сървъра за бази данни, които актуализират един общ файл с данни).

Въпроси и отговори

В: Какво представлява алгоритъмът на кеша?

В: Какво е коефициент на попадане?

В: Какво описва латентността?

В: Какво представлява оптималният алгоритъм на Белади?

Въпрос: Как работи принципът за най-рядко използвана информация (LRU)?

Въпрос: Как функционира функцията за най-скорошно използване (MRU)?

В: Какви други алгоритми съществуват за поддържане на кохерентността на кеша?

Търсене по буква