Сети массового обслуживания и их применение. Понятие о системах массового обслуживания (СМО). Главные понятия Теории

Применение различных математических методов к формализации. Акцент на сложную систему - непредсказуемую. Носитель неопределенности является человек.

Характерным примером стохастических (случайные, вероятностные) задач являются модели систем массового обслуживания.

СМО имеют повсеместное распространение. Это телефонные сети, автозаправочные станции, предприятия бытового обслуживания, билетные кассы, торговые мероприятия и т.д.

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

Примерами СМО могут служить:

посты технического обслуживания автомобилей;

посты ремонта автомобилей;

аудиторские фирмы и т.д.

Основоположником теории массового обслуживания, в частности, теории очередей, является известный датский ученый А.К.Эрланг (1878-1929), который исследовал процессы обслуживания на телефонных станциях.

Системы, в которых имеют место процессы обслуживания, называют системами массового обслуживания (СМО).

Чтобы описать систему массового обслуживания, необходимо задать:

- входной поток заявок;

- дисциплину обслуживания;

- время обслуживания

- количество каналов обслуживания.

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

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

первым пришел – первым обслуживаешься;

пришел последним - обслуживаешься первым; (коробочка для теннисных шариков, стек в технике)

случайный отбор заявок;

отбор заявок по критерию приоритетности.

Время обслуживания заявки в СМО является случайной величиной. Наиболее распространенным законом распределения является экспоненциальный закон.  - скорость обслуживания. =количество заявок обслуживания/ед. времени.

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

Обобщенная структура СМО представлена на рис.

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

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

К задачам определения характеристик структуры СМО относятся задача выбора количества каналов обслуживания (базовых элементов {Ф i }), задача определения способа соединения каналов (множества элементов связей {Hj}), а также задача определения пропускной способности каналов.

1). Выбор структуры . Если каналы работают параллельно, то проблема выбора Str сводится к определению количества каналов в обслуживающей части исходя из условия обеспечения работоспособности СМО. (Если очередь не является бесконечно растущей).

Отметим, что при определении количества каналов системы, в случае их параллельного расположения, необходимо соблюдать условие работоспособности системы . Обозначим:  - среднее число заявок, поступающих в единицу времени, т.е. интенсивность входного потока;  - среднее число заявок, удовлетворяемых в единицу времени, т.е. интенсивность обслуживания; S - количество каналов обслуживания. Тогда условие работоспособности СМО запишется

или
. Выполнение этого условия позволяет вычислить нижнюю границу количества каналов.

В случае, если
, система не справляется с очередью. Очередь при этом растет безгранично.

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

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

1. Показатели эффективности использования СМО.

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

Относительная пропускная способность СМО – отношение среднего числа заявок, обслуживаемых СМО в единицу времени, к среднему числу поступивших заявок за это время.

Средняя продолжительность периода занятости СМО.

Коэффициент использования СМО - средняя доля времени, в течение которого СМО занята обслуживанием заявок.

2. Показатели качества обслуживания заявок.

Среднее время ожидания заявки в очереди.

Среднее время пребывания заявки в СМО.

Вероятность отказа заявке в обслуживании без ожидания.

Вероятность того, что поступившая заявка немедленно будет принята к обслуживанию.

Закон распределения времени ожидания заявки в очереди.

Закон распределения времени пребывания заявки в СМО.

Среднее число заявок, находящихся в очереди.

Среднее число заявок, находящихся в СМО.

3. Показатели эффективности функционирования пары «СМО - потребитель».

При выборе критерия эффективности функционирования СМО необходимо учесть двойственный подход к рассмотрению систем массового обслуживания. Например, работу универсама, как СМО, можно рассматривать с противоположных сторон. С одной, традиционно принятой, стороны покупатель, ожидающий свою очередь у кассы, представляет собой заявку на обслуживание, а кассир - канал обслуживания. С другой стороны, кассир, который ожидает покупателей, может быть рассмотрен в качестве заявки на обслуживание, а покупатель - обслуживающее устройство, способное удовлетворить заявку, т.е. подойти к кассе и прекратить вынужденный простой кассира. (традиционно – покупателей > чем кассиров, если кассиров > чем покупателей, они ждут покупателей).

С
учетом этого целесообразно минимизировать обе части СМО одновременно.

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

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

1. По характеру обслуживания выделяют следующие виды СМО:

1.1. Системы с ожиданием или системы с очередью . Требования, поступившие в систему и не принятые немедленно к обслуживанию, накапливаются в очереди. Если каналы свободны, то заявка обслуживается. Если же все каналы заняты в момент поступления заявки, то очередная заявка будет обслужена после завершения обслуживания предыдущей. Такая система называется полнодоступной (с неограниченной очередью).

Существуют системы с автономным обслуживанием, когда обслуживание начинается в определенные моменты времени;

Системы с ограниченной очередью . (ремонт в гараже)

Системы с отказами . Все заявки, прибывшие в момент обслуживания заявки, получают отказ. (ГТС)

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

2. По количеству каналов обслуживания СМО подразделяются на следующие группы.

Одноканальные СМО.

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

3. По кругу обслуживаемых объектов различают два вида.

Замкнутые СМО. Замкнутая система массового обслуживания - это система массового обслуживания, в которой обслуженные требования могут возвращаться в систему и вновь поступать на обслуживание. Примерами замкнутой СМО являются ремонтные мастерские, сберегательные банки.

Открытые СМО.

4. По количеству этапов обслуживания различают однофазные и многофазные СМО.

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

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

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

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

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

По количеству обслуживающих приборов СМО делятся на одноканальные и многоканальные (рис. 2.1.).

Рис. 2.1. а – одноканальная СМО; б – многоканальная СМО

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

Сеть массового обслуживания задается следующим набором параметров:

параметрами источника заявок;
структурой, определяющей конфигурацию связей и вероятности передачи заявок между узлами сети;
параметрами узлов сети (систем массового обслуживания): дисциплиной обслуживания, числом одинаковых обслуживающих аппаратов (каналов) в каждом узле, распределением длительности обслуживания заявок в каждом узле сети.

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

загрузку – среднее по времени число заявок, обслуживаемых сетью, и одновременно среднее число каналов, занятых обслуживанием;
число заявок, ожидающих обслуживания в сети;
число заявок, находящихся в сети (в состоянии ожидания и обслуживания);
суммарное время ожидания заявки в сети;
суммарное время пребывания заявки в сети.

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

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

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

Рис. 2.2. Разомкнутая (а) и замкнутая (б) стохастические сети

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

Рассмотрим ряд частных типов сетевых моделей, используемых для воспроизведения различных сторон функционирования ВС.

ВНИМАНИЕ!!! Этот раздел будет состоять из нескольких страниц, остальные из которых в данный момент находится в стадии написания. Но уже написанная часть достаточно интересная, поэтому я считаю, что будет полезно уже сейчас сделать её доступной читателям

Давно-давно, когда мы были студентами, этот раздел математики у нас выпил немало студенческой крови. А между тем, этот раздел чрезвычайно интересный!

Моделирование СМО — для тех, кто уже всё знает.

Датский инженер Агнер Эрланг работал в телефонной компании и занялся в начале XX в. рассчётами, касающимися работы телефонной станции: какая доля попыток позвонить не будет успешной, т.к. заняты все линии, сколько нужно иметь линий связи, если абоненты могут дожидаться освобождения линии или если будут прекращать попытку. В технике фамилия датского инженера осталась в виде единицы измерения абонентской нагрузки Эрланг (Эрл ).

1 Эрл - это занятие одной телефонной линии в течение 1 часа.

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

Я не ставлю себе целью написать целый учебник по ТМО. Такого роду материалов в интернете много. «Изюминкой» моей статьи должен стать интерактивный онлайн-расчётник, который позволит менять исходные данные и смотреть, как будет меняться поведение системы.

Главные понятия Теории:

Система массового обслуживания (СМО) объект, принимающий заявки и осуществляющий их обслуживание. Для обслуживания в состав СМО может входить один или несколько приборов Сеть массового обслуживания (СеМО) несколько СМО, между которыми заявки циркулируют. Заявка поступает в какую-либо СМО сети, а получив обслуживание, может поступить в другую СМО сети либо покинуть её. Заявка объект, поступающий в СМО и требующий обслуживания. Также может называться требованием, запросом или как-то ещё. Прибор часть СМО, которая осуществляет обслуживание заявки. Также может называться обслуживающим устройством, каналом, либо это может быть работник или целая бригада. Очередь множество заявок, поступивших в СМО, обслуживание которых ещё не началось по причине занятости всех приборов в системе. Накопитель Часть СМО, в которой содержится очередь.

Исходные данные для рассчётов в ТМО

λ - интенсивность потока заявок среднее количество заявок, поступающих в систему в течение заданного количества времени. Единица измерения - заявок в час (час -1) μ - интенсивность обслуживания среднее количество заявок, которое прибор может обслужить в течение заданного количества времени. Единица измерения - заявок в час (час -1) n - количество обслуживающих приборов количество приборов в составе СМО, каждый из которых может обслуживать заявки. Поступающая заявка обслуживается в любом свободном приборе, т.е. все приборы работают параллельно. Характер потока заявок и обслуживания По своей сути, закон распределения случайной величины времени между поступлением заявок (если речь идёт о потоке заявок) или продолжительности обслуживания конкретной заявки (если речь идёт об интенсивности обслуживания). Может иметь экспоненциальное, нормальное, равномерное или ещё какое угодно распределение. Поток заявок может вообще иметь детерминированный характер (по расписанию), а продолжительность обслуживания может быть и константной m - Размер накопителя Размером накопителя определяется характер СМО: при нулевом размере заявка получает отказ в обслуживании при отсутствии свободных приборов. Если накопитель бесконечный, все заявки будут ожидать обслуживания по мере освобождения приборов. Если же размер накопителя конечный, то при наличии свободных мест заявка помещается в очередь, а при заполнении накопителя заявка получает отказ в обслуживании

Основные показатели работы СМО

ρ - коэффициент загрузки отношение интенсивности потока заявок к суммарной интенсивности обслужвания. Коэффициент загрузки позволяет определить, будет ли система справляться с задачами или из-за перегрузки будет неработоспособной. Вероятность наличия в системе n заявок, вероятность простоя системы наибольшее количество задач ТМО требует найти оптимальное количество обслуживающих приборов или размер накопителя. Вероятность и среднее время ожидания доля заявок, которые попадают в очередь, среднее время пребывания заявок в ожидании начала обслуживания Вероятность отказа доля заявок, получающих отказ в обслуживании. Неактуально для систем с бесконечным накопителем.

Какие задачи позволяет решать ТМО?

Вот несколько типичных задач, которые могут быть решены с применением аппарата теории массового обслуживания. На этой странице скоро появится расчётник, который позволит найти решение этих задач.

Классическая задача. Справочная служба имеет многолинейный телефонный номер, в среднем разговор оператора с абонентом длится 3 минуты, а в течение суток поступает 600 звонков. Сколько нужно иметь телефонных линий (и посадить операторов), чтобы не более 2% звонков оставались без ответа по причине занятости всех линий? А если звонков будет 300 или 1400 в течение суток?
В терминах ТМО задача звучит так:
- λ = 25 звонков в час (600 звонков поделить на 24 часа)
- μ = 20 звонков в час (60 минут поделить на 3)
- m = 0 (при занятости всех линий звонящий абонент услышит гудки «занято»)
- Найти n , при условии, что вероятность отказа 2%
В резервуар водонапорной башни железнодорожной станции непрерывно поступает вода - по кубометру воды за 3 минуты. От водонапорной башни воду получают три гидроколонки для снабжения паровозов водой. На каждую колонку заезжает паровоз в среднем раз в 2 часа и берёт от 10 до 30 кубометров воды (количество воды равномерно распределено в указанном диапазоне). При переполнении резервуара вода вытекает из переливной трубы, чего желательно избегать. Какой объём резервуара требуется водонапорной башне?
В терминах ТМО задача звучит так:
- λ = 20 м 3 в час
- μ = 10 м 3 в час (математическое ожидание разового расхода 20 м
- n = 2 - количество каналов обслуживания (гидроколонок)
- Найти m - размер накопителя, т.е. резервуара при условии нулевой вероятности отказа

В кассу вокзала приходит в среднем по 200 человек в час. Каждого будущего пассажира кассир обслуживает в среднем 4 минуты. Сколько должно работать касс, чтобы касса успевала обслужить каждого желающего? А сколько должно работать касс, чтобы люди стояли в очереди не более 20 минут?

В терминах ТМО:

λ = 200 человек в час
μ = 15 человек в час (60 минут поделить на 4)
m = ∞ , т.е. в очереди может быть бесконечно много людей
Найти n , при котором S имеет конечную величину

Пора уже что-то посчитать!

Вычислительные мощности, доступные каждому в XXI веке колоссальны, и позволяют легко и непринуждённо проводить ресурсоёмкий расчёт - имитационное моделирование . В таблице ниже осуществляется моделирование простенькой одиночной системы массового обслуживания. Можно изменять любые из исходных данных и наблюдать, как система отзывается. Можно, например, увеличить интенсивность потока заявок и наблюдать, как система будет «утопать» в заявках (или увеличится поток отказов, если размер накопителя конечен). А вслед за этим можно увеличить количество приборов в системе и наблюдать, как показатели работы придут в норму. В этом расчёте предельная длина очереди равна 1000. Для большинства применений это можно считать бесконечно большим накопителем, однако следует помнить, что если в накопителе окажется больше тысячи заявок, расчёт будет некорректным.

Параметр	Величина	Пояснение
Исходные данные
λ		в час - Интенсивность потока заявок
P μ (t)	Эксп. Эрл.	Закон распределения времени обслуживания: экспоненциальный .
μ		в час - Интенсивность потока обслуживания (каждым прибором)
k		Масштабный коэффициент
25% за минут 50% за минут 99% за минут 50% в интервале минут 95% в интервале минут
n		Количество каналов обслуживания (не более 50)
Результаты моделирования (на момент)
t		Время моделирования
t		Время моделирования
S		Состояние СМО, т.е. количество заявок на обслуживании + в накопителе
S-n		Длина очереди
Статистика , показатели работы системы
—		Количество поступивших заявок
p 0		Вероятность простоя СМО
P 1-n		Загруженность обслуживающих приборов
S MAX		Максимальное количество заявок в системе за время моделирования
p W		Вероятность ожидания
T W		Среднее время ожидания, мин.
T Wmax		Максимальное время ожидания, мин.
P n	Распределение вероятностей пребывания СМО в различных состояниях
T W	Распределение времени ожидания в очереди

Если интересно, см. математической модели в этой таблице. Даже такая модель позволяет делать интересные наблюдения. Например, можно сравнить несколько СМО с одинаковой производительностью μ×n, обслуживающих одинаковый поток заявок λ, но содержащих различное количество обслуживающих приборов n. В зависимости от того, стремимся ли мы сократить количество обслуживающих аппаратов или же вероятность ожидания, выгодным будет либо наличие одного высокопроизводительного прибора, или десятка низкопроизводительных. Также видно, что среднее арифметическое времени ожидания - величина коварная. Надо будет сделать расчёт медианной величины...

См. также:

Моделирование системы массового обслуживания — более серьёзный расчёт с более гибко регулируемыми параметрами

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

Аналитическая модель сети представляет собой совокупность математических соотношений, связывающих между собой входные и выходные характеристики сети. При выводе таких соотношений приходится пренебрегать какими-то малосущественными деталями или обстоятельствами .

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

где – время распространения, время обслуживания и время ожидания соответственно. Одной из задач аналитического моделирования является определение среднего значения D. При больших загрузках основной вклад дает ожидание обслуживания IV. Для описания очередей в дальнейшем будет использована нотация Д. Дж. Кенделла:

где А – процесс прибытия; В – процесс обслуживания; С – число серверов (узлов); К – максимальный размер очереди (по умолчанию – ∞);

in – число клиентов (по умолчанию – да); z – схема работы буфера (по умолчанию FIFO).

Буквы А и В представляют процессы прихода и обслуживания и обычно заменяются следующими буквами, характеризующими закон, соответствующий распределению событий:

Наиболее распространенными схемами работы буферов являются

FIFO (First-In-First-Out), LIFO (Last-In-First-Out) и FIRO (First-In- Random-Out). Например, запись M/M/2 означает очередь, для которой времена прихода и обслуживания имеют экспоненциальное распределение, имеется два сервера, длина очереди и число клиентов могут быть сколь угодно большими, а буфер работает по схеме FIFO .

Среднее значение длины очереди Q при заданной средней входной частоте сообщений λ и среднем времени ожидания W определяется на основе теоремы Литла (1961) :

Для варианта очереди M/G/ 1 входной процесс характеризуется распределением Пуассона со скоростью поступления сообщений λ. Вероятность поступления к сообщений на вход за время t равно:

(3.3)

Пусть N – число клиентов в системе, Q – число клиентов в очереди и пусть вероятность того, что входящий клиент обнаружит j других клиентов, равна:

Тогда среднее время ожидания:

где σ – среднеквадратичное отклонение для распределения времени обслуживания.

Для варианта очереди(Η – функция

распределения времени обслуживания). Откуда следует.

Для варианта очереди M/D/ 1 время обслуживания постоянно, а среднее время ожидания составляет:

Рассмотрим вариант сети Ethernet на основе концентратора- переключателя с числом каналов N. При этом будет предполагаться, что сообщения на входе всех узлов имеют пуассоновское распределение со средней интенсивностью, распределение сообщений по длине произвольно. Сообщения отправляются в том же порядке, в котором они прибыли. Трафик в сети предполагается симметричным. Очередь имеет модель. Среднее время ожидания в этом случае равно:

где

(3.9)

где, аравно вероятности того, что сообщение отправителя /" направлено получателю. Требование стабильности требует, чтобы. Для бо́льших n это приводит к

Работа сети Ethernet характеризуется рядом параметров, к числу которых относятся вероятность захвата канала и эффективность . Первый параметр определяется по выражению

где Ρ – вероятность того, что ровно одна станция попытается передать кадр в течение такта и захватить канал; Q – число станций, пытающихся захватить канал для передачи кадра данных.

Эффективность LAN Ethernet определяется следующим образом. Общее время работы сети Ethernet делится между интервалами передачи и интервалами конкуренции. Для передачи кадра данных требуется L/C секунд, где L – длина кадра в битах, С – скорость передачи данных в бит/сек. Среднее время Τ , необходимое на захват канала, равно:

где W – среднее число тактов, прошедших в интервале конкуренции, пока станция не захватит канал для передачи кадра данных; В – длительность такта или время до обнаружения конфликта после начала передачи кадра.

Среднее число тактов W рассчитывается следующим образом:

С учетом введенных показателей эффективность Ε работы локальной сети Ethernet определяется следующим образом:

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

1. Одноканальные СМО с ожиданием. Представляют собой один обслуживающий прибор с бесконечной очередью. Данная СМО является наиболее распространенной при моделировании. С той или иной долей приближения с ее помощью можно моделировать практически любой узел ЛВС.
2. Одноканальные СМО с потерями. Представляют собой один обслуживающий прибор с конечным числом мест в очереди. Если число заявок превышает число мест в очереди, то лишние заявки теряются. Этот тип СМО может быть использован при моделировании каналов передачи в ЛВС.
3. Многоканальные СМО с ожиданием. Представляют собой несколько параллельно работающих обслуживающих приборов с общей бесконечной очередью. Данный тип СМО часто используется при моделировании групп абонентских терминалов ЛВС, работающих в диалоговом режиме.
4. Многоканальные СМО с потерями. Представляют собой несколько параллельно работающих обслуживающих приборов с общей очередью, число мест в которой ограничено. Эти СМО, как и одноканальные с потерями, часто используются для моделирования каналов связи в ЛВС.
5. Одноканальные СМО с групповым поступлением заявок. Представляют собой один обслуживающий прибор с бесконечной очередью. Перед обслуживанием заявки группируются в пакеты по определенному правилу.
6. Одноканальные СМО с групповым обслуживанием заявок. Представляют собой один обслуживающий прибор с бесконечной очередью. Заявки обслуживаются пакетами, составляемыми по определенному правилу. Последние два типа СМО могут использоваться для моделирования таких узлов ЛВС, как центры (узлы) коммутации.

Локальная вычислительная сеть в целом может быть представлена в виде сети массового обслуживания. Различают открытые , замкнутые и смешанные сети.

Открытой называется есть массового обслуживания, состоящая из Μ узлов, причем хотя бы в один из узлов сети поступает извне входящий поток заявок и имеется сток заявок из сети. Для открытых сетей характерно то, что интенсивность поступления заявок в сеть не зависит от состояния сети, т. е. от числа заявок, уже поступивших в сеть. Открытые сети используются для моделирования ЛВС, работающих в неоперативном режиме. Каждая заявка поступает на вход соответствующего узла коммутации, где определяется место ее обработки. Затем заявка передается на "свой" сервер или по каналу связи – на "соседний", где обрабатывается, после чего возвращается к источнику и покидает сеть .

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

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

Абоненты с терминалов посылают запросы, которые по каналам связи поступают на узлы коммутации, а оттуда – на обработку на "свой" или "соседний" сервер. Дальнейшая обработка осуществляется так же, как в открытой сети .

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

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

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

Различают экспоненциальные и неэкспоненциальные модели ЛВС. Экспоненциальные модели основаны на предположении о том, что потоки заявок, поступающие в ЛВС, являются пуассоновскими, а время обслуживания в узлах ЛВС имеет экспоненциальное распределение.

Для таких сетей получены точные методы для определения их характеристик; трудоемкость получения решения зависит в основном от размерности сети .

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

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

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

Применение диффузионной аппроксимации при анализе ЛВС основано на следующем:

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

Постановка задачи анализа ЛВС при этом примет следующий вид. Дано:

число узлов ЛВС;
тип каждого узла ЛВС (тип СМО, моделирующей данный узел);
дисциплина обслуживания в каждом узле ЛВС;
общее число типов источников заявок, работающих в диалоговом режиме;
общее число типов источников заявок, работающих в неоперативном режиме;
для диалоговых источников в случае сложного режима работы число технологических процессов каждого типа, число операций в каждом технологическом процессе, среднее и ΚΚΒ времени выполнения каждой операции, матрица вероятностей передач между операциями, а также наличие или отсутствие на каждой операции обращения к ЛВС;
для диалоговых источников в случае простого режима работы число источников (терминалов) каждого типа, среднее и ΚΚΒ времени реакции абонента на ответ сети;
для неоперативных абонентов – средняя интенсивность поступления заявок и ΚΚΒ времени между поступлениями заявок; по каждому типу заявок (диалоговому и неоперативному) средняя интенсивность обслуживания в каждом узле ЛВС, ΚΚΒ времени обслуживания в узлах ЛВС и матрица вероятностей передач между узлами. Требуется найти:
среднее значение и дисперсию (или стандартное отклонение) времени задержки заявки каждого типа в ЛВС в целом;
среднее значение и дисперсию (или стандартное отклонение) времени задержки в узлах ЛВС;
загрузку узлов ЛВС;
вероятность потери заявки в узле ЛВС (для узлов, моделируемых СМО с потерями).

Ограничения могут быть следующими:

вероятность потери заявки не должна превышать 1;

все характеристики должны быть положительны.

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

Рассмотренный в предыдущей лекции марковский случайный процесс с дискретными состояниями и непрерывным временем имеет место в системах массового обслуживания (СМО).

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

Примерами систем массового обслуживания могут служить:

расчетно-кассовые узлы в банках, на предприятиях;
персональные компьютеры, обслуживающие поступающие заявки или требования на решение тех или иных задач;
станции технического обслуживания автомобилей; АЗС;
аудиторские фирмы;
отделы налоговых инспекций, занимающиеся приёмкой и проверкой текущей отчетности предприятий;
телефонные станции и т. д.

	Узлы	Требования

Больница	Санитары	Пациенты
Производство
Аэропорт	Выходы на взлетно-посадочные полосы Пункты регистрации	Пассажиры

Рассмотрим схему работы СМО (рис. 1). Система состоит из генератора заявок, диспетчера и узла обслуживания, узла учета отказов (терминатора, уничтожителя заявок). Узел обслуживания в общем случае может иметь несколько каналов обслуживания.

Рис. 1

Генератор заявок – объект, порождающий заявки: улица, цех с установленными агрегатами. На вход поступает поток заявок (поток покупателей в магазин, поток сломавшихся агрегатов (машин, станков) на ремонт, поток посетителей в гардероб, поток машин на АЗС и т. д.).
Диспетчер – человек или устройство, которое знает, что делать с заявкой. Узел, регулирующий и направляющий заявки к каналам обслуживания. Диспетчер:

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

Очередь – накопитель заявок. Очередь может отсутствовать.
Узел обслуживания состоит из конечного числа каналов обслуживания. Каждый канал имеет 3 состояния: свободен, занят, не работает. Если все каналы заняты, то можно придумать стратегию, кому передавать заявку.
Отказ от обслуживания наступает, если все каналы заняты (некоторые в том числе могут не работать).

Кроме этих основных элементов в СМО в некоторых источниках выделяются также следующие составляющие:

терминатор – уничтожитель трансактов;

склад – накопитель ресурсов и готовой продукции;

счет бухгалтерского учета – для выполнения операций типа «проводка»;

менеджер – распорядитель ресурсов;

Классификация СМО

Первое деление (по наличию очередей):

СМО с отказами;
СМО с очередью.

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

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

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

Итак, например, рассматриваются следующие СМО:

СМО с нетерпеливыми заявками (длина очереди и время обслуживания ограничено);
СМО с обслуживанием с приоритетом, т. е. некоторые заявки обслуживаются вне очереди и т. д.

Типы ограничения очереди могут быть комбинированными.

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

Естественно, поток заявок, порожденный самой системой, будет зависеть от системы и ее состояния.

Кроме этого СМО делятся на открытые СМО и замкнутые СМО.

В открытой СМО характеристики потока заявок не зависят от того, в каком состоянии сама СМО (сколько каналов занято). В замкнутой СМО – зависят. Например, если один рабочий обслуживает группу станков, время от времени требующих наладки, то интенсивность потока «требований» со стороны станков зависит от того, сколько их уже исправно и ждет наладки.

Пример замкнутой системы: выдача кассиром зарплаты на предприятии.

По количеству каналов СМО делятся на:

одноканальные;
многоканальные.

Характеристики системы массового обслуживания

Основными характеристиками системы массового обслуживания любого вида являются:

входной поток поступающих требований или заявок на обслуживание;
дисциплина очереди;
механизм обслуживания.

Входной поток требований

Для описания входного потока требуется задать вероятностный закон, определяющий последовательность моментов поступления требований на обслуживание, и указать количество таких требований в каждом очередном поступлении. При этом, как правило, оперируют понятием «вероятностное распределение моментов поступления требований». Здесь могут поступать как единичные, так и групповые требования (количество таких требований в каждом очередном поступлении ). В последнем случае обычно речь идет о системе обслуживания с параллельно-групповым обслуживанием.

А i – время поступления между требованиями – независимые одинаково распределенные случайные величины;

E(A) – среднее (МО) время поступления;

λ=1/E(A) – интенсивность поступления требований;

Характеристики входного потока:

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

Дисциплина очереди

Очередь – совокупность требований, ожидающих обслуживания.

Очередь имеет имя.

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

первым пришел – первый обслуживаешься;

first in first out (FIFO)

самый распространенный тип очереди.

Какая структура данных подойдет для описания такой очереди? Массив плох (ограничен). Можно использовать структуру типа СПИСОК.

Список имеет начало и конец. Список состоит из записей. Запись – это ячейка списка. Заявка поступает в конец списка, а выбирается на обслуживание из начала списка. Запись состоит из характеристики заявки и ссылки (указатель, за кем стоит). Кроме этого, если очередь с ограничением на время ожидания, то еще должно быть указано предельное время ожидания.

Вы как программисты должны уметь делать списки двусторонние, односторонние.

Действия со списком:

вставить в хвост;
взять из начала;
удалить из списка по истечении времени ожидания.
пришел последним - обслуживаешься первым LIFO (обойма для патронов, тупик на железнодорожной станции, зашел в набитый вагон).

Структура, известная как СТЕК. Может быть описан структурой массив или список;

случайный отбор заявок;
отбор заявок по критерию приоритетности.

Каждая заявка характеризуется помимо прочего уровнем приоритета и при поступлении помещается не в хвост очереди, а в конец своей приоритетной группы. Диспетчер осуществляет сортировку по приоритету.

Характеристики очереди

ограничение времени ожидания момента наступления обслуживания (имеет место очередь с ограниченным временем ожидания обслуживания, что ассоциируется с понятием «допустимая длина очереди»);
длина очереди.

Механизм обслуживания

Механизм обслуживания определяется характеристиками самой процедуры обслуживания и структурой обслуживающей системы. К характеристикам процедуры обслуживания относятся:

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

Для аналитического описания характеристик процедуры обслуживания оперируют понятием «вероятностное распределение времени обслуживания требований».

S i – время обслуживания i -го требования;

E(S) – среднее время обслуживания;

μ=1/E(S) – скорость обслуживания требований.

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

Коэффициент использования СМО

N ·μ – скорость обслуживания в системе, когда заняты все устройства обслуживания.

ρ=λ/(N μ) – называется коэффициентом использования СМО , показывает, насколько задействованы ресурсы системы.

Структура обслуживающей системы

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

Пример. Кассы в магазине.

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

Пример. Медицинская комиссия.

Комбинированное обслуживание – обслуживание вкладов в сберкассе: сначала контролер, потом кассир. Как правило, 2 контролера на одного кассира.

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

вероятностным распределением моментов поступлений заявок на обслуживание (единичных или групповых);
мощностью источника требований;
вероятностным распределением времени продолжительности обслуживания;
конфигурацией обслуживающей системы (параллельное, последовательное или параллельно-последовательное обслуживание);
количеством и производительностью обслуживающих каналов;
дисциплиной очереди.

Основные критерии эффективности функционирования СМО

В качестве основных критериев эффективности функционирования систем массового обслуживания в зависимости от характера решаемой задачи могут выступать:

вероятность немедленного обслуживания поступившей заявки (Р обсл =К обс /К пост);
вероятность отказа в обслуживании поступившей заявки (P отк =К отк /К пост);

Очевидно, что Р обсл + P отк =1.

Потоки, задержки, обслуживание. Формула Поллачека–Хинчина

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

D i – задержка в очереди требования i ;

W i =D i +S i – время нахождения в системе требования i .

(с вероятностью 1) – установившаяся средняя задержка требования в очереди;

(с вероятностью 1) – установившееся среднее время нахождения требования в СМО (waiting).

Q(t) – число требований в очереди в момент времени t;

L(t) – число требований в системе в момент времени t (Q(t) плюс число требований, которые находятся на обслуживании в момент времени t.

Тогда показатели (если существуют)

(с вероятностью 1) – установившееся среднее по времени число требований в очереди;

(с вероятностью 1) – установившееся среднее по времени число требований в системе.

Заметим, что ρ<1 – обязательное условие существования d, w, Q и L в системе массового обслуживания.

Если вспомнить, что ρ= λ/(N μ), то видно, что если интенсивность поступления заявок больше, чем N μ, то ρ>1 и естественно, что система не сможет справиться с таким потоком заявок, а следовательно, нельзя говорить о величинах d, w, Q и L.

К наиболее общим и нужным результатам для систем массового обслуживания относятся уравнения сохранения

Следует обратить внимание, что упомянутые выше критерии оценки работы системы могут быть аналитически вычислены для систем массового обслуживания M/M/N (N >1), т. е. систем с Марковскими потоками заявок и обслуживания. Для М/G/ l при любом распределении G и для некоторых других систем. Вообще распределение времени между поступлениями, распределение времени обслуживания или обеих этих величин должно быть экспоненциальным (или разновидностью экспоненциального распределения Эрланга k-го порядка), чтобы аналитическое решение стало возможным.

Кроме этого можно также говорить о таких характеристиках, как:

абсолютная пропускная способность системы – А=Р обсл *λ;
относительная пропускная способность системы –

Еще один интересный (и наглядный) пример аналитического решения – вычисление установившейся средней задержки в очереди для системы массового обслуживания M/G/ 1 по формуле:

В России эта формула известна как формула Поллачека– Хинчина, за рубежом эта формула связывается с именем Росса (Ross).

Таким образом, если E(S) имеет большее значение, тогда перегрузка (в данном случае измеряемая как d ) будет большей; чего и следовало ожидать. По формуле можно обнаружить и менее очевидный факт: перегрузка также увеличивается, когда изменчивость распределения времени обслуживания возрастает, даже если среднее время обслуживания остается прежним. Интуитивно это можно объяснить так: дисперсия случайной величины времени обслуживания может принять большое значение (поскольку она должна быть положительной), т. е. единственное устройство обслуживания будет занято длительное время, что приведет к увеличению очереди.

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

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