Федеральное агентство по образованию

ОТЧЕТ

по лабораторной работе №1

Вариант 4

Преподаватель

Студент гр.

Екатеринбург, 2008

Цель работы

Изучение методов использования иерархических сетей Петри при анализе многоуровневых вычислительных структур (ВС).

Сети Петри

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

Сети Петри с успехом могут применяться при использовании любого метода. Возможны два пути практического применения СП при проектировании и анализе систем. Первый путь заключается в использовании СП-моделей в качестве вспомогательного инструмента анализа. В этом случае построенная структура моделируется сетью Петри и модель анализируется. Любые трудности, встречающиеся при анализе, указывают на изъяны в проекте. Для их исправления необходимо модифицировать проект. Модифицированный проект затем снова моделируется и анализируется. Этот цикл повторяется до тех пор, пока проводимый анализ не приведет к успеху. Второй путь заключается в том, что весь процесс проектирования и определения характеристик ВС проводится в терминах сетей Петри.

Вычислительные структуры, назначение которых заключается в вводе, обработке и выводе информации. Предлагаемые структуры состоят из процессорных элементов (ПЭ), которые могут соединяться последовательно и параллельно, и каналов ввода-вывода, которые состоят из подканалов. Последовательное соединение ПЭi и ПЭj обозначается как - (ПЭi?ПЭj), параллельное соединение ПЭi и Пэj - как - (ПЭi||ПЭj).

Постановка задачи

Даны вычислительные структуры BC1 и ВС2, которые имеют соответственно параллельный (ПЭ1||ПЭ2||ПЭЗ) и последовательный (ПЭ1?ПЭ2) процессоры. Обработка данных в процессорах BC1 и ВС2 начинается одновременно. Канал ввода-вывода имеет один подканал и выполняет ввод и вывод данных в каждой вычислительной структуре.

Лабораторное задание

1. Выбрать вычислительную структуру в соответствии с вариантом.

2. Разработать СП-модель в соответствии с ее словесным описанием.

3. Провести анализ полученной СП-модели при помощи графа достижимости.

4. Провести анализ полученной СП-модели на ограниченность, активность, обратимость, конечность функционирования.

5. На основе исследования сделать выводы о корректности модели, предложить варианты устранения недостатков в случае их обнаружения.

СП-модель в соответствии с ее словесным описанием

P0-- признак, сигнализирующий о начале передачи потока данных;

t0 - выдача соответствующим вычислительным структурам BC1 и ВС2 потока данных;

BC1:

P1 - признак, готовности к обработке данных 1-ым ПЭ;

t1 - функционирование 1-го ПЭ1 при обработке команд;

P13- признак, готовности к обработке данных 2-ым ПЭ;

t2 - функционирование 2-го ПЭ1 при обработке команд;

P14 - признак окончания обработки данных BC1(последовательного процесса).

BC2:

P3 - признак, готовности к обработке данных 1-ым ПЭ;

P4 - признак, готовности к обработке данных 2-ым ПЭ;

P5 - признак, готовности к обработке данных 3-им ПЭ

t3 - функционирование 1-го ПЭ1 при обработке команд;

t4 - функционирование 2-го ПЭ1 при обработке команд;

t5 - функционирование 3-го ПЭ1 при обработке команд;

P10 - признак окончания обработки данных ПЭ1;

P9 - признак окончания обработки данных ПЭ2;

P12 - признак окончания обработки данных ПЭ3;

t8 - выработка признаков окончания обработки команды параллельным процессором;

P11 - признак окончания обработки данных BC2(параллельного процесса);

T9 - выработка признаков окончания обработки команд BC1 и BC2.

Анализ СП-модели

Другое направление исследования функционирования сети Петри связано с изменением количества фишек в конкретной или произвольной позиции в процессе функционирования сети. Сеть Петри называется ограниченной, или просто ограниченной, если для любой маркировки, достижимой от маркировки М0, количество фишек в любой позиции не превышает некоторого числа К, т .е. М(р) <= К для любого р и любой маркировки М, принадлежащей R(M0). Сеть Петри (N, M0) называется безопасной, если она 1-ограниченна.

Полученная вычислительная структура безопасна, т.е она 1-ограниченна.

Конечность функционирования структуры (о достижении тупиковой разметки).

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

Ситуация дедлока не возникает при любой последовательности срабатываний переходов.

Граф достижимости

Выводы

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