close

Вход

Забыли?

вход по аккаунту

?

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

код для вставкиСкачать
ВЕСТНИК ТОМСКОГО ГОСУДАРСТВЕННОГО УНИВЕРСИТЕТА
2011
Управление, вычислительная техника и информатика
№ 4(17)
УДК 519.872
Л. А. Жидкова, С.П. Моисеева
ИССЛЕДОВАНИЕ СИСТЕМЫ ПАРАЛЛЕЛЬНОГО ОБСЛУЖИВАНИЯ
КРАТНЫХ ЗАЯВОК ПРОСТЕЙШЕГО ПОТОКА
В работе построена модель параллельного обслуживания заявок в системе
массового обслуживания, состоящей из k блоков обслуживания с неограниченным числом обслуживающих приборов. Найдено аналитическое выражение для производящей функций многомерного распределения вероятностей состояний цепи Маркова, характеризующей число заявок в каждом
блоке (подсистеме) в нестационарном режиме. Проведены расчеты основных вероятностных характеристик.
Ключевые слова: немарковские системы с неограниченным числом обслуживающих приборов, пуассоновский поток кратных заявок. параллельное
обслуживание, система массового обслуживания.
Параллельность процессов вычислений и обработки информации является одним из основных принципов, используемых при проектировании современных
компьютерных сетей. Это позволяет достигать максимальной скорости в работе и
существенной экономии времени. При оценке производительности первостепенное значение имеет продолжительность вычислительных процессов. Случайный
характер процессов формирования, обработки и передачи данных обуславливает
необходимость применения стохастических моделей, в качестве которых широко
используются модели массового обслуживания. Использование аппарата теории
массового обслуживания позволяет построить математические модели коммутационных сетей и провести теоретические исследования параметров функционирования реальной вычислительной системы [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-мерной цепью Маркова.
Л. А. Жидкова, С.П. Моисеева
50
λ(k)
μ1
μ1
. . .
μ2
μ2
. . .
. . .
. . .
. . .
μk
μ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 ) ,
откуда получаем систему дифференциальных уравнений:
∂P ( j1 , j2 ,..., jk , t )
= − ( λ + j1μ1 + j2μ 2 + ... + jk μ k ) P ( j1 , j2 ,..., jk , t ) +
∂t
+ ( j1 + 1) μ1 P ( j1 + 1, j2 ,..., jk , t ) + ( j2 + 1) μ 2 P ( j1 , j2 + 1,..., jk , t ) + ...
... + ( jk + 1) μ k P ( j1 , j2 ,..., jk + 1, t ) + λP ( j1 − 1, j2 − 1,..., jk − 1, t ) .
(1)
Определив производящую функцию k-мерного распределения P ( j1 , j2 ,..., jk , t )
в виде
F ( x1 , x2 ,..., xk , t ) =
∞
∞
∞
∑ ∑ ... ∑ x1 j x2 j ...xk j
1
j1 = 0 j2 = 0
jk = 0
2
k
P ( j1 , j2 ,..., jk , t ) ,
нетрудно показать, что она удовлетворяет уравнению
∂F ( x1 , x2 ,..., xk , t )
∂F ( x1 , x2 ,..., xk , t )
∂F ( x1 , x2 ,..., xk , t )
+ ( x1 − 1) μ1
+ ( x2 − 1) μ 2
+ ...
∂t
∂x1
∂x2
... + ( xk − 1) μ k
∂F ( x1 , x2 ,..., xk , t )
= λ ( x1 x2 ...xk − 1) F ( x1 , x2 ,..., xk , t ) .
∂xk
(2)
Исследование системы параллельного обслуживания кратных заявок простейшего потока 51
1.2. Вид производящей функции
при нестационарном функционировании СМО
Поставим задачу нахождения производящей функции при нестационарном
режиме функционирования рассматриваемой СМО, удовлетворяющей линейному
дифференциальному уравнению с частными производными первого порядка (2).
Для нахождения дополнительных условий воспользуемся тем фактом, что
производящая функция нестационарного распределения вероятностей числа занятых приборов в системе M|М|∞ определяется выражением [4]:
∞
⎧λ
⎫
F ( x, t ) = ∑ xi P (i, t ) = exp ⎨ ( x − 1)t ⎬ .
μ
⎩
⎭
i =0
Тогда для производящих функций одномерных маргинальных распределений
имеем
F ( x1 ,1,...1, t ) =
∞
∞
∞
∞
∑ ∑ ... ∑ x1 j P( j1 , j2 ,..., jk , t ) = ∑ x1 j P( j1 , t ) =
1
j1 = 0 j2 = 0
jk = 0
1
j1 = 0
⎧λ
⎫
= F ( j1 , t ) = exp ⎨ ( x1 − 1)t ⎬ .
⎩ μ1
⎭
⎧λ
⎫
F (1, x2 ,...,1, t ) = exp ⎨ ( x2 − 1)t ⎬ ,
⎩μ2
⎭
⎧λ
⎫
F (1,1,..., xk , t ) = exp ⎨ ( xk − 1)t ⎬ ,
μ
⎩ k
⎭
F (1,1,..., t ) = 1 , F ( x1 , x2 ,..., 0 ) = 1 .
(3)
Запишем систему уравнений (2) в частных производных первого порядка (2)
[4, 6]:
dxk
dx1
dx2
dt
dF
.
=
=
= ... =
=
1 μ1 ( x1 − 1) μ 2 ( x2 − 1)
μ k ( xk − 1) λ ( x1 x2 ...xk − 1) F
Систему обыкновенных дифференциальных уравнений перепишем в следующем виде:
dxk
dx1
dx2
dt
=
=
= ... =
=
1 μ1 ( x1 − 1) μ 2 ( x2 − 1)
μ k ( xk − 1)
= 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) ]} .
Решая данную систему, получаем, что решение имеет вид
(
)
F ( x1 , x2 ,..., xk , t ) = Φ ( x1 − 1) e−μ1t , ( x2 − 1) e−μ2t ,..., ( xk − 1) e−μk t ×
⎧ λ ( x1 − 1) ⋅ ( x2 − 1) ⋅ ... ⋅ ( xk − 1)
× exp ⎨
+
μ1 + μ 2 + ... + μ k
⎩
Л. А. Жидкова, С.П. Моисеева
52
+
λ ( x2 − 1) ⋅ ( x3 − 1) ⋅ ... ⋅ ( xk − 1) λ ⋅ ( x1 − 1) ⋅ ( x3 − 1) ⋅ ... ⋅ ( xk − 1)
+
+ ...
μ 2 + μ3 ... + μ k
μ1 + μ3 + ... + μ k
... +
+
λ ⋅ ( x1 − 1) ⋅ ... ⋅ ( xk − 2 − 1) ⋅ ( xk − 1)
+
μ1 + ... + μ k − 2 + μ k
λ ⋅ ( x1 − 1) ⋅ ... ⋅ ( xk − 2 − 1) ⋅ ( xk −1 − 1) λ ( x1 − 1) λ ( x2 − 1)
λ ( xk − 1) ⎫
+
+
+ ... +
⎬,
μ1 + ... + μ k − 2 + μ k −1
μ1
μ2
μk
⎭
где Φ(x1, x2,…, xk,) – произвольная дифференцируемая функция.
Учитывая дополнительные условия (3), имеем
⎧ λ ( x1 − 1)( x2 − 1) ... ( xk − 1)
+
F ( x1 , x2 ,..., xk , 0 ) = Φ ( x1 − 1, x2 − 1,..., xk − 1) exp ⎨
μ1 + μ 2 + ... + μ k
⎩
+
... +
λ ( x2 − 1) ⋅ ( x3 − 1) ⋅ ... ⋅ ( xk − 1) λ ⋅ ( x1 − 1) ⋅ ( x3 − 1) ⋅ ... ⋅ ( xk − 1)
+
+ ...
μ 2 + μ3 ... + μ k
μ1 + μ3 + ... + μ k
λ ⋅ ( x1 − 1) ⋅ ... ⋅ ( xk − 2 − 1) ⋅ ( xk −1 − 1) λ ( x1 − 1) λ ( x2 − 1)
λ ( xk − 1) ⎫
+
+
+ ... +
⎬ =1
μ1 + ... + μ k − 2 + μ k −1
μ1
μ2
μk
⎭
Откуда
⎧ ⎛ λ ⋅ ( x1 − 1) ⋅ ( x2 − 1) ⋅ ... ⋅ ( xk − 1)
Φ ( x1 − 1, x2 − 1,..., xk − 1) = exp ⎨− ⎜
+
μ1 + μ 2 + ... + μ k
⎩ ⎝
+
... +
λ ⋅ ( x2 − 1) ⋅ ( x3 − 1) ⋅ ... ⋅ ( xk − 1) λ ⋅ ( x1 − 1) ⋅ ( x3 − 1) ⋅ ... ⋅ ( xk − 1)
+
+ ...
μ 2 + μ3 ... + μ k
μ1 + μ3 + ... + μ k
λ ⋅ ( x1 − 1) ⋅ ... ⋅ ( xk − 2 − 1) ⋅ ( xk −1 − 1) λ ( x1 − 1) λ ( x2 − 1)
λ ( xk − 1) ⎫
+
+
+ ... +
⎬.
μ1 + ... + μ k − 2 + μ k −1
μ1
μ2
μk
⎭
Следовательно,
(
)
Φ ( x1 − 1) e −μ1t , ( x2 − 1) e −μ 2t ,..., ( xk − 1) e−μ k t =
⎧
λ
= exp ⎨−
( x1 − 1)( x2 − 1) ... ( xk − 1) ×
⎩ μ1 + μ 2 + ... + μ k
−
λ
( x2 − 1) ⋅ ( x3 − 1) ⋅ ... ⋅ ( xk − 1) e−(μ 2 +μ3 +...+μ k )t −
μ 2 + μ 3 ... + μ k
−
λ
( x1 − 1) ⋅ ( x3 − 1) ⋅ ... ⋅ ( xk − 1) e−( μ1 +μ3 +...+μ k )t −
μ1 + μ 3 + ... + μ k
−
λ
( x1 − 1) ...( xk − 2 ) ( xk − 1) e−( μ1 +...+μ k -2 +μ k )t −
μ1 + ... + μ k-2 + μ k
−
⎫
λ
λ
λ
( x1 − 1) e−μ1t − ( x2 − 1) e−μ 2t − ... − ( xk − 1) e−μ k t ⎬ .
μ1
μ2
μk
⎭
(4)
Исследование системы параллельного обслуживания кратных заявок простейшего потока 53
Подставляя полученное выражение в (4), получаем выражение для производящей функции F ( x1 , x2 ,..., xk , t ) :
⎧
λ
F ( x1 , x2 ,..., xk , t ) = exp ⎨
( x1 − 1)( x2 − 1) ... ( xk − 1) 1 − e−( μ1 +μ 2 +...+μ k )t +
⎩ μ1 + μ 2 + ... + μ k
(
+
+
λ
( x2 − 1) ⋅ ( x3 − 1) ⋅ ... ⋅ ( xk − 1) 1 − e−( μ 2 +μ3 +...+μ k )t +
μ 2 + μ 3 + ... + μ k
+
(
)
λ
( x1 − 1) ⋅ ( x3 − 1) ⋅ ... ⋅ ( xk − 1) ⋅ 1 − e−( μ1 +μ3 +...+μ k )t + ...
μ1 + μ 3 + ... + μ k
... +
+
)
(
)
λ
( x1 − 1) ...( xk − 2 ) ( xk − 1) 1 − e−(μ1 +...+μk − 2 +μk )t +
μ1 + ... + μ k − 2 + μ k
(
)
λ
( x1 − 1) ...( xk − 2 ) ( xk −1 − 1) 1 − e−( μ1 +...+μk − 2 +μk −1 )t +
μ1 + ... + μ k − 2 + μ k −1
(
)
⎫
λ
λ
λ
( x1 − 1) 1 − e−μ1t + ( x2 − 1) 1 − e−μ2t + ... + ( x k −1) 1 − e−μk t ⎬ .
μ1
μ2
μk
⎭
(
)
(
)
(
)
(5)
Если в (5) t →∞, то получим вид производящей функции для финального распределения вероятностей рассматриваемой системы.
Полученное выражение для производящей функции позволяет получить основные стационарные характеристики k-мерной цепи Маркова, характеризующей
число заявок в каждом блоке (подсистеме).
Математическое ожидание числа заявок в каждом блоке (подсистеме)
Mik =
∂F ( x1 , x2 ,..., xk )
∂xk
x1 =1
x2 =1
...
xk =1
=
λ
.
μk
Дисперсия числа заявок в каждом блоке (подсистеме)
Dik =
λ
.
μk
Коэффициент корреляции
Rij =
μ i ×μ j
μi + μ j
.
Заключение
В настоящей работе были построена математическая модель параллельного
обслуживания кратных заявокв в идее СМО с k блоками обслуживания. Проведено исследование, а именно, получены выражение для производящей функций и
основные вероятностные характеристики k-мерной цепи Маркова, характеризующие число заявок в каждом блоке (подсистеме).
54
Л. А. Жидкова, С.П. Моисеева
ЛИТЕРАТУРА
1. Гнеденко Б.В., Коваленко И.Н. Введение в теорию массового обслуживания. 4-е изд.,
испр. М.: Изд-во ЛКИ, 2007. 400 с.
2. Эндрюс Г.Р. Основы многопоточного, параллельного и распределенного программирования: пер. с англ. М.: Изд. дом «Вильямс», 2003. 512 с.
3. Ивановская И.А., Моисеева С.П. Математическая модель параллельного обслуживания
заявок в распределенных вычислительных системах // Сборник научных статей. Минск,
2010. Вып. 3. С. 123−128.
4. Назаров А.А., Терпугов А.Ф. Теория массового обслуживания: учеб. пособие. Томск:
Изд-во НТЛ, 2004. 228 с.
5. Чечельницкий А.А., Кучеренко О.В. Стационарные характеристики параллельно функционирующих систем обслуживания с двумерным входным потоком // Сборник научных статей. Минск, 2009. Вып. 2. С. 262−268.
6. Эльcгольц Л.Э. Дифференциальные уравнения и вариационное исчисление. М.: Наука,
1969. 424 с.
Жидкова Любовь Александровна
Моисеева Светлана Петровна
Томский государственный университет
E-mail: zhidkovala@mail.ru; smoiseeva@mail.ru
Поступила в редакцию 19 августа 2011 г.
Документ
Категория
Без категории
Просмотров
3
Размер файла
399 Кб
Теги
обслуживание, система, заявок, кратные, параллельное, исследование, простейшего, поток
1/--страниц
Пожаловаться на содержимое документа