Материал: 2443
31
массового обслуживания, различают два основных вида СМО:системы с отказами, в которых заявка, поступившая в систему в
момент, когда все каналы заняты, получает отказ и покидает очередь;системы с ожиданием (очередью), в которых заявка,
поступившая в момент, когда все каналы обслуживания заняты, становится в очередь и ждет, пока не освободится один из каналов.
Для указания типа СМО используются общепринятые обозначения Кендалла – Баша: X/Y/Z/m,
где X – вид закона распределения интервалов поступления заявок; Y – вид закона распределения времени обслуживания заявок;
Z – число каналов;
m – число мест в очереди.
В обозначениях вида закона распределения буква M соответствует экспоненциальному распределению (от слова Марковиан), букваE–распределению Эрланга, R – равномерному распределению и D – детерминированной величине.
Например, запись M/M/1означает одноканальную систему с экспоненциальными распределениями времени поступления и обслуживания заявок (М – марковская) без очереди.
2.7.Расчёт основных характеристик СМО на основе использования их аналитическихмоделей
Рассмотрим такие СМО, в которых возможные состояния системы образуют цепь и каждое состояние, кроме исходного и последнего, связано прямой и обратной связью с двумя соседними состояниями. Такая схема процесса, протекающего в системе, называется схемой «гибели и размножения». Термин ведёт начало от биологических задач, процесс описывает изменение численности популяции.
Если в такой системе все потоки, переводящие систему из состояния в состояние пуассоновские, то процесс называется
марковским случайным процессом «гибели и размножения».
Заметим, что в таких системах все состояния являются существенными, а значит, существуют финальные вероятности состояний, которые можно найти из линейной системы уравнений Эрланга.
На практике значительная часть систем (СМО) может описываться в рамках процесса «гибели и размножения».
32
Рассмотрим некоторые типы таких систем: а) одноканальные с отказами (без очереди); б) одноканальные с ограниченной очередью; в) многоканальные с отказами (без очереди); г) многоканальные с ограниченной очередью.
Одноканальные системы с отказами
Рассмотрим одноканальную систему обслуживания с отказом, т. е. если поступает заявка на обслуживание, а устройство занято, то заявка получает отказ в обслуживании. Граф системы (рис. 2.5) имеет два состояния S0 – устройство свободно и S1 – устройство занято. Пусть интенсивность входящего потока равна λ (количество заявок в ед. времени), а интенсивность обслуживания равна µ.
S0 S1
Рис. 2.5. Граф одноканальной системы без очереди
Для изображённого графа система уравнений Эрланга имеет вид:
Из неё находим: 
Основные характеристики системы M/M/1:
вероятность отказа Pотк = Р1 = λ / (λ + µ); вероятность обслуживания Робс = 1 – Pотк = µ / (λ+µ).
Одноканальные системы с ограниченнойочередью
Рассмотрим теперь случай, когда устройство одноканальное, но если оно занято, то заявка не получает отказ, а становится в очередь к устройству. Очередь имеет длину не более n мест. Соответственно, граф
33
состояний (см. рис. 2.6) будет иметь n + 1 вершину: состояние S0 – устройство свободно; S1 – устройство занято, нет очереди; S2 – устройство занято, 1 в очереди; Sn+1 – устройство занято, n заявок в очереди.
|
|
|
|
|
|
|
|
|
|
S0 |
S1 |
S2 |
Sn |
Sn+1 |
|
|
|
|
|
Рис. 2.6. Граф одноканальной системы с очередью
Для такого графа система Эрланга имеет вид:
Из неё последовательно выражая все Рk через Р0 и подставляя в последнее нормировочное уравнение, имеем:
Основные характеристики системы M/M/1 / n:
вероятность отказа Pотк = Рn+1 = (λ/µ)n+1P0; вероятность обслуживания (относительная пропускная
способность) Q = Робс=1 – Pотк ;
абсолютная пропускная способность А = λQ;
среднее число мест в очереди N = P2 + 2P3 + 3P4 +…nPn+1 .
Многоканальные системы сотказами
Рассмотрим случай, когда устройство многоканальное, количество каналов равно m. Если все каналы заняты, то заявка получает отказ. Граф
34
состояний будет иметь m + 1 вершину (см. рис. 2.7): состояние S0 – устройство свободно; S1 – один канал занят; S2 – два канала занято; Sm – m каналов занято.
|
|
|
|
S0 |
S1 |
S2 |
Sm |
|
|
2 |
m |
Рис. 2.7. Граф одноканальной системы с очередью
Обратите внимание, что интенсивность выходящих потоков кратна µ, например, при переходе из состояния S2 в состояние S1 интенсивность потока равна 2µ, т. к. если были заняты два канала, а затем стал занят один, то неизвестно какой из них освободился: µ + µ = 2µ.
Для этого графа построим систему уравнений Эрланга:
Выражаем все Рk через Р0 и подставляем в последнее нормировочное уравнение:
Основные характеристики системы M/M/m:
вероятность отказа Pотк = Рm = 1/m! (λ/µ)mP0; вероятность обслуживания Q =Робс=1– Pотк ; абсолютная пропускная способность А= λQ;
среднее количество занятых каналов К = P1 + 2P2 + 3P3 +…mPm .
Количество каналов можно вычислить проще, зная соотношение
35
А = µК : среднее число заявок, обслуженных в единицу времени, равно произведению средней производительности одного канала на среднее число занятых каналов.
Многоканальные системы сограниченной очередью
Пусть в системе имеется m каналов обслуживания и n мест в очереди. Если свободных мест в очереди нет, заявка получает отказ. Граф состояний такой системы имеет вид (рис. 2.8):
|
|
|
|
|
|
|
S0 |
S1 |
S2 |
. . . |
Sm |
Sm+1 . . . |
Sm+n |
|
2 |
|
m |
m |
m |
m |
Рис. 2.8. Граф многоканальной системы с очередью
Граф динамики многоканальной системы такого вида состоит из двух частей: до состояния Sm – все m каналов занято, очереди нет, и после от Sm+1 – все m заняты, одна заявка в очереди до Sm+n – все каналы заняты, n заявок в очереди. Общее количество состояний в графе конечно и равно m + n + 1, включая нулевое состояние, где n – величина, ограничивающая длину очереди (в другой терминологии – n – количество мест в накопителе очереди), m – количество каналов обслуживания.
Построим систему уравнений Эрланга для этой СМО и
разрешим её. Обозначим |
|
, тогда формулы вероятностей |
|
состояний имеют вид:
Основные характеристики системы M/M/m/n: