Электронная библиотека Веда
Цели библиотеки
Скачать бесплатно
Доставка литературы
Доставка диссертаций
Размещение литературы
Контактные данные
Я ищу:
Библиотечный каталог российских и украинских диссертаций

Вы находитесь:
Диссертационные работы России
Технические науки
Системный анализ, управление и обработка информации

Диссертационная работа:

Аль-Згуль Мосаб Бассам Юсеф. Гибридные алгоритмы кэширования для систем обработки и хранения информации : диссертация ... кандидата технических наук : 05.13.01 / Аль-Згуль Мосаб Бассам Юсеф; [Место защиты: Дон. гос. техн. ун-т].- Ростов-на-Дону, 2009.- 151 с.: ил. РГБ ОД, 61 09-5/2172

смотреть содержание
смотреть введение
Содержание к работе:

ВВЕДЕНИЕ 5

Глава 1. ОСОБЕННОСТИ КЭШИРОВАНИЯ В ИНФОРМАЦИОННЫХ СИСТЕМАХ 11

1.1. Кэширование информации в базах данных 11

1.1.1. Основные архитектуры БД 111

1.1.2. Кэширование в СУБД с файл-серверной архитектурой... 15

1.1.3. Кэширование в архитектуре клиент-сервер 16

1.1.4. Кэширование в объектно-ориентированных СУБД

1.2. Кэширование информации в Web-системах 25

1.3. Выводы по первой главе 31

Глава 2. МОДЕЛИ И МЕТОДЫ КЭШИРОВАНИЯ ИНФОРМАЦИИ 32

2.1. Основные определения и терминология систем кэширования информации 32

2.2. Математические модели потоков запросов

2.2.1. Основные определения, термины и допущения в моделях потоков запросов 43

2.2.2. Моделирование циклических трасс 45

2.2.3. Моделирование трасс с равновероятным законом распределения объектов в потоке запросов 45

2.2.4. Моделирование трасс на базе закона распределения Зипфа 47

2.2.5. Моделирование трасс со стационарными и нестационарными потоками запросов 47

2.2.6. Реальные потоки запросов в исследованиях кэш-систем...

2.3. Математическая модель алгоритма кэширования 49

2.4. Основные алгоритмы кэширования

2.4.1. Оптимальный алгоритм LFD 52

2.4.2. Оптимальный алгоритм АО

2.4.3. Алгоритм NRU 56

2.4.4. Алгоритм FIFO 57

2.4.5. Алгоритм «вторая попытка» 59

2.4.6. Алгоритм «CLOCK» 61

2.4.7. Алгоритм LRU

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. Гибридизация по способам хранения информации

2.6. Обзор прочих гибридных алгоритмов кэширования 85

2.7. Выводы по второй главе 86

Глава 3. МАТЕМАТИЧЕСКАЯ МОДЕЛЬ МЕТОДА ГИБРИДИЗАЦИИ ДВУХ АЛГОРИТМОВ КЭШИРОВАНИЯ 90

3.1. Математическая модель гибридного алгоритма 90

3.2. Модель управляемого гибридного алгоритма 92

3.3. Метод стохастической гибридизации 93

3.4. Модель управления гибридной стохастической кэш-системой...

3.4.1. Число участков к=2 101

3.4.2. Число участков к=1 1

3.5. Метод обнаружения изменения закона распределения 102

3.6. Выводы по третьей главе 105

Глава 4. ЭКСПЕРИМЕНТАЛЬНЫ ИССЛЕДОВАНИЯ ГИБРИДНЫХ АЛГОРИТМОВ КЭШИРОВАНИЯ 106

4.1. Функциональная структура программного комплекса 106

4.1.1. Объектно-ориентированное конструирование функциональных блоков 108

4.1.2. Структура баз данных программного комплекса CacheEfficiency ПО

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

СПИСОК ИСПОЛЬЗУЕМЫХ ИСТОЧНИКОВ 130

ПРИЛОЖЕНИЯ 141

Приложение А. Исходный код базовых классов 141

Приложение Б. Результаты испытаний алгоритма SRRFU на нестационарной трассе (поток запросов по равно вероятному закону)...

Приложение В. Результаты испытаний алгоритма SRRFU на нестационарной трассе (поток запросов по закону Зипфа "70-30")

Приложение Г. Результаты испытаний алгоритма SRRFU на нестационарной трассе (поток запросов по закону Зипфа "80-20")

Приложение Д. Свидетельства об официальной регистрации 149

Приложение Е. Акт внедрения 1  

Введение к работе:

Актуальность исследования. При обработке больших объёмов данных всегда возникает проблема обеспечения скорости доступа к ним. Кэширование — это универсальный метод повышения скорости доступа к данным, основанный на комбинации двух типов памяти, отличающихся временем доступа, объемом и стоимостью хранения данных. Наиболее часто используемая в данный период информация динамически копируется из «медленной, но большой» памяти в «быструю, но маленькую» кэш-память. В настоящее время к разработке новых алгоритмов и технологий кэширования проявляется очень большой интерес. Повышению эффективности систем кэширования посвящены работы таких исследователей, как: Aho A.V., Denning P.J., Ullman ID., Chen Y.C., Shedler G.S., Nilson R.A., Sharieh A., Belady LA., Coffman E.G., Dasarathan D., Choi J., Lee D., Megiddo N., Modha D., Castro M., Ad/a A., Liskov В., Sabeghi M., Yaghmaee M.H., Subramanian R., Smaragdakis Y., Zhou Y., Вирт H., Кнут Д., Дейт К.Дж., Соколинский Л.В., Кузнецов С.Д., Сущенко СП. и других.

Под оценкой эффективности работы кэш-системы обычно понимают вероятность нахождения запрошенного в потоке запросов объекта в кэшпамяти. Особенностью многопользовательских систем обработки информации является постоянно изменяющееся распределение объектов в потоке запросов. Следовательно, важнейшим качеством алгоритмов кэширования в системах хранения и обработки информации является их возможность адаптироваться к нестационарным потокам. При этом на стационарных потоках алгоритм должен обеспечивать эффективность, максимально близкую к теоретической верхней оценке. В настоящее время для достижения высокой эффективности кэш-систем как на стационарных, так и на нестационарных потоках запросов все чаще используют гибридные системы. Под гибридизацией понимают объединение двух и более базовых алгоритмов в единую систему. Именно гибридизация систем кэширования является эффективным способом использования растущей производительности процессоров для компенсации отставания темпов роста скорости доступа к памяти.

Эти обстоятельства делают актуальным теоретическое и практическое исследование применения методов гибридизации для повышения эффективности кэш-системы в системах обработки и хранения информации.

Целью диссертационного исследования является разработка и исследование метода гибридизации алгоритмов кэширования в системах обработки и хранения информации.

Для достижения данной цели необходимо решить следующие задачи:

  1. проанализировать существующие алгоритмы кэширования и возможности их применения в информационных системах;

  2. исследовать и классифицировать существующие методы гибридизации алгоритмов кэширования;

  1. разработать универсальный, метод комбинирования разнородных алгоритмов кэширования объектов в информационных системах;

  2. разработать off-line алгоритм управления гибридными алгоритмами кэширования в информационных системах;

  3. разработать программные средства для экспериментального исследования эффективности гибридных алгоритмов кэширования в системах обработки и хранения информации.

Методы исследования..Для решения поставленных в диссертации задач использовались методы теории информационных систем и систем БД, методы системного анализа, математического моделирования, методы теорий вероятностей и математической статистики, а также методы математического программирования. '-Новые научные результаты, полученные в диссертации:

  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.

Практическая значимость диссертационной работы заключается в.следующемт 'г''"'"' ,; v.----'--

стохастическая гибридизация алгоритмов кэширования позволяет разрабатывать гибридные алгоритмы на основе любого количества произвольных базовых алгоритмов с целью повышения эффективности использования кэш-памяти и, следовательно, повышения производительности систем обработки и хранения информации;

^. -2) областью применения стохастической гибридизации могут быть не только, кэш-системы информационных систем хранения и обработки информации, но и все уровни кэш-памяти любых микропроцессорных систем, так как она просто реализуется, в том числе и аппаратно. .„

3) зарегистрированный в отраслевом фонде алгоритмов и программ
(ОФАП)-"Программный стенд для исследования алгоритмов кэширрвания";
позволяет исследовать базовые и гибридные алгоритмы кэширования
при различных потоках запросов к системам обработки.и, хранения ин-.:
формации; " " " ;'"'."" '.'." '..,'".'.', :.., ,:

  1. метод DCD может быть использован для модификации известных систем кэширования с целью повышения их эффективности;

  2. работа является хорошим практическим приложением к учебному процессу, так как предложенные решения позволяют изучить и применять на практике идеи теории информационных систем и систем БД, системного анализа, теории вероятностей, что необходимо при изучении дисциплин «Базы данных» и «Системное программирование».

Апробация диссертационной работы. Материалы диссертационной работы апробировались на международной научной конференции (МНК) "Математические методы в технике и технологиях": XX МНК -ММТТ-20 (ЯГТУ, Ярославль, 2007); XXI МНК - ММТТ-2Г (СГТУ, Саратов, 2008); XXII МНК - ММТТ-22 (ДГТУ, Ростов-на-Дону, 2008). V Spring young researchers' colloquium on database and information systems (SYRCoDIS V), Saint-Petersburg, 2008. На международных научно-методических симпозиумах "Современные проблемы многоуровневого образования" (Дивно-морск - 2006, Дивноморск - 2007, Дивноморск - 2008). Промежуточные материалы диссертационных исследований докладывались на ежегодных научно-технических конференциях Донского государственного технического университета.

Публикации. Всего по теме диссертации опубликовано 10 печатных работ (одна из них - в издании, включенном в перечень ВАК), в которых отражены основные результаты диссертации.


© Научная электронная библиотека «Веда», 2003-2013.
info@lib.ua-ru.net