Иерархическая структуризация сетевых моделей подсистем ввода-вывода ЭВМ

Размещено на http://www.allbest.ru/

ИЕРАРХИЧЕСКАЯ СТРУКТУРИЗАЦИЯ СЕТЕВЫХ МОДЕЛЕЙ ПОДСИСТЕМ ВВОДА-ВЫВОДА ЭВМ

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

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

На рис. 1 приведен пример представления следующих элементов: а) позиции; б) перехода, в) не терминала и г) “оболочки” макроопределения, представляющей внешнюю среду или окружение. Через контакты “оболочки” осуществляется взаимодействие с внешним миром. Контакты на рис. 1 выделены точками.

Рис. 1

Для описания иерархической графовой структуры можно воспользоваться схемами сопряжения [2, 3]. Для этого введем структурные метапеременные, значениями которых являются переменные следующих типов: P-позиции, Т-переходы, S - нетерминалы, О - “оболочка”. Введенные метапеременные обозначим С. Математической моделью элемента Сj (рис. 2), используемого для формального описания сопряжения его с прочими элементами системы и внешней средой, является пара множеств [Xi(j)]1m и [Yi(j)]1t входных и выходных контактов.

Рис. 2

Схема сопряжения содержит множество входных и выходных контактов всех элементов системы и внешней среды и операторы сопряжения на вес уровнях иерархии. Это так называемые схемы сопряжения в канонической форме, основанные на понятиях контакта и элементарного канала. В них накладываются некоторые ограничения на число подключаемых к контактам элементарных каналов.

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

Определим сетевое макроопределение, используя понятие графа, дополняя его структурными и описательными функциями.

Орграф - это двойка (V,E), где V - конечное множеств вершин, EН VXV- множество ребер. Пусть N - множеств элементов сетевого макроопределения; f:V® N - сюръективное отображение множества вершин на множество элементов. Ядро этого отображения Ker f является разбиением множества контактов по отдельным элементам.

Произведем следующую классификацию элементов из множества N:

N=N_{S ?} N_{T ?} N_{P ?} {n_o};

N_{S ?} N_{T ?} N_{P ?} {n_o}=?

где N_S-множество нетерминалов; N_T-множество переходов; N_P-множество позиций; n_o - элемент “оболочка”.

Обозначим ? ^-1 как k, тогда V_S = k(N_S) - множество контактов нетерминалов; V_T = k(N_T) - множество контактов переходов; V_Р = k(N_Р) - множество контактов позиций (|V_P| = |N_P|); V_О = k(n_O) множество контактов „оболочки"; V_S=V_S'^? V_S''; V_S'^? V_S''= ? - множество контактов нетерминалов делится на множество входных V_S' и выходных V_S''контактов; V_О=V_О'^? V_S''; V_О'^? V_О''= ? - множество контактов „оболочки" делится на множество входных V_О' и выходных V_О'' контактов;

?: N_S? V_S ? ? - функция разметки нетерминалов и их контактов, где ? - множество меток.

Структура сетевого макроопределения является атрибутной, т. е. вершинам, элементам, дугам могут быть приписаны атрибуты. Рассмотрим два множества атрибутов, а именно: множество атрибутов элементов А и множество атрибутов дуг В. Обозначим ?:N? 2^A - функция, которая связывает множество атрибутов элементов с каждым элементом; ?:Е? 2^B - функция, которая связывает множество атрибутов ребер с каждым ребром. Из этого следует, что сетевое макроопределение состоит из чисто структурной части, заданной объектами N, V, E, ?, ? и семантической компоненты, которая определяется атрибутами каждого элемента и ребра.

Для последующей имитации многоуровневую сетевую модель необходимо привести к одноуровневому представлению, которое включает в себя только прямые связи между терминальными элементами (т.е. без посредства контактов нетерминальных элементов). Процесс перехода к одноуровневому представлению назовем генерацией или компоновкой. Этот процесс естественно описывается графовыми грамматиками (ГГ), в которых предусматривается механизм для генерации множества графов. В терминах ГГ можно описывать эквивалентные структурные преобразования [3], в частности переход от многоуровневой схемы сопряжения к одноуровневой, определив для этого подходящую ГГ. Помимо этого, ГГ могут служить средством для спецификации систем, представленных в виде иерархически связанных графов. Известно несколько видов графовых грамматик. Наиболее простые из них основаны на правилах замены узла или дуги графа некоторым подграфом.

Определим модель ГГ, в которой будем описывать представляемую систему. Наиболее подходящей является ГГ с заменой узлов. Существующие. ГГ этого вида, например NLC-графовые грамматики, не подходят из-за специфичности введенной выше графовой структуры.

Вводимая ГГ имеет следующие особенности.

В области замены: ГГ будет с заменой узлов элементов; замена элемента зависит только от его метки. В области встраивания: правила встраивания являются глобальными, т, е. механизм встраивания предусмотрен для целой грамматики, а не для каждой продукции индивидуально; связываются только вершины, которые являются прямыми соседями заменяемого элемента в основном графе с теми вершинами в заменяющем графе, которые связаны с его “оболочкой”, что является только необходимым условием для того, чтобы две вершины были соединены; будут ли они действительно связаны, зависит только от меток контактов, с которыми соединены вершины; ГГ является атрибутной. Атрибуты связываются с синтаксическими элементами продукции. Правила вычисления атрибутов являются фиксированными и общими для всех продукций.

ГГ определим как четверку

G=(?,?,P,S),

где

· ? - конечное множество меток;

· ? - собственное подмножество ?, называемое терминальными метками;

· P- конечное множество продукций. Каждая продукция должна быть задана в форме (d,D), где d? ? -?, D? G?, G? означает множество всех графов (вернее графовых структур, определенных выше) с узловыми метками из ? ;

· S - специальный нетерминал, называемый начальным.

Путь, в котором продукция (d,D) применяется для трансформации графа M, следующий (граф M назовем основным).

Шаг 1: Найти появление узла с меткой d в графе M, т. е. должен существовать такой узел n, что ? _M(n)=d. Назовем узел n порождающим. Множество узлов, которые непосредственно связаны с порождающим узлом (точнее с его контактами), назовем соседями.

Шаг 2: Добавить к графу M граф? D, изоморфный графу D. Граф ? D будет называться дочерним.

Шаг 3: Используя некоторый фиксированный алгоритм, встроить подграф ? D в основной граф M. В результате встраивания основной граф М преобразуется к графу ? M . Рассмотрим более подробно процедуру встраивания.

Обозначим EMB (D,? M \? D) - множество ребер между дочерним графом и графом, т. е. множество связей, соединяющих граф? D с окружением:

EMB (? D, ? M \? D) = {(x, y) \ x? V_{(? D)}, y? V_{(? M\? D),} {z",y}? E_(M), z"? V"_S(n), {x, z'}? E_{(? D)}, z'? V"_{O(? D)}, ? {z'}=? (z")}? {(x, y) \ x ? V_{(? M\? D),} y ? V_{(? D)}, {x, z"}? E_(M), z"? V's(n), {z", y}? E_{(? D)}, z'? V_{O(? D)}, ? (z")= ? (z')}.

Индекс в скобках ограничивает множество теми элементами, которые принадлежат объекту - индексу. В нижней части рис.3 схематично приведен пример встраивания графа D в граф М. В нижней части рисунка представлена примененная к графу M функция. Пунктирными линиями изображены связи, сгенерированные при встраивании.

Шаг 4: Удалить порождающий узел n в основном графе (удаляя все связанные c ним ребра). Удалить “оболочку” дочернего графа (удаляя при этом все принадлежащие ей контакты с инцидентными им ребрами). В примере, представленном на рис. 3, удаляются ребра (x1, z1), (x2, z1), (z2, y).

Таким образом, при замене узла n основного графа M графом ? D получается граф ? M:

?M = (M ? ? D ? EMB (? D, ? M \ ? D)) \ (n? n_{O(? D)}),

где n_{O(? D)} - оболочка графа ? D.

Пишем M ? ? M, чтобы обозначить отношение „? M непосредственно выводится из M в G" Если существует конечная последовательность преобразований M_О? M_1? …? M_m, тогда пишем M_О *? M_m и говорим, что M_m выводится из M_О в G.

Конечная последовательность называется выводом длиной m. Язык, генерируемый грамматикой G - множество графов с терминальными метками, которые могут быть выведены из начального графа с меткой S, такой, что L (G) = {M? G? \S *? M}.

Рис. 3

сетевой модель графовой структура

Для однозначности и конечности процесса генерации сетевой модели необходимо выполнение определенных условий, которые легко устанавливаются. Язык L(G) в этом случае будет состоять из единственного графа.

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

С каждой продукцией связываются правила вычисления атрибутов. Рассмотрим только те атрибуты, которые участвуют в правилах вычисления: pr - приоритет синтаксического элемента; коrrpr - коррекция приоритета (может быть как положительной, так и отрицательной); ar - тип приоритета (0-абсолютный. 1? относительный). Эти атрибуты приписываются нетерминальным элементам и некоторым терминальным элементам (переходам). Следуя терминологии атрибутных строковых грамматик, будем классифицировать атрибуты на синтезируемые и наследуемые. Для определяемой генерирующей ГГ дополнительно вводим собственные атрибуты для нетерминальных элементов. В каждом графе нетерминал может иметь различные по значению собственные атрибуты. Собственные атрибуты в процессе генерации не изменяются. В нашем случае рr - наследуемый атрибут, а коrrрr и ar - собственные. Пусть рr (b) - приоритет нетерминала b в левой части продукции; рr {п), коrrрr {п), аr (n) - атрибуты узла n? N_{S ?} N_T правой части продукции. Правила вычисления атрибутов будут таковы:

Приписывание приоритетов нетерминалам является удобным механизмом назначения приоритетов группам переходов, обычно представляющих какую-то определенную подмодель. Считается, что начальный нетерминал имеет абсолютный приоритет, равный нулю.

Описанная выше ГГ для генерации одноуровневой модели реализована в комплексе программ КОМПОНОВЩИК. КОМПОНОВЩИК может производить полную или неполную генерацию. Неполностью сгенерированную структуру, т. е. такую, в которой не все элементы являются терминальными, можно назвать сентенциальной формой. Каждый граф (вернее, сетевое макроопределение) в системе хранится в разделе библиотеки. Поэтому для его идентификации можно указать конструкцию вида: <имя библиотеки>.<имя раздела библиотеки>. Представление сетевого макроопределения в алфавите ГГ формируется транслятором с языка описания моделей. Многоуровневая модель определяется с помощью продукций. Возможно явное и неявное их задание. Для связи с КОМПОНОВЩИКОМ используется следующее предложение директивного языка (языка описания задания), записанное в форме РБНФ:

# COMPACK <A>,<M>{USE = <B>(<C>.<D> {,<C>.<D>})? NOUSE = <E>{,<E>}}{LE = <F>}¹

где <A>, <M> - соответственно DD-имя библиотеки и имя раздела, где хранится начальное сетевое макроопределение;

<В>, <С> - соответственно DD-имя библиотеки и имя раздела, где хранится сетевое макроопределение правой части продукции, заданной явным образом;

<D> - метка нетерминала левой части этой продукции;

<Е> - имя метки нетерминала, который запрещен для замены;

<F>={1? 2? 3} -максимально допустимый уровень ошибок. при котором еще продолжается генерация.

Для выгрузки сгенерированной структуры во внешнюю память можно воспользоваться командой #UNLOAD <P>, <Q>, где <P> - DD-имя библиотеки, в которую выгружается структура; <Q> - имя раздела библиотеки.

В заключение отметим макросредства, используемые в других сетевых моделях. В КОМБИ-сетях для поддержки иерархического проектирования были введены K-переходы и K-позиции [б]. При этом K-переход “обрамлен” только переходами, а граничными элементами K-позиции являются только позиции, Представленное выше макросредство является более общим в том смысле, что граничными элементами нетерминала могут быть как позиции, так и переходы. Макро сети описаны в работе [7].

ЛИТЕРАТУРА

1. Котов В.Е. Сети Петри. - М.: Наука, 1984. - 157 с.

2. Бусленко Н.П. Моделирoвaние сложных систем. - М.- Наука, 1978. - 399 с.

3. Бусленко В.Н. Автоматизация имитационного моделирования сложных систем. - М,: Наука, 1977. - 238 с.

4. Проектирование подсистем внешних запоминающих устройств с прямым доступом на основе сетевых моделей // П. Вашкевич, В.Н. Дубинин, С.А. Зинкин, Б.М. Рaков. - Вопросы радиоэлектроники, сер. ЭВТ, 1984, вып. 13, с.78-82.

5. D. Janssens, G. Rozenberg. Graph grammars with node-label controlled rewriting and embedding. - „Lecture Notes in Computer Seience", 1983, v. 153, pp. 186-205.

6. H.D. Gerhardt. KOMBI - Netze. Еine Petri-Netzervweilerung zur Besclireibung kombinierter mathematischer Modelle. „Wissenschaftliche Zeitschrift der Humboldt-Universitat zu Berlin", 1981, t. 30, № 5, ss. 463-471.

7. J.D. Noe, G.1.Nutt. Macro E-nets for Representation of Parallel Systems. „IEEE Transactions on computers", v.С -22, № 8, 1973.

Размещено на Allbest.ru