Введение
1 Постановка задачи 6
1.1 Проблемы проектирования кэш-систем 6
1.2 Задача кэширования для одноуровневой кэш-системы 7
2 Конкурентный анализ алгоритмов кэширования 10
2.1 Элементы конкурентного анализа 10
2.2 Оценка конкурентности некоторых детерминированных и вероятностных
стратегий замещения страниц в кэш-памяти 12
3 Моделирование одноуровневых систем кэширования 18
3.1 Автоматная модель алгоритмов кэширования 18
3.2 Характеризация автоматной модели 21
3.3 Методология оценки эффективности алгоритмов кэширования 22
4 Алгоритмы и программы решения задачи 24
4.1 Описание гибридного алгоритма 24
4.2 Описание разработанных программных средств 26
4.3 Экспериментальное исследование гибридного алгоритма 26
Заключение 31
Список использованных источников 32


Купить

Компьютер состоит из самых разных по принципам работы и назначению устройств, и его подсистемы и узлы работают с различной скоростью. Использование кэш-систем является одним из приемов, направленных на согласование работы разных по скорости устройств и повышение производительности вы-числительных систем [8]. Кэш-системы в зависимости от назначения могут значительно различаться. Однако основным принципом их реализации является использование двух типов памяти: основной памяти (большой по объему, но медленной) и кэш-памяти (быстрой, но ограниченного объема) [4]. В настоящее время наблюдается интенсивная заинтересованность исследователей во всем мире в повышении производительности различных вычислительных систем, в том числе за счет использования кэш-систем.
При проектировании кэш-системы определяются основные ее параметры, к которым относятся: количество уровней и степень ассоциативности кэша, размер кэш-памяти, стратегия замещения (или политика вытеснения) страниц из кэш-памяти [3]. Задача определения оптимальной стратегии замещения страниц, ее также называют задачей кэширования, является центральной при создании кэш-систем.
Суть этой задачи для одноуровневой системы кэширования заключается в следующем. Основная память разбита на страницы равной длины. Страницы пронумерованы. Все страницы равны по важности и размеру. Кэш-память со-держит ограниченное количество страниц. Первоначально кэш-память пуста. На очередном шаге поступает запрос на какую-то страницу. Если эта страница в кэш-памяти уже имеется, то достаточно сообщить ее номер расположения в кэше. Если запрашиваемой страницы нет в кэше, то требуется решить, в какое место кэша можно ее записать и сделать это, считав запрашиваемую страницу из основной памяти. Задача кэширования состоит в том, чтобы определить ка¬кую именно страницу удалить из кэша, чтобы освободить место для новой страницы. Данная задача может быть обобщена на более сложные структуры кэш-системы. Так в случае с сегментированным кэшем возникает необходимость организации работы с каждым сегментом в отдельности, а для многоуровневой системы - отдельно с каждым уровнем.
Алгоритмы решения задачи кэширования называют алгоритмами кэширования или стратегиями замещения. В качестве входных данных для алгоритмов кэширования выступают размер кэша и последовательность запрашиваемых страниц. Примечательно, что все стратегии замещения являются online алгоритмами, поскольку считается, что для них последовательность запрашиваемых страниц целиком неизвестна, т. е. изначально неизвестны все входные данные и длина входа алгоритма. Напомним, что online алгоритмы - это алгоритмы, обрабатывающие вход по мере поступления [6, 9]. Качество работы (или эффективность) таких алгоритмов невозможно оценить традиционными способами через ресурсную сложность. Их эффективность принято оценивать с помощью конкурентного анализа [11].
Наиболее известными стратегиями замещения для одноуровневых кэш- систем являются алгоритмы LRU, MRU, LFU, FIFO [3]. Данные стратегии широко используются в системах ввода-вывода реальных операционных систем. Их часто называют стратегиями типа LRU. Для них характерны следующие особенности: они детерминированные, в них не предусмотрена сегментация кэш-памяти, они реализуют стратегии замещения страниц, основываясь на истории обработки запросов. Кроме политик типа LRU также широко используются вероятностные и адаптивные алгоритмы. Примером вероятностного алгоритма является алгоритм маркировки (MARKER), а примером адаптивного алгоритма - алгоритм ARC (Adaptive Replacement Cache) [13].
Несмотря на то, что к настоящему времени уже разработан целый спектр алгоритмов кэширования, проблема поиска новых подходов к их разработке - подходов, позволяющих улучшить эффективность работы алгоритмов кэширования в различных ситуациях, остается актуальной. Одним из таких подходов, активно развивающимся в последнее время, является гибридизация (скрещивание) известных алгоритмов. Гибридному подходу посвящены работы М.Б. Аль- Згуль, А. Жукова [2, 4].
Объектом исследования бакалаврской работы являются кэш-системы, а предметом исследования модели и алгоритмы кэширования, направленные на увеличение эффективности кэш-систем.
Цель работы: исследование стратегий замещения страниц одноуровневой системы кэширования, разработка моделей и алгоритмов гибридизации известных стратегий замещения.
Для достижения поставленной цели, в работе требовалось
- изучить принципы построения кэш-систем и известных стратегий замещения;
- изучить основы конкурентного анализа online алгоритмов;
- разработать программные реализации алгоритма Белади, алгоритма LRU, алгоритма маркировки;
- провести теоретические и экспериментальные исследования конкурентности алгоритмов типа LRU и алгоритма маркировки;
- разработать автоматные модели стратегий замещения и их гибридизации;
- разработать гибридный алгоритм кэширования и реализовать его в виде программы;
- на основе экспериментальных исследований найти параметры, необходимые для эффективного функционирования разработанного гибридного алгоритма.
Купить