Понятие о системах массового обслуживания (СМО). На практическом занятии рассмотрим этот путь и сравним результаты моделирования с теоретическим решением Сети массового обслуживания и их применение

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

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

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

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

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

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

Основные характеристики СМО

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

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

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

Схема СМО изображена на рисунке 5.1.

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

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

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

СМО явля-ется предметом изучения теории массового обслуживания .

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

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

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

1. Показатели эффективности использования СМО:

1.1. Абсолютная пропускная способность СМО - среднее число заявок, которое сможет обслужить СМО в единицу времени.

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

1.3. Средняя продолжительность периода занятости СМО.

1.4. Коэффициент использования СМО — средняя доля времени, в течение которого СМО занята обслужи-ванием заявок.

2. Показатели качества обслуживания заявок :

2.1. Среднее время ожидания заявки в очереди.

2.2. Среднее время пребывания заявки в СМО.

2.3. Вероятность отказа заявке в обслуживании без ожи-дания.

2.4. Вероятность того, что поступившая заявка немедлен-но будет принята к обслуживанию.

2.5. Закон распределения времени ожидания заявки в очереди.

2.6. Закон распределения времени пребывания заявки в СМО.

2.7. Среднее число заявок, находящихся в очереди.

2.8. Среднее число заявок, находящихся в СМО, и т.п.

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

Случайный характер потока заявок и длительности их об-служивания порождает в СМО случайный процесс . Поскольку моменты времени T i и интервалы времени поступле-ния заявок T , продолжительность операций обслуживания Т обс , про-стоя в очереди T оч , длина очереди l оч — случайные величины, то характеристики состояния систем массового обслуживания носят вероятностный характер. Поэтому для решения задач теории массового обслужива-ния необходимо этот случайный процесс изучить, т.е. постро-ить и проанализировать его математическую модель.

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

Простейший поток обладает тремя основными свойствами : ординарности, стационарности и отсутствия последействия.

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

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

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

Для простейшего потока частота поступления требований в систему подчиняется закону Пуассона , т. е. вероятность по-ступления за время T ровно k требований задается формулой

где λ — интенсивность потока заявок , т. е. среднее число заявок, поступающих в СМО в единицу времени,

где τ — среднее значение интервала времени между двумя со-седними заявками.

Для такого потока заявок время между двумя соседними заяв-ками распределено экспоненциально с плотностью вероятности

Случайное время ожидания в очереди начала обслуживания то-же можно считать распределенным экспоненциально:

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

где Т оч - среднее значение времени ожидания в очереди.

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

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

Важной характеристикой СМО, объединяющей показатели λ и μ , является интенсивность нагрузки, которая показывает степень согласования указанных потоков зая-вок:

Перечисленные показатели k, τ, λ, l оч, Т оч, ν, Т обс, μ, ρ, Р k являются наиболее общими для СМО.

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

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

СеМО классифицируют по нескольким признакам (рис. 2.5).

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

Коэффициент (коэффициент передачи) характеризует долю заявок, поступающих вj -й узел от источника заявок, либо среднее число прохождений заявки через данный узел за время ее нахождения в сети.

Если интенсивности потоков заявок в узлах сети связаны нелинейной зависимостью (например, ), то сеть называется нелинейной.

Сеть всегда линейна, если в ней заявки не теряются и не размножаются.

Рис. 2.5. Классификация СеМО

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

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

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

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

– законом распределения длительности обслуживания в узлах;

– приоритетами;

– маршрутами (путями движения заявок в сети).

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

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

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

– входные потоки СеМО пуассоновские;

– во всех N СМО время обслуживания заявок имеет экспоненциальную функцию распределения вероятностей, заявки обслуживаются в порядке прихода;

– переход заявки с выхода i -й на вход j -й СМО является независимым случайным событием, имеющим вероятность ,;– вероятность ухода заявки изCeМО.

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

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

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

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

5.2.1 Описание сети. Обозначения

Рассмотрим сеть МО, для описания которой будем использовать следующие обозначения:

М - конечное множество узлов сети,

М - число узлов в сети МО,

Номер узла, .

Узлы предполагаются следующих типов:

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

1) бесконечнолинейные;

2) однолинейные с бесконечной емкостью накопителя, инверсионной дисциплиной обслуживания с прерыванием обслуживания и дообслуживанием;

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

Множество узлов типа обозначается а число приборов в узле - .

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

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

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

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

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

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

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

Очевидно, что при таком описании сети объем и длина соответствуют обслуживанию заявки в узле с номером . Напомним, что допускаются маршруты R, в которых номера могут повторяться, т.е. заявка может обслуживаться в одном и том же узле s несколько раз, причем с различными длительностями обслуживания.

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

совместную ФР маршрута и объемов заявки на этапах, через

условную совместную ФР длительностей обслуживания заявки на этапах при фиксированных маршруте и объемах и через

условную ФР длительности обслуживания заявки на этапе (в узле с номером ) при фиксированных маршруте и объемах.

Относительно введенных функций делаются следующие предположения.

(П 1.) Длительности обслуживания предполагаются условно независимыми вдоль маршрута, т.е. условная ФР имеет вид

(П 2.) Экспоненциальные узлы s являются -линейными СМО (с бесконечной емкостью накопителя), интенсивности обслуживания в которых любой заявки каждым прибором равны

Таким образом, если , т.е. на этапе маршрута заявка обслуживается в узле s типа 0, то

Иными словами, длительность обслуживания в узле типа 0 не зависит ни от маршрута R, ни от объемов Y (включая объем ) и имеет экспоненциальное с параметром распределение.

(П 3). Функции распределения не содержат сингулярной компоненты.

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

Кроме того, для узлов типов 1-3 положим

и для сокращения записи результатов обозначим дополнительно через

условные плотности распределения времени окончания (интенсивности) обслуживания заявки с характеристиками на этапе маршрута (в узле ) при условии, что она обслуживалась время Заметим при этом, что если на этапе маршрута заявка обслуживается в экспоненциальном узле с номером (т.е. если ), то

ЛЕКЦИЯ 2 (4 часа). МОДЕЛИРОВАНИЕ ВС НА ОСНОВЕ СИСТЕМ И СЕТЕЙ МАССОВОГО ОБСЛУЖИВАНИЯ.

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

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

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

По количеству обслуживающих приборов СМО делятся на одноканальные и многоканальные (рис. 2.1.).

DIV_ADBLOCK33">

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

Параметрами источника заявок;

Структурой, определяющей конфигурацию связей и вероятности передачи заявок между узлами сети;

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

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

Загрузку – среднее по времени число заявок, обслуживаемых сетью, и одновременно среднее число каналов, занятых обслуживанием;

Число заявок, ожидающих обслуживания в сети;

Число заявок, находящихся в сети (в состоянии ожидания и обслуживания);

Суммарное время ожидания заявки в сети;

Суммарное время пребывания заявки в сети.

Определение стохастических сетей

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

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

Для описания ВС используются разомкнутые и замкнутые стохастические сети. В разомкнутой (открытой) сети интенсивность входного потока заявок https://pandia.ru/text/78/299/images/image004_1.gif" width="614" height="134 src=">.gif" width="16" height="19 src=">

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

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

Рассмотрим ряд частных типов сетевых моделей, используемых для воспроизведения различных сторон функционирования ВС.

2.2. Детерминированные сети очередей.

Рассмотрим систему, которая характеризуется наличием каналов прямого доступа в память со стороны накопителей на лентах (НМЛ) и дисках (НМД), а также со стороны терминалов объекта управления. Схема системы представлена на рис. 2.3.(а)..gif" width="19" height="17 src=">, каналам, каждому из НМД и НМЛ. Современные мультипрограммные ОС поддерживают одновременную обработку заданий путем разделения между ними системных ресурсов. При этом достигается максимальное совмещение прикладных задач пользователей при чередовании обработки на центральном процессоре и периферийных средствах.

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

На рис. 2.3 (б) изображена схема действия процесса, рассматриваемая с позиций проблемного программиста. Операции прикладной программы расположены в порядке их выполнения и включают: 1 – работа прикладной программы (счет 1); 2 – печать данных; 3 – обмен с НМД; 4 – работа прикладной программы (счет 2); 5 – выдача информации на объект управления. Макрокоманды запроса к печати, обмена с НМД и объектом управления интерпретируются управляющими программами ОС и инициируют работу соответствующих каналов. Эти операции пронумерованы следующими цифрами: 6 – выполнение программы управления печатью; 7 – выполнение программы управления НМД; 8 – управляющие действия на терминале объекта. Из рис. 2.3.(б) видно, что выполнение операций прикладной программы и ОС чередуется и в очереди к процессору размещаются запросы на обслуживание различного типа.

https://pandia.ru/text/78/299/images/image009_1.gif" width="13" height="15 src=">.gif" width="12" height="15 src="> - НМД..gif" width="15" height="19 src=">, у которого очередь не возникает, так как число терминалов равно числу процессов в системе. Совокупность узлов и очередей соединена дугами, каждая из которых указывает возможные пути движения процессов. Процесс может занимать ресурс узла или находиться в очереди к нему..gif" width="15" height="19 src=">.gif" width="13" height="19 src=">, являющийся источником заявок. На дуге, соединяющей узлы и https://pandia.ru/text/78/299/images/image017_0.gif" width="40" height="19 src=">, которая указывает на формирование начального значения атрибута-операции, которая становится равной 1..gif" width="13" height="15 src=">.gif" width="41" height="19 src=">. Эта запись указывает как дальнейший путь процесса после операции 1, так и новое значение его атрибута-операции..gif" width="13" height="19 src=">..gif" width="13" height="15 src=">.gif" width="12" height="13 src=">.gif" width="13" height="15 src=">, 6.gif" width="13" height="15 src=">, 7.gif" width="13" height="15 src=">.gif" width="15" height="19 src=">.gif" width="13" height="13 src=">.gif" width="57" height="27 src=">.gif" height="17 src=">-м узле.

2.3. Стохастические сети очередей

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

Сетевая модель с элементами случайности представлена на рис. 2.4. Модель процессора представлена узлом Ввод данных" href="/text/category/vvod_dannih/" rel="bookmark">ввода-вывода данных с НМД описаны двумя последовательными этапами: подвод головки дисковода и поиск информации представлены узлами https://pandia.ru/text/78/299/images/image011_0.gif" width="12" height="15 src=">, а обмен через канал узлом.gif" width="15" height="19 src=">.gif" width="15" height="17 src=">.gif" width="15 height=17 src=" height="17">.gif" width="19" height="17 src=">.gif" width="21" height="24 src="> создается процесс..gif" width="19" height="17 src=">. Если при выполнении программы (операция 1) возникает запрос к базе данных , то процесс переходит к операции 2 (переход 1https://pandia.ru/text/78/299/images/image007_1.gif" width="19" height="17 src="> может быть направлен к одному из накопителей информации..gif" width="13" height="19 src=">,.gif" width="15" height="19 src=">.gif" width="13" height="19 src=">), он получит обслуживание, связанное с позиционированием головок чтения-записи на необходимые цилиндр и сектор..gif" width="13" height="15 src="> обеспечивает создание данных, передаваемых канальной программе..gif" width="19" height="17 src=">, где получает обслуживание, необходимое для выхода из прерывания по обращению к канальной программе и планирования возврата к проблемной программе..gif" width="20" height="15 src=">1). Таким образом, завершается цикл выполнения системных операций по организации обмена данными между основной памятью и диском.

https://pandia.ru/text/78/299/images/image027_0.gif" width="15" height="17 src=">.gif" width="20" height="15 src=">.gif" width="13" height="15 src=">.gif" width="20" height="15 src=">.gif" width="20" height="2 src=">Рассмотрим сети с активными ресурсами (узлами), трудоёмкость выполнения заявки в которых характеризуется временем vir, где r = 1,R - тип заявки и её цепь. Если r-заявки поступают в сеть из внешнего источника и после обслуживания покидают её, сеть называется открытой (разомкнутой) по отношению к цепи r. Сеть, не имеющая внешних источников, называется замкнутой. В смешанных сетях существуют как открытые, так и замкнутые цепи заявок.

В зависимости от области приложений сети с несколькими типами заявок называют либо многоцепными, либо многопродуктовыми. В замкнутых цепях назначают узел, возможно даже фиктивный, который принимают за начало и конец маршрута. Некоторые из узлов могут повторятся в маршрутной цепи несколько раз. Число αir, характеризующее число визитов в узел i заявок маршрута r, называют коэффициентом посещения (передачи).

Коэффициент посещения в стационарном режиме обслуживания можно определить из отношения:

αir = λir / λ0r, (2.1)

где λ0r - интенсивность потока r-заявок из начального узла маршрутной цепи заявок.

λir - интенсивность потока заявок в узел i.

Для разомкнутой цепи величину λ0r задают. Для замкнутой цепи величина λ0r определяется множеством параметров сети и характеризует её производительность (пропускную способность).

В стохастической сети движение r-заявок описывают маршрутной матрицей вероятностей переходов Pr = | pijr |, где pijr - вероятность того, что r-заявка после обслуживания в узле i переходит к узлу j.

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

λir = ∑λjir (2.2)

Здесь https://pandia.ru/text/78/299/images/image035_0.gif" width="308" height="138 src=">.gif" width="25" height="2 src=">λir = ∑ pjir λjr, i =0,N. (2.4)

Поскольку для разомкнутой цепи задают поток из внешнего источника λ0r и маршрутную матрицу Pr, то из уравнений (2.1) и (2.4) можно найти λir и αir.

Для замкнутой цепи уравнение балансов потоков (2.4) представляется однородной системой с бесконечным множеством решений. Поэтому для расчёта процессов в замкнутых цепях в качестве исходных данных берут величины λir. Поскольку за полный цикл заявка посещает начальный узел трассы один раз, коэффициент посещения нулевого узла равен единице. Учитывая, что λ0r=1 и подставляя λir = αir λ0r (из (2.1)) в левую и правую части системы уравнений (2.4), получаем уравнения для расчёта коэффициентов посещения замкнутой цепи:

https://pandia.ru/text/78/299/images/image039_0.gif" width="132" height="49 src="> i =0,N, т. е. имеем систему уравнение аналогичную (2.4) для расчёта αir,

https://pandia.ru/text/78/299/images/image041_0.gif" width="90" height="45 src="> i =0,N.

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

Мультиклассовая сеть

https://pandia.ru/text/78/299/images/image042_0.gif" width="29" height="26 src="> |. Элементы DIV_ADBLOCK37">

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

Интенсивность потока заявок в классе s системы i из других систем сети обозначим λis. Уравнения баланса потоков стационарного режима сети имеют вид:

https://pandia.ru/text/78/299/images/image044_0.gif" width="144" height="49 src="> (2.6)

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

· обслуживание в порядке поступления (FiFo);

· разделение времени (PS), предполагающее, что если в узле находится n запросов, то в единицу времени каждому из них будет представлен квант обслуживания длиною 1/n;

· прерывание на основе абсолютных приоритетов с дообслуживанием в обратном порядке(P);

· обслуживание без ожидания (Д)

Первые три способа представляют узлы, обслуживающие с ожиданием (узлы первого типа). Узлы второго типа, представляют индивидуальные ресурсы, закреплённые за процессом.

Введём обозначения:

niq - среднее число заявок класса q в узле i;

ni = ∑q niq - среднее число заявок в узле i;

Kr = ∑i ni - среднее число заявок цепи r;

K = ∑r Kr - число заявок в сети.

Gif" width="14" height="2 src=">.gif" width="14" height="2 src=">.gif" width="14" height="2 src=">Состояние сети описывается вектором n = (n1 ,n2 ,…,ni,…,nN), где ni - состояние узла i .

Gif" width="14" height="2 src=">.gif" width="10" height="2 src=">.gif" width="19" height="26 src="> ,…,SN) = (P1(S1), P2(S2),…,Декомпозиция" href="/text/category/dekompozitciya/" rel="bookmark">декомпозиции (структурирования). Основой классических алгоритмов вычисления G(K) является операция свертки нескольких векторов, которая представима в виде рекуррентных выражений по многомерной схеме Горнера.

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

Разомкнутые сети. Представим математическое обеспечение для расчёта однородных экспоненциальных сетей с несколькими потоками заявок. Математические модели названного класса описывают следующими исходными данными:

· интенсивность внешних источников пуассоновских потоков – λ0r;

· экспоненциально распределённой трудоёмкостью обслуживания в i-ом узле– vi = 1/μ, где μ - интенсивность обслуживания;

· коэффициентами посещения в i –e узлы - αir.

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

Характеристики сети рассчитывают следующим образом. Загрузка узла i со стороны потока заявок типа r:

https://pandia.ru/text/78/299/images/image052.gif" width="20" height="26 src="> = λi/μi , vi = 1/μi, https://pandia.ru/text/78/299/images/image052.gif" width="20 height=26 src=" height="26"> =https://pandia.ru/text/78/299/images/image052.gif" width="20" height="26 src="> vi/(1-https://pandia.ru/text/78/299/images/image052.gif" width="20" height="26 src="> ).

Воспользовавшись формулой Литла (ni = λiVi), найдём число заявок каждого типа в узле i:

nir = λir Vir = https://pandia.ru/text/78/299/images/image055.gif" width="67" height="39 src="> .

Замкнутые сети. Алгоритм расчёта сети через вероятности состояний.

Для замкнутых марковских сетей вероятности состояний определяются из решений, представимых в форме произведения (2.7). Если сеть состоит из FiFo-узлов, то вероятности состояний:

P(n1 n2…nN) =1/G(K) * Π https://pandia.ru/text/78/299/images/image052.gif" width="20" height="26 src="> = λi/μi - загрузка i-ой системы, равная отношению интенсивности потока к интенсивности обслуживания в i-й системе: m =1,K1; n = 1,K2; i = 1,N.Vi2(K1,K2) = vi2. (2.13)

Приведённые зависимости верны, если в FIFO-узлах время обслуживания не зависит от цепи, т. е. vi1 =vi2. В PS-узлах оно может различаться. При необходимости через G можно найти вероятности состояний и другие характеристики.

Основной недостаток алгоритма – большой диапазон изменения величины G, приводящий к переполнению, потери значности, погрешностям округления.

Метод анализа средних (МАС)

МАС может быть легко получен из алгоритма свертки и формул (ni = λiVi) Литла для цепи и узлов сети. Так, в случае одноцепной сети при K1 = K из выражения (2.13) имеем:

Vi(K) = vi. (2.14)

tпреб. tобсл. tожид. vi

Исходя из формулы Литла для цепи и учитывая, что время полного цикла заявки в сети,

C(K) = ∑i αiVi(K), (2.15)

получаем:

λ0(K) = K/C, (2.16)

а из формулы Литла для узла находим:

ni(K) = αiλ0(K)Vi(K). (2.17)

Заметим, что ni(0) =0. Рекуррентные вычисления по формулам (2.13) – (2.16) сразу дают искомые характеристики процессов и узлов сети. Загрузку находят из соотношения:

https://pandia.ru/text/78/299/images/image067.gif" width="88" height="39 src="> (2.15)

Рассмотрим более общий случай обслуживания в узлах. Введём величину bi(j), характеризующую ёмкость узла i, когда в нём находится j заявок. Для одноканальных обслуживающих приборов с постоянной скоростью обслуживания bi(j) =1. Для Д-узлов bi(j) =j. Для узлов, скорость обслуживания в которых зависит от нагрузки, имеем 0 < bi(j)<∞. Обычно bi(j) - монотонная неубывающая функция j, т. е.

bi(j) > bi(j-1) и bi(j+1) - bi(j) ≤ bi(j) - bi(j-1).

Например, если в узле находится двухканальный обслуживающий прибор, то bi(1) =1, bi(j) =2 для всех j ≥2.

Ёмкость узла (нагрузочная способность) определяется отношением:

bi(j) = μi(j)/μi(1), (2.19)

где μi(j) - интенсивность обслуживания в узле i, если в нём находится j заявок, а μi(1) - если одна заявка.

Если скорость обслуживания в узле зависит от нагрузки, как это описано формулой (2.19), то время пребывания можно вычислить по формуле:

Vi(K) = vi , (2.20)

где bm - максимальная нагрузочная способность узла i, bm≤K.

https://pandia.ru/text/78/299/images/image069.gif" width="614" height="87 src=">

https://pandia.ru/text/78/299/images/image071.gif" width="26" height="62 src="> Vir(K) = vir,

1 – для FIFO-, PS-узлов;

0 – для Д-узлов.

3. λ0r(K) = Kr/ ∑i αir left">

Рис. 2.5. Порядок обхода узлов при расчёте двухцепной сети с популяцией К = (2,2). ↓ - направление движения линии фронта.

Изображённый на рисунке граф – это не диаграмма состояний сети, а диаграмма возможных объёмов заявок в сети, содержащая несравнимо меньшее число вершин, чем диаграмма состояний. Число вершин в графе не зависит от числа узлов в сети.

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

По количеству обслуживающих приборов СМО делятся на одноканальные и многоканальные (рис. 2.1.).

Рис. 2.1. а – одноканальная СМО; б – многоканальная СМО

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

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

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

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

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

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

Рис. 2.2. Разомкнутая (а) и замкнутая (б) стохастические сети

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

Основные характеристики СМО

5.2.1 Описание сети. Обозначения

Похожие статьи