Модели сетей массового обслуживания

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

В качестве примера можно рассмотреть организацию вычисли­тельного процесса на современной ЭВМ. Отдельные блоки ЭВМ пред­ставляются системами массового обслуживания. Блок-схема соответ­ствующей сети представлена на рис.3.3. Работа мультиплексного канала с различными устройствами ввода-вывода моделируется СМО С₃ с очередью 0₃, селекторный канал с внешними накопителями отобра­жается СМО С₂, а процессор с ОЗУ - СМО C₁ с очередями 0₂ и 0₁ соответственно. В зависимости от оснащения ЭВМ указанные СМО могут быть одно- и многоканальными [6]. Источник заявок интенсивностью l₀ воздействует на вход сети, причем заявки начинают обслуживать­ся СМО C₁. Физически эти заявки содержатся в ОЗУ ЭВМ после ввода соответствующего пакета задач.

 

 

 

 

Рис.3.3

 

Заявки, выходящие из одних СМО, поступают на обслуживание в другие СМО в соответствии с конфигурацией или топологией сети. Направление перехода заявок из одной СМО (C_i) в другую (C_j) оп­ределяется вероятностями p_ij. Поэтому сети СМО удобно предс­тавлять взвешенными орграфами, вершины которых являются отдельными СМО C_i, а дуги указывают направление перехода заявок. Ве­са дуг равны вероятностям пере­хода p_ij. Сети, изображенной на рис. 3.3, соответствует граф, представленный на рис. 3.4. Ис­точник входных заявок представ­ляется отдельной фиктивной СМО С₀. Взвешенному орграфу сети соответствует матрица переходных вероятностей размерностью (N+l)´(N+l)

                 

 

где N - количество СМО в сети. Поскольку заявки в сети не теряют­ся, то вышедшие из СМО C_j заявки будут равны сумме заявок, кото­рые поступают на входы других СМО, связанных с выходом C_j, и поэ­тому

                          (3.13)

Как известно, матрицы, у которых в каждой строке выполняется условие (3.13), называются стохастическими. Поэтому сети массового обслуживания являются стохастическими сетями. Заявки входят в сеть с вероятностями p_oj, а покидают ее с вероятностями р_j0 (j=1,…,N). При этом полагается р₀₀ = 0, так как случай р₀₀ ¹0 не представляет практического интереса (заявки не поступают в сеть, а возвращаются в источник). Поскольку потоки заявок посту­пают в каждую j-ю СМО в виде линейной комбинации выходящих пото­ков из i-х СМО с весами p_ij, то такие стохастические сети назо­вем линейными.

Будем считать, что элементами сети являются одно- или много­канальные СМО с неограниченными очередями, причем для каждой СМО выполняются условия стабилизации очереди (r_i<1 и æ_j<1). Кроме того, будем полагать, что входной поток сети является пуассоновским, а времена обслуживания в каждой СМО подчиняются экспоненци­альному распределению. Тогда, в соответствии с изложенным в 3.2, выходной поток сети является пуассоновским с интенсивностью, рав­ной интенсивности входного потока. Такие сети называются линейны­ми экспоненциальными стохастическими сетями. Они и будут являться предметом для дальнейшего рассмотрения. Отметим одну важную осо­бенность экспоненциальных стохастических сетей. Чем больше СМО входит в сеть и чем сложней ее структура, тем точнее результаты, основанные на заменах реальных потоков простейшими. Этот факт яв­ляется следствием предельной теоремы для суммарных потоков.

Так же как и в обычных СМО, различают разомкнутые и замкну­тые сети. В разомкнутых сетях интенсивность потока заявок не за­висит от состояния сети. Если общее число заявок, циркулирующее в сети, ограничено, т.е. при поступлении заявки в сеть интенсив­ность потока входных заявок уменьшается, то такая сеть называется замкнутой. Источник заявок в разомкнутой СМО представляется как некая фиктивная СМО С₀ (см.рис.3.4) с бесконечным числом заявок и интенсивностью обслуживания их, равной l₀. В замкнутой CMО так­же содержится фиктивный источник заявок С₀, который представляют как СМО с интенсивностью входных заявок l₀ и нулевым временем обслуживания. При этом матрицы передач как замкнутой, так и ра­зомкнутой сетей имеют одну и ту же размерность (N+l)´(N+1).

 

 

Рим.3.4

 

Пусть l_i - входной поток C_i. Заявки из С_j поступают в C_i с вероятностью р_ji, поэтому

                                                  (3.14)

 

В матричном виде (3.14) записывается как l = р^тl. Если ввести в рассмотрение так называемую динамическую матрицу D = Р - Е,

где Е - единичная матрица, то (3.14) перепишется в виде

(р₀₀-1)l₀ + p₁₀l₁ +…+ р_N0l_N =0

p₀₁l₀ + (p₁₁-1)l₁ +…+ р_N1l_N =0                               (3.15)

…

p_0Nl₀ + p_1Nl₁ +…+ (P_NN-1)l_N = 0 

Система (3.15) имеет нетривиальное решение, если D – вырожденная матрица. Это действительно так, поскольку вследствие (3.13) мат­рица Р вырождена, поэтому вырождена и D. Ранг матриц Р и D равен N, если каждое состояние сети может быть достигнуто из любого другого за конечное число переходов. Такая сеть является неразло­жимой, а множество ее вершин образует эргодическое множество. В дальнейшем будем рассматривать неразложимые сети, в которых ранг матриц Р и D равен N. Тогда из системы (3.15) определяются не интенсивности, а соотношения интенсивностей

l_i=a_il₀                              (3.16)

Коэффициенты a_i (i=1,…,N) называются коэффициентами передачи. Они имеют следующий смысл. Одна и та же заявка, поступающая из С₀, может пройти через C_iнесколько раз. Коэффициент a_i показыва­ет среднее число прохождений через систему C_i одной заявки, по­ступившей от С₀.

Для разомкнутых сетей интенсивность l₀ известна, поэтому ре­шение (3.16) единственно. Рассмотрим вначале условия существова­ния установившегося режима в разомкнутой системе. Очевидно, что для этого необходимо соблюдение условий стабилизации очереди в каждой СМО:

l_i = a_il₀ < m_i, r_I = a_i/m_i < l

для одноканальных СМО и

l_i = a_il₀ < n_im_i

для многоканальных СМО.

Следовательно: стационарный режим в разомкнутой сети будет иметь место при

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

                                (3.17)

 

 где k_i и n_i - число заявок и число каналов в i-й системе соот­ветственно; r_i=l_i/m_i; æ_i=r_i/n_i. Тогда вероятности состояний СМО с очередями запишутся в виде

                p_i(k_i)=B_i(k_i)p_0i                           (3.18)

Для случая n_i=1 (одноканальные СМО) выражения для плотностей вероятностей (2.34) и (3.17) принимают вид

p_0i=l-r_i; B_i(k_i)=r_i^k1 и p_i(k_i)=r_i ^k1(1-r_i)                        (3.19)

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

с условием нормировки

                                      (3.20)

 

Среднее число заявок в сети и среднее число заявок в очередях всех СМО в сети равны соответственно

                 

где k_i и r_i определяются выражениями (2.35) и (2.36). Поскольку коэффициенты передачи a_i определяют среднее число прохождений за­явки через i-ю СМО, то среднее время нахождения заявки в сети и среднее время ожидания заявки в очередях СМО данной сети равны соответственно

где  - среднее, время пребывания заявки в i-й СМО.  - среднее время ожидания заявки в i-й СМО.

Перейдем к замкнутым сетям. Коэффициенты передач a_i рассчи­тываются так же, как и для разомкнутых сетей, полагая l₀=1. Одна­ко истинные значения l_i по-прежнему остаются неизвестными, по­скольку неизвестно l₀. Эти параметры определяются с помощью ве­роятностей состояний. Так как в отличие от предыдущего случая число заявок в замкнутой сети k - постоянная и конечная величина, то и число ее состояний также конечно. Обозначим через S(k,N) множество всех состояний замкнутой сети, в которой k заявок про­извольным образом распределяются между N СМО. Мощность этого мно­жества |S(k,N)| равна числу сочетаний с повторениями из N эле­ментов по k. Как известно, это число

При любых размещениях k заявок по N СМО необходимо выполнение ра­венства

                                                      (3.21)

В связи с этим вероятность некоторого состояния, определяемого некоторым конкретным размещением заявок по N СМО сети:

                                  (3.22)

 

где числитель вычисляется так же, как и для разомкнутых сетей, а в знаменателе стоит нормирующий множитель. Этот множитель появля­ется из-за того, что рассматриваются только те состояния, для ко­торых справедливо (3.21). Сумма в (3.22) берется по всем  элементам конечного множества в отличие от разомкнутых сетей, где суммирование в условии нормировки (3.20) ведется от 0 до ¥. При суммировании всех вероятностей p(k₁,…,k_N) по состояниям S₁Î(k,N) необходимо вводить нормирующий множитель, так как эта сумма по конечному множеству состояний будет меньше единицы (см.(3.20)). Подставим в (3.19) формулы для p_i(k_i) из (3.18), учиты­вая при этом, что выражения р_0i не зависят от k_i ни в (2.34), ни в (3.19). Тогда соответствующие сомножители в числителе и знаме­нателе формулы (3.22) сокращаются и соотношения для вероятностей состояний принимают вид

                                  (3.23)

В частном случае, для сети из одноканальных систем имеем

                             (3.24)

 

Выражения (3.23) и (3.24) зависят не от r_i(l_i), а от соотношения a_i=l_i/l₀. Действительно, заменив в (3.17) или в (3.19) l_i на a_il₀, получим

                B_i(k_i,l_i)=l₀^k1b_i(k_i,a_i)                     (3.25)

Подставив (3.25) в (3.23) с учетом (3.21), получим, что вероят­ности p(k₁,…,k_N) не зависят от l₀, поэтому их можно рассчи­тывать на основании определенных ранее величин a_i.

Вероятность того, что в системе i будет находиться R заявок:

                                    (3.26)

Суммирование в (3.26) ведется лишь по тем состояниям, для которых число заявок k_i в i-й СМО равно R при произвольном размещении за­явок по остальным СМО любыми возможными сочетаниями. Вероятность того, что i-я СМО не загружена:

Теперь можно определить интенсивности входных потоков, воздейст­вующих на отдельные СМО. Для одноканальных СМО из (3.19) следует

Для многоканальных СМО r_i равно среднему числу занятых каналов  (см.(2.36)). Поэтому

От вычисленных величин r_i легко перейти к l_i, а затем применить для расчета отдельных СМО известные формулы. По этим формулам можно, в частности, рассчитать среднее число заявок r_i в очереди i-й СМО. Затем можно проверить правильность вычислений выполнением условия

Расчет остальных характеристик сети производится аналогично пре­дыдущему случаю.

 

 

Список литературы

1. Вентцель Е.С. Исследование операций. -М.: Сов.радио, 1972.

2. Ивченко Г.И., Каштанов В.А., Коваленко И.Н. Теория массового обслуживания. -М.: Высш. шк., 1982.

3. Овчаров Л.А. Прикладные задачи теории массового обслуживания. -М.: Машиностроение, 1969.

4. Хинчин А.Я. Работы по математической теории массового обслужи­вания. - М.: Физматгиз, 1963.

5. Кофман А., Крюон Р. Массовое обслуживание. Теория и приложе­ния. - М.: Мир, 1965.

6. Основы теории вычислительных систем/ Под ред. С.А.Майорова. -М.: Высш. шк., 1978.

7. Тараканов К.В., Овчаров Л.А., Тырышкин А.Н. Аналитические ме­тоды исследования систем. - М.: Сов.радио, 1974.

8. Клейнрок Л. Вычислительные системы с очередями. - М.: Мир, 1979.                                                   

9. Романцев В.В., Яковлев С.А. Моделирование систем массового обслуживания: Учеб. пособие/СПбГЭТУ. -СПб.,1995.

 

ОГЛАВЛЕНИЕ

1. МАТЕМАТИЧЕСКИЕ ОСНОВЫ ТЕОРИИ МАССОВОГО ОБСЛУЖИВАНИЯ.. 

1.1. Предмет теории массового обслуживания.    

1.2. Основы марковских процессов. Уравнения Колмогорова..    

1.3. Предельные вероятности состояний..   

1.4. Простейший поток событий    

1.5. Потоки Пальма и Эрланга   

2. МОДЕЛИ СИСТЕМ МАССОВОГО ОБСЛУЖИВАНИЯ ПРИ ПУАССОНОВСКИХ ПОТОКАХ ЗАЯВОК 

2.1. Модели систем массового обслуживания с отказами   

2.2. Модели систем с очередями

2.3. Модель замкнутой системы

2.4. Модели систем с различными дисциплинами подключения каналов к обслуживанию

3. МОДЕЛИ НЕПУАССОНОВСКИХ СИСТЕМ МАССОВОГО ОБСЛУЖИВАНИЯ

И СТОХАСТИЧЕСКИХ СЕТЕЙ

3.1. Модели систем с непуассоновскими потоками заявок

3.2. Модели многофазных систем

3.3. Модели сетей массового обслуживания

Список литературы

 

Романцев Вениамин Викторович

Аналитические модели систем массового обслуживания

Учебное пособие

197376, С.-Петербург, ул. Проф. Попова, 5