Алгоритмы замещения Кривых Алексей Зольников Павел Самунь Виктор IT Summer SPb

Оптимальный алгоритм (алгоритм Белади) Вытеснять те сегменты, которые не понадобятся дольше всего Идеальный оракул

LRU Least Recently Used Вытесняем сегмент, который не использовался дольше всего, где - количество страниц, замещенных LRU, B – размер кэша, a-константа Недостаток: Использует слишком мало информации

Random Replacement Замещает случайно выбранный сегмент Был реализован в ARM процессорах Главное преимущество - простота

LFU LFU – Feast Frequently Used Вытесняем элемент, к которым обращались меньше всего раз Недостаток: Имеет тенденцию хранить страницы, которые были популярны в прошлом.

LRU/K LRU/1 = LRU Преимущества – Использует больше информации, чем LRU, при K >1 – Основан на понятии «старение», учитывающем, только последние K обращений Недостаток: – Cложность – Необходим вспомогательный алгоритм для неопределенного случая

Backward K-distance Имеем к моменту времени t строку запросов, если, и было в точности K-1 значений i, таких, что где, если p не появлялось K раз в строке

LRU/K замещение В качестве жертвы выбираем сегмент, для которого максимальное Неопределенная ситуация возникает, если сегментов с больше одного, в этом случае необходимо использовать вспомогательный алгоритм

2Q 2Q – 2 Queue Как и LRU/K имеет тенденцию оставлять только популярные страницы Как утверждает Theodore Jonson из университета Флорида, работает также хорошо, как и LRU/K Ain(25% ) – FIFO, Am-LRU, Aout(50%)-FIFO

2Q2Q If (X ϶ Am) then pushToHead(X, Am) else if(X ϶ Aout) then pushToHead (X, Am) else if (X ϶Ain) else pushToHead(X, Ain) pushToHead(V, Aout) end if Где X – запрашиваемая страница, V - жертва