Адаптивные алгоритмы кэширования в информационных системах

• Автор: Жуков, Александр Игоревич
• Шифр специальности: 05.13.01
• Научная степень: Кандидатская
• Год защиты: 2012
• Место защиты: Ростов-на-Дону
• Количество страниц: 194 с. : ил.

СОДЕРЖАНИЕ
ВВЕДЕНИЕ.

1 УНИВЕРСАЛЬНАЯ МЕТОДОЛОГИЯ УВЕЛИЧЕНИЯ ПРОИЗВОДИТЕЛЬНОСТИ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ

1.1 Общие вопросы организации систем кэширования

1.2 Особенности кэширования информации в системах.

1.3 Проблемы реализации кэшсистем

1.3.1 Реализация иерархических кэшсистем.

1.3.2 Обеспечение согласованности данных кэша.

1.3.3 Влияние размера кэшпамяти на эффективность системы кэширования

1.3.4 Выбор стратегии замещения объектов в кэшпамяти.

1.3.4.1 Идеальные стратегии замещения

1.3.4.2 Стратегии замещения семейства
1.3.4.3 Специальные стратегии замещения
1.3.4.4 Стратегии замещения семейства
1.3.4.5 Комбинационные стратегии замещения.
1.3.4.6 Нечеткие стратегии замещения.
1.3.4.7 Адаптивные стратегии замещения.
1.3.4.8 Классификация стратегий замещения
1.4 Выводы но главе.
2 ИССЛЕДОВАНИЕ И МОДЕЛИРОВАНИЕ ОДНОУРОВНЕВЫХ СИСТЕМ КЭШИРОВАНИЯ.
2.1 Методология исследования эффективности алгоритмов замещения
2.2 Математическая модель потока запросов.
2.3 Параметры количественного исследования и методы обработки полученных результатов
2.4 Моделирование одноуровневой системы кэширования.
2.4.1 Математическая модель абстрактной одноуровневой системы кэширования.
2.4.2 Математические модели известных стратегий замещения
2.4.2.1 Математическая модель
2.4.2.2 Математическая модель I.
2.4.2.3 Математическая модель
2.4.2.4 Математическая модель нечеткого алгоритма кэширования
2.4.2.5 Математическая модель
2.4.3 Обобщенная математическая модель управляемой стохастической гибридной системы кэширования.
2.5 Формализованная постановка решаемой научной задачи
2.6 Выводы по главе.
3.1 Адаптивная кэшсистема на базе стохастического гибридного алгоритма кэширования.
3.1.1 Реализуемая схема адаптации
3.1.2 Методы поиска вектора управления стохастическим гибридным алгоритмом кэширования
3.1.3 Увеличение скорости реагирования на изменения в трассе.
3.2 Адаптивная кэшсистема ресурсов на базе нечеткой логики
3.3 Выводы но главе
4 ЭКСПЕРИМЕНТАЛЬНОЕ ИССЛЕДОВАНИЕ КЭШСИСТЕМ
4.1 Программный стенд дли исследования одноуровневых кэшсистем .
4.2 Результаты экспериментальных исследований
4.2.1 Сравнение алгоритмов кэширования на квазисгационарных трассах
4.2.2 Сравнение алгоритмов кэширования на грассах с петлеобразной моделью доступа
4.2.3 Сравнение алгоритмов кэширования на нестационарных синтезированных трассах
4.2.3 Сравнение алгоритмов кэширования на реальных трассах
4.3 Практические результаты внедрения разработанных решений
4.4 Выводы по главе
ЗАКЛЮЧЕНИЕ.
СПИСОК ИСПОЛЬЗУЕМЫХ ИСТОЧНИКОВ


При определении типа трассы будем ассоциировать его название либо с некоторой характеристикой трассы, как правило, законом распределения обращений к объектам в данной трассе, либо для реапьных трасс - с се источником. Таким образом, тип трассы определяет ее принадлежность к заранее заданному нами множеству трасс этого типа, каждый элемент которого обладает определенными свойствами. Важным понятием, используемым при моделировании трасс, является понятие «стек дистанций» (англ. Мэттсоном []. Другими словами, дистанция объекта А отображает число уникальных обращений к другим объектам ИС, которое было произведено с момента последнего доступа к объекту А. Также дистанцией, применительно к трассе объектов, называют участок трассы для объекта А, который начинается и заканчивается обращением к объекту А и внутри себя не содержит обращений к этому объекту [,]. Кэш-память или кэш - это хранилище цифровой информации, характеризуемое более высокой стоимостью храпения данных по сравнению с основной памятью, т. Основная наснять - это хранилище полного набора объектов информационной системы, которые могут быть предоставлены ее пользователям. Объект внутри информационной системы существует до тех пор, пока он находится в основной памяти. Кэш-система - компонент информационной системы, располагаемый между интерфейсом доступа к объектам основной памяти и пользователем системы и реализующий управление кэш-памятью, а именно операции чтения и записи объектов. В случае нехватки свободного пространства в кэш-памяти кэш-система инициирует выполнение алгоритма кэширования. Важнейшими свойствами кэш-систем, характеризующими их роль внутри информационных систем, являются латентность и ненавязчивостъ. Латентность подразумевает сокрытие функционирования кэш-системы от конечного пользователя, а ненавязчивостъ означает сохранение работоспособности информационной системы в случае отключения кэш-системы. Таким образом, необходимым условием организации кэш-систем является наличие кэш-памяти и методов управлением ею. Алгоритм функционирования простой кэш-системы представлен на рисунке 1. Рис. В данном случае можем говорить о простой кэш-системе в том смысле, что в представленной системе определен лишь один уровень кэширования и одна кэш-память. В зарубежной литературе такие системы также называют одиночными (англ. Функционирование простой кэш-системы происходит по следующей схеме: информационная система получает запрос на предоставление объекта, после чего переадресует данный запрос кэш-системе. Затем кэш-сисгема определяет наличие соответствующего запросу объекта в кэшпамяти и, если он найден, возвращает его информационной системе, которая, в свою очередь, предоставляет его пользователю. Такая ситуация называется кэш-попаданием. В этом случае говорят о кэш-промахе. Различают обязательные кэш-промахи, возникающие независимо от принципов реализации кэш-систсмы при первом обращении к объекту пользователей информационной системы, а также возможные промахи, которые происходят, когда объект был вытеснен из кэш-памяти до очередного доступа к нему. Полученный из основной памяти после кэш-промаха объект передается пользователю, запросившему его. Кроме того, его копия направляется кэш-системе, которая должна сохранить его в кэш-памяти. Если свободного места в кэш-памяти уже не осталось, то кэш-система запускает алгоритм замещения объектов в кэш-памяти. Алгоритм замещения объектов в кэше (англ. Основной задачей алгоритма кэширования, как правило, является снижение числа возможных промахов []. Применительно к информационным технологиям различают online алгоритмы, которые последовательно обрабатывают входной иогок данных в том смысле, что данные поступающие на вход системы обрабатываются шаг за шагом, при этом в момент запуска алгоритма весь входной поток недоступен, и offline алгоритмы, которьie реализуются только после получения всех входных данных []. Стратегия замещения (англ. В общем случае для оценки полезности объекта обычно говорят о критерии полезности, который будем называть кэш-рейтингом объекта [], определение которого отличается для разных алгоритмов. В различных источниках в зарубежной литературе кэш-рейтинг также называют кэш-значением (англ.