Некоторые вопросы разработки представляют особый интерес. Первый из них связан с тем, что если запрос ввода-вывода удовлетворяется кэшем, то данные из кэша должны быть переданы запросившему процессу. Это может быть выполнено как путем пересылки блока данных в основной памяти из кэша в область пользовательского процесса, так и посредством совместного использования памяти кэша (в этом случае запросившему процессу можно передать указатель на соответствующий слот кэша). Последний подход экономит время, использовавшееся для пересылки данных из памяти в память, и разрешает совместный доступ к кэшу другим процессам (в соответствии с рассмотренной в главе 5, "Параллельные вычисления: взаимоисключения и многозадачность", моделью читателей/писателей).
Второй вопрос связан со стратегией замещения. Когда в кэш поступает новый сектор, он должен заменить один из содержащихся в кэше секторов. Эта проблема аналогична рассмотренной в главе 8, "Виртуальная память", проблеме замещения страниц. При изучении этого вопроса был опробован ряд алгоритмов, и в результате наиболее подходящим (и, соответственно, распространенным) оказался алгоритм замены блока, к которому дольше всего не было обращений (least recently used — LRU). Логически кэш состоит из стека блоков, причем на вершине стека располагается блок, к которому было последнее обращение. При обращении к блоку в кэше он перемещается из текущей позиции на вершину стека. Если блок поступает с диска, то самый нижний блок стека удаляется, а вновь поступивший блок размещается на вершине стека. Естественно, необходимости в реальном перемещении блоков по основной памяти нет — с кэшем может быть связан стек указателей на блоки.
Другой возможностью является алгоритм замены тех блоков, обращение к которым происходит наименее часто (least frequently used — LFU). Этот алгоритм может быть реализован посредством назначения счетчика каждому блоку кэша. При поступлении блока его счетчику присваивается значение 1; с каждым новым обращением значение счетчика увеличивается на 1. При необходимости замены выбирается блок с наименьшим значением счетчика. Может показаться, что LFU является более подходящей по сравнению с LRU стратегией, поскольку LFU использует более существенную информацию о блоках. Однако у простого LFU-алгоритма имеется следующая проблема. Может возникнуть ситуация, когда обращение к некоторым блокам выполняется относительно редко, но зато при обращении интервалы между повторными обращениями оказываются короткими вследствие локализации. Тем самым значение счетчика резко увеличивается и не отражает реальной вероятности использования данного блока в ближайшее время. Так эффект локализации может стать причиной того, что алгоритм LFU произведет неверный выбор замещаемого блока.
Для преодоления этого недостатка алгоритма LFU предлагается технология, известная как замещение, основанное на частоте обращений [ROBI90]. Для ясности рассмотрим упрощенную версию, представленную на рис. 11.11,а. Блоки логически организованы в виде стека, как в алгоритме LRU. Ряд блоков в верхней части стека отделяется как новый раздел. При успешном обращении к кэшу соответствующий блок перемещается на вершину стека. Если блок к этому времени уже находился в новом разделе, то его счетчик обращений не увеличивается; i в противном случае его значение увеличивается на 1. Из-за того что размер нового раздела достаточно большой, счетчики блоков, к которым происходит многократное обращение за короткий период времени, останутся неизменными. Если же выполняется обращение к блоку, отсутствующему в кэше, для замещения выбирается блок с наименьшим значением счетчика, расположенный вне нового раздела; в случае наличия нескольких таких блоков выбирается тот, к которому дольше всего не было обращений.
Авторы сообщают, что такая стратегия приводит лишь к незначительному улучшению стратегии LRU. Проблема заключается в следующем.
1. При отсутствии блока в кэше блок загружается в новый раздел со значением счетчика, равным 1.
2. Значение счетчика остается равным 1 все время пребывания блока в новом разделе.
3. В конечном счете блоки покидают новый раздел, значение счетчика при этом остается равным 1.
4. Если к такому блоку не происходит обращения за достаточно короткий промежуток времени, то вполне вероятно, что он будет заменен, поскольку значение его счетчика — наименьшее среди всех блоков вне нового раздела.
Внесение еще одного улучшения в алгоритм позволяет решить эту проблему. Разобьем стек на три раздела — новый, средний и старый (рис. 11.11,6). Как и прежде, счетчик обращений у блоков нового раздела не увеличивается. Для замещения, как и ранее, выбираются только блоки из старого раздела. Если средний раздел имеет достаточно большой размер, то это позволяет блокам с относительно частыми обращениями успеть увеличить значение счетчика до того, как они могут оказаться замещены. При имитационном моделировании авторы обнаружили, что такая усовершенствованная стратегия работает значительно лучше, чем простой алгоритм LRU или LFU.
Рис. 11.11. Замещение, основанное на частоте обращений
Независимо от конкретной стратегии замещение может выполняться по требованию или предварительно. В первом случае сектор замещается только тогда, когда требуется свободный слот; при втором подходе одновременно освобождается несколько слотов. Обоснование такого подхода заключается в необходимости записи секторов из кэша на диск. Если сектор, загруженный в кэш, использовался только для чтения, то нет необходимости в его записи на диск; однако если содержимое сектора было изменено, то перед замещением сектор необходимо записать на диск. В этом случае имеет смысл кластеризация для достижения минимального времени поиска.
