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

004615925

Воробьев Павел Евгеньевич

РАЗРАБОТКА МЕТОДОВ И АЛГОРИТМОВ ОПТИМАЛЬНОГО КЕШИРОВАБИЯ ФАЙЛОВ НА ВНЕШНИХ НОСИТЕЛЯХ

Специальность: 05.13.15 - Вычислительные машины, комплексы и компьютерные сети

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата технических наук

Москва-2010 - ^ пси ?гип

004615925

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

Научный руководитель: д.т.н., профессор Тихонов А.Н.

Официальные оппоненты: д.т.н., профессор Саксонов Е.А.

к.т.н., доцент Бычкова H.A.

Ведущая организация: Московский государственный университет приборостроения и информатики (МГУПИ)

Защита диссертации состоится <¿2/»2010г. в 14-00 часов на заседание диссертационного совета Д 212.133.03 Ъри МИЭМ: 109028, Москва, Б. Трехсвятительский пер., д. 3.

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

Автореферат разослан «30» 2010г.

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

доктор технических наук, доцент ЛеохинЮЛ.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

также объем памяти используемых компьютеров, применительно к построенным моделям;

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

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

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

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

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

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

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

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

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

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

к ним, а также объем памяти используемых компьютеров, применительно к построенным моделям;

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

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

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

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

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

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

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

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ Во введении обосновывается актуальность темы диссертационной работы, формулируется цель, научная новизна и практическая значимость полученных результатов.

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

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

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

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

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

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

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

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

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

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

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

Пусть Щ - размер ¿-го внешнего файла (Мб.);

и. - размер ¡-го кэш блока, предназначенного для кэширования

только Ьго файла (Кб., Мб.); V - объем свободной оперативной памяти (Мб.).

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

№

V/ : ■^■одлил^й7, - £/,.) -> гшп;

I и^У, (1)

I

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

-ИГ,

>,— тт;

г и,.-,.

1У,-У; »

V/ 1 < < ЖГ

(2)

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

Г,

тах—-

' и,

тт;

I

V/: 1 < С/,

(3)

Распараллеливая для сокращения времени поиск информации в п файлах т рабочими станциями однородной локальной вычислительной сети, каждая рабочая станция которой исследует «своё» подмножество файлов, можно показать, что (2) в этом случае сводится к виду:

пил;

VГ.^и^Гу,

и*,

>1

где: подмножество файлов, обследуемое ]-ой рабочей станцией

(СК-О;

Уу - объем свободной оперативной памяти j-oй рабочей стаьщии (0<3<т+1).

Рассмотрим теперь поиск решения системы (3). Заменяя целевую

функцию (3) эквивалентной шп— -> тах, преобразуем (3) к виду:

¡Ж,

■ и,

ш—-> тах: ' Г,

>

V;: 1 < и, < Щ.

(5)

Поскольку, в соответствии с последним ограничением, идеальное значение каждой переменной системы (3) отвечает верхней ее границе, равной Щ, пользуясь методом эталонов [7] система (3) может быть сведена к однокритериальной задаче вида:

1-й

"V,

I

I

2^= К;

I

V/:! <и,<ТГг

ш;

(б)

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

оперативной памяти и, одновременно, число обращений к внешним носителям. Данная задача может быть записана в виде:

>-*-¿--»Пип;

£ и, ;

п

->пип;

ы

■Р** (7)

V ¡,7^^1,0;

У/.КеА'.

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

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

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

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

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

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

Алгоритм проверки стратегии кэширования.

Используемые при проведении эксперимента обозначения: - суммарный размер кластера файлов, размещенных на внешних носителях (Мб.);

щ - размер внешних файлов (Мб.);

и, - размер кэш блока, предназначенного для кэширования ьго файла (Мб.);

V - объем свободной оперативной памяти (V = ]Г[/,) (Мб.);

»

п - число файлов на внешних носителях;

Ж, -ттЩ;

* 1 ;

IV =тахЩ;

"я I

Л =

Б - значение целевой функции систем (2) и (3) при условии, что величины кэш-блоков оптимальны;

^ - значение целевой функции систем (2) и (3) при условии, что величины всех кэш-блоков равны V/: и, /п;

V .-выигрыш в числе обращений к внешним носителям,

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

Ниже приводится пошаговое описание алгоритма:

Шаг 1. Фиксируется ранее не анализировавшееся значение т| в диапазоне от двух до десяти. Если таковых нет, то перейти к ша1у 14.

к+к

Шаг 2. Все возможные значения V в диапазоне п 2 считаем не просмотренными.

Шаг 3. Выбирается ранее не просмотренное значение V. Если таковых нет, то перейти к шагу 13.

Шаг 4.1 = 1.

Шаг 5. Вычисляется оптимальное значение объема блока кэширования и<.

Шаг 6. Если 1=п, то перейти к шагу 8, в противном случае - к шагу 7.

Шаг 7. ¡=1 И, перейти к шагу 5.

Шаг 8. Вычисляется величина Б.

Шаг 9. Вычисляется величина .Р0.

Шаг 10. Вычисление величины выигрыша у в числе обращений к внешнему носителю, вызванному оптимизацией размеров кэш-блоков по сравнению со случаем, когда все кэш-блоки имеют одинаковый объем:

Шаг 11. Печать величин у, V, ц.

Шаг 12. Перейти к шагу 3.

Шаг 13. Перейти к шагу 1. Шаг 14. Конец алгоритма. Блок-схема алгоритма приведена ниже на рис. 1.

С'-Нлягиго '•')'

О У

Рис. 1. Блок схема алгоритма.

По результатам экспериментов, включающих два направления:

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

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

сделаны следующие выводы:

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

Во втором случае, при использовании нового алгоритма, четко просматривается «область нечувствительности» системы к величине V, превышающей 0,55 Гб. (рис. 2).

V

Рис. 2. Зависимость эффективности оптимизации размеров блоков

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

Рис. 2 можно трактовать, как отсутствие необходимости прибегать к оптимизации размеров блоков кэширования данных, если их суммарный объем сравнительно «невелик».

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Подписано в печать 11.11.2WD. Фермат 60x84/16. Бумага типографская № 2. Печать - ризография. Усл. печ. л. 1,2 Тираж Ш экз. Заказ 1037.

Московский государственный институт электроники и математики 109028, Москва, БТрехсвятительский пер., 3.

Центр оперативной полиграфии (495) 916-88-04, 916-89-25

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

ГЛАВА 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. Получены экспериментальные результаты, базирующиеся на предложенной методике и фиксирующие диапазон применимости развитых в диссертации подходов.

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