5Лабораторная работа №5. Системы массового обслуживания (смо) и их характеристики

Основные компоненты СМО.

В любой простой СМО (рис. 5.1) на обслуживающее устройство прибывают из источника заявок (S) некоторые объекты (заявки). Они присоединяются к ожидающей очереди (Q), если она есть, или обслуживаются в некотором порядке в обрабатывающем устройстве (D), а затем покидают систему.

Рис. 5.1 Одноканальная СМО

(с одним устройством обслужива­ния).

Источник заявок (S).

Для задания входящего потока заявок необходимо описать моменты времени их поступления в систему (закон поступления) и количество заявок, которое поступило одно­временно. Закон поступления может быть детерминированный (на­пример, одна заявка поступает каждые 5 мин) или вероятност­ный (заявки могут появляться с равной вероятностью в интерва­ле 5±2 мин).

Очередь (Q).

Дисциплины постановки в очередь и выбора из нее опреде­ляют порядок постановки заявок в очередь, если заняты устрой­ства обслуживания, и порядок выбора из очереди, если освобождается обслуживающее устройство. Простейшая дисциплина допускает постановку в очередь в порядке поступления заявок. Такую дис­циплину называют «раньше поступил - раньше обслужился» напри­мер, очередь к телефону-автомату.

Организация очереди по правилу «последний поступил - пер­вый обслужился» допускает, что на обслуживание выбираются последние требования из очереди. Это правило также называется «стеком» или «магазином».

Правило выбора из очереди может быть случайным (RANDOM).

Возможна также организация выбора из очереди по парамет­рам (например, мужчины в очереди пропускают женщин вперед).

На очередь могут накладываться ограничения по длине очереди или по времени пребывания в ней. Например, если в очереди нахо­дится более трех заявок, то новая заявка, которая поступи­ла, покидает систему; или, если время пребывания в очереди более двух минут, то заявка покидает систему.

Очередь может быть с ограниченным количеством мест ожида­ния в ней - это так называемый буфер (например, бункер, в который поступают заготовки раньше, чем они будут обработаны станком). Для ускорения работы компьютеров используются буферы при об­мене информацией между быстрыми и медленными устройствами (буферы ввода-вывода). Информация заранее разметается в буфере, а потом считывается из него. В сетях ЭВМ буферы используются для организации очередей сообщений или пакетов, если линия связи занята.

Обрабатывающее устройство (D).

Время обслуживания в обрабатывающем устройстве бывает детерминированным или заданным вероятностным законом распределения. Обслуживание может организовываться с помощью одного уст­ройства - это так называемые системы с одним устройством (ка­налом) обслуживания - или с несколькими идентичными устройст­вами обслуживания, например, если установлено несколько кабин с телефонами-автоматами. Системы с идентичными устройствами об­служивания называют многоканальными системами. Устройства обслуживания могут быть объединены в последовательную цепочку. Это многофазные системы обслуживания, в которых требования последовательно проходят несколько фаз обслуживания, перед тем как покинуть систему. В качестве примера многофазной системы об­служивания можно рассмотреть сборочный конвейер.

Дисциплины обслуживания определяют:

• при каких условиях прекращается обслуживание заявок;

• как выбирается для обслуживания следующая заявка;

• что делать с частично обслуженной заявкой.

Различают дисциплины обслуживания бесприоритетные и приоритетные. При бесприоритетном обслуживании порядок об­служивания определяется дисциплиной выбора из очереди. В компьютерных системах часто используются циклические дисциплины обслуживания, то есть требование (программа) много­кратно использует устройство (процессор) для обслуживания перед тем, как его оставит. После каждого этапа обслуживания заявка снова поступает в очередь к устройству.

При приоритетном обслуживании заявок задается некото­рый параметр, который определяет ею приоритет. Этот параметр может задаваться в числовом виде (статический приоритет) или в виде функции, которая зависит от времени пребывания в системе (динамический приоритет).

Дисциплины обслуживания могут быть с относительными или абсолютными приоритетами. Относительный приоритет преду­сматривает, что поступление заявок с более высоким приорите­том не перерывает обслуживания менее приоритетной заявки (обслуживание без прерывания). Из заявок с одинаковыми при­оритетами могут организовываться очереди.

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

Обозначения систем с одним устройством обслуживания.

Для обозначения СМО используются три параметра для первых трех параметров: X/Y/Z,

где X - распределение времени поступления;

Y - распределение времени обслуживания;

Z - число обслуживаю­щих устройств.

В теории СМО некоторые аналитические решения были получе­ны для систем вида D/D/l, M/M/1 и M/G/1. Для других значений пара­метров систем обслуживания аналитические решения не были получе­ны, то есть эта проблема мотивирует использование моделирования.

Самая известная модель - это так называемая СМО типа М/М/1, где М - марковские процессы распределения времени поступления и обслуживания с одним устройством. Например, в системе М/М/1 время между двумя поступлениями в систему требований и время об­служивания имеют экспоненциальные распределения. Такая СМО иногда используется как модель для одного процессора компьютер­ной системы или как стандартное устройство ввода-вывода (напри­мер, магнитный диск). Система D/D/1 - детерминированная система, тогда как D/M/1 - смешанная. Если о системе мало известно, это обо­значается как G/G/m, то есть система с произвольными распределе­ниями и m устройствами.

Детерминированная система (D/D/1).

а) Основные предположения. Относительно потока требований и их обслу­живания сделаем следующие предположения:

• Источник заявок. Заявки поступают от источника заявок через одинаковые интервалы времени, каждый интервал длиной в а единиц.

• Дисциплина очереди. «Раньше пришел — раньше обслужился» т. е. ожидающие заявки образуют очередь, и когда устройство осво­бодится, на обслуживание поступает заявка, имеющее большее время ожидания.

• Обрабатывающее устройство. Заявки обслуживаются за одинаковые интервалы времени, каждый длиной в b единиц. Как только закончится обслуживание одной заявки, устройство готово обслуживанию следующей заявки.

Замечание. Принято определять длину очереди как общее число заявок, находящихся на обслуживании и ожидающих в очереди. На рисунке изображена общая схема модели очереди.

б) Формальный анализ. Поведение системы зависит от того, как связаны между собой b и а. Рассмотрим отдельно каждый случай:

• b>а. Это значит, что скорость обслуживания 1/b меньше, чем скорость поступления заявок 1/a, т. е. заявки обслуживаются и покидают систему медленнее, чем прибывают. Ясно, что в этом случае должна образоваться очередь и она будет неопределенно возрастать.

• b=а. Если в очереди нет заявок, то первая поступившая заявка сразу начинает обслуживаться. Ее обслуживание закон­чится в тот же самый момент, в который поступит вторая заявка. И следовательно, не будет ожидающих заявок. Если первоначально есть очередь, то ее длина (т. е. число заявок, ожидающих обслуживания, плюс число обслуживаемых) будет оставаться постоянной.

• b < а. Это значит, что скорость обслуживания больше, чем скорость поступления заявок; следовательно, какое бы ни было начальное число ожидающих заявок, длина очереди, несомненно, будет сокращаться до 1 или 0. Пусть в начале процесса число заявок в очереди n, (n> 2); если первоначально есть только одна заявка (т.е. n=1), то она будет обслужена прежде, чем поступят следующая заявка, и в очереди никого не будет).

Момент времени, когда система обслуживания станет свободной от заявок, определяется по формуле

, (1)

где […] - обозначает целую часть числа без округления.

Заявка, поступившая в момент времени , найдет систему обслуживания пустой или только что освободившейся.

Заявка, поступившая в момент времени , найдет впереди себя

заявок, стоящих в очереди, причем первая из них в этот момент поступит на обслуживание. В последней формуле: n - начальная очередь; - число заявок обслуженных к моменту времени ; - число новых поступлений. Следовательно, время ожидания для этой заявки равно:

(2)

Пример выполнения работы.

Предположим, что b=1 мин, а=4 мин, n=12. Для обслуживания всех 12 заявок нужно bn =12 мин. В течение этого времени поступят дальнейшие 12/4 =3 заявки и станут в очередь; им вместе потребуется 31 =3 мин на обслуживание. В течение этих 3 мин не поступит ни одной заявки (так как 3 < а), т. е. заявки, которые в дальнейшем поступят в систему, не придется ждать обслуживания.

Следовательно, общее чисто заявок в системе равно 12 + 3 =15 требованиям (сюда включено и первые из 12 заявок - их обслуживание началось, как только начался процесс).

Определим по формуле (1) момент времени, когда система обслуживания впервые станет свободной от требований

мин.

Результаты расчетов проиллюстрированы на рисунке.

Построим гистограмму времени ожидания для всех поступающих заявок.

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

Вариант	а	b	n
1	5	2	20
2	3	1	50
3	6	3	30
4	2	1	6
5	4	2	10
6	3	1	8
7	4	2	12
8	6	3	7
9	3	1	6
10	8	2	20
11	8	4	15
12	3	2	11
13	4	3	9
14	5	1	8
15	3	2	10
16	7	3	7
17	4	1	6
18	3	2	16
19	6	4	10
20	4	3	20
21	3	2	9
22	8	4	15
23	5	4	12
24	4	3	16
25	5	3	20