Математические модели и средства программной поддержки поиска оптимальных стратегий кэширования в операционных системах и системах с базами данных тема диссертации и автореферата по ВАК РФ 05.13.01, кандидат технических наук Копылов, Игорь Валентинович

• Копылов, Игорь Валентинович
• кандидат технических наук
• 2002

Оглавление диссертации кандидат технических наук Копылов, Игорь Валентинович

Введение.

Глава 1. Подсистема ввода/вывода ЭВМ и ее производительность.

1.1 Диск. Геометрия диска.

1.2 Способы повышения производительности ввода/вывода.

1.2.1 Кэширование.

1.2.2 Последовательный доступ.

1.2.3 Асинхронный обмен.

1.2.4 Параллелизм.

1.3 Обзор литературы.

1.4 Исторические аспекты и коммерческие продукты.

1.5 Выбор направления исследования. Постановка и систематизация задач исследования.

1.6 Выводы.

Глава 2. Классические стратегии кэширования: построение и анализ.

2.1 Алгоритмы замещения и сравнительный анализ эффективности.

2.1.1 Детерминированные алгоритмы замещения.

2.1.2 Сравнительный анализ эффективности алгоритмов замещения.

2.1.3 Маркирующие алгоритмы.

2.1.4 Рандомизированные алгоритмы замещения.

2.2 Методика оценки коэффициентов сравнительной эффективности алгоритмов замещения.

2.2.1 Метод потенциальных функций.

2.2.2 Минимаксный принцип Yao.

2.3 Имитационное моделирование стратегий замещений.

2.4 Выводы.

Глава 3. Организация эффективного ввода/вывода и оптимального кэш-менеджмента.

3.1 Обозначения, определения и допущения.

3.2 Математические модели оптимальной декомпозиции файлов данных по дискам.

3.2.1 Модели декомпозиции файлов с запретом их дублирования.

3.2.2 Модели декомпозиции файлов с возможностью их дублирования.

3.2.3 Метод ветвей и границ как один из алгоритмов решения задач оптимальной декомпозиции файлов.

3.3 Математические модели размещения файлов данных на диске.

3.4 Математические модели кэширования и упреждения файлов данных.

3.4.1 Последовательный обмен с дисками.

3.4.2 Параллельный обмен с дисками.

3.4.3 Решение задач оптимального кэширования и упреждения.

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

3.5.1 Временные ряды: анализ и прогноз.

3.5.2 Алгоритм адаптивного краткосрочного прогнозирования.

3.6 Выводы.

Глава 4. Библиотека кэширования и упреждения SmartCache.

4.1 Структура и прикладной программный интерфейс SmartCache.

4.1.1 Структура SmartCache.

4.1.2 Прикладной программный интерфейс SmartCache.

4.2 Экспериментальная проверка SmartCache.

4.3 Выводы.

Введение диссертации (часть автореферата) на тему «Математические модели и средства программной поддержки поиска оптимальных стратегий кэширования в операционных системах и системах с базами данных»

Значительный рост производительности процессоров и уменьшение времени цикла оперативной памяти привёл к тому, что обработка запросов ввода/вывода стала критической в эффективности вычислительных систем. Улучшение технических характеристик аппаратных средств ЭВМ, емкость внешней памяти в которых возросла до сотен терабайт, по экстенсивному пути развития ограничено технологическими возможностями и уровнем развития конструкторской базы, прежде всего, из-за присущих механическим носителям физических ограничений. Вследствие этого данный метод теряет свою привлекательность и заставляет искать другие пути повышения производительности вычислительных машин.

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

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

Однако до настоящего времени решение подобного рода задач технического проектирования и программирования в основном базировалось на опыте и интуиции разработчиков. Такой эмпирический подход уже на ранних стадиях разработки мог внести ошибки в решения, устранение большинства которых обходится слишком высокой ценой. Это в полной мере относится к решению задач декомпозиции файлов данных и их размещения в многоуровневой памяти ЭВМ, которые бы минимизировали верхнюю границу числа обращений к внешним носителям и ряду других задач, возникающих в процессе создания систем с базами данных и АСУ [1, 2, 3].

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

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

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

Научная новизна диссертационной работы заключается в:

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

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

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

Практическое значение работы:

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

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

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

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

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

• алгоритмы поиска оптимальных стратегий кэширования в общем случае;

• методы аналитического анализа стратегий кэширования в частных случаях;

• средства программной поддержки интеллектуальных баз данных, ориентированных на ускоренный поиск и обработку информации. Апробация и реализация работы. Основные результаты диссертации докладывались на международной научно-практической конференции «Моделирование. Теория, методы и средства.» (г. Новочеркасск, апрель 2001г.), научно-практической конференции «Современные информационные технологии в образовании» (г. Владикавказ, май-июнь 2001 г.), межвузовской научно-практической конференции «Новые информационные технологии и их применение» (г. Владикавказ, ноябрь 2001 г.), международной конференции «Новые информационные технологии в науке, образовании, экономике» (г. Владикавказ, июнь 2002 г.), международной конференции «Информационные технологии и системы: наука и практика» (г. Владикавказ, октябрь 2002 г.).

Разработанные методы оптимального управления внешней и кэшпамятью и реализованное на их основе программное обеспечение внедрены в эксплуатацию в Государственном научно-исследовательском институте системной интеграции (ГосНИИСИ) г. Москва, ЗАО «Мобильные коммуникации» (Мобилком) г. Владикавказ, АКБ Жилкоммунбанк (ЗАО) г. Владикавказ, АКБ "Адамон Банк" г. Владикавказ, а также использованы при разработке пакетов прикладных программ, в ходе выполнения проекта «Создание виртуальной интернет-выставки возможностей и достижений министерства образования РФ» (код проекта 265(000)207.039) в рамках федеральной целевой программы и при финансовой поддержке Министерства образования РФ (см. Приложение).

Публикации. По материалам диссертации опубликовано 9 работ. Структура и объем диссертации. Диссертация состоит из введения, четырех глав, заключения, списка литературы из 124 наименований, приложения, содержит 33 рисунка, 17 таблиц и 157 страниц текста.

Заключение диссертации по теме «Системный анализ, управление и обработка информации (по отраслям)», Копылов, Игорь Валентинович

Основные результаты выполненной работы заключаются в следующем:

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

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

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

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

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

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

7. Развитая в диссертации технология кэширования и декомпозиции файлов данных внедрена в практику разработки нового программного обеспечения.

139

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

Развитый в работе формализм позволил проанализировать эффективность различных стратегий кэширования применительно к разным сочетаниям аппаратно-программных средств и условий поиска данных. В ряде случаев удалось получить эффективные алгоритмы поиска оптимальных стратегий кэширования, программно реализованные в модуле SmartCache.

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

ЗАКЛЮЧЕНИЕ

Настоящая диссертационная работа является законченной научно-исследовательской работой, в которой решены актуальные научно-технические задачи.

Список литературы диссертационного исследования кандидат технических наук Копылов, Игорь Валентинович, 2002 год

1. Гроппен В.О. Принципы оптимизации программного обеспечения ЭВМ. -Ростов н/Д.:Изд-во Рост, ун-та, 1993.-168 с.

2. Инмон У., Фридман Л. Методология экспертной оценки проектных решений для систем с базами данных. -М.:Финансы и статистика, 1986283 с.

3. Будаева А.А., Копылов И.В. Об одной модели поиска эффективных стратегий решения задач таксономии большой размерности в подсистеме АСУ «ВУЗ» // Владикавказ, Труды СКГТУ, 2002. Вып. 9, 118-124 с.

4. Russel Hugo Patterson III. Informed Prefetching and Caching. Ph. Doctor Thesis, CMU-CS-97-204, School of Computer Science Carnegie Mellon University Pittsburgh, December 1997, p. 240.

5. Leonard Chung, Jim Gray,Bruce Worthington,Robert Horst. Windows 2000 Disk 10 Performance. Technical Report MS-TR-2000-55, Microsoft Research, Advanced Technology Division, Microsoft Corporation, One Microsoft Way, Redmond, WA, June 2000, p. 50.

6. William V. Courtright II, Garth Gibson, Mark Holland, Jim Zelenka. A structured approach to Redundant disk array implementation. Technical Report CMU-CS-96-137, School of Computer Science Carnegie Mellon University, 10 June 1996, p. 16.

7. Финогенов К Г. MS-DOS. -M :МП «Малип», 1992.-128 с.

8. Андрианов С. Испытания на «жесткость».// Мир ПК № 12, 2001., с. 18-35.

9. Шнитман В. Современные высокопроизводительные компьютеры. М. :МП «Малип», 1996.-245 с. Также доступна как информационно-аналитические материалы Центра Информационных Технологий, http://citforum.ru.

10. Копылов И.В. Об одной стратегии эффективной организации эксплуатации дисковых массивов// Сб. научных трудов аспирантов. -Владикавказ, СКГТУ: Изд-во «Терек», 2000, с. 161-166.

11. Andrew Tomkins, R. Hugo Patterson, and Garth Gibson. Informed multiprocess prefetching and caching. In Proc. of the SIGMETRICS'97, Seatle, Washington, June 1997, pp. 100-114.

12. Andrew Tomkins. Practical and Theoretical Issues in Prefetching and Caching. Technical Report CMU-CS-97-181, Computer Science Department Carnegie, Mellon University, Pittsburgh, October 7, 1997, p. 28.

13. Margo Ilene Seltzer. File System Performance and Transaction Suport. Ph. Doctor Thesis. Computer Science Department, University of California at Berkeley, 1992, p. 120.

14. Microsoft Developer Network Library. © 2000 Microsoft Corporation. http://msdn.microsoft.com.

15. Groppen V.O. Models and algorithms of software optimization. //1-st IFAC Workshop on Modeling and Architectures for real-time Control. Abstracts. 1113 September, 1991, Bangor, North Wales, United Kingdom, p. 46-47.

16. J. K. Ousterhout, H. Da Costa, D. Harrison, M. A. Kunze and J. G. Thompson. A Trace-Driven Analisys of the UNIX 4.2 BSD File System. In Procs. of the Tenth Symposium on Operating Systems Principles, Orcas Island WA, December 1985, pp. 15-24.

17. Ethan L. Miller, Randy H. Katz, Input/output behavior of supercomputing applications. In Procs. of the 1991 ACM/IEEE conference on Supercomputing, Albuquerque, New Mexico, US, November 18-22, 1991, p.567-576.

18. B. T. Zivkov, A. J. Smith. Disk Caching in Large Databases and Timeshared Systems. Technical Report CSD-96-913, Computer Science Division, Univ. of California, Berkeley, September 1996, p.75.

19. David Kotz. Disk-Directed I/O for MIMD Multiprocessors. In Proc. of the 1st USENIX Symp. on Operating Systems Design and Implementation, Monterey, CA, November 1994, pp. 61-74.

20. David Kotz, Carla Schlatter Ellis. Caching and Writeback Policies in Parallel File Systems. Journal of Parallel and Distributed Computing, Volume 17 , Issue 1-2 Jan./Feb. 1993, p. 8.

21. D. Kotz and C. S. Ellis. Practical Prefetching Techniques for Parallel File Systems. Journal of Distributed and Parallel Databases, Vol. 1, pp. 33-51, 1993.

22. Erik Riedel, Catharine van Ingen, Jim Gray. A Performance Study of Sequential I/O on Windows NT(TM) 4. In the Procs of the 2nd USENIX Windows NT Symposium, 1998, Seattle, Washington, 1998, p. 23.

23. Alan J. Smith. Sequential program prefetching in memory hierarchies. IEEE Computer, 11(12) :7-21, December 1978, p.38

24. A. S. Grimshaw and E. C. Loyot Jr. ELFS: Object-oriented extensible file systems. Technical Report Computer Science Techinical Report № TR-91-14, University of Virginia, 1991, p.31.

25. Geoffrey H. Kuenning. The design of the Seer predictive caching scheme. In Procs. Workshop on Mobile Computing Systems and Applications (MCSA), Santa Cruz, California, U.S., IEEE Computer Society Press, December 1994, pp. 37-43.

26. Chao-Hsien Lee, Meng Chang Chen, and Ruei-Chuan Chang. HiPEC: High Performance External Virtual Memory Caching. In Procs. of First Symposium on Operating Systems Design and Impl. (OSDI), Monterey, CA, 14-17 November 1994, pp. 53-64.

27. Apratim Purakayastha, Carla Schlatter Ellis, David Kotz. Enwrich: A Computer-Processor writecaching scheme for parallel file systems. In Proc. Fourth Workshop on I/O Parallel and Distributed Systems, Philadelphia, PA, USA, May 1996, pp. 55-68.

28. Копылов И.В. О некоторых аспектах проектирования универсальной автоматически упреждающей файловой системы. М., Рукопись деп. в ВИНИТИ, № 723-В00, 2000.-13 с.

29. Р. Cao and Е. W. Felten and A. Karlin and K.Li. Implementation and Performance of Integrated Application-Controlled Caching, Prefetching and Disk Scheduling. ACM Transactions on Computer Systems. 14(4):311-343. Nov 1996.

30. J. Griffioen and R. Appleton. Reducing File System Latency Using a Predictive Approach. In Proc. 1994 USENIX Summer Conf., Boston, Massachusetts, USA , June 1994, p. 197-207.

31. R. Hugo Patterson, Garth A. Gibson, M. Satyanarayanan. A Status Report on Research in Transparent Informed Prefetching, in ACM Operating Systems Review, V 27(2), April, 1993, pp.21-34.

32. R. Hugo Patterson, Garth A. Gibson. Exposing I/O Concurrency with Informed Prefetching, in Proc. Third International Conf. on Parallel and Distributed Information Systems, Austin, TX, Sept. 28-30, 1994, pp. 7-16.

33. R.H. Patterson, G.A. Gibson, M. Satyanarayanan. Using Transparent Informed Prefetching (TIP) to Reduce File Read Latency. Goddard Conference on Mass Storage Systems and Technologies, Greenbelt, MD, September, 1992, pp. 329342.

34. R. H. Patterson, G. A. Gibson, E. Ginting, D. Stodolsky and J. Zelenka.1.formed Prefetching and Caching. In Proc. Fifteenth Symp. on Operating Systems Principles, Copper Mountain Resort, CO, December 1995, p. 79-95 ACM.

35. James E. Bennett, Michael J. Flynn. Reducing Cache Miss Rates Using Prediction Caches. Technical Report CSL-TR-96-707, Computer Systems Laboratory, Stanford University, October 1996, p. 35.

36. Todd C. Mowry. Tolerating latency through software-controlled data prefetching. Ph Doctor Thesis. Stanford University, March 1994, p. 221.

37. Т. C. Mowry and C. Luk. Predicting data cache misses in non-numeric applications through correlation profiling. In 30th International Symposium on Microarchitecture, Dec 1997, pp. 314-320.

38. Tulica Mitra, Chuana-Kai Yang, Tzi-cher Chieueh. Application-Specific File Prefetching in Stony Brook Linux. Technical Report. Computer Science Department, State University of New York at Stony Brook, July 1, 1999, p. 17.

39. Garth A. Gibson, R. Hugo Patterson, M. Satyanarayanan. Disk Reads with DRAM Latency. In Third Workshop on Workstation Operating Systems, Key Biscayne, FL, April, 1992, pp. 126-131.

40. Christine Fricker, Philippe Robert. An analytical cache model. TR № 1496, INRIA, domaine de Voluceau B.P. 105, 78153 Le Chesnay Cedex, France. Septembre 1991, p. 28.

41. Thomas M. Kroeger and Darrell D. E. Long. Predicting File System Actions from Prior Events. USENIX 1996 Annual Technical Conference, San Diego, CA, January 22-26, 1996, pp. 319-328.

42. Thomas M. Kroeger. Predicting file system actions from reference patternce. Master of Science Thesis, CS department, University of California Santa Cruz, December 1996, p. 46.

43. Hui Lei, and Dan Duchamp. An Analitycal approach to File Prefetching. In Proc. USENIX 1997 Annual Technical Conference Anabeum, California, January 6-10, 1997, p. 15.

44. James Griffioen and Randy Appleton. Performance Measurements of Automatic Prefetching. In Proc. of the ISCA International Conference on Parallel and Distributed Computing Systems, September 1995, p. 34.

45. James Griffioen and Randy Appleton. The design, implementation and evaluation of caching file system. Technical Report CS-264-96, Department of Computer Science, University of Kentucky, Lexington, June 30, 1996, p. 33.

46. Kenneth M. Curewitz, P. Krishnan, Jeffrey Scott Vitter. Practical Prefetching via Data Compression. In Proc.of the 1993 ACM Conference on Management of Data (SIGMOD), Washington, DC,May 1993, pp. 257-266.

47. Jeffrey Scott Vitter, P. Krishnan. Optimal prefetching via Data Compression. Technical Report CS-1995-25, Department of Computer Science, Duke University, Durham, November 13, 1995, p. 20.

48. P. Krishnan, Jeffrey Scott Vitter. Optimal prediction for prefetching in the worst case. In Proc. of the 5th Annual ACM-SIAM Symposium on Discrete Algorithms, Arlington, Virginia, January 1994, pp. 392-401.

49. C. Chen and N. Roussopoulos. Adaptive database buffer allocation using query feedback. In Proc. of the 19th Very Large Databases Conference, Dublin,1.eland, 1993, pp. 342-353.

50. Tracy Kimbrel. Parallel Prefetching and Caching. Ph. Doctor Thesis. Computer Science Department, University of Washington, 1997, p. 159.

51. Trace Kimbrel, Anna R. Karlin. Near-Optimal Parallel Prefetching and Caching. SIAM Journal on Computing Volume 29, Number 4 pp. 1051-1082.

52. Darry L. Willick, Derek L. Eager, and Richard B. Bunt. Disk Cache Replacement Policies for Network Fileservers. Proceedings of the 13th International Conference on Distributed Computing Systems. May 25-28, 1993, Pittsburgh, Pennsylvania, USA, pp. 2-11.

53. M. G. Baker, J.H. Hartman, M. D. Kupfer, J. K. Ousterhout. Measurements of a Distributed File System, In Proc. the 13th Symp. on Operating System Principles, Pasific Grove, С A, October 1991, p. 198-212.

54. Prabuddha Biswas, К. K. Ramakrishnan, Don Towsley, С. M. Krishna. Performance Benefits of None-Volatile Caches in Distributed File Systems. Technical Report. Office and Teamware Engineering Digital Equipment Corporation, Nashua, p. 34.

55. Thomas H. Cormen, David Kotz. Integrating Theory and Practice in Parallel File Systems. In Procs. of DAGS Symposium on Parallel I/O and Databases, Washington, June 1993. pp. 64-74.

56. Thomas H. Cormen, David Kotz. Intelligent, Adaptive File System Policy

57. Selection. In Procs. of the Sixth Symposium on the Frontiers of Massively Parallel Computation (October 1996), pp. 172-179.

58. Steve Dropsho, Chip Weems. Comparing Caching Techniques for Multitasking Real-Time Systems. Technical Report. -CS-1997-065, November, 1997 Computer Science Department, University of Massachussets-Amberst, 1997, p. 16.

59. Rakesh Barve, Edward F. Grove, Jeffrey Scott Vitter. Application Controlled Paging for a Shared Cache. SIAM Journal on Computing, 29(4), 2000, 12901303.

60. P. Krishnan. Online Prediction Algorithms for Databases and Operating Systems. PhD thesis, Department of Computer Science, Brown University, Providence, Rhode Island 02912, USA, August 1995. Also as Technical Report CS-95-24, p. 136.

61. V. S. Pai, P. Druschel, and W. Zwaenepoel. IO-Lite: a unified I/O buffering and caching system. ACM Transactions on Computer Systems, 18( 1 ):37—66, 2000.

62. Eric Torng. A unified analysis of paging and caching. Algorithmica 20:175200, February 1998, p. 25.

63. Neal E. Young. On-Line File Caching. Technical Report PCS-TR97-320, Department of Computer Science, Dartmouth College, Hanover, p. 8.

64. Douglas Comer, James Griffioen. A new design for Distributed Systems: The Remote Memory Model. In Procs. of the Summer 1990 USENIX Conference, pages 127-135, June 1990, p. 15.

65. P. Sarkar and J. Hartman, Efficient Cooperative Caching using Hints, Proceedings of ACM Operating Systems Design and Implementation

66. Conference (OSDI'96), October, 1996, Seattle, Washington, pp. 267-280.

67. David Rochberg, Garth Gibson. Prefetching Over a Network: Early Experience With CTIP. ACM SIGMETRICS Performance Evaluation Review, V 25 (3), December, 1997, pp.29-36.

68. Тага M. Madhyastha, Daniel A. Reed. Input/Output Access Pattern Classification Using Hidden Markov Models. Workshop on Input/Output in Parallel and Distributed Systems (IOPADS), November 1997, pp.57-67.

69. Madhyastha, Т. M., and Reed, D. A.lntelligent, Adaptive File System Policy Selection. In Procs. of the Sixth Symposium on the Frontiers of Massively Parallel Computation, October 1996, pp. 172-179.

70. Peter Bosch, Sape Mullender. Extensive Write Caching. Broadcast Technical Report №63, Esprit Basic Research Project 6360, Universiteit Twente ,October 21, 1994, p. 13.

71. Peter Chen. Optimizing Delay in Delayed-Write File Systems. Technical Report CSE-TR-293-96, Computer Science and Engeneering Division, Department of Electrical Engeneering and Computer Science, University of Michigan, May 1996, p. 11.

72. Geoffrey H. Kuenning. Seer: Predictive File Hoarding for Disconnected Mobile Operation. Technical Report UCLA-CSD-970015, UCLA Computer Science Department, University of California, Los Angeles, May, 1997, p. 154.

73. Бурков В.Н., Рубинштейн М.И., Соколов В.Б. Некоторые задачи оптимального размещения информации в памяти большого объема. //Автоматика и телемеханика, № 9, 1969., с. 83-91.

74. Гроппен В.О. Эффективные стратегии использования кэш-памяти.// Автоматика и телемеханика № 1, 1993, с. 173-179.

75. Гроппен В.О., Копылов И.В. Модели и методы поиска эффективных стратегий буферизации в сетевых файловых серверах удаленного доступа// Труды СКГТУ, 2002. Вып. 9, Издательство СКГТУ "Терек", 114-118 с.

76. Groppen V.O. Expert systems for computer memory optimal control. // IF AC Workshop on Safety, Reliability and Applications of Emerging Intelligent Control Technologies. Hong Kong, 12-14 December 1994 , p. 226-228.

77. P.J. Denning. Working sets past and present. IEEE Trans. Software Eng., 6:6484, 1980.

78. Дейтел Г. Введение в операционные системы. Том 1. -М.:Мир, 1987.-359 с.

79. Цикритзис Д., Бернстайн Ф. Операционные системы. -М.:Мир, 1977 336 с.

80. P. Cao and Е. W. Felten and A. Karlin and K.Li. A study of integrated prefetching and caching strategies. In Proc. of the Joint International Conference on Measurement & modeling of Computer Systems (SIGMETRICS), Ottawa, Canada, May, 1995, pp. 188-197.

81. Pei Cao. Allocation Policies for Application-Controlled File Cache Management. Technical Report. Computer Sciences Department, University of Wisconsin-Madison, June 1997, p. 5.

82. Gideon Glass and Pei Cao. Adaptive Page Replacement Based on Memory Reference Behavior. Computer Science Department, University of Wisconsin-Madison. Technical Report 1338, UW-Madison Computer Sciences Department, January 1997, p. 6.

83. L.A. Belady. A study of replacement algorithms for virtual storage computers. IBM Systems Journal, 5:78-101, 1966.

84. Dimitris Achlioptas, Marek Chrobak, John Noga. Competitive analysis of randomized paging algorithms. In Procs. 4th European Symposium on Algorithms, LNCS 1136, p.419-430, Springer, 1996.

85. S. Albers. Competitive Online algorithms. BRICS Lecture Series LS-96-2, BRICS, Department of Computer Science, University of Aarhus, September 1996, p. 57.

86. Susanne Albers. Online algorithms:a study of graph-theretic concepts. Techical Report № TR-14-101. Max-Planck-Institut fur Informatic, Im Stadtwald, Germany, 1997, p. 17.

87. Susanne Albers, Sanjeev Arora, Sanjeev Khanna. Page replacement for general caching problem. Techical Report № TR-14-1013. Max-Planck-Institut for Informatic, Im Stadtwald, Germany, 1997, p. 10.

88. Amos Fiat, Richard M. Karp, Michael Luby, Lyle A. McGeoch, Daniel D. Sleator, Neal E. Young. Competitive paging algorithms. Journal of Algorithms, v.12 n.4, p.685-699, Dec. 1991.

89. Amos Fiat, Yuval Rabani, Yiftach Ravid. Competitive k-Server algorithms. Journal of Computer and System Sciences, 48(3):410-428, June 1994.

90. Sandy Irani. Competitive analysis of paging: a survey. TEchnical Report. Information and Computer Science Department, University of California, Irvine, p. 19.

91. Steven Phillips, Jeffery Westbrook. On-line algorithms: competitive analysis and beyond. January 1998, p. 35.

92. S. Ben-David, A. Borodin, R.M. Karp, G. Tardos and A. Wigderson. On the power of randomization in on-line algorithms. Algorithmica, 11:2-14, 1994.

93. Daniel D. Sleator , Robert E. Tarjan, Amortized efficiency of list update and paging rules, Communications of the ACM, v.28 n.2, Feb. 1985, pp.202-208.

94. Neal Young. Competitive paging and dual-guided on-line weighted cachingand mathing algorithms. Ph Doctor Thesis. Princeton University, October 1991, p. 69.

95. Neal Young. The K-Server Dual and Loose Competitiveness for Paging. Algorithmica 11(6): 525-541, 1994.

96. Octavian Procopiuc. NEC TR 23-34-98. Randomization in on-line algorithms. April 1998, p. 17.

97. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. -М.-МЦНМО, 2000.-960 с.

98. А.С. Yao. Probabilistic Computations: Towards a unified Measure of Complexity. In Procs. of the 17th Annual Symposium on Foundations of Computer Science, 1977, pp. 222-227.

99. Цымблер M.Jl. Методы построения программного комплеса для управления данными в вычислительных системах с массовым параллелизмом. Диссертация на соискание уч. ст. канд. физ.-мат. наук, Челябинский государственный университет, 2000.

100. Оре О. Теория графов.-М.:Наука, Главная редакция физико-математической литературы, 1980.—336с.

101. Lend А.Н., and Doig A.G. An automatic method of solving discrete programming problems. Econometrica 28, 1960, pp. 497-520.

102. Little J.D.C., Murty K.G., Sweeney D.W., and Karel C. An algorithm for the traveling salesman problem. Operations Research 11, 1963, pp. 972-989.

103. Липский В Комбинаторика для программистов -М.:Мир, 1988, 213 с.

104. Мухачёва Э. А., Рубинштейн Г. Ш. Математическое программирование. -Новосибирск:Наука, 1977.-320 с.

105. Рейнгольд Э., Нивергельт Ю. , Део Н. Комбинаторные алгоритмы. Теория и практика. -М:Мир, 1980.-480 с.

106. Elizabeth Shriver, Christopher Small, and Keith A. Smith. Why does file system prefetching work? In USENIX 1999 Annual Technical Conference, Monterey, С A, June 1999, pp. 71-84.

107. Копылов И.В. К задаче оптимального размещения файлов в иерархической памяти ЭВМ. М., Рукопись деп. в ВИНИТИ, № 724-ВОО,2000. -8 с.

108. Айвазян С.А., Бухштабер В.М., Енюков И.С., Мешалкин Л.Д. Прикладная статистика: Исследование зависимостей. М.: Финансы и статистика, 1985. -471 с.

109. Андерсен Т. Статистический анализ временных рядов. М: Мир, 1976756 с.

110. Тюрин Ю. Н., Макаров А. А. Статистический анализ данных на компьютере. -М.:Инфра-М, 1998.-528 с.

111. Бокс Дж., Дженкинс Г. Анализ временных рядов. Прогноз и управление.-М.:- Мир, 1974. -197 с.

112. Лукашин Ю.П. Адаптивные методы краткосрочного прогнозирования. -М.:Статистика, 1979.-254 с.

113. Страуструп Б. Язык программирования С++. Часть вторая. Пер. с англ. Киев: «ДиаСофт», 1993. - 296 с.

114. Anthony LaMarca, Richard Е. Ladner. The Influence of Caches on the Performance of Sorting. J. Algorithms 31(1), 1999, pp.66-104.7» 24, \0 2002 г.

115. УТВЕРЖДАЮ .иректрр ГосНИИСИ1. Ю.М. Кузнецов1. АКТо внедрении программного продукта

116. ЗАО «Мобилком» приняло от Копылова И.В. программный пакет SmartCache, реализующий оптимальное кэширование и упреждение данных.

117. АКБ «Жилкоммунбанк» (ЗАО) принял от Копылова И.В. программный пакет SmartCache, реализующий оптимальное кэширование и упреждение данных.

118. Председатель комиссии: Худиева А.Р.1. Члены комиссии:1. Бекоева А.И.1. ADAMON BANK INC.

119. Stanislavsky st., Vladikavkaz, North Ossetia Alania, 362040 RUSSIAtel.: (867-2) 74-12-78, 74-13-55 fax [phone], 53-67-81

120. АКБ «Адамон Банк» принял от Копылова И.В. пакет программ SmartCache, реализующий декомпозицию файлов данных, их кэширование и упреждение.

121. Гутиевой Ф.Х. Цахилова И.А. Сорокин С.В.черный Коммерческий Банк АДАМОН БАНК1. ADAMON BANK Incorporated