Logo GenDocs.ru

Поиск по сайту:  

Загрузка...

Лекции по моделированию систем - файл Сетевые модели.doc


Загрузка...
Лекции по моделированию систем
скачать (1799.4 kb.)

Доступные файлы (18):

10_Псевдослучайные числа, процедуры их получения.doc127kb.31.03.2005 20:30скачать
11_Моделирование случайных воздействий.doc302kb.21.04.2005 22:59скачать
12_Приближенные способы преобразования.doc279kb.22.04.2005 01:52скачать
13_Имитационное моделирование.doc505kb.28.04.2005 15:43скачать
14_Характеристики мод-х систем и типовые схемы.doc1157kb.04.05.2005 23:18скачать
15_Планирование экспериментов.doc236kb.12.05.2005 16:07скачать
1_введение.doc207kb.07.01.2005 19:19скачать
1_общ_вопр_мод.DOC105kb.26.01.2005 11:17скачать
2_матем_мет_мод.doc89kb.22.02.2005 11:16скачать
3_Сетевые модели.doc21kb.08.02.2005 18:48скачать
6_Системы массового обслуживания.doc234kb.02.03.2005 23:51скачать
7_Сетевые модели Сети Петри.doc264kb.11.03.2005 10:17скачать
8_Обощенные модели А-схемы.doc206kb.18.03.2005 01:16скачать
9_Концептуальные, алгоритмические, статические модели.doc90kb.25.03.2005 13:09скачать
P-схемы.doc137kb.24.02.2005 22:48скачать
Модели данных.doc26kb.08.02.2005 14:10скачать
Непрерывно детерминированные модели.doc58kb.22.02.2005 17:07скачать
Сетевые модели.doc379kb.08.02.2005 18:42скачать

Сетевые модели.doc

Реклама MarketGid:
Загрузка...
ИЕРАРХИЧЕСКАЯ СТРУКТУРИЗАЦИЯ СЕТЕВЫХ МОДЕЛЕЙ ПОДСИСТЕМ ВВОДА-ВЫВОДА ЭВМ

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

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

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

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

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

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

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

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

N=NS NT NP {no};

NS NT NP {no}= ,

где NS-множество нетерминалов; NT-множество переходов; NP-множество позиций; no - элемент “оболочка”.

Обозначим  -1 как k, тогда VS = k(NS) - множество контактов нетерминалов; VT = k(NT) - множество контактов переходов; VР = k(NР) - множество контактов позиций (|VP| = |NP|); VО = k(nO) множество контактов „оболочки"; VS=VS VS’’; VS VS’’= - множество контактов нетерминалов делится на множество входных VS и выходных VS’’контактов; VО=VО VS’’; VО VО’’= - множество контактов „оболочки" делится на множество входных VО и выходных VО’’ контактов;

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

Структура сетевого макроопределения является атрибутной, т. е. вершинам, элементам, дугам могут быть приписаны атрибуты. Рассмотрим два множества атрибутов, а именно: множество атрибутов элементов А и множество атрибутов дуг В. Обозначим  :N 2A - функция, которая связывает множество атрибутов элементов с каждым элементом;  2B - функция, которая связывает множество атрибутов ребер с каждым ребром. Из этого следует, что сетевое макроопределение состоит из чисто структурной части, заданной объектами 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’ VO( 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 nO( D)),

где nO( D) - оболочка графа  D.

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

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

 



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

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

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



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

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

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

где <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.







Скачать файл (1799.4 kb.)

Поиск по сайту:  

© gendocs.ru
При копировании укажите ссылку.
обратиться к администрации