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

УДК 004.436.4

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

chernen@bmstu.ru

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

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

Определим пространство состояний системы как Декартово произведение S=σ(q_i). В этом пространстве каждый параметр выступает в роли координаты, а размерность пространства равна мощности множества Q. Элемент пространства S есть возможное состояние системы.

В дальнейшем нас будет интересовать процесс изменения состояний системы во времени. Примем за основу определение процесса, предложенное в работе [1].

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

где:

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

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

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

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

Если множество T задано как упорядоченное, то в определении процесса α может быть опущено.

В общем случае множества T и S могут быть как дискретными, так и непрерывными.

Интервал времени [t_Н, t_К], где t_Н=min{T}, t_К=max{T}, назовем интервалом определения процесса.

Поскольку пространство S координатного типа, то в случае необходимости подчеркнуть систему координат Q, на которой оно определено, будем обозначать его также S_Q.

В этих обозначениях, если множество Т задано, как упорядоченное, а пространство S определено на множестве параметров Q, определить процесс можно как: Z=< S_Q, T, F >.

Кортеж , где - значения элементов множества X , будем обозначать как  .

Определим фазовое пространство Ф процесса Z как Ф=T´S .

Тогда график F есть подмножество Ф.

Если f∈ F, то  f = <t, >, где t∈T.

Если Q₁Q, то определим понятие проекции f на пространство  как:

= <t, >.  Проекцией f на T является t.

Пусть процесс Z задан на интервале [t_Н, t_К]. Введем понятие подпроцесса Z ⁱ как плотное во времени подмножество процесса Z на интервале [t_i; t_j] при условии, что [t_i; t_j]  [t_Н, t_К]. Плотность по времени означает, что на интервале [t_i; t_j] нет ни одной точки, принадлежащей Т и не относящейся к подпроцессу Z ⁱ. Этот интервал назовем интервалом определения подпроцесса. Понятие подпроцесса позволяет рассматривать процесс в виде последовательности подпроцессов и производить операции разделения и объединения фрагментов процесса.

Рассмотрим ряд операций над процессами, описываемых с помощью введенных выше понятий.

Операция свертки процесса

Пусть задан процесс Z=<S, T, F, α>

Процесс Z₁=<S₁, T₁, F₁, α₁> является сверткой процесса Z, если он получен в результате следующих преобразований:

а) произведено полное разбиение интервала определения процесса Z на n непересекающихся подинтервалов [τ_j, τ_j+1], где j=1..n, причем τ₁=t_Н , τ_n+1=t_К . В результате получим разбиение процесса Z на n подпроцессов  Z ^j (j=1..n);

б) поставим в соответствие каждому подпроцессу Z^j одно значение состояния  из множества S₁ и одно значение времени β^j из интервала [τ_j, τ_j+1]. В результате получим дискретное множество  , график , отношение α₁α.

Таким образом, получим новый процесс Z₁, который и называется сверткой процесса Z. Очевидно, процесс Z₁ дискретен во времени. Никаких ограничений на характер пространства состояний S₁ не накладывается. Однако на практике при проведении операции свертки пространство S₁, как правило, оказывается значительно меньшей мощности, чем исходное пространство S.

Рассмотрим для примера процесс решения задачи c использованием CPU и жесткого диска HD (рис. 1).

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

Пусть исходный процесс Z описан в пространстве S, имеющем следующие состояния: {обращение к памяти, загрузка регистров, операции сумматора, головка диска, запись-считывание на диске, печать результата}. Множество моментов времени изменения состояния Т={0, t1, t2, t3, t4, t5, t6, t7, t8, t9, t10, t11}.

Допустим, что нам необходимо построить процесс Z1, отражающий лишь длительность занятия задачей CPU и жесткого диска HD. Для этого зададим новое пространство S1, имеющее следующие состояния: {ожидание, решение в CPU, работа с HD}. Разобьем интервал определения процесса Z на подинтервалы: П1, П2, П3, П4, П5. Это разбиение определяет также соответствующие подпроцессы процесса Z. Выполним отображение подпроцессов процесса Z на фазовую плоскость процесса Z1: П1 отображается в точку А, П2 – в точку В, П3 – в точку С, П4 – в точку D, П5 – в точку Е. В результате получим процесс Z1 с пространством состояний S1, множеством моментов времени изменения состояния Т1={0, t1, t7, t8, t10}. График этого процесса приведен на этом же рисунке.

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

Операция свертки относится к классу операций анализа.

Операция развертки

Операция развертки обратна по отношению к операции свертки: процесс Z является разверткой процесса Z₁. При выполнении этой операции необходимо каждую точку  процесса Z₁ развернуть в подпроцесс Z ^j.

Операция развертки относится к классу операций синтеза.

Операция проецирования

Процесс Z₁ является проекцией процесса Z на координатное пространство  (обозначение ), если Q₁Q и процесс построен по следующей процедуре:

1)              каждую точку графика F проецируем на пространство . В результате получаем множество . Мощность множества  равна мощности множества F ;

2)              упорядочиваем множество  в соответствие с α. Результат действий 1) и 2) будем называть отображением процесса Z на пространство ;

3)              вводим отношение эквивалентности на множестве  такое, что r подряд расположенных точек f_i+1 ,… f_i+r  множества ( f_i+1= <tⁱ⁺¹, s₁ⁱ⁺¹> ,… f_i+r=<t^i+r, s₁^i+r>) считаются эквивалентными, если s₁ⁱ⁺¹= s₁ⁱ⁺² = …=s₁^i+r

 r может принимать любые положительные целые значения, начиная от 1. Таким образом формируются классы эквивалентных значений K_Э . При r=1 класс содержит одну единственную точку.

4)               каждому классу эквивалентности K_Э на  ставим в соответствие одну точку  f_экв= <t_min, s_экв>   где  , s_экв=s₁ⁱ=… для всего класса К_Э

5)              формируем множество F₁ из элементов f_экв по всем классам эквивалентности на  , мощность F₁ равна количеству классов эквивалентности на .

6)              проецируя F₁ на T, получим множество T₁. Очевидно, что T₁T, сужение отношения α на T₁ обозначим α₁.

В результате выполнения вышеуказанных операций получим процесс :

Z₁=<, T₁, F₁, α₁>.

Пользуясь операцией проецирования, можно переопределить понятие подпроцесса:

Пример операции проецирования приведен на рис. 2. На нем показан исходный процесс Z, заданный в двухпараметрическом пространстве S=σ(А)хσ(В), где σ(А)={g, h, k, m, n}, σ(B)={a, b, c, d}. Ось времени не показана, однако значения моментов времени изменения состояний указаны в кружочках, обозначающих соответствующее состояние. Таким образом, как видно из рисунка, множество Т={1, 2, 3, 4, 5, 6, 7, 8, 9}.

Рисунок 2. Процесс Z в двухпараметрическом пространстве

График процесса F={<1,<g,a>, <2,<h,c,>, <3,<h,b>, <4,<k,a>, <5,<m,a>, <6,<m,d>, <7,<n,d>, <8,<n,b>, <9,<k,b>}

Построим процесс , являющийся проекцией процесса Z на пространство s(А), в соответствие с алгоритмом выполнения операции проецирования.

1) Строим график _А={<1,g>, <2,h>, <3,h>, <4,k>, <5,m>, <6,m>, <7,n>, <8,n>, <9,k>}

2) Множество _А уже упорядочено по времени. Получаем отображение процесса Z на пространство s(А), показанное на рис. 3.

Рисунок 3. Отображение процесса Z на параметр А

3) На множестве _А определяем классы эквивалентности: К₁ – точка 1, К₂ – точки 2,3, К₃ – точка 4, К₄ – точки 5,6, К₅ – точки 7,8, К₆ – точка 9.

4) Ставим в соответствие классу К₂ точку <2,h>, классу К₄ точку <5,m>, классу К₅ точку <7,n>.

5) Формируем график F_A={<1,g>, <2,h>, <4,k>, <5,m>, <7,n>, <9,k>}

6) Формируем множество времен изменения состояний Т_А=<1,2,4,5,7,9>

Полученный в результате проведенных операций процесс  показан на рис. 4.

Рисунок 4. Процесс Z_A – проекция процесса Z на параметр А

Аналогично строится и проекция процесса Z на параметр В (пространство, состоящее из единственного параметра). Процесс Z_B показан на рис. 5.

Рисунок 5. Отображение процесса Z на параметр В

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

Рисунок 6. Процесс Z_В - проекция процесса Z на параметр В

Операция объединения

Пространство S_Q называется склейкой пространств  и , если Q=Q₁Q₂. Интерес представляет случай непустого пересечения Q₁ и Q₂., когда пространства  и  имеют общую область.

Пусть кортеж s₁ принадлежит пространству , кортеж s₂ принадлежит пространству .Обозначим значения параметра q из кортежа s₁ как , а значение параметра q из кортежа s₂ как .

Тогда    s₁=<……>,      s₂=<……>.

Кортеж  s  является левой склейкой кортежей s₁ и s₂, когда:

s_л= <………>.

Правая склейка определяется как:

s_п= <………>.

Если s_л=s_п, то склейка называется функциональной.

Пусть заданы процессы Z₁=<, T₁, F₁, α₁> и Z₂=<, T₂, F₂, α₂>. Процесс Z=<, T, F, α> является объединением процессов Z₁ и Z₂ (обозначение Z= Z₁Z₂), если:

·   S_Q является склейкой пространств  и  

·   T= T₁T₂

·   для каждого t∈T строится: f_t=<t, s_t>, где s_t – склейка кортежей s¹_t (s¹_t∈) и s²_t (s²_t∈) , кортежи s¹_t и s²_t принадлежат соответственно графикам F₁ и F₂ для значения t

·   все склейки кортежей s¹_t и s²_t для всех t∈T являются функциональными

·   совокупность f_t для всех t∈T формирует график F

·   отношение α строится как транзитивное замыкание на α₁α₂.

Процессы Z₁ и Z₂ , допускающие операцию объединения, называются согласованными.

Можно доказать ряд утверждений

Утверждение 1.

Два процесса Z₁ с пространством состояний  и Z₂ с пространством состояний  согласованы, если Q₁ Q₂=Ø.

Утверждение 2.

Пусть задан процесс Z₁ с пространством состояний  и Z₂ с пространством состояний . Пусть в некоторой момент времени t состояние Z₁ равно s₁∈, а состояние Z₂ равно s₂∈. В общем случае будем полагать, что Q₁Q₂≠Ø. Обозначим Q₃=Q₁Q₂.

Если для всех моментов времени t∈T значения <……>=<……>, то процессы Z₁ и Z₂ –согласованы.

Утверждение 3.

Если  и , то процессы Z₁ и Z₂ согласованы.

Утверждение 4.

Пусть заданы процесс Z₁, определенный на интервале  , и Z₂, определенный на интервале .

Если  =Ø, то процессы Z₁ и Z₂ согласованы.

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

Литература

1. Бусленко Н.П., Калашников В.В., Коваленко И.Н. Лекции по теории сложных систем. - М.: Сов.Радио, 1973. - 438 с.

2. Черненький В.М. Процессно - ориентированная концепция системного моделирования АСУ: Дис...док. тех. наук.-М.,2000.-350с.