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

• Автор: Воробьев, Павел Евгеньевич
• Шифр специальности: 05.13.15
• Научная степень: Кандидатская
• Год защиты: 2010
• Место защиты: Москва
• Количество страниц: 123 с. : ил.

ВВЕДЕНИЕ

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

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

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

1.2. Флэш НАКОПИТЕЛИ

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

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

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

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

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

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

1.5. Краткий обзор литературных источников
1.6. Динамика развития аппаратно-программных средств кэширования данных
1.7. Выбор направления исследований, содержательная постановка
и систематизация задач
1.8. Заключение
ГЛАВА 2. МАТЕМАТИЧЕСКИЙ АППАРАТ ПОИСКА ЭФФЕКТИВНЫХ СТРАТЕГИЙ РАЗМЕЩЕНИЯ ИНФОРМАЦИОННЫХ МАССИВОВ НА ВНЕШНИХ НОСИТЕЛЯХ
2.1. оптимальное размещение информационных массивов в памяти на магнитных
лентах для случая двунаправленного поиска
2.1.1. Стратегия поиска данных на магнитной ленте с возвратом в начальное положение
2.1.2. СТРАТЕГИЯ управления магнитной лентой, осуществляющей поиск без возврата в исходное положение
2.1.3. Двунаправленный поиск и однонаправленное считывание
2.2. Оптимизация размещения ИМ при независимых обращениях
2.3. Приближенное решение задач оптимального размещения ИМ в общем случае..
2.4. Управление внешними накопителями при нестационар!юй статистике
обращений
2.5. Заключение
ГЛАВА 3. ОПТИМАЛЬНЫЕ СТРАТЕГИИ КЭШИРОВАНИЯ ДАННЫХ
3.1. Формальные постановки задач оптимального кэширования
3.2. Аналитический аппарат поиска оптимальных с тратегий кэширования
3.3. Заключение
ГЛАВА 4. ЭКСПЕРИМЕНТАЛЬНАЯ ПРОВЕРКА ПОЛУЧЕННЫХ ЗАВИСИМОСТЕЙ
4.1. Традиционная оценка эффективности стратегий кэширования данных
4.1.1. Детерминированные алгоритмы замещения
4.1.2. Рандомизированные алгоритмы замещения
4.1.3. Экспериментальная оценка эффективности системы кэширования по
числу промахов
4.2. Оценка эффективности стратегий кэширования данных учитывающая их специфику
4.2.1. Процедура экспериментальной проверки полученных аналитически результатов
4.2.2. Эффективность оптимизации размеров блоков кэширования
на базе системы (3.14)
4.2.3. Эффективность оптимизации размеров блоков кэширования
на базе системы (3.19)
4.3. Заключение
ЗАКЛЮЧЕНИЕ
ЛИТЕРАТУРА

Введение
Значительный рост производительности процессоров и уменьшение времени цикла оперативной памяти- привели к тому, что обработка запросов ввода/вывода стала критической в эффективности вычислительных систем. Улучшение технических характеристик аппаратных средств ЭВМ, емкость внешней памяти в которых возросла до сотен терабайт, по экстенсивному пути развития ограничено технологическими возможностями и уровнем развития конструкторской базы, прежде всего, из-за присущих механическим носителям физических ограничений. Вследствие этого данный метод повышения, производительности компьютеров теряет свою привлекательность и заставляет искать другие пути повышения производительности вычислительных машин.
Кроме того, с ростом сложности, а также размерности технических и научных задач возрастают требования к объему внешней» памяти. Воет объема» памяти в свою очередь приводит к большим, физическим размерам носителей и препятствует снижению времени доступа и увеличению скорости передачи данных в такой памяти.
Таким образом, стремление добиться максимальной производительности вычислительных систем при заданных ограничениях на ресурсы аппаратных средств приводит к необходимости реализации собственных, специфичных для конкретного приложения алгоритмов ввода/вывода и, следовательно, неразрывно связано с повышением научно-технического уровня проектирования, включающего оптимизацию организации данных и программного обеспечения на основе изучения объемов и количества баз данных, методов доступа к данным, связей между данными, особенностей жизненного цикла данных, анализа потока обращений к внешним носителям.
Однако до настоящего времени решение подобного рода задач технического проектирования и программирования в основном базировалось на опыте и интуиции разработчиков. Такой эмпирический подход уже на ранних стадиях разработки мог внести ошибки в решения, устранение большинства
головок для считывания оставшихся дорожек в кэш, заставляя процессор простаивать в ожидании диска и контроллера.
Контроллер IBM 3880 Model 23 преодолел подобные ограничения реализацией возможности одновременной передачи данных от DASD к кэшу и из кэша к системной шине. Помимо этого объём внутренней памяти был увеличен до 64 Mb с добавлением двух режимов работы: последовательным, подразумевающем простое упреждение следующей дорожки, и bypass-cache -режимом, предполагающем прямую передачу данных, минуя кэш.
Sperry Univac Cache/Disk System, STC 8890 Disk/Cache Buffer Control Unit, Amperif Cache Disk System - продукты, подобные описанным выше.
Сегодня обычной практикой является реализация аппаратного кэша объёмом 521КЬ-2МЬ для дешевых моделей рабочих станций такими производителями как Western Digital, Seagate, Samsung, IBM, HP и др.
SmartDrive, Norton Disk Cache - также широко. распространённые утилиты кэширования для персональных компьютеров первого поколения [7].
1.7 Выбор направления исследований, содержательная постановка и систематизация задач
Общность задач кэширования файлов и управления виртуальной памятью {swap-файлом, swap-разделом), далее просто свопингом, значительно сказалась на изучении эффективных стратегий кэширования: результаты, получаемые в исследованиях и экспериментах применительно к странично организованной виртуальной памяти, как правило, распространялись и на механизмы кэширования, что на наш взгляд не совсем верно. Несмотря на одну цель - минимизацию числа обращений к внешним носителям, или в терминах кэш-менеджера - минимизацию доли промахов, природа кэширования и свопинга различна:
1. Эффективность свопинга определяется, как правило, наличием устойчивого рабочего множества [9, 86-88] страниц виртуальной памяти