Analysis of the parallel service model of multiple service requests operating in unsteady mode..pdf Параллельность процессов вычислений и обработки информации является од-ним из основных принципов, используемых при проектировании современных компьютерных сетей. Это позволяет достигать максимальной скорости в работе и существенной экономии времени. При оценке производительности первостепен-ное значение имеет продолжительность вычислительных процессов. Случайный характер процессов формирования, обработки и передачи данных обуславливает необходимость применения стохастических моделей, в качестве которых широко используются модели массового обслуживания. Использование аппарата теории массового обслуживания позволяет построить математические модели коммута-ционных сетей и провести теоретические исследования параметров функциониро-вания реальной вычислительной системы[1, с. 9 - 13; 2, с. 19 - 21].Одним из основных принципов при проектировании современных компьютер-ных сетей является параллельность процессов обработки информации. Поэтому анализ математических моделей с параллельно функционирующими блоками об-служивания и общими входящими потоками имеет практическое значение [3 - 5].1. СМО с параллельным обслуживанием сдвоенных заявокРассмотрим систему с двумя блоками обслуживания (рис. 1), каждый из кото-рых содержит неограниченное число приборов. На вход системы поступает про-стейший с параметром λ поток сдвоенных заявок, то есть в момент наступления со-бытия в рассматриваемом потоке в систему одновременно поступают две заявки.Дисциплина обслуживания определяется тем, что одна из этих заявок поступа-ет в первый, а другая - во второй блоки обслуживания и занимает любой из сво-бодных приборов, на котором выполняется ее обслуживание в течение случайно-го времени, распределенного по экспоненциальному закону с параметрами µ1 и µ2 соответственно.Состояние системы определим вектором {i1,i2}, где ik - число заявок в k-м бло-ке. Тогда случайный процесс {i1(t),i2(t)} изменения во времени состояний системы является двумерной эргодической цепью Маркова [1].1 Работа выполнена в рамках аналитической ведомственной целевой программы «Развитие научного потенциала высшей школы (2009-2010 годы)», проект № 476122И.А. Ивановская, С.П. МоисееваОбозначим P(i, j, t) = P{i1(t) = i, i2(t) = j} - распределение вероятностей со-стояний двумерной цепи Маркова, характеризующей число заявок в каждом бло-ке (подсистеме) в момент времени t.п1Ц1XИ2и2Рис. 1. СМО с параллельным обслуживанием сдвоенных заявок1.1. Система дифференциальных уравнений КолмогороваСоставим Δ t-методом прямую систему дифференциальных уравнений Колмогорова [4]. По формуле полной вероятности запишем равенстваP(i, j,t + ^) = (1-XAt)(1-i^At)(1-j^2At)P(i, j,t) + XAtP(i-1, j-1,t) ++(i +1)1^ AtP(i +1, j, t) + (j + 1)]i2AtP(i, j +1,t ) + o(At). Откуда получаем систему дифференциальных уравнений: dP(i,j,t)-(X + ih + jц2 )P(i, j, t) + P ( i -1, j -1,t ) +dt+(i + 1)m.1P(i +1, j, t) + (j + 1)]i2P(i, j +1,t ).(1)Определим производящую функцию двумерного распределения P(i , j, t) в виде [3]СО СОi=0 j=0Из системы дифференциальных уравнений Колмогорова (1) имеемdF(x,y,t)dtао ао-XFf(x,y, t ) - h Z ZixiyjP(i, j,t ) - i-2 Z Z jyjxiP (i, j, t )+i=0 j=1i=1 j=0+^ZZxi yjP(i-1 ,j-1 , t )+hZZ(i+1)xiyP(i+1,j,t )+^2ZZ( j+1)xiyP(i,j+1, t),i=1 j=1i=0 j=0i=0 j=0откуда получаем линейное дифференциальное уравнение в частных производных первого порядка для функций F(x,y,t):Исследование модели параллельного обслуживания кратных заявок 23dF(x,y,t) = F(x,y,t) F(x,y,t) -XF(x,y,t) - \i1x \\.2y +ot ox ay F(x,y,t) F(x,y,t)+kxyF(x,y,t) + yi1 -\x2 ,dx dyотсюдаF ( x , y , t ) + ^x-1)дF ( x , y , t ) + ^y-1)дF ( x , y , t ) = Чxy-1) F (x,y , t ). (2) dt ox dy1.2. Вид производящей функции при нестационарном функционировании СМОПоставим задачу нахождения производящей функции при нестационарном функционировании рассматриваемой СМО.F(x,y,t) удовлетворяет линейному дифференциальному уравнению с частными производными первого порядка.Для нахождения начальных условий воспользуемся тем фактом, что производящая функция нестационарного распределения вероятностей числа занятых приборов в системе M ׀ M ׀∞ определяется выражением [4, с. 70 - 72]:F(x,t) = i,x i P(i,t) = exp I -(x-1)t=0 IM-Тогда для производящих функций одномерных маргинальных распределений имеемСО СО СО Г Л ~]F(x, 1,t) = YZ xiP( i, j, t) =Z xiP ( i,t ) = exp - (x -1)ti=0 j=0 j=0 I 1 JCO CO CO Г ЛF(1,y,t) = ^^yj P(i, j.t) =^yj P(j,t) = expl-( y-1) ti=0 j=0 j=0 IM-2F(1,1, t) = 1,) (3)Запишем систему уравнений (2) в частных производных первого порядка [4, с. 71; 6, с. 241]:dt = dx = dy = dF1 щ(x-1) V-2(y-1) X(xy-1)F .Систему обыкновенных дифференциальных уравнений перепишем в следующем виде:dt = dx = dy = dF1 M-1(x-1) ]i2(y-1) X[(x-1)(y-1) + (x-1) + (y-1)]F Найдем два первых интеграла этой системы. Один из них найдем из уравненияdxdt =----------.щ(x-1)Исследование модели параллельного обслуживания кратных заявок 23dF(x,y,t) = F(x,y,t) F(x,y,t) -XF(x,y,t) - \i1x \\.2y +ot ox ay F(x,y,t) F(x,y,t)+kxyF(x,y,t) + yi1 -\x2 ,dx dyотсюдаF ( x , y , t ) + ^x-1)дF ( x , y , t ) + ^y-1)дF ( x , y , t ) = Чxy-1) F (x,y , t ). (2) dt ox dy1.2. Вид производящей функции при нестационарном функционировании СМОПоставим задачу нахождения производящей функции при нестационарном функционировании рассматриваемой СМО.F(x,y,t) удовлетворяет линейному дифференциальному уравнению с частными производными первого порядка.Для нахождения начальных условий воспользуемся тем фактом, что производящая функция нестационарного распределения вероятностей числа занятых приборов в системе M ׀ M ׀∞ определяется выражением [4, с. 70 - 72]:F(x,t) = i,x i P(i,t) = exp I -(x-1)t=0 IM-Тогда для производящих функций одномерных маргинальных распределений имеемСО СО СО Г Л ~]F(x, 1,t) = YZ xiP( i, j, t) =Z xiP ( i,t ) = exp - (x -1)ti=0 j=0 j=0 I 1 JCO CO CO Г ЛF(1,y,t) = ^^yj P(i, j.t) =^yj P(j,t) = expl-( y-1) ti=0 j=0 j=0 IM-2F(1,1, t) = 1,) (3)Запишем систему уравнений (2) в частных производных первого порядка [4, с. 71; 6, с. 241]:dt = dx = dy = dF1 щ(x-1) V-2(y-1) X(xy-1)F .Систему обыкновенных дифференциальных уравнений перепишем в следующем виде:dt = dx = dy = dF1 M-1(x-1) ]i2(y-1) X[(x-1)(y-1) + (x-1) + (y-1)]F Найдем два первых интеграла этой системы. Один из них найдем из уравненияdxdt =----------.щ(x-1)24И.А. Ивановская, С.П. МоисееваОчевидно, имеемМ = ln(x-1)-ln C 1, откуда получаем выраженияx-1 = C1e>i1t,C 1 =(x-1)e^t1.(4)Другой первый интеграл найдем из уравненияdydt =V2( y-1)ИмеемV2t = ln(y-1)-lnC2,откуда получаем выраженияy-1 = C2e^ ,C2 = (y-1)e^2t.(5)Последний интеграл найдем из уравненияdF= dtXF[(x-1)(y-1) + (x-1) + (y-1)]1,dFdtXF(C1e^ -C2e^ +C1e^ +C2e^) 1dF = X( C1 e 1 t.C2e^+C1 e 1 t+C2e^) dt, FlnF-lnC3 =C1C 2e(^1+2) t + - C1 e1t + - C2e^,M-1 +1^2M1M2F = C3 -expj^^C 1C2 e (1^ + - C 1 e*1 t + - C2e^A.(6)LM-1 +И-2M1M2JПодставляя выражения (4), (5) для C1 и C2 , общее решение уравнения (6) можно записать следующим образом:F(x,y , t)=ф((x-1)e-^,(y-1)e-^2t)exp\ -+-(x-1)+-(y-1)к (7){ M-1+M-2M1М2Jгде Ф(x,y) - произвольная дифференцируемая функция.Для того чтобы найти Ф(x,y), воспользуемся начальными условиями (3):F(x,y ,0) = Ф(x-1, y-1)-exp{Х(x-1)(y-1) +-(x-1)+ - (y-1) = 1,{M-1 +M-2M1М2Ф(x-1,y-1) = exp - (1)( y1) + - (x-1) + - (y-1)[ КM1+M2ИМ2Исследование модели параллельного обслуживания кратных заявок25Следовательно,ф((x-1)e-^1 t ,(y-1)e-^)=exp\-Х( x-1)(y-1) e^+^) t--(x-1)e-^--(y-1)e{Щ+Ц2М-1М2Подставляя полученное выражение в (7), запишем вид производящей функцииF(xy,t):F(x,y,t)=exp\^( x-1)( y-1) 1- e^^)^x-1) 1-e-^+ ( y-1) 1-e-^. (8)LM-1+M-2hМ2)Из (8) можно получить основные вероятностные характеристики двумерной цепи Маркова, характеризующей число заявок в каждом блоке (подсистеме) в момент времени.Для этого возьмем производные соответствующих порядков.Учитывая, чтоF ( x , y , t ) = (^^(y-1)(1-e^+^) + (1-e^))F(x,y,t),dx^h+M2hJдyУр-1+Р-2V-2)d2F(x,y,t) ( X-(и+и)t X2,^(y -1) ( 1-e^)t ) + -( 1-e - 1 t ) F(x,y,t),dx'vM-1 +M-2M-1d2F(xy,t) =r^(x-1)(1-e -(1+2) )+A(1-e -^) 2 F (x,y,t),dy2^M-1+M-2M-2^_ (1 - e -(H1+H2 )t ) + (J_ (y - 1) (1 - e -(^1+2 ) t ) + A (1 - e -^ )M-1 + M-2lh+M2hдxдyx f^ (x -1) ( 1 - e-( 1+ 2)t ) + - ( 1 - e - 2 t )Ik + M-2M2получаем1)математическое ожидание числа заявок:а)в первом блоке системы:M-1б)во втором блоке системы:Mi2 =-( 1-e^2t ) ;М-22)дисперсия числа заявок:а) в первом блоке системы:Mi 12 -Mi 1 = -( 1-e-^)26И.А. Ивановская, С.П. Моисееваб) во втором блоке системы:M22-M2= ⎜-( 1-e-μ 2 t )3) корреляционный момент двумерной случайной величины {i1,i2}Если в (8) t ->■ да, то получим вид производящей функции для стационарного распределения вероятностейF(x,y) = exp⎨(x-1)(y-1) + - (x-1) + - (y-1)⎩μ 1 +μ2μ 1μ 22. СМО с параллельным обслуживанием кратных заявок (при к = 3)Рассмотрим систему с тремя блоками обслуживания (рис.2), каждый из которых содержит неограниченное число приборов. На вход системы поступает простейший с параметром поток строенных заявок, то есть в момент наступления события в рассматриваемом потоке в систему одновременно поступают три заявки.μiμ:μ 1μ1. . .λμ2μ2. . .μ 3μ 3. . .Рис. 2. СМО с параллельным обслуживанием строенных заявокДисциплина обслуживания определяется тем, что одна из этих заявок поступает в первый, вторая - во второй, а третья - в третий блоки обслуживания и занимает любой из свободных приборов, на котором выполняется ее обслуживание в течение случайного времени, распределенного по экспоненциальному закону с параметрами µ1, µ2 и µ3 соответственно.Состояние системы определим вектором {i 1,i2,i 3}, где ik - число заявок в k-м блоке. Тогда случайный процесс {i1(t),i2(t),i3(t)}, изменения во времени состояний системы является трехмерной эргодической цепью Маркова [1. С. 29 - 31].ОбозначимP(i,j,k,t) = P{i 1 (t) = i,i2 (t ) = j , i 3 (t ) = k}- распределение вероятностей состояний трехмерной цепи Маркова, характеризующей число заявок в каждом блоке (подсистеме) в момент времени t.Ставится задача нахождения производящей функции при нестационарном функционировании рассматриваемой СМО.Исследование модели параллельного обслуживания кратных заявок27Система дифференциальных уравнений Колмогорова будет иметь видdP(i j k t)w, , =-(X + iii1+jii2+kii3)P(i,j,k,t) + (i + 1)ii1P(i + 1,j,k,t) ++ (j + 1)lL2P(i,j + 1,k,t) + (k + 1)iL3P(i,j,k + 1,t) + XP(i-1,j-1,k-1,t). (9)Определим производящую функцию трехмерного распределения P(i, j, k, t) в видеСО СОСОF(x,y,z,t) = XXXxiyj zkP(i, j,k,t ) .i=0 j=0 k=0Из системы дифференциальных уравнений Колмогорова (9) для распределений P(ij, k,t) нетрудно получить дифференциальное уравнение в частных производных первого порядка для функций F(xy,z,t) следующего вида:dF(x,y,z,t) (dF(x,y,z,t)dF(x,y,z,t)dF(x,y,z,t)atoxayoz= X(xyz-1)F(x,y,z,t).Затем, проведя аналогичные выкладки так же, как в разделе 1, получим следующие результаты.Выражение для производящей функции F(xy,z,t) запишем в видеF(x,y,z,t) = exp(x-1)(y-1)(z-1) ( 1-e-^+^3)t ) ++^^(x-1)(y-1) ( 1-e-( 1+^) + ^-(y-1)(z-1) ( 1-e-^^) +M1+M2М2+М3+ ^^(x-1)(z-1) ( 1-e-^+^t ) + - (x-1) ( 1-e-^) +M1 +М-3M1^^1+-(y-1) ( 1-e-2t ) +- (z-1) ( 1-e-^H.(10)М2М3))Из полученной производящей функции (10) получим основные вероятностные характеристики трехмерной цепи Маркова, характеризующей число заявок в каждом блоке (подсистеме) в момент времени.1) математическое ожидание числа заявок:а)в первом блоке системы:M1б)во втором блоке системы:Mi2 =-( 1-e-2t ) , М2в)в третьем блоке системы:Mi 3 =-( 1-e-3t ) ; М328И.А. Ивановская, С.П. Моисеева2) дисперсия числа заявок:а) в первом блоке системы:Mi2 -Mi 1 = -( 1-e M)б)во втором блоке системы:Mi22-Mi2=\- ( 1-e-M)Mi22 -Mi 2в)в третьем блоке системы:Mi32-Mi3=(-( 1-e-^)Если рассматривать стационарный режим, то получим следующий вид производящей функции F(xy,z):F(x,y,z) = exp\(x-1)(y-1)(z-1) + ^^(x-1)(y-1)L M-1 + М-2 + М-3М-1 +М-2+^^(y-1)(z-1) + ^^(x-1)(z-1)+-(x-1) + - (y-1) + -(z-1)\.И2+ШM-1+Ц-3М-1М2М3JЗаключениеТаким образом, в работе рассмотрены системы массового обслуживания с параллельным обслуживанием кратных заявок с двумя и тремя блоками обслуживания. Получены выражения для производящих функций и числовые характеристики цепи Маркова при нестационарном функционировании рассматриваемых СМО.

Скачать электронную версию публикации