Главная Случайная страница


Полезное:

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


Категории:

АрхитектураАстрономияБиологияГеографияГеологияИнформатикаИскусствоИсторияКулинарияКультураМаркетингМатематикаМедицинаМенеджментОхрана трудаПравоПроизводствоПсихологияРелигияСоциологияСпортТехникаФизикаФилософияХимияЭкологияЭкономикаЭлектроника






Сети Петри для моделирования





 

События и условия.

Простое представление системы сетью Петри основано на двух основополагающих понятиях: событиях и условиях. События — это действия, имеющие место в системе. Возникновением событий управляет состояние системы Состояние системы может быть описано множеством условий. Условие может принимать либо значение «истина», либо значение «ложь». Для того чтобы событие произошло, необходимо выполнение соответствующих условий. Эти условия называются предусловиями события. Возникновение события может вызвать нарушение предусловий и может привести к выполнению других условий, постусловий.

В качестве примера рассмотрим задачу моделирования простого автомата-продавца. Автомат-продавец находится в состоянии ожидания до тех пор, пока не появится заказ, который он выполняет и посылает на доставку.

Условиями для такой системы являются:

а) автомат-продавец ждет;

б) заказ прибыл и ждет;

в) автомат-продавец выполняет заказ;

г) заказ выполнен.

Событиями будут:

1. Заказ поступил.

2. Автомат-продавец начинает выполнение заказа.

3 Автомат-продавец заканчивает выполнение заказа.

4. Заказ посылается на доставку.

Таблица предусловий и постусловий:

 

 

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

Сеть Петри на рис.6.1 иллюстрирует модель приведенного выше автомата-продавца.

 

 

Рис 6.1: Сеть Петри для простого автомата-продавца.

 

Более сложная система. Система автоавтомат-продавец состоит из трех различных автоматов M1, М2 и М3 и двух операторов F1 и F2. Оператор F1 воздействует на автоматы М1 и М2, а оператор F2 — на М1 и М3. Заказы требуют двух стадий обработки. Сначала они должны быть обработаны автоматом М1, затем либо автоматом М2 либо М3. Эта система будет иметь следующие условия:

а) заказ прибыл и ждет обработки автоматом М1.

б) заказ обработан автоматом М1 и ждет обработки либо автоматом М2, либо М3;

в) заказ выполнен;

г) автомат M1 незанят;

д) автомат М2 незанят;

е) автомат М3 незанят;

ж) оператор F1 незанят;

з) оператор F2 незанят;

и) автомат М1 находится под воздействием оператора F1;

к) автомат М1 находится под воздействием оператора F2,

л) автомат М2 находится под воздействием оператора F1,

м) автомат М3 находится под воздействием оператора F2.

При этом могут происходить следующие события:

1. Поступление заказа.

2. Оператор F1 начинает выполнение заказа на автомате M1

3. Оператор F1 закончил выполнение заказа на автомате М1.

4. Оператор F2 начинает выполнение заказа на автомате М1.

5. Оператор F2 закончил выполнение заказа на автомате М1.

6. Оператор F1 начинает выполнение заказа на М2.

7. Оператор F1 закончил выполнение заказа на М2.

8. Оператор F2 начинает выполнение заказа на М3.

9. Оператор F2 закончил выполнение заказа на М3.

10. Заказ посылается на доставку.

Таблица предусловий и постусловий:

 

 

 

Рис 6.2: Сеть Петри для сложного автомата-продавца.

 

Одновременность и конфликт.

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

В сети Петри отсутствует измерение времени или течение времени. Выполнение сети Петри (или поведение моделируемой системы) рассматривается как последовательность дискретных событий. Порядок появления событий является одним из возможных, допускаемых основной структурой. Это приводит к явной недетерминированности в выполнении сети Петри. Если в какой-то момент времени разрешено более одного перехода, то любой из нескольких возможных переходов может стать «следующим» запускаемым. Выбор запускаемого перехода осуществляется недетерминированным образом, т. е. случайно. Эта особенность сети Петри отражает тот факт, что в реальной жизненной ситуации, где несколько действий происходит одновременно, возникающий порядок появления событий — не однозначен; может возникнуть любая из множества последовательностей событий. Однако частичный порядок появления события — единственен.

Для простоты обычно вводят следующее ограничение. Запуск перехода (и соответствующего события) рассматривается как мгновенное событие, занимающее нулевое время, и возникновение двух событий одновременно невозможно. Моделируемое таким образом событие называется примитивным; примитивные события мгновенны и неодновременны.

 

Рис 6.3: Понятие одновременности и конфликта в Сетях Петри.

 

Аппаратное обеспечение ЭВМ.

ЭВМ с конвейерной обработкой.

Конвейер состоит из набора операций, которые могут выполняться одновременно. Когда операция k завершается, она передает свой результат операции (k + 1) и ожидает от операции (k — 1) нового задания.

Для управления блоком k асинхронного конвейера необходимо знать, когда выполняются следующие условия:

• входной регистр заполнен;

• входной регистр пуст;

• выходной регистр заполнен;

• выходной регистр пуст;

• блок занят;

• блок свободен;

• пересылка осуществлена.

 

 

Рис 6.4: Модель сети Петри устройства управления асинхронной ЭВМ с конвейерной обработкой.

 

Кратные функциональные блоки.

Каждому функциональному блоку и каждому регистру поставим в соответствие позицию: если блок или регистр свободен — в позицию будет помещена фишка, если нет — фишки в позиции не будет. Кратные идентичные функциональные блоки показываются соответствующим числом фишек в позициях. На рис. 6.5 изображена часть сети Петри, которая может быть использована для моделирования выполнения инструкции, использующей блок u и регистры i, j и k.

 

Программное обеспечение ЭВМ.

Блок-схемы

Перевод блок-схемы в сеть Петри заменяет узлы блок-схемы на переходы, а дуги блок-схемы — на позиции. Каждая дуга блок-схемы соответствует точно одной позиции в сети Петри. Узлы блок-схемы представляются по-разному в зависимости от типа узла: вычисления или принятия решения, см. рис.6.6.

 

 

Рис 6.5: Часть сети Петри, моделирующая устройство управления для ЭВМ с кратными регистрами и кратными функциональными блоками.

 

 

 

Рис 6.6: Перевод узлов вычисления и принятия решения в блок-схеме в переходы в сети Петри.

 

 

Рис 6.7: Пример блок-схемы и соответствующей ей сети Петри

 

Фишка, находящаяся в позиции, означает, что счетчик команд установлен на готовность выполнения следующей инструкции. Каждая позиция имеет единственный выходной переход, за исключением позиции, которая предшествует принятию решения; такие позиции имеют по два выходных перехода, соответствующих истинному и ложному значению предиката. Переходы связываются с действиями программы: вычислениями и принятиями решений. Переходы для вычислений имеют один вход и один выход; переход, представляющий вычисления, не может находиться в конфликте, поскольку его входная позиция не является входной для какого-либо другого перехода. Действие же, связанное с принятием решения, вводит в сеть конфликт. Выбор способа разрешения конфликта либо недетерминирован, либо им можно управлять извне (предсказателем, вычисляющим истинность или ложность предиката и вынуждающим запуск нужного перехода). Различие между этими двумя способами разрешения конфликта — методологический вопрос.

 

Синхронизация.

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

Задача о взаимном исключении.

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

 

 

Рис 6.8: Взаимное исключение. Управление доступом к критическим секциям осуществляется таким образом, что оба процесса не могут одновременно выполнять свои критические секции.

 

Задача о производителе/потребителе.

 

 

Рис 6.9: Задача о производителе/потребителе, моделируемая сетью Петри. Справа: задача о производителе/потребителе с ограниченным буфером. Буфер, представленный позициями В и В', ограничен п ячейками.

 

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

В другом варианте задачи используется буфер ограниченного размера. Следовательно, производитель не может постоянно работать с той скоростью, которая ему нужна, а вынужден ждать, если потребитель работает медленно и буфер заполнен. На рис. 6.9 (справа) показано решение этой проблемы. Ограниченному буферу сопоставляются две позиции: В представляет количество элементов данных, которые произведены, но еще не использованы (число заполненных ячеек), В' — количество пустых ячеек в буфере. Первоначально В' имеет n фишек, а В фишек не имеет.

Задача о чтении/записи.

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

 

 

Рис 6.10: Задача о чтении/записи в случае, когда число процессов чтения ограничено величиной n. Первоначально имеются s процессов чтения и t процессов записи.

 

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

 

Date: 2015-09-05; view: 2637; Нарушение авторских прав; Помощь в написании работы --> СЮДА...



mydocx.ru - 2015-2024 year. (0.006 sec.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав - Пожаловаться на публикацию