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

• Воробьев, Павел Евгеньевич
• кандидат технических наук
• 2010

Оглавление диссертации кандидат технических наук Воробьев, Павел Евгеньевич

ВВЕДЕНИЕ.ОШИБКА! ЗАКЛАДКА НЕ ОПРЕДЕЛЕНА.

ГЛАВА 1 ВНЕШНИЕ НАКОПИТЕЛИ ИНФОРМАЦИИ И ИХ

ПРОИЗВОДИТЕЛЬНОСТЬ.

1.1. Оптические накопители данных.

1.2. Флэш накопители.

1.3. Дисковые накопители.

1.4. Способы повышения производительности внешних i 1акопителей.

1.4.1 Кэширование файлов, размещенных на внешних носителях.

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

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

1.4.4 Распараллеливание поиска на дисковых накопителях.

1.5. Краткий обзор литературных источников.

1.6. Динамика развития аппаратно-программных средств кэширования данных.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

При этом применялись:

• метод множителей Лагранжа, который, применительно к исследовавшимся моделям, гарантировал глобально оптимальное решение, причем полученное не итеративно, а аналитически, т. е. с минимальными временными затратами;

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

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

• подходы, применяемые в комбинаторном программировании, которые были использованы для доказательства теорем третьей главы.

На защиту выносятся:

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

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

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

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

Апробация и реализация« работы. Основные положения* диссертации^ докладывались на семинарах ФГУ ГНИИ ИТТ «Информика», на!Всероссийской научно-методической конференции- «Телематика» (Санкт-Петербург,

2007,2008,2009), на международных конференциях «ИТ-технологии: развитие и приложения», Владикавказ, 2008 и 2009 годы, на международной научной конференции «Информационные технологии и системы. Наука и практика»,

Владикавказ 2009 год, на* семинарах кафедры автоматизированной обработки информации Северо-Кавказского горно-металлургического института государственного технологического университета) г. Владикавказ.

Разработанные методы оптимального управления внешней и кэш— памятью и реализованное на их основе программное обеспечение внедрены» в эксплуатацию в Федеральном государственном учреждении. «Государственный научно-исследовательский институт информационных технологий и телекоммуникаций» (ФГУ ГНИИ ИТТ «ИНФОРМИКА»), Северо-Кавказском7

Горно-Металлургическом Институте (Государственный Технологический Университет), а так же в Московском государственном технологическом университете «Станкин» (МГТУ «Станкин»).

Публикации. Результаты диссертационной работы отражены в 6 опубликованных печатных работах, в том числе 1 - в рецензируемом журнале из списка ВАК РФ.

Структура и объем диссертации. Диссертация состоит из введения, четырех глав, заключения, списка литературы из 106 наименований, содержит 23 рисунка, 1 таблицы, 1 блок схемы и 123 страниц текста.

Заключение диссертации по теме «Вычислительные машины и системы», Воробьев, Павел Евгеньевич

Заключение

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

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

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

2. Разработана система математических моделей (системы (3.4), (3.17), (3.36)), предназначенных для оптимизации работы драйвера жесткого диска в различных условиях.

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

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

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

Список литературы диссертационного исследования кандидат технических наук Воробьев, Павел Евгеньевич, 2010 год

1. Бурков В. Н., Соколов В. В. Оптимальное размещение информации в памяти большого объема. Доклад на конференции «Проблемы создания больших информационных вычислительных систем и обработки информации на ЭВМ». Киев, 27—30 мая 1968 г.

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

3. Бурков В. Н. Соколов В. Б. Оптимальное размещение информационных массивов в памяти на магнитных лентах для случая двунаправленного поиска. Автоматика и телемеханика. № 4. 1969.

4. Б у р к о в В. Н. Рубинштейн М. И., Соколов В. Б. Оптимальное управление памятью большого объема, при нестационарной» статистике независимых обращений. Автоматика и телемеханика. № . 1970.

5. Воробьев П.Е. Аналитические подходы к поиску оптимальных стратегий кэширования. Материалы международной научно-технической конференции «ИТ-технологии: развитие и приложения», Владикавказ, 2008, с.33-40.

6. Воробьев П.Е. Аппаратные средства и эффективные стратегии кэширования данных. Тезисы докладов Международной научной конференции «Информационные технологии и системы. Наука и практика.» Часть 2, Владикавказ 2009, с.78 80.

7. Воробьев П.Е. Внешние накопители данных: конструкция и эксплуатация. Материалы X международной научно-технической конференции «ИТ-технологии: развитие и приложения», Владикавказ, 2009, с. 9-19.

8. Воробьев П.Е. Внешние накопители данных: конструкция и эффективная эксплуатация// Проектирование и технология электронных средств. 2009. № 1. С. 65-67.

9. Воробьев П.Е. Аналитические подходы к поиску оптимальных стратегий кэширования// Материалы IX международной научно-технической конференции ИТ-технологии: Развитие и Приложения. Владикавказ, Изд-во Фламинго, 2008. С. 33-40.

10. Воробьев П.Е. Аналитическое решение минимаксной задачи оптимального кэширования данных// Труды XV Всероссийской научно-методической конференции «Телематика 2008» Санкт-Петербург, 2008. С. 73-75.

11. Воробьев П.Е. Поиск эффективных стратегий кэширования данных// Труды XVI Всероссийской научно-методической конференции «Телематика 2009» Санкт-Петербург, 2009. С. 133-134.

12. Воробьев П.Е. Эффективная организация мониторинга горных территорий// Материалы V международной научно-технической конференции Устойчивое развитие горных территорий: проблемы и перспективы интеграции науки и образования. Владикавказ, 2004. С. 568569.

13. Воробьев П.Е. Внешние накопители данных: конструкции, программное обеспечение, эффективная эксплуатация// Материалы X международной научно-технической конференции ИТ-технологии: Развитие и Приложения. Владикавказ, Изд-во Фламинго, 2009. С. 9-18.

14. Гроппен В. О., В.В. Мазин. Эффективная реализация одной стратегии взаимодействия внешней и оперативной памяти ЭВМ Тезисы докладов XI всесоюзного совещания по проблемам управления, Ташкент, 1989 г. с. 202.

15. Гроппен В.О. Принципы решения многокритериальных задач с помощью эталонов. Труды XII Всеросийской научно- методическойконференции Телематика, Санкт Петербург, 6-9 июня 2005, том 1, стр. 125 128.

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

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

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

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

20. Ч и о с о в В. А. Задача рационального расположения массивов информации на магнитной ленте. Кибернетика. № 4, 1968.

21. М. G. Baker, J.H. Hartman, М. D. Kupfer, J. К. Ousterhout. Measurements of a Distributed File System, In Proc. the 13th Symp. on Operating System Principles, Pasific Grove, CA, October 1991, p. 198-212.

22. Kavita Bala, M. Frans Kaashoek, William E. Weihl. Software prefetching and caching for translation lookaside buffers.

23. Rakesh Barve, Edward F. Grove, Jeffrey Scott Vitter. Application Controlled Paging for a Shared Cache. In Proc. of the 36th Annual Symposium on Foundations of Computer Scince, October 1995, 204-213.

24. Rakesh Barve, Mahesh Kallahalla, Peter J. Varman, Jefferey Scott Vitter. Competitive Parallel Disk Prefetching and Buffer Management. In Proc. of the 5th Annual Workshop on I/O in Parallel and Distributed Systems.

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

26. Prabuddha Biswas, K. K. Ramakrishnan, Don Towsley, C. M. Krishna. Perfomance Benefits of None-Volatile Caches in Distributed File Systems.

27. Avrim Blum, Merrick L. Furst, Andrew Tomkins. What to do with your free time: algorithms for requests and randomized weighted caching.

28. Peter Bosch, Sape Mullender. Extensive Write Caching. Broadcast Technical Report, Esprit Basic Research Project 6360, October 21, 1994.

29. Jose Carlos Brustoloni, Peter Steekiste. Application-Allocated IO Buffering with system-allocated perfomance. Technical Report CMU-CS-96-169, School of Computer Science, Carnegie Mellon University, August 1996.

30. P. Cao and E. 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.

31. Pei Cao. Allocation Policies for Application-Controlled File Cache Management. Computer Sciences Department, University of Wisconsin-Madison, June 1997.

32. C. Chen and N. Roussopoulos. Adaptive database buffer allocation using query feedback. In Proc. of the 19th YLDB Conference, Dublin, Ireland, 1993.

33. 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, 1996.

34. Douglas Comer, James Griffioen. A new design for Distributed Systems: The Remote Memory Model. Technical Report CSD-TR-977, Department of Computer Science Purdue University West Lafayette.

35. Douglas Comer, James Griffioen. Efficient Order-Depended Communication in a distributed virtual memory memory environment. In Proc. in the Symposium on Experience with Distributed and Multiprocessor Systems (SEDMS) III, March 1992.

36. Thomas H. Cormen, David Kotz. Integrating Theory and Practice in Parallel File Systems. DAGS 1993 Symposium on Parallel I/O and Databases.

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

38. 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.

39. 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.

40. Michael D. Dahlin, Clifford J. Mather, Randolph Y. Wang, Thomas E. Anderson, and David A. Patterson. A quantitative analysis of cache policies forscalable network file system. Computer Science Division, University of California at Berkeley.

41. Michael D. Dahlin, Randolph Y. Wang, Thomas E. Anderson, David A. Patteron. Cooperative Caching using Remote Client Memory to Improve File System Perfomance. In Proc. of the First Symposium on Operating Systems Design and Implementation (OSDI 1994).

42. Steve Dropsho, Chip Weems. Comparing Caching Techniques for Multitasking Real-Time Systems. Computer Science Department, University of Massachussets-Amberst, April 30,1997.

43. Christine Fricker, Philippe Robert. An analytical cache model. INRIA, domaine de Voluceau B.P. 105, 78153 Le Chesnay Cedex, France. Septembre 1991.

44. Gregory R. Ganger, Yale N. Patt. Metadata Update Perfomance in File Systems. In Proc. of the First USENIX Symposium on Operating Systems Design and Implementation, November 1994, pp.49-60.

45. 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.

46. J. Griffioen and R. Appleton. Reducing File System Latency Using a Predictive Approach. In Proc. 1994 USENIX Summer Conf., June 1994, p. 197207.

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

48. 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.

49. 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.

50. Tracy Kimbrel. Parallel Prefetching and Caching. Computer Science Department, University of Washington, 1997.

51. Trace Kimbrel, Anna R. Karlin. Near-Optimal Parallel Prefetching and Caching. In Proc. of the 1996 IEEE Symposium on Foundation of Computer Science, October, 1996, p. 64,181.

52. 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.

53. David Kotz, Nils Nieuwejaar. Dynamic File-Access Characteristics of a Production Parallel Scientific Workload. Technical Report PCS-TR-94-211, Department of Computer Science Dartmouth College, August 3, 1994.

54. David Kotz, Carla Schlatter Ellis. Caching and Writeback Policies in Parallel File Systems. Dept. of Math and Computer Science, Darthmouth College Hanover.

55. D. Kotz and C. S. Ellis. Practical Prefetching Techniques for Parallel File Systems. In Proc. First Intl. Conf. on Parallel and Distributed Information Systems, December 1991, p. 182-189 ACM.

56. P. Krishnan. Online Prediction Algorithms for Databases and Operating Systems.

57. 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.

58. Thomas M. Kroeger. Predicting file system actions from reference patternce. CS department University of California Santa Cruz, December 1996.

59. Thomas M. Kroeger and Darreil D. E. Long. Predicting File System Actions from Prior Events. Department of Computer & Information Sciences University of California, Santa Cruz, 1996.

60. Thomas M. Kroeger, Darreil D. E. Long, Jeffrey C. Mogul. Exploring the Bounds of Web Latency Reduction from Caching and Prefetching. Department of Computer Engineering University of California, Santa Cruz.

61. 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.

62. Geoffrey H. Kuenning. The design of the Seer predictive caching system.

63. Chao-Hsien Lee, Meng Chang Chen and Ruei-Chuan Chang. HiPEC: High Perfomance External Virtual Memory Cahing. Department of Computer and Information Science, National Chiao Tung University, Taiwan, ROC.

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

65. Kester Li. Towards A Low Power File System.

66. Tara M. Madhyastha, Christopher L. Elford, Daniel A. Reed. Optimizing Input/Output Using Adaptive File System Policies.

67. Tara M. Madhyastha, Daniel A. Reed. Exploiting Global Input/Output Access Pattern Classification. Department of Computer Science, University of Illinois, Urbana.

68. Tara 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.

69. Chris Metcalf. Data prefetching: a cost/perfomance analysis. Laboratory for Computer Science Massachusetts Institute of Technology, Cambridge.

70. Ethan L. Miller. Input/Output Behavior of Supercomputing Applications.

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

72. Todd C. Mowry, Monica S. Lam, and Anoop Gupta. Design and evaluation of a compiler algorithm for prefetching. In The Fifth International Conference on Architectural Support for Programming Languages and Operating Systems, October 1992, p.38.

73. Todd C. Mowry, Chi-Keung Luk. Predicting Data Cache Misses in Non-Numeric Applications through Correlation Profiling. Technical Report CMU-CS-97-175, School of Computer Science, Carnegie Mellon University, Pittsburg, September 1997.

74. 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 Proc. of the 10th Symp. on Operating System, December 1985, p. 15-24.

75. Vivek S. Pai, Peter Druschel, Willy Zwaenpoel. IO-Lite: A unified I/O buffering and caching system. CS Technical Report TR97-291, Rice University, 1997.

76. Russel Hugo Patterson III. Informed Prefetching and Caching. Technical Report CMU-CS-97-204, School of Computer Science Carnegie Mellon University Pittsburgh,, December 1997.

77. 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.

78. R. Hugo Patterson, Garth A. Gibson, M. Satyanarayanan. A Status Report on Research in Transparent Informed Prefetching. Technical Report CMU-CS-93-113, School of Computer Science Carnegie Mellon University, February 1993.

79. 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.

80. 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. 329-342.

81. R. H. Patterson, G. A. Gibson, E. Ginting, D. Stodolsky and J. Zelenka. Informed Prefetching and Caching. In Proc. Fifteenth Symp. on Operating Systems Principles, December 1995, p. 79-95 ACM.

82. 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, pp. 55-68, May 1996.

83. Dan Revel, Dylan McNamee, David Steere, and Jonathan Walpole. Adaptive prefetching for Device-Independent File I/O. Department of Computer Science and Engineering, Oregon Graduate Institute of Science and Technology.

84. Kathy J. Richardson. I/O characterization and attribute cache data for eleven measured workloads. Technical Report No. CSL-TR-94-656, Computer Systems Laboratory Departments of Electrical Engineering and Computer Science Stanford University. Dec 1994.

85. 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.

86. Giovanni Maria Sacco and Mario Schkolnick. A mechanism for managing the buffer pool in a relational database system using the hot set model.

87. Proceedings of the Eighth International Conference on Very Large Data Bases, Mexico City, September, 1982.

88. Prasenj it Sarkar and John Hartman. Efficient Cooperative Caching using Hints. Department of Computer Science University of Arizona, Tucson^ AZ 85721.

89. Margo Ilene Seltzer. File System Perfomance and Transaction Suport. Computer Science Department, University of California at Berkeley, 1992.

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

91. Andrew Tomkins, R. Hugo Patterson^ and Garth Gibson. Informed multiprocess prefetching and caching. In Proc. of the SIGMETRICS'97, June 1997.

92. 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.

93. Eric Torng. A unified analysis of paging; and; caching. Department of Computer Science Michigan State University.MI 48824-1027.

94. Amin Vahdat, Thomas Anderson. Transparent Result Caching. Computer Science Division University of California, Berkeley, Department of Computer Science and Engineering, University of Washington, Seattle, 1996.

95. 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.

96. Dairy L. Willick, Derek L. Eager, and Richard B. Bunt. Disk Cache Replacement Policies for Network Fileservers. Department of Computational Science, University of Saskatchewan, Saskatoon, October 13,1992.

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

98. Barbara Tockey Zivkov, Alan Jay Smith. Disk Caching in Large Databases and Timeshared Systems. Computer Science Division, University of California, Berkeley, September, 1996.

99. Каган Б. M., Адасько В. И., Пурэ Р. Р., Запоминающие устройства большой ёмкости, М., 1968

100. Pareto V. Cours d'Economie Politique. Lausanne: Houge, 1889.

101. Ralph Labarge. DVD Authoring and Production. CMP Books. 2001

102. Э. Таненбаум. Современные операционные системы; Modern operating systems. 2006.J