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

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

Выполнено исследование таких операций над процессами, каксвертка, развертка, проецирование, объединение. Материал опирается наспособ задания процесса, названный алгоритмической моделью процесса(АМП), включающий такие понятия, как элементарный оператор, трекоператоров и инициатор.

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

Под функционированиемсистемы понимается процесс изменения ее состояния во времени. В данномкурсе рассматривается способ описания такого процесса с учетом того, чтосистема имеет высокую размерность, разделяется на множество объектов,различным способом связанных между собой, руководствуется сложнымиалгоритмами, описывающими переход из одного состояния в другое.3Всюсовокупность параметров системы, определяющих процессфункционирования или участвующих в нем, назовем параметрическиммножеством системы Q  qi ni1 , где qi – некоторый параметр.

Каждыйпараметр qi принимает множество значений, обозначаемое в дальнейшем как(qi ).Например, выберем в качестве системы центральный процессор (ЦП) ижесткий диск (Д).Для ЦП определим следующие параметры:количество процессоров (КП)производительность одного процессора (ПОП)состояние процессора (СП)стоимость процессора (СтП).Для Д определим следующие параметры:скорость записи и считывания (СЗС)состояние диска (СД).Тогда множества значений параметров можно определить следующимобразом:(КП) = {1, 2};(ПОП) = {10, 50, 100, 500}, эти значения могут соответствовать какойлибо системе оценки производительности, например, обозначать среднееколичество тысяч операций за единицу времени;(СП) = {“работает”, “простаивает”, “тестируется”};(СтП) = {2 - 20}, эти значения стоимости могут быть выражены,например, в некоторых условных единицах;(СЗС) = {10 - 50}, эти показатели скорости операций на диске могутбыть заданы аналогично параметру ПОП;(СД) = {“работает”, “простаивает”, “ремонтируется”}.4ОпределимпроизведениепространствоS= П(qi).iсостоянийсистемыкакдекартовоВ этом пространстве каждый параметр выступает вроли координаты, а размерность пространства равна мощности множества Q.ЭлементпространстваSестьвозможноесостояниесистемы.Врассмотренном выше примере размерность пространства состояний равна 6, асамо пространство состояний имеет вид:S = (КП) х (ПОП) х (СП) х (СтП) х (СЗС) х (СД)Возможным состоянием системы sS может быть следующий кортеж:s = <2, 50, “простаивает”, 15, 40, “ремонтируется”>В дальнейшем нас будет интересовать процесс изменения состоянийсистемы во времени.

Примем за основу определение процесса, предложенноев работе [2].Процесс Z есть четверка:Z=< S, T, F,  >(1)где:S – пространство состояний системы, определенное ранее;T – множество моментов времени изменения состояний системы;F – график процесса, определяемый как отображение TS, причем этоотображение должно быть функциональным (однозначным); – отношение линейного порядка на T.Если множество T задано как упорядоченное, то в определении процесса может быть опущено.В общем случае множества T и S могут быть как дискретными, так инепрерывными.Интервалвремени [tН ,tК],интервалом определения процесса.где tН =min{T}, tК=max{T}, назовем5ПосколькунеобходимостипространствоподчеркнутьSкоординатногосистемутипа,координат Q,товслучаена которой оноопределено, будем обозначать его также SQ .В этих обозначениях, если множество Т задано, как упорядоченное, апространство S определено на множестве параметров Q, определить процессZ=< SQ , T, F >.Кортеж  ~x1 ...~x i ...~x n  , где ~xi - значения элементов множества X , будемможно как:обозначать как  ...

~x ...  .XОпределим фазовое пространство Ф процесса Z как Ф=TS .Тогда график F есть подмножество Ф.Если f  F, то f = <t,  ... ~q ...  >, где tT.QЕсли Q1 Q, то определим понятие проекции f на пространство SQ1 как:Пр SQ f = <t,  ... q~ ...  >. Проекцией f на T является t.1Q1Введем понятие подпроцесса Z i как плотное во времени подмножествопроцесса Z на интервале [ti ; tj ] при условии, что [ti ; tj ]  [tН , tК]. Плотность повремени означает, что на интервале [ti ; tj ] нет ни одной точки, принадлежащейТ и не относящейся к подпроцессу Z i . Этот интервал назовем интерваломопределения подпроцесса. Понятие подпроцесса позволяет рассматриватьпроцесс в виде последовательности подпроцессов и производить операцииразделения и объединения фрагментов процесса.2.

Операции над процессамиОперация свертки процессаПусть задан процесс Z=<S, T, F, >Процесс Z1 =<S1 , T1 , F 1 ,  1 > является сверткой процесса Z, если онполучен в результате следующих преобразований:6а) произведено полное разбиение интервала определения процесса Z на nнепересекающихся подинтервалов [j , j+1 ], где j=1..n, причем 1 =tН , n+1 =tК .В результате получим разбиение процесса Z на n подпроцессов Z j (j=1..n);б) поставим в соответствие каждому подпроцессу Zjодно значениесостояния s1j из множества S1 и одно значение времени j из интервалаn[j , j+1 ]. В результате получим дискретное множество T 1   j  j  1 , графикn j  1 , отношение  1 .F1    j , s1j Таким образом, получим новый процесс Z1 , который и называетсясверткой процесса Z. Очевидно, процесс Z1 дискретен во времени. Никакихограничений на характер пространства состояний S1 не накладывается.

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

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

В результате получим процесс Z1 с пространством состояний S1,множеством моментов времени изменения состояния Т1={0, t1, t7, t8, t10}.График этого процесса приведен на этом же рисунке.Как видно из примера, операция свертки порождает новый процесс,дискретный во времени, поскольку подпроцессы процесса Z, имеющиеконечную длительность, отображаются лишь на одну точку фазовойплоскости нового процесса Z1.Операция свертки относится к классу операций анализа.Операция разверткиОперация развертки обратна по отношению к операции свертки: процессZ является разверткой процесса Z1 .

При выполнении этой операциинеобходимо каждую точку  j , S1j процесса Z1 развернуть в подпроцесс Z j .Поставим каждому jв соответствие интервал [ j , j+1 ], при условии,что:j  j j+1и [ j , j+1 ]= .j(2)Зададим отображение B j : [ j , j+1 ]  S. Отображение B j позволяетполучить фазовую траекторию подпроцесса Z j . Для построения процесса Z вцелом необходимо задать все B j (j=1,..,n). Операция развертки позволяетвосстановить исходный процесс на основе некоторых представлений освернутых процессах.Операция развертки относится к классу операций синтеза.9Операция проецированияПроцесс Z1 является проекцией процесса Z на координатное пространствоSQ1(обозначениеZ1  Пр SQ Z ), если Q1 Q и процесс построен по1следующей процедуре:1) каждую точку графика F проецируем на пространство SQ1 .

В результатеполучаем множество F . Мощность множества F равна мощностимножества F ;2) упорядочиваеммножествоFвсоответствиес.Результат действий 1) и 2) будем называть отображением процесса Zна пространство SQ1 ;3) вводим отношение эквивалентности на множестве F такое, что rподряд расположенных точек f i+1 ,… f i+rмножества F ( f i+1 = <ti+1 ,s1 i+1 > ,… f i+r=<ti+r, s1 i+r>) считаются эквивалентными, если s1 i+1 = s1 i+2 =…=s1 i+rr может принимать любые положительные целые значения, начиная от 1.Таким образом формируются классы эквивалентных значений KЭ . Приr=1 класс содержит одну единственную точку.4) каждому классу эквивалентности KЭ на F ставим в соответствие однуточку f экв= <tmin , sэкв>где tmin  min t , sэкв=s1 i =… для всего класса ti K ЭКЭ .5) формируем множество F 1 из элементов f экв по всем классамэквивалентности на F , мощность F 1 равна количеству классовэквивалентности на F .106) проецируя F 1 на T, получим множество T1 .

Очевидно, что T1 T,сужение отношения  на T1 обозначим  1 .В результате выполнения вышеуказанных операций получим процессZ1  Пр SQ Z :1Z1 =< SQ1 , T1 , F 1 ,  1 >.Пользуясь операцией проецирования, можно переопределить понятиеподпроцесса:Z t1 ,t2   Прt1 ,t2 ZРисунок 2.

Процесс Z в двухпараметрическом пространствеПример операции проецирования приведен на рисунке 2. На нем показанисходный процесс Z, заданный в двухпараметрическом пространствеS=(А)х(В), где (А)={g, h, k, m, n}, (B)={a, b, c, d}. Ось времени непоказана, однако значения моментов времени изменения состояний указаны в11кружочках, обозначающих соответствующее состояние. Таким образом, каквидно из рисунка, множество Т={1, 2, 3, 4, 5, 6, 7, 8, 9}.График процесса 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 A  Пр s Z , являющийся проекцией процесса Z наAпространство (А), в соответствие с алгоритмом выполнения операциипроецирования.1) Строим график F А ={<1,g>, <2,h>, <3,h>, <4,k>, <5,m>, <6,m>,<7,n>, <8,n>, <9,k>}2) Множество F А уже упорядочено по времени.

Получаем отображениепроцесса Z на пространство (А), показанное на рисунке 3.Рисунок 3. Отображение процесса Z на параметр А3) На множестве F А определяем классы эквивалентности: К1 – точка 1,К2 – точки 2,3, К3 – точка 4, К4 – точки 5,6, К5 – точки 7,8, К6 – точка 9.4) Ставим в соответствие классу К2 точку <2,h>, классу К4 точку <5,m>,классу К5 точку <7,n>.5) Формируем график FA ={<1,g>, <2,h>, <4,k>, <5,m>, <7,n>, <9,k>}6) Формируем множество времен изменения состояний Т А =<1,2,4,5,7,9>12Полученный в результате проведенных операций процесс Z A  Пр s ZAпоказан на рисунке 4.Рисунок 4.