Моделирование систем массового обслуживания (стр. 7 из 7)

S1 заменяем эквивалентной цепочкой из трех псевдосостояний.

Последние 2 уравнения являются условием нормировки и условием эквивалентности замены состояния S1 псевдосостояниями.

Метод вложенных цепей Маркова.

Вложенные марковские цепи образуются следующим образом: в исходном случайном процессе выбираются такие моменты времени tk, в которых значения характеристик процесса образует марковскую цепь. Моменты времени t_k обычно являются случайными и зависят от свойств самого процесса. Исходный процесс исследуется в выбранные моменты времени с помощью стандартных методов теории массового обслуживания.

Частным случаем вложенных цепей Маркова, являются полумарковские случайные процессы. Случайный процесс с конечным или счетным множеством состояний называется полумарковским, если заданны вероятности перехода системы из одного состояния в другое и распределение времени пребывания процесса в каждом состоянии (в виде функции распределения F(t) или в виде плотности распределения f(t))

Классификация систем массового обслуживания

В общем случае СМО классифицируется по следующим признакам:

· закону распределения входного потока

· числу обслуживающих приборов

· закону распределения времени обслуживания в обслуживающих приборах

· числу мест в очереди

· дисциплине обслуживания

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

A | B | C | D | E

A	Закон распределения интервалов времени между поступлением заявок.	M – экспоненциальныйE – ЭрлангаH– гиперэкспоненциальныйГ – гамма-распределениеD– детерминированное распределениеG – произвольное распределение
B	Закон распределения времени обслуживания в приборах СМО.
C	Число обслуживающих приборов.	1 – для одноканальных системl– для многоканальных систем
D	Число мест в очереди. Если число мест не ограничено, то поле можно опустить.	r либо n – для конечного числа мест
E	Дисциплина обслуживания. По умолчанию LIFO – в этом случае поле может опускаться.	FIFO, LIFO, RANDOM

Примеры.

M | M | 1

СМО с одним обслуживающим прибором, бесконечной очередью, экспоненциальным законом распределения интервалов времени между поступлением заявок и временем обслуживания и дисциплиной обслуживания FIFO.

E | H | l | r | LIFO

CМО с несколькими обслуживающими приборами, конечной очередью, законом распределения Эрланга интервалов между поступлением заявок, гиперэкспоненциальным законом распределения времени обслуживания заявок в приборах и дисциплиной обслуживания LIFO.

G | G | l

СМО с несколькими приборами, бесконечной очередью, произвольными законами распределения времени между поступлением заявок и времени обслуживания, FIFO.

Для моделирования вычислительной системы наиболее часто используются следующие типы СМО:

1. Одноканальная СМО с ожиданием.

· один обслуживающий прибор с бесконечной очередью

· является наиболее распространенной при моделировании

· может заменить практически любой узел вычислительной системы или ЛВС

2. Одноканальная СМО с потерями.

· один обслуживающий прибор с конечным числом мест в очереди

· если число заявок превышает число мест в очереди, то лишние заявки теряются

· используется при моделировании каналов передач данных в ВС и ЛВС

3. Многоканальная СМО с ожиданием.

· несколько параллельно работающих обслуживающих приборов с общей бесконечной очередью

· используется при моделировании групп абонентских терминалов, работающих в диалоговом режиме

4. Многоканальная СМО с потерями.

· несколько параллельно работающих обслуживающих приборов с общей очередью, число мест в которой ограничено

· часто используется, как и (2), при исследовании каналов связи

5. Одноканальная СМО с групповым поступлением заявок

· один обслуживающий прибор с бесконечной очередью

· перед обслуживанием заявки группируются в пакеты по определенном признаку или правилам

· используется для моделирования центров коммутации

6. Одноканальная СМО с групповым обслуживанием заявок

· один обслуживающий прибор с бесконечной очередью

· заявки обслуживаются пакетами, составленными по определенному правилу

· используется для моделирования центров коммутации

Наименование	Обозначение	Схема
Одноканальная с ожиданием	G \| G \| 1
Одноканальная с потерями	*G \| G \| 1 \| r*
Многоканальная с ожиданием	*G \| G \| l*
Многоканальная с потерями	*G \| G \| l \| r*
Одноканальная с групповым поступлением заявок	*Gr \| G \| 1* r
Одноканальная с групповым обслуживанием заявок	*G \| Gr \| 1* r

Вычислительные сети в целом могут быть представлены в виде СМО. Различают следующие типы сетей:

1. Открытые

2. Замкнутые

3. Смешанные

Открытой называется СМО, состоящая из m узлов, причем хотя бы в один из узлов сети поступают извне входной поток заявок и обязательное имеется хотя бы один сток заявок из сети.

Для открытой системы характерно то, что интенсивность поступления заявок в сеть не зависит от состояния сети, т.е. от числа заявок уже поступивших в сеть. Такие сети как правило используются для моделирования ВС, работающих в неоперативном режиме.

S1, S2 – моделируют работу узлов коммутации

S3, S4 – моделируют работу серверов

S5, S6 – моделируют работу межузловых каналов

В сети циркулируют 2 потока заявок. Каждая заявка поступает на вход соответствующего узла коммутатора, где определяется место её обработки. Затем заявка передается на свой сервер или по каналу связи на соседний сервер, где обрабатывается. После чего, возвращается к источнику и покидает сеть.

Замкнутой называется СМО с множеством узлов m без источника и стока, в которой циркулирует постоянное число заявок.

Замкнутые СМО используются для моделирования таких ВС, источником информации для которых служат абонентские терминалы, работающие в диалоговом режиме. В этом случае каждая группа абонентских терминалов представляется в виде многоканальной СМО с ожиданием и включается в состав устройств сети.

Простой режим работы диалоговых абонентов: абонент не производит никаких действий, кроме посылки заданий в ВС и обслуживания полученного ответа.

S01, S02 – группа абонентских терминалов

S7, S8 – каналы связи с абонентами

S1, S2 – узлы коммутации

S3, S4 – серверы

S5, S6 – каналы межузловой связи

Абоненты с терминалов посылают запросы, которые по каналам связи поступают на узлы коммутатора, а оттуда на обработку на свой или соседний сервер.

При сложном режиме диалога работа абонентов представляется в виде совокупности операций некоторого процесса, называющимся технологическим. Каждая операция технологического процесса моделируется соответствующей СМО. Причем, часть операций может предусматривать обращение к ВС, а другая часть может замыкаться сама на себя.

Схема представленная на рисунке находится на месте S01 и S02.

Cмешанной называется СМО, в которой циркулируют несколько различных типов заявок (трафика). Причем относительно одних типов заявок сеть замкнута, а относительно других – открыта.

С помощью смешанных сетей моделируются такие ВС, часть абонентов которых работает в диалоговом режиме, а часть в неоперативном. Для диалоговых абонентов различают также простой и сложный режимы работы. Часто смешанные СМО используются в сетях, в которых сервер дополнительно загружается задачами, решаемыми на фоне работы самой сети.