Советов Б.Я., Яковлев С.А. Моделирование систем (3-е изд., 2001) (1186218), страница 69
Текст из файла (страница 69)
Рассмотрим особенности представления в виде КЛА Р-схемы,представляющей собой конечный асинхронный вероятностный автомат Мура, который ве имеет жесткой тактности, а изменяет свое состояние только при поступлениивходного сигнала. Пусть Хш и К, — конечные входной и выходной алфавиты автомата, a Z a — конечное множество его внутренних состояний. Полагаем для определенности, что А"а={1, 2, ..., А}, У»={1, 2,..., A/}, Z a ={l, 2, ..., Щ функционированиетакой Р-схемы описывается следующим образом: если в момент времени I автоматнаходился в состоянии z,(/)=i и поступил входной сигнал x,(t)=k, то состояниекавтомата z a (f+0) - у выбирается случайно с вероятностью р5У > 0, £ ^ = 1 , fc=1, К.J-iВыдаваемый при этом выходной сигнал ул е Уа является однозначной функциейнового состояния, в которое перешел автомат, т.
е. ул—т=Ф{}), где Ф — некотораядетерминированная функция с множеством значений Уа и областью определения Za.Для представления такой Р-схемы в виде КЛА в качестве множества входныхсигналов агрегата X выберем множество Хл, а в качестве множества выходныхсигналов Y— множество Уа. В качестве основных состояний КЛА / выберем множество Z a и будем полагать, что ||v||=0 для всех ve/, т. е. вектор дополнительныхкоординат z w не определяется. При таком задании КЛА многогранники Z w неопределяются, т. е. отпадают вопросы, связанные с движением внутри многогранников, выходом на границу и распределением Pt.Таким образом, функционирование такого КЛА сводится к скачкам состоянияпри поступлении входных сигналов, причем из-за отсутствия вектора дополнительных координат такие скачки сводятся лишь к скачкам основного состояния v, чтотребует только задания распределения Рг, которое совпадает с распределением P\f.Содержание выходного сигнала, выдаваемого в момент поступления входного сигнала КЛА, определяется только функцией Ф.Если предположить, что ||v||=0, ||Я||=0, Ы | = 0 для всех v, X, ц, то КЛАпревращается в Р-схему общего вида.298Способы построения моделирующих алгоритмов А-схем.
Основные преимущества агрегативного подхода состоят в том, что в рукиразработчиков моделей и пользователей дается одна и та же формальная схема, т. е. А-схема. Это позволяет использовать результаты математических исследований процессов, описывающих функционирование агрегативных систем, при создании моделирующихалгоритмов и их программной реализации на ЭВМ. В настоящеевремя имеются разработки математического обеспечения, в основукоторого положен агрегативный подход. Но при этом у пользователя всегда должна оставаться свобода в переходе от концептуальной к формальной модели.
Таким образом, имеется возможностьмноговариантного представления процесса функционирования некоторой системы S в виде модели М, построенной на основе А-схем.Пример 8.16. Рассмотрим технологию перехода от содержательного описанияк А-схеме на примере Q-схемы, структура которой приведена на рис. 8.6. Такойпереход возможен, так как А-схема отражает наиболее общий подход к формализации процесса функционирования системы S. Для представления этой системыв виде Л-схемы будем использовать пять типов агрегатов, а именно: АЕ — внешняясреда; Аи — накопитель; Ах — канал; Аг — распределитель; Ас — сумматор. Функции агрегатов Аи и А соответствуют функциям таких элементов Q-схемы, какнакопитель (Н) и канал (К). Агрегат А* позволяет формализовать взаимодействиемежду агрегатами Л-схемы и внешней средой Е. Использование вспомогательныхагрегатов Аг и Ас вызвано необходимостью синхронизации работы агрегатов в составе А-схемы в соответствии с принятыми дисциплинами ностановки в очередьи обслуживания заявок.
Кроме того, через агрегат Ас возможна передача сигналовот различных выходных контактов одних агрегатов на один и тот же входнойконтакт другого агрегата, что запрещено делать непосредственно (см. § 2.7).При таких предположениях структура А-схемы будет иметь вид, приведенный нарис. 8.29. Опишем работу каждого типа агрегатов, показанных на рис. 8.30, в отдельности.Агрегат «Внешняя среда» АЕ (рис. 8.30, а) имеет два входных контакта и одинвыходной: на вход Xt№) поступают обслуженные заявки (сигнал jcf' = l); на входХ2№) —заявки, получившие отказ в обслуживании (сигнал х2№) = 1); с выхода У^®снимают заявки через промежутки времени, распределенные по заданному законураспределения входящего потока заявок.
Вектор состояний агрегата АЕ : г Е (/) = 1.Агрегат «Канал» Ак (рис. 8.30, 6) имеет три входных контакта и один выходной:на вход Xf-) подают сигнал поступления заявки на обслуживание; на вход Xf} —сигнал разрешения выдачи обслуженной заявки; на вход Хф — сигнал блокировкиРис.
8.29. Пример А-схемы общего вида299а)г)ОбслуженныезаявкиЗоядни, получившие отка.Сх,£* 2ОV,Поступление^,Входящийпоток заявки(-> * (илииящци tiumunзаявкихпяЬпк /J.n,pMu Разрешение IБлокировка /Разрешение 2,5)Блокировка 2Поступление /Г>заявки С * |Разрешение ,-,выдачи >-» X, У,Блокировка f-\выдачи^DОо-Выдача оослуженной заявкид)1 вход1 входВыдача заявкиУ.-О *-С х2Разрешение на.заявкищЩ^дшЩх,„Разрешение на>> uБлокировка ^L~Потеря заявки? $°$"С X,выдачи ^ Лг у2 ^J wa-jff переполнения заявкиРазрешение ^^ .Накопитель1ы~а~ачи^ *з Y3 ^Поступление^г>.
Выдача по 1<-) направлениюВыдача по 2направлениюD Разрешение навыдачу заявкиблокировкавыдачи заявкиX^UВыдачаРазрешение по 1направлению^ Блокировка па I>-/ направлениюРазрешение по 2направлению/>. Блокировка па 2направлениюООРис. 8.30. Агрегатывыдачи обслуженной каналом заявки; с выхода Yf> снимают сигнал выдачи обслуженной каналом заявки.
Вектор состояний агрегатаz,t(o-Wf(o.'5w.*5w}.где zf (r) — время, оставшееся до окончания обслуживания заявки, которая находится в канале;если блокировка отсутствует,в противном случае;если заявка находится в канале,в противном случае.В том случае, если время обслуживания заявки в канале истекло, т. е. z*(<)<0,но ее выдача из канала запрещена, т.
е. г? (/) = 0, заявка остается в канале до тех пор,пока не придет сигнал z* (f)= l.Агрегат «Накопитель» Ан (рис. 8.30, в) имеет три входа и три выхода, входныеконтактыХ?\ Xf\ Х^ соответствуют по своим функциям контактам Xf\Xf\Xf-] агрегата Ах, с выхода Ff1' выдается заявка, стоящая в очереди в накопителепервой; с выхода Y^ выдаются заявки, потерянные из-за переполнения накопителя;с выхода УУ поступает сигнало том, что накопитель полностью заполнен.
Внутреннее состояние агрегата Ан описывается векторомгн(о=Ф?('), *?(')},300где z?(r) — число заявок в накопителе;нП, если блокировка отсутствует,(О в противном случае.Агрегат «Распределитель» Ат (рис. 8.30, г) служит для разделения поступающегона вход Xf потока заявок по двум направлениям — выходам Yf) и Yf, чтосоответствует принятой дисциплине обслуживания, т. е. алгоритму взаимодействиянакопителя и канала. В рассматриваемом примере поступившаяв Лр-заявка передакется через выход Yf\ если соответствующий ему агрегат А свободен для принятияна обслуживание этой заявки; в противном случае заявка выдается через выход Yf.Информация о занятости соответствующих агрегатов А\ на которые поступаютзаявки с выходов Yf, Yf, передается на входные контактыXf—Xf.
Если обаагрегата А* не могут принять заявки от агрегата Ат,е то на выходной контактYf выдается сигнал, запрещающий передачу заявки А . Как только один из агрегатов А* освободится (о чем выдается соответствующий сигнал Аит на входыXf — Xf, сигналс контакта У?' разрешает посылающему агрегату А пересылкузаявки через Аг в А*, т. е. заявка в А* не хранится. Внутреннее состояние агрегатаопределяется векторомгр(0 = М(0>^(')},гдеесли разрешена передача заявки по выходу,в противном случае;если разрешена передача заявки по выходу,*5М..в противном случаеАгрегат «Сумматор» Ас (рис.
8.34, д) выполняет функции, обратные агрегату Ат,т.к е. избирательно суммирует поступающие заявки отндвух кпосылающих агрегатовА и передает их на вход принимающего агрегата (А и Л ). При поступлении навход Х*Р или Xf сигнала разрешения передачи заявки от принимающего агрегатасумматор Ас должен последовательно опросить принимающие агрегаты. Для этогосначала передается сигнал разрешения на первый из посылающих агрегатов (контактУР). От этого посылающего агрегата либо поступает сигнал на входной контактХ*Р, либо он отсутствует. В первом случае поступившая заявка передается дальше(контакт УР), в противном случае посылается сигнал разрешения (контакт yip) навторой из посылающих агрегатов. Внутреннее состояние агрегата Ас определяетсявектором*СМ-{*?('».где-fr.если выдача заявки разрешена,в противном случае.Таким образом, используя набор аргегатов Аг, Ак, Ан, Av и Ас,можно описать процесс функционирования рассматриваемой системы (см.