Советов Б.Я., Яковлев С.А. Моделирование систем (3-е изд., 2001) (1186218), страница 17
Текст из файла (страница 17)
е. обратная связь отсутствует, а в замкнутых67Q-схемах имеются обратные связи, по которым заявки двигаютсяв направлении, обратном движению вход-выход.Собственными (внутренними) параметрами Q-схемы будут являться количество фаз Аф, количество каналов в каждой фазе Lkj,j = l , L , количество накопителейкаждой фазы Ьт, к=\, L$, емкость /-го накопителя LtB. Следует отметить, что в теории массового обслуживания в зависимости от емкости накопителя применяют следующую терминологиюH для систем массового обслуживания: системы с потерями (L, =0, т. е.
накопитель в прибореIJ, отсутствует, аHимеется только канал обслуживания К,), системыс ожиданием (L, -»oo, т. е. накопитель Ht имеет бесконечную емкость и очередь заявок не ограничивается) и системы смешанноготипа (с ограниченной емкостью накопителя Щ. Всю совокупностьсобственных параметров Q-схемы обозначим как подмножество Н.Для задания Q-схемы также необходимо описать алгоритмы еефункционирования, которые определяют набор правил поведениязаявок в системе в различных неоднозначных ситуациях. В зависимости от места возникновения таких ситуаций различают алгоритмы (дисциплины) ожидания заявок в накопителе Н, и обслуживаниязаявок каналом Kt каждого элементарного обслуживающего прибора П, Q-схемы. Неоднородность заявок, отражающая процесс в тойили иной реальной системе, учитывается с помощью введения классов приоритетов.В зависимости от динамики приоритетов в Q-схемах различаютстатические и динамические приоритеты.
Статические приоритетыназначаются заранее и не зависят от состояний Q-схемы, т. е. ониявляются фиксированными в пределах решения конкретной задачимоделирования. Динамические приоритеты возникают при моделировании в зависимости от возникающих ситуаций.
Исходя из правил выбора заявок из накопителя Ht на обслуживание каналом Khможно выделить относительные и абсолютные приоритеты. Относительный приоритет означает, что заявка с более высоким приоритетом, поступившая в накопитель Hh ожидает окончания обслуживания предшествующей заявки каналом К, и только послеэтого занимает канал. Абсолютный приоритет означает, что заявкас более высоким приоритетом, поступившая в накопитель Н,, прерывает обслуживание каналом К/ заявки с более низким приоритетом и сама занимает канал (при этом вытесненная из А",- заявкаможет либо покинуть систему, либо может быть снова записана накакое-то место в Щ.При рассмотрении алгоритмов функционирования приборов обслуживания Z7, (каналов Kt и накопителей Щ необходимо такжезадать набор правил, по которым заявки покидают Н, и К{.
дляHi — либо правила переполнения, по которым заявки в зависимости от заполнения Ht покидают систему, либо правила ухода,68связанные с истечением времени ожидания заявки в Hh для К, —правила выбора маршрутов или направлений ухода. Кроме того,для заявок необходимо задать правила, по которым они остаютсяв канале Kt или не допускаются до обслуживания каналом Кь т. е.правила блокировок канала. При этом различают блокировки Kt повыходу и по входу.
Такие блокировки отражают наличие управляющих связей в Q-схеме, регулирующих поток заявок в зависимостиот состояний Q-схемы. Весь набор возможных алгоритмов поведения заявок в Q-схеме можно представить в виде некоторого оператора алгоритмов поведения заявок А.Таким образом, Q-схема, описывающая процесс функционирования системы массового обслуживания любой сложности, однозначно задается в виде Q=<JV, U, H, Z, R, А).При ряде упрощающих предположений относително подмножеств входящих потоков WVL потоков обслуживания U (выполнениеусловий стационарности, ординарности и ограниченного последействия) оператора сопряжения элементов структуры R (однофазноеодноканальное обслуживание в разомкнутой системе), подмножества собственных параметров Н (обслуживание с бесконечной емкостью накопителя), оператора алгоритмов обслуживания заявокЛ (бесприоритетное обслуживание без прерываний и блокировок)для оценки вероятностно-временных характеристик можно использовать аналитический аппарат, разработанный в теории массовогообслуживания.
При принятых предположениях в обозначениях Д.Кендалла будет иметь место классическая система обслуживаниятипа М/М/1 (одноканальная система с марковским входящим потоком заявок и марковским потоком обслуживания). Рассмотрим напримере основные аналитические соотношения для такой элементарной Q-схемы [6, 24, 37].Пример 2.6. Допустим, что процесс обслуживания начинается при отсутствиизаявок в накопителе.
Тогда состояния системы массового обслуживания описываются следующей системой уравнений:Ря (/+Д»)-Р. (О [1-(Я+/*)А']+Л-1 (1)Ш+Ря+1Р0 (t+At)=P0(ОМ'. « > 1 .(О ( 1 - М О + Л (ОМ'.где Р„ (г) — вероятность нахождения системы в состоянии z„ (/)eZ в момент времени I, т. е. когда в вей имеется л заявок.Эти уравнения следуют из того, что вероятность нахождения в системе л заявокв момент времени (/+AQ равна вероятности нахождения в системе л заявок в момент/, умноженной на вероятность того, что за время At в систему не поступит ни однойзаявки и ни одна заявка не будет обслужена, плюс вероятность нахождения в системе(л— 1) заявок в момент t, умноженная на вероятность того, что за время Д/ поступитодна заявка и ни одна заявка не будет обслужена, плюс вероятность нахожденияв системе (л +1) заявок в момент /, умноженная на вероятность того, что за время AtОдна заявка покинет систему и не поступит ни одной заявки.
Вероятность того, чтоза время At не поступит ни одной заявки и ниодна заявка не покинет систему, равна(1 — АДО (1— /iAt). Член, содержащий (At)1, при составлении дифференциальногоуравнения опускается. Следовательно, можно записать 1— (X+ii)At. Относительноостальных двух членов первого уравнения заметим, что69XAt (1-М0*ЯДг, pAt (1-ЯД0*мД'Перенеся Р„ (0 влево и устремив Д» к нулю, получим систему дифференциальныхуравнений{dP„ (О/ЛW 0 (О/А(Л+иУ. (0+^n-i (О+Л+1 ('). «>1.^о(0+мЛ(0-Найдем выражение для математического ожидания числа заявок, находящихсяв накопителе, и среднего времени ожидания заявок в накопителе для стационарногосостояния р=И/ц<\. Приравняв нулю производные по времени и исключив, такимобразом, время t нз уравнений, получим систему алгебраических уравненийГ(Л+/|)д,«4А,-1+т,-|, я>1,|(1+/>)л=Л|+1+йРя-1, ">1.W>o-«Pi»\pi~PPo-Пусть в первом уравнении п=\.
Тогда (l+p)Pi=p2+PPo- Подставив сюдазначение ;», из второго уравнения, находим р2"Р2Ро- Повторяя эти операции,получаем ря**р2р0, причем £ р„ = 1, так как это сумма вероятностей того, что•-Dв системе нет ни одной заявки, имеется одна заявка, две заявки и т. д. Сумма этихвероятностей должна быть равна единице, так как рассматриваются все возможныевосостояния системы. Поэтому £ р /»0 = 1,«-0СО00шили Y.PoP Ро £ />"-А>/(1-/>)=!. откуда р 0 - 1 - р .
Следовательно, рншр (1-р).»-0»-0Полученное выражение представляет собой геометрическое распределение.Математическое ожидание числа заявок, находящихся в системе (приборе),СОВО' • " £ «р>1=(1-/>) Z Д Р в Р 0 - Р ) Отметим, что /„ —•- среднее значение и возможны колебания числа заявок, ожидающих обслуживания, что можно оценить с помощью дисперсии:»**д-0При этомDO№S «*A-(1-P) I л2р"=р/(1-р)+2р2/(1-р)2.»-0я-0Следовательно,£['J=M1-P)+2P2/(1-P)J.Математическое ожидание числа заявок, находящихся в накопителе.00'Н=1(Л-1)/>Я = / „ - Р = Р / ( 1 - Р ) - Р = Р2/(1-Р)»-1Среднее время ожидания заявок в накопителе'в=1М=Р2/[А(1-р)].70Возможности оценки характеристик с использованием аналитических моделей теории массового обслуживания являются весьмаограниченными по сравнению с требованиями практики исследования и проектирования систем, формализуемых в виде Q-схем.
Несравненно большими возможностями обладают имитационные модели, позволяющие исследовать Q-схему, задаваемую Q=(W, U,H,Z, Y, R, А}, без ограничений. На работу с Q-схемами при машиннойреализации моделей ориентированы многие языки имитационногомоделирования, например SIMULA, SIMSCRIPT, GPSS и др. Детально вопросы, связанные с имитационным моделированием g-схем,будут рассмотрены далее.2.6. СЕТЕВЫЕ МОДЕЛИ (JV-СХЕМЫ)В практике моделирования объектов часто приходится решатьзадачи, связанные с формализованным описанием и анализом причинно-следственных связей в сложных системах, где одновременнопараллельно протекает несколько процессов.
Самым распространенным в настоящее время формализмом, описывающим структуруи взаимодействие параллельных систем и процессов, являются сетиПетри (англ. Petri Nets), предложенные К. Петри [28, 30].Основные соотношения. Теория сетей Петри развивается в нескольких направлениях: разработка математических основ, структурная теория сетей, различные приложения (параллельное программирование, дискретные динамические системы и т.
д.).Формально сеть Петри (N-схема) задается четверкой видаN=(B,D,I,0),где В — конечное множество символов, называемых позициями,ВФ0\ D — конечное множество символов, называемых переходами, D^0, В[)рФ0\ I—входная функция (прямая функция инцидентности), I: BxD-*{0, 1}; О — выходная функция (обратнаяфункция инцидентности), О : Dx 2?-»{0,1}. Таким образом, входнаяфункция / отображает переход d, в множество входных позицийbtel(dj), а выходная функция О отображает переход d, в множествовыходных позиций bteD(dj). Для каждого перехода djeD можноопределить множество входных позиций перехода 1(d) и выходныхпозиций перехода О (dj) какЩ)={Ь,еВ\[{Ьь4)=1},0(dJ)={bieB\0(dJ, £,) = !},i=T7n\j=\,m,n=\B\, m=\D\.Аналогично, для каждого перехода bteB вводятся определениямножества входных переходов позиции 1(b) и множества выходныхпереходов позиции О (£>,):711(Ьд={djeD\I(dj, Ь,)=1},O(bd={djeD\0(bh dj)=l}.Графически N-схема изображаетсяв виде двудольного ориентированногомультиграфа, представляющего собойРис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
