русс | укр

Языки программирования

ПаскальСиАссемблерJavaMatlabPhpHtmlJavaScriptCSSC#DelphiТурбо Пролог

Компьютерные сетиСистемное программное обеспечениеИнформационные технологииПрограммирование

Все о программировании


Linux Unix Алгоритмические языки Аналоговые и гибридные вычислительные устройства Архитектура микроконтроллеров Введение в разработку распределенных информационных систем Введение в численные методы Дискретная математика Информационное обслуживание пользователей Информация и моделирование в управлении производством Компьютерная графика Математическое и компьютерное моделирование Моделирование Нейрокомпьютеры Проектирование программ диагностики компьютерных систем и сетей Проектирование системных программ Системы счисления Теория статистики Теория оптимизации Уроки AutoCAD 3D Уроки базы данных Access Уроки Orcad Цифровые автоматы Шпаргалки по компьютеру Шпаргалки по программированию Экспертные системы Элементы теории информации

Модификации сетей Петри

   Временная сеть Петри

Такая сеть позволяет более реалистично отражать процессы в ВС. Во временных сетях каждому переходу tj сопоставляется время Tj. Если переход возбуждается, то метки, вызвавшие запуск перехода, покидают входные позиции Pre(tj). Порождение меток в выходных позициях Post(tj) происходит через время Tj.

Формальное определение временной сети:
TN = {N, T}
где N - сеть Петри; T:  -функция времён срабатывания, сопоставляющая каждому переходу постоянное время срабатывания; R0 - множество неотрицательных рациональных чисел.

 

Сеть с приоритетами переходов

Формальное определение:
PRN = {N, PR}
где N - сеть Петри; PR - отношение приоритетности (порядка), задаваемое на множестве переходов Т и определяющее порядок потребления меток возбуждёнными переходами в условиях конфликта за метку.

 

Временная сеть с приоритетами переходов

Такая сеть объединяет элементы, описанные в рассмотренных выше классах сетей.

Формальное определение:
PRTN = {N, T, PR}
Пример модели взаимодействия между узлами сети ЭВМ, описывающей протокол связи с исправлением ошибки. Протокол предусматривает подтверждение приёма посланного сообщения, повторение передачи при потере сообщения и соответствует упрощенной версии реального протокола.

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

Переходам tj сопоставлены времена Tj, отражающие длительность выполнения соответствующих действий в системе обработки и обмена, генераторах помех и тайм-аута. отношения приоритетности введены для двух пар переходов – (t­2,t8) и (t7,t11), поскольку только по отношению к ним может возникнуть конфликт за метку. Они имеют вид:

PR(t8) > PR(t2)      и       PR(t7) > PR(t11)

 

vrem_set_s_priopit

ПрИ – процессор-источник;
ПрП – процессор-приёмник;
ГТ – генератор тайм-аута;
ИП – источник помех;
t1 - передача сообщений в буфер обмена; t2 - приём сообщения; t3 - посылка подтверждения о приёме данных; t4 - приём подтверждения; t5 - обработка данных в ПрИ; t6 - обработка в ПрП; t7 - повторение передачи; t8, t9 - переходы модели источника помех; t10, t11 - элементы ГТ;
P1 - конец обработки в ПрИ и запрос действия t1; P2 - буфер сообщения; P3 - ПрП готов принять сообщение и запрашивает t2; P4 - ПрИ ожидает подтверждения; P5 - завершение действия t2 и запуск t3; P6 - запрос t6; P7 - буфер подтверждения;  P8 - запрос t5; P9, P10 - позиции ГТ; P11, P12 - позиции ИП

Передача сообщения процессором-источником порождает буферирование копии сообщения и запуск генератора тайм-аута, посылку сообщения в канал, а также формирование условия подтверждения о приёме, что отражается появлением меток в P2, P4, P9. Если сообщение в канале P32 исчезнет благодаря действию ИП (что отражается возбуждением t8), то не приходит подтверждение приёма (метка в P7 не появится), и через время тайм-аута (связанное с t10) произойдёт повторная выдача сообщения в канал (что отражается срабатыванием t7). С t9 связан интервал времени между потерей в канале очередного сообщения и возникновением условия для потери следующего сообщения. С t10 связано время тайм-аута, через которое организуется повторная посылка потерянного сообщения. Если через T10 в P4 нет метки, то не создадутся условия возбуждения t7 и метка из P10 покинет ГТ.

На рисунке изображён граф допустимых маркирований элементов модели ПрП и ПрИ. В вершинах графа состояний перечислены наборы позиций, в которых одновременно находятся метки-сообщения (при начальном маркировании M0). Ориентированные дуги указывают переходы между состояниями системы, а пометки у дуг указывают переходы между состояниями системы, а пометки у дуг указывают на переходы  t, срабатывание которых вызывает данное изменение состояния.

graf_markirovaniy

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

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

 

Раскрашенные сети

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

Метками раскрашенной сети приписывают атрибуты, которые называют цветами. Правила возбуждения переходов дополняются условиями, предполагающими выбор меток определённых цветов из позиций Pre(tj). Срабатывание переходов сопровождается посылкой в позиции Post(tj) меток, с задаваемыми значениями цвета.

 

RS_primer1 

t1, t2 - загрузка процессоров
t3, t4 - обработка
t5, t6 - освобождение процессоров
P0  - позиция супервизора
P1, P2 - заявки на обработку
P3, P4 - Заявки приняты
P5, P6 - конец обработки
P7, P8 - обработанные заявки
P9, P10 - двоичные семафоры,
исключающие попытки запустить
занятые процессоры.

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

Начальный цвет метки в P0 равен C1 и дуга (P0,t­1) окрашена в C1. Поэтому условие возбуждения выполнимо для перехода t1. После срабатывания t1 в P0 метка возвращается, уже имея цвет C2, поскольку дуга (t1,P0) раскрашена в цвет C2.

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

супервизора представлен последовательностью срабатывания переходов t1, t2 (t3, t4) t5, t6, т. е. происходит запуск первого процессора, затем второго, после чего следует их освобождение и цикл повторяется.
RS_primer2a

В примере 2 раскрашенная сеть используется для представления мультипрограммного выполнения алгоритма с ветвями и точкой синхронизации в ВС с процессором и УВВ.
а) – граф алгоритма
б) – биграф алгоритма
в) – модель мультипрограммного выполнения алгоритмов, представленная раскрашенной сетью.

На Пр и УВВ параллельно могут выполняться операторы 2 и 3, завершение которых является условием выполнения оператора 0 (что видно из Рис.а). Переходы t0 – t3 биграфа (Рис. б) соответствуют вершинам графа на (Рис. а). Для отображения точки входа в алгоритм на его биграфе введена маркированная позиция P1, поэтому нулевой вершине графа (Рис. а) поставлены в соответствие переходы t0 и t4 биграфа. При построении сети (Рис. в) учтено, что время выполнения операций t1 и t4 мало по сравнению с остальными. Учитывая также, что действия t0 и t2 выполняются на процессоре, позиции P1 и P5, а также P2 и P6 биграфа совмещены на (Рис. в) и обозначены как P1 и P2. Процессы выполнения алгоритмов представлены движением меток. Раскраска меток двухэлементная, определяющая номер процесса a = {1, 2, 3} и номер этапа обработки C = {C0, C1, C2, C3}.

Из (Рис. в) видно, что некоторые из дуг раскрашены одним цветом (Ci), другие парой цветов (aCi), третьи не раскрашены вовсе, что учитывается при управлении возбуждением переходов и изменении цвета меток. Заметим, что при раскрашивании парой цветов все эти признаки анализируются или изменяются в комплексе. Например, входные дуги перехода t4 помечены парами aC2 и aC3, что определяет выбор для синхронизации на t4 процессов с одним и тем же номером a и завершенными этапами обработки C2 и C3 соответственно.

Следующий пример 3 показывает изобразительные возможности раскрашенных сетей по разделению путей данных и управления в УВВ. Данные от двух источников U1 и U2 помечены квадратами в P1 и P3, а сигналы запроса на обработку – кружками в P2 и P4. Запросы принимаются  (переходы t1, t2), накапливаются в регистре (позиция P5), выбираются из неё (переход t3) и запускают пересылку данных от источников (P1 или P3) в буфер P7. Метка-треугольник в позиции P8 отражает управляющий процесс, разрешающий выполнение только одной из двух операций считывания t4 или  t5.

ПРИМЕР 3

RS_primer3

Таким образом, процедура раскраски сети Петри – это модельный способ трактовки различных по характеру реальных элементов:
- в  алгоритмах – номера оператора или этапа обработки;
- в мультипрограммных системах – номера задачи, её приоритета и других атрибутов;
- для ресурсов – их типа, способы использования и т. п.

 

Приоритетные раскрашенные сети

В таких сетях приоритетность необходимо определять и по отношению к меткам. Для этого задают отношения приоритетности на множестве цветов и сопоставляют их определённым дугам (Pitj). Правила возбуждения перехода tj реализуют приоритетный выбор метки для возбуждения перехода на основе значения соответствующего атрибута-приоритета (цвета) метки.

Приоритетные раскрашенные сети адекватно представляют приоритетное обслуживание процессов.

Например, спецификация правил приоритетного обслуживания для модели мультипрограммного выполнения алгоритма (ПРИМЕР 2) включает определение отношения порядка (приоритетности) на множестве номеров задач a = {1, 2, 3}. Сопоставление этого правила дугам (P1t0) и (P3t3) указывает на приоритетность выбора процесса для выполнения процессором и объектом управления.

Аналогично задаётся отношение порядка на множестве признаков  представленных на Рис. графически. Правило выбора сопоставляется дуге (P5t3) этой модели.

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

Просмотров: 8194

Вернуться в оглавление:Моделирование




Карта сайта Карта сайта укр


Уроки php mysql Программирование

Онлайн система счисления Калькулятор онлайн обычный Инженерный калькулятор онлайн Замена русских букв на английские для вебмастеров Замена русских букв на английские

Аппаратное и программное обеспечение Графика и компьютерная сфера Интегрированная геоинформационная система Интернет Компьютер Комплектующие компьютера Лекции Методы и средства измерений неэлектрических величин Обслуживание компьютерных и периферийных устройств Операционные системы Параллельное программирование Проектирование электронных средств Периферийные устройства Полезные ресурсы для программистов Программы для программистов Статьи для программистов Cтруктура и организация данных


 


Не нашли то, что искали? Google вам в помощь!

 
 

© life-prog.ru При использовании материалов прямая ссылка на сайт обязательна.