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

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

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

Что же характеризует эти системы как СМО? Такие системы можно описать, если задать:

1) входящий поток требований или заявок, которые поступают на обслуживание;

2) дисциплину постановки в очередь и выбор из нее;

3) правило, по которому осуществляется обслуживание;

4) выходящий поток требований;

5) режимы работы.

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

где λ - интенсивность потока требований (число требований за еди­ницу времени).

На практике обоснованием того, что входящий поток требова­ний имеет распределение Пуассона, является то, что требования по­ступают от большого числа независимых источников за определен­ный интервал времени. Примерами могут быть вызовы абонентов в телефонной сети, запросы к распределенной базе данных от абонен­тов сети за некоторое время и другие. Для того, чтобы при моделиро­вании задать пуассоновский поток требований в систему, достаточно задать экспоненциальное распределение интервалов времени поступ­ление для соседних требований, графики функций плотности и рас­пределения которых для λ = 1 показаны на рис. 1.1.

Дисциплины постановки в очередь и выбора из нее опреде­ляют порядок постановки требований в очередь, если заняты устрой­ства обслуживания, и порядок выбора из очереди, если освобождает­ся обслуживающее устройство. Простейшая дисциплина допускает постановку в очередь в порядке поступления требований. Такую дис­циплину называют «раньше поступил - раньше обслужился» (РПРО, в англоязычной литературе FIFO - First In-First Out), напри­мер, очередь к телефону-автомату.

Организация очереди по правилу «последний поступил - пер­вый обслужился» (ПППО, в англоязычной литературе LIFO - Last In-First Out) допускает, что на обслуживание выбираются последние требования из очереди. Это правило также называется «стеком» или «магазином».

Правило выбора из очереди может быть случайным (RANDOM).

Возможна также организация выбора из очереди по парамет­рам (например, мужчины в очереди пропускают женщин вперед).

На очередь могут накладываться ограничения по длине очереди или по времени пребывания в ней. Например, если в очереди нахо­дится более трех требований, то новое требование, которое поступи­ло, покидает систему; или, если время пребывания в очереди более двух минут, то требование покидает систему.

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

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

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

Дисциплины обслуживания определяют:

- при каких условиях прекращается обслуживание требований;

- как выбирается для обслуживания следующее требование;

- что делать с частично обслуженным требованием.

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

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

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

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

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

Выходящий поток - это поток требований, которые покидают систему, причем требования в нем могут быть как обслуженные, так и не обслуженные. Структура выходящего потока может иметь боль­шее значение для многофазных систем, где этот поток становится входящим для следующей фазы обслуживания. Распределение требо­ваний в выходящем потоке во времени зависит от плотности входя­щего потока и характеристик работы устройств обслуживания. Из теории массового обслуживания известно, что выходящий поток из СМО с т устройствами с ожиданием при простейшем входящем по­токе с параметром λ и экспоненциальном распределении времени об­служивания с параметром μ есть простейший поток с параметром λ = min{λ,mμ}. Такое замечание дает возможность построить теорию сложных СМО, где выходящий поток из одних систем обслуживания есть входящий в другие системы. Это так называемые многофазные системы и сети СМО. Во всех других случаях распределение выхо­дящих потоков из СМО имеет более сложную вероятностную приро­ду и может изучаться только наблюдениями за функционированием этих СМО с помощью моделирования.

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

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

N = λ T. (1.2)

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