автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.01, диссертация на тему:Гибридные алгоритмы кэширования для систем обработки и хранения информации

На правах рукописи

АЛЬ-ЗГУЛЬ МОСАБ БАССАМ ЮСЕФ

ГИБРИДНЫЕ АЛГОРИТМЫ

КЭШИРОВАНИЯ ДЛЯ СИСТЕМ ОБРАБОТКИ И ХРАНЕНИЯ ИНФОРМАЦИИ

Специальность 05.13.01 - Системный анализ, управление и обработка информации (в машиностроении)

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

Ростов-на-Дону 2009

003471725

Работа выполнена в Государственном образовательном учреждении высшего профессионального образования «Донской государственный технический университет» на кафедре «Программное обеспечение вычислительной техники и автоматизированных систем».

Научный руководитель: Официальные оппоненты:

Ведущая организация:

«.т.н., доцент

Михаил Васильевич Гранков

д.т.н., профессор • Виктор Анатольевич Иванов

к.т.н., доцент

Валерий Валерьевич Хашковскш

ФГУ «Информационно-методический центр анализа» Федеральной службы по надзору в сфере образования и науки.

Защита состоится « 28 » мая 2009 г. в « И » часов на заседании диссертационного совета Д-212.058.04 Донского государственного технического университета по адресу:

344000, г. Ростов-на-Дону, пл. Гагарина 1, ДГТУ, ауд. № 252 .

С диссертацией можно ознакомиться в научной библиотеке Донского государственного технического университета.

Автореферат разослан « 24 » апреля 2009 года. Отзывы на автореферат в двух экземплярах, заверенные гербовой печатью, просим направлять в адрес совета.

Ученый секретарь диссертационного совета

к. т. н., доцент Н.С. Могилевская

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность исследования. При обработке больших объёмов данных всегда возникает проблема обеспечения скорости доступа к ним. Кэширование — это универсальный метод повышения скорости доступа к данным, основанный на комбинации двух типов памяти, отличающихся временем доступа, объемом и стоимостью хранения данных. Наиболее часто используемая в данный период информация динамически копируется из «медленной, но большой» памяти в «быструю, но маленькую» кэш-память. В настоящее время к разработке новых алгоритмов и технологий кэширования проявляется очень большой интерес. Повышению эффективности систем кэширования посвящены работы таких исследователей, как: 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., Ad/a 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.

Практическая значимость диссертационной работы заключается^, следующем: V. ..

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

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

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

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

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

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

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

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ

Во введении обосновывается актуальность темы диссертационной работы, приводятся формулировки цели и задач исследований, отмечаются полученные новые научные результаты, их практическая ценность, реализация, апробация и структура диссертации.

В первой главе рассмотрены особенности кэширования в системах обработки и хранения информации.

Подробно рассмотрены возможности кэширования информации в СУБД с файл-серверной архитектурой и с архитектурой клиент-сервер.

Отмечено, что результаты исследований рациональных методов кэширования могут быть внедрены прикладными программистами в системы кэширования СУБД и Web-системы, что обусловлено открытостью таких систем.

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

Во второй главе приводятся основные понятия, терминология и модели, связанные с проектированием и исследованием систем кэширования. Отмечено, что алгоритм замены данных в кэш-памяти существенно влияет на ее эффективность. Если в системе имеется основное запоминающее устройство со средним временем доступа /, и кэш-память,

б

имеющая время доступа 1г{/г</,), при этом р - вероятность кэш-

попадания, то среднее время доступа к данным в системе с кэш-памятью по формуле полной вероятности равно:

/ = /,-(!-+ = )•/> + /,. U)

Из (1) видно, что среднее время доступа к данным линейно зависит от вероятности кэш-попаданий. Следовательно, кэширование имеет смысл только при высокой вероятности кэш-попаданий.

Далее во второй главе рассмотрены особенности известных алгоритмов кэширования. Для большинства основных алгоритмов в работе удалось построить математические модели, которые были использованы в экспериментальных исследованиях. Важную роль в анализе эффективности алгоритмов кэширования играют так называемые оптимальные алгоритмы LFD и АО. Эти алгоритмы практически нереализуемы, однако позволяют получить верхние оценки вероятности кэш-попаданий для систем кэш-памяти и, следовательно, оценить эффективность работы кэш-систем. Наиболее близким по эффективности к оптимальному алгоритму АО является алгоритм LFU, однако его недостатки не позволяют использовать этот алгоритм на нестационарных потоках запросов объектов. Наиболее распространенный алгоритм LRU эффективно использует временную локальность объектов в потоках запросов и имеет высокий процент кэш-попаданий на нестационарных трассах. Так как алгоритм далёк от алгоритма АО, то на стационарных трассах алгоритм LRU теоретически проигрывает алгоритму LFU в эффективности. Перспективным является использование комбинаций различных алгоритмов и, прежде всего, комбинации алгоритмов LRU и LFU. При обнаружении цикличности трассы повышение эффективности может быть достигнуто при использовании идей оптимального алгоритма LFD, так как для циклических трасс вполне реально прогнозировать дистанцию появления объектов из кэш-памяти на будущем участке трассы.

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

В настоящей работе выделены следующие способы объединения базовых алгоритмов гибридом:

1) основной/дополнительный алгоритмы кэширования;

2) использование явной свертки рейтингов объектов базовых алгоритмов;

3) последовательное включение базовых алгоритмов;

4) использование нечеткой логики;

5) гибридизация по способам хранения информации.

Гибридизация по методу основной/дополнительный обычно применяется в том случая, если основной алгоритм кэширования по вектору состояния управления не всегда может однозначно решить задачу выбора объекта-жертвы. Типичным примером такого гибрида можно считать алгоритм LFU, в котором как дополнительный используется алгоритм LRU. Как пример использования явной свертки рейтингов объектов от базовых алгоритмов в работе рассмотрен алгоритм LRFU. За счет оригинально подобранной свертки этот алгоритм позволяет менять степень влияния базовых алгоритмов, которыми являются алгоритмы LRU и LFU, на итоговый рейтинг каждого объекта из кэша. Особенностью алгоритма является возможность адаптации к изменению потока запросов. Недостатком алгоритма является высокая алгоритмическая сложность расчета свертки рейтингов.

Как пример последовательного включения базовых алгоритмов рассмотрен алгоритм ARC, который фактически реализует вариант простой аппаратной свертки рейтингов алгоритмов LRU и LFU. Алгоритм адаптируется к потоку запросов и показывает эффективность, превышающую эффективность LRU.

Примером использования нечёткой логики является алгоритм FPR. В этом алгоритме для каждого объекта из кэш-памяти регистрируется три параметра: новизна (ReferenceRecency), частота (ReferenceFrequency), дистанция обращений (ReuseDistance). Данный метод является реализацией незамкнутой системы управления кэшем, в которой регистрируются параметры входного потока запросов, и с помощью нечётких правил решается задача выбора жертвы. Эффективность принятых решений в данном алгоритме не контролируется.

Интересный вид гибридизации получается на основе различных единиц кэширования. Это новая технология возникла для управления кэшем клиентов в ООСУБД. Примером гибрида такого класса служит алгоритм НАС (Hybrid Adaptive Caching).

Из анализа предложенной системы классификации можно выделить следующие свойства рассмотренных гибридов:

1) гибридизация структур данных;

2) адаптивность к потоку запросов;

3) анализ входного потока запросов;

4) использование различных единиц памяти.

Связь свойств гибридов со способами гибридизации содержится в табл.1.

Таблица 1

Способ гибридизации Пример Свойство гибридов

1 2 3 4

1 LFU/LRU +

2 LRFU + +

3 ARC + +

4 FPR +

5 НАС +

В заключении констатируется, что:

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

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

• для уже существующих гибридов применение ещё одного уровня гибридизации с использованием еще одного базового алгоритма могло бы обеспечить получение новых положительных свойств;

• возможность управления степенью влияния базовых алгоритмов на итоговый рейтинг позволяет построить адаптивные к изменению потока запросов on и off-line алгоритмы;

положительные результаты, полученные с помощью как адаптивных алгоритмов (ARC, IRFU, НАС), так и незамкнутых гибридных систем, в которых анализируются параметры входного по отношению к кэш-системе потока запросов (FPR), позволяют надеяться, что использование анализа входного потока повысит эффективность адаптивных алгоритмов.

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

' /V = {1,2..;«}. (2)

В системе имеется кэш-система с множеством адресов кэш-памяти:

М - {1,2...»;} . ' .... . (3)

Кэш-система находится под воздействием потока а. запросов к объектам

■.:<a-(r„r^:,r„.:j-T), ■■ ; ' (4)

где е N - объект, запрошенный у кэш-системы в момент времени t.

Обозначим через Шт - множество подмножеств множества N объектов системы, которые могут быть расположены в кэш-памяти М ;

(5)

Пусть кэш-система при решении задачи о выборе жертвы может использовать два базовых алгоритма кэширования: А, и л,;

A =(Gr <7io>£ih.. -.....'...., ... (6)

- - (7)

где Q,, Q2 - множество состояний управления алгоритмов А[ и А2; qm, q20 - начальные состояния управления алгоритмов А и Аг; g,, g2 - отображения перехода алгоритмов Л, и А2, которые по состоянию кэш-памяти и соответствующим состояниям управления q, и q2 позволяют получить новое состояние кэш-памяти и новые состояния управления qu и q2i соответственно для алгоритмов А, и Аг.

g,--MmxQ,xN->mHxQ,; (8)

(<?,<7,,), если х с Л';

#,(5,д,,*) = ■{(£'-'{я} >9н)> если (9)

(£ и {л} \ {у}, д,,), если (х £ 5) л (¡^ = т) л (у е 5) л (у = (5, <7,));

(/,: 9Л„, х _> /V (10)

- отображение выбора жертвы по А,.

&:®1..х02хЛГ->ЙЙ.,х01; (И)

= саи л-«г5л|5'| <(12)

(.г*Л')л(|Л'| = ,„)лСе5)лО' = </г(5,<?,)); </2 : 9Л,„ х £>, -> N (13)

- отображение выбора жертвы по л,.

Гибридным алгоритмом А базовых алгоритмов Л, и А2 будем называть упорядоченное множество

Л = (£Ш><7,«.</2О-£Ь (Н)

где £ - отображение перехода гибридного алгоритма;

' ^'-.т^д^р.хм-ут^о^д,, (15)

При этом:

(З',,<7п.921) = (1б)

если х

ф\д„д2,х) =• ,<?„//,,), саш хй5л|5(<т; (17)

где л - объект, запрошенный у кэш-системы в момент ?; Л' - состояние кэш-памяти в момент /; </, - состояние управления алгоритма Л, в момент г; - состояние управления алгоритма Л2 в момент I; д„ -состояние управления алгоритма А, в момент (+1; д21 -состояние управления алгоритма л, в момент / +1; Я - отображение выбора жертвы;

«••9Л.Х0Х&-*//. (18)

Отображение Л по состоянию кэш-памяти и состояниям управления </, и алгоритмов л, и Л2 позволяет выбрать объект:жертву у из состояния кэш памяти 5. Из данной модели видно, что основная проблема гибридизации заключается в выборе отображения й, которое обеспечивает выбор жертвы, опираясь на состояния управления qi и q2 базовых алгоритмов А> и Аг. Для того чтобы управлять степенью влияния алго-

ритмов А1 и Лг на выбор жертвы, введем понятия нормированного управления. Пусть безразмерная переменная Ле[0,1] отражает степень влияния алгоритмов ах и аг на принятие решения о выборе жертвы отображением Д. Переменную X будем называть параметром управления степенью влиянии алгоритмов Л, и аг.

Если единичный отрезок [0,1] обозначить через /: / = [0,1], тогда я будет иметь вид

= (19)

Пусть при этом Я обладает следующими свойствами:

) = г/2(5,?2), (20)

Л(&?|.?2.1) = (21)

где и с/-, отображения (10) и (13).

В этом случае отображение перехода для гибрида а базовых алгоритмов а, и а2 это:

!;•.m,l|xQtxQгxIxN~><m,„xQ|xQ2, (22)

При этом в общем случае = g(S,q^,q1,X,x), где X - значение

параметра управления степенью влияния алгоритмов а1 и аг в момент времени /;

(£,<?,,,<7л) ,если

.если хйЯл^ст;

= 4 ■ (23)

(5 и {х] \ {у} ,довели (х «5 Я) л (|5| = т) л (у е 5)

а 0> = Л(5,?„<22Д));

(24)

Для достижения поставленной в настоящей работе цели предлагается получать гибриды базовых алгоритмов кэширования с помощью метода случайного смешивания стратегий, который применяется, в частности, в теории кооперативных игр. Рассмотрим идею метода на примере гибридизации двух алгоритмов кэширования.

При решении задачи выбора объекта-жертвы случайным образом будем применять либо алгоритм А,, либо А2, Управляющим параметром является вероятность выбора алгоритма а, . Пусть в некоторый момент г необходимо обеспечить вероятность выбора алгоритма а, при решении задачи о выборе жертвы, равную X, 0 < X <, 1. Тогда при решении этой задачи алгоритм а2 должен быть выбран с вероятностью 1-х . Сгенерируем случайную величину 4, распределенную на интервале [0,1] по равномерному закону распределения. Если значение случайной величины £ в момент I окажется меньше X, то для решения задачи выбора Жертвы

будем использовать алгоритм л, (т.е. результат отображения </,(5, <■/,)). Если значение £ окажется больше либо равным Я, то для решения задачи о выборе жертвы будем использовать алгоритм А2 (т.е. результат отображения(/2(5,172)). Предложенный метод гибридизации будем называть методом стохастической гибридизации.

Стохастическим управляемым гибридным алгоритмом, построенным на базовых алгоритмах А, и А2, будем называть кортеж

¿=«2„(>г>ЯтЯго Л-£)< (25)

где ^ е / = [0,1] - начальное значение управляющего параметра алгоритма А ; £ - отображение перехода:

Я:£И„х01х&х/хЛГ-»9Л1„х0хе1 (26)

= (27)

= = если Я<£< 1;

где -состояние кэш-памяти в момент времени 1 + 1; х = г1 -объект, запрошенный в момент времени I, причем .г е Я,; £ е / - случайное число, имеющее равновероятный закон распределения на единичном интервале / = [0,!].

Далее в работе показано, что задача управления гибридным алгоритмом кэширования относится к классу задач стохастического событийного программирования при отсутствии явного выражения для критерия, в качестве которого естественно выбрать оценку вероятности кэш-попаданий. Получаем следующую задачу: найти значение Я, управляющего параметра алгоритма Л = (б,,(?2,<7,0><72оЛ>5')/ обеспечивающего шах Я,, где - оценка вероятности кэш-попаданий на участке <о,к трассы (О.

Упростим поставленную задачу и будем считать, что участок г^., трассы со, предшествующий а>1к, известен и записан в оперативной памяти. Методом статистических испытаний найдем значение , обеспечивающее максимальную частоту кэш-попаданий /»_, на участке м„ ,. Для участка <о1к примем Лк = я,.,.

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

В четвертой главе приведено описание программного стенда, который применялся для экспериментальных исследований гибридных ал-

12

горитмов, разработанных с помощью предложенного метода стохастической гибридизации, Кроме реализации предложенных гибридов в ПО стенда реализованы алгоритмы кэширования и распространённые гибридные алгоритмы, математические модели которых разработаны в настоящей диссертации. Модульная структура стенда позволяет моделировать и исследовать различные алгоритмы кэширования, производить статистическую обработку результатов экспериментов. Предусмотрена возможность экспорта результатов испытаний для последующей их обработки с помощью математических пакетов программ.

В четвертой главе приведены сравнительные испытания разработанных гибридных алгоритмов. Испытания проводились в три этапа. На первом этапе сравнивалась эффективность одного из известных и удачных алгоритмов LRFU с разработанным гибридом RRFU. Оба эти алгоритма были получены на базе алгоритмов LRU и LFU.

На рис.1 дан пример изменения процента кэш-попаданий известного гибрида LRFU в сравнении с базовыми алгоритмами LRU и LFU. На рис.2 показаны аналогичные зависимости для разработанного гибрида RRFU.

LFU 46%

Участок 1

•А.—А—

Участок 3

.о- -с tf

Поток зan/xxxMi оо (цммоии, (ЭООО обращений «адиицо шка/t

Рис. 1. Изменение процента кэш-попаданий алгоритма LRFU

• LFU 46%

Участок 1

Участок 2

Участок !

Потгж запросов оо «ремвни, (3000 Обраидашй оелницо итоп

Рис. 2. Изменение процента кэш-попаданий алгоритма ЙЙРи Средние проценты кэш-попаданий алгоритмов для трасс рис. 1 и 2

приведены в табл.2.

Таблица 2

Алгоритм LFU 1 LRU LRFU RRFU

Ср. процент кэш-попаданий 46% 39% 66% 65%

Сравнительные испытания показали практически идентичную эффективность алгоритмов 1.1^11 и ЯЯРи. Следует отметить, однако, высокую алгоритмическую сложность реализации Простота 1ШРи не вызывает сомнения в возможности реализации этого алгоритма даже аппаратно.

На втором этапе проведены многочисленные испытания алгоритма ЯЯР11 на нестационарных трассах. Как известно, именно такие трассы сложны для эффективной работы кэш-систем. Для генерации трасс использовались разработанные математические модели. Каждая трасса состояла из участков, на каждом из которых поддерживался стационарный поток со своим законом распределения. Для участков ■ использовались законы распределения Зипфа и равномерный закон распределения. Пример результатов испытаний при использовании на участках закона Зипфа "80-20" показан на рис.3.

LRU 13% Zlpfe "80-20" dynamic

-RRFU 15,7%

(2000 обращений >• одиицо школы)

Рис. 3. Изменение процента кэш-попаданий алгоритма RRFU на нестационарной трассе (поток запросов на участках по закону Зипфа "80-20")

Алгоритм RRFU показал высокую эффективность, существенно превышающую эффективность LRU. Как и следовало ожидать, алгоритм LFU показывает очень низкие результаты. Из рис. 3 видно, что эффективность работы алгоритма RRFU может быть повышена, если уменьшить "провалы" частоты кэш-попаданий в начале каждого участка трассы.

Гибрид RRFU был модифицирован методом DCD и назван SRRFU. Испытания на третьем этапе показали, что гибрид SRRFU существенно сокращает "провалы" эффективности в начале каждого участка трассы, которые наблюдаются у алгоритма RRFU, рис. 4.

LRU 13% Ztpfa -ао-ао" dynamic

LFU 4,5%

—A—SRRFU 18,4%

ПОТОК ЭИПрОСО» ПО OfJMaHH. (2000 Овр«Щ411И»1

Рис.4. Изменение процента кэш-попаданий алгоритма ЗЯЯРи на нестационарной трассе (поток запросов на участках по закону Зипфа "80-20")

Результаты статистических испытаний эффективности алгоритма Б1ШРи в сравнении с базовыми алгоритмами приведены в табл.3.

______________________________________________________________________ ______________________Таблица 3

Закон Увеличение вероятное™ кэш-попаданий

распределения SRRFU в сравнении с LRU SRRFU зсравнении с LFU

появления объектов на Средний Доверительный Средний • Доверительный

участках трассы % интервал с: Р=0.95 % интервал с Р=0.95

Равномерный закон 10.65 [8.64,12.66] 304 [228,380]

распределения

Распределение Зипфа 18.76 [14.51,23] 312 [234,390]

•70-30"

Распределение Зипфа 16.2 [12.49,19.91] 290 [213,368]

"80-20"

Алгоритм SRRFU испытывался на стационарных трассах (рис. 5). Как и следовало ожидать, алгоритм LFU на таких трассах по эффективности превышает алгоритм LRU. Отличие эффективности алгоритма SRRFU от эффективности LFU статистически незначимо.

•«•LRU 12,4% Zlpfa "80-20" static LFU 10,8% -A-SRRFU 10,53%

Поток запросов no аромоми. (2000 обращений а одччт шкапы)

Рис. 5. Изменение процента кэш-попаданий алгоритма БЯКРУ на стационарной трассе (поток запросов по закону Зипфа "80-20")

Рис. 6. Изменение процента кэш-попаданий алгоритма 51ЖР11 на реальной трассе

В заключение было проведено испытание алгоритма на реальной трассе. Данная трасса была получена с помощью записи обращений к Web-страницам через прокси-сервер одной из торговых фирм г. Ростова-на-Дону. Результаты испытаний приведены на рис. 6. Как видно на графиках, алгоритм SRRFU показывает вероятность кэш-попаданий в 1.12 раза большую, чем LRU, и в 2.24 раза большую, чем LFU. Следует отметить, что реальная кэш-система прокси-сервера, работающая по алгоритму LRU, обеспечивала практически тот же процент кэш-попаданий (24%), что был получен на модели для этого же алгоритма (24.5%) на том же потоке запросов.

ЗАКЛЮЧЕНИЕ

1. Выполненный анализ позволил классифицировать существующие методы гибридизация, показал актуальность и значимость диссертационной работы, позволил наметить возможные направления получения новых гибридов. Кроме того, было отмечено отсутствие формальных методов гибридизации.

2. Разработанные математические модели гибридных и управляемых гибридных алгоритмов позволили обосновать метод стохастической гибридизации, базирующийся на случайном смешивании стратегий. Разработанный метод отличается простотой реализации и позволяет получать гибридные алгоритмы на основе любого количества произвольных базовых алгоритмов.

3. Предложенный off-line алгоритм управления гибридным алгоритмом, полученный методом стохастической гибридизации, позволил реализовать простую схему адаптации гибридного алгоритма к изменению законов распределения появления объектов информационной системы в потоке запросов.

4. Разработанный программный стенд позволил экспериментально исследовать предложенные в работе методы и алгоритмы. Статистическая обработка результатов экспериментов показала высокую достоверность эффективности полученных гибридных алгоритмов по сравнению с базовыми.

Таким образом, поставленная в диссертации цель достигнута.

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

Публикации в ведущих рецензируемых изданиях, рекомендованных ВАК РФ

1. Аль-Згуль Мосаб Бассам. Гибридные алгоритмы в системах кэширования объектов / Аль-Згуль Мосаб Бассам // Вестник ДГТУ, 2008, №4.

Публикации в других изданиях

2. Гранков М.В. Методы разработки тестов на быстродействие информационных систем с использованием цепей Маркова / М.В. Гранков, Мосаб Бассам Аль-Згуль, Тхань Хунг Нго // Инновационные образовательные технологии в технических университетах: сб. науч. статей по проблемам высшей школы / ЮРГТУ. - Новочеркасск, 2006. С. 394-396.

3. Гранков M.B. Принципы интеграции разнородных систем поддержки учебного процесса в вузе/ М.В. Гранков, Мосаб Б.Ю. Аль-Згуль, Жуков А.И. // Современные проблемы многоуровневого образования: сб. трудов II междунар, научно-методического симпозиума, ММТТ XX. - Россов н/Д: Издательский центр ДГТУ, 2007. С. 294-297.

4. Аль-Згуль М.Б. Применение алгоритма адаптивного кэширование в объектно-ориентированных базах данных / М.Б. Аль-Згуль // Системный анализ, управление и обработка информации: 1-й межвуз. сборник науч. статьей молодых ученых / ДГТУ. - Ростов н/Д, 2007.

5. Аль-Згуль М.Б. Алгоритм моделирования потоков запросов к информационной системе / Мосаб Бассам Аль-Згуль // Математические методы в технике и технологиях: сб. тр. XXI междунар. науч. конференция. - Саратов, 2008.

6. Аль-Згуль Мосаб Бассам. Программный стенд для исследования эффективности алгоритмов кэширования / Мосаб Бассам Аль-Згуль, Тхань Хунг Нго // Математические методы в технике и технологиях: сб. тр. XXI междунар. науч. конференции. - Саратов, 2008.

7. AI Zgool Mosab Bassam, Grankov Michael Vasilevich,. Ngo Thanh Hung. The Framework for Study of Caching Algorithm Efficiency // Proceedings of the Spring young researchers' colloquium on database and information systems - SYRCoDlS 5, volume A. - Saint-Petersburg, 2008.

8. Аль Згуль Мосаб Б.Ю. "Толстый клиент" - технология оптимизации системы поддержки учебного процесса / Мосаб Б.Ю. Аль Згуль,.М.А. Соколов, А.И. Жуков // Математические методы в технике и технологиях: сб. тр. XXII междунар. науч. конференции. - Ростов-на-Дону, 2008.

9. A.c. № 11450. Программный стенд для исследования алгоритмов кэширования / М.Б. Альзгуль, Т.Х. Нго - № государственной регистрации 50200801940; дата регистрации 29.08.2008. - 1 с.

10. Альзгуль М.Б., Нго Т.Х. Программный стенд для исследования алгоритмов кэширования. [Электронный ресурс]. // Инновации в науке и образовании (Телеграф отраслевого фонда алгоритмов и прог рамм).- №9(44). - 2008. - С. 32-33. - Режим доступа: http://ofap.ru/portal/newspaper/2008/9_44.pdf. - Загл. с экрана.

В печать 23.04.09.

Объем 1,0 усл.п.л. Офсет. Формат 60x84/16

Бумага тип № 3. Заказ №189. Тираж 120._____

Издательский центр ДГТУ

Адрес университета и полиграфического предприятия: 344010, г. Ростов-на-Дону, пл. Гагарина,!.

ВВЕДЕНИЕ.

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

СИСТЕМАХ.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.4.7. Алгоритм LRU.

2.4.8. Алгоритм «рабочий набор».

2.4.9. Алгоритм WSCIock.

2.4.10. Алгоритм LFU.

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

2.5.1. Гибридизация по методу основной / дополнительный.

2.5.2. Последовательное включение алгоритмов.

2.5.3. Гибридизация с помощью свертки рейтингов.

2.5.4. Использование в гибридизации нечеткой логики.

2.5.5. Гибридизация по способам хранения информации.

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

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

Глава 3. МАТЕМАТИЧЕСКАЯ МОДЕЛЬ МЕТОДА ГИБРИДИЗАЦИИ

ДВУХ АЛГОРИТМОВ КЭШИРОВАНИЯ.

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

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

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

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

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

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

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

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

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

АЛГОРИТМОВ КЭШИРОВАНИЯ.

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

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

4.1.2. Структура баз данных программного комплекса СасЬеЕ£йс1епсу.

4.1.3. Интерфейс Программного стенда и работа с ним.

4.2. Результаты экспериментальных исследований.

4.2.1. Сравнения гибридных алгоритмов ЬКРи и ЫИРи.

4.2.2. Исследование гибридного алгоритма Ш^и.

4.2.3. Экспериментальное исследование модифицированного гибрида ЗЛИ^и.

4.2.4. Испытание эффективности гибрида БКИРи на реальной трассе.

4.3. Выводы по четвертой главе.

Актуальность исследования. При обработке больших объёмов данных всегда возникает проблема обеспечения скорости доступа к ним. Поскольку СУБД работают с базами данных, размер которых значительно превышает объем доступной оперативной памяти, нет возможности поместить всю информацию из базы данных в оперативную память, и большая ее часть во время работы системы будет оставаться на внешних носителях (магнитных дисках). Практически единственным эффективным способом уменьшения количества обращений к дискам является буферизация данных в оперативной памяти, или так называемое кэширование.

Кэширование — это универсальный метод повышения скорости доступа к данным, основанный на комбинации двух типов памяти, отличающихся временем доступа, объемом и стоимостью хранения данных. Наиболее часто используемая в данный период информация динамически копируется из «медленной, но большой» памяти в «быструю, но маленькую» кэш-память. В настоящее время к разработке новых алгоритмов и технологий кэширования проявляется очень большой интерес. В мире ежегодно издаётся сотни статей, посвящённых алгоритмам кэширования. Повышению эффективности систем кэширования посвящены работы таких исследователей, как: 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 researchers' colloquium on database and information systems (SYRCoDIS V), Saint-Petersburg, 2008; на I международном научно-методическом симпозиуме «Современные проблемы многоуровневого образования» (Дивноморск, 2006); на П международном научно-методическом симпозиуме «Современные проблемы многоуровневого образования» (Дивноморск, 2007);

У" на III международном научно-методическом симпозиуме «Современные проблемы многоуровневого образования» (Дивноморск, 2008);

Промежуточные материалы диссертационных исследований докладывались на ежегодных научно-технических конференциях Донского государственного технического университета.

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

Структура и объём работы. Диссертация состоит из введения, 4 глав, заключения, списка литературы и 6 приложений. Основная часть работы изложена на 140 страницах машинописного текста, 38 рисунках, 18 таблицах.

4.3. Выводы по четвертой главе

Разработанный программный стенд позволил реализовать сравнительные испытания различных алгоритмов кэширования и гибридов. Кроме реализации предложенных гибридов в ПО стенда реализованы алгоритмы кэшировании и распространённые гибридные алгоритмы, математические модели которых разработаны в настоящей работе. Модульная структура стенда позволяет моделировать и исследовать различные алгоритмы кэширования, производить статистическую обработку результатов экспериментов. Предусмотрена возможность экспорта результатов испытаний для последующей их обработки с помощью математических пакетов программ.

Статистическая обработка результатов экспериментов показала высокую достоверность эффективности полученных гибридных алгоритмов по сравнению с базовыми. Так как было показано, что разработанный гибрид RRFU, базирующийся на двух стратегиях кэширования LRU и LFU, позволяет увеличить частоту кэш-попаданий для нестационарных трасс, полученных на базе закона распределения Зипфа "80-20", в среднем на 10% и с вероятностью, 0,95 - не менее чем на 8% .

Применение в алгоритме RRFU метода обнаружения изменения закона распределения вероятности появления объектов в запросах к системам обработки информации с использованием меры Махалонобиса DCD, позволило разработать новый гибрид SRRFU, обеспечивающий на нестационарных трассах, полученных на базе закона распределения Зипфа "80-20", увеличение частоты кэш-попаданий не менее чем на 12% с уровнем значимости 0,95.

129

ЗАКЛЮЧЕНИЕ

1. Выполненный анализ позволил классифицировать существующие методы гибридизация, показал актуальность и значимость диссертационной работы, позволил наметить возможные направления получения новых гибридов. Кроме того, было отмечено отсутствие формальных методов гибридизации.

2. Разработанные математические модели гибридных и управляемых гибридных алгоритмов позволили обосновать метод стохастической гибридизации, базирующийся на случайном смешивании стратегий. Разработанный метод отличается простотой реализации и позволяет получать гибридные алгоритмы на основе любого количества произвольных базовых алгоритмов.

3. Предложенный off-line алгоритм управления гибридным алгоритмом, полученный методом стохастической гибридизации, позволил реализовать простую схему адаптации гибридного алгоритма к изменению законов распределения появления объектов информационной системы в потоке запросов.

4. Разработанный программный стенд позволил экспериментально исследовать предложенные в работе методы и алгоритмы. Статистическая обработка результатов экспериментов показала высокую достоверность эффективности полученных гибридных алгоритмов по сравнению с базовыми.

Таким образом, основные задачи диссертационной работы решены полностью и достигнута ее цель.

1. Ahmad Sharieh: "A Mathematical Model for Non-Uniform Memory Access Machines", Department of Computer Science Jordan University, 1998.

2. Aho A.V., Denning P. J., and Ullman J. D., Principles of optimal page replacement, J. ACM, vol. 18, no. 1, 1971.

3. Astrahan M.M., et al. System R: Relational Approach to Database Management, ACM Transactions on Database Systems. -1976. -Vol.1, No. 2.-P. 97137.

4. Bansal S., Modha DS, CAR: Clock with Adaptive Replacement, Proceedings of the USENIX Conference on File and Storage Technologies, 2004.

5. Belady, L.A., Nelson, R.A., and Shedler, G.S.: "An Anomaly in space-Time Characteristics of Certain Programs Running in a Paging Machine", Commun. Of the ACM, vol. 12, pp.349-353, June 1969.

6. Berkeley DB Programmer's Tutorial and Reference Guide Электронный ресурс.-Режим доступа: http://www.mtholyoke.edu/~mcrowley/perltmp/ docs.db3055/ref/toc.html, свободный.

7. Brown P., Stonebraker M. BigSur: A System For the Management of Earth Science Data, VLDB'95, Proceedings of 21th International Conference on Very Large Data Bases, September 11-15, 1995, Zurich, Switzerland. -Morgan Kaufmann, 1995. P. 720-728.

8. Butterworth P., A. Otis, and J. Stein. The GemStone database management system. Comm. of the ACM, 34(10):64-77, Oct. 1991.

9. Carey M. et al. Storage management for objects in EXODUS. In W. Kim and F. Lochovsky, editors, Object-Oriented Concepts, Databases, and Applications. Addison-Wesley, 1989.

10. Carey M. J. et al. Shoring up persistent applications. In ACM SIGMOD Int. Conf. on Management of Data, pages 383-394, Minneapolis, MN, May 1994.

11. Carey M. J., DeWitt D. J., and Naughton J. F. The 007 Benchmark. In Proc. of ACM SIGMOD International Conference on Management of Data, pages 12-21,Washington D.C., May 1993.

12. Carey M. J., De Witt D. J., and Naughton J. F. The 007 benchmark. Technical Report; Revised Version dated 7/21/1994 1140, University of Wisconsin-Madison, 1994. At ftp://ftp.cs.wisc.edu/007.

13. Carr W. R. and Hennessy J. L., "WSClock a simple and effective algorithm for virtual memory management" in Proc. Eighth Symp. Operating System Principles, pp 8795, 1981.

14. Chamberlin D.D., et al. A History and Evaluation of System R, Communications of the ACM. -1981. -Vol. 24, No. 10. -P. 632-646.

15. Chang E. E. and R. H. Katz. Exploiting inheritance and structure semantics for effective clustering and buffering in an object-oriented dbms. In ACM SIGMOD Int. Conf. on Management of Data, pages 348-357, Portland, OR, May 1989.

16. Choi J., Noh S., Min S., Cho Y., Towards Application/File-Level Characterization of Block References: A Case for Fine-Grained Buffer Management, Proceedings of ACM SIGMETRICS Conference on Measuring and Modeling of Computer Systems, June 2000.

17. Codd E.F. A Relational Model of Data for Large Shared Data Banks, Communications of the ACM. -1970. -Vol. 13, No. 6. -P. 377-387.

18. Coffman E.G., Denning P.J. Operating Systems Theory. -Prentice-Hall,1973.

19. Day M. Client cache management in a distributed object database. Technical Report MIT/LCS/TR-652, MIT Laboratory for Computer Science, 1995.

20. Denning, P. J., The locality principle, Communication of the ACM 48, 7,2005.

21. Denning, P. J.: "Working sets past and present", IEEE Trans. Software Engineering, vol. SE-6, pp. 64-84, Jan. 1980.

22. Denning, P.J.: "The Working Set Model for Program Behavior", Community of the ACM, vol.11, pp.323-333, 1986a.

23. Denning, P.J.: "Thrashing Its Causes and Prevention", Proc. AFIPS National Computer Conf., AFIPS, pp.915-922, 1986b.

24. Denning, P.J.: "Virtual Memory", Computing Surveys, vol. 2, pp. 153189, Sept. 1970.

25. Dinesh Dasarathan, Santhosh Kulandaiyan, ADAPTIVE CACHE REPLACEMENT TECHNIQUE , School of Computer Science and Engineering College of Engineering, Guindy Anna University, Chennai-25. 2002.

26. Donghee Lee, Sam H. Noh, Jongmoo Choi, Sang Lyul Min, «Implementation and Performance Evaluation of the LRFU Replacement Policy», Dep. Of Computer Engineering, Seoul National University, Seoul 151-742 Korea. 1996.

27. Dozier J. Access to data in NASA's Earth observing system, Proceedings of the 1992 ACM SIGMOD International Conference on Management of Data, San Diego, California, June 2-5, 1992. -ACM Press, 1992. -P. 1.

28. Feldman J., Computer Architecture, A Designer's Text Based on a Generic RISC Architecture, 1st ed., New York: McGraw-Hill, 1994.

29. Fox E.A., Akscyn R.M., Furuta R.K., Leggett J.J. Digital libraries ,Communications of the ACM. -1995. -Vol. 38, No. 4. -P. 22-28.

30. Frew J., Dozier J. Data Management for Earth System Science, ACM SIGMOD Record. 1997. -Vol. 26, No. 1. -P. 27-31.

31. Gaponenko I., et al. The BaBar Database: Challenges, Trends and Projections, Proc. of Int. Conf. on Computing in High Energy and Nuclear Physics (CHEP'01), September 3 7, 2001, Beijing, China. -Science Press, 2001.

32. Gibson G.A., Vitter J.S., Wilkes J. Strategic directions in storage I/O issues in large-scale computing // ACM Computing Surveys. -1996. -Vol. 28, No. 4.-P. 779-793.

33. Gray J., Graefe G. The Five-Minute Rule Ten Years Later, and Other Computer Storage Rules of Thumb // SIGMOD Record. -1997. -Vol. 26, No. 4. -P. 63-68.

34. Heising W.P. Note on Random Addressing Techniques // IBM Systems Journal. -1963. -Vol. 2, No. 2. -P. 112-116.35. http://www.objectstore.net.

35. Jelenkovic P. R., Radovanovic A. Optimizing the LRU algorithm for Web caching. // 18th. International Teletraffic Congress, Berlin, Germany, 2003.

36. Jeon Heung-Seok ,Noh Sam-Hyeok. An Efficient Buffer Cache Management Algorithm based on Prefetching // Korea, 2000.

37. Jiang S., Zhang X., LIRS: An Efficient Low Interference Recency Set Replacement Policy to Improve Buffer Cache performance, SIGMETRICS, 2002.

38. Kalakota R., Whinston A. Readings in Electronic Commerce. -Addison-Wesley, 1997.

39. Ke Wang, Salvatore J. Stolfo. Anomalous Pay load-based Network Intrusion Detection.// Computer Science Department, New York, 2004.

40. Kemper A. and D. Kossmann. Dual-buffer strategies in object bases. In 20th Int. Conf. on Very Large Data Bases (VLDB), pages 427-438, Santiago, Chile, 1994.

41. Kim W., J. F. Garza, N. Ballou, and D. Woelk. Architecture of the ORION next-generation database system. IEEE Trans, on Knowledge and Data Engineering, 2(1):109-124, Mar. 1990.

42. Lamb C., G. Landis, J. Orenstein, and D. Weinreb. The ObjectStore database system. Comm. of the ACM, 34(10):50-63, Oct. 1991.

43. Lawrence R. Rabiner. A tutorial on Hidden Markov Models and selected applications in speech recognition. // Proceedings of the IEEE, VOL. 77, NO. 2, Feb 1989. http://www.cs.ubc.ca/~muphyk/Bayers/rabiner.pdf.

44. Lee D., Choi D., Kim J.-H., Noh S. H., Min S. L., Cho Y., Kim C. S., LRFU: A spectrum of policies that subsumes the least recently used and least frequently used policies, IEEE Trans. Computers, vol. 50, no. 12, 2001.

45. Lee D„ Choi J., Kim J.-H., Min S.L., Cho Y., Kim C.S., Noh S.H., On the Existence of a Spectrum of Policies That Subsumes the Least Recently Used (LRU) and Least Frequently Used (LFU) Policies, Proceedings ACM SIGMETRICS, 1999.

46. Liskov В., Adya A., Castro M., Day M., Ghemawat S., Gruber R., Maheshwari U., Myers A. C., and Shrira L. Safe and efficient sharing of persistent objects in Thor. In ACM SIGMOD Int. Conf. on Management of Data, pages 318329, June 1996.

47. Local Caching Электронный ресурс. Режим доступа: http://msdn2.microsoft.com/en-us/library/aa365201 .aspx, свободный. [Loci]

48. Lu G. Multimedia Database Management System. -Artech House, 1999.1.l.

49. Malkewitz, R.: "Head Pointing and Speech Control as a hands-free interface to Desktop Computing", Proc. Third Int'l Conf. on Assistive Technologies, ACM, pp. 182-188,1998. Malkl.

50. Mamdani E.H., Assilian S., An experiment in linguistic synthesis with a fuzzy logic controller, International Journal of Man-Machine Studies, Vol. 7, No. 1, pp.1-13, 1975.

51. Management of Data, Washington, D.C., May 26-28, 1993. ACM Press.1993.

52. Mark Nottingham. Caching Tutorial for Web Authors and Webmasters Электронный ресурс. Режим доступа: http://www.webcaching.com/mnottutorial/, свободный. [Maml]

53. Mazen Kharbutli and Yan Solihi, "Counter-Based Cache Replacement Algorithms", Department of Electrical and Computer Engineering North Carolina State University, 2004. Mazl.

54. Megiddo N., Modha DS., Outperforming LRU with an adaptive replacement cache algorithm, Computer, 2004.57. memcached Wikipedia, the free encyclopedia Электронный ресурс. -Режим доступа: http://en.wikipedia.org/wiki/Memcached, свободный.

55. Miguel Castro, Atul Adya, Barbara Liskov, and Andrew C. Myers, «НАС: Hybrid Adaptive Caching for Distributed Storage Systems», Proceedings of the 16th ACM Symposium on Operating Systems Principles, Saint-Malo, France, 5-8 October 1997.

56. Mojtaba Sabeghi, and Mohammad Hossein Yaghmaee, «Using Fuzzy Logic to Improve Cache Replacement Decisions», IJCSNS International Journal of Computer Science and Network Security, VOL.6 No.3 A, March 2006 , Iran.

57. Nicola V. F. et.al. Analysis of the Generalized Clock Buffer Replacement Scheme for Database Transaction // Processing. In SIGMETRICS-92, 1992.

58. Nimrod Megiddo and Dharmendra S. Modha. Simple Adaptive Cache Outperforms LRU, February 2003.

59. Nutt G., Operating Systems, A Modern Perspective, 2nd ed., Reading, Mass.: Addison Wesley Longman, 2000.

60. O'Toole J. and Shrira L. Opportunistic log: Efficient installation reads in a reliable object server. In Proceedings of the Symp. on Operating System Design and Implementation (OSDI), pages 39-48, Monterey, CA, 1994.

61. O'Neil E.J., O'Neil P.E., Weikum G. The LRU-K Page Replacement Algorithm For Database Disk Buffering // Proceedings of the 1993 ACM SIGMOD International Conference on Management of Data, Washington, D.C., May 26-28, 1993. ACM Press. 1993. P. 297-306.

62. Ontos, Inc., Lowell, MA. Ontos Reference Manual, 1992.

63. Ranjith Subramanian, Yannis Smaragdakis, Gabriel H. Loh, «Adaptive Caches: Effective Shaping of Cache Behavior to Workloads», USA 2006. Rani.

64. Schatz В., Chen H. Digital Libraries: Technological Advances and Social Impacts, IEEE Computer. -1999. -Vol. 32, No. 2. -P. 45-50. Schal.

65. Seok Jeon H., Sam H. Noh. Dynamic buffer cache management scheme based on simple and aggressive prefetching // Proceedings of 4th annual Linux Showcase & Conference, Volume 4, 2000.

66. Singhal V., S. V. Kakkad, and P. R. Wilson. Texas: An efficient, portable persistent store. In 5th Int. Workshop on Persistent Object Systems (POS), pages 1133, San Miniato, Italy, Sept. 1992.

67. Sin-Min Lee Lecture Notes for CS147 Program 3, Tuesday November 23,2004.

68. Stonebraker M. Retrospection on a Database System, ACM Transactions On Database Systems. -1980. -Vol. 5, No. 2. -P. 225-240. Ston2.

69. Stonebraker M., et al. The Design and Implementation of INGRES, ACM Transactions On Database Systems. -1976. -Vol. 1, No. 3. -P. 189-222. Stonl.

70. Stonebraker M., Frew J., Gardels K., Meredith J. The Sequoia 2000 Benchmark, Proceedings of the 1993 ACM SIGMOD International Conference on Management of Data, Washington, D.C., May 26-28, 1993. -ACM Press, 1993. -P. 211. Ston3.

71. Sugeno, M., Industrial applications of fuzzy control, Elsevier Science Inc., New York, NY, 1985.

72. SWIG 1.1 Users Manual Электронный ресурс. Режим доступа: http://www.swig.org/DocLl/HTML/Contents.html, свободный. [Swil]

73. Szalay A.S., et al. The SDSS SkyServer Public Access to the Sloan Digital Sky Server Data // Proceedings of the 2002 ACM SIGMOD International Conference on Management of Data, Madison, Wisconsin, June 3-6, 2002.-ACM Press, 2002. Szal.

74. Ted Neward "The Vietnam of Computer Science", http://blogs.tedneward.com/2006/06/26/The+Vietnam+of+Computer+Science.aspx, 2006. 77.

75. Tsangaris M. and J. F. Naughton. On the performance of object clustering techniques. In ACM SIGMOD Int. Conf. on Management of Data, pages 144-153, San Diego, CA, June 1992.

76. Tsangaris M. and Naughton J. A stochastic approach for clustering in object bases. In Proc. ACM SIGMOD International Conference on Management of Data, pages 12-21, Denver, CO, 1991. ACM.

77. Tsichritzis D. and Bernstein P., Operating Systems, 1st ed., London: Academic Press, 1974.

78. Umapathi C., Raja. J.A Prefeching Algorithm for Improving Web Performance //Journal of Applied Science 6(15):3122-3127, 2006.

79. Vakali A. I., "LRU-based algorithms for Web Cache Replacement", Department of Informatics Aristotle University of Thessaloniki, Greece,2000. Vakl.

80. Wang Lie-Xin, A course in fuzzy systems and control, Prentice Hall, Paperback, Published August 1996.

81. Web Cache Wikipedia, the free encyclopedia Электронный ресурс. -Режим доступа: http://en.wikipedia.org/wiki/Webcache, свободный.

82. White S. and D. DeWitt. A performance study of alternative object faulting and pointer swizzling strategies. In 18th Int. Conf. on Very Large Data Bases (VLDB), pages 419-431, Vancouver, British Columbia, Aug. 1992.

83. White S. J. and D. J. De Witt. QuickStore: A high performance mapped object store. In ACM SIGMOD Int. Conf. on Management of Data, pages 395-406, Minneapolis, MN, May 1994.

84. Yuanyuan Zhou, James F. Philbin. The Multi-Queue Replacement Algorithm for Second Level Buffer Caches \\ Proceedings of the 2001 USENIX Annual Technical Conference, Boston, USA June 25-30, 2001. Yual.

85. Zipf G.K. Human Behavior and the Principle of Least Effort: an Introduction to Human Ecology. -Cambridge, Mass.: Addison-Wesley, 1949. -573 p.

86. Аль-Згуль М.Б. Алгоритм моделирования потоков запросов к информационной системе. // ММТТ21, секция 11, май 2008.

87. Аль-Згуль Мосаб Бассам. Гибридные алгоритмы в системах кэширования объектов.// Вестник ДГТУ, №4, 2008.

88. Архангельский А. Я. Программирование в Delphi для Windows. Версии 2006, 2007, Turbo Delphi. M.:Бином-Пресс, 2007. -1248с.

89. Вильям Дж., Пейдж, Использование Oracle8/8i, Москва 2000.

90. Волковой В.Н., Козлова В.Н. Системный анализ и принятие решений / словарь справочник, издательства «Высшая школа», 2004. Вол1.

91. Голицына O.JI. Основы алгоритмизации и программирования / Голицына O.JL, Попов И.И. 2-е изд. - М.: Форум:Инфра-М, 2006. - 432с.

92. Грановский В. А., Сирая Т. Н. Методы обработка экспериментальных данных при измерениях. -Л.: Энергоатомиздат. Ленингр. отделение, 1990.

93. Гранков М.В., Нго Тхань Хунг, Аль Згуль Мосаб Бассам, «Методы разработки тестов на быстродействие информационных систем с использованием цепей Маркова», сборнике научных статей по проблемам высшей школы, ЮРГТУ Новочеркасска, ноябрь 2006.

94. Дейт К. Дж. Введение в системы баз данных. 7-ое издание / К. Дж Дейт. М.: Вильяме, 2001. - 1072с.

95. Жак C.B. Математические модели менеджмента и маркетинга, Ростова-на-Дону 1997. Жа1.

96. Златопольский Д. Программирование. Типовые задачи, алгоритмы, методы. -М.:Бином. Лаборатория знаний, 2007.-222с.

97. ЮО.Кендалл С. UML Основные концепции.: Пер. с англ. М.: Издательский дом "Вильяме", 2002. - 144 с.:ил.

98. Клир Дж. Системология автоматизация решения системных задач / Перевод на русский язык, издательство «Радио и связь», 1990. Кли1.

99. Кнут Д.Э. Искусство программирования, т. 1. Основные алгоритмы, 3-е изд. -М.: Издательский дом "Вильяме", 2000. -720 с.

100. Ковалев М.М. Дискретная оптимизация целочисленное программирование, издание второе, Москва 2003. Ков1.

101. Когаловский М.Р., Новиков Б.А. Электронные библиотеки новый класс информационных систем, Программирование. -2000. -№3. -С. 3-8. Korl.

102. Колесников A.B. Гибридные интеллектуальные системы: теория и технология разработки. СПб.: Изд-во СПбГТУ, 2001.-600 с.

103. Юб.Колин А. Введение в операционные системы. —М.: Мир, 1975. 106.

104. Корнеев B.B. Современные микропроцессоры/ B.B. Корнеев, A.B. Киселев.- М:Нолидж.-1998. 237с.

105. Кузнецов С.Д. Вьетнам компьютерной науки, http://www.citforum.ru/database/articles/vietnam, июнь 2006.

106. Кузнецов С.Д. Методы оптимизации выполнения запросов в реляционных СУБД, Сб. Итоги науки и техники. Вычислительные науки. -Т.1. -М.-.ВИНИТИ, 1989. -С. 76-153.

107. О.Кузнецов С.Д. СУБД и файловые системы. -М.: Майор, 2001.

108. Jbo Б. Теория и практика неопределенного программирования. // Москва, БИНОМ, Лаборатория знаний, 2005.

109. Моисеев H.H., Иванилов Ю.П, Столярова Е.М. Методы оптимизации / издательства «Наука», 1978. Мои1.

110. ПЗ.Моненко А. Д. Delphi 7 / Моненко А. Д.- СПб.: БХВ-Петербург, 2006. 476с.

111. Нго Т.Х., Аль-Згуль Б.М., Программный стенд для исследования эффективности алгоритмов кэширования, XXI Том 5,Саратов 2008.

112. Нго Тхань Хунг. Метод вертикальной кластеризации для реляционных систем хранения и обработки информации.// ДГТУ, Диссертация, 2008.

113. Нго Тхань Хунг. Метод вертикальной кластеризации для реляционных систем хранения и обработки информации, автореферат, ДГТУ, Ростов-на-Дону, 2008.

114. Олифер В.Г., Олифер H.A., Сетевые операционные системы, 2-е издание, Питер 2008.

115. Румшиский JI. 3. Математическая обработка результатов эксперимента Справочное руководство/ JI. 3. Румшиский - М: изд-во "Наука", 1971. -35с. Рум2.

116. Подвальный C.JI. Базы данных: модели данных, SQL, проектирование Учебное пособие/ C.JI. Подвальный, Т.И. Сергеева, М.В. Гранков. - Ростов н/Д: Издательский центр ДГТУ, 2007. -202 с.

117. Рэндал Э. Брайант, Дэвид Р. 0"Халларон. : "Компьютерные системы архитектура и программирования взгляд программиста", Пер. с англ. — СПб.: БХВ-Петербург 2005. Рэн1.

118. Свидетельство об отраслевой регистрации разработки № 11450. Программный стенд для исследования алгоритмов кэширования / М.Б. Альзгуль, Т.Х. Нго — № государственной регистрации 50200801940; дата регистрации 29.08.2008 1 с.

119. Соколинский Л.Б. Методы организации параллельных систем баз данных на вычислительных системах с массовым параллелизмом.// ЧТУ, проект 00-07-90077 поддержке Российского фонда фундаментальных исследований, Челябинск ,2003. Сокол2.

120. Соколинский Л.Б. Стратегия замещения или как освободить место в буфере, проект 00-07-90077 поддержке Российского фонда фундаментальных исследований, 2002.

121. Соколинский Л.Б. Методы организации параллельных систем баз данных на вычислительных системах с массовым параллелизмом. // Челябинский государственный университет, диссертации, Челябинск,2003.

122. Таненбаум Э. Современные Операционные Системы, 2-е изд. Питер-2002,С.250-253.

123. Томас Конноли Каролин Бегг Анна Старчан «Базы данных. Проектирование, реализация и сопровождение. Теория и практика.» Издательство «Вильяме» 2001 г.

124. Химмельблау Д. Прикладное нелинейное программирование / Перевод на русский язык, издательство «Мир», 1975.

125. Цветков В.Я. Геоинформационные системы и технологии. М.: Финансы и статистика, 1998. Цвет1.

126. Чаки Ф. Современная теория управления, нелинейные, оптимальные и адаптивные системы / Перевод на русский язык, издательство «Мир», 1975. Чак1.