Содержание к диссертации
Введение
1 Математические модели и алгоритмы управления стеками в двухуровневой памяти 14
1.1 Оптимальное управление одним стеком в двухуровневой памяти 14
1.1.1 Постановка задачи 14
1.1.2 Математическая модель и матрица вероятностей переходов 17
1.1.3 Решение задачи и результаты численных экспериментов 22
1.2 Оптимальное управление двумя параллельными стеками в двух уровневой памяти 26
1.2.1 Постановка задачи 26
1.2.2 Математическая модель и матрица вероятностей переходов 27
1.2.3 Решение задачи и результаты численных экспериментов 32
2 Оптимальное управление двумя FIFO-очередями в памяти одного уровня 36
2.1 Постановка задачи 36
2.2 Связанное представление двух очередей 37
2.2.1 Математическая модель 37
2.3 Страничное представление двух очередей 38
2.3.1 Математическая модель и матрица вероятностей переходов 39
2.3.2 Оптимальный размер страницы 45
2.4 Решение задачи 46
2.5 Результаты численных экспериментов 48
3 Оптимальное управление очередью с двумя приоритетами в памяти одного уровня 51
3.1 Постановка задачи 51
3.2 Последовательное представление 52
3.2.1 Математическая модель и матрица вероятностей переходов 52
3.3 Связанное представление 58
3.3.1 Математическая модель 58
3.4 Страничное представление 60
3.4.1 Математическая модель и матрица вероятностей переходов 60
3.5 Решение задачи 66
3.6 Результаты численных экспериментов 67
4 Оптимальное управление тремя FIFO-очередями в памяти одного уровня 70
4.1 Постановка задачи 70
4.2 Последовательное представление трех очередей 71
4.2.1 Математическая модель и матрица вероятностей переходов 71
4.3 Связанное представление трех очередей 77
4.3.1 Математическая модель 78
4.4 Страничное представление трех очередей 79
4.4.1 Математическая модель и матрица вероятностей переходов 80
4.4.2 Оптимальный размер страницы 86
4.5 Решение задачи 87
4.6 Результаты численных экспериментов 89
5 Оптимальное управление тремя FIFO-очередями на бесконечном времени 92
5.1 Постановка задачи 92
5.2 Последовательное представление трех очередей 93
5.2.1 Математическая модель и матрица вероятностей переходов 93
5.3 Связанное представление трех очередей 102
5.3.1 Математическая модель 103
5.4 Решение задачи и результаты численных экспериментов . 113
Заключение 117
Литература 118
- Математическая модель и матрица вероятностей переходов
- Математическая модель и матрица вероятностей переходов
- Математическая модель и матрица вероятностей переходов
- Математическая модель и матрица вероятностей переходов
Введение к работе
В настоящее время все более востребованными становятся устройства с жесткими ограничениями на ресурсы памяти, например, различные сетевые и мобильные устройства, что вызывает особые требования к алгоритмам управления памятью. В связи с этим актуальной является задача разработки математических моделей и алгоритмов оптимального управления базовыми динамическими структурами данных, такими как стеки, очереди и приоритетные очереди.
Стеком LIFO (Last In First Out) называется линейный список, в котором все включения и исключения (и обычно всякий доступ) происходят на одном конце, который называется вершиной стека. Другой по отношению к вершине конец стека называется началом стека. Очередью FIFO (First In First Out) называется линейный список, в котором все включения происходят на одном конце (конец очереди), а все исключения (и обычно всякий доступ) происходят на другом конце (начало очереди) [25]. Под линейным списком будем понимать множество узлов, структурные свойства которого ограничиваются лишь их линейным (одномерным) относительным положением.
Понятие стека широко используется при разработке программного и аппаратного обеспечения. Стеки используются в алгоритмах синтаксического разбора [16, 34, 35], для анализа скобочной структуры текста и вычисления выражений [29], в алгоритмах машинной графики [39], в алгоритмах поиска на графах [25, 30], в алгоритмах сортировки [26, 40], в системе управления процессами [33, 38, 45], при разработке архитектуры [17, 22, 23, 27, 33, 44]. При разработке RISC процессоров для работы со скалярными аргументами и локальными переменными функций организуются перекрывающиеся окна регистров постоянного или переменного размеров [47, 51]. В этом случае получаем один стек с элементами типа "окно" в главной памяти, у которого
несколько верхних элементов образуют циклический стек на регистрах. В архитектуре Intel Itanium [60] у каждой процедуры есть регистровый стек с элементами переменного размера для хранения параметров. Выходные параметры одной процедуры являются входными параметрами другой. В процессорах Intel, Motorola и др. стек наращивается в сторону уменьшающихся значений адресов памяти. Это означает, что указателю позиции вершины того или иного стека первоначально присваивается значение самого старшего адреса области памяти, предоставляемой для организации данного стека [36, 37].
При переполнении или опустошении регистровой вершины стека на практике применяют несколько программных и аппаратных методов, которые имеют преимущества по сравнению с универсальными алгоритмами замещения кэш-памяти [51, 59]:
Large Stack. Можно сделать стек большим и предполагать, что переполнения не будет, а если оно все же произошло, то совершить аварийное завершение работы.
Demand fed single element stack manager. В этой стратегии вершина стека реализована аппаратно, как циклический буфер, а продолжение стека находится в памяти. При переполнении и опустошении аппаратного стека перемещается один элемент (или несколько элементов) в память из буфера или наоборот.
Paging stack manager. В этом методе вершина реализована программно как часть специальной памяти. При опустошении вершины стека из памяти копируется половина буфера, а при переполнении нижняя половина буфера перемещается в память, верхняя половина перемещается в начало буфера.
Barometr-Pointer Algorithm. Предлагались реализации стека, когда перемещения элементов между уровнями памяти происходят не при переполнении или опустошении, а при отклонении от оптимального состояния вершины (обычно считается, что это половина быстрого буфера) в фоновом режиме, т.е. параллельно с обычным выполнением
команд (аналог опережающей подкачки и откачки в страничной виртуальной памяти).
5. An associative cashe. Кэш-память для стековых машин не дает преимуществ по сравнению с рассмотренными методами, т.к. сложнее для аппаратной реализации и в тоже время не учитывает специфики стека как структуры LIFO. Но, если в стек нужно помещать структуры данных переменного размера, такие как строки и структуры, использование кэш-памяти может быть целесообразно.
Во всех этих методах вершина стека является продолжением стека, находящегося в памяти второго уровня.
Возможны также аппаратные методы реализации, когда вершина стека является копией стека, находящегося в памяти второго уровня. Тогда запоминание элементов при переполнении не нужно, а требуется лишь восстановление при опустошении [47].
В работах [31, 50] в качестве теоретической модели, описывающей управление вершиной стека в двухуровневой памяти, было предложено одномерное случайное блуждание [46]. На базе этой модели решалась задача определения оптимального количества элементов вершины стека в быстрой памяти, которое должно оставаться после перераспределения. Однако, некоторые специалисты [48] считают, что модель классического случайного блуждания недостаточно точно описывает поведение стеков, а более адекватной была бы модель, в которой вероятность следующей операции со стеком зависит от того, какая операция была предыдущей. Простейшая такая модель, описывающая поведение одного стека в двухуровневой памяти, предложена в [1, 7].
Если рассмотреть несколько стеков (процессов) и общий ресурс быстрой памяти, то можно показать, что встречное расположение стеков в виде пар стеков, растущих навстречу друг другу, лучше раздельного, если в качестве критерия оптимальности выбрано среднее время работы стеков до переполнения [42, 58]. Задача построения математической модели такого способа распределения памяти была поставлена Д. Кнутом [25]. Исследовалось пове-
дение двух стеков, расположенных в памяти объема т и растущих навстречу друг другу. В этом случае место встречи стеков можно рассматривать как случайную величину. Известно, что на каждом шаге с вероятностью р может произойти исключение элемента из одного из стеков, с вероятностью 1 — р может произойти включение информации в один из стеков. Пусть М{т,р) математическое ожидание случайной величины тах(к\, /^), где к\ и / длины стеков при встрече. Задача состоит в том, чтобы установить вид функции М(т,р). В [41] предложен алгоритм вычисления М(т,р) для конечных значений т. Для решения задачи использовалась теория поглощающих цепей Маркова [24]. В [61] решалась задача исследования М(т,р) при т —* со для 0.25 < р < 0.5. В [49, 52, 53] исследовалось асимптотическое поведение размеров стеков при переполнении и времени работы до переполнения памяти для 0 < р < 0.25. В [54] решалась задача для случая, когда вероятности включения и исключения информации зависят от размеров стеков. В [42, 55, 58] предложены марковские модели для решения задач управления несколькими стеками. В [14] исследовалась задача управления двумя параллельными стеками в двухуровневой памяти.
FIFO-очереди используются в компьютерных сетях, операционных системах, графических системах, устройствах промышленной автоматики. Ряд американских фирм выпускает микросхемы, реализующие работу с несколькими FIFO-очередями (IDT Inc. [32], Cypress, AverLogic Technologies). В диссертационной работе рассмотрены некоторые задачи оптимального представления нескольких FIFO-очередей в памяти одного уровня. Оптимальность понимается либо в смысле максимизации среднего времени работы до переполнения какой-либо очереди, либо в смысле минимизации доли потерянных элементов при бесконечном времени работы очередей. Первый критерий разумно применять в программных системах, когда переполнение какой-либо очереди может привести к остановке работы программы. Второй критерий уместен, например, в сетевых маршрутизаторах, когда пакеты, которые помещаются в переполненную очередь, просто теряются ("сброс хвоста") [18]. Потери пакетов приводят к нежелательному результату, поэтому число таких ситуаций необходимо свести к минимуму.
Для организации FIFO-очередей в памяти компьютера применяются два принципиально разных способа представления: последовательный и связанный [25]. Известны указатели на конец и начало очереди. В последовательном способе организации каждой очереди отводится определенная область памяти. При такой организации часто очередь зациклена, т.е. при достижении концом очереди конечной границы выделенной области памяти следующие включения элементов будут происходить с начальной границы, если есть свободная память. В связанном способе организации очередь представлена в виде связанного списка, каждый элемент которого состоит из двух единиц памяти, одна из которых используется для хранения информации, другая для хранения указателя на следующий элемент. В некоторых приложениях, например, в ряде версий операционных систем, для сетевых маршрутизаторов применяется некий промежуточный способ, когда очереди представлены в виде связанного списка буферов (страниц) одинаковой длины. В связанном представлении затраты памяти на хранение связей самые большие, в последовательном представлении таких затрат нет, но есть потери памяти за счет того, что при переполнении одной из очередей другая очередь заполнена не до конца. В страничном представлении есть затраты памяти первого и второго рода.
В работах [12, 43] рассматривались задачи оптимального управления двумя FIFO-очередями.
Во многих приложениях требуется обработка записей с упорядоченными определенным образом ключами. Часто накапливается некоторый набор записей, после чего обрабатывается запись с максимальным значением ключа, затем, возможно, накопление записей продолжается, обрабатывается запись с наибольшим текущим ключом и т. д. Соответствующая структура данных, поддерживающая операции вставки нового элемента и удаления элемента с наибольшим приоритетом, называется очередью по приоритетам [21, 28, 40].
Существуют различные способы реализации очередей с приоритетами. Одним из часто используемых способов является представление N - приоритетной очереди в виде N FIFO-очередей. Приложениями очередей по приоритетам являются системы моделирования, в рамках которых ключи
могут соответствовать моментам возникновения событий, что обеспечивает возможность их обработки в хронологическом порядке, системы планирования заданий в компьютерных системах, где ключи могут соответствовать приоритетам, указывающим, какой из пользователей должен быть обслужен первым. Метод приоритетной очереди достаточно широко используется, например, как один из аппаратно-независимых методов управления перегрузками в технологии QoS. В операционной системе Cisco IOS реализация приоритетной очереди содержит четыре различные подочереди: high, medium, normal и low priority [18].
Целью диссертационной работы является построение и анализ математических моделей и оптимальных методов реализации динамических структур данных, таких как стеки, очереди и приоритетные очереди. В качестве критериев оптимальности рассматриваются: минимальное среднее время, затрачиваемое на работу со стеком и на перераспределение памяти после переполнения или опустошения в случае работы с одним стеком в двухуровневой памяти, максимальное среднее время работы до перераспределения памяти после переполнения или опустошения в случае работы с двумя стеками в двухуровневой памяти, максимальное среднее время работы до переполнения выделенного объема памяти в случае работы с двумя и тремя FIFO-очередями и в случае работы с двухприоритетной очередью в памяти одного уровня, минимальная доля потерянных элементов при переполнении выделенного объема памяти в случае работы с тремя FIFO-очередями на бесконечном времени.
Основными результатами диссертации являются:
Математические модели, описывающие процесс работы с одним стеком и двумя параллельными стеками в двухуровневой памяти.
Математические модели, описывающие процесс работы с двумя и тремя FIFO-очередями в памяти одного уровня для последовательного, связанного и страничного способов представления.
Математические модели, описывающие процесс работы с двухприоритетной очередью в памяти одного уровня для последовательного,
связанного и страничного способов представления.
Математические модели, описывающие процесс работы с тремя FIFO-очередями на бесконечном времени в памяти одного уровня для последовательного и связанного способов представления.
Комплекс алгоритмов и программ, реализующих предложенные в работе математические модели. Для заданных критериев оптимальности определяется наилучший способ представления структур данных. Комплекс программ реализован на языке C++. Вычисления проводились на суперкомпьютере IBM pSeries690(Regatta), установленном на ВМК МГУ им. М.В. Ломоносова.
Предложены оценки эффективности основных способов представления динамических структур данных в памяти одного и двух уровней для рассмотренных критериев оптимальности. Предложенные в работе математические модели и алгоритмы являются новыми и могут быть использованы при разработке аппаратного и программного обеспечения ЭВМ.
Результаты диссертации были представлены на конференциях:
Пятый Международный Конгресс по математическому моделированию (Дубна, 2002 г.);
V международная конференция «Дискретные модели в теории управляющих систем» (Ратмино, 2003 г.);
IV Всероссийский симпозиум по прикладной и промышленной математике (Летняя сессия, Петрозаводск, июнь 2003 г.), (Осенняя сессия, Сочи, октябрь 2003 г.);
Первая Всероссийская научная конференция «Методы и средства обработки информации» (Москва, 2003 г.);
Восьмой международный семинар «Дискретная математика и ее приложения» (Москва, 2004 г.).
Шестая Международная Петрозаводская конференция «Вероятностные методы в дискретной математике» (Петрозаводск, 2004 г.);
Вторая Всероссийская научная конференция «Методы и средства обработки информации» (Москва, 2005 г.);
Российско-Скандинавский симпозиум «Теория вероятностей и ее приложения» (Петрозаводск, 2006 г.);
Девятый международный семинар «Дискретная математика и ее приложения» (Москва, 2007 г.).
Работа поддержана грантами РФФИ №01-01-0113, №03-01-06415 (MAC), №06-01-00303.
Результаты диссертации опубликованы в 9 статьях [1, 2, 3, 7, 10, 11, 12, 13, 14] и 8 тезисах докладов [4, 5, 6, 8, 9, 15, 56, 57].
Диссертационная работа состоит из введения, пяти глав, заключения и списка литературы. В первой главе рассматриваются задачи оптимального управления стеками в двухуровневой памяти. Предлагается и исследуется математическая модель поведения стека, когда вероятность операции, которая будет произведена со стеком на следующем шаге, зависит от операции, произведенной на текущем шаге. В качестве критерия оптимальности рассматривается минимальное среднее время, затрачиваемое на работу со стеком и на перераспределение памяти после переполнения или опустошения. Также, предложена и исследуется математическая модель оптимального управления двумя параллельными стеками. Предполагается, что вершины двух стеков растут навстречу друг другу в быстрой памяти, к которой разрешен доступ нескольких параллельных процессов. Для описания процесса работы со стеками предлагается и исследуется модель в виде случайного блуждания по целочисленной решетке в двухмерном пространстве. В качестве критерия оптимальности рассматривается максимальное среднее время работы со стеками до перераспределения памяти после переполнения или опустошения.
Во второй главе рассматривается задача оптимального управления двумя очередями в памяти одного уровня. Исследуются связанный и страничный способы организации двух очередей. Для описания процесса работы с очередями предлагаются и исследуются математические модели в виде слу-
чайного блуждания по целочисленной решетке в двухмерном пространстве. В качестве критерия оптимальности рассматривается максимальное среднее время работы с очередями до переполнения выделенного объема памяти.
В третьей главе рассматривается задача оптимального управления очередью с двумя приоритетами в памяти одного уровня. Исследуются последовательный, связанный и страничный способы организации приоритетной очереди. Для описания процесса работы с очередью предлагаются и исследуются математические модели в виде случайного блуждания по целочисленной решетке в двухмерном пространстве. В качестве критерия оптимальности рассматривается максимальное среднее время работы с очередью до переполнения выделенного объема памяти.
В четвертой главе рассматривается задача оптимального управления тремя очередями в памяти одного уровня. Исследуются последовательный, связанный и страничный способы организации трех очередей. Для описания процесса работы с очередями предлагаются и исследуются математические модели в виде случайного блужданияпо целочисленной решетке в трехмерном пространстве. В качестве критерия оптимальности рассматривается максимальное среднее время работы с очередями до переполнения выделенного объема памяти.
В пятой главе рассматривается задача оптимального управления тремя очередями на бесконечном времени, когда при переполнении какой-либо из очередей работа завершена не будет, а поступающие элементы будут удаляться из очереди. Исследуются последовательный и связанный способы организации трех очередей. Для описания процесса работы с очередями предлагаются и исследуются математические модели в виде случайного блуждания по целочисленной решетке в трехмерном пространстве. В качестве критерия оптимальности рассматривается минимальная доля потерянных элементов при переполнении выделенного объема памяти.
Математическая модель и матрица вероятностей переходов
В качестве математической модели рассмотрим случайное блуждание на прямой (рис. 1.5), где координата точки соответствует количеству элементов в стеке. Пронумеруем состояния сначала из г в г + 1, т.е. (г, г + 1), затем обратно в г из г + 1, т.е. (г + 1,г), начиная с младшего номера. Если размер памяти равен т, то состояний будет 2га, их нумерация будет такая: (0,1)(1,0)(1,2)(2,1)...(г,г + 1)(г + 1,1)...(га - 1,га)(га,т - 1). Поглощающими будут состояния (0, —1) и (m,ra + 1). Начальное состояние XQ будем обозначать номером этого состояния 0 і т. При введенной нумерации получаем конечную однородную поглощающую цепь Маркова, в которой количество невозвратных состояний равно 2т + 1 (2т пар и начальное состояние), количество поглощающих состояний равно 2.
Пусть известно время обмена информацией между уровнями памяти. Обозначим время доступа к вершине стека в быстрой памяти to, время перемещения одного элемента в быстрой памяти ti, время доступа к памяти второго уровня t2, время обмена одним элементом между уровнями памяти tz- Предполагаем, что потери времени при перемещении элементов пропорциональны числу перемещаемых элементов.
Рассмотрим средний коэффициент потерь, введенный в теории кэшпамяти [51], который равен процентному отношению обращений к памяти, при которых приходилось вызывать данные из дополнительной памяти, к общему числу обращений. Например, если коэффициент потерь равен 1% (т.е. 1/100 обращений приходится к памяти второго уровня, а 99/100 к памяти первого уровня), то время доступа к памяти второго уровня 2, включая передачу данных, в 100 раз больше времени доступа к памяти первого уровня о- Тогда средняя скорость вычислений будет составлять примерно половину той скорости, которая была бы, если бы все данные
Первая строка соответствует начальному состоянию. Она будет состоять из нулей, т.к. начальным состоянием будет 1, а из него нельзя попасть в поглощающие операцией включения или исключения элемента в стек (вероятность перехода из 1 в (0,-1) равна 0, вероятность перехода из 1 в (2,3) равна 0) (рис. 1.6). Так как всего два поглощающих состояния, то в матрице будет всего два ненулевых элемента. Из поглощающих состояний нельзя вернуться в предыдущее, значит, в матрице не будет элементов, равных вероятности возврата р\ и рг-Рассмотрим вероятности переходов: из (0,1) в (0,-1) вероятность перехода равна 0, из (0,1) в (2,3) вероятность перехода равна 0, из (1,0) в (0,-1) вероятность перехода равна qi, из (1,0) в (2,3) вероятность перехода равна 0, из (1,2) в (0,-1) вероятность перехода равна 0, из (1,2) в (2,3) вероятность перехода равна #2, из (2,1) в (0,-1) вероятность перехода равна 0, из (2,1) в (2,3) вероятность перехода равна 0.
Если добавить еще одну единицу памяти (рис. 1.8), то появятся два новых невозвратных состояния (п— 1,п) и (п,п — 1), т.е. количество невозвратных состояний будет равно 2п— 1 + 2 = 2n + 1. Тогда количество строк в матрице R увеличится на 2. Поглощающими будут состояния (0,-1) и [п,п-\-1). Теперь из состояния (п— 1,п) можно попасть в поглощающее состояние (п, п +1) с вероятностью 92) а вероятность перехода из (п — 2, п — 1) в (n — 1,п) будет равна 0, т.к. нельзя попасть в поглощающее состояние из состояния (п — 2, п — 1). Тогда количество нулевых строк между ненулевыми в матрице R увеличится на две и будет 2(п — 1) — 4 + 2 = 2п — 4. Остальные строки матрицы останутся без изменения.
При таких начальных состояниях в рассмотренной выше матрице R будет изменена первая строка. На рисунке 1.9 видно, что при начальном состоянии 0 переходу из 0 в (0, —1) будет соответствовать ненулевой элемент первой строки матрицы R, при начальном состоянии т переходу из т в (т,т + 1) также будет соответствовать ненулевой элемент первой строки матрицы R. Этот элемент равен q\ или Р2, если начальным состоянием будет 0, pi или #2, если начальным состоянием будет т, учитывая, переполнение или опустошение стека произошло.
Для решения задачи вычислим фундаментальную матрицу N — (I — Q) l [24], где I - единичная матрица, Q - это матрица вероятностей переходов из невозвратных состояний в невозвратные, включая начальное состояние. Вид матрицы Q установлен в работе [7]. Элемент N{j имеет смысл кол-ва единиц времени, которое процесс находился в состоянии j если блуждание началось из состояния .
Для определения оптимального состояния хо, т.е. состояния, при котором среднее время доступа минимально, необходимо перебрать все возможные начальные состояния, вычислить для каждого среднее время доступа и выбрать состояние, которому соответствует минимальное время.
Для реализации алгоритма решения задачи разработана программа для ЭВМ, которая для заданных вероятностных характеристик и размера памяти генерирует матрицу Q, вычисляет матрицы N и В, вычисляет среднее время доступа F(XQ) и определяет оптимальное состояние XQ. Некоторые результаты вычислений представлены в таблице 1.1 для т = 32. Параметры, определяющие характеристики памяти, взяты из работы [50]: — 1Д tx = 1.0, t2 = 30.0, t3 = 16.0.
Математическая модель и матрица вероятностей переходов
Обозначим текущие длины очередей х\ и Х2. В качестве математической модели процесса работы с очередями рассмотрим случайное блуждание по целочисленной решетке в треугольной области Х\ О, Х2 О, xi+X2 m-I + l (рис. 2.5), где х\ + Х2 = m - j + 1 - поглощающий экран, попадание на который характеризуется как переполнение выделенного объема памяти, Х\ = — 1 и жг = -1- отражающие экраны, попадание на которые характеризуется как исключение элемента из пустой очереди.
Индукция проводится по количеству единиц памяти п, которое используется для хранения информации.
1)Пусть размер памяти т = 4,х = 2,п = 2 (рис. 2.6). Размерность матрицы Q будет 6x6. Рассмотрим состояние 1. Из него можно перейти в состояние 4 с вероятностью qi, можно остаться в состоянии 1 с вероятностью г+ #2 операции, не изменяющей длины очередей ( прибавляем, т.к. в состоянии 1 может быть исключение элемента из второй очереди, которая пуста при Х2 = 0, но при этом длина очередей не меняется). Остальные элементы в этой строке будут нулями, т.к. переходы из состояния 1 в состояния 2,3,5,6 невозможны.
Рассмотрим состояние 2. Из него можно перейти в состояние 4 с вероят ностью исключения элемента из второй очереди 92) можно перейти в состояние 5 с вероятностью исключения элемента из первой очереди qi, можно остаться в состоянии 2 с вероятностью г операции, не изменяющей длины очередей. Остальные элементы в этой строке будут нулями, т.к. переходы из состояния 2 в состояния 1,3,6 невозможны.
Рассмотрим состояние 6. Из него можно перейти в состояние 4 с вероятностью включения элемента в первую очередь pi, можно перейти в состояние 5 с вероятностью р2 включения элемента во вторую очередь, можно остаться в состоянии б с вероятностью г + (ft + #2 операции, не изменяющей длины очередей (#i и #2 прибавляются, т.к. в этом состоянии обе очереди пусты, а исключение из пустой очереди не меняет ее длины). Остальные элементы в этой строке будут нулями, т.к. переходы из состояния 6 в состояния 1,2,3 невозможны.
Для решения задачи вычислим фундаментальную матрицу N = (I — Q) l. Для вычисления среднего времени блуждания, т.е. времени работы с очередями, просуммируем элементы матрицы N в строке, которая соответствует процессу блуждания, выходящему из состояния Х\ = Х2 = 0. Согласно введенной нумерации это будет последняя строка матрицы N.
В страничном способе организации при переполнении какой-либо очереди страница, которая содержит ее начало, может быть не заполнена до конца. В этом случае другая очередь не может использовать эту страницу. Но у этой очереди страницы, которые содержат ее начало и конец, тоже будут заполнены не до конца, поэтому переполненная очередь не может использовать эти страницы. Фактически, блуждание происходит в меньшей по размеру области. Поэтому вычисленное с помощью фундаментальной матрицы среднее время блуждания будет оценкой сверху для реального среднего времени. Обозначим эту оценку Ттах.
Также можно вычислить оценку снизу для среднего времени блуждания Тт{П, если рассмотреть, что при переполнении одной из очередей, в страницах, которые содержат начало переполненной очереди и начало и конец другой очереди, занято по одной ячейке.
Тогда для оценки сверху будем рассматривать блуждание в области Хі + Х2 гп — — + 1, а для оценки снизу блуждание в обла-сти х\ -f Х2 гп — — — 3(х — 2) + 1, где слагаемое 3(х — 2) - это три страницы, у которых заполнено по одной ячейке.
Заметим, что при связанном представлении очередей таких потерь памяти нет, а значит вычисленное время Т - это среднее время блуждания. Определим, для какого размера памяти т область блуждания в случае связанного представления очередей меньше, чем область блуждания в случае страничного представления для минимальной оценки среднего времени.
Для реализации алгоритма решения задачи разработаны программы для ЭВМ, которые генерируют матрицу Q, вычисляют матрицу iV и среднее время работы Т для каждого из рассмотренных способов организации очередей. Результаты вычислений представлены в таблицах 2.1, 2.2. В первых пяти столбцах находятся вероятностные характеристики очередей, в столбце с названием га содержится размер выделенной памяти. В таблице 2.1 столбец с названием Л[ соответствует последовательному способу организации очередей. В последовательном способе каждой очереди выделяется некоторое количество единиц памяти из общего объема. Необходимо определить разбиение памяти между очередями в зависимости от заданных вероятностных характеристик так, чтобы среднее время работы было максимально. В столбце с названием s находится оптимальное количество единиц памяти, выделенных первой очереди, в столбце с названием Т находится среднее время работы. Часто при реализации последовательного способа очередь зациклена, т.е. при достижении конечной границы области памяти следующие включения элементов будут происходить с начальной границы, если есть свободная память. В этом случае целесообразно один элемент всегда оставлять пустым, иначе в случае переполнения невозможно будет отличить переполненную очередь от пустой, и организация такой циклической очереди будет сложной [25]. Поэтому для реализации двух последовательных очередей необходимо два элемента оставить пустыми, т.е. для хранения информации будут использоваться m — 2 единиц памяти. Результаты для последовательного представления двух очередей взяты из работы [12].
Математическая модель и матрица вероятностей переходов
В последовательном способе организации каждой FIFO-очереди выделено некоторое количество единиц памяти из данных га единиц. Проверим, что при размере памяти m — d выполняется утверждение теоремы. Если добавить еще одну единицу памяти, то при фиксированном 5 поглощающая граница области блуждания при т = d — \ х% = d — s сдвинется на единицу вправо и будет Х2 = d-\- 1. Тогда получим s + 1 новых невозвратных состояний. Согласно введенной нумерации, эти состояния будут иметь младшие номера. Количество невозвратных состояний будет (s + l)(d — s) + (s + l) = (s + l)(d — s + 1).
Подматрицы матрицы Q характеризуют определенные операции над очередями. Подматрица А характеризует операции, при которых не изменяется длина очереди (например, чтение), и операции включения элементов в очередь с приоритетом 1, подматрица В - операции исключения элементов из очереди с приоритетом 2, подматрица С - операции включения элементов в очереди, подматрица А - операции, при которых не изменяется длина очереди и операции включения и исключения элементов в очередь с приоритетом 1. 3.3 Связанное представление
Обозначим текущие длины FIFO-очередей х\ и х і. В качестве математической модели процесса работы с приоритетной очередью рассмотрим случайное блуждание по целочисленной решетке в треугольной области Х\ О, #2 0, Xi -\-Х2 у +1 (рис. 3.7), где xi + Х2 = тг +1 - поглощающий экран, попадание на который характеризуется как переполнение выделенного объема памяти, (—1,0) и (0, —1) - отражающие точки, т.к. только в состоянии х\ — Х2 = 0 возможно исключение из пустой очереди. Исключение элементов из первой FIFO-очереди может происходить только при Х2 = 0.
Блуждание начинается в точке 2:1=2:2 = 0. Необходимо найти среднее время блуждания Т до попадания на поглощающий экран. Предполагаем, что т кратно х. Для хранения указателей используется единиц памяти, для хранения информации используется т — единиц памяти. Количество страниц равно j. Для хранения информации у каждой страницы используется х — 1 единиц памяти. При х = 2 получаем связанное представление очередей.
Предполагаем, что существует механизм работы со списком свободных страниц, который позволяет при заполнении страницы предоставить очереди новую страницу. Если в очереди освободилась страница, то она возвращается в список свободных страниц. Переполнение наступает тогда, когда список свободных страниц пуст и какая-то из FIFO-очередей переполнила страницу.
Обозначим текущие длины FIFO-очередей х\ и Х2. В качестве математической модели процесса работы с приоритетной очередью рассмотрим случайное блуждание по целочисленной решетке в треугольной области х\ О, #2 0, xi + Х2 т - 2f + 1 (рис. 3.10), где х\ -f х2 = т - + 1 - погло-щающий экран, попадание на который характеризуется как переполнение выделенного объема памяти, (—1,0) и (0,-1) - отражающие точки, т.к. только в состоянии х\ — Х2 = 0 возможно исключение из пустой очереди.
Рассмотрим состояние 2. Из него можно перейти в состояние 5 с вероятностью q исключения элемента из очереди с приоритетом 2, можно остаться в состоянии 2 с вероятностью г. Остальные элементы в этой строке будут нулями, т.к. переходы из состояния 2 в состояния 1,3,4,6 невозможны.
Рассмотрим состояние 5. Из него можно перейти в состояние 3 с вероятностью pi включения элемента в очередь с приоритетом 1, в состояние 2 с вероятностью Р2 включения элемента в очередь с приоритетом 2, в со стояние б с вероятностью q исключения элемента из очереди с приоритетом 1 (исключения из очереди с приоритетом 1 могут происходить только при Х2 = О, т.е. если очередь с приоритетом 2 пуста), можно остаться в состоянии 5 с вероятностью г. Остальные элементы в этой строке будут нулями, т.к. переходы из состояния 5 в состояния 1,4 невозможны.
Рассмотрим состояние 6. Из него можно перейти в состояние 4 с вероятностью р2 включения элемента в первую очередь, можно перейти в состояние 5 с вероятностью pi включения элемента во вторую очередь, можно остаться в состоянии 6 с вероятностью г + q (q прибавляется потому, что в этом состоянии обе очереди пусты, а исключение из пустой очереди не меняет ее длины). Остальные элементы в этой строке будут нулями, т.к. переходы из состояния б в состояния 1,2,3 невозможны.
Проверим, что при размере памяти n — d выполняется утверждение теоремы. Если добавить еще одну единицу памяти, тогда поглощающая граница сдвинется вправо на единицу и будет Х\ -f х2 = d + 1. Тогда в цепи появятся d + 1 новых невозвратных состояний. Количество невозвратных состояний в цепи будет равно + (d+l) = + + Количество строк и столбцов в матрице Q при п = d— 1 увеличится на d+І. Согласно введенной нумерации, новьге состояния будут иметь младшие номера, а состояния цепи при п = d — 1 будут следовать за ними.
Для решения задачи вычислим фундаментальную матрицу N = (I — Q)-1. В случае последовательного представления необходимо построить матрицу Q, вычислить матрицу N для всевозможных значений s. Для вычисления среднего времени блуждания просуммируем элементы матрицы N в строке, которая соответствует начальному состоянию х\ = Х2 = 0. Согласно введенной нумерации это будет строка с номером (s + 1)(т — s + 1) — s. Затем сравним полученное время для разных значений s и выберем максимальное. Соответствующее максимальному времени значение s будет оптимальным разбиением памяти для последовательного представления.
В случае связанного и страничного представления необходимо построить матрицу Q, вычислить матрицу N и просуммировать элементы матрицы N в строке, которая соответствует начальному состоянию х\ = х% = 0. Согласно введенной нумерации это будет последняя строка матрицы N.
В случае страничного представления вычисленное среднее время блуждания будет оценкой сверху для реального среднего времени. Обозначим эту оценку Ттах. Также, можно вычислить оценку снизу Ттіп для среднего времени блуждания. Для оценки сверху рассмотрим блуждание в области Х\ + Х2 т — j + 1, для оценки снизу блуждание в области Х\ + : т — j — 3(х — 2) + 1. При связанном представлении вычисленное время Т - это среднее время блуждания.
Для страничного представления оптимальный размер страницы равен х — 1. Рассматривая, для какого размера памяти m область блуждания в случае связанного представления может быть меньше, чем область блуждания в случае страничного представления для минимальной оценки среднего времени, получаем, что для m 24 при х = 1 и для любого m при 2 х j среднее время блуждания до поглощения в случае связанно го представления будет меньше, чем минимальная оценка среднего времени в случае страничного представления.
Для реализации алгоритма решения задачи разработаны программы для ЭВМ, которые генерируют матрицу Q, вычисляют матрицу N и среднее время работы для каждого из рассмотренных способов представления. Результаты вычислений представлены в таблицах 3.1, 3.2, 3.3.
Столбец с названием А\ соответствует последовательному представлению для размера памяти га, столбец с названием А[ соответствует последовательному представлению для размера памяти га—2, т.е. когда учитываются две единицы памяти при реализации двух циклических FIFO-очередей. В столбце с названием s находится оптимальное количество единиц памяти, выделенных первой FIFO-очереди, в столбце с названием Т находится среднее время работы.
Математическая модель и матрица вероятностей переходов
Обозначим текущие длины очередей Х\, %2 и 2. В качестве математической модели процесса работы с очередями рассмотрим случайное блуждание по целочисленной решетке в трехмерном пространстве 0 Х\ s + 1, 0 X2 z-hl,0 x$ m — s — z + l (рис. 4.2), где Х\ = s +1, х% — z+1, Хз = т — s — z + l поглощающие экраны, попадание на которые характеризуется как переполнение одной из очередей, а, х\ = — 1, x-i — — 1, х% = — 1 - отражающие экраны, попадание на которые характеризуется как исключение элемента из пустой очереди.
Случайное блуждание будем рассматривать как конечную однородную поглощающую цепь Маркова. Пронумеруем невозвратные состояния цепи так, как показано на рисунке 4.4 (т.е. сначала состояния, находящиеся в плоскости ( 1,) при #3 = 0, затем при х% = 1, и т.д. поднимаемся по оси #з). Количество невозвратных состояний в такой цепи равно (s + l)(z-\-l)(m — s — z + l). Например, для т = 6, s = 2,z = 2 количество невозвратных состояний равно 27 (рис. 4.4).
Из примера видно, что в подматрице А ко всем диагональным элементам прибавлена вероятность q%. Эта подматрица описывает блуждание в плоскости (х\,Х2) при #з = 0, а при исключении элемента из пустой третьей очереди длина очередей не меняется. Рассматривая подматрицы А и А , заметим, что в каждой подматрице D ко всем элементам на главной диагонали прибавлена вероятность q\, т.к. эта подматрица описывает блуждание при х\ = О, т.е. если первая очередь пуста.
Проверим, что при размере памяти т = d выполняется утверждение теоремы. Если добавить еще одну единицу памяти, то при заданных s 0 и z 0 эта единица памяти будет дана третьей очереди. Тогда поглощающая грань параллелепипеда х% = d — s — z сдвинется на единицу вверх по оси #з и будет Х2, — d — s — z + \. Появится еще одна плоскость для блуждания ( 1,0) при Хз = d-s-z. Тогда получим (s + l)(z + l) новых невозвратных состояний. Количество невозвратных состояний в цепи будет равно (s+l){z+l)(d-s-z)+(s+l)(z+l) = (s+l)(z+l)(d-s-z+l). Согласно введенной нумерации, новые состояния будут иметь старшие номера.
Заметим, что подматрицы матрицы Q характеризуют определенные операции над очередями. Подматрица А характеризует блуждание в плоскости (#1,3) при постоянном значении #з, т.е. описывает операции включения и исключения информации для первой и второй очередей. Подматрицы В и С характеризуют операции исключения и включения информации в третью очередь.
В связанном способе организации очередь представлена в виде связанного списка, каждый элемент которого состоит из двух единиц памяти, одна из которых используется для хранения информации, вторая содержит указатель на следующий элемент в списке (рис. 4.6).
Обозначим указатели на первые элементы очередей Fi, F и F , указатели на последние элементы очередей R\, 1 и Яз. Предполагаем, что т кратно 2. При таком представлении очередей всего будет у элементов. Для хранения указателей используется Щ единиц памяти, для хранения инфор-мации используется у единиц памяти. Рис. 4.6 Связанное представление трех очередей
Обозначим текущие длины очередей Xi, x i и #з. В качестве математической модели процесса работы с очередями рассмотрим случайное блуждание по целочисленной решетке в трехмерном пространстве х\ О, Х2 О, #з 0, х\ + х2 + хз у + 1 (рис. 4.7), где Х\ +Х2 + х$ = у + 1 - поглощающий экран, попадание на который характеризуется как переполнение выделенного объема памяти, Х\ = —1, Х2 = —1 и #з = —1 - отражающие экраны, попадание на которые характеризуется как исключение элемента из пустой очереди.
Блуждание начинается в точке х\ = Х2 = хз = О- Необходимо найти Т среднее время блуждания до попадания на поглощающий экран. Рассмотрим случай, когда в очереди хранятся данные, длина информационной части которых равна L 1 единиц памяти. Тогда длина каждого элемента очереди будет L +1, где одна единица памяти содержит указатель на следующий элемент. Предполагаем, что m кратно L +1. Количество эле ментов в этом случае будет -. Для хранения указателей используется -щ единиц памяти. В качестве математической модели будем иметь случайное блуждание по целочисленной решетке в трехмерном пространстве х\ О, Х2 0, х3 0, xi + х2 + х3 2%Ї +1 (рис. 4.8), где х\ + х2 + х3 = -щ +1 -поглощающий экран, Х\ = — 1, х2 = — 1 и гсз = — 1 - отражающие экраны.
Блуждание начинается в точке Х\= х2 — х% = 0. Необходимо найти Т среднее время блуждания до попадания на поглощающий экран и сравнить со средним временем блуждания в случае последовательного представления, когда длина информационной части равна L.
В страничном способе организации очередь представлена в виде связанного списка страниц размера х единиц памяти. Если одна очередь заняла страницу, то другая очередь не может ее использовать (рис. 4.9). Обозначим указатели на первые элементы очередей Fi, F2 и F$, указатели на последние элементы очередей R\, R2 и R$.
Предполагаем, что существует механизм работы со списком свободных страниц, который позволяет при заполнении страницы предоставить очереди новую страницу. Если в какой-то очереди освободилась страница, то она возвращается в список свободных страниц. Переполнение наступает тогда, когда список свободных страниц пуст и какая-то из очередей переполнила страницу.
Обозначим текущие длины очередей х\,Х2 ижз- В качестве математической модели процесса работы с очередями рассмотрим случайное блуждание по целочисленной решетке в трехмерном пространстве х\ О, Х2 0, #3 0, xi + х2 + хз т — + 1 (рис. 4.10), где х\ + Х2 + хз = т — j + 1 поглощающий экран, попадание на который характеризуется как переполнение выделенного объема памяти, а х\ = —1, X2 = — 1 и #з = — 1 отражающие экраны, попадание на которые характеризуется как исключение элемента из пустой очереди.
Для решения задачи вычислим фундаментальную матрицу N = (I — Q) l. В случае последовательной организации очередей необходимо построить матрицу Q, вычислить матрицу N для всевозможных значений s и z. Для вычисления среднего времени работы очередей просуммируем элементы матрицы iV в строке, которая соответствует начальному состоянию х\ = хч = x-s = 0. Согласно введенной нумерации это будет строка с номером (s+l)(z+l) — z. Затем сравним полученное время для разных значений s и z и выберем максимальное. Соответствующие максимальному времени значения s п z будут оптимальным разбиением памяти. В случае связанной и страничной организации очередей необходимо построить матрицу Q, вычислить матрицу N и просуммировать элементы матрицы N в строке, которая соответствует начальному состоянию Х\ = Х2 = хз = 0. Согласно введенной нумерации это будет последняя строка матрицы N.
В страничном способе организации при переполнении какой-либо очереди страница, которая содержит ее начало, может быть не заполнена до конца. В этом случае две другие очереди не могут использовать эту страницу. Но у этих очередей страницы, в которых содержатся начальные и конечные элементы, тоже будут заполнены не до конца, поэтому переполненная очередь не может использовать эти страницы. Фактически, блуждание происходит в меньшей по размеру области. Поэтому вычисленное с помощью фундаментальной матрицы среднее время блуждания будет оценкой сверху для реального среднего времени. Обозначим эту оценку Ттах.
Также можно вычислить оценку снизу Ттіп для среднего времени блуждания, если рассмотреть, что при переполнении одной из очередей, в страницах, которые содержат начало переполненной очереди и начало и конец другой очереди, занято по одной ячейке.
Тогда для оценки сверху будем рассматривать блуждание в области i-f-#2 + #3 т- + \, а для оценки снизу блуждание в области х\ + Х2 + хз т — — Ъ(х - 2) + 1, где слагаемое 5(х — 2) - это пять страниц, у которых заполнено по одной ячейке. При связанном представлении очередей, т.е. для размера страницы х = 2, таких потерь памяти нет, а значит вычисленное время Т - это среднее время блуждания.
Вычислим, для какого размера памяти m область блуждания в случае связанного представления очередей меньше, чем область блуждания в случае страничного представления для минимальной оценки среднего времени.
