Гибридные алгоритмы кэширования для систем обработки и хранения информации тема диссертации и автореферата по ВАК РФ 05.13.01, кандидат технических наук Аль-Згуль Мосаб Бассам Юсеф

• Аль-Згуль Мосаб Бассам Юсеф
• кандидат технических наук
• 2009

Оглавление диссертации кандидат технических наук Аль-Згуль Мосаб Бассам Юсеф

ВВЕДЕНИЕ.

Глава 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. Разработанный программный стенд позволил экспериментально исследовать предложенные в работе методы и алгоритмы. Статистическая обработка результатов экспериментов показала высокую достоверность эффективности полученных гибридных алгоритмов по сравнению с базовыми.

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

Список литературы диссертационного исследования кандидат технических наук Аль-Згуль Мосаб Бассам Юсеф, 2009 год

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.