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

Труды Карельского научного центра РАН № 1. 2013. С. 46-54

УДК 004.01:006.72

МАТЕМАТИЧЕСКИЙ АНАЛИЗ ОДНОГО СПОСОБА ПРЕДСТАВЛЕНИЯ ДВУХ Е1ЕО-ОЧЕРЕДЕЙ В ОБЩЕЙ ПАМЯТИ

Н. В. Каблукова1, А. В. Соколов2

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

2 Институт прикладных математических исследований Карельского научного центра РАН

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

В работе [8] поставлена задача построения математической модели процесса работы с несколькими FIFO-очередями в общей памяти, когда на нечетном шаге дискретного времени с известными вероятностями допускаются операции включения элементов в очереди, а на четном - операции исключения.

В [5] предложена математическая модель этого процесса для двух FIFO-очередей, и решается задача оптимального разбиения общей памяти для очередей в случае их последовательного циклического представления.

В данной работе построены математическая и имитационная модели процесса работы с двумя очередями, когда они двигаются по кругу друг за другом [9].

Ключевые слова: FIFO-очередь, случайное блуждание, регулярные цепи Маркова.

N. V. Kablukova, A. V. Sokolov. MATHEMATICAL ANALYSIS OF A WAY OF PRESENTING TWO FIFO QUEUES IN SHARED MEMORY

Many applications need to work with several FIFO queues located in a common memory space. Various software or hardware solutions are used to this end [4, 7, 8]. In [8] the problem was formulated for building a mathematical model of the process of working with several FIFO queues in shared memory, where insertion of an item in the queue is allowed on an odd step of the discrete time, and deletion operations -on an even step. The probabilities of the operations are known. In [5] a mathematical model of this process for the number of queues n = 2 was proposed, and the problem of optimal partitioning of the shared memory between the two FIFO queues in the case of successive cyclic representation was dealt with.

In this paper we construct a mathematical and a simulation models of the process of working with two queues, when they move around a circle, one after another [9].

Key words: FIFO queue, casual walk, regular Markov chains.

Введение

Эффективные алгоритмы работы с несколькими Р1РО-очередями в общем пространстве памяти необходимы при разработке различных сетевых устройств и встроенных операционных систем, управляющих потоками пакетов 1гЛегпе1;, таких, например, как С18СО 1ОБ, где требования на время обработки пакетов маршрутизатором очень жесткие. Механизм страничной виртуальной памяти здесь не используется, и вся работа происходит в нескольких пулах оперативной памяти. Количество очередей в таких устройствах может достигать нескольких сотен и тысяч, а в будущем, по экспертным оценкам, может достигнуть нескольких миллионов [14]. Для представления Р1РО-очередей применяют различные программные или аппаратные решения

[4, 7, 8].

В данной статье анализируются математические модели для некоторых способов представления нескольких Р1РО-очередей в памяти одного уровня [7]. В качестве критерия оптимальности рассмотрена минимальная доля потерянных элементов при бесконечном времени работы очередей. Эту величину разумно минимизировать, когда переполнение очереди является не аварийной, а стандартной ситуацией (здесь мы подчеркиваем, что в некоторых приложениях при переполнении очереди работа программы заканчивается, и тогда в качестве критерия оптимальности надо рассматривать максимальное среднее время до переполнения памяти). Т. е., если очередь занимает всю предоставленную ей память, то все последующие элементы, поступающие в нее, отбрасываются до тех пор, пока не появится свободная память (т. е. до тех пор, пока не произойдет исключение элемента из очереди). Такая схема работы применяется, например, в работе сетевых маршрутизаторов [4] в том случае, когда по мере увеличения трафика очередь на исходящем интерфейсе маршрутизатора заполняется пакетами. Такое поведение маршрутизатора называется "сбросом хвоста" . Потери пакетов приводят к нежелательному результату, поэтому число таких ситуаций необходимо свести к минимуму. Мы в этой работе строим математическую модель в виде случайных блужданий по целочисленной пирамиде. Первоначально такие модели в виде случайного блуждания в треугольнике [10, 12, 13] были построены для решения задачи анализа процесса работы с двумя стеками, растущими навстречу друг другу, поставленной в [7]. В этих моделях предполагается, что на

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

В работе [8] приведены результаты имитационных экспериментов и поставлена задача построить математическую модель процесса работы с несколькими FIFO-очередями в общей памяти, когда операции с очередями выполняются по несколько другому принципу. В данной схеме работы на нечетном шаге допускаются операции включения элементов в одну из n очередей с равными вероятностями, а на четном шаге - операции исключения элементов из очередей с равными вероятностями. Исключение из пустой очереди не приводит к завершению работы. В [8] ставилась задача определить вероятность (как функцию от n и j) того, что очередь, выбранная для операции на j-ом шаге, будет пустой, а также вычислить математическое ожидание количества элементов в очередях после j операций. В данной задаче не рассматривался конкретный способ представления очередей в памяти, т. е. предполагалось, что очереди могут быть неограниченной длины, что на практике невыполнимо.

В [5] предложена математическая модель этого процесса для числа очередей n = 2, и решается задача оптимального разбиения общей памяти для двух FIFO-очередей в случае их последовательного циклического представления в предположении, что операции с очередями выполняются по этому принципу, но с неравными вероятностями.

В данной работе построены математическая и имитационная модели процесса работы с двумя очередями, когда они двигаются по кругу друг за другом [9]. В случае, когда одна из очередей была пустой, но ожила, она начинает работу с середины пустого места.

Для решения поставленных задач используется аппарат управляемых случайных блужданий, регулярных цепей Маркова, система Intel Math Kernel Library PARDISO*. Анализируются результаты численных экспериментов, в которых производится сравнение двух методов представления очередей. Вычисления производились с помощью кластера КарНЦ РАН.

Математическая модель

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

Операции, производимые с очередями, выполняются по следующей схеме: на нечетном шаге происходит операция включения в одну из очередей, на четном шаге - операция исключения из какой-либо очереди, причем известны некоторые вероятностные характеристики операций, производимых с очередями. Пусть pi и Р2 - вероятности включения информации в первую и вторую очереди соответственно, qi и q2 - вероятности исключения информации из первой и второй очередей соответственно.

Поскольку построенная на основе такой постановки задачи марковская цепь не будет являться регулярной и однородной, два последовательных шага объединяем в один, а также вводим следующие вероятности операций, не изменяющих длины очередей (например, чтение): ri - на нечетном шаге и Г2 - на четном шаге, при этом r1 = 0, r2 = 0.

Соответственно, p1 +р2+r1 = 1, q1 +q2+r2 =

1.

Тогда на каждом шаге могут быть выполнены следующие действия:

1. Включение в первую, исключение из второй очереди с вероятностью p1q2,

2. Включение во вторую, исключение из первой очереди с вероятностью p2q1,

3. Включение в первую очередь с вероятностью p1r2,

4. Включение во вторую очередь с вероятностью p2r2,

5. Исключение из первой очереди с вероятностью q1r1,

6. Исключение из второй очереди с вероятностью q2r1,

7. Остаться на месте с вероятностью p1q1 + P2q2 + Г1Г2,

где P1q2 + P2q1 + Р1Г2 + Р2Г2 + q1r1 + q2^ + рш + P2q2 + Г1Г2 = 1.

Предполагается, что в очередях хранятся данные фиксированного размера. При исключении информации из пустой очереди не происходит завершения работы. Область блуждания показана на рис. 1.

Рис. 1. Схема движения очередей

Целью исследования является определение средней доли потерянных элементов для сравнения со средней долей потерянных элементов при последовательном способе организации очередей в случае оптимального разбиения общей памяти [5].

Обозначим через х и у - текущие длины очередей, через г - расстояние между концом первой очереди и началом второй [7]. В качестве математической модели рассматриваем блуждание по целочисленной трехмерной пирамиде с вершиной (0,0,0) и основанием х + у + г = т.

Для учета потерянных элементов вводим два фиктивных экрана:

1. (а) г = —1 и х+у'+г = т + 1 (у' = у + 1), где блуждание переходит на экран г = —1, если происходит включение в первую очередь в то время, когда г = 0, и на экран х+у'+г = т+1, если происходит включение во вторую очередь в то время, когда х + у + г = т. В данном случае элемент будет потерян, а очереди будут находиться на экранах до тех пор, пока поступают новые элементы, в случае исключения элемента очереди вернутся в состояния, принадлежащие пирамиде.

(б) В случае, когда происходит включение во вторую очередь и исключение из первой очереди, в то время когда х + у + г = т, происходит потеря элемента и одновременно увеличение расстояния между концом второй и началом первой очереди. Поэтому для этого также необходимо

0

ввести экран, который будет учитывать данную ситуацию (х' = х — 1).

2. Если происходят операции включения и исключения из первой очереди при г = 0 либо операции включения и исключения из второй очереди при х + у + г = т, происходит потеря элемента, а очереди возвращаются в состояния, принадлежащие пирамиде. Для учета потери элемента вводим экраны г = —2 и х + у' + г = т + 2 (у' = у + 2) соответственно.

Определим схему переходов между состояниями. Пусть (x,y,z) - текущее состояние процесса, тогда блуждание по пирамиде можно описать следующим образом (1). Величина distance означает расстояние между концом первой очереди и началом второй. Если оживает первая очередь, то distance = m-y-1 , и

distance = [т-;Х-1], если оживает вторая очередь. Черта сверху состояния указывает на то, что состояние принадлежит одному из фиктивных экранов.

/ \ Г1Г2, / \

/ \ p1 ' 2 f ! ! !\ (x,y,z) -----У (x ,y ,z ) =

/ N p2r2 ( ! ! !\

/ \ q1r1 { f f f\

< \ q2ri / / / /\

/ \ Pi92v / I I l\

/ \ P2qi i }} }\

(x, y, z) --------У (x ,y ,z ) =

/ \ p1q1v

/ N p2q2 ( ! ! !\

x + 1,y,z — 1) x,y,z> 0

x + 1, 0, 0) y = 0,x<m

1, y, distance — 1) x = 0, y < m

z = 0, y = 0 либо x x = 0, y = m

x^ —1)

x, y + 1, z)

x, y + 1, z) x, y, z > 0

x, 1, distance) y = 0, x < m

0, y, 0) x = 0, y < m

x + y + z = m

0 либо x = 1

x, y + 1 , z

0, y, 0) x

x — 1,0, 0) y = 0 x — 1, y, z) иначе

x, 0, 0) y = 0 либо y = 1

0, y — 1, 0) x = 0

x, y — 1, z + 1) иначе

x +1,y — 1, z) x, y, z > 0

x +1, 0, 0) x < m, y = 0 либо y =1

1, y — 1, distance) x = 0, y < m

x, y — 1 , — 1) z = 0, y = 0 либо x = m

x, y — 1, z + 1) x = 0, y = m

x — 1,y + 1, z) x, y, z > 0 x — 1,1, distance) y = 0, x < m 0, y + 1 , 0) y < m, x = 0 либо x = 1

x',y, z) x + y + z = m

x, y, z — 1) x, y, z > 0

0, y, 0)

x, 0, 0)

=,y, —2)

x,y + 1,0)

x, y, z + 1) x, 0, 0)

0, y, 0)

x=0

y=0

z = 0, x = 0 z = 0, y = m

x, y, z > 0 y=0

x=0

x, y + 2, z + 1) x + y + z

m

m

Переходы с первого фиктивного экрана:

1) переходы с плоскости г = —1 (2):

(х,у, —1) Р2^2, / / / / \ (х , у , г ) =

(х,у, —1) У2г1к (х' ,у',г') =

(х,у, —1) Р2У2к ' ,у ' (х

(х,у, —1) Р1У2, ' ,у ' (х

(х,у, —1) Р2У1, ' ,у ' (х

, 0)

(х, у, 0) у = 0 либо у = 1

(х,у - 1,1) У > 1

(х,у + 2,1) х + у = т (х,у, 1) иначе

у = 0

(х,у — 1, —1) иначе

(ж', у, 0) х + у = т

(х — 1,у + 1, 0) иначе

2) переходы из состояний х + у' + г = т + 1 (у' = у + 1) (3):

/ , 1 \ Р1'2. / / / /\

(х, у + 1, ^) ----------> (х , у , г ) =

^ II \ 41^1 / / / /ч

(х, у + 1, ^) -----------> (х , у , г ) =

^ II N У2'1 / ' ' 'ч

(х, у + 1, ^) ----------> (х , у , г ) =

/ I 1 \ Р2 У1 . / / / /ч

/ , -| \ Р1У1, / / / /\

(х, у + 1, г) ---------> (х , у , г ) =

/ I 1 \ Р1У2, / ' ' 'ч

(х, у + 1, г) ---------> (х , у , г ) =

х + 1,у, г — 1) х,у,г> 0

х + 1, 0, 0) у = 0,х<т

1, у, йгв£атесе — 1) х = 0, у < т

г = 0, у = 0 либо х = т х = 0, у = т

х, у, —1)

,у + 1,г)

0, у, 0) х = 0 либо х = 1

х — 1, 0, 0) у = 0

х — 1, у, г) иначе

х, 0, 0) у = 0 либо у = 1

0, у — 1, 0) х = 0

х,у — 1,г + 1) иначе

х + 1,у — 1,г) х,у,г> 0

х + 1, 0, 0) х < т, у = 0 либо у = 1

1,у — 1, йгв£атесе) х = 0,у<т

г = 0, у = 0 либо х = т х = 0, у = т

(х,у,г — 1) х, у, г

(0,у, 0) х =0

(х, 0, 0) у =0

(х,у, —2) г = 0,

(х, у + 1, 0) г = 0,

х=0

у=0

х = 0, у = 0

3) переходы из состояний (ж', у, г) (ж' = ж — 1) Переходы из состояний второго фиктивного

повторяют переходы из соответствующих со- экрана повторяют переходы из соответствую-

стояний, принадлежащих пирамиде (4): щих состояний, принадлежащих пирамиде (5):

(0, у, 0) ж' = 0

(ж', у, г) ^

(ж', у, г) иначе. {Ю

(

т

(ж, y, z) ^ (ж — 1, y, z + 2) для z = —2

y=0

y=1

У + z = иначе.

m

для ж + y; + z = m + 2

Случайное блуждание будем рассматривать в виде регулярной конечной цепи Маркова с переходной матрицей Р. Зададим нумерацию так, как показано на рис. 2: сначала нумеруем состояния, принадлежащие основанию пирамиды (г = 0), далее поперечным сечениям (г = 1, 2,..., т — 1) и высоте пирамиды (г = т), затем состояния первого фиктивного экрана, последними нумеруем состояния второго фиктивного экрана.

Рис. 2. Нумерация состояний при m = 4

Нумерацию начинаем с нуля, общее количество состояний в цепи будет

Е

i=0

(i + 1)  (i + 2) + 5m2 + 7m + 4

Далее согласно введенной нумерации состояний и вышеуказанной схеме переходов составляется матрица переходных вероятностей P. В данном исследовании был установлен вид матрицы P для произвольных значений параметра m. При составлении матрицы для каждого конкретного состояния определяются те состояния, в которые процесс переходит при выполнении допустимых операций, и вычисляются соответствующие вероятности переходов. Данный процесс был автоматизирован при помощи программы на языке Си.

Следующим шагом является решение уравнения а  P = а, где а - предельный вектор для полученной марковской цепи. Для решения этого уравнения применялось средство решения Intel Math Kernel Library PARDISO* библиотеки Intel MKL. Данный инстру-

1Матрица с большим количеством нулей.

мент используется для прямого решения систем линейных алгебраических уравнений с разреженной матрицей1, причем разработаны функции как для симметричных, так и для несимметричных матриц.

Элемент вектора аг - это средняя доля времени, которое процесс проводит в состоянии г [6]. Для вычисления времени, проводимого процессом в состояниях, где происходят потери элементов очередей, нужно просуммировать элементы вектора а, соответствующие состояниям на экранах. При введенной нумерации это будут последние ^5то2+27т+4 ^ элементов вектора а.

Эксперименты и результаты

После завершения работы над моделью было проведено несколько экспериментов для возможного выявления присущих ей свойств и сравнения с ранее полученными данными и графиками.

1. Для выяснения ситуаций, когда выгоднее применить случай движения очередей по кругу, был проведен ряд вычислений с различными наборами исходных данных. Аналогичные вычисления были проведены для последовательного способа организации очередей в общей памяти при оптимальном разбиении памяти [5].

Также был рассмотрен случай, когда память заранее делится пополам при последовательном способе организации очередей. Это может быть полезно, если заранее неизвестны вероятностные характеристики операций, производимых с очередями. Некоторые полученные данные указаны в таблице, где столбцы (1) и (2) означают последовательное расположение очередей в памяти при оптимальном делении памяти и делении памяти пополам соответственно, столбец (3) - движение очередей по кругу друг за другом. Указанные результаты были подтверждены имитационными экспериментами.

Входные данные Величина потерь Т при переполнении

Р1 = 0, 4,р2 = 0, 45, д1 = 0, 4, д2 = 0, 45 0,0568543452 (в = 8) 0,0568543452 0,0319323619

Р1 = 0, 3,р2 = 0, 45, д1 = 0, 35, д2 = 0, 5 0,0190375345 (8 = 8) 0,0190375345 0,0125850917

р1 = 0,8,р2 = 0,1, д1 = 0,1, д2 = 0,8 0,7000000000 (8 = 10) 0,7000000040 0,6958703274

р1 = 0, 75, р2 = 0,1, д1 = 0,15, д2 = 0, 7 0,6000000000 (8 = 10) 0,6000000099 0,5749273399

р1 = 0, 7,р2 = 0,15, д1 = 0, 2, д2 = 0, 65 0,5000000008 (8 = 9) 0,5000000032 0,4557056302

р1 = 0,6,р2 = 0,3, д1 = 0,15, д2 = 0, 75 0,4500000039 (8 = 9) 0,4500000354 0,4455273285

р1 = 0, 4,р2 = 0, 45, д1 = 0, 6, д2 = 0, 35 0,1022326838 (5 = 6) 0,1030173486 0,0889535997

р1 = 0, 3,р2 = 0, 6, д1 = 0, 45, д2 = 0, 45 0,1502357136 (8 = 6) 0,1514556020 0,1200671464

Р1 = 0, 25, Р2 = 0, 65, д1 = 0, 45, д2 = 0, 45 0,1901271731 (8 = 5) 0,2002810614 0,1943398747

р1 = 0, 2,р2 = 0, 3, д1 = 0, 45, д2 = 0, 05 0,2500009312 (8 = 7) 0,2500844509 0,3931085764

р1 = 0,3,р2 = 0, 5, д1 = 0,1, д2 = 0,8 0,2000042218 (8 = 8) 0,2000042218 0,3319594498

0,05 0,1 0,15 0,2 0,25 0,3 0,35 0,4 0,45

1>

Рис. 3. Потери при постоянной величине д

0,8

0,05 0,1 0,15 0,2 0,25 0,3 0,35 0,4 0,45

ч

Рис. 4. Потери при постоянной величине р

По этим данным видно, что при движении очередей по кругу потери меньше в двух случаях:

(а) вероятности включения и исключения в очереди равны (либо практически равны). Это можно прокомментировать тем, что в такой ситуации обе очереди равномерно двигаются друг за другом по кругу, не переполняясь;

(б) вероятность включения в одну из очередей намного больше, чем вероятность включения в другую очередь, а вероятность исключения из этой очереди - намного меньше, чем из другой. Данный случай объясняется тем, что при данных условиях та из очередей, вероятность включения в которую меньше, практически не занимает места в памяти, соответственно, теряется меньше включаемых элементов.

В других случаях лучше использовать оптимальное разбиение памяти в последовательном способе организации очередей. Если же вероятностные характеристики вообще неизвестны, предпочтительнее делить память пополам при последовательном расположении очередей.

2. Пусть Р1 = Р2 = р, <?1 = <?2 = д, т. е. рассматриваем ситуацию равновероятного включения и исключения информации из очередей, тогда г1 = 1 — 2р, г2 = 1 — 2д.

В данных условиях были построены графики зависимости суммарных потерь от изменения р при постоянной величине д (рис. 3), и от изменения д при постоянной величине р (рис. 4).

Подобные графики были также представлены в работе [5].

Работа выполнена при финансовой поддержке гранта РФФИ (проект 12-01-00253) и Программы стратегического развития ПетрГУ в рамках реализации комплекса мероприятий по развитию научно-исследовательской деятельности.

Литература

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

2. Аксенова Е. А., Лазутина А. А., Соколов А. В. Исследование немарковской модели управления стеком в двухуровневой памяти // Программирование. 2004. № 1. С. 1-10.

3. Аксенова Е. А., Соколов А. В. Оптимальное управление двумя параллельными стеками // Дискретная математика. 2007. № 1. С. 67-75.

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

5. Каблукова Н. В., Соколов А. В. Оптимальное разбиение общей памяти для двух последовательных циклических FIFO-очередей // Прикладная информатика. 2012. № (40). С. 113-125.

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

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

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

9. Соколов А. В. Математические модели и алгоритмы оптимального управления динамическими структурами данных. Петрозаводск: ПетрГУ, 2002. 216 с.

10. Соколов А. В. О распределении памяти для двух стеков // Автоматизация эксперимента и обработки данных. Петрозаводск: изд-во Карельского филиала АН СССР, 1980. С. 65-71.

11. Aksenova E. A., Sokolov A. V. The optimal implementation of two FIFO-queues in single-level memory // Applied Mathematics. 2011. Vol. 2, N 10. P. 1297-1302.

12. Flajolet P. The evolution of two stacks in bounded space and random walks in a triangle // Lecture Notes in Computer Science. 1986. Vol. 223. P. 325-340.

13. Louchard G., Schott R., Tolley M., Zimmermann P. Random walks, heat equation and distributed algorithms // Journal of Computational and Applied Mathematics. 1994. N 53. P. 243-274.

14. Nikologiannis A., Katevenis M. Multi-Queue Management for Advanced QoS in High-Speed Communication Systems Computer Architecture and VLSI Systems Lab, Institute of Computer Science (ICS) Head.

http://archvlsi.ics.forth.gr/muqpro/ queueMgt.html

СВЕДЕНИЯ ОБ АВТОРАХ:

Каблукова Наталья Вениаминовна

студентка

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

ул. Ленина, 33, Петрозаводск, Республика Карелия,

Россия, 185910

эл. почта: xituska@mail.ru

Соколов Андрей Владимирович

ведущий научный сотрудник

Институт прикладных математических исследований Карельского научного центра РАН ул. Пушкинская, 11, Петрозаводск, Республика Карелия, Россия, 185910 эл. почта: avs@krc.karelia.ru тел.: (8142) 766312

Kablukova, Natalia

Petrozavodsk State University

33 Lenina St., 185910 Petrozavodsk, Karelia, Russia e-mail: xitushka@mail.ru

Sokolov, Andrey

Institute of Applied Mathematical Research, Karelian Research Centre, Russian Academy of Sciences 11 Pushkinskaya St., 185910 Petrozavodsk, Karelia, Russia

e-mail: avs@krc.karelia.ru tel.: (8142) 766312