Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

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

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

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

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

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

Функционирование СМО представляется как процесс прохождения заявок через систему. Правило, по которому заявки поступают из очередей на обслуживание в ОА, называется дисциплиной обслуживания, а величина преимущественного права на обслуживания – приоритетом. Для каждого приоритета на входе ОА образуется своя очередь. Если заявка поступает на вход ОА, занятого обслуживанием заявки с более низким приоритетом, то возможно прерывание ранее начатого обслуживания – такой приоритет называется абсолютным. Если прерывания ранее начатого обслуживания не происходит – приоритет относительный.

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

Классификационное обозначение СМО имеет вид A/B/C/D/E, где позиции, обозначенные буквами, означают следующие характеристики:

A – обозначение закона распределения времени поступления заявок входного потока (обозначение М соответствует экспоненциальному закону распределения, Г – гамма-распределению, Е – распределению Эрланга, Н – гиперэкспоненциальному распределению, N – нормальному распределению, R – равномерному распределению, D – постоянному времени обслуживания, G – произвольному или неизвестному закону распределения, Gr – групповому (пакетному) поступлению заявок на обслуживание);

B – обозначение закона распределения времени обслуживания в устройствах (используются те же обозначения, что и для распределения времени поступления заявок);

C – число ОА;

D – число мест в очереди (для неограниченных опускается);

E – дисциплина обслуживания: для дисциплины FIFO данное обозначение опускается; также используются обозначения LIFO, RANDOM, SF (Short Forward – «короткие вперед» – в первую очередь обслуживаются те заявки из очереди, которые требуют меньшего времени обслуживания).

Примеры обозначений:

- М/М/1: СМО с одним ОА, бесконечной очередью, экспоненциальными законами распределения интервалов времени между поступлениями заявок и времени обслуживания, дисциплиной обслуживания FIFO;

- Е/Н/m/r/LIFO: СМО с m обслуживающими аппаратами, очередью, ограниченной r местами, эрланговским законом распределения интервалов между поступлениями заявок, гиперэкспоненциальным распределением времени обслуживания в ОА, дисциплиной обслуживания LIFO.

Если СМО в дополнение к перечисленным характеристикам обладает какими-либо особенностями, последние добавляются к обозначению в качестве комментария (например, СМО типа G/G/1 с ненадежным ОА и временем ожидания в очереди, ограниченным 3,5 секундами).

Для моделирования ВС наиболее часто используются комбинации типов СМО, приведенные в таблице 8.

Таблица 8

Наименование Обозначение Графическое обозначение Описание
Одноканальная СМО с ожиданием G/G/1 Один ОА с бесконечной очередью. С той или иной долей приближения моделирует любой узел или процесс ВС, например механизм разделения среды протокола Ethernet.
Одноканальная СМО с потерями G/G/1/r Один ОА с конечным числом мест в очереди. Если число заявок превышает число мест в очереди, то лишние заявки теряются. Используется при моделировании каналов передачи в ВС.
Многоканальная СМО с ожиданием G/G/m Несколько параллельно работающих ОА с общей бесконечной очередью. Используется при моделировании групп абонентских терминалов ВС, работающих в диалоговом режиме.
Многоканальная СМО с потерями G/G/m/r Несколько параллельно работающих ОА с общей очередью, число мест в которой ограничено. Используются для моделирования каналов связи в ВС.
Одноканальная СМО с групповым поступлением заявок Gr/G/1 Один ОА с бесконечной очередью. Перед обслуживанием заявки группируются в пакеты по определенному правилу. Используется для моделирования узлов коммутации.
Одноканальная СМО с групповым обслуживанием заявок G/Gr/1 Один ОА с бесконечной очередью. Заявки обслуживаются пакетами, составляемыми по определенному правилу. Используется для моделирования узлов коммутации.

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

К основным операционным характеристикам относятся:

Q(t) – длина очереди в момент времени t, т. е. число заявок, ожидающих обслуживания с учетом или без тех заявок, обслуживание которых уже началось;

Qn – длина очереди на n –й стадии, при этом предполагается, что стадии реализуются в дискретном режиме и определяются теми или иными событиями (например, появлением запроса на обслуживание, или выбытием заявки из системы);

W(t) – виртуальная продолжительность ожидания относительно момента времени t, т. е. время ожидания обслуживания для заявки, которое поступит в систему в момент времени t;

Wn – продолжительность периода, в течение которого n -я заявка ожидает обслуживания;

Ti – продолжительность периода занятости системы, начало которого соответствует Q(0)=i, т. е. длина периода занятости системы, начинающегося при наличии в системе i заявок;

In – продолжительность n –го периода простоя системы, т. е. длина интервала, в течении которого система в n –й раз оказывается незанятой.

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

Многие системы массового обслуживания обладают тем свойством, что по истечении определенного времени их поведение в некотором смысле стабилизируется. Формально это выражается в появлении стационарных (периодических) свойств процессов Q(t) и W(t) при t®¥, и Qn, Wn при n®¥. Условия, при которых системы переходят в стационарное состояние, представляют отдельный интерес для исследования.

В соответствии с общей классификацией моделей различают аналитические и имитационные модели СМО.

<== предыдущая лекция | следующая лекция ==>
Рост пленок. Эпитаксия | Вопрос. Задачи оптимизации цепей поставок
Поделиться с друзьями:


Дата добавления: 2014-01-03; Просмотров: 819; Нарушение авторских прав?; Мы поможем в написании вашей работы!


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



studopedia.su - Студопедия (2013 - 2024) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление




Генерация страницы за: 0.019 сек.