Буферизация и кэширование
Если требуемый блок диска не найден в кэше, то для него должен быть выделен буфер. Проблема в том, что общее количество буферов кэша ограничено. Чтобы отдать один из них под требуемый блок, надо «вытеснить» из кэша один из блоков, которые там хранились. При этом, если вытесняемый блок «грязный», то он должен быть «очищен», т.е. записан на диск. При вытеснении «чистого» блока никаких операций с диском выполнять не надо.
Какой из блоков, хранящихся в кэше, следует выбрать для вытеснения, чтобы сократить общее количество обращений к диску? Это крайне важный вопрос, и если он будет решаться неправильно, то вся работа системы может затормозиться из-за постоянных обращений к диску.
Имеется теоретически оптимальное решение данной задачи, которое заключается в следующем. Число обращений к диску будет минимально, если каждый раз выбирать для вытеснения тот блок данных, к которому в будущем дольше всего не будет обращений. К сожалению, воспользоваться этим правилом на практике невозможно, так как последовательность обращений к блокам диска непредсказуема. Данный теоретический результат полезен только как недостижимый идеал, с которым можно сравнивать результаты применения более реалистичных алгоритмов выбора.
Среди алгоритмов, используемых на практике, лучшим считается алгоритм LRU (Least Recently Used, в вольном переводе «давно не использовавшийся»). Он заключается в следующем: выбирать для вытеснения следует тот блок, к которому дольше всего не было обращений. Здесь как раз используется принцип локальности ссылок: раз обращений давно не было, то, вероятно, их и не будет в ближайшее время.
Как на практике реализуется выбор блока по правилу LRU? Очевидное решение – при каждом обращении к буферу записывать в его заголовке текущее время, а при выборе для вытеснения искать самую раннюю запись – слишком громоздко и медленно. Есть гораздо лучшая возможность.
Все буферы кэша связываются в линейный список. В заголовке каждого буфера хранится ссылка на следующий по порядку списка буфер (фактически хранится индекс этого буфера в массиве буферов). При каждом обращении к блоку данных для чтения или записи выполняется также перемещение соответствующего буфера в конец списка. Это не означает перемещения данных, хранящихся в буфере, изменяются только несколько ссылок в заголовках.
предыдущаяследующая