Материал: Оптимизация и моделирование в автоматизированных системах

рова для описания вероятностей состояний СМО не будет трёхдиагональной. Вследствие этого система алгебраических уравнений для предельных вероятностей не может быть разрешена приёмами, приводящими к известным формулам Эрланга. Еще более затруднён анализ СМО в случае нарушения ключевой предпосылки теории СМО − условия ординарности потока входных и переработанных заявок. Тем не менее, большинство реальных СМО в той или иной степени отклоняется от классической аксиоматике: трудно обеспечить идеальное совпадение пропускных способностей. Большинство систем массового обслуживания (СМО) на практике относятся к системам, которые не могут быть описаны простым графом гибели-размножения. Наглядным примером таких систем является модель массового обслуживания с частичной взаимопомощью между каналами. Не только решение, но и составление систем дифференциальных уравнений, а также построение графа состояний для подобных систем массового обслуживания большой размерности возможно осуществить только с помощью методов компьютерного моделирования.

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

Введем следующие понятия.

Определение 1. Системой массового обслуживания с однородными каналами будем называть СМО, в которой пропускная способность всех каналов равна.

Определение 2. Системой массового обслуживания с неоднородными каналами будем называть СМО, в которой пропускная способность по крайней мере двух каналов различна.

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

Определение 4. Системой массового обслуживания с различимыми каналами будем называть СМО с неоднородными каналами и раздельными накопителями.

Рассмотрим классическую систему массового обслуживания с общей очередью длины m и k приборами равной пропускной способности μ. Далее та-

175

кие приборы будем называть однородными (рис. 1). Через λ обозначим интенсивность входящего потока заявок.

Рис. 1. 2-канальная система массового обслуживания с общей ограниченной очередью длины 3 с однородными каналами.

Эта система массового обслуживания может быть представлена орграфом процесса гибели и размножения (рис. 2).

Рис. 2. Граф СМО с общей очередью длины m и k однородными каналами

Здесь состояние системы массового обслуживания обозначено через век-

кую систему массового обслуживания можно задать сигнатурой T=T(μ;k;m), k>0.

Определение 5.

Выражение T=T(μ1,μ2,…,μk;m1,m2,…,mk), описывающее СМО, где μi –

пропускная способность и mi – ёмкость очереди i-го канала, i 1, k ; k>0, будем

называть сигнатурой данной системы массового обслуживания. Приведем пример.

Пример 1. СМО сигнатуры T(μ;2;2) имеет множество различимых со-

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

В том случае, когда каналы неоднородные при общей очереди, то сигнатура примет вид T=T(μ1,μ2,…,μk;m). Этот случай нельзя представить графом процесса гибели и размножения, поэтому необходимо ввести понятие диспетчеризации, или оптимальной политики.

Обратимся к графу, изображенному на рис. 2. Веса его дуг означают вероятности перехода системы из состояния Si в состояние Sj. Так как приборы

176

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

Определение 6. Диспетчеризацией входящих заявок СМО с k неоднородными каналами и/или раздельными очередями будем называть правила, по которым поступившая заявка, заставшая систему в состоянии (x1,x2,…,xk;y1,y2,…,yk),

направляется на обслуживание к i-му каналу, i 1,k , выбор которого определя-

ется только состоянием СМО в момент поступления заявки.

Пусть очередная входная заявка обнаруживает систему в состоянии (x1,x2,…,xk;y1,y2,…,yk), не являющемся состоянием отказа (1,1,…,1;m1,m2,…,mk). Если существует единственный канал (с номером i), способный принять заявку

(0 ≤ yi ≤ xi mi −1 ), то заявка направляется к нему. В противном случае оптималь-

ным считаем выбор i-го канала обслуживания, способного обработать заявку с минимальным средним суммарным временем T обслуживания попавших в него заявок:

где χi – случайная величина, характеризующая незавершённость обработки заявки, находящейся в i-м канале в момент поступления новой заявки, 0≤χi≤1. Для простоты будем здесь и далее считать, что χi=1.

Пример 4. Рассмотрим СМО с 2 неоднородными каналами пропускной способности µ1>µ2 без очереди (сигнатура T=T(μ1,μ2;0,0)). При диспетчеризации

(1) граф такой СМО будет следующим (рис. 3).

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

Рис. 3. Граф СМО T=T(μ1,μ2;0,0)при диспетчеризации (1)

Если каналы однородные при раздельных очередях к ним (рис. 3), их сигнатура примет вид T=T(μ;m1,m2,…,mk).

177

Рис. 4. 2-канальная СМО с раздельными очередями ограниченной длины

очередей.

Пример 2. СМО сигнатуры T(μ;1,1) имеет множество различимых состоя-

шая заявка не может находиться в очереди канала 2, если он свободен. Однако,

заявки через канал 1 или канал 2.

Единственный возможный метод оптимизации СМО ˗ распределение емкостей накопителей между каналами различной производительности, а также их упорядочение, т.е. по параметрам не меняющимся в процессе функционирования СМО

В практически распространенных случаях СМО с неоднородными каналами и раздельными очередями подобные аналитические методы моделирования неприменимы.

Это связано с тем, что они распространяются только на системы с простейшими потоками событий. Уравнения Колмогорова для марковских процес-

Это значит, что интервалы времени между событиями потока распределены по

закону Пуассона: p(k) = λk e−λ . k!

178

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

Уравнения Колмогорова эффективно решаются только в случае однородных марковских цепей, иначе говоря, при λij = λij(t) уравнения Колмогорова могут не иметь аналитического решения. Также практически важное стационарное решение гарантированно существует лишь для однородных марковских цепей.

Наконец, немаловажной оказывается сложность составления уравнений Колмогорова для системы массового обслуживания с различимыми каналами для задач большой размерности. Например, если для многоканальной системы обслуживания с общим накопителем число состояний системы составляет m + n + 1, где n – количество каналов, m – емкость общего накопителя, то для СМО с n различимыми каналами и емкостью накопителей m1 = m2 = … = mi = … mn =

n−1

m число допустимых состояний составит (m +1)∑mi .

i=0

В частном случае простейших потоков СМО с различимыми каналами и протокола диспетчеризации данную модель массового обслуживания можно описать уравнениями Колмогорова.

Рассмотрим СМО с различимыми каналами сигнатуры T(0,15;0,05;0,03;0,0,0), с нотификацией состояний вида Sj=S(x1,x2,x3;0,0,0),

xi = 0,1. На рис. 5 представлен граф состояний такой системы.

Рис. 5. Граф состояний СМО сигнатуры T(0,15;0,05;0,03;0,0,0) с диспетчеризацией

179