Известия РАН. Теория и системы управления, 2019, № 5, стр. 56-74

Введение. При разработке математических моделей процессов обработки запросов в компьютерных и коммуникационных системах, как правило, предполагается, что серверы являются идентичными по всем показателям (по скорости обработки запросов, надежности, стоимости эксплуатации и т.д.). Однако допущение о том, что сервера идентичны зачастую является грубым приближением к реальной ситуации, так как в процессе расширения существующих систем приходится использовать гетерогенные сервера (heterogeneous servers (HS)). Сервера с различными скоростями особенно часто встречаются в системах, где в процессе обработки запросов участвуют не машины (аппараты, компьютеры и т.д.), а люди.

Вкратце рассмотрим публикации, посвященные математическому анализу систем с гетерогенными серверами.

Прежде всего отметим, что в отличие от систем с гомогеными серверами, в системах с гетерогенными серверами важное значение имеют правила доступа запросов к серверам. Наиболее часто используемыми правилами являются рандомизированный доступ (randomized access), упорядоченный доступ (ordered entry), а также доступ, основанный на схеме “первым используется быстрый сервер” (fast server first (FSF)). При рандомизированном доступе с равными вероятностями назначается один из свободных серверов; при упорядоченном доступе заранее все сервера нумеруются и назначается свободный сервер, который имеет минимальный номер; при FSF-схеме доступа всегда назначается сервер, который имеет максимальную скорость среди всех свободных серверов.

Первая публикация, посвященная изучению систем с HS, была [1]. В ней рассматривалась марковская система с бесконечной очередью и рандомизированным доступом. Предложены формулы для нахождения вероятностей состояний и среднее число запросов в системе и в очереди. Указывается, что в частном случае, когда все серверы являются гомогенными (идентичными), получаются известные классические результаты. Кроме того, показано, что если скорости HS сильно отличаются друг от друга, то замена исходной системы на систему с аналогичным числом гомогенных серверов, где скорость каждого сервера равна среднеарифметическому значению гетереогенных серверов, ведет к тому, что характеристики этих систем будут сильно отличаться друг от друга; иначе если скорости HS мало отличаются друг от друга, то “ощибка” будет незначительной.

После данной работы модели систем с HS долгое время не подвергались исследованиям, и лишь с 70-х годов прошлого века начались интенсивные исследования таких систем. В [2, 3] вычислены характеристики систем с двумя и тремя серверами и рандомизированным доступом. Полученные результаты сравниваются с аналогичными результатами систем с гомогенными серверами.

Одним из ведущих направлений было обобщение классических результатов, полученных ранее для систем с гомогенными серверами. Так, в [4] предложено обобщение известной В-формулы Эрланга для системы с гетерогенными серверами без буфера для ожидания заявок и произвольной функцией распределения (ф.р.) времени их обслуживания с рандомизированным доступом. В [5 ] рассмотрено обобщение последней модели, т.е. в ней считается, что поступающие запросы могут терятся с определенными вероятностями, если даже в моменты их поступления имеются свободные сервера, при этом эти вероятности зависят от числа свободных серверов. Получен аналог В-формулы Эрланга для такой модели и показано, что в стациоанарном режиме выходящий поток также является Пуассоновским. Согласно [6], вероятность потери в марковской системе с гетерогенными серверами и без буфера для ожидания заявок имеет минимальное значение при использовании FSF-схемы доступа.

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

Подробно изучены модели, в которых принято правило упорядоченного доступа [8–16]. Детальный анализ этих работ можно найти в [16], где предложен метод нахождения вероятности потери в системе с гетерогенными серверами без буфера для ожидания заявок и произвольной ф.р. интервалов между поступлениями запросов.

Практический интерес представляют работы, в которых учитывается эффект катастрофы [17–21] (это такое случайное явление, при возникновании которого система полностью прекращает работу и все запросы теряются) и прогулки серверов [22–25]. В [26] изучается модель системы, в которой HS расположены не параллельно, а последовательно. Определенный научный интерес представляют работы, в которых изучаются асимптотические свойства систем при наличии огромного количества HS [27–30]. Здесь же отметим, что из-за сложности математического анализа в них в основном рассматриваются модели систем с двумя или тремя серверами [31–34].

Задачи оптимизации систем обслуживания с HS имеют важное практическое значение. Они подробно рассмотрены в монографии [35]. Следует отметить, что методы многокритеральной оптимизации являются эффективным аппаратом для решения задач оптимального распределения ресурсов гетерогенных вычислительных систем [36, 37] (в них можно найти подробный список работ в этом направлении).

Анализ доступной литературы показал, что до сих пор изучались модели систем обслуживания с HS при наличии лишь идентичных (по важности) запросов. Авторам неизвестны работы, посвященные изучению моделей систем обслуживания с HS и разнотипными запросами, хотя наличие HS подсказывает о необходимости определенной классификации обрабатываемых в них запросов. Иными словами, для повышения экономической эффективности (относительно выбранного критерия качества) работы системы с HS следует выделить высокоприоритетные (H-запросы) и низкоприоритетные запросы (L-запросы) и организовать обработки H-запросов в высокоскоростных серверах (F-серверы), а медленные сервера (S-сервера) будут обрабатывать L-запросы.

Если принимается конкретная классификация запросов, то в системах с HS естественным образом возникает проблема введения надлежащих приоритетов для организации обслуживания разнотипных запросов. Хорошо известно, что независящие от состояния системы приоритеты (внесистемные приоритеты) являются малоэффективными, и потому для повышения экономической эффективности системы следует использовать зависящие от состояния системы приоритеты (внутрисистемные приоритеты).

Среди разнообразных приоритетов особое место занимают скачкообразные приоритеты (jump priorities (JP)), которые легко реализуются на практике. Эти приоритеты в дискретных (по времени) системах с одним сервером и бесконечными буферами для ожидания разнотипных запросов впервые были определены в [38–40]. В них предполагалось, что скачки L-запросов в очередь H-запросов происходят, согласно схеме Бернулли, с постоянными параметрами. В дальнейшем зависящие от состояния JP в непрерывных (по времени) системах с одним сервером и конечными буферами (раздельными или общий) для ожидания разнотипных запросов определены в [41, 42], в которых также решены задачи их оптимизации.

Следует отметить, что использование JP в системах с гетерогенными серверами напрашивается само по себе, так как в таких системах именно за счет введения зависящих от состояния системы JP можно организовать переход L-запроса в очередь H-запросов и таким образом избежать нежелательной ситуации долгого ожидания в очереди L-запросов. При этом также следует учитывать и ограничения, предъявляемые к качеству обслуживания H-запросами.

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

1. Описание моделей и постановка задачи. Сначала рассмотрим системы с раздельными очередями разнотипных запросов. Ее структурная схема показана на рис. 1. Система содержит два гетерогенных сервера: быстрый (F-сервер) и медленный серверы (S-сервер). Эти серверы предназначены для обслуживания потоков запросов двух типов – высокоприоритетных (H-запросы) и низкоприоритетных (L-запросы), при этом H-запросы обслуживаются в F-сервере, а L-запросы – в S-сервере.

Считается, что оба потока запросов являются пуассоновскими с интенсивностями ${{\lambda }_{H}}$ и ${{\lambda }_{L}}$ для H-запросов и L-запросов соответственно. Время обслуживания запросов в обоих серверах являются случайными величинами с показательной ф.р.; среднее время обслуживания в F-сервере и S-сервере равны $\mu _{F}^{{ - 1}}$ и $\mu _{S}^{{ - 1}}$ соответственно, при этом скорость обслуживания F-сервера больше, чем скорость обслуживания S-сервера, т.е. ${{\mu }_{F}} > {{\mu }_{S}}$.

Для ожидания запросов в очереди имеются раздельные буфера конечных размеров, при этом максимальное число H-запросов и L-запросов в системе равны ${{K}_{H}}$ и ${{K}_{L}}$. Иными словами, размер буфера для H-запросов (H-буфер) равен ${{K}_{H}} - 1$, а соответствующий буфер для L-запросов (L-буфер) имеет размерность ${{K}_{L}} - 1$.

Для предотвращения “старения” L-запросов в очереди рандомизированные JP определяются следующим образом. Поступающие H-запросы всегда присоединяются к H-буферу, если там имеется свободное место. Вместе с тем L-запросы в зависимости от состояния системы могут переходить в H-буфер, при этом состояния системы в каждый момент времени задаются двумерным вектором (${{n}_{H}},{{n}_{L}}$), где компоненты ${{n}_{H}}$ и ${{n}_{L}}$ указывают на число H-запросов и L-запросов в системе соответственно. Иными словами, в момент поступления L-запроса один из них с вероятностью $J\left( {{{n}_{H}},{{n}_{L}}} \right)$, $0 < J\left( {{{n}_{H}},{{n}_{L}}} \right) \leqslant 1$, переходит в H-буфер (если там имеется свободное место) или с дополнительной вероятностью $1 - J\left( {{{n}_{H}},{{n}_{L}}} \right)$ либо присоединяется в L-буфер (если тут имеется свободное место), либо покидает систему необслуженным (если тут не имеется свободное место). Если L-запрос переходит в H-буфер, то в дальнейшем он обслуживается как H-запрос.

На практике зависящие от состояния рандомизированные JP $J\left( {{{n}_{H}},{{n}_{L}}} \right)$ могут быть определены различными способами. Так, интуитивно эффективным и легко реализумым способом задания этих приоритетов является следующая схема их определения. Вводится некоторый пороговый параметр r, $1 \leqslant r \leqslant {{K}_{L}}$, и если в момент поступления L-запроса разница между числом L-запросов и H-запросов меньше, чем $r,$ то поступивший L-запрос присоединяется к L-буферу; иначе один из L-запросов (для определенности считается, что L-запрос, стоящий в начале очереди) либо с вероятностью $\alpha $ переходит в конец очереди H-буфера (если там имеется свободное место), либо с вероятностью $1 - \alpha $ поступивший L-запрос принимается в L-буфер при наличии тут свободных мест; иначе он с такой же вероятностью теряется. Если в момент поступления L-запроса H-буфер переполнен, то $J\left( {{{K}_{H}},{{n}_{L}}} \right) = 0$ для любого ${{n}_{L}}$. Иными словами, в этой схеме рандомизированные JP $J\left( {{{n}_{H}},{{n}_{L}}} \right)$ определяются так:

Ниже для определенности изложения используются JP, которые определяются соотношением (1.1). Если в соотношение (1.1) считать, что α = 1, то получаются детерминированные JP, т.е. каждый раз, когда разница между числом L-запросов и H-запросов не меньше, чем r, то L-запрос, стоящий в начале очереди, присоединяется к очереди H-запросов.

В случае системы с общей очередью для разнотипных запросов считается, что размер буфера равен K, $K < \infty $ , при этом после изменения типа L-запрос остается в том же буфере, но он рассматривается уже как H-запрос. Здесь допустимыми значениями порогового параметра r являются $1 \leqslant r \leqslant K$. В этой модели возможны ситуации, когда общий буфер полностью занят запросами одного типа, но сервер, который обслуживает запросы другого типа, свободен, а поступающий запрос соответствующего типа не может занимать свободный сервер. Для устранения подобных нежелательных ситуаций в этой модели принимается следующая схема доступа: если буфер полностью оккупирован H-запросами (L-запросами), а S-сервер (F-сервер) является свободным, то при поступлении L-запроса (H-запроса) допускается доступ данного запроса прямо к S-серверу (F-сервер), минуя процесс буферизации.

Задача состоит в нахождении совместного распределения числа разнотипных запросов в описанных выше системах с гетерогенными серверами и разработке методов вычисления их характеристик.

2. Точный метод расчета вероятностей состояний и характеристик изучаемых систем. Сначала рассмотрим системы с раздельными очередями. Математической моделью системы является двумерная цепь Маркова (ЦМ) с состояниями вида $\left( {{{n}_{H}},{{n}_{L}}} \right)$, при этом ее пространство состояний определяется как $E = \{ \left( {{{n}_{H}},{{n}_{L}}} \right){\text{:}}\;{{n}_{H}} = \overline {0,{{K}_{H}}} ,\;{{n}_{L}} = \overline {0,{{K}_{L}}} \} $.

Рассмотрим задачи определения элементов производящей матрицы (ПМ) данной ЦМ, которые определяют интенсивности переходов между ее состояниями (см. рис. 2, a).

Замечание 1. Во избежание загромождений на рис. 2, а, б на дугах графов указаны интенсивности переходов лишь для тех состояний, начиная с которого эти интенсивности в соответствующих строках и столбцах не меняются. В графах жирными кружками обозначены состояния, в которых возможны скачки L-запросов. В них также приняты следующие обозначения: $x = \left( {1 - \alpha } \right){{\lambda }_{L}}$, $y = {{\lambda }_{H}} + \left( {1 - \alpha } \right){{\lambda }_{L}}$.

Пусть $q(({{n}_{H}},{{n}_{L}}),(n_{H}^{'},n_{L}^{'}))$ – интенсивность перехода из состояния $({{n}_{H}},{{n}_{L}}) \in E$ в состояние $(n_{H}^{'},n_{L}^{'}) \in E$. Учитывая соотношение (1.1) эти величины определяются следующим образом (для простоты изложения ниже указываются лишь положительные элементы ПМ):

случаи ${{n}_{L}} - {{n}_{H}} < r$:

случаи ${{n}_{L}} - {{n}_{H}} \geqslant r$:

Из формул (2.1) и (2.2) заключаем, что все состояния изучаемой ЦМ сообщаются друг с другом (см. рис. 2, а), т.е. существуют стационарные вероятности состояний. Пусть p(n_H, n_L), $({{n}_{H}},{{n}_{L}}) \in E,$ обозначают вероятности состояний этой ЦМ. Известно, что эти вероятности находятся в результате решения соответствующей системы уравнений равновесия (СУР), которая составляется на основе соотношений (2.1), (2.2) (из-за очевидности ее составления явный вид этой СУР здесь не приводится).

После нахождения вероятностей состояний системы удается определить характеристики исследуемой системы, которые представляют собой маргинальные распределения данной цепи: вероятности потери разнотипных запросов; средняя интенсивность скачков L-запросов в H-буфер; среднее число разнотипных запросов в системе.

Поскольку H-запросы теряются лишь тогда, когда в моменты их поступления в системе уже имеются K_H запросов данного типа, то вероятность потери H-запросов $\left( {P{{B}_{H}}} \right)$ определяется как

Для нахождения вероятности потери L-запросов следует рассматривать состояния типа $\left( {{{n}_{H}},\,{{K}_{L}}} \right)$, при этом необходимо различать два случая: 1) $0 \leqslant {{n}_{H}} \leqslant {{K}_{L}} - r$; 2) ${{K}_{L}} - r < {{n}_{H}} \leqslant {{K}_{L}}$. Если в момент поступления L-запроса имеет место случай 1), то он теряется с вероятностью 1 – α, а в случаях 2) этот запрос теряется с вероятностью единица. Следовательно, используя формулы полной вероятности, заключаем, что вероятность потери L-запросов $\left( {P{{B}_{L}}} \right)$ определяется следующим образом:

Скачки L-запросов в H-буфер происходят в моменты поступления L-запросов с вероятностью α, если в эти моменты система находится в состоянии $\left( {{{n}_{H}},\,{{n}_{L}}} \right)$, в котором выполняется условие ${{n}_{L}} - {{n}_{H}} \geqslant r$. Отсюда заключаем, что средняя интенсивность скачков L-запросов в H-буфер $\left( {R{{J}_{{LH}}}} \right)$ вычисляется как

Среднее число H-запросов $\left( {{{N}_{H}}} \right)$ и L-запросов $\left( {{{N}_{L}}} \right)$ в системе определяются как математические ожидания соответствующих случайных величин, т.е.

Таким образом, приведенные выше формулы (2.1)–(2.7) позволяют вычислить стационарные вероятности состояний и характеристик системы с раздельными очередями.

Теперь рассмотрим системы с общей очередью. Как и выше, математической моделью данной системы является двумерная ЦМ с состояниями вида $\left( {{{n}_{H}},{{n}_{L}}} \right),$ но здесь ее пространство состояний определяется как

где ${{x}^{ + }} = \max \left( {0,x} \right)$ (см. рис. 2, б).

Элементы ПМ данной ЦМ определяются аналогично (2.1), (2.2), но при этом в правой части формулы (2.1) в первой и во второй строке оба условия ${{n}_{H}} < {{K}_{H}}$ и ${{n}_{L}} < {{K}_{L}}$ заменяются условием ${{\left( {{{n}_{H}} - 1} \right)}^{ + }} + {{\left( {{{n}_{L}} - 1} \right)}^{ + }} < K$.

Далее составляется соответствующая СУР для стационарных вероятностей состояний данной модели и определяются характеристики изучаемой системы. В результате анализа работы системы, заключаем, что искомые характеристики (2.3)–(2.7) для данной модели определяются из следующих формул:

Разработанный выше подход для нахождения стационарных вероятностей состояний и с их помощью характеристик изучаемых моделей систем с гетерогоенными серверами является точным и легко реализуется для моделей умеренной размерности. Вместе с тем, с ростом размерности моделей применение разработанного подхода требует неоправданно больших затрат машинного времени. Более того, в случаях плохой обусловленности ПМ изучаемой модели возникают проблемы вычислительной неустойчивости. Известные матрично-геометрические методы [43–45] частично решают эти проблемы (о недостатках этих методов см. [46]).

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

3. Приближенный метод расчета вероятностей состояний и характеристик системы. Сначала рассмотрим системы с раздельными очередями. Предложенный метод основан на принципах фазового укрупенения состояний двумерных ЦМ. Его применение требует расщепления ПС модели на такие классы, чтобы интенсивности переходов между состояниями внутри классов намного превосходили интенсивности между состояниями из разных классов.

В данной модели такое расщепление легко осуществляется. Действительно, поскольку F-сервер имеет более высокую скорость обслуживания, чем S-сервер, и принимая допущение о том, что интенсивность H-запросов намного больше, чем интенсивность L-запросов, то разбиение графа состояний по строкам (см. рис. 2а) удовлетворяет указанному выше требованию. Иными словами, рассматривается следующее расщепление ПС модели:

где ${{E}_{l}} = \{ (h,l) \in E:h = \overline {0,{{K}_{H}}} \} $, $l = \overline {0,{{K}_{L}}} $.

Замечание 2. Здесь и далее во избежание многоярусных индексов и для упрощения обозначений в некоторых формулах вектор состояния $\left( {{{n}_{H}},{{n}_{L}}} \right)$ заменяется на вектор (h, l).

На основе расщепления (3.1) ПС исходной модели все микросостояния внутри каждого класса ${{E}_{l}}$ объединяются в одно укрупненное состояние $\left\langle l \right\rangle $, и таким образом, определяется множество укрупненных состояний $\Omega = \{ \left\langle l \right\rangle {\text{:}}\;l = \overline {0,{{K}_{L}}} \} $.

Приближенные значения вероятностей состояний $\tilde {p}\left( {h,l} \right)$, $\left( {h,l} \right) \in E$ исходной модели определяются как [46]

где ${{\rho }_{l}}(h)$ – вероятность состояния $\left( {h,l} \right)$ внутри расщепленной модели с пространством состояний ${{E}_{l}}$, а $\pi \left( {\left\langle l \right\rangle } \right)$ – вероятность укрупненного состояния $\left\langle l \right\rangle \in \Omega $.

Для вычисления ${{\rho }_{l}}(h)$ необходимо раздельно рассматривать два случая: 1) $0 \leqslant l \leqslant r - 1$; 2) $r \leqslant l \leqslant {{K}_{L}}$.

Для первого случая из соотношений (2.1) получаем, что искомые вероятности состояний внутри всех расщепленных моделей с пространством состояний ${{E}_{l}}$, $0 \leqslant l \leqslant r - 1$, совпадают с вероятностями состояний одномерного процесса размножения-гибели с постоянными интенсивностями (см. рис. 2, а), т.е.

где ${{{{\nu }_{H}} = {{\lambda }_{H}}} \mathord{\left/ {\vphantom {{{{\nu }_{H}} = {{\lambda }_{H}}} {{{\mu }_{F}}}}} \right. \kern-0em} {{{\mu }_{F}}}}$.

Для второго случая из соотношений (2.2) получаем, что вероятности состояний внутри расщепленной модели с пространством состояний E_l, $r \leqslant l \leqslant {{K}_{L}}$, совпадают с вероятностями состояний одномерного процесса размножения-гибели с переменными интенсивностями (см. рис. 2, а), т.е.

где ${{\rho }_{l}}\left( 0 \right)$ находится из условия нормировки, т.е. ${{\rho }_{l}}\left( 0 \right) + ... + {{\rho }_{l}}\left( {{{K}_{H}}} \right) = 1$ для каждого l, $r \leqslant l \leqslant {{K}_{L}}$. Здесь и далее приняты следующие обозначения: $b = {{{{\lambda }_{L}}} \mathord{\left/ {\vphantom {{{{\lambda }_{L}}} {{{\mu }_{F}}}}} \right. \kern-0em} {{{\mu }_{F}}}}$, $c = {{{{\lambda }_{L}}} \mathord{\left/ {\vphantom {{{{\lambda }_{L}}} {{{\lambda }_{H}}}}} \right. \kern-0em} {{{\lambda }_{H}}}}$.

Пусть $q\left( {\left\langle {{{l}_{1}}} \right\rangle ,\left\langle {{{l}_{2}}} \right\rangle } \right)$, $\left\langle {{{l}_{1}}} \right\rangle ,\left\langle {{{l}_{2}}} \right\rangle \in \Omega $ обозначает интенсивность перехода из укрупненного состояния $\left\langle {{{l}_{1}}} \right\rangle $ в укрупненное состояние $\left\langle {{{l}_{2}}} \right\rangle $. Тогда с учетом результатов [46] после определенных математических выкладок находим, что указанные интенсивности переходов вычисляются следующим образом:

где

Следовательно, из (3.5) имеем

где ${{\nu }_{L}} = {{{{\lambda }_{L}}} \mathord{\left/ {\vphantom {{{{\lambda }_{L}}} {{{\mu }_{S}}}}} \right. \kern-0em} {{{\mu }_{S}}}}$, ${{\tilde {\nu }}_{L}} = {{\tilde {\lambda }} \mathord{\left/ {\vphantom {{\tilde {\lambda }} {{{\mu }_{S}}}}} \right. \kern-0em} {{{\mu }_{S}}}}$. Вероятность $\pi \left( {\left\langle 0 \right\rangle } \right)$ находится из условия нормировки, т.е. $\pi (\langle 0\rangle ) + \ldots + \pi (\langle {{K}_{L}}\rangle )$ = 1.

С учетом соотношений (3.3)–(3.6) из (3.2) вычисляются приближенные значения вероятностей состояний. После нахождения этих вероятностей легко определяются приближенные значения характеристик (2.3)–(2.7) системы с раздельными очередями:

Далее вкратце рассмотрим применение разработанного приближенного подхода для изучения системы с общей очередью. В данном случае вероятности состояний внутри расщепленных моделей с пространством состояний E_l при $0 \leqslant l \leqslant r - 1$ и при $r \leqslant l \leqslant K + 1$ также вычисляются по формулам (3.3) и (3.4) соответственно, но при этом в этих формулах параметр K_H заменяется параметром $K + 1 - {{\left( {h - 1} \right)}^{ + }}$. Интенсивности переходов между состояниями укрупненной модели определяются аналогично (3.5), где в правой части этой формулы во второй строке параметр K_L заменяется на K + 1, а параметр ${{K}_{H}}$ (см. выражение для параметра $\tilde {\lambda }$), как и выше, заменяется параметром $K + 1 - {{\left( {h - 1} \right)}^{ + }}$. Следовательно, вероятности укрупненных состояний вычисляются по формуле (3.6), где параметр K_L опять заменяется на K + 1.

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

4. Численные результаты. Проводимые здесь численные эксперименты имеют три цели: 1) оценить точность разработанных приближенных формул для расчета стационарных вероятностей состояний и характеристик изучаемых систем; 2) изучить зависимость этих характеристик от значений порогового параметра $r$ скачкообразных приоритетов; 3) решить задачи оптимизации этих характеристик.

Сначала рассмотрим результаты для модели с раздельными очередями. Относительно первой цели отметим, что точность приближенных значений вероятностей состояний оценивается с помощью следующих мер близости [46]:

подобия косинуса:

максимум разностей:

Результаты сравнительного анализа значений вероятностей состояний при точном и приближенном подходах показаны в табл. 1. Здесь исходные данные модели выбраны так: ${{\mu }_{F}} = 50$, ${{\mu }_{S}}$ = 30, $\alpha = 0.2$. Кроме того, для двух пар размеров буферов $\left( {{{K}_{H}},{{K}_{L}}} \right) = \left( {5,5} \right)$ и $\left( {{{K}_{H}},{{K}_{L}}} \right) = \left( {10,5} \right)$ значения порогового параметра $r = 3$, а для пары $({{K}_{H}},{{K}_{L}})$ = (10, 10) выбран $r = 8$.

Из табл. 1 видно, что мера близости (4.1) равна почти 1, а также в подавляющем большинстве экспериментов точные и приближенные значения вероятностей состояний в наихудших случаях отличаются в третьем знаке после десятичной точки, иными словами, на высокую степень точности разработанных приближенных формул указывает и мера близости (4.2). Заметим, что проведенные численные эксперименты показали и высокую степень точности разработанных приближенных формул для характеристик (2.3)–(2.7), при этом в них исходные данные остались прежними (см. табл. 2 и 3).

Относительно второй цели численных экспериментов отметим, что здесь изучается поведение характеристик моделей при изменении значений порогового параметра r; при этом сравниваются характеристики системы при использовании детерминированных ($\alpha = 1$) и рандомизированных JP ($\alpha < 1$).

На рис. 3 показаны зависимости характеристик системы от параметра $r$ в модели с раздельными очередями, при этом исходные параметры системы выбираются так: ${{\lambda }_{H}} = 50$, ${{\lambda }_{L}} = 30$, ${{\mu }_{F}} = 40$, ${{\mu }_{S}} = 20$, ${{K}_{H}} = {{K}_{L}} = 10$.

Из рис. 3, а видно, при использовании обоих типов JP функция $P{{B}_{H}}$ – убывающая функция. Этого следовало ожидать, так как с ростом параметра r L-запросы реже переходят в H-буфер, и тем самым увеличиваются шансы H-запросов для доступа в свой буфер; также ожидаемым является тот факт, что при использовании детерминированных JP, вероятность потери H-запросов больше, чем при использовании рандомизированных JP. Действительно, при использовании детерминированных JP L-запросы с большей интенсивностью переходят в H-буфер, чем при использовании рандомизированных JP, иными словами, при использовании рандомизированных JP H-запросы имеют больше шансов для доступа в буфер.

Обратная картина наблюдается для функции $P{{B}_{L}}$, т.е. она является возрастающей функцией и при использовании детерминированных JP, вероятность потери L-запросов меньше, чем при использовании рандомизированных JP (см. рис. 3, б). Возрастание этой функции объясняется тем, что, как это было отмечено выше, с ростом параметра r L-запросы реже переходят в H-буфер, и тем самым они больше загружают свой буфер, т.е. уменьшаются шансы L-запросов для доступа в свой буфер. С другой стороны, при использовании детерминированных JP L-запросы с большей интенсивностью переходят в H-буфер, чем при использовании рандомизированных JP, и тем самым при использовании детерминированных JP L-запросы имеют больше шансов для доступа в свой буфер.

Как и следовало ожидать, функция $R{{J}_{{LH}}}$ является убывающей относительно параметра $r$, так как с ростом этого параметра уменьшается интенсивность перехода L-запросов в H-буфер, при этом эта величина при использовании детерминированных JP больше, чем при использовании рандомизированных JP (см. рис. 3, в).

Функция N_H является убывающей (см. рис. 3, г), так как с ростом параметра r уменьшается интенсивность перехода L-запросов в H-буфер, и тем самым уменьшается среднее число H-запросов в системе; здесь значения этой функции больше при использовании детерминированных JP, так как при этом интенсивность переходов из L-буфера в H-буфер больше, чем при использовании рандомизированных JP.

Поведение функции N_L отличается от поведения функции N_H (см. рис. 3, д). Несколько неожиданным, на первый взгляд, кажется факт о том, что при использовании детерминированных JP среднее число L-запросов в системе чуть больше, чем при использовании рандомизированных JP (вообще значения этой функции при использовании обоих типов JP почти совпадают). Однако этот факт имеет следующее объяснение: при использовании детерминированных JP и при малых значениях параметра $r$ интенсивность перехода L-запросов в H-буфер больше, чем при рандомизированных JP, и тем самым при использовании детерминированных JP все больше шансов появляются для доступа L-запросов в свой буфер.

Теперь рассмотрим результаты для модели с общей очередью. Для данной модели результаты сравнительного анализа значений вероятностей состояний при точном и приближенном подходах показаны в табл. 4. Здесь исходные данные модели выбраны так: ${{\mu }_{F}} = 50$, ${{\mu }_{S}} = 35$, $\alpha = 0.2$. Из табл. 5 и 6 видно, что и для такой модели предложенные алгоритмы имеют высокую точность.

На рис. 4 приводятся графики, которые показывают поведение характеристик этой модели при изменении значений порогового параметра r; при этом сравниваются характеристики системы при использовании детерминированных и рандомизированных скачкообразных приоритетов. Нагрузочные параметры системы выбираются, как и для модели с раздельными очередями, а размер общего буфера K = 10.

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

Из рис. 4, а видно, как и в случае модели с раздельными очередями (см. рис. 3, а), что при использовании обоих типов JP функция $P{{B}_{H}}$ является убывающей функцией. При использовании детерминированных JP вероятность потери H-запросов больше, чем при использовании рандомизированных JP. Несмотря на то, что в данной модели размер общего буфера (K = 10) в 2 раза меньше, чем суммарный размер общего буфера в модели с раздельными буферами (${{K}_{H}} = {{K}_{L}}$ = 10), здесь при использовании обоих типов JP вероятности потери H-запросов оказываются меньше, чем в модели с раздельными буферами (см. также рис. 3, а). Вместе с тем здесь, как и в случае модели с раздельными буферами, при использовании детерминированных JP вероятность потери H-запросов больше, чем при использовании рандомизированных JP.

В отличие от модели с раздельными буферами (см. рис. 3, б) функция $P{{B}_{L}}$ здесь не является возрастающей функцией, одновременно она и не является убывающей (см. рис. 4, б). Это объясняется тем, что с ростом параметра r L-запросы реже меняют свой тип, и тем самым загрузка F-сервера уменьшается, следовательно, уменьшается и тотальная загрузка общего буфера, т.е. уменьшается и вероятность потери L-запросов. Вместе с тем с ростом параметра $r$ эти запросы больше загружают свой медленный S-сервер, т.е. следует ожидать, что при определенных значениях нагрузочных параметров разнотипных запросов загрузка общего буфера будет возрастать, что является причиной увеличения вероятности потери L-запросов. Здесь, как и в случае модели с раздельными буферами, при использовании рандомизированных JP вероятность потери L-запросов больше, чем при использовании детерминированных JP. Однако абсолютные значения вероятности потери L-запросов при использовании JP различного типа отличаются друг от друга лишь в третьем знаке после десятичной точки.

Функция $R{{J}_{{LH}}}$ в этой модели также является убывающей (см. рис. 4, в), при этом, как и следовало ожидать, значения этой функции при использовании детерминированных JP больше, чем при использовании рандомизированных JP. Следует также отметить, что абсолютные значения этой функции в несколько раз меньше, чем в модели с раздельными очередями (см. также рис. 3, в).

Функция N_H, как и в модели с раздельными очередями, является убывающей (см. рис. 4, г), при этом, как и при использовании детерминированных JP, значения этой функции больше, чем при использовании рандомизированных JP. Интересным является факт о том, что в обеих моделях абсолютные значения этой функции при использовании JP обоих типов близки друг другу (см. рис. 3, г).

Неожиданным оказывается поведение функции N_L, так как вопреки ожиданиям с ростом параметра r она хоть с очень малой скоростью, но растет (рис. 4, д), т.е. разница между максимальным и минимальным значениями этой функции составляет меньше 0.5. Это объясняется тем, что с ростом параметра r эти запросы больше загружают свой медленный S-сервер, и именно за счет этого имеется такая малая разница. Вместе с тем, как и следовало ожидать, значения этой функции при использовании детерминированных JP меньше, чем при использовании рандомизированных JP. Следует также отметить, что абсолютные значения этой функции почти 2 раза меньше, чем в модели с раздельными очередями.

Интересно отметить, что в моделях обеих типов с ростом параметра r значения всех функций при использовании JP обоих типов очень близки и при $r = {{K}_{L}}$ их разница имеет минимальное значение (см. рис. 3 и 4). Это объясняется тем, что с ростом параметра r число состояний, при котором происходят переходы из L-буфера в H-буфер, уменьшается, и поэтому выбор схемы определения JP мало влияет на характеристики системы.

В конце данного раздела рассмотрим третью цель проводимых численных экспериментов, а именно рассмотрим задачи минимизации суммарных штрафов (Total Cost, TC), связанных с функционированием системы для обеих моделей; при этом для краткости изложения, а также с учетом возможности их практической реализации здесь рассматриваются лишь системы с рандомизированными скачкообразными приоритетами.

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

В стационарном режиме суммарные штрафы определяются как

где ${{c}_{{JP}}}$ – цена одного скачка из L-очереди в H-очередь; ${{c}_{{LH}}}$ (${{c}_{{LL}}}$) – штрафы за потери одного H-запроса (L-запроса); ${{c}_{{WH}}}$ (${{c}_{{WL}}}$) – цена за единицу времени пребывания в системе одного H-запроса (L-запроса).

Тогда задача оптимизации формально записывается в виде

При любых значениях входных параметров задача (4.4) имеет решение, так как множество возможных (допустимых) решений является дискретным и конечным.

В табл. 7 приводятся результаты решения задачи (4.4) для моделей обеих типов со следующими исходными данными: ${{\lambda }_{H}} = 25$, ${{\lambda }_{L}} = 35$, ${{\mu }_{H}} = 30$, ${{\mu }_{L}} = 20$, $\alpha = 0.7.$

Коэффициенты в выражении функционала (4.3) выбирались как

Результаты решения задачи (4.4) показаны в табл. 3. Их анализ позволяет сделать следующие выводы:

в модели системы с раздельными очередями при фиксированных значениях размера буфера для H-запросов рост размера буфера для L-запросов ведет к увеличению оптимального решения задачи (4.4), при этом уменьшается минимальное значение целевой функции (4.3);

в модели системы с общей очередью рост размера буфера ведет к увеличению оптимального решения задачи (4.4), при этом минимальное значение целевой функции (4.3) также уменьшается;

для обоих типов моделей оптимальное значение параметра $r{\text{*}}$ близко к его максимально возможному значению.

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

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

В данной работе для простоты изложения рассмотрено наличие лишь одного сервера каждого типа. Вместе с тем предложенный подход позволяет исследовать системы с произвольным числом серверов каждого типа. Кроме того, здесь также для простоты изложения при определении рандомизированных скачкообразных приоритетов считается, что вероятность скачка из L-буфера в H-буфер является постоянной величиной. С использованием предложенного подхода можно рассматривать случаи, когда эта вероятность зависит от разности количества разнотипных запросов, т.е. можно исследовать случаи, когда с ростом разницы количества разнотипных запросов указанная вероятность также увеличивается, например $\alpha \left( {{{n}_{L}} - {{n}_{H}}} \right) = {{\left( {{{n}_{L}} - {{n}_{H}}} \right)} \mathord{\left/ {\vphantom {{\left( {{{n}_{L}} - {{n}_{H}}} \right)} {\left( {{{n}_{L}} - {{n}_{H}} + 1} \right)}}} \right. \kern-0em} {\left( {{{n}_{L}} - {{n}_{H}} + 1} \right)}}$. Эти задачи могут быть предметами специальных исследований.