35. Дисковый кэш. Алгоритмы замещения.

Дисковый кэш

Мы уже знакомы с понятием кэш-памяти – это память находящаяся между

регистрами процесса и основной памятью по производительности, она уменьшает среднее

время доступа к памяти благодаря принципу локализации.

Такой же принцип может применяться к дисковой памяти. Кэш диска – это буфер в

основной памяти, который может содержать несколько секторов диска. При запросе

некоторого сектора, он сначала ищется в КЭШе, и если находится там, то немедленно

возвращается. В противном случае происходит операция ввода-вывода, и сектор

считывается в буфер. По принципу локализации, есть вероятность, что этот сектор может

снова потребоваться в ближайшем будущем.

При разработке дискового КЭШа возникают следующие вопросы:

1. Если необходимый сектор найден в КЭШе, он может копироваться в область

памяти процесса. Или возможна передача процессу указателя на сектор в

КЭШе, но при этом требуется обеспечение совместного использования КЭШа

несколькими процессами (установка блокировки при доступе и т.д.)

2. Вопрос стратегии замещения. Если весь кэш заполнен, и необходимо

считывание нового блока с диска, какой блок из КЭШа выбрать для замещения?

Алгоритмы замещения

Наиболее подходящим и распространенным оказался алгоритм замены блока, к

которому дольше всего не было обращений. В этом случае кэш организован в виде

стека. На вершине стека – блок, к которому было последнее обращение. При запросе

блока, он перемещается наверх (используется не прямое перемещение памяти, а стек

указателей). При необходимости замещения, удаляется самый нижний блок стека.

Алгоритм замены блоков, обращение к которым происходи наименее часто.

Каждому блоку в КЭШе назначается счетчик. Изначально ему присваивается значение 1. С

каждым обращением счетчик увеличивается на 1. При замещении выбирается блок с

наименьшим счетчиком. Недостаток – удаление из КЭШа блоков, которые используются

относительно редко, но промежуток между обращениями к ним небольшой вследствие

локализации.

Замещение, основанное на частоте обращений. Блоки организованы в виде стека.

Часть блоков верхней части стека – новый раздел. При успешном обращении к КЭШу

нужный блок перемещается наверх. Если блок уже находился в новом разделе, его счетчик

не меняется, иначе счетчик увеличивается на 1. Счетчики блоков, к которым происходят

частые обращения за короткий промежуток времени, останутся неизменными. Если

запрошен блок, которого нет в КЭШе, для замены выбирается блок с наименьшим

счетчиком/