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

• Автор: Копылов, Игорь Валентинович
• Шифр специальности: 05.13.01
• Научная степень: Кандидатская
• Год защиты: 2002
• Место защиты: Владикавказ
• Количество страниц: 157 с. : ил

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 Минимаксный принцип Уао
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. Библиотека кэширования и упреждения БтаПСасИе.
4.1 Структура и прикладной программный интерфейс ЗтагтСасЬе
4.1.1 Структура БтаПСасЬе
4.1.2 Прикладной программный интерфейс БшаСасЬе.
4.2 Экспериментальная проверка БтапСасЬе.
4.3 Выводы.
Заключение.
Литература


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