Содержание к диссертации
Введение
Глава 1. Особенности кэширования в информационных системах 11
1.1. Кэширование информации в базах данных 11
1.1.1. Основные архитектуры БД 11
1.1.2. Кэширование в СУБД с файл-серверной архитектурой... 15
1.1.3. Кэширование в архитектуре клиент-сервер 16
1.1.4. Кэширование в объектно-ориентированных СУБД 22
1.2. Кэширование информации в Web-системах 25
1.3. Выводы по первой главе 31
Глава 2. Модели и методы кэширования информации 32
2.1. Основные определения и терминология систем кэширования информации 32
2.2. Математические модели потоков запросов 39
2.2.1. Основные определения, термины и допущения в моделях потоков запросов 43
2.2.2. Моделирование циклических трасс 45
2.2.3. Моделирование трасс с равновероятным законом распределения объектов в потоке запросов 45
2.2.4. Моделирование трасс на базе закона распределения Зипфа 47
2.2.5. Моделирование трасс со стационарными и нестационарными потоками запросов 47
2.2.6. Реальные потоки запросов в исследованиях кэш-систем... 48
2.3. Математическая модель алгоритма кэширования 49
2.4. Основные алгоритмы кэширования 51
2.4.1. Оптимальный алгоритм LFD 52
2.4.2. Оптимальный алгоритм АО 54
2.4.3. Алгоритм NRU 56
2.4.4. Алгоритм FIFO 57
2.4.5. Алгоритм «вторая попытка» 59
2.4.6. Алгоритм «CLOCK» 61
2.4.7. Алгоритм LRU 62
2.4.8. Алгоритм «рабочий набор» 66
2.4.9. Алгоритм WSCIock 67
2.4.10. Алгоритм LFU 69
2.5. Классификация методов гибридизации алгоритмов кэширования в системах обработки информации 71
2.5.1. Гибридизация по методу основной / дополнительный 72
2.5.2. Последовательное включение алгоритмов 73
2.5.3. Гибридизация с помощью свертки рейтингов 76
2.5.4. Использование в гибридизации нечеткой логики 78
2.5.5. Гибридизация по способам хранения информации 82
2.6. Обзор прочих гибридных алгоритмов кэширования 85
2.7. Выводы по второй главе 86
Глава 3. Математическая модель метода гибридизации двух алгоритмов кэширования 90
3.1. Математическая модель гибридного алгоритма 90
3.2. Модель управляемого гибридного алгоритма 92
3.3. Метод стохастической гибридизации 93
3.4. Модель управления гибридной стохастической кэш-системой... 97
3.4.1. Число участков к=2 101
3.4.2. Число участков к=1 102
3.5. Метод обнаружения изменения закона распределения 102
3.6. Выводы по третьей главе 105
Глава 4. Экспериментальны исследования гибридных алгоритмов кэширования 106
4.1. Функциональная структура программного комплекса 106
4.1.1. Объектно-ориентированное конструирование функциональных блоков 108
4.1.2. Структура баз данных программного комплекса CacheEfficiency 110
4.1.3. Интерфейс Программного стенда и работа с ним 114
4.2. Результаты экспериментальных исследований 116
4.2.1. Сравнения гибридных алгоритмов LRFU и RRFU 116
4.2.2. Исследование гибридного алгоритма RRFU 119
4.2.3. Экспериментальное исследование модифицированного гибрида SRRFU... 123
4.2.4. Испытание эффективности гибрида SRRFU на реальной трассе 127
4.3. Выводы по четвертой главе 128
Заключение 129
- Основные архитектуры БД
- Основные определения и терминология систем кэширования информации
- Математическая модель гибридного алгоритма
- Структура баз данных программного комплекса CacheEfficiency
Введение к работе
Актуальность исследования. При обработке больших объёмов данных всегда возникает проблема обеспечения скорости доступа к ним. Поскольку СУБД работают с базами данных, размер которых значительно превышает объем доступной оперативной памяти, нет возможности поместить всю информацию из базы данных в оперативную память, и большая ее часть во время работы системы будет оставаться на внешних носителях (магнитных дисках). Практически единственным эффективным способом уменьшения количества обращений к дискам является буферизация данных в оперативной памяти, или так называемое кэширование.
Кэширование — это универсальный метод повышения скорости доступа к данным, основанный на комбинации двух типов памяти, отличающихся временем доступа, объемом и стоимостью хранения данных. Наиболее часто используемая в данный период информация динамически копируется из «медленной, но большой» памяти в «быструю, но маленькую» кэш-память. В настоящее время к разработке новых алгоритмов и технологий кэширования проявляется очень большой интерес. В мире ежегодно издаётся сотни статей, посвященных алгоритмам кэширования. Повышению эффективности систем кэширования посвящены работы таких исследователей, как: Aho A.V., Denning P.J., Ullman J.D., Chen Y.C., Shedler G.S., Nilson R.A., Sharieh A., Belady L.A., Coffman E.G., Dasarathan D., Choi J., Lee D., Megiddo N., Modha D., Castro M., Adya A., Liskov В., Sabeghi M., Yaghmaee M.H., Subramanian R., Smaragdakis Y., Zhou Y., Вирт H., Кнут Д., Дейт К.Дж., Соколинский Л.Б., Кузнецов С.Д., Сущенко СП. и других.
Под оценкой эффективности работы кэш-системы обычно понимают вероятность нахождения запрошенного в потоке запросов объекта в кэшпамяти системы. Особенностью многопользовательских систем обработки информации является постоянно изменяющееся распределение объектов в потоке запросов. Следовательно, важнейшим качеством алгоритмов кэширования в системах хранения и обработки информации является его возможность адаптироваться к нестационарным потокам. При этом на стационарных потоках алгоритм должен обеспечивать эффективность, максимально близкую к теоретической верхней оценке. Одним из современных и интенсивно разрабатываемых в настоящее время методов решения данной проблемы является применение гибридных алгоритмов кэширования. Под гибридизацией понимают объединение двух и более базовых алгоритмов в единую систему. Именно гибридизация в системах кэширования является эффективным способом использования темпов роста производительности процессоров для компенсации отставания темпов роста скорости доступа к памяти.
Эти обстоятельства делают актуальным теоретическое и практическое исследование применения методов гибридизации для повышения эффективности кэш-систем в системах обработки и хранения информации.
Целью диссертационного исследования является разработка и исследование метода гибридизации алгоритмов кэширования в системах обработки и хранения информация.
Для достижения данной цели необходимо решить следующие основные задачи:
1) проанализировать существующие алгоритмы кэширования и возможности их применения в информационных системах;
2) исследовать и классифицировать существующие методы гибридизации алгоритмов кэширования;
3) разработать универсальный метод комбинирования разнородных алгоритмов кэширования объектов в информационных системах;
4) разработать off-line алгоритм управления гибридными алгоритмами кэширования в информационных системах;
5) разработать программные средства для экспериментального исследования эффективности гибридных алгоритмов кэширования в системах обработки и хранения информации. Новые научные результаты диссертационной работы:
1. Метод стохастической гибридизации алгоритмов кэширования, основанный на случайном смешивании стратегий, который, в отличие от существующих методов, позволяет получать гибридные алгоритмы на основе любого количества произвольных базовых алгоритмов.
2. Алгоритм адаптивного управления стохастическим гибридом RRFU, базирующимся на двух стратегиях кэширования LRU и LFU, который позволяет увеличить частоту кэш-попаданий для нестационарных трасс, полученных на базе закона распределения Зипфа "80-20", в среднем на 10% и с вероятностью 0,95 - не менее чем на 8%.
3. Метод обнаружения изменения закона распределения вероятности появления объектов в запросах к системам обработки информации с использованием меры Махалонобиса (DCD - Detection of Changes in Distribution), применение которого в алгоритме RRFU позволило разработать новый гибрид SRRFU, обеспечивающий на нестационарных трассах, полученных на базе закона распределения Зипфа "80-20", увеличение частоты кэш-попаданий не менее чем на 12% с уровнем значимости 0,95.
Методы исследования. Для решения поставленных в диссертации задач использовались методы теории информационных систем и систем БД, методы системного анализа, математического моделирования, методы теории вероятностей и математической статистики, а так же методы математического программирования.
Практическая значимость диссертационной работы определяется несколькими составляющими:
1) стохастическая гибридизация алгоритмов кэширования позволяет разрабатывать гибридные алгоритмы на основе любого количества произвольных базовых алгоритмов с целью повышения эффективности использования кэш-памяти и, следовательно, повышения производительности систем обработки и хранения информации;
2) областью применения стохастической гибридизации могут быть не только кэш-системы информационных систем хранения и обработки информации, но и все уровни кэш-памяти любых микропроцессорных систем, так как она просто реализуется, в том числе и аппаратно;
3) зарегистрированный в отраслевом фонде алгоритмов и программ (ОФАП) "Программный стенд для исследования алгоритмов кэширования" позволяет исследовать базовые и гибридные алгоритмы кэширования при различных потоках запросов к системам обработки и хранения информации;
4) предложенный метод сокращения времени расчёта значения управляющего параметра стохастического гибридного алгоритма, основанный на обнаружении изменения закона распределения вероятности появления объектов в запросах к системам обработки информации с использованием меры Махалонобиса, позволяет увеличить вероятность кэш-попаданий и может быть использован для модификации известных систем кэширования;
5) работа является хорошим практическим приложением к учебному процессу, так как предложенные решения позволяют изучить и применять на практике идеи теории информационных систем и систем БД, системного анализа, теории вероятностей, что необходимо при изучении дисциплин «Базы данных» и «Системное программирование».
Апробация диссертационной работы. Основные результаты диссертационной работы получили апробацию на следующих международных конференциях:
на XX Международной научной конференции "Математические методы в технике и технологиях" (ММТТ-20), ЯГТУ, Ярославль, 2007;
на XXI Международной научной конференции "Математические методы в технике и технологиях" (ММТТ-21), СГТУ, Саратов, 2008;
на XXII Международной научной конференции "Математические методы в технике и технологиях" (ММТТ-22), ДГТУ, Ростов-на-Дону, 2008;
V Spring young researchers1 colloquium on database and information systems (SYRCoDIS V), Saint-Petersburg, 2008;
на I международном научно-методическом симпозиуме «Современные проблемы многоуровневого образования» (Дивноморск, 2006);
на II международном научно-методическом симпозиуме «Современные проблемы многоуровневого образования» (Дивноморск, 2007); на III международном научно-методическом симпозиуме «Современные проблемы многоуровневого образования» (Дивноморск, 2008);
Промежуточные материалы диссертационных исследований
докладывались на ежегодных научно-технических конференциях Донского государственного технического университета.
Публикации. По теме диссертационного исследования опубликовано 10 печатных работ (одна в издании, включенном в перечень ВАК), в которых отражены его основные результаты.
Структура и объём работы. Диссертация состоит из введения, 4 глав, заключения, списка литературы и 6 приложений. Основная часть работы изложена на 140 страницах машинописного текста, 38 рисунках, 18 таблицах.
В первой главе рассмотрены особенности кэширования в системах обработки и хранения информации. Подробно рассмотрены особенности кэширования информации в СУБД с файл-серверной архитектурой и с архитектурой клиент-сервер. Отмечено, что исследования рациональных методов кэширования могут быть внедрены прикладными программистами в системы кэширования СУБД и Web-системы. Это обусловлено открытостью систем кэширования в архитектуре клиент - сервер и Web-системах. Многоуровневость систем кэширования предоставляет дополнительные возможности внедрения современных методов повышения скорости доступа к информации даже на уровне прикладных программистов.
Во второй главе приводятся основные понятия, терминология и модели, связанные с проектированием и исследованием систем кэширования. Вводится понятие объекта кэширования как неделимую, с точки зрения системы кэширования, порцию информации. Приведена математическая модель алгоритма кэширования, взятая из работ Aho A.V., Denning P.J., Ullman J.D. и несколько уточненная в настоящей работе.
Рассмотрены особенности известных алгоритмов кэширования. Для большинства основных алгоритмов в работе удалось построить математические модели, которые были использованы в экспериментальных исследованиях.
Последняя часть второй главы посвящается обзору и классификации известных методов гибридизации алгоритмов кэширования в системах обработки и хранения информации. Идея рассматривать работу кэш-систему как сложный и неоднородный процесс и использовать для управления этой системой гибридные методы не нова, однако в открытой литературе отсутствует система классификации методов гибридизации алгоритмов кэширования.
В третьей главе приведена математическая модель гибридного алгоритма на примере гибридизации двух базовых алгоритмов и математической модель метода адаптивного управления стохастическим гибридным алгоритмом.
Рассмотрена возможность применения метрики Махалонобиса для обнаружения изменения закона распределения вероятности появления объектов информационной системы в потоке запросов к кэш системе с целью модификации адаптивных систем кэширования. Предложенный метод модификации назван DCD.
В четвертой главе приведено описание программного стенда, который применялся для экспериментальных исследований гибридных алгоритмов, разработанных с помощью предложенного метода стохастической гибридизации. Кроме реализации предложенных гибридов в ПО стенда реализованы алгоритмы кэширования и распространённые гибридные алгоритмы, математические модели которых разработаны в настоящей диссертации. Модульная структура стенда позволяет моделировать и исследовать различные алгоритмы кэширования, производить статистическую обработку результатов экспериментов. Предусмотрена возможность экспорта результатов испытаний для последующей их обработки с помощью математических пакетов программ.
Далее приведены сравнительные испытания разработанных гибридных алгоритмов.
В заключении подводятся итоги диссертационного исследования.
Основные архитектуры БД
В настоящей работе рассматриваются возможности повышения эффективности алгоритмов применительно к системам баз данных и Web-системам. Именно для этих областей вполне реально разработать и внедрить новые идеи в алгоритмы кэширования. Это обусловлено открытостью для прикладных программистов механизмов кэширования в распространенных СУБД, таких, как ORACLE и возможностью реализации новых идей в поисковых Web-системах. Аппаратная реализация новых алгоритмов для использования в устройствах микроэлектроники требует сложного технологического оборудования и под силу лишь крупным компаниям. Это не значит, что новые идеи не могут быть реализованы, например, в процессорах. Речь идёт лишь о наших приоритетных интересах и технологических возможностях.
На реализацию систем кэширования оказывает влияние, прежде всего, архитектура информационных систем. База данных в общем случае состоит из следующих компонентов [97]: - данных; - программного обеспечения; - аппаратного обеспечения; - пользователей. Рассмотрим вкратце названные компоненты и некоторые связанные с ними понятия. База данных (БД) представляет собой совокупность специальным образом организованных данных, хранимых в памяти вычислительной системы. Данные, хранимые в БД, имеют определенную логическую структуру, которую называют моделью представления данных. К основным моделям представления данных (моделям данных) относятся следующие: - иерархическая; - сетевая; - реляционная; - постреляционная; - многомерная; - объектно-ориентированная. В теории баз данных первые три модели являются основными. Пользовательские данные отображают состояние объектов и их взаимосвязи в рассматриваемой предметной области. Системные данные предназначены для описания структуры пользовательских данных и для организации нормального функционирования баз данных. Обычно данные, хранящиеся в БД, называются постоянными (хотя они не долго могут оставаться такими). «Постоянными» они называются по отношению к другим данным: промежуточным, входным, выходным. Входные данные — это информация, передаваемая системе (обычно с терминала или рабочей станции). Такая информация может стать причиной изменения постоянных данных. Выходные данные - это сообщения и результаты, выдаваемые системой Ясно, что различие между видами данных нельзя назвать четкими, они определяются на интуитивном уровне. Из программного обеспечения следует выделить, прежде всего: - системы управления базами данных; - приложения: - утилиты: - средства разработки приложений: - средства разработки баз данных. Система управления базами данных (СУБД) - это комплекс языковых, математических и программных средств, предназначенных для централизованного создания, ведения и совместного использования БД многими пользователями. Обычно СУБД различают по используемой модели данных. Так СУБД, основанные на использовании реляционной модели данных, называют реляционными СУБД. Количество современных систем управления базами данных исчисляется тысячами [119]. Приложение — программа или комплекс программ, обеспечивающих автоматизацию обработки информации для прикладной задачи с использованием базы данных. Приложения для работы с базами данных могут создаваться в среде и вне среды СУБД. Приложения, созданные в среде СУБД, как правило, могут работать только под управлением этой СУБД (например, приложения Access). Вне среды СУБД приложения создаются с помощью системы программирования, имеющей средства доступа к базе данных. Примерами таких систем являются: Delphi или C++ Builder. Приложения, разработанные в среде СУБД, часто называют приложениями СУБД, а приложения, разработанные вне СУБД,- внешними приложениями. Общим у всех приложений является то, что они используют предоставляемый СУБД интерфейс доступа к информации в БД. Утилиты - это программные средства работы с БД специального назначения. В некоторых случаях утилиты используют прямой доступ к информации в БД в обход предоставляемого СУБД интерфейса. Средства разработки приложений и баз данных представляют собой программные обеспечения, позволяющие автоматизировать процессы разработки. Аппаратное обеспечение (вычислительная система) представляет собой совокупность взаимосвязанных и согласованно действующих ЭВМ или процессоров и других устройств, обеспечивающих автоматизацию процессов приема, обработки и выдачи информации пользователям. Поскольку основными функциями базы данных являются хранение и обработка данных, то используемая вычислительная система, наряду с приемлемой мощностью центральных процессоров (ЦП), должна иметь достаточный объем оперативной и внешней памяти прямого доступа.
Основные определения и терминология систем кэширования информации
Кэширование - это универсальный метод, который пригоден для ускорения доступа к оперативной памяти, к диску и к другим видам запоминающих устройств [117]. Память вычислительной машины представляет собой иерархию запоминающих устройств (ЗУ), отличающихся средним временем доступа к данным, объемом и стоимостью хранения одного бита (рис.2.1). Фундаментом этой пирамиды запоминающих устройств, служит внешняя память, как правило, представляемая жестким диском. Она имеет большой объем (десятки и сотни гигабайт), но скорость доступа к данным является невысокой. Время доступа к диску измеряется миллисекундами. На следующем уровне располагается более быстродействующая (время доступа равно примерно 10-20 наносекундам) и менее объемная (от десятков мегабайт до нескольких гигабайт) оперативная память [32,33], реализуемая на относительно медленной динамической памяти DRAM. Следует отметить, что все перечисленные характеристики ЗУ быстро изменяются по мере совершенствования вычислительной аппаратуры, но в данном случае важны не абсолютные значения времени доступа или объема памяти, а их соотношение для разных типов запоминающих устройств. Для хранения данных, к которым необходимо обеспечить быстрый доступ, используются компактные быстродействующие запоминающие устройства на основе статической памяти SRAM, объем которых составляет от нескольких десятков до нескольких сотен килобайт, а время доступа к данным обычно не превышает 8 не. Верхушку в этой пирамиде составляют внутренние регистры процессора, которые также могут быть использованы для промежуточного хранения данных. Общий объем регистров составляет несколько десятков байт, а время доступа определяется быстродействием процессора, и равно в настоящее время примерно 2-3 не.
Если кэширование применяется для уменьшения среднего времени доступа к оперативной памяти, то в качестве кэша используют быстродействующую статическую память. Если кэширование используется системой ввода-вывода для ускорения доступа к данным, хранящимся на диске, то в этом случае роль кэш-памяти выполняют буферы в оперативной памяти, в которых оседают наиболее активно используемые данные. Виртуальную память также можно считать одним из вариантов реализации принципа кэширования данных, при котором оперативная память выступает в роли кэша по отношению к внешней памяти - жесткому диску. В этом случае кэширование используется не для того, чтобы уменьшить время доступа к данным, а для того, чтобы заставить диск частично подменить оперативную память за счет перемещения временно неиспользуемого кода и данных на диск с целью освобождения места для активных процессов [110].
Зачастую содержимое кэш-памяти представляет собой совокупность записей обо всех загруженных в нее элементах данных из основной памяти. Каждая запись об элементе данных включает в себя: - значение элемента данных; - адрес, который этот элемент данных имеет в основной памяти; - дополнительную информацию, которая используется для реализации алгоритма замещения данных в кэше и обычно включает признак модификации и признак действительности данных. В современном программировании кэширование находит широкое применение как в системах хранения памяти, базах данных, Web серверах, микропрограммных средствах, процессорах и файловых системах, так и в дисководах, разнообразных независимых диск - контроллерах и операционных системах. В многоуровневой иерархии памяти кэш является вспомогательной системой хранения данных, но стоит дороже. Таким образом, стоимость нередко становится причиной ограничения размера кэш-памяти до некоторой доли вспомогательной памяти. Кэш и вспомогательная память оперируют однородными элементами, например, блоками или объектами. Понятие "Объект" все чаще используется в СУБД, теоретические основы которых находятся под давлением "объектной" парадигмы, развиваемой в ООП. Некоторые концепции этой парадигмы легко переносятся в базы данных [58]. Это, прежде всего, такие понятия, как: класс, объект, метод, наследование и т.д., мало того, многие из этих понятий использовались, например, в ER-моделях задолго до оформления ООП как целостной концепции программирования.
Математическая модель гибридного алгоритма
Очень интересный вид гибридизации получается на основе различных единиц кэширования. Это новая технология возникла для управления кэшем клиентов в ООСУБД или в системах хранения объектов [58]. Примером гибрида такого класса служит алгоритм НАС (Hybrid Adaptive Caching). Это гибрид между кэшированием страницами и объектами, комбинирующий их достоинства и исключающий их недостатки. Страничный алгоритм кэширования обеспечивает низкую вероятность промахов и эффективно работает только при хорошей пространственной локальности. При плохой локальности каждая страница содержит лишь малый процент требуемых, так называемых «горячих» объектов. Алгоритм НАС адаптивный, и когда локальность объектов в страницах хорошая, поведение алгоритма совпадает с поведением страничного алгоритма, а при плохой локальности поведение алгоритма совпадает с объектным алгоритмом. В распределенных системах обработки и хранения информации серверы поддерживают систему доступа к информации через приложения, запущенные на стороне клиентов [8,9,44,48, 86]. Как известно, эти системы кэшируют требуемую информацию на стороне клиента, чтобы обеспечить минимальные задержки при обращении к объектам. Адаптивное гибридное кэширование является новой технологией, и алгоритм НАС, комбинирующий кэширование страниц и объектов, снижает процент кэш-промахов на клиенте. Этот алгоритм реализован специально для систем хранения и обработки информации, но может быть использован и в других системах, например, в файловых системах. Большинство существующих систем управления кэш-памятью клиента применяет алгоритм кэширования именно страницами[44,69,86]. При этом, когда происходит кэш-промах, клиент удаляет страницу-жертву из своего кэша и получает от сервера страницу, содержащую нулшые ему объекты. Кэширование страницами распространено благодаря простоте в управлении страницами с фиксированными размерами. Низкая вероятность кэш-промахов может быть обусловлена эффективной кластеризацией объектов между страницами. Получение эффективной кластеризации, обеспечивающей высокую производительность кэш-системы для всех запросов к информационной системе - достаточно сложная задача [15,19,78,116]. Во время эксплуатации параметры распределения запросов могут изменяться, и производительность системы упадёт. Эффективные алгоритмы рекластеризации имеют высокую трудоёмкость [78,116]. Каждая страница содержит горячие объекты (hot), к которым произойдут обращения в ближайшем будущем и холодные (Cold) объекты, к которым не будет обращений в ближайшее время. Неэффективная кластеризация приводит к снижению процента заполнения страницы горячими объектами. Пространство кэша у клиента заполняется холодными объектами, от которых нет никакой пользы. Эффективность, очевидно, можно повысить, увеличив процент горячих объектов [35,116].
Системы, поддерживающие объектное кэширование (Object-caching systems) [10,42,43,48,65,85] позволяют клиенту кэшировать горячие объекты без кэширования страниц, к которым они принадлежат. Таким образом, кэширования объектами уменьшает вероятность кэш-промахов по отношению к системам кэширования страницами с неэффективной кластеризацией. Кэширование объектами имеет два основных недостатка: во-первых, объекты имеют переменный размер, а не фиксированный как страницы, что усложняет доступ к объектам в кэш-памяти и, во-вторых, количество объектов намного большее, чем страниц. Их поддержка и статистический учет требуют очень больших ресурсов.
Понятие такой двойной (дуальной) буферизации (Dual buffering) рождалось в результате бурного развития и исследования объектных кэш-систем. В результате было предложено статически разделить клиентский кэш на кэш-объектов и кэш-страниц. Эта технология обеспечивала более низкую вероятность кэш-промахов, чем у предыдущих систем кэширования объектами или страницами, когда коэффициент разделение настраивается вручную в зависимости от поведения самой системы и закона распределения обращений к объектам.
С появлением алгоритма НАС, как утверждают авторы [8,9,44,48,86] была предложена первая технология, предлагающая адекватное решение проблем настройки таких алгоритмов. Алгоритм НАС адаптивно управляет разделением кэша клиента так, чтобы обеспечить максимальную частоту кэш-попаданий. O Toole и Shrira представили имитационную модель, с помощью которой были произведены все исследования адаптивной системы кэширования на базе алгоритма НАС [63].
Структура баз данных программного комплекса CacheEfficiency
Будем считать, что если D S, то на участке со1к произошло изменение закона распределения объектов в потоке запросов и необходимо включить механизм адаптации гибридного алгоритма. В противном случае включать механизм адаптации нет необходимости. Величина 8 может быть получена с помощью предварительного обучения системы.
После введенных обозначений приведём алгоритм распознавания изменения закона появления объектов в потоке запросов. многопользовательскому режиму работы информационной системы, приведены в четвертой главе и показывают что разработанный метод сокращения времени расчёта значения управляющего параметра стохастического гибридного алгоритма, основанный на обнаружении изменения закона распределения вероятности появления объектов в запросах к системам обработки информации с использованием меры Махалонобиса, позволяет увеличить вероятность кэш-попаданий для предложенного гибридного алгоритма. 3.6. Выводы по третьей главе Полученные в настоящей главе модели гибридного алгоритма и управляемого гибридного алгоритма позволили сосредоточится на формальной стороне гибридизации и теоретически обосновать метод стохастической гибридизации, который позволяет получать гибриды любого количества произвольных алгоритмов кэширования. Разработанная математическая модель гибрида, полученного методом стохастической гибридизации, является формализованной основой алгоритмов работы любых гибридов, полученных данным методом. Обосновано, что задача управления таким алгоритмом относится к классу задач стохастического нелинейного событийного программирования при отсутствии аналитического выражения для критерия, в качестве которого выбрана частота кэш-попаданий на участке трассы. Рассмотренные возможности применения метрики Махалонобиса для обнаружения изменения закона распределения вероятности появления объектов информационной системы в потоке запросов к кэш системе. Основной задачей настоящей главы является определение требований к программному средству и реализация необходимой функциональности в виде программного комплекса. Массовая постановка экспериментов требует наличия удобного автоматического программного средства для их проведения, оценки и анализа полученных результатов. Перед перечислением технических требований к системе, опишем используемые понятия: Опыт — единица оценки работы алгоритмов при конкретных условиях задачи, которое включает в себя: параметры задачи, матрицу трассы, набор алгоритмов со своими индивидуальными настройками, критерий оптимизации. Матрица трассы — матрица размера пхт, заполненная с помощью внутреннего модуля генератор трасс. ГСТ - генератор случайных трасс, позволяющий получать случайные трассы, с различными законами распределения появления объектов в запросах. Набор опытов - массив опытов (групп опытов) с различными условиями задач, созданный с определенным набором алгоритмов кэширования. Группа опытов - массив опытов, объединенных по определенному набору параметров. Набор алгоритмов — список алгоритмов связанных с конкретной задачей и сохраняющий свои параметры во время обработки всего набора опытов. Критерий оптимизации - частота кэш-попаданий в опытах, в большинстве случаев обозначается как HitMax. Результат - решение задачи кэширования, полученное одним из алгоритмов и имеющим оценку по заданному критерию. 107 Требования к системе: - ПО должно обеспечивать массовую постановку эксперимента, кол-во опытов более 10000, не требуя при этом больших объемов оперативной памяти, места на жестком диске, и процессорных ресурсов; - ПО должно функционировать на обычных рабочих станциях, не требуя для расчета суперкомпьютеров; - должны быть реализованы основные классы базовых алгоритмов, LRU, LFU, FIFO, Clock, Random, в том числе и различные гибридных алгоритмов LRFU, ARC, 2Q; - система должна статистически обрабатывать результаты и выдавать их в развернутом виде по каждому алгоритмы в разрезе различных параметров задачи; - необходима возможность сохранения в постоянную память набора опытов с решениями и выбранными алгоритмами для последующего анализа данных.
