Черненький В.М. - Теоретические основы построения имитационного процесса

МГТУ им. Н.Э. БауманаФакультет «Информатика и системы управления»Кафедра «Системы обработки информации и управления»УДК 519.876.5ТЕОРЕТИЧЕСКИЕ ОСНОВЫ ПОСТРОЕНИЯИМИТАЦИОННОГО ПРОЦЕССАЭлектронное учебное изданиеУчебное пособие по дисциплине«Описание параллельных процессов»АвторЧерненький В.М.Рекомендуется НМС МГТУ им. Н.Э. Баумана в качестве учебного пособияМОСКВА2012АннотацияПостроение имитационной модели АСУ выполняется на основеописания процессов функционирования, таким образом, модель описанияпараллельных процессов позволяетметодоввыполнить исследование в областипостроения имитационных моделей.Имитационный процессрассматривается, как один последовательный вычислительный процесс, накоторый отображается система параллельных взаимосвязанных процессов.Алгоритмическая модель описания процесса (АМП) позволила получитьуниверсальную системную модель имитационного процесса, сформироватьструктуры моделирующих алгоритмов.Основные положенияПусть заданы два элементарных оператора hl и hk одного процесса Z,причем hl hk, (hk сцеплен с hl.).Утверждение 1.

Если hl hk, тоа) tktlб) первым должен вычисляться оператор hl .Доказательство: Поскольку процесс Z развивается в соответствии стреком элементарных операторов и порядком  на T, то сцеплениеэлементарного оператора в момент времени t1 с любым оператором,имеющим ttl невозможно. Но поскольку hl hk, то следовательно tktl . Т.к.hl hk, то отсюда следует, что пространство состояний hl является частьюаргументов оператора hk. Таким образом, вычисление hk невозможно безопределения состояния hk.

Что и требовалось доказать.Рассмотрим влияние отношения сцепления на последовательностьвыполнения операторов при моделировании. Пус ть заданы два процесса Z1 иZ2 , условно изображенные на рис. 1.Дискретные состояния процесса Z1 пронумерованы от 1 до 13, апроцесса Z2 - от 14 до 26. Рассмотрим четыре типовых случая:а) моделируется один процесс Z1 , причем его операторы не сцепленымежду собой.S2Z232196451071211138T2S2Z214161719182122242015252623T2t1t2t3t4t5t6t7t8t9t10t 11t12t 13Рисунок 1. Пример сцепления процессовб)моделируется процессZ1 безограничения на сцепленностьэлементарных операторов;в) моделируются два процесса Z1 и Z2 , при этом эти процессы несцеплены между собой;г) моделируются два сцепленных процесса Z1 и Z1На рисунке 1 стрелками указано отношение сцепления.A. Моделирование процесса Z1 при несцепленных операторах hi (i).Посколькусцеплениепоследовательностьhi hi+1вычисленийотсутствуетэлементарныхдлявсехоператоровнеi,тоимеетзначения и операторы hi (i).

могут вычисляться в любом порядке.Б. Моделирование процесса Z1 в общем случае.Естественно предположить, что последовательные состояния одногопроцесса сцеплены между собой.Предположим, что hi hi+1 , для всех i  1, n . Из утверждения 1 следует,чтовтакомслучаеti+1 >tiдлявсехi  1, n .Такимобразом,последовательность сцепленных операторов строго следует порядку  на T.Из этого же утверждения следует, что последовательнос ть вычисленийоператоров должна определяться этим же порядком.В. Моделирование несцепленных между собой процессов Z1 и Z2 .Предполагаем, что процессы Z1 и Z2 в отдельности представлены общимслучаем. Если hi 1 - операторы процесса Z1, а hj2 - операторы процесса Z2 , топо предположению отсутствует сцепление между hi 1 и hj2 для всех i и j. Также, как и в случае А, здесь последовательность вычислений элементарныхоператоров из разных процессов не имеет значения.

Однако, поскольку всеhi 1 сцеплены между собой, и все hj 2 также сцеплены между собой, важно,чтобы в этой последовательности выполнялся порядок  1 для процесса Z1 и2 для процесса Z2 . В частнос ти, возможен вариант вычисления сначала всехоператоров процесса Z1 , а затем всех операторов процесса Z2 . Очевидно, чтопорядок  1 и  2 при этом сохраняется.Г. Моделирование сцепленных между собой процессов Z1 и Z2.

Примерсцепления показан на рисунке 1.В этом случае должен быть обязательно выдержан порядок  1 для Z1 и2 для Z2 , поскольку в общем случае внутри каждого процесса существуетсцепленность элементарных операторов. Кроме того, необходимо выполнитьусловия Утверждения 1 для любой пары сцепленных операторов из разныхпроцессов. Так, для приведенного на рисунке 5 примера в соответс твии сусловиями Утверждения 1, из операторов h1 и h14 первым долженвычисляться оператор h1 , из h5 и h18 первым - h18 и т.д.Получим возможный порядок вычислений: h1 , h14 , (h2, h15 ), (h3 , h16 ), h17,h4 и т.д.В скобках указаны пары операторов из разных процессов, для которыхможно поменять порядок вычислений.На основании проведенного анализа можно сделать следующие выводы:1.

Для каждого процесса в ходе вычисления операторов необходимострого придерживаться порядка  на Т.2. Выполнение п.1. обеспечивает реализацию сцепленности операторовhi hj, если ti <tj , в рамках реализации одного процесса.3. При выполнении п.1 указание сцепленности операторов с разнымзначением ti в рамках одного процесса не добавляет новых ограничений напорядок расчета и может быть опущено.Действительно, если вычислены элементарные операторы h10 и h23 вмомент времени t10 , то указание h23 h11 не меняет порядок вычислений,поскольку к моменту времени t11 будет рассчитан оператор h23 .

При этомусловие сцепленности выполняется автоматически.4. Для определения порядка расчета операторов, принадлежащихразным процессам, важно знание отношения сцепления для операторовразных процессов с одинаковым значением времени ti .Такимопределенияобразом,порядкаможносформулироватьвычисленияследующийэлементарныхалгоритмоператоровдлясовокупности параллельных процессов.Пусть заданы треки процессов Zi (i  1, n ):h , ijiдля всех i. Пустьтекущее значение времени равно t и все элементарные операторы hi , укоторых ti t , вычислены. Для всех hij, имеющих ti =t и обладающихусловным временным оператором ( h ij )t , определим для каждого очередноймомент времени ti j+1 cцепления инициатора по своему треку, задаваемыйэтим временным оператором.

Получим множествоt .ij 1Назовем егоактивным временным множеством.Это множество содержит по одному значению от каждого процесса,остановленного на элементарном операторе, содержащем временное условиепродвижения инициатора. Определим очередное значение времени поформуле:t0  mint ij 1 , ( i )(1)Последовательное применение формулы 1 строит упорядоченноемножество T t ,  t , где t -линейный порядок на T t .

Докажем ряд егосвойств.Для процесса Zi имеем множество Ti и линейный порядок  i (i  1, n ).Рассмотрим множество T  T i ( i ) и порядок  T на T, полученныйтранзитивным замыканием порядков i .Утверждение 2.Множества T t и T равны.В самом деле, любой элемент tTt был определен по формуле (2) из множества t ij 1 , элементы которого принадлежат Ti( i  1, n ). ПосколькуT  T i ( i ) , то они же принадлежат и T. Следовательно, каждый элементмножества Ttпринадлежит и множеству T. Аналогично доказывается, чтоесли элемент принадлежит T, то он же принадлежит и Tt .

Таким образом,утверждение 2 доказано.Утверждение 3.На упорядоченном множестве T t ,  tсохраняютсявсе порядки  i (i  1, n ).Рассмотрим множество Ti с порядком  i. Возьмем два любых егоэлемента ti k и ti l. Пусть в соответствие с i ti k <ti l; . Тогда, в соответствие с (2) ti kокажется минимальным элементом в {ti j+1 } раньше, чем ti1 , и следовательно,войдет во множество Ttраньше, чем ti 1 . Поскольку упорядочение в Ttопределяется порядком поступления элементов в Tt , то, следовательно, и в Ttti k <ti 1.

Аналогично можно провести доказательство и для остальныхпроцессов. Таким образом, утверждение 3 доказано.На основании Утверждений 2 и 3 можно сделать заключение о том, чтоформула (1) позволяет построить новое множество T, включающее всеэлементы множеств Ti (i) , и провести упорядочение его элементов такимобразом, что сохраняются все отношения порядка в каждом из них.Поскольку каждому tTi (i) ставится в соответствие свой элементарныйоператор в треке, то определение порядка на T дает возможность однозначноопределить порядок на всем множестве элементарных операторов заданныхпроцессов.Классы одновременных событийРассмотрим последовательнос ть выполнения элементарных операторовв системе.

Пусть система содержит 9 объектов, в каждом из которыхразвивается процесс. На рисунке 2 приведен пример организации треков нанекотором временном интервале. Пусть в некоторый момент временисистема находилась в состоянии, показанном на рисунке 6 слева. Назовем егоначальнымсостоянием.Для каждогопроцесса Ziуказантекущийэлементарный оператор в следующих обозначениях:hni, c , hni, y ,(2)где i - номер процесса (он же - номер строки);n - порядковый номер элементарного оператора в своем треке;с - символ “состояние”;у=л - символ логического условия продвижения инициатора;у=t - символ временного условия продвижения инициатора.Предположим, что к этому моменту времени все элементарныеоператоры вычислены. Тогда активное временное множество на текущиймомент равно {t110, t3 11 , t621, t9 26 ,}Определим в соответс твии с (1) очередной момент времени, как:t0 =min {t110, t311, t6 21 , t926}(3)Для примера рис.

2 t0 =t110 .Таким образом, из начального состояния система переходит в новоесостояние в момент времени t1 10, соответствующее временному условию h1,t9 .Начальное состояниеZ1 :<h 91,c ,h91,t>Z2 :<h 82,c,h 82,л>Z3 :<h 103,c,h103,t>Z4 :<h 154,c ,h154,л><h 111,c, h11 1,t><h101,c, h 101,л><h 121,c, h 121,л>t12 1t10 1<h102,c ,h 102,л><h92,c, h 92,л><h113,c, h113,t><h164,c, h 164,л><h 123,c ,h 123,л>t 113<h 216,c, h 216,л>h206,t>t 21 6<h207,c ,h20 7,t>T6<h 227,c,h227,t>T7<h338,c, h338,t>T8<h269,c, h 269,л>Z9 :<h259,c ,h25 9,t><h269,c, h269,t>t26 9t101t113t216t217T4T5<h 217,c, h 217,л><h 328,c, h 328,л>Z8 :<h 318,c ,h 318,л><h 184,c ,h184,t><h 226,c, h 226,л>t 217T2T3<h65,c ,h 65,л>Z5 :<h 65,c ,h65,л>Z7 :<h197,c ,h 197,л>t123<h174,c, h 174,л><h 75,c, h 75,л>Z6 :<h 206,c,<h112,c, h112,t>T1t2 69t12 3T9t1 21Рисунок 2.