Курс_ИОиТПР_Комолов_АВ (1006469), страница 3
Текст из файла (страница 3)
Ответы:
4. Теория массового обслуживания.
Разделяется на 2 раздела:
-
теория потоков;
-
теория систем массового обслуживания (СМО).
Потоки случайных событий: если события повторяются с течением времени, то можно говорить о потоке этих событий (явлений).
Если события, образующие поток, одинаковы в каком-то смысле (по форме проявления, по природе и т. д.), то поток называется однородным.
Если в некотором потоке события происходят через равные, возможно, наперед заданные промежутки времени, то он называется регулярным.
Если эти промежутки времени между событиями представляют собой случайную величину, то поток называется случайным.
Каковы средства описания свойств потока и что является предметом описания?
Существует графическое представление потоков, в котором на оси времени t размещаются случайным образом точки, символизирующие поток событий.
T
t
Рассмотрим на этой оси некоторый случайный интервал длиной .
Количество событий, приходящихся на этот интервал, случайно, то есть являются случайной величиной с возможными значениями.
H – случайная величина – количество событий на интервале
= 0, 1, 2, …
Характеристикой случайного потока может служить функция распределения случайной величины H – F().
Случайная величина T – время между любыми двумя соседними событиями в потоке. Ее возможные значения: t от 0 до .
Тогда функция распределения случайной величины T – F(t) является второй важной характеристикой потока.
H – дискретная случайная величина
T – непрерывная случайная величина
H является главной характеристикой любого потока, так как зная ее закон распределения, мы можем широко охарактеризовать поток.
Поток является стационарным, если его характеристики не меняются со временем (при любой , F() – остается одной и той же).
Если в потоке соседние события не могут (хотя бы теоретически) повториться мгновенно, то такой поток называется ординарным (то есть событие произошло, потом поток “отдыхает”).
Если в потоке картина, наблюдаемая в разных непересекающихся интервалах 1 и 2, одна и та же в вероятностном смысле, то поток называется потоком без последействия.
0 1 2 t
То есть события интервала 1 не влияют на события интервала2.
Простейший случайный поток
(поток Пуасона).
Характерные особенности потока Пуасона:
-
случайная величина H распределена по зкону Пуасона:
()2
P(H = ) = e-, где = 0, 1, 2, …
!
P
- среднеожидаемое значение H (математическое ожидание H) или интенсивность потока-
в
ремя T как случайная величина распределена по показательному закону:
f(t) = e-, t (0; )
f(t)
1
t
-
поток стационарен (так как P(H = ) не зависит от t) и без последействия.
Верно для данного потока, что:
P(H 2)
Lim = 0 выразитель свойства ординарности
0 P(H = 1)
Система массового обслуживания (СМО).
Любая система, подвергающаяся воздействию потока событий и реагирующая на это тем, что как-то преобразует этот поток и порождает новый поток событий, может быть названа СМО.
исходящий
поток
СМО
входящий
поток


Простейшая модель обслуживания.
Одноканальная СМО с отказом.
Предположим:
-
дана СМО, способная обрабатывать поступающие заявки только в последовательном режиме (то есть одноканальная)
з
аявки (события)
______


-
входящий поток заявок – Пуасоновский с интенсивностью
-
исходящий поток формируется при условии, что время обслуживания каждой заявки в системе, являясь случайным, распределено по показательному закону с параметром (вместо )
f(t) = e-t
- интенсивность обслуживания
-
заявка, пришедшая в систему и заставшая ее занятой, покидает систему (не дожидаясь обслуживания, получает отказ).
В этих условиях требуется определять характеристики рассматриваемой СМО (вероятность отказа, пропускную способность и др.) и тем самым построить формальную модель системы.
Общий подход к исследованию СМО, в том числе и этой, предполагает рассмотрение возможных состояний СМО в разные моменты времени и условий их перехода из одного состояния в другое.
Возможные состояния простейшей СМО:
-
S0 – система свободна;
-
S1 – система занята обслуживанием заявки.
Переход из одного состояния в другое происходит:
- из S0 в S1 с интенсивностью
- из S1 в S0 с интенсивностью
Схема возможных состояний и переходов для данной СМО:
t - t t t + t t
t - мало
Какова вероятность того, что в произвольно взятый момент времени t система окажется в состоянии S0?
Это условие будет верно, когда:
-
либо потому, что была в S0 и за t осталась в нем;
-
либо была в состоянии S1, но за t стала S0.
Такая логика дает возможность получить систему дифференциальных уравнений, описывающих процесс, происходящий в системе.
dp0(t)
= - (+ )p0(t) - система была бы, если бы было много состояний
dt
Условие: P0 = 1 при t = 0
Решением уравнения будет:
P0 = + e-(+ )t
+ +
Из условия P0 + P1 = 1 следует, что:
P1 = (1 – e-( + )t)
+
P0
P1,P0
P1
/+
/+

P1,P0
/+
P1

P
t
1
P0
P0
/+


P1
1
t




//
С течением времени система выходит на стационарный режим работы, который характеризуется неизменностью значений P1 и P0 и они равны:
P0стац = /; P1стац = /
Характеристики:
-
вероятность отказа в обслуживании равна вероятности того, что в произвольно взятый момент времени система окажется занятой обслуживанием заявки, то есть
Pотк = P1стац = /
-
относительная пропускная способность системы – доля обслуженных заявок от общего числа пришедших заявок:
qотн = P0стац = /
Если , то система начинает не справляться со своими задачами, и вероятность отказа начинает стремиться к единице.
Если , то система будет почти всегда свободна и относительная пропускная способность будет стремиться к единице.
Если , то каждая пришедшая заявка с вероятностью 0,5 будет либо обслужена, либо получит отказ.
Пример:
Пусть должно быть Pотк 0,1, то есть
/ 0,1, 10 .
Многоканальная система обслуживания с отказами.
Многоканальность – способность обслуживать заявки в параллельном режиме.
заявки


СМО
1……………
.
r……………






Каналы идентичны в смысле своих возможностей.
Поток обслуживания (результатов) формируется исходя из того, что каждый канал обслуживания имеет интенсивность .
То есть это объединение r простейших систем.
Предполагается, что заявка, пришедшая в систему и заставшая все каналы занятыми, получает отказ в обслуживании.
Требуется дать описание процессов, проходящих в системе, и определенные характеристики системы (вероятность отказа, qотн и др.).
Схема состояний и переходов:
S0 – система абсолютно свободна (все каналы свободны);
S1 – в системе занят один канал, остальные свободны;
Sr – система занята полностью (все r каналов).
………….
………..














2 ……r…
…….
P0 P1 P2 ………………………… Pr
t
t t + t
Получим систему уравнений:
d P0/dt = - P0 + P1
…………………….
d
PK/dt = -( + k)PK + PK-1 + (k+1)PK+1
… ………………….
dPr/dt = - rPr + Pr-1
k
= 1, 2, ……., r-1
P0 = 1, PK = 0 (k = 1, 2, ……., r) при t = 0
r 1 P0
P0 = [ ( )]-1; PK = ()K
=0 ! r!
k = 1, ………., r
Характеристики:
-
Pотк = Pr = (/)r(P0 /r!)
-
qотн = 1 - Pr = 1 – (/)r(P0 /r!)
-
среднее число заявок, обслуживаемых одновременно
nоднср = (/)qотн
Эта система значительно эффективнее (в r! раз), чем одноканальная.
Одноканальная СМО с ограниченной очередью.
………….
_______


СМО
2 1
Допускается пребывание заявок, нашедших систему занятой, в очереди.
Длина этой очереди не должна быть больше некоторой величины .
Требуется: проанализировать процесс и найти характеристики системы.
Схема состояний и переходов
λ λ λ
μ μ μ
-
п
еречень состояний одноканальной системы с отказом
S0 – система свободна
S0 - система занята
S0 - система занята и одна заявка в очереди
…..
Sη+1 – система занята и очередь наполнена