bigpo.ru
добавить свой файл
1

МАТЕМАТИЧЕСКАЯ МОДЕЛЬ ОПТИМАЛЬНОГО УПРАВЛЕНИЯ ДВУХПРИОРИТЕТНОЙ ОЧЕРЕДЬЮ

В СЛУЧАЕ ПЕРЕРАСПРЕДЕЛЕНИЯ ПАМЯТИ

ПОСЛЕ ПЕРЕПОЛНЕНИЯ



Е. А. Аксенова1


1Институт прикладных математических исследований

Карельского научного центра РАН,

Петрозаводский государственный университет,

Петрозаводск, Россия


Во многих приложениях используется структура данных, в которой основными операциями являются вставка элемента и удаление элемента с наибольшим приоритетом. Такую структуру данных называют приоритетной очередью [1-3]. В [4-7] предлагались математические модели и алгоритмы оптимального управления несколькими FIFO-очередями в общей памяти одного уровня. Целью данной работы является исследование двухприоритетной очереди в случае представления ее в виде двух FIFO очередей [3]. В таком способе представления все элементы с одинаковым приоритетом помещаются в одну FIFO-очередь, и память не тратится на хранение приоритетов.


Очередь с двумя приоритетами

Рассмотрим очередь с двумя приоритетами, расположенную в памяти размера m единиц. Двухприоритетную очередь представим в виде двух FIFO-очередей. Первой очереди присвоен приоритет 1, второй - приоритет 2. Наивысший приоритет 2. Известны вероятностные характеристики приоритетной очереди:

  • pi – вероятность включения элемента с приоритетом i, i=1,2;

  • q – вероятность исключения элемента из очереди;

  • r – вероятность операции, не изменяющей длину очереди;

где p1+p2+q+r=1. При исключении элемента из пустой очереди работа не завершается. В очереди могут храниться элементы длины L. Предположим, что m кратно L. Тогда максимальное количество элементов в очереди обозначим n = m/L.

Оптимальное распределение памяти

Рассматривается последовательный способ организации приоритетной очереди. Необходимо определить, как распределить память между FIFO-очередями. В качестве критерия оптимальности рассматривается максимальное среднее время работы с приоритетной очередью до переполнения выделенного объема памяти.

В последовательном способе двухприоритетная очередь представлена в виде двух последовательных FIFO-очередей. Пусть s - количество элементов, выделенных первой FIFO-очереди, (n-s) - второй FIFO-очереди, 0 ≤ s n (Рис. 1).



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


Обозначим текущие длины FIFO-очередей x1 и x2. В качестве математической модели процесса работы с приоритетной очередью будем рассматривать случайное блуждание в области 0≤ x1<s+1, 0≤ x2<n-s+1, где ( 1,0) и (0,-1) - отражающие точки, x1=s+1, x2=n-s+1- поглощающие границы (Рис. 2). Блуждание начинается в точке x1=0, x2=0. Необходимо определить такое значение 0 ≤ sn, чтобы среднее время работы с приоритетной очередью до переполнения выделенного объема памяти было максимально.



Рис. 2. Область блуждания

Оптимальное перераспределение памяти

В данном разделе предлагается математическая модель и алгоритм оптимального перераспределения памяти после переполнения одной из FIFO-очередей для последовательного способа представления двухприоритетной очереди. Пусть s - количество элементов выделенных первой FIFO-очереди, (n-s) - второй FIFO-очереди. Требуется оптимально перераспределить свободную память между очередями после переполнения одной из FIFO-очередей, чтобы среднее время до следующего перераспределения памяти было максимально. В начале работы s выбирается оптимально, критерий – максимальное среднее время до переполнения.

Обозначим текущие длины очередей x1 и x2. В качестве математической модели рассмотрим случайное блуждание по целочисленной решетке в прямоугольной области на плоскости 0 ≤ x1< s+1, 0 ≤ x2< n-s+1. Блуждание начинается в точке x1=0, x2=0. Переполнению первой очереди соответствуют точки на прямой x1=s+1, переполнению второй очереди - точки на прямой x2=n-s+1. При переполнении одной из FIFO-очередей происходит перераспределение свободной памяти между FIFO-очередями и работа с программной системой продолжается. При попытке включения элемента в заполненную очередь, когда x1=s (или x2=n-s), требуется определить новую область блуждания 0 ≤ x1< s*+1, 0≤ x2< n-s*+1, т.е. найти такое значение s*, где s*>s (или n-s* > n-s), чтобы среднее время до следующего переполнения одной из FIFO-очередей было максимальным (Рис. 3).




Рис. 3. Выбор новой области блуждания


Решение задачи

Случайное блуждание по целочисленной решетке будем рассматривать как конечную однородную поглощающая цепь Маркова с матрицей вероятностей переходов P. Для решения задачи требуется матрица Q вероятностей переходов из невозвратных состояний в невозвратные (Q - подматрица матрицы P). Вводится нумерация состояний Марковской цепи, это позволяет определить структуру матрицы Q для любого размера памяти m, и любых значений s и L. Среднее время вычисляется с помощью фундаментальной матрицы N=(E-Q)-1 [8], где Nij – это среднее количество единиц времени, которое процесс находился в состоянии j, если начальным было i.

Вычисление критерия оптимальности в данной задаче является очень ресурсоемким за счет обращения матрицы (E-Q) большого размера.

Алгоритм:

  1. Ввод вероятностных характеристик приоритетной очереди, размера памяти m, длины элемента L; n=m/L;

  2. Для каждого значения s, 0 ≤ s n, генерируем матрицу Q, вычисляем матрицу N;

  3. Для каждого значения s суммируем элементы матрицы N в строке, соответствующей состоянию x1= 0, x2= 0;

  4. Выбираем такое значение s, которому соответствует максимальная сумма элементов в строке соответствующей матрицы N;

  5. Для каждого состояния, в котором одна из FIFO-очередей заполнила выделенную память, т. е. x1 = s или x2 = n-s, перебираем значения 0 ≤ s* ≤ n, где s* > s, если x1=s, и n-s* > n-s, если x2=n-s. Для каждого s* генерируем новую матрицу Q, вычисляем матрицу N;

  6. Для каждого значения s* суммируем элементы матрицы N в строке, соответствующей рассматриваемому состоянию ( x1=s или x2=n-s);

  7. Выбираем такое значение s*, которому соответствует максимальная сумма элементов в строке соответствующей матрицы N. Для каждого состояния, соответствующего тому, что одна из FIFO-очередей заполнила выделенную память, получаем оптимальное значение s*.

Шаги 5-7 можно повторять до полного исчерпания свободной памяти (если перед каждым новым перераспределением текущее значение s* обозначить как s).

Матрицу N можно представить в виде N=(E-Q)-1=E+Q+Q2+...= ∑ Qk, k=0,1,…,∞. Такое представление матрицы N дает выигрыш в размере памяти для вычислений. Поскольку для алгоритма важна сумма элементов в определенной строке матрицы N, то запись в виде суммы ряда позволяет вычислять элементы конкретной строки, не вычисляя остальных элементов матрицы.

Работа выполнена при финансовой поддержке гранта РФФИ (проект 12-01-00253-а).


СПИСОК ЛИТЕРАТУРЫ


1. Кнут Д. Искусство программирования для ЭВМ. М.: Вильямс, 2001.

2. Седжвик Р. Фундаментальные алгоритмы на С++. К.: Диасофт, 2001.

3. Боллапрагада В., Мэрфи К., Уайт Р. Структура операционной системы Cisco IOS. М.: Вильямс, 2002.

4. Аксенова Е. А., Соколов А. В. Некоторые задачи оптимального управления FIFO-очередями // Труды Второй Всероссийской научной конференции «Методы и средства обработки информации». М.:Изд. отдел ВМК МГУ им. М.В. Ломоносова, 2005, с. 318-322.

5. Аксенова Е. А. Оптимальное управление FIFO-очередями на бесконечном времени // Межвузовский сборник «Стохастическая оптимизация в информатике». СПб: Изд-во С.-Петербургского университета, 2006, с.71-76.

6. Аксенова Е. А., Драц А. В., Соколов А. В. Об оптимальном управлении FIFO-очередями на бесконечном времени // Обозрение прикладной и промышленной математики. Т.16, вып.3, 2009, с. 401-415.

7. Аксенова Е. А., Драц А.В., Соколов А. В. Оптимальное управление n FIFO-очередями на бесконечном времени // Информационно - управляющие системы. № 6, 2009, с. 46-54.

8. Кемени Дж., Снелл Дж. Конечные цепи Маркова. М.: Наука, 1970.