1 Модели массового обслуживания




страница1/5
Дата05.05.2016
Размер0.86 Mb.
  1   2   3   4   5

Ф СО ПГУ 7.18.1/02




Министерство образования и науки Республики Казахстан

Павлодарский государственный университет им. С. Торайгырова

Факультет физики, математики и информационных технологий


опорный конспект лекций




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





Павлодар

Ф СО ПГУ 7.18.1/14


УТВЕРЖДАЮ

Декан ФФМиИТ

______________С.К. Тлеукенов

«__»________________200_ г.


Составитель: магистр ИС, старший преподаватель Вихлянова Т.В

(должность, уч. степень, звание, подпись)




Кафедра Информатика и информационные системы




опорный конспект лекций




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

(полное наименование дисциплины по рабочему учебному плану)
для студентов специальности (ей)_ 050703 Информационные системы

(шифр и полное наименование специальности)

Рекомендована на заседании кафедры от «__»______________200_ г.

Протокол №_____


Заведующий кафедрой____________________Нурбекова Ж.К.

(подпись)


Одобрена методическим советом факультета ФФМиИТ

«___»___________200_ г. Протокол №______


Председатель МС_______________________________ Даутова А.З.

(подпись)



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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Распределение Пуассона – распределение вероятностей случайных величин xi, принимающих целые неотрицательные значения k = 0,1,2,…,n с вероятностями [3, 4, 9, 20]



(5.1)

где λ > 0 – параметр.

Математическое ожидание, дисперсия и моменты более высоких порядков равны λ. Сумма независимых случайных величин Xi, имеющих распределение Пуассона с параметрами λi, подчиняется также распределению Пуассона с параметрами ∑λi. Это предельное распределение безгранично делимо: если сумма случайных величин имеет распределение Пуассона, то каждое слагаемое можно представить как распределенное по закону Пуассона.

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

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

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

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

Если поток обладает всеми тремя свойствами, он называется простейшим (пуассоновским).

Время обслуживания (как и время между поступлениями в систему обслуживания), когда поток обслуживания (или поступления в систему) обладает этими тремя свойствами, распределено по экспоненциальному закону

g(t) = μeμt, (5.2)

где μ – параметр, величина, обратная среднему времени обслуживания одной заявки: μ = 1/mt обсл.

Величина λ должна быть меньше, чем μ, иначе очередь будет расти до бесконечности по геометрической прогрессии.

Когда входящий поток – пуассоновский, а время обслуживания распределено по экспоненциальному закону, при одном приборе обслуживания, система обозначается М/М/1. Буква G в обозначении системы массового обслуживания означает произвольное распределение, Ek – распределение Эрланга порядка k, D – детерминированный поток (равные промежутки времени между поступлениями требований в систему или применительно к прибору обслуживания – неслучайное и одинаковое время обслуживания для всех требований). Например, E3/G /2 означает, что входящий поток системы – эрланговский третьего порядка, поток обслуживания имеет произвольное распределение времени обслуживания, число обслуживающих приборов равно двум.

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

Отношение λ/μ = ρ – загрузка системы (коэффициент загрузки).

Расчетные формулы для системы М/М/1 имеют следующий вид:

вероятность того, что обслуживающий прибор свободен,



Р0 =1ρ. (5.3)

среднее число требований в системе (находящихся в очереди и на обслуживании)



E(n) = ρ/(1ρ); (5.4)

среднее время ожидания обслуживания



E(t) = ρ/[μ(1ρ)]; (5.5)

средняя длина очереди, ожидающей обслуживания,



E(no) = ρ2/(1 – ρ); (5.6)

среднее время, проведенное требованием в системе,



E(tc) = 1/[μ(1 – ρ)]. (5.7)

Пример 1. Требования поступают на обслуживающее устройство (в кассу магазина для оплаты покупок) случайно, причем средний промежуток времени между поступлениями требований равен 1,0 мин, среднее время обслуживания – 0,8 мин. Определить: среднее число требований в системе; среднее время ожидания обслуживания; среднюю длину очереди, ожидающей обслуживания; среднее время; проведенное требованием в системе; вероятность отсутствия требований в системе, если она состоит из одного прибора и имеет пуассоновский входящий поток и экспоненциальное время обслуживания (М/М/1).

Решение. Так как средний промежуток времени между поступлениями требований известен: mt пост = 1 мин, то среднее число покупателей, приходящих к кассе для расчета за покупки в течение 1 мин,

λ = 1/mt пост; λ = 1/1 = 1 покупатель/мин.

Поскольку среднее время обслуживания mt обсл = 0,8 мин, то среднее число покупателей, обслуживаемых в 1 мин,

μ = 1/mtобсл ; μ = 1/0,8 = 1,25,

т. е. в среднем кассир обслуживает более одного покупателя в минуту.

Тогда вероятность простоя системы (в данном случае кассы и кассира)



Р0 = 1 – ρ; Р0 = 1 – 0,8 = 0,2,

т. е. 20 % рабочего времени система простаивает.

Среднее число покупателей в системе (стоят в очереди плюс один рассчитывается за покупку)

E(n) = ρ/(1ρ); E(n) = 0,8/(1 – 0,8) = 4 покупателя.

Среднее время ожидания в очереди



E(t) = ρ/μ(1 – ρ); E(t) = 0,8/(1,25·0,2) =3,2 мин.

Средняя длина очереди, ожидающей обслуживания,



E(n0) = ρ2/(1 – ρ); E(n) = 0,82/ (1 – 0,8) = 3,2 покупателя.

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

Среднее время, проведенное покупателем в системе, ожидая сначала в очереди, а потом и собственно своего обслуживания кассиром,

E(tc) = 1/μ(1 – ρ); E(tc) = 1/[1,25·(1 – 0,8)] = 4 мин.

Пример 2. При этих же условиях задачи рассматривается ситуация: добавлен еще один кассовый аппарат с кассиром при тех же условиях: все покупатели стоят в одной очереди и, как только один из кассиров освобождается, первый из стоящих в очереди поступает к нему на обслуживание (т. е. имеет место система М/М/2). Как изменятся первые три основных показателя?

Решение. Вероятность простоя системы

Р0 = (2ρ)/ (2 + ρ); P0 = (2 – 0,8)/(2 + 0,8) = 0,43,

т. е. 43 % рабочего времени кассиры будут простаивать.

Среднее число требований в системе

E(n) = 2ρ/(4ρ2); E(n) = 2·0,8/(4 – 0,82) = 0,48,

т. е. практически очереди нет.

Среднее время ожидания обслуживания

E(t) = ρ2/[μ(4ρ2)]; E(t) = 0,82/ 1,25(4 – 0,82) = 0,15 мин.

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

Модели М/М/m (здесь m – число обслуживающих приборов) можно использовать в любых случаях, нужно только помнить, что они дают завышенные показатели при одних и тех же значениях λ и μ, когда законы распределения величин, формирующих случайные потоки, более упорядочены.


Тема 2 Вероятностные сети систем массового обслуживания
Существует большое множество методов анализа сетей связи, среди которых основу составляют методы математического анализа и имитационного моделирования. В последнее время большой интерес представляет также тензорный метод анализа сетей [1], который можно выделить в отдельную категорию, поскольку идея метода коренным образом отличается от остальных методов. Тензорный метод занимает особую позицию, являясь не похожим на другие методы. Особенностью данного метода является то, что его автор попытался объединить все процессы, происходящие в системе, и взглянуть на систему с более общей точки зрения. Так, при анализе какой-либо сложной сети, необходимо сначала получить результаты для одного элемента данной сети, а затем распространить эти результаты на всю сеть. Более того, введение таких понятий, как «преобразование», «инвариантность» и «группа» приводит к появлению новой математической сущности. Такой сущностью является геометрический объект, который представлен не одной, а бесконечным множеством матриц. Изменение системы координат (топологии сети) приводит к изменению компонентов геометрического объекта (компонентов матриц), при этом сам геометрический объект остается неизменным. Это позволяет рассматривать целый класс сетей как один объект, а переход между ними осуществлять с помощью специальной матрицы перехода.

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

Моделью сетей интегрального обслуживания в данной работе являются сети массового обслуживания двух типов: контурные и ортогональные. Основные результаты по тензорному анализу сетей представлены в [1, 2].

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

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

Рис. 1. Блок-схема системы массового обслуживания

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

GENERATE (Exponential (1,0,T))

TEST L Q$Line1,N, Destroy

QUEUE Line1

SEIZE SMO1

ADVANCE (Exponential (1,0,To))

RELEASE SMO1

DEPART Line1

В данной программе блок GENERATE создает поток транзактов, поступающий на СМО. С помощью блока TEST задается ограничение размера буфера N. Блоки QUEUE и DEPART необходимы для накопления информации о средней длине очереди и времени задержки.

При моделировании сети связи необходимо произвести объединение СМО в соответствии со структурой сети.

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





Рис. 2. Обобщенная блок-схема сети связи

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

Рассмотрим моделирование контурной сети интегрального обслуживания с СМО вида M/M/1/N. Сравнение результатов моделирования будем производить с расчетом характеристик сети с помощью тензорного метода.

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

Для анализа использована сеть, состоящая из 10 систем массового обслуживания. Структура такой сети приведена на рис. 3.



Рис. 3. Структура анализируемой сети

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

Решение системы уравнений [1, 2] дает следующие значения интенсивностей потоков сообщений в ветвях и контурах: , , .

Имитационное моделирование производится на основе заданных интенсивностей потоков сообщений и фиксированных объемов буферов.

Результаты моделирования представлены в таблице 1.

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



Таблица 1

Результаты исследования контурной сети двумя методами

(ТМ – тензорный метод, ИМ – имитационное моделирование,


П – относительная погрешность)

СМО

λ, Эрл

Средние длины очереди

Средние временные задержки, с

ТМ

ТМ

ИМ

П, %

ТМ

ИМ

П, %

1

0,098

1,215

1,214

0,08

12,56

12,567

0,05

2

0,096

1,877

1,876

0,05

19,50

19,503

0,02

3

0,031

0,299

0,298

0,33

10,36

10,350

0,09

4

0,073

1,853

1,827

1,40

25,60

25,221

1,48

5

0,064

5,610

5,598

0,22

90,60

90,764

0,17

6

0,058

4,310

4,295

0,35

73,85

73,871

0,03

7

0,051

1,928

1,921

0,36

36,2

36,116

0,23

8

0,019

2,310

2,295

0,65

89,50

89,843

0,38

9

0,023

3,010

2,989

0,70

114,00

113,02

0,86

10

0,021

1,900

1,885

0,78

77,0

77,784

1,00

Кроме контурных сетей особый интерес представляют ортогональные сети. В данной работе для анализа использована ортогональная сеть, состоящая из 10 систем массового обслуживания с классификацией M/M/1/N. Структура такой сети приведена на рис. 4.





Рис. 4. Структура анализируемой сети

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

Имитационное моделирование производится на основе заданных интенсивностей потоков сообщений и фиксированных объемов буферов. Результаты расчета тензорным методом и методом имитационного моделирования сведены в таблицу 2.

Таблица 2

Сравнение результатов, полученных обоими методами

(П – погрешность)



СМО

Тензорный метод

Имитационное моделирование

Среднее время задержки Ti

Средняя длина очереди Ni

Среднее время задержки Ti

Средняя длина очереди Ni

П δN, %

П δT, %

1

11,3

0,112

11,278

0,113

0,885

0,195

2

54,0

0,773

52,606

0,771

0,259

0,730

3

453,0

2,110

450,547

2,084

1,232

0,542

4

254,3

1,875

259,303

1,847

1,493

1,967

5

270,0

1,870

273,363

1,839

1,658

1,230

6

190,0

1,785

191,983

1,780

0,280

1,033

7

935,0

2,330

925,045

2,366

1,522

1,065

8

276,0

1,240

280,041

1,260

1,587

1,443

9

49,0

0,675

48,886

0,686

1,630

0,233

10

173,0

1,67

173,939

1,667

0,178

0,540

Результаты позволяют сделать очевидные выводы: значения средней длины очереди и среднего времени задержки, полученные тензорным методом и методом имитационного моделирования, практически совпадают с точностью до 2 процентов. При этом средняя погрешность составляет порядка одного процента, а максимальная погрешность не превышает 1,967 %. Максимальная погрешность наблюдается в случае СМО с номером 4, для которой загрузка является наибольшей и составляет 0,725. Значительная погрешность во многом может быть обусловлена формулой расчета вероятности потерь в системе массового обслуживания, неточность которой возрастает при увеличении размера буфера и загрузки СМО.

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

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



  1   2   3   4   5


База данных защищена авторским правом ©ekonoom.ru 2016
обратиться к администрации

    Главная страница