Исследование системы параллельного обслуживания кратных заявок простейшего потока | Вестник Томского государственного университета. Управление, вычислительная техника и информатика. 2011. № 4(17).

Исследование системы параллельного обслуживания кратных заявок простейшего потока

В работе построена модель параллельного обслуживания заявок в системе массового обслуживания, состоящей из 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−j1ƒ1ƒt)⋅(1−j2ƒ2ƒt)⋅...⋅(1−jkƒkƒt)P(j1, j2,..., jk,t)+P( j1+1, j2,..., jk,t)⋅( j1+1)⋅ ƒ1ƒt++P(j1,j2+1,...,jk,t)⋅( j2+1)⋅ƒ2ƒt+......+P(j1, j2,..., jk+1,t)⋅( jk+1)⋅ƒkƒt++ƒƒ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 kƒx− ⋅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 tkkƒx 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-мерной цепи Маркова, характери-зующие число заявок в каждом блоке (подсистеме).

Ключевые слова

parallel service, Poisson current of multiple claims, unlimited number of service devices, non-Markov chains, система массового обслуживания, пуассоновский поток кратных заявок. параллельное обслуживание, немарковские системы с неограниченным числом обслуживающих приборов

Авторы

ФИООрганизацияДополнительноE-mail
Жидкова Любовь АлександровнаНациональный исследовательский Томский государственный университетмагистрантка кафедры теории вероятности и математической статистики факультета прикладной математики и кибернетикиzhidkovala@mail.ru
Моисеева Светлана ПетровнаНациональный исследовательский Томский государственный университетдоцент, кандидат технических наук, доцент кафедры теории вероятности и математической статистики факультета прикладной математики и кибернетикиsmoiseeva@mail.ru
Всего: 2

Ссылки

Эльcгольц Л.Э. Дифференциальные уравнения и вариационное исчисление. М.: Наука, 1969. 424 с.
Назаров А.А., Терпугов А.Ф. Теория массового обслуживания: учеб. пособие. Томск: Изд-во НТЛ, 2004. 228 с.
Чечельницкий А.А., Кучеренко О.В. Стационарные характеристики параллельно функционирующих систем обслуживания с двумерным входным потоком // Сборник научных статей. Минск, 2009. Вып. 2. С. 262−268.
Ивановская И.А., Моисеева С.П. Математическая модель параллельного обслуживания заявок в распределенных вычислительных системах // Сборник научных статей. Минск, 2010. Вып. 3. С. 123−128.
Эндрюс Г.Р. Основы многопоточного, параллельного и распределенного программирования: пер. с англ. М.: Изд. дом «Вильямс», 2003. 512 с.
Гнеденко Б.В., Коваленко И.Н. Введение в теорию массового обслуживания. 4-е изд., испр. М.: Изд-во ЛКИ, 2007. 400 с.
 Исследование системы параллельного обслуживания кратных заявок простейшего потока | Вестник Томского государственного университета. Управление, вычислительная техника и информатика. 2011. № 4(17).

Исследование системы параллельного обслуживания кратных заявок простейшего потока | Вестник Томского государственного университета. Управление, вычислительная техника и информатика. 2011. № 4(17).

Полнотекстовая версия