Алгоритм вытеснения

0 232

Алгоритм работы кэша с отложенной записью

Кэширование, выполняемое операционной системой
Кэш оперативной памяти состоит из следующих элементов:
набор страниц оперативной памяти, разделённых на буферы, равные по длине блоку данных соответствующего устройства внешней памяти; набор заголовков буферов, описывающих состояние соответствующего буфера; хеш-таблицы, содержащей соответствие номера блока заголовку; списки свободных буферов. Изначально все заголовки буферов помещаются в список свободных буферов. Если процесс намеревается прочитать или модифицировать блок, то он выполняет следующий алгоритм:
пытается найти в хеш-таблице заголовок буфера с заданным номером; в случае, если полученный буфер занят, ждёт его освобождения; в случае, если буфер не найден в хеш-таблице, берёт первый буфер из хвоста списка свободных; в случае, если список свободных буферов пуст, то выполняется алгоритм вытеснения (см. ниже); в случае, если полученный буфер помечен как «грязный», выполняет асинхронную запись содержимого буфера во внешнюю память. удаляет буфер из хеш-таблицы, если он был помещён в неё; помещает буфер в хеш-таблицу с новым номером. Процесс читает данные в полученный буфер и освобождает его. В случае модификации процесс перед освобождением помечает буфер как «грязный». При освобождении буфер помещается в голову списка свободных буферов.
Таким образом:
если процесс прочитал некоторый блок в буфер, то велика вероятность, что другой процесс при чтении этого блока найдёт буфер в оперативной памяти; запись данных во внешнюю выполняется только тогда, когда не хватает «чистых» буферов, либо по запросу. Основная статья: Алгоритмы кэширования
Если список свободных буферов пуст, то выполняется алгоритм вытеснения буфера. Алгоритм вытеснения существенно влияет на производительность кэша. Существуют следующие алгоритмы:
LRU (Least Recently Used) — вытесняется буфер, неиспользованный дольше всех; MRU (Most Recently Used) — вытесняется последний использованный буфер; LFU (англ.) (Least Frequently Used) — вытесняется буфер, использованный реже всех; ARC (англ.) (Adaptive Replacement Cache) — алгоритм вытеснения, комбинирующий LRU и LFU, запатентованный IBM. Применение того или иного алгоритма зависит от стратегии кэширования данных. LRU наиболее эффективен, если данные гарантированно будут повторно использованы в ближайшее время. MRU наиболее эффективен, если данные гарантированно не будут повторно использованы в ближайшее время. В случае, если приложение явно указывает стратегию кэширования для некоторого набора данных, то кэш будет функционировать наиболее эффективно.

Войти с помощью: 
Подписаться
Уведомление о
guest
0 Комментарий
Встроенные отзывы
Посмотреть все комментарии
0
Будем рады вашим мыслям, пожалуйста, прокомментируйте.x
()
x