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

Система массового обслуживания

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

Выбор требования из очереди на обслуживание производится с помощью так называемой дисциплины обслуживания. Их примерами являются FCFS/FIFO (пришедший первым обслуживается первым), LCFS/LIFO (пришедший последним обслуживается первым), random (англ.) (случайный выбор). В системах с ожиданием накопитель в общем случае может иметь сложную структуру.

Основные понятия СМО

Требование (заявка) — запрос на обслуживание.

Входящий поток требований — совокупность требований, поступающих в СМО.

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

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

См. также

Литература

Полезное

Смотреть что такое «Система массового обслуживания» в других словарях:

система массового обслуживания — СМО Система, предназначенная для обслуживания случайных потоков вызовов абонентов в сетях связи (рис. Q 3). Общепринятое условное обозначение, используемое для описания систем массового обслуживания, состоит из трех символов A/S/m, где символ А… … Справочник технического переводчика

Система массового обслуживания — [serving system] совокупность пунктов (каналов, станций, приборов), на которые в случайные или неслучайные моменты времени поступают заявки на обслуживание (требования), подлежащие удовлетворению. Примеров таких систем можно привести очень много … Экономико-математический словарь

СИСТЕМА МАССОВОГО ОБСЛУЖИВАНИЯ — математическая модель, созданная для изучения качества работы реальных систем, в которых реализуются последовательности однородных элементарных операций обслуживания. С.м.о. – основной предмет исследования теории массового обслуживания. С.м.о.… … Большой экономический словарь

Многофазная система массового обслуживания — [multis­ta­ge queueing system] система, в которой поступившее требование проходит последовательно несколько этапов обработки. Для анализа таких систем необходимо знать не только длину очереди, время ожидания обслуживания, нагрузку каждого… … Экономико-математический словарь

многофазная система массового обслуживания — Система, в которой поступившее требование проходит последовательно несколько этапов обработки. Для анализа таких систем необходимо знать не только длину очереди, время ожидания обслуживания, нагрузку каждого последовательного звена системы, но и… … Справочник технического переводчика

Многоканальная система массового обслуживания — [mul­ti­channel system] система, в которой поступившее требование может быть обслужено одним из нескольких каналов, входящих в блок обслуживания … Экономико-математический словарь

многоканальная система массового обслуживания — Система, в которой поступившее требование может быть обслужено одним из нескольких каналов, входящих в блок обслуживания. [http://slovar lopatnikov.ru/] Тематики экономика EN multichannel system … Справочник технического переводчика

МАССОВОГО ОБСЛУЖИВАНИЯ СИСТЕМА — с ожиданием многоканальная система массового обслуживания, алгоритм к рой предусматривает накапливание вызовов в очереди, если в момент их прихода система оказалась занятой; при этом обслуживание вызовов ведется в нескольких каналах одновременно … Математическая энциклопедия

МАССОВОГО ОБСЛУЖИВАНИЯ СИСТЕМА — с отказами система массового обслуживания, алгоритм к рой предусматривает выбывание вызовов, в момент прихода к рых все каналы оказались занятыми. Основные определения и обозначения см. в ст. Массового обслуживания система. 1) Естественными… … Математическая энциклопедия

МАССОВОГО ОБСЛУЖИВАНИЯ СИСТЕМА — с ожиданнем и одним каналом обслуживания система массового обслуживания, алгоритм к рой предусматривает, что вызовы, не принятые немедленно к обслуживанию (заставшие систему занятой), накапливаются в очереди; при этом обслуживание следующего… … Математическая энциклопедия

Источник

Тема 6. Системы массового обслуживания (СМО)

Цель

Ознакомить с понятиями:

Оглавление

Понятие СМО

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

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

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

Выходы на взлетно-посадочные полосы

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

Рис. 1

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

first in first out (FIFO)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Заметим, что ρ 1 и естественно, что система не сможет справиться с таким потоком заявок, а следовательно, нельзя говорить о величинах d, w, Q и L.

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

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

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

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

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

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

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

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

Рассмотрим непрерывные марковские цепи, которые характеризуют процессы гибели и размножения. Количество событий соответствует количеству каналов. S₀ – событие «все свободны, нет занятых каналов»; S₁ – один канал занят, и т. д. Таким образом имеем процесс, в котором каждому событию соответствует целое число, которое характеризует количество занятых каналов. Событие заключается в том, что количество занятых каналов может уменьшиться на 1, или увеличиться на 1.

Простейшая одноканальная модель

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

, где λ – интенсивность поступления заявок;

Плотность распределения длительностей обслуживания:

, где μ – интенсивность (скорость) обслуживания.

Потоки заявок и обслуживаний простейшие.

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

Система имеет два состояния:

Переход из состояния S₀ в состояние S₁ происходит с интенсивностью λ, из состояния S₁ в состояние S₀ – с интенсивностью μ.

Возможны два подхода к решению задачи.

1-й путь. С помощью уравнений Колмогорова

Здесь на самом деле только одно уравнение, т. к.

Начальное условие p₀(0)=0– канал свободен.

Линейное неоднородное уравнение 1-го порядка (см. лекцию 2).

Видно, что данное решение имеет стационар

Нетрудно убедиться, что для одноканальной СМО с отказами вероятность Р₀(t) есть не что иное, как относительная пропускная способность системы.

Действительно, Р₀(t) – вероятность того, что в момент t канал свободен и заявка, пришедшая к моменту tt, будет обслужена, а следовательно, для данного момента времени t среднее отношение числа обслуженных заявок к числу поступивших также равно Р₀(t).

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

Абсолютная пропускная способность канала

2-й путь. Статистическое моделирование с использованием метода Монте-Карло.

На практическом занятии рассмотрим этот путь и сравним результаты моделирования с теоретическим решением.

Приложение. Трансакты и их «семейства»

В некоторых программных средах, например, в отечественной системе Pilgrim [2], предназначенных для имитационного моделирования экономических процессов, используется понятие трансакта.

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

Источник

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

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

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

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

Понятие марковского случайного процесса

Под случайным (вероятностным или стохастическим) процессом понимается процесс изменения во времени состояния какой-либо системы в соответствии с вероятностными закономерностями.

Процесс работы СМО представляет собой случайный процесс с дискретными состояниями и непрерывным временем. Это означает, что состояние СМО меняется скачком в случайные моменты появления каких-то событий (например, прихода новой заявки, окончания обслуживания и т.п.).

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

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

Решение. Возможные состояния системы: — оба узла исправны; — первый узел ремонтируется, второй исправен; — второй узел ремонтируется, первый исправен; — оба узла ремонтируются. Граф системы приведен на рис. 1.

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

Потоки событий

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

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

Поток событий называется простейшим (или стационарным пуассоновским ), если он одновременно стационарен, ординарен и не имеет последействия. Название «простейший» объясняется тем, что СМО с простейшими потоками имеет наиболее простое математическое описание. Заметим, что регулярный поток не является «простейшим», так как он обладает последействием: моменты появления событий в таком потоке жестко зафиксированы.

Найдем распределение интервала времени между произвольными двумя соседними событиями простейшего потока.

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

Плотность вероятности случайной величины есть производная ее функции распределения (рис. 3), т.е.

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

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

Для простейшего потока с интенсивностью вероятность попадания на элементарный (малый) отрезок времени хотя бы одного события потока равна согласно (4)

Источник