Тема: ИССЛЕДОВАНИЕ СТРАТЕГИЙ ЗАМЕЩЕНИЯ СТРАНИЦ ДЛЯ ЗАДАЧИ КЭШИРОВАНИЯ

Компьютер состоит из самых разных по принципам работы и назначению устройств, и его подсистемы и узлы работают с различной скоростью. Использование кэш-систем является одним из приемов, направленных на согласование работы разных по скорости устройств и повышение производительности вы-числительных систем [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 и алгоритма маркировки;
- разработать автоматные модели стратегий замещения и их гибридизации;
- разработать гибридный алгоритм кэширования и реализовать его в виде программы;
- на основе экспериментальных исследований найти параметры, необходимые для эффективного функционирования разработанного гибридного алгоритма.
Купить

В бакалаврской работе проведено исследование задачи кэширования, вы-явлены принципы построения кэш-систем, сформулирована задача кэширования. Разработаны программы, реализующие алгоритмы Белади, LRU, MARKER для решения задачи кэширования в режимах offline и online. Выполнен анализ online алгоритмов LRU, MARKER с помощью аппарата конкурентного анализа, а также вычислительные эксперименты, подтверждающие теоретические оценки эффективности этих алгоритмов. Представлена автоматная модель алгоритмов кэширования. На ее основе разработан гибридный алгоритм, эффективно совмещающий работу двух известных стратегий замещения страниц LRU и LFU. Гибридный алгоритм реализован в виде программы. Проведены вычисли¬тельные эксперименты, подтверждающие эффективность гибридного алгоритма в различных ситуациях, включая «худшие случаи» для каждого из гибридизируемых алгоритмов в отдельности. Найдено значение параметра Д, обеспечивающее эффективность гибридного алгоритма кэширования.
Результаты бакалаврской работы могут быть использованы при разработке различных типов кэш-систем.
Результаты бакалаврской работы докладывались на двух конференциях: «Международная научная конференция студентов, аспирантов и молодых ученых «Молодежь и наука: проспект Свободный-2015» (Красноярск, 2015)»; «Международная научная конференция студентов, аспирантов и молодых ученых «Молодежь и наука: проспект Свободный-2016» (Красноярск, 2016)».
Результаты бакалаврской работы опубликованы в материалах указанных выше конференциях и в электронном рецензируемом издании: Петраков И.Е. Модели и алгоритмы гибридизации алгоритмов кэширования // Программные продукты, системы и алгоритмы. - 2016. - № 3. - Режим доступа: http://www.swsys-web.ru/

Купить