Оглавление
Введение
1 Динамическое распределение памяти
1.1 Базовые структуры данных
1.1.1 Линейные списки.
1.1.2 Стеки, очереди и деки.
1.1.3 Последовательное представление стека
1.1.4 Последовательное представление очереди .
1.1.5 Связанное представление линейных списков .
1.1.6 Список свободной памяти.
1.1.7 Последовательное представление нескольких
линейных списков.
1.1.8 Бинарные деревья
1.1.9 Произвольные деревья
1.1. Применение динамических структур в машинной графике.
1.1. Другие области применения стеков и очередей
1.1. Применение очередей в 1Ш1Хподобных системах .
1.2 Виртуальная память
1.2.1 Развитие способов адресации .
1.2.2 Организация обмена информацией между
уровнями памяти
1.2.3 Фрагментация памяти.
1.2.4 Методы динамического распределения нестраничной памяти.
1.3 Применение стеков в процессорах
1.3.1 Классификация стековых компьютеров
1.3.2 Методы управления памятью в стековых компьютерах.
1.3 3 Управление регистровыми окнами в ШБС
процессорах
2 Оптимальное управление стеками
2.1 Оптимальное управление одним стеком в двухуровневой памяти.
2.1.1 ЛЫнимизация среднего числа перераспределений стека
2.1.2 Минимизация среднего времени доступа с учетом потерь на перераспределения стека . .
2.2 Немарковская модель поведения стека .
2.2.1 Максимизация среднего времени .
2.2.2 Минимизация средних затрат времени с учетом перераспределения
2.3 Решение задачи Д. Кнута о двух стеках, растущих
навстречу друг другу
2.4 Оптимальное управление двумя стеками, растущими навстречу друг другу в двухуровневой памяти . .
2.4.1 Минимизация среднего числа перераспределений стеков .
2.4.2 Минимизация среднего времени доступа с учетом потерь на перераспределения стеков .
2.4.3 Оптимальное управление двумя параллельными стеками
2.5 Оптимальное расположение п стеков в памяти
2.6 Оптимальное распределение п стеков в памяти одного уровня .
2.6.1 Оптимальное начальное распределение памяти
2.6.2 Случай п3
2.6.3 Оптимальное управление тремя стеками, допускающими только включения
2.6.4 Оптимальное управление четырьмя стеками,
допускающими только включения.
2.6.5 Оптимальное управление тремя стеками в
общем случае
2.6.6 Оптимальное распределение четырех и более
стеков в одноуровневой памяти
2.6.7 Оптимальное управление тремя стеками, ко
гда два стека растут навстречу друг другу, а третий растет навстречу им обоим одновременно
2.6.8 Математическая модель связанного метода
представления трех стеков.
2.6.9 Математическая модель страничного представления трех стеков
2.7 Оптимальное управление тремя стеками в двухуровневой памяти
2.8 Оптимальное управление п 4 стеками в двухуровневой памяти
3 Оптимальное управление очередями
3.1 Оптимальное управление одной очередью в двухуровневой памяти
3.1.1 Параметризованная реализация циклической
очереди в двухуровневой памяти
3.1.2 Математическая модель
3.1.3 Результаты вычислений
3.2 Оптимальное управление двумя циклическими оче
редями в случае раздельной реализации.
3.2.1 Оптимальное управление двумя циклическими очередями в случае раздельной реализации, когда разрешены только включения в очереди.
3.3 Математическая модель связанного представления двух очередей .
3.4 Математическая модель страничного представления двух очередей .
3.4.1 Выбор оптимального размера страницы
3.4.2 Матрица переходных вероятностей.
3.5 Численные результаты.
3.6 Оптимальное управление двумя очередями в случае, когда очереди двигаются друг за другом по кругу . .
3.6.1 Результаты экспериментов
3.7 Оптимальное управление к очередями в памяти одного уровня
3.8 Оптимальное управление очередями в общей памяти в случае, когда очереди принадлежат разным процессам
3.8.1 Случай раздельной последовательной циклической реализации.
3.8.2 Случай, когда очереди двигаются друг за другом по кругу.
3.9 Оптимальное управление очередями в общей памя
I ти в случае бесконечного времени блуждания
4 Оптимальные методы распределения памяти сегментами разных длин
4.1 Оценка минимального размера памяти, необходимого для динамического распределения сегментов разных длин
4.2 Оценка эффективности методов динамического распределения нестраничной памяти
4.2.1 Модель метода II.
4.2.2 Модель метода I
4.2.3 Модель метода ОРТI.
4.2.4 Модель метода динамического распределения памяти в ОС ЕС ЭВМ.
4.2.5 Анализ численных результатов
Приложение. Результаты численных экспериментов
Приложение 1. Результаты тестирования программ
Приложение 2. Анализ результатов
Литература
- Київ+380960830922