Разработка и анализ математических моделей и алгоритмов динамического распределения памяти в задачах управления стеками

• Автор: Лазутина, Анна Александровна
• Шифр специальности: 05.13.18
• Научная степень: Кандидатская
• Год защиты: 2006
• Место защиты: Петрозаводск
• Количество страниц: 146 с. : ил.

Оглавление
Введение

1 Оптимальное управление тремя стеками в памяти одного уровня

1.1 Постановка задачи

1.2 Последовательное представление.

1.3 Представление трех стеков, как четырех

1.3.1 Математическая модель и матрица вероятностей переходов .

1.3.2 Результаты численных экспериментов

1.4 Связанное представление

1.4.1 Математическая модель и матрица вероятностей переходов .

1.4.2 Результаты численных экспериментов

1.4.3 Сравнение связанного и последовательного представлений .
1.4.4 Случай, когда размер информационной части произвольный .
1.5 Страничное представление.
1.5.1 Оптимальный размер страницы.
1.5.2 Математическая модель.
1.5.3 Результаты численных экспериментов
1.С Заключение.
2 Оптимальное управление четырьмя стеками в памяти одного уровня
2.1 Постановка задачи.
2.2 Связанное представление четырех стеков в памяти одного уровня .
2.2.1 Математическая модель и матрица вероятностей переходов
2.2.2 Результаты численных экспериментов.
2.3 Страничное представление
2.3.1 Оптимальный размер страницы
2.3.2 Математическая модель
2.3.3 Результаты численных экспериментов.
2.4 Последовательное представление четырех стеков в памяти одного уровня.
2.4.1 Математическая модель
2.4.2 Результаты численных экспериментов.
2.4.3 Сравнение связанного и последовательного представлений
2.4.4 Случай, когда размер информационной части произвольный
2.5 Заключение
3 Оптимальное управление тремя стеками в случае параллельного выполнения операций
3.1 Случай, когда возможны параллельные включения или параллельные исключения.
3.1.1 Последовательное представление.
3.1.1.1 Три стека, допускающих только включения . .
3.1.1.2 Общий случай .
3.1.1.2.1 Математическая модель.
3.1.1.2.2 Результаты численных экспериментов
3.1.2 Связанное представление
3.1.2.1 Математическая модель
3.1.3 Случай, когда длина информационной части имеет произвольный размер.
3.1.4 Страничное представление.
3.1.4.1 Оптимальный размер страницы .
3.1.4.2 Математическая модель
3.1.4.3 Результаты численных экспериментов
3.2 Случай, когда возможны не более двух параллельных операций, включение и исключение.
3.2.1 Последовательное представление.
3.2.1.1 Математическая модель
3.2.2 Связанное представление
3.2.2.1 Математическая модель
3.2.3 Случай, когда длина информационной части имеет произвольный размер.
3.2.4 Страничное представление.
3.2.4.1 Математическая модель
3.2.5 Результаты численных экспериментов.
3.3 Заключение.
4 Немарковская модель управления одним стеком в двухуровневой памяти
4.1 Постановка задачи
4.2 Математическая модель
4.3 Матрица переходных вероятностей
4.4 Результаты численных экспериментов.
Заключение
Литература


В данной работе построены математические модели этих двух способов представления стеков и сравнение этих способов с точки зрения среднего времени работы до переполнения. Существует большое количество устройств с ограниченными ресурсами памяти. Это мобильные устройства, встраевыемые системы, бортовые и промышленные компьютеры, системы реального времени, сетевые устройства и т. В своей работе они активно используют стековую архитектуру. Поэтому для подобных устройств актуально не только грамотное управление памятью как таковой, но и управление конкретными структурами данных, в частности, стеками. Это позволит повысить эффективность их работы и снизит затраты на производство. В последнее время вычислительная техника достигла небывалых высот. Наряду с многопроцессорными системами широкое распространение получили системы, основанные на многоядерных процессорах. Это могут быть мощные вычислительные серверы со множеством процессоров и однопроцессорные персональные компьютеры []. В работе построена модель поведения трех стеков в памяти одного уровня при наличии двух или трех процессоров. В связи с вышеизложенным, построение математических моделей поведения одного или нескольких стеков в памяти одного или двух уровней, а также с учетом возможного параллельного выполнения операций, является важной и актуальной задачей. Цель работы — построение математических моделей и алгоритмов оптимального управления стеками, с точки зрения максимизации среднего времени до переполнения одного из стеков в памяти одного уровня и максимизации среднего времени работы до перераспределения одного стека в памяти двух уровней. Математические модели, описывающие поведение трех стеков в памяти одного уровня для следующих вариантов представления стеков: последовательное представление трех стеков как четырех, связанное, страничное представление. Математические модели, описывающие поведение четырех стеков в памяти одного уровня для следующих способов представления стеков: последовательное, связанное, страничное представление. Математические модели, описывающие поведение трех стеков в памяти одного уровня в случае параллельного выполнения операций для следующих способов представления стеков: последовательное, связанное, страничное представление. Немарковская модель поведения одного стека в двухуровневой памяти в случае, когда вероятность операции, которая будет произведена со стеком на следующем шаге, зависит от того, какая операция была произведена на текущем шаге, для трех алгоритмов управления верхушкой стека. Пакет программ, реализующий рассмотренные в работе математические модели. Пакет разработан на C++ для суперкомпьютера IBM pSeries0(Regatta), установленного на ВМК МГУ им. М.В. Ломоносова. Научная новизна и практическая ценность. В работе предложены новые математические модели поведения трех и четырех стеков в памяти одного уровня, а также трех стеков в случае параллельного выполнения операций в памяти одного уровня. Получены выводы об эффективности основных способов представления стеков с точки зрения максимизации среднего времени работы, в предположении, что известны вероятностные характеристики стеков. Предложена новая математическая модель, описывающая поведение одного стека в двух уровневой памяти, когда вероятность операции, которая будет произведена со стеком на следующем шаге, зависит от того, какая операция была произведена на текущем шаге. Разработан пакет программ, реализующий рассмотренные в работе математические модели. Предложенные в работе алгоритмы могут быть использованы при разработке аппаратного и программного обеспечения ЭВМ со стековой организацией памяти и при реализации алгоритмов работы со стеками на обычных ЭВМ. Апробация работы. Основные материалы диссертации представлялись на Пятом Международном Конгрессе по математическому моделированию (Дубна, г. V международной конференции "Дискретные модели в теории управляющих систем"(Ратмино, г. IV Всероссийском симпозиуме по прикладной и промышленной математике (Летняя сессия. Петрозаводск, июнь г. Осенняя сессия. Сочи, октябрь г. Первой Всероссийской научной конференции "Методы и средства обработки информации" (Москва, г.