НАУКА и ОБРАЗОВАНИЕ

УДК 004.436.4 

МГТУ им. Н.Э. Баумана

chernen@bmstu.ru

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

Процесс Z есть четверка [1]:

Z=< S, T, F, a >

где:

S - пространство состояний системы, определенное ранее;

T - множество моментов времени изменения состояний системы;

F – график процесса, определяемый как отображение T→S, причем это отображение должно быть функциональным (однозначным);

α- отношение линейного порядка на T.

Пусть имеем объект O_l в системе Q. Тогда генерация процесса  может быть выполнена путем задания оператора  [1]:

где: ;

A - множество аргументов: AQ;

ω- случайное число.

Остальные определения опираются на материал [2].

В ходе развития процесса совокупность аргументов во множестве  может изменяться. Таким образом, состав элементов множества   в общем случае зависит от времени. Обозначим эту зависимость как . Рассмотрим два объекта O_l и O_m в системе Q. Пусть , а процессы в них заданы следующими операторами:

.

Если  и , то такие процессы и объекты называются не сцепленными в момент времени t_i.

Если , то объект O_m сцеплен с объектом O_l в момент времени t_i. То же относится и к их процессам. Это означает, что для определения состояния объекта O_m в момент времени t_i, необходимо знание состояния объекта O_l в это же время. Обозначим отношение сцепления как O_l→O_m. Не следует смешивать отношение сцепления и зависимости. Так, если O_m→O_l и O_l→O_k, то вовсе не обязательно, чтобы O_m→O_k. Таким образом, отношение сцепления не является транзитивным.

Если к отношению сцепления добавить полное транзитивное замыкание, то получим отношение зависимости. Т.е. если O_l зависит от O_m, а O_k зависит от O_l, то O_k зависит и от O_m. Таким образом, отношение сцепления можно определить как отношение непосредственной зависимости.

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

Рассмотрим дискретный во времени процесс Z. Пространство состояний S может быть как непрерывным, так и дискретным. Поставим в соответствие каждой i-ой точке процесса (момент времени изменения состояния t_i) некоторый оператор . Оператор  вычисляет значение состояния  в момент времени t_i:

.

Оператор  описывает вычисление только одной i-й точки процесса Z. В силу этого условия будем в дальнейшем называть этот оператор элементарным.

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

.

Введем новый элемент модели - инициатор. Он обладает свойствами динамичности и инициативности. Динамичность - инициатор имеет возможность перемещаться от оператора к оператору; будем называть попадание инициатора на оператор сцеплением инициатора с элементарным оператором. Инициативность - в момент сцепления инициатора с оператором происходит выполнение (инициирование) элементарного оператора, что соответствует вычислению нового состояния процесса. При этом полагаем, что выполнение элементарного оператора происходит мгновенно. Таким образом, описание процесса может быть выполнено путем задания линейной последовательности операторов  и перемещения по этой последовательности инициатора I, сцепляющегося с элементарными операторами  в заданные моменты времени t_i изменения состояния процесса. Алгоритмическая модель описания процесса предполагает, что моменты сцепления инициатора с элементарными операторами определяют сами элементарные операторы. С этой целью вводится оператор условия сцепления инициатора , который определяет условие, при выполнении которого инициатор сцепляется со следующим оператором . Возможны следующие варианты задания такого условия:

а) указание момента времени сцепления инициатора с оператором ;

б) определение логического условия, при выполнении которого инициатор сцепляется с оператором .

Таким образом, определим элементарный оператор h_i, как двойку:

.

При сцеплении инициатора с элементарным оператором h_i происходит мгновенное выполнение его обеих составных частей: выполнение  позволяет вычислить новое состояние s_i процесса Z, а выполнение оператора  дает возможность определить момент времени, либо логическое условие сцепления инициатора со следующим элементарным оператором h_i+1. Линейную последовательность элементарных операторов назовем треком TR:

.

Таким образом, можно АМП определить как двойку:

АМП=<TR,I>.

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

Пусть заданы два элементарных оператора h_l и h_k одного процесса Z, причем h_l→h_k, (h_k сцеплен с h_l.).

Утверждение 1. Если h_l→h_k, то

а) t_k≥t_l

б) первым должен вычисляться оператор h_l.

Рассмотрим влияние отношения сцепления на последовательность выполнения операторов при моделировании. Пусть заданы два процесса Z₁ и Z₂, условно изображенные на рис. 1.

Рисунок 1. Пример сцепления процессов

Дискретные состояния процесса Z₁ пронумерованы от 1 до 13, а процесса Z₂ - от 14 до 26. Рассмотрим четыре типовых случая:

а) моделируется один процесс Z₁, причем его операторы не сцеплены между собой.

б) моделируется процесс Z₁ без ограничения на сцепленность элементарных операторов;

в) моделируются два процесса Z₁ и Z₂, при этом эти процессы не сцеплены между собой;

г) моделируются два сцепленных процесса Z₁ и Z₁

На рис. 1 стрелками указано отношение сцепления.

A. Моделирование процесса Z₁ при несцепленных  операторах h_i (∀i).

Поскольку сцепление h_i→h_i+1  отсутствует для всех i, то последовательность вычислений элементарных операторов не имеет значения и операторы h_i (∀i). могут вычисляться в любом порядке.

Б. Моделирование процесса Z₁ в общем случае наличия сцепленности.

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

Предположим, что h_i→h_i+1, для всех . Из утверждения 1 следует, что в таком случае t_i+1>t_i для всех . Таким образом, последовательность сцепленных операторов строго следует порядку α на T. Из этого же утверждения следует, что последовательность вычислений операторов должна определяться этим же порядком.

В. Моделирование несцепленных между собой процессов Z₁ и Z₂.

Предполагаем, что процессы Z₁ и Z₂ в отдельности представлены общим случаем. Если h_i¹ - операторы процесса Z₁, а h_j² - операторы процесса Z₂, то по предположению отсутствует сцепление между h_i¹ и h_j² для всех i и j. Так же, как и в случае А, здесь последовательность вычислений элементарных операторов из разных процессов не имеет значения. Однако, поскольку все h_i¹ сцеплены между собой, и все h_j² также сцеплены между собой, важно, чтобы в этой последовательности выполнялся порядок a₁ для процесса Z₁ и a₂ для процесса Z₂. В частности, возможен вариант вычисления сначала всех операторов процесса Z₁, а затем всех операторов процесса Z₂. Очевидно, что порядок α₁ и α₂ при этом сохраняется.

Г. Моделирование сцепленных между собой процессов Z₁ и Z₂. Пример сцепления показан на рис. 1.

В этом случае должен быть обязательно выдержан порядок α₁ для Z₁ и α₂ для Z₂, поскольку в общем случае внутри каждого процесса существует сцепленность элементарных операторов. Кроме того, необходимо выполнить условия Утверждения 1 для любой пары сцепленных операторов из разных процессов. Так, для приведенного на рисунке 1 примера в соответствие с условиями Утверждения 1, из операторов h₁ и h₁₄ первым должен вычисляться оператор h₁, из h₅ и h₁₈ первым - h₁₈ и т.д.

Получим возможный порядок вычислений: h₁, h₁₄, (h₂, h₁₅), (h₃, h₁₆), h₁₇, h₄ и т.д.

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

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

1. Для каждого процесса в ходе вычисления операторов необходимо строго придерживаться порядка a на Т.

2. Выполнение п.1. обеспечивает реализацию сцепленности операторов h_i→h_j, если t_i<t_j , в рамках реализации одного процесса.

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

Действительно, если вычислены элементарные операторы h₁₀ и h₂₃ в момент времени t₁₀, то указание h₂₃→h₁₁ не меняет порядок вычислений, поскольку к моменту времени t₁₁ будет рассчитан оператор h₂₃. При этом условие сцепленности выполняется автоматически.

4. Для определения порядка расчета операторов, принадлежащих разным процессам, важно знание отношения сцепления для операторов разных процессов с одинаковым значением времени t_i.

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

Пусть заданы треки процессов Zⁱ ():  для всех i. Пусть текущее значение времени равно t и все элементарные операторы hⁱ, у которых tⁱ≤t , вычислены. Для всех hⁱ_j  , имеющих tⁱ=t и обладающих условным временным оператором , определим для каждого очередной момент времени tⁱ_j+1  cцепления инициатора по своему треку, задаваемый этим временным оператором. Получим множество . Назовем его активным временным множеством.

Это множество содержит по одному значению от каждого процесса, остановленного на элементарном операторе, содержащем временное условие продвижения инициатора. Определим очередное значение времени по формуле:

Последовательное применение формулы строит упорядоченное множество , где α^t -линейный порядок на T^t. Докажем ряд его свойств.

Для процесса Zⁱ имеем множество Tⁱ и линейный порядок αⁱ (). Рассмотрим множество  и порядок α^T на T, полученный транзитивным замыканием порядков αⁱ.

Утверждение 2.    Множества T^t и T равны.

В самом деле, любой элемент t∈T^t был определен из множества , элементы которого принадлежат Tⁱ (). Поскольку , то они же принадлежат и T. Следовательно, каждый элемент множества T^tпринадлежит и множеству T. Аналогично доказывается, что если элемент  принадлежит T, то он же принадлежит и T^t. Таким образом, утверждение 2 доказано.

Утверждение 3.    На упорядоченном множестве  сохраняются все порядки aⁱ ().

Рассмотрим множество Tⁱ с порядком αⁱ. Возьмем два любых его элемента tⁱ_k и tⁱ_l. Пусть в соответствие с αⁱ tⁱ_k<tⁱ_l;. Тогда, в соответствие с (2.14) tⁱ_k окажется минимальным элементом в {tⁱ_j+1} раньше, чем tⁱ₁, и следовательно, войдет во множество T^t  раньше, чем tⁱ₁. Поскольку упорядочение в T^t определяется порядком поступления элементов в T^t, то, следовательно, и в T^t  tⁱ_k<tⁱ₁. Аналогично можно провести доказательство и для остальных процессов. Таким образом, утверждение 3 доказано.

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

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

Рисунок 2. Пример реализации процессов через события

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

где i -номер процесса (он же- номер строки);

n -порядковый номер элементарного оператора в своем треке;

с -символ “состояние”;

у=л - символ логического условия продвижения инициатора;

у=t - символ временного условия продвижения инициатора.

Предположим, что к этому моменту времени все элементарные операторы вычислены. Тогда активное временное множество на текущий момент равно {t¹₁₀, t³₁₁, t⁶₂₁, t⁹₂₆,}

Определим в соответствии с (1) очередной момент времени, как:

t₀ =min {t¹₁₀, t³₁₁, t⁶₂₁, t⁹₂₆}

Для примера рис. 2  t₀=t¹₁₀ .

Таким образом, из начального состояния система переходит в новое состояние в момент времени t¹₁₀, соответствующее временному условию h^1,t₉.

В этот момент времени инициатор I₁ процесса Z₁ перемещается в элементарный оператор (h^1,c₁₀, h^1,л₁₀) , вычисляя новое состояние объекта O₁, а значит, и системы в целом. При этом оказывается выполненным условие h^4,Л₁₅ и h^7,Л₁₉.. В треке процесса Z₄ выполняется оператор состояния h^4,с₁₆ и устанавливается логическое условие h^4,Л₁₆, а в треке процесса Z₇ – h^7,с₂₀ и временное условие h^7,t₂₀. На рис. 2 соответствующие события отмечены светлыми кружками. Событие по временному условию показано на рис. 6 в виде темного кружка. Так как больше условий не выполняется, то необходимо перейти к новым элементарным операторам в соответствии с треками. В рассматриваемый момент времени следующее активное временное множество имеет вид . Согласно (1) необходимо перейти к новому моменту времени . В нашем случае t₀=. Первым выполняется оператор , который изменяет состояние объекта O₃ и системы в целом, а также формирует новый заказ времени передвижения своего инициатора I₃ в момент времени . При этом выполняются логические условия для процессов Z₅ и Z₈. Инициаторы I₅ и I₈ вызывают выполнение операторов <h^5,c₇,h^5,л₇ > и <h^8,c₃₂ ,h^8,л₃₂> соответственно. Формируется новое активное временное множество: , наименьшим в котором является . С оператора  и начинается следующий цикл вычислений, и т.д.

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

Выполнение каждого элементарного оператора назовем событием в системе. Событие активное, если оно следует в треке за элементарным оператором, содержащем h^t. На рис. 2 условия, содержащие h^t , выделены жирным шрифтом. К активным событиям относятся выполнение <h₁₀^1,c,h₁₀^1,л>, <h₁₁^3,c,h₁₁^3,t>, <h₂₁^6,c,h₂₁^6,л> и т.д.

Событие пассивное, если оно следует в треке за элементарным оператором, содержащем h^л. На рис. 2 к пассивным событиям относятся выполнение <h₁₁^1,c,h₁₁^1,t>, <h₉^2,c,h₉^2,л>, <h₁₇^4,c,h₁₇^4,л> и т.д.

Множество событий, происходящих в один и тот же момент модельного времени, назовем классом одновременных событий (КОС). На рис. 2 класс одновременных событий в момент времени  включает события для 1, 4 и 7-го процессов; в момент времени  КОС составляют события для 3, 5 и 8-го процессов и т.д.

Рассмотрение КОС примера на рис. 2 показывает, что в каждом КОС содержится активное событие. Введем следующие допущения:

Допущение 1. В каждом КОС содержится одно и только одно активное событие.

Тогда: а) все остальные события в КОС, если они есть, являются пассивными;

  б) количество КОС равно мощности объединенного множества времен T.

Допущение 2. Первым событием в любом КОС является активное событие.

Если это так, то оставшиеся пассивные события для определения последовательности своего выполнения требуют знания отношения сцепления. Представим отношение сцепления в КОС в виде направленного графа. На рис. 3 приведен пример некоторого КОС с заданным на нем отношением сцепления.

Рисунок 3. Пример КОС

Здесь: h_a - активное событие; h_b, h_c, h_d, h_e, h_f- пассивные события.

Из графа следует, что после h_a необходимо выполнить h_b либо h_c; затем h_d, либо h_e; и наконец h_f.

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

Так, условие выполнения события h_d должно содержать выражение, проверяющее выполнение события h_b. Если это удается сделать, то алгоритм формирования КОС выглядит следующим образом:

1. Выполняется активное событие.

2. Проверяются условия всех возможных в системе пассивных событий.

3. Если выполняется условие пассивного события, то оно вычисляется. Алгоритм продолжается с п.2.

Важно найти признак, по которому можно определить завершенность КОС.

Теорема А

КОС завершен, если все условия, заданные операторами h^л во всех треках, равны 0.

Поскольку КОС содержит одно активное событие и оно выполняется первым, то все остальные события пассивные. Пассивное событие по определению выполняется, если определяющее его условие равно 1. Однако, по предположению, все условия, заданные h^л , равны 0. Таким образом, выполнение пассивного события невозможно, а единственное активное событие уже выполнено. Поскольку не выполняется ни один элементарный оператор, состояние системы и параметры условных операторов не могут быть изменены. Состояние системы зафиксировано и не будет изменено вплоть до нового КОС. Что и требовалось доказать.

Теорема Б

Первым событием в КОС является активное событие.

Доказывая теорему А, мы показали, что когда завершен КОС, то все условия в условных операторах системы равны 0, и состояние системы не может быть изменено ни одним пассивным событием. Значит, следующий КОС может начаться только с активного события. Что и требовалось доказать.

Таким образом, наше допущение 2 о начальной функции активного события в КОС доказано строго в теореме Б.

Литература

1. Бусленко Н.П., Калашников В.В., Коваленко И.Н. Лекции по теории сложных систем. - М.: Сов.Радио, 1973. - 438 с.
2. Черненький В.М. Процессно-ориентированная концепция системного моделирования АСУ: диссертация ... доктора технических наук: 05.13.06, М., 2000 - 299 с.ил.