Алгоритмы замещения Кривых Алексей krivykhalexey@mail.ru Зольников Павел pasha.zolnikov@gmail.com Самунь Виктор victor.samun@gmail.com IT Summer SPb 2012. - презентация

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

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

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

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

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

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

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

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

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

10 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 - жертва

11