Содержание к диссертации
Введение
1 Управление стеками в памяти одного уровня 12
1.1 Постановка задачи 14
1.2 Последовательное представление 15
1.3 Связное представление 19
1.4 Страничное представление 22
1.5 Результаты 27
2 Среднее время работы до переполнения 31
2.1 Последовательное представление 32
2.2 Движение по кругу 36
2.3 Случай параллельного выполнения операций 39
2.4 Результаты 41
3 Работа на бесконечном времени 45
3.1 Последовательное представление очередей 46
3.1.1 Вычисление доли времени 46
3.1.2 Оптимальное разбиение памяти. Случай равных вероятностей 52
3.1.3 Оптимальное разбиение памяти. Общий случай 58
3.2 Связанное представление очередей 60
3.2.1 Вычисление доли времени 60
3.2.2 Случай равных вероятностей з
3.2.3 Общий случай 66
3.3 Движение по кругу 70
3.4 Результаты 73
3.5 Задача Седжвика
3.5.1 Одна очередь в памяти неограниченного размера 76
3.5.2 Общий случай 80
3.5.3 Численные результаты 82
4 Управление приоритетной очередью 84
4.1 Постановка задачи 85
4.2 Среднее время работы до переполнения
4.2.1 Представление в виде массива 86
4.2.2 Представление в виде последовательных FIFO-очередей 87
4.3 Управление на бесконечном времени 88
4.3.1 Представление в виде массива 88
4.3.2 Представление в виде последовательных FIFO-очередей 89
4.4 Результаты 91
Заключение 94
Литература
- Связное представление
- Случай параллельного выполнения операций
- Оптимальное разбиение памяти. Случай равных вероятностей
- Представление в виде последовательных FIFO-очередей
Введение к работе
Актуальность темы. В настоящее время стремительно развивается индустрия производства программного и аппаратного обеспечения для таких устройств, как мобильные телефоны, планшеты, персональные компьютеры, автоматизированные средства обработки данных и т.д. Как правило, эти устройства обладают достаточно жесткими ограничениями на быструю память, такую как регистры, кеш, оперативная память и т.п. Это связано с дороговизной производства и большим энергопотреблением (для мобильных устройств). В связи с этим необходимо уделять особое внимание алгоритмам управления памятью в этих устройствах и, прежде всего, работе с базовыми структурами данных, такими как LIFO-стеки, FIFO-очереди и приоритетные очереди. Например, алгоритмы работы с очередями, необходимые при разработке встроенных операционных систем, управляющих потоками пакетов в Internet, таких, например, как Cisco IOS, где требования на время обработки пакетов маршрутизатором очень жесткие. Механизм страничной виртуальной памяти здесь не используется и вся работа происходит в нескольких пулах оперативной памяти. FIFO-очереди и приоритетные очереди используются в компьютерных сетях, операционных системах, графических системах, устройствах промышленной автоматики. Ряд американских фирм выпускает микросхемы, реализующие работу с несколькими FIFO-очередями. Например, известна реализация устройств FIFO-памяти в виде микросхем, выпускаемых американской фирмой IDT Inc. (аналогичную продукцию выпускают ее конкуренты - фирмы Cypress и AverLogic Techologies). В семействах памяти Multi-Queue FIFOs реализована работа с несколькими параллельными FIFO-очередями на одном кристалле. Число очередей и длина каждой очереди устанавливается программным путем на этапе инициализации устройства.
Целью работы является построение и анализ математических моделей различных способов представления динамических структур данных: LIFO-стеков, FIFO-очередей и приоритетных очередей. Критериями оптимальности являются максимальное среднее время работы до переполнения и минимальная доля потерянных элементов при работе на бесконечном времени. Для достижения поставленной цели необходимо было решить следующие задачи:
1. Построить и проанализировать математические модели описывающие различные способы представления LIFO-стеков в памяти одного уровня.
-
Построить и проанализировать математические модели описывающие различные способы представления FIFO-очередей в памяти одного уровня.
-
Построить и проанализировать математические модели описывающие различные способы представления приоритетной очереди в памяти одного уровня.
-
Разработать комплекс программ, реализующие предложенные модели и алгоритмы.
Методы исследования: аппарат случайных блужданий, теория поглощающих и регулярных цепей Маркова, методы математического анализа и комбинаторики.
Научная новизна. Все предложенные в работе модели и алгоритмы являются новыми. Предложенные ранее модели описывали способы работы описывали процесс работы с конкретным число стеков, очередей или приоритетов у приоритетной очереди или строили имитационную модель. Предложенные в работе модели и алгоритмы позволяют решить поставленные задачи для произвольного количества стеков, очередей или приоритетов в приоритетной очереди.
Теоретическая и практическая значимость Предложенные в работе модели и методы могут быть использованы при проектировании программных и аппаратных комплексов использующих динамические структуры данных.
Положения, выносимые на защиту:
-
Построение и анализ математических моделей, описывающих различные способы представления LIFO-стеков в памяти одного уровня.
-
Построение и анализ математических моделей, описывающих различные способы представления FIFO-очередей в памяти одного уровня.
-
Построение и анализ математических моделей, описывающих различные способы представления FIFO-очередей в памяти одного уровня при работе на бесконечном времени.
-
Построение и анализ математических моделей, описывающих различные способы представления приоритетной очереди в памяти одного уровня.
-
Комплекс программ, реализующих предложенные в работе алгоритмы и
модели.
Связь работы с научными программами, темами. Основные результаты диссертации были получены в рамках исследования, выполнявшихся в ходе работы над госбюджетными темами Института прикладных математических исследований Карельского научного центра РАН. Работа поддержана грантами РФФИ 09-01-00330-а, 12-01-00253-а, 15-01-03404-а и программой стратегического развития ПетрГУ в рамках реализации комплекса мероприятий по развитию научно-исследовательской деятельности.
Апробация работы. Результаты работы были представлены и обсуждались на следующих конференциях:
-
VII Международная Петрозаводская конференция «Вероятностные методы в дискретной математике», 1-6 июня 2008, Петрозаводск.
-
XVI Всероссийская научно-методическая конференция «Телематика-2009», 22-25 июня 2009, Санкт-Петербург.
-
Третья Всероссийская научная конференция «Методы и средства обработки информации», 6-8 октября 2009, Москва.
-
Международная научно-техническая конференция «Многопроцессорные вычислительные и управляющие системы», 28 сентября - 3 октября 2009, с. Дивноморское.
-
Международная научная конференция «Дискретная математика, алгебра и их приложения», 19-22 октября 2009, Минск.
-
Annual International Workshop on Advances in Methods of Information and Communication Technology, 25-26 мая 2010, Петрозаводск.
-
Международная суперкомпьютерная конференция «Научный сервис в сети Интернет: суперкомпьютерные центры и задачи», 20-25 сентября 2010, Новороссийск.
-
Международная научно-техническая конференция «Суперкомпьютерные технологии: разработка, программирование, применение. СКТ-2010», 27 сентября - 2 октября 2010, с. Дивноморское.
-
Седьмая международная научная молодежная школа «Высокопроизводительные вычислительные системы ВПВС-2010», 27 сентярбя - 2 октября 2010, с. Дивноморское.
10. 15 Всероссийская конференция «Математические методы распознавания образов», 11-17 сентября 2011, Петрозаводск.
-
5 Всероссийская конференция «Имитационное моделирование. Теория и практика», 19-21 октября 2011, Санкт-Петербург.
-
Third Russian Finnish Symposium on Discrete Mathematics, 15-18 сентября 2014, Петрозаводск.
-
12th International Conference of Numerical Analysis and Applied Mathematics, 22-28 сентября 2014, Родос.
Личный вклад. Содержание диссертации и основные положения, выносимые на защиту, отражают персональный вклад автора в опубликованные работы. Подготовка к публикации полученных результатов проводилась совместно с соавторами, причем вклад диссертанта был значительным. Все представленные в диссертации результаты получены лично автором.
Публикации. Основные результаты по теме диссертации изложены в 22 печатных изданиях, 5 из которых опубликованы в научных изданиях, рекомендованных ВАК, 12 — в тезисах докладов.
Объем и структура работы. Диссертация состоит из введения, четырех глав, заключения и приложения. Полный объем диссертации 106 страниц текста с 29 рисунками и 2 таблицами. Список литературы содержит 65 наименований.
Связное представление
Необходимо отметить, что во всех случаях преставления сложность включения и исключения одного элемента равна 0(1). Для связанного (страничного) представления это достигается путем ведения списка свободных ячеек (страниц) памяти и обновления его после каждой операции включения/исключения. Важную роль играет отношение размера указателя к размеру информационной части /. Чем меньше значение /, тем меньшая часть памяти тратится на хранение указателей и тем выгоднее использовать связанное и страничного представления. В главе предложены математические модели и алгоритмы, описывающие последовательный, связанный и страничный способы представления стеков, и определены, какой из методов эффективнее при известных вероятностных характеристиках. Задача была решена для двух, трех и четырех стеков в работах [21] и [22]. 1.1 Постановка задачи
Рассмотрим п стеков находящихся в памяти размера т. Время дискретно. Вероятностные характеристики известны, на каждом шаге возможна одна из следующих операций: — Включение элемента в первый стек с вероятностью 1, — Исключение элемента из первого стека с вероятностью gi, — Включение элемента в n-ный стек с вероятностью рп, — Исключение элемента из n-нного стека с вероятностью qn, — Чтение или любая другая операция без изменения стека с вероятностью г. Pi + Ц\ + +Pn + Qn + т = 1- Вероятности не зависят от времени и от количества элементов в стеках. Работа начинается с пустых стеков, и не происходит завершения работы при попытке исключения элемента из пустого стека. Х\,Х2, ,хп - текущие длины структур данных. Необходимо найти среднее время работы до переполнения Т. В случае связанного представления часть памяти тратится на указатели. / - отношение размера указателя к размеру информационной части для связанного и страничного представлений. Будем считать, что информационная часть занимает одну единицу памяти. В случае последовательного представления возникает дополнительная задача оптимального разбиения памяти. к{ - размер памяти, выделенный под г-ю пару стеков.
Последовательное представление Пример нумерации представлен на рисунке (1.4). Для того, чтобы построить матрицу вероятностей переходов, построим функцию F{x\ X2i ixn) = 11 Где / - номер состояния, с помощью которой можно будет вычислять номер состояния по текущим длинам стеков. В соответствии с введенным порядком состояний:
Если появляется вторая пара стеков, то состояния {х\,х2) становятся равными (жі,Ж2,0,0). Между состояниями (жі,#2,0,0) и (#і,#2 + 1,0,0) нужно
Чтобы найти среднее время блуждания Т, необходимо вычислить фундаментальную матрицу N = (Е — Q) . Nij - среднее время, которое процесс проведет в состоянии j, если он начался в состоянии і. Поскольку работа начинается с пустых структур данных, то і = 0 и Т = У ] NQJ. Таким образом, з необходимо вычислить только первую строку фундаментальной матрицы N. Чтобы найти оптимальное разбиение памяти, необходимо перебрать все возможные варианты разбиения памяти и для каждого из них найти среднее время работы до переполнения. Всего возможно Ото-1 = (т-п/2)!(п/2-1)! сп0 собов разбиения. Некоторые из них заведомо неоптимальны, поэтому перед построением фундаментальной матрицы можно сделать следующие проверки (стеки с номерами і1, І2 и j1, j 2 объединены в пары):
То есть, если вероятности включения и исключения элементов в 2 пары стеков равны, то им нужно выделить примерно поровну памяти. Получаем следующий алгоритм для решения задачи: — Перебрать все возможные варианты разбиения быстрой памяти. — Для каждого разбиения проверить выполнение (1) и (2). — Для каждого разбиения перебрать все возможные разбиения стеков на пары. Если оно не удовлетворяет этим условиям, то перейти к следующему разбиению. Иначе построить матрицу переходных вероятностей и вычислить среднее время работы до переполнения — Выбрать наибольшее время блуждания из всех найденных. 1.3 Связное представление М = _TTJJ - размер памяти, который тратится на размещение информационных частей, он же равен общему количеству элементов, которые можно разместить в памяти. Например, если элемент списка объявлен как struct nodejDataT info; node link;}; sizeof(info)= 4 sizeof(link); sizeof(info) = 4 байт и размер памяти равен 40 байт, то т = 10, / = 1/4 и М = _TT]J = 8 (Единица памяти равна 4 байта).
Количество состояний равно М\2\ Доказательство. Проведем аналогию с размещением объектов по ячейкам [24]: Число способов размещения п одинаковых объектов по т различным ячейкам равно С +т-1. В качестве объектов выступают единицы данных, а вместо ячеек - стеки. Будем считать, если ячейка памяти пустая, то она принадлежит (п + 1)-му стеку. Поэтому, всего единиц данных будет М, а стеков п +1.
Случай параллельного выполнения операций
Чтобы найти среднее время блуж;дания Т, нуж;но построить фундаментальную матрицу N (с. 17). Чтобы найти оптимальное разбиение памяти, необходимо перебрать все возможные разбиения памяти, для каждого из них найти среднее время работы до переполнения и выбрать наибольшее время. Всего для размера памяти тип очередей существует С \ = /п_щто_пм способов разбиения. Но некоторые из них заведомо невыгодны, поэтому перед построением матрицы переходных вероятностей можно сделать очевидные проверки. Для 2-х очередей с номерами і и j должны быть выполнены условия: 1. Если (qi qj и pi pj) или ( qj и pi Pj), то должно выполняться rvi _ rvj. То есть, если в г-ю очередь чаще происходят включения и реже исключения элементов чем в j-ю, то и памяти г-той очереди нужно выделить по крайней мере не меньше чем j -той. 2. Если qi = qj и pi = pj, то \hb — kj\ 1. To есть, если вероятности включения и исключения элементов в 2 очереди равны, то им нужно выделить примерно поровну памяти. (Уело 36 виє \{ — j\ 1 нельзя заменить на { = j, например для 2-х очередей и размера быстрой памяти 5 и вероятностных характеристик i = 2 = i = 2 = 0.25 оптимальным разбиением будет \ = 2, 2 = 3 или \ = 3, 2 = 2, но равенство \ = 2 не выполняется).
Проверка этих условий в некоторых случаях позволяет значительно сократить количество вычислений. (Например для 3-х очередей при размере быстрой памяти 30 и вероятностных характеристиках \ = i = 2 = 2 = з = % = е только оптимальное разбиение \ = 2 = % = 10 удовлетворяет вышеописанным условиям, поэтому нужно будет вычислить время блуждания только для этого разбиения). Получаем следующий алгоритм для решения задачи:
Перебрать все возможные варианты разбиения быстрой памяти. Для каждого разбиения проверить выполнение (1) и (2). Если оно не удовлетворяет этим условиям, то перейти к следующему разбиению. Иначе построить матрицу переходных вероятностей и вычислить среднее время работы до переполнения текущие длины очередей, - расстояние от головы первой очереди до хвоста второй. Величины (\,2,) однозначно определяют положение очередей в памяти. Переполнение наступает когда первая очередь догоняет вторую (при = 0) или вторая догоняет первую \ + 2 + = 0 В качестве математической модели рассмотрим блуждание по целочисленной трехмерной пирамиде с вершиной (0,0,0), ребрами \ = 0, 2 = 0, = 0 и основанием x + у + z = т.
Предложенные в этой и предыдущей главах модели можно обобщить на случай параллельного выполнения операций. В предыдущих параграфах считалось, что в каждый момент времени происходит работа только с одной структурой данных. Это могли быть, например, несколько стеков процессов выполняющихся на процессоре с одним ядром или несколько потоков входных данных с одним обрабатывающим устройством. Рассмотрим случай, когда операции включения/исключения элементов могут выполняться одновременно с несколькими структурами данных. Например, несколько процессоров обрабатывают данные в общей памяти или есть несколько потоков входных данных и несколько обрабатывающих устройств.
Будем считать, что известны все возможные изменения длин структур данных за одну единицу времени (і,2,. .. ,п) и вероятности (і,2, . . . ,п). Например, если в быстрой памяти находятся структур данных, в каждую из которых независимо от других можно включать и исключать элементы i - вероятность включения элемента в тую структуру данных, - вероятность исключения, І - вероятность чтения), то вероятности (і,2,... ,п) можно посчитать следующим орбразом: (1,1,...,1) = \2 . . .п вероятность одновременного включения элемен 40 тов во все структуры данных,
Если АІ 1, то в тую структуру данных включается больше одного элемента в единицу времени. Если А І —1, ТО ИЗ туй структуры данных исключается больше одного элемента в единицу времени. Заметим, что можно говорить только об одновременном включении нескольких элементов одинаковых длин, а не о включении элементов разных длин, поскольку в этом случае вероятности исключения элементов зависели бы от предыстории (например, при включении в стек элемента длины 2 вероятность исключения элементы длины 2 на следующем шаге будет больше 0, а при включении элемента длины 1 вероятность исключения элемента длины 2 будет равна 0). Иными словами, рассматриваемая система не обладала бы Марковским свойством, а значит к ней нельзя было бы применить аппарат поглощающих цепей Маркова.
Для связанного представления структур данных и для последовательного представления стеков будем считать, что невозможны одновременное исключение элемента и запись элемента в одну и ту же ячейку памяти. Рассмотрим переход системы из состояния (і,... ,п) в состояние ( і,.. . , п) при последовательном представлении очередей:
Оптимальное разбиение памяти. Случай равных вероятностей
В качестве математической модели рассмотрим блуждание по целочисленной трехмерной пирамиде с вершиной (0,0,0), ребрами и основанием Дополнительно, для каждого состояния на плоскостях введем состояния «сброса хвоста». Рассмотрим случайное блуждание как конечную однородную регулярную цепь Маркова.
Переходы из состояний «сброса хвоста» такие же, как и из соответствующих состояний У построенной цепи Маркова существует предельный вектор , который удовлетворяет уравнению = . По закону больших чисел значение является долей времени, которое процесс проводит в состоянии . Чтобы найти долю времени, которую система проводит в состоянии «сброса хвоста», необходимо вычислить сумму тех компонент вектора , которые соответствуют состояниям «сброса хвоста». В примере на рис. 3.3 необходимо будет просуммировать компоненты с номерами от 35 до 60.
В предыдущих параграфах были получены формулы, позволяющие в явном виде вычислять долю времени, которую система проводит в состоянии «сброса хвоста». В этом параграфе приводятся результаты сравнения последовательного и связанного представлений. Результаты справедливы в предельной форме, когда, но, как показывают результаты тестов, они справедливы в допредельной форме, когда размер памяти довольно мал (около 10-20 единиц). Для вычислений использовалась система векторной алгебры Maxima [32]. Рассмотрим несколько случаев зависимостей между вероятностными характеристиками.
В случае, если вероятности включения элементов в структуры данных меньше, чем вероятности исключения, доля времени, которую система проводит в состоянии «сброса хвоста» экспоненциально стремится к 0 для обоих представлений. Предпочтительнее использовать то представление, у которого показатель экспоненты меньше. Графики 3.4 показывают сравнение доли времени Р для различных способов представления очредей.
Рассмотрим систему из п FIFO-очередей, находящуюся в памяти неограниченного размера. Время дискретно. На нечетном шаге в одну из очередей с вероятностью 1/п помещается элемент. На четном шаге из произвольной очереди исключается элемент с вероятностью 1/п. Необходимо найти x(n,t) - средний размер очередей после t шагов и P(n,t) - вероятность исключения элемента из пустой очереди на шаге t. Поел.
Рассмотрим одну очередь, находящуюся в памяти одного уровня неограниченного размера. В начальный момент времени очередь пустая. Время дискретно и в каждый момент времени возможна одна из операций: — включение элемента в очередь с вероятностью р, — исключение элемента из очереди с вероятностью q, — чтение элемента из очереди без исключения с вероятностью г. p + q + r = 1. При исключении элемента из пустой очереди ошибки не происходит. L(t) - длина очереди в момент времени t. x(t) = m[L(t)] - математическое ожидание длины очереди за шагов. P{L(t) = і} — вероятность того, что через t операций после начала работы длина очереди будет равна і. По определению математического ожидания [33]:
Рассмотрим одну из очередей в задаче Седжвика. Объединим два шага в один (включение элемента в одну из очередей и исключение элемента из одной из очередей). Чтобы за шаг размер очереди увеличился на единицу, необходимо на нечетном этапе в него включить элемент с вероятностью 1/п, а на четном — исключить из другой очереди с вероятностью (п — 1)/п. Поэтому вероятность того, что за один шаг длина очереди увеличится на один элемент равна
Чтобы за один шаг длина очереди не изменилась, необходимо включить и исключить элемент из рассматриваемой очереди или включить и исключить элементы из других очередей, поэтому
Выражение (3.6) показывает вероятность того, что послед шагов в очереди будет ноль элементов. Найдем вероятность исключения из пустой очереди на шаге t. Для этого необходимо, чтобы длина очереди на шаге t — 1 была равна нулю и на шаге t была попытка исключения из нее.
В главе предложены и исследованы математические модели для представления приоритетной очереди в памяти одного уровня. Рассмотрены представления в виде массива и в виде п последовательных FIFO-очередей. В случае представления в виде массива вместе с каждым элементом необходимо хранить его приоритет. В этом случае переполнение наступит только тогда, когда вся свободная память закончится, но часть памяти тратится на хранение приоритетов.
В случае представления приоритетной очереди в виде п последовательных FIFO-очередей все элементы с одинаковыми приоритетами помещаются в одну FIFO-очередь. (Число FIFO-очередей равно количеству приоритетов в приоритетной очереди). Каждой FIFO-очереди выделен свой участок памяти. В этом случае память не тратится на хранение приоритетов, но могут возникнуть потери памяти в том случае, если одна из FIFO-очередей полностью исчерпает свою часть памяти, а остальные заполнят ее не полностью. Здесь возникает дополнительная задача оптимального разбиения памяти между FIFO-очередями. Если использовать связанное представление очередей, т. е. хранить каждую FIFO-очередь не в виде массива, а в виде связного списка, то этот метод представления приоритетной очереди сводится к представлению в виде массива. Вместе с каждым элементом хранить нужно будет не его приоритет, а указатель на следующий элемент FIFO-очереди. Поэтому этот случай представления приоритетной очереди отдельно рассмотрен не будет. В качестве критериев оптимальности рассмотрены максимальное среднее время работы до переполнения и минимальная доля времени, которую очередь проводит в состоянии «сброса хвоста». Задача для числа приоритетов п = 2 была решена в работе [34].
Представление в виде последовательных FIFO-очередей
Для описания процесса построим соответствующую поглощающую цепь Маркова. Необходимо построить матрицу вероятностей переходов Q. Для этого нужно знать номер каждого состояния ФункцияF(x\ X2-, ,хп) = I имеет точно такой же вид, как и в случае п последовательных FIFO-очередей Для вычисления среднего времени блуждания нужно вычислить фундаментальную матрицу N = (Е — Q) l [23]. N{j - среднее время, которое процесс проведет в состоянии j, если он начался в состоянии і. Поскольку работа начинается с пустых структур данных, тоі = 0иТ = NQJ.
Чтобы найти оптимальное разбиение памяти, необходимо перебрать все возможные разбиения памяти, для каждого из них найти среднее время работы до переполнения и выбрать наибольшее время. Всего для размера памяти
Как и в предыдущем критерии, часть памяти тратится на хранение прио элементов в памяти. В качестве ритетов. Всего можно хранить математической модели рассмотрим блуждание в одномерном интервале длины . Переход из состояния () в состояние (1) происходит в соответствии со следующими правилами:
Пусть \,.. . ,п - фиксированное разбиение памяти между очередями. В качестве математической модели рассмотрим блуждание по целочисленному мерному параллелепипеду, ограниченному гиперплоскостями { = О, { = і, (1 ). Дополнительно, к каждому состоянию на гиперплоскостях j = j введем состояние «сброса хвоста» Количество обычных состояний равно ПГ=і + 1) Количество состояний «сброса хвоста», соответствующих -й очереди равно
Перенумеруем сначала обычные состояния в лексикографическом порядке, как в предыдущем параграфе, затем перенумеруем состояния «сброса хвоста», соответствующие гиперплоскости \ = \, затем соответствующие гиперплоскости 2 = 2 и т.д. На каждой гиперплоскости { = { перенумеруем состояния в лексикографическом порядке, по аналогии с обычными состояниями. Пример нумерации состояний показан на рис. 4.1. Состояния с номерами больше 35 являются состояниями «сброса хвоста». 0 3 6 9 48 2 12 15 18 21 51 2
У построенной цепи Маркова существует предельный вектор а, который удовлетворяет уравнению aQ = а. По закону больших чисел значение оц является долей времени, которое процесс проводит в состоянии і. Чтобы найти долю времени, которую система проводит в состоянии «сброса хвоста», необходимо вычислить сумму тех компонент вектора а, которые соответствуют состояниям «сброса хвоста». В примере на рис. 4.1 необходимо будет просуммировать компоненты с номерами от 36 до 68.
Для решения задачи были написаны программы на языке С, которые вычисляют матрицу Q, среднее время работы до переполнения и долю времени, которую система проводит в состоянии «сброса хвоста» и находят оптимальное разбиение памяти между очередями в случае представления приоритетной очереди в виде последовательных FIFO-очередей. Некоторые результаты работы программ представлены в таблицах 3 и 4. В строке Т находится среднее время работы до переполнения в случае представления в виде п FIFO-очередей, в строках ki (1 і 4) - оптимальное разбиение памяти. В строке Р находится доля времени, которую система проводит в состоянии «сброса хвоста» в случае представления в виде п FIFO-очередей. В строке 1\ указано время работы в случае представления в виде массива,
Из полученных численных результатов можно сделать вывод, что для критерия максимизации среднего времени работы до переполнения Т представление приоритетной очереди в виде массива предпочтительнее использовать, если на приоритеты тратится 1/3 часть или меньше памяти. Если на приоритеты тратится половина памяти, то предпочтительнее использовать представление в виде п FIFO-очередей. Для критерия минимизации доли потерянных элементов практически во всех наборах вероятностей предпочтительнее использовать представление в виде массива, если на хранение ключей тратится 1/3 часть памяти или меньше. Если общая вероятность включения элементов в приоритетную очередь р = р\ + + рп намного больше вероятности исключения, то доля времени с ростом памяти быстро стремится к величине р — q.
Память в случае представления в виде п последовательных FIFO-очередей нужно выделить больше тем очередям, которые хранят элементы с меньшими приоритетами. На практике так обычно и делается, например, CISCO в своих маршрутизаторах использует очередь с 4 приоритетами и выделяет по умолчанию FIFO-очередям по 80, 60, 40, 20 единиц памяти, соответственно [19]. Предложенные в работе модели и программы могут дать для известных значений вероятностей выполнения операций оптимальное размеры очередей разных приоритетов, которые системный администратор может учитывать при настройке маршрутизатора.