В работе построена модель параллельного обслуживания заявок в системе массового обслуживания, состоящей из k блоков обслуживания с неограниченным числом обслуживающих приборов. Найдено аналитическое выражение для производящей функций многомерного распределения вероятностей состояний цепи Маркова, характеризующей число заявок в каждом блоке (подсистеме) в нестационарном режиме. Проведены расчеты основных вероятностных характеристик.
Investigation of the parallel service system with multiple claims of the Poisson process.pdf Параллельность процессов вычислений и обработки информации является од-ним из основных принципов, используемых при проектировании современныхкомпьютерных сетей. Это позволяет достигать максимальной скорости в работе исущественной экономии времени. При оценке производительности первостепен-ное значение имеет продолжительность вычислительных процессов. Случайныйхарактер процессов формирования, обработки и передачи данных обуславливаетнеобходимость применения стохастических моделей, в качестве которых широкоиспользуются модели массового обслуживания. Использование аппарата теориимассового обслуживания позволяет построить математические модели коммута-ционных сетей и провести теоретические исследования параметров функциониро-вания реальной вычислительной системы [1, 2].Одним из основных принципов при проектировании современных компьютер-ных сетей является параллельность процессов обработки информации. Поэтомуанализ математических моделей с параллельно функционирующими блоками об-служивания и общими входящими потоками имеет практическое значение [3 - 5].1. СМО с параллельным обслуживанием k кратных заявокРассмотрим систему с k блоками обслуживания (рис. 1), каждый из которыхсодержит неограниченное число приборов. На вход системы поступает простей-ший с параметром поток k заявок, то есть в момент наступления события в рас-сматриваемом потоке в систему одновременно поступают k заявок.Дисциплина обслуживания определяется тем, что одна из этих заявок поступа-ет в первый, вторая - во второй, третья - в третий, и так далее , k-я - в k-й блокиобслуживания и занимает любой из свободных приборов, на котором выполняетсяеё обслуживание в течение случайного времени, распределенного по экспоненци-альному закону с параметрами 1, 2,…, k соответственно.Состояние системы определим вектором {i1 , i2 , … ,ik }, где ik - число заявок вk-м блоке. Тогда случайный процесс {i1(t), i2(t), … , ik(t)} изменения во временисостояний системы является k-мерной цепью Маркова.Рис. 1. СМО с параллельным обслуживанием k заявокОбозначимP(j1, j2,..., jk,t)=P{i1(t)=j1,i2(t)=j2,...,ik(t)=jk}распределение вероятностей состояний k-мерной цепи Маркова, характеризую-щей число заявок в каждом блоке (подсистеме) в момент времени t.1 . 1 . С и с т е м а д и ф ф е р е н ц и а л ь н ы х у р а в н е н и й К о л м о г о р о в аСоставим t-методом прямую систему дифференциальных уравнений Колмо-горова [4]. По формуле полной вероятности имеемP(j1,j2,...,jk,t+t)= (1−t)⋅(1−j11t)⋅(1−j22t)⋅...⋅(1−jkkt)P(j1, j2,..., jk,t)+P( j1+1, j2,..., jk,t)⋅( j1+1)⋅ 1t++P(j1,j2+1,...,jk,t)⋅( j2+1)⋅2t+......+P(j1, j2,..., jk+1,t)⋅( jk+1)⋅kt++tP(j1−1, j2−1,..., jk −1,t)+ о(t) ,откуда получаем систему дифференциальных уравнений:( 1 2 ) ( ) ( )1 1 2 2 1 2, ,..., ,k ... , ,..., ,k k kP j j j tj j j P j j j tt= − + + + + ++(j1+1)1P(j1+1,j2,...,jk,t)+(j2+1)2P(j1,j2+1,...,jk,t)+......+(jk+1)kP(j1,j2,...,jk+1,t)+P(j1−1,j2−1,...,jk−1,t). (1)Определив производящую функцию k-мерного распределения P(j1, j2,..., jk ,t)в виде( ) 1 2 ( )1 21 2 1 2 1 20 0 0, ,..., , ... ... k , ,..., ,kj j jk k kj j jF x x x t x x x P j j j t = = == ,нетрудно показать, что она удовлетворяет уравнению( 1 2 ) ( ) ( 1 2 ) ( ) ( 1 2 )1 1 2 21 2, ,..., , , ,..., , , ,..., ,F x x xkt 1 F x x xkt 1 F x x xk t ...x xt x x + − + − + ( ) ( 1 2 ) ( ) ( )1 2 1 2, ,..., ,... 1 k ... 1 , ,..., ,k k k kkF x x x tx x x x F x x x tx+ − = −. (2)1 . 2 . В и д п р о и з в о д я щ е й ф у н к ц и ип р и н е с т а ц и о н а р н о м ф у н к ц и о н и р о в а н и и С М ОПоставим задачу нахождения производящей функции при нестационарномрежиме функционирования рассматриваемой СМО, удовлетворяющей линейномудифференциальному уравнению с частными производными первого порядка (2).Для нахождения дополнительных условий воспользуемся тем фактом, чтопроизводящая функция нестационарного распределения вероятностей числа заня-тых приборов в системе M|М| определяется выражением [4]:0( , ) ( , ) exp ( 1)iiF x t x P i t x t== = ⎧⎨ − ⎫⎬⎩ ⎭ .Тогда для производящих функций одномерных маргинальных распределенийимеем1 11 2 11 1 1 2 1 10 0 0 0( ,1,...1, ) ... ( , ,..., , ) ( , )kj jkj j j jFx t x Pj j j t x Pjt = = = == = =(1) 11F j,t exp (x 1)t⎧ ⎫= = ⎨ − ⎬⎩ ⎭.2 22(1, ,...,1, ) exp ( 1)F x t x t⎧ ⎫= ⎨ − ⎬⎩ ⎭,k(1,1,..., , ) exp ( 1)F xkt xk t⎧ ⎫= ⎨ − ⎬⎩ ⎭,F(1,1,...,t)= 1 , F(x1,x2,...,0)= 1. (3)Запишем систему уравнений (2) в частных производных первого порядка (2)[4, 6]:( ) ( ) ( ) ( )1 21 1 2 2 1 2...1 1 1 1 ... 1kk k kdt dx dx dx dFx x x x x x F= = = = =− − − −.Систему обыкновенных дифференциальных уравнений перепишем в следую-щем виде:1 21 1 2 2...1 ( 1) ( 1) ( 1)kk kdt dx dx dxx x x= = = = =− − −= dF /⋅{F [(x1−1)⋅(x2−1)⋅...⋅(xk−1)+(x2 −1)⋅(x3 −1)⋅...⋅(xk−1)+......+(x1−1)⋅(x3−1)⋅...⋅(xk−1)+...+(x1−1)⋅...⋅(xk−2 −1)⋅(xk −1)++(x1−1)⋅...⋅(xk−2−1)⋅(xk−1 −1)+(x1 −1)+(x2 −1)+...+(xk −1)]} .Решая данную систему, получаем, что решение имеет вид( ) (( ) 1( ) 2 ( ) )1, 2,..., , 1 1 t, 2 1 t,..., 1 k tF x x xkt = x − e− x − e− xk− e− ( 1 ) ( 2 ) ( )1 21 1 ... 1exp...kk⎧x− ⋅x− ⋅ ⋅x− ⎨ ++ + + + + + + (1 ) 2 ( )1 21 ... ( 1) 1......k kk kx x− x− ⋅ − ⋅ ⋅ − ⋅ −+ + + + + (1 ) 2 ( 1 ) ( 1 ) ( 2 ) ( )1 2 1 1 21 ... ( 1) 1 1 1 1......k k kk k kx x− x− x x x− − ⋅ − ⋅ ⋅ − ⋅ − − − − ⎫+ + + + + ⎬ + + + ⎭, (4)где (x1, x2,…, xk,) - произвольная дифференцируемая функция.Учитывая дополнительные условия (3), имеем( ) ( ) (1 )(2 ) ( )1 2 1 21 21 1... 1, ,..., ,0 1, 1,..., 1 exp...kk kkx x xF x x x x x x⎧ − − −= − − − ⎨ +⎩ + + + ( 2 ) 3 ( ) ( 1 ) 3 ( )2 3 1 31 ( 1) ... 1 1 ( 1) ... 1...... ...k kk kx− ⋅x− ⋅ ⋅x− ⋅x− ⋅x− ⋅ ⋅x−+ + + + + + + + (1 ) 2 ( 1 ) ( 1 ) ( 2 ) ( )1 2 1 1 21 ... ( 1) 1 1 1 1... ... 1...k k kk k kx x− x− x x x− − ⋅ − ⋅ ⋅ − ⋅ − − − − ⎫+ + + + + ⎬ = + + + ⎭Откуда( ) ( 1 ) ( 2 ) ( )1 21 2 1 1... 11, 1,..., 1 exp + +...+ kkkx x xx x x⎧ ⎛ ⋅ − ⋅ − ⋅ ⋅ − − − − = ⎨−⎜ +⎩ ⎝( 2 ) 3 ( ) ( 1 ) 3 ( )2 3 1 31 ( 1) ... 1 1 ( 1) ... 1...... ...k kk k ⋅x− ⋅x− ⋅ ⋅x− ⋅x− ⋅x− ⋅ ⋅x−+ + + + + + + + (1 ) 2 ( 1 ) ( 1 ) ( 2 ) ( )1 2 1 1 21 ... ( 1) 1 1 1 1... ......k k kk k kx x− x− x x x− − ⋅ − ⋅ ⋅ − ⋅ − − − − ⎫+ + + + + ⎬ + + + ⎭.Следовательно,(( ) 1( ) 2 ( ) k)1 1 t, 2 1 t,..., 1 t x− e− x − e− xk − e− =(1 )(2 ) ( )1 2exp 1 1 ... 1 + +...+ kkx x x⎧= − − − − ⎨⎩( ) ( ) ( ) (2+3+...+ )2 32 3 1 1... 1 + ...+ k tkk− x− ⋅x− ⋅ ⋅x− e− −( ) ( ) ( ) (1+3+...+ )1 31 3 1 1... 1 + +...+k tkk− x− ⋅x− ⋅ ⋅x− e− −( ) ( ) (1+...+k-2+ )1 21 k-2 1 ...( ) 1 +...+ + k tk kkx x x e−− − − − −( ) 1 ( ) 2 ( ) 1 21 2 1 1 ... 1 t t k tkkx e− x e− x e− ⎫− − − − − − − ⎬⎭Подставляя полученное выражение в (4), получаем выражение для производя-щей функции F(x1,x2,...,xk ,t) :( )( ) ( )( (1+2+...+ ))1 2 1 21 2( , ,..., , ) exp 1 1 ... 1 1 + +...+k tk kkF x x x t ⎧ x x x e−= − − − − + ⎨⎩( ) ( ) ( )( (2+3+...+ ))2 32 3 1 1... 11 + +...+ k tkk+ x− ⋅x− ⋅ ⋅x− −e− +( ) ( )( (1+3+...+ ))1 31 3 1 ( 1) ... 1 1 ... + +...+k tkk+ x− ⋅x− ⋅ ⋅x− ⋅ −e− +( ) ( )( ( 1 ... 2 ))1 21 2... 1 ...( ) 1 1...k ktk kk kx x x e− + + − +−−+ − − − + + + + ( ) ( )( ( 1 ... 2 1))1 2 11 2 11 ...( ) 1 1...k k tk kk kx x x e− + + − + −− −− −+ − − − + + + + ( )( 1) ( )( 2) ( )( )1 21 21 1 t 1 1 t ... 1 1 k tkkx e− x e− x e− ⎫+ − − + − − + + − − ⎬ ⎭. (5)Если в (5) t →∞, то получим вид производящей функции для финального рас-пределения вероятностей рассматриваемой системы.Полученное выражение для производящей функции позволяет получить ос-новные стационарные характеристики k-мерной цепи Маркова, характеризующейчисло заявок в каждом блоке (подсистеме).Математическое ожидание числа заявок в каждом блоке (подсистеме)121 211...1( , ,..., ) kkk xk x kxF x x xMix ==== =.Дисперсия числа заявок в каждом блоке (подсистеме)k kDi = .Коэффициент корреляции . + i jiji jR = .ЗаключениеВ настоящей работе были построена математическая модель параллельногообслуживания кратных заявокв в идее СМО с k блоками обслуживания. Проведе-но исследование, а именно, получены выражение для производящей функций иосновные вероятностные характеристики k-мерной цепи Маркова, характери-зующие число заявок в каждом блоке (подсистеме).
Эльcгольц Л.Э. Дифференциальные уравнения и вариационное исчисление. М.: Наука, 1969. 424 с.
Назаров А.А., Терпугов А.Ф. Теория массового обслуживания: учеб. пособие. Томск: Изд-во НТЛ, 2004. 228 с.
Чечельницкий А.А., Кучеренко О.В. Стационарные характеристики параллельно функционирующих систем обслуживания с двумерным входным потоком // Сборник научных статей. Минск, 2009. Вып. 2. С. 262−268.
Ивановская И.А., Моисеева С.П. Математическая модель параллельного обслуживания заявок в распределенных вычислительных системах // Сборник научных статей. Минск, 2010. Вып. 3. С. 123−128.
Эндрюс Г.Р. Основы многопоточного, параллельного и распределенного программирования: пер. с англ. М.: Изд. дом «Вильямс», 2003. 512 с.
Гнеденко Б.В., Коваленко И.Н. Введение в теорию массового обслуживания. 4-е изд., испр. М.: Изд-во ЛКИ, 2007. 400 с.