Файл: Конспект лекций Для студентов специальности 080801. 65 - приклад.doc

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

N = λ T. (1.2)

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

1.2. Системы с одним устройством обслуживания

Рассмотрим одноканальную (с одним устройством обслужива­ния) СМО, показанную на рис. 1.2.

Если обозначить среднее время пребывания требований в очереди w и рассматривать СМО как очередь q, то, используя формулу Литтла, можно найти среднее количество требований в очереди:

Если обозначить среднее время обслуживания в устройствех и рассматривать СМО как устройство S, то, используя формулу Литтла можно найти среднее количество требований в устройстве:

Всегда имеет место уравнениеT = w+x, где Т - среднее время пребывания требований в СМО с одним устройством обслуживания.

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

Для обозначения СМО используются три параметра для первых трех параметров: X/Y/Z, где X - распределение времени поступления; Y- распределение времени обслуживания; Z- число обслуживаю­щих устройств.

В теории СМО некоторые аналитические решения были получе­ны для систем вида D/D/1, М/М/1 и M/G/1. Для других значений пара­метров систем обслуживания аналитические решения не были получе­ны, то есть эта проблема мотивирует использование моделирования.

Самая известная модель - это так называемая СМО типа М/М/1, где М - марковские процессы распределения времени поступления и обслуживания с одним устройством. Например, в системе М/М/1 время между двумя поступлениями в систему требований и время об­служивания имеют экспоненциальные распределения. Такая СМО иногда используется как модель для одного процессора компьютер­ной системы или как стандартное устройство ввода-вывода (напри­мер, магнитный диск). Система D/D/1 - детерминированная система, тогда как D/M/1 - смешанная. Если о системе мало известно, это обозначается как G/G/m, то есть система с произвольными распределе­ниями и т устройствами.