logo
Свойства систем Методы системнрго анализа

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

Сетевые модели могут быть представлены:

события, результат работы);

действия, операции, ребра – работы);

отражают только направление перехода от одной вершины к

другой.

Часто применяют также термины источник и сток. Источником называют исходное событие (или работу), стоком – конечное событие. Сеть может иметь несколько источников и один сток (одноцелевые сети), один источник и несколько стоков (многоцелевые сети).

При анализе сетей их оценивают по одному из критериев

(например, по времени или стоимости и т.д.), а затем, суммируя оценки вершин (или ребер, в зависимости от вида сети), определят путь, наилучший с точки зрения данного критерия. Этот путь называют критическим.

Основным математическим аппаратом анализом сетевых графиков является теория графа.

Теория графа – математическая теория, которая развивалась независимо от сетевого планирования. Основная терминология этой теории приведена в таблице 10.

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

В более сложных случаях – если граф вероятностный – решение не всегда может быть найдено.

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

Применение графических представлений

Графические методы применяются в основном для решения различных организационных вопросов, для наглядного представления информации (например, в лингвистике для представления процесса анализа текста – дерево составляющих) (см. таблицу 9) для оптимизации планирования и управления (СПУ).

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

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

При большой привлекательности сетевые модели имеют один довольно существенный недостаток: при их формировании необходимо участие квалифицированных работников, хорошо знающих процессы в системе, причем некоторые исследователи оценивают долю «ручного» труда при применении сетевых моделей

в 95% от общего времени, затрачиваемого на анализ ситуаций и процессов с применением сетевого моделирования. Для снижения доли «ручного» квалифицированного труда, перспективным является сочетание графических представлений с семиотическими, которые могут позволить формализовать и автоматизировать процесс порождения не только последовательностей вершин, но и самих вершин.

Лингвистические, семиотические методы (Пузырева Н.) – файл с докладом не сдала

Логические методы (Меркурьев М.) – файл не сдал

Сети Петри (Садовская А.)

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

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

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

Группой вычислительных структур были проведены две большие конференции по сетям Петри: Конференция Проекта МАС по параллельным системам и параллельным вычислениям в 1970 году в Вудс Холле, и Конференция по сетям Петри и связанным с ними методам в 1975 году в МТИ. Обе эти конференции внесли вклад в распространение результатов и методов теории сетей Петри.

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

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

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

Сеть Петри состоит из 4 элементов: множество позиций Р, множество переходов Т, входная функция I, выходная функция О. Входная и выходная функции связаны с переходами и позициями. Входная функция I отображает переход tj в множество позиций I(tj), называемых входными позициями перехода. Выходная функция О отображает переход tj в множество позиций О(tj), называемых выходными позициями перехода.

Сеть Петри С является четверкой С=(P,T,I,O), P=(p1 p2 pn) – конечное множество позиций n>=0, T=(t1 t2 tm) – конечное множество переходов m>=0. Множество позиций и множество переходов не пересекаются

Позиция pi является входной позицией перехода tj, в этом случае, если pi принадлежит I(tj). Pi является выходной позицией, если pi принадлежит O(tj). Входы и выходы переходов представляют собой комплекты позиций.

I(p1)={} O(p1)={t1}

I(p2)={t1,t4} O(p2)={t2}

I(p3)={t1,t4} O(p3)={t2,t3}

I(p4)={t3} O(p4)={t4}

I(p5)={t1,t2} O(p5)={t2}

C=( P , T , I , O )

P={p1 , p2 , p3 , p4, p5}

T={t1 , t2 , t3 , t4 }

Для иллюстрации понятий теории сетей Петри гораздо более удобно графическое представление сети Петри. Теоретико-графовым представлением сети Петри является двудольный ориентированный мультиграф. Структура сети Петри представляет совокупность позиций и переходов. В соответствии с этим граф сети Петри обладает двумя типами узлов. Кружок – О- является позицией, а планка 1 – переходом. Ориентированные дуги (стрелки соединяют позиции и переходы), при этом некоторые дуги направлены от позиций к переходам. Другие – от переходов к позициям. Дуга, направленная от позиции pi к переходу tj, определяет позицию которая является входом перехода. Сеть Петри есть мультиграф, так как он допускает существование кратных дуг от одной вершины графа к другой. Следует добавить, что так как дуги являются направленными, то это ориентированный мультиграф. Мы знаем, что вершины графа можно разделить на два множества (позиции и переходы) таким образом, что каждая дуга будет направлена от элемента одного множества (позиции или переходов) к элементу другого множества (переходов или позиций); следовательно, такой граф является двудольным ориентированным графом.

Маркировка  есть присвоение фишек позициям сетей Петри. Фишка – это примитивное понятие сетей Петри (подобно позициям и переходам). Фишки присваиваются позициям. Количество и положение фишек при выполнении сети Петри могут изменяться. Фишки используются для определения выполнения сети Петри.

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

Переход может запускаться только в том случае, когда он разрешен. Переход называется разрешенным, если каждая из его входных позиций имеет число фишек по крайней мере равное числу дуг из позиции в переход. Кратные фишки необходимы для кратных входных дуг. Фишки во входной позиции, которые разрешают переход, называются его разрешающими фишками. Например, если позиции р1 и р2 служат входами для перехода t4 , тогда t4 – разрешен, если р1 и р2 имеют хотя бы по 1 фишке. Для перехода t7 – с входным комплектом {р6,р6,р6} позиция р6 должна обладать по крайней мере тремя фишками, для того чтобы t7 был разрешен.

Переход запускается удалением всех разрешающих фишек из его входных позиций и последующим помещением в каждую из его выходных позиций по 1 фишке для каждой дуги. Кратные фишки создаются для кратных выходных дуг.

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

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

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

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

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

Не примитивными называются такие события длительность которых отлична от 0. Они не являются не одновременными и, следовательно, могут пересекаться во времени. Так как осуществление большинства событий в реальном мире занимает некоторое время, то они являются не примитивными событиями, и поэтому не могут должным образом моделироваться переходами в сети Петри. Однако это не приводит к возникновению проблем при моделировании систем. Не примитивное событие может быть представлено в виде двух примитивных событий: «начало не примитивного события», «конец не примитивного события» и условие «не примитивное событие происходит». Эта ситуация может быть промоделирована с помощью сети

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

Другая ситуация, в которой одновременное выполнение затруднено и которая характеризуется возможностью одновременного возникновения событий показана на втором рисунке. Здесь два разрешенных перехода находятся в конфликте. Может быть запущен только 1 переход, так как при запуске он удаляет фишку из общего входа и запрещает другой переход.

Разработке методов моделирования по сетям Петри внимания уделялось мало. Однако существуют специальные области, в которых сети Петри представляются идеальным инструментом для моделирования.

Конечные автоматы:

На низком уровне вычислительные системы могут быть описаны автоматами. Автомат – пятерка (,,,, ), где

 - конечное множество состояний

 - конечные входной алфавит

 - конечный выходной алфавит

 - функция следующего состояния

 - функция выхода

Автоматы часто представляются в виде графов переходов. Состояния представляются кружками, являющимися вершинами. Дуга из состояния qi в состояние qj, помеченная a/b, означает что, находясь в состоянии qi , автомат при входе а перейдет в состояние qj, выдавая при этом символ b.

В качестве примера рассмотрим изображенный автомат. Он преобразует двоичное число, представленное последовательностью бит, начиная с младшего, в дополнении до двух. В данном случае входной и выходной алфавиты состоят из трех символов: 0, 1, R. Автомат начинает работать в состоянии q1. Символ сброса R означает конец или начало числа и возвращает автомат в исходное состояние. Выход автомата для символа сброса является просто его повторением.

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

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

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

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

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

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

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

В качестве примера рассмотрим сложение двух чисел с плавающей точкой. Основные шаги этой операции предполагают:

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

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

В асинхронном конвейере в среднем процесс обработки может быть ускорен сигнализацией о завершении каждого шага конвейерной обработки и готовности передать свой операнд и получить новый. Результат шага к конвейерной обработки может быть послан на шаг к+1, как только шаг к выполнен , а блок к+1 свободен.

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