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

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

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

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

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

Источники делятся на: конечные; бесконечные; с ограниченной емко­стью. Конечные источники характеризуются тем, что после формирования очередной заявки они переходят в состояние ожидания возвращения обслужен­ной заявки. В частности, это терминалы информационной системы, которые после формирования задания для выполнения сервером переходят в состояние ожидания ответного сообщения. Бесконечные источники генерируют заявки, не дожидаясь результатов обслуживания. Например, бесконечным ис­точником является общежитие, а заявками - студенты, выходящие из общежи­тия и направляющиеся на обед в столовую. Источники с ограниченной емкостью р характеризуются тем, что они могут независимо сформировать р заявок, а следующую р+1 -ю заявку генерируют только после обслуживания одной из ранее сформированных заявок. Источники классифицируются на: однородные и неоднородные.

Определение 4. Источники являются однородными, если формируе­мые ими заявки имеют одинаковые вероятностные характеристики.

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

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

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

Рис.4

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

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

обслуживание заявок в порядке поступления (first come first served — FCFS). Особенность реализации этой дисциплины в многолинейных системах состоит в том, что для заявки, выбранной на обслуживание, назначение прибора производится случайным образом;

обслуживание заявок в инверсионном порядке (last come first served - LCFS), предполагающее выбор в качестве первоочередной - заявки, поступив­шей в систему последней;

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

обслуживание заявок на основе равномерного разделения приборов (processor sharing - PS), в соответствии с которой каждая из n находящихся в системе заявок обслуживается с одинаковой скоростью 1/ n;

обслуживание на основе циклического алгоритма планирования (round robin - RR).

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

Рис.5

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

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

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

обслуживание по принципу SRT «по наименьшему остающемуся време­ни». Отличие этого принципа от дисциплины SIF состоит в том, что в рассмат­риваемой дисциплине допускается прерывание обслуживания текущей заявки в том случае, если вновь поступившая заявка имеет меньшее оценочное время выполнения;

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

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

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

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

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

Дата добавления: 2014-01-04