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

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

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

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

эффективность используемого в системе оборудования.

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

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

Первые задачи ТМО были рассмотрены сотрудником Копенгагенской телефонной компании Агнером Эрлангом в период между 1908 и 1922 годами. Стояла задача упорядочить работу телефонной станции и заранее рассчитать качество обслуживания потребителей в зависимости от числа используемых устройств.

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

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

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

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

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

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

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

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

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

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

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

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

Поэтому аналитическое исследование используют для предварительной оценки различных предлагаемых вариантов систем, а основным подходом к анализу САПР на системном уровне проектирования считают имитационное моделирование.

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

- в СМО используются бесприоритетные дисциплины обслуживания типа FIFO.

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

- времена обслуживания заявок в устройствах выбираются в соответствии с экспоненциальным (показательным) законом распределения. Название потока - пуассоновский - происходит от того, что для этого потока вероятность появления k заявок за интервал t определяется законом Пуассона f(t) = e^-t.

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

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

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

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

Обычно принимается условие: сумма вероятностей перехода из состояния Si состояние Sj равна 0 или ,где   — число состояний. V_ii – вероятность того что система останется в старом состоянии

На рис. 1 приведен пример марковской цепи в виде графа перехода состояний с состояниями  , а в табл. 1 представлена матрица интенсивностей переходов для этого примера.

V_ii – вероятность того что система останется в старом состоянии. V_{11 =}-V₁₂-V₁₃-V₁₄

Таблица 1    

Состояние

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

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

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

(1)

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

Разделив выражение (1) на   и перейдя к пределу при  , получим откуда следуют уравнения Колмогорова

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

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

В стационарном состоянии   и уравнения Колмогорова составляют систему алгебраических уравнений, в которой  -й узел представлен уравнением

(2)

Прибавляя   к левой и правой частям уравнения (2) и учитывая что получаем т.е. где   — финальные вероятности

Пример аналитической модели

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

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

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

Рис. 1.  Пример СМО

S₀ –система свободна, S₁ –пришла первая заявка, S₂ – вторая и т.д.

Матрица интенсивностей представлена в табл. 1. 

Состояние						...
						...
						...
						...
						...
						...
...	...	...	...	...	...	...

Уравнения Колмогорова для установившегося режима имеют вид: и т.д.

Таблица 1    

и т.д.

Здесь введено обозначение  - "приведенная интенсивность" потока заявок. Физический смысл ее таков: величина a представляет собой среднее число заявок, приходящих в СМО за среднее время обслуживания одной заявки. Установившийся режим возможен только при  .

Так как то  (св-ва многочлена)

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

среднюю длину   очереди к ОА

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

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

T_av =N_{av/лямбда ,} среднее время пребывания заяв­ки в очереди равно среднему числу заявок в очереди, деленному на интенсивность потока заявок

T_or =Q_{av/ лямбда ,}

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