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

Содержание

 

Введение 3

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

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

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

Заключение 22

Список использованных источников 23

 

 

 

 

 

 

 

 

 

Введение

 

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

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

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

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

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

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

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

 

 

 

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

 

Типовыми непрерывно- стохастическими Q-схемами являются системы массового обслуживания (СМО) (англ. queueing system).

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

Потоком событий называется последовательность событий, происходящих одно за другим в какие - то случайные моменты времени. Различают потоки однородных и неоднородных событий. Поток событий называется однородным, если он характеризуется только моментами поступления этих событий (вызывающими моментами) и задается последовательностью {tn} = {0 £ t1 £ t2 ... £ tn £ …},где tn – момент наступления n-го события – неотрицательное вещественное число. Однородный поток событий также может быть задан в виде последовательности промежутков времени между n-ми (n – 1)-м событиями {tn}, которая однозначно связана с последовательностью вызывающих моментов {tn}, где tn = tn - tn-1, п ³ 1, t0 = 0, т.е. t1 = t1. Потоком неоднородных событий называется последовательность {tn, fn}, где tn –вызывающие моменты; fn – набор признаков события. Например, применительно к процессу обслуживания для неоднородного потока заявок может быть задана принадлежность к тому или иному источнику заявок, наличие приоритета, возможность обслуживания тем или иным типом канала.

В любом элементарном акте обслуживания можно выделить две основные составляющие: ожидание обслуживания заявкой и собственно обслуживание заявки. Это можно изобразить в виде некоторого i-го прибора обслуживания Пi (рис. 1), состоящего из накопителя заявок Hi, в котором может одновременно находиться ji=0, JiH заявок, где JiH – емкость i-гo накопителя, и канала обслуживания заявок (или просто канала) Ki. На каждый элемент прибора обслуживания Пi поступают потоки событий: в накопитель Hi поток заявок wi, на канал Ki - поток обслуживаний и i.

Заявки, обслуженные каналом Ki, и заявки, покинувшие прибор Пi по различным причинам необслуженными (например, из-за переполнения накопителя Hi), образуют выходной поток yi Î Y, т.е. интервалы времени между моментами выхода заявок образуют подмножество выходных переменных.

 

Рисунок 1. Прибор обслуживания заявок

Обычно, поток заявок wiÎW, т.е. интервалы времени между моментами появления заявок на входе Ki, образует подмножество неуправляемых переменных, а поток обслуживания uiÎU, т.е. интервалы времени между началом и окончанием обслуживания заявки, образует подмножество управляемых переменных.

Процесс функционирования прибора обслуживания Пi, можно представить как процесс изменения состояний его элементов во времени zi(t). Переход в новое состояние для Пi, означает изменение количества заявок, которые в нем находятся (в канале Ki и в накопителе Hi). Таким образом, вектор состояний для Пi, имеет вид  , где ziH - состояние накопителя Hi, (ziH = 0 - накопитель пуст, ziH = 1 – в накопителе имеется одна заявка, ziH = JiH – накопитель полностью заполнен); JiH – емкость накопителя Нi, измеряемая числом заявок, которые в нем могут поместиться; zik – состояние канала Ki (zik=0 – канал свободен, zik = 1 – канал занят).

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

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

Собственными (внутренними) параметрами Q-схемы будут являться количество фаз Jф, количество каналов в каждой фазе Jkj, j =   , количество накопителей каждой фазы JHk, k = , емкость i-го накопителя JiH. Следует отметить, что в теории массового обслуживания в зависимости от емкости накопителя применяют следующую терминологию для систем массового обслуживания:

- системы с потерями (JiH=0, т.е. накопитель в приборе Пi - отсутствует, а имеется только канал обслуживания Кi),

- системы с ожиданием (JiH®¥, т.е. накопитель Нi имеет бесконечную емкость и очередь заявок не ограничивается),

- системы смешанного типа (с ограниченной емкостью накопителя Нi). Всю совокупность собственных параметров Q-схемы обозначим как подмножество Н.

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

В зависимости от динамики приоритетов в Q-схемах различают статические и динамические приоритеты. Статические приоритеты назначаются заранее и не зависят от состояний Q-схемы. Динамические приоритеты возникают при моделировании в зависимости от возникающих ситуаций. Исходя из правил выбора заявок из накопителя Нi на обслуживание каналом Кi, можно выделить относительные и абсолютные приоритеты. Относительный приоритет означает, что заявка с более высоким приоритетом, поступившая в накопитель Нi, ожидает окончания обслуживания предшествующей заявки каналом Ki и только после этого занимает канал. Абсолютный приоритет означает, что заявка с более высоким приоритетом, поступившая в накопитель Hi, прерывает обслуживание каналом Кiзаявки с более низким приоритетом и сама занимает канал (при этом вытесненная из Кi заявка может либо покинуть систему, либо может быть снова записана на какое-то место в Hi).

При рассмотрении алгоритмов функционирования приборов обслуживания Пi(каналов Кi и накопителей Нi) необходимо также задать набор правил, по которым заявки покидают Нi и Кi: для Нi - либо правила переполнения, по которым заявки в зависимости от заполнения Нi покидают систему, либо правила ухода, связанные с истечением времени ожидания заявки в Нi, для Кi — правила выбора маршрутов или направлений ухода. Кроме того, для заявок необходимо задать правила, по которым они остаются в канале Кi или не допускаются до обслуживания каналомКi, т.е. правила блокировок канала. При этом различают блокировки Ki по выходу и по входу. Такие блокировки отражают наличие управляющих связей в Q-схеме, регулирующих поток заявок в зависимости от состояний Q-схемы. Весь набор возможных алгоритмов поведения заявок в Q-схеме можно представить в виде некоторого оператора алгоритмов поведения заявок A.

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

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

 (1)

Где Т - среднее значение интервала между поступлением очередных требований.

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

вероятность   того, что в обслуживающую систему за время t поступит именно k требований:

 (2)

где   - среднее число требований, поступивших на обслуживание в единицу времени.

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

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

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

 (3)

где v - интенсивность обслуживания одного требования одним обслуживающим устройством, которая определяется из соотношения:

 (4)

где  - среднее время обслуживания одного требования одним обслуживающим устройством.

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

   (5)

где n - количество обслуживающих устройств.

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

 (6)

где a - коэффициент загрузки;   - интенсивность поступления требований в систему; v - интенсивность обслуживания одного требования одним обслуживающим устройством.

 (7)

Учитывая, что - интенсивность поступления требований в систему

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