Вопрос №3 Принципы проектирования информационного обеспечения программного комплекса

Вид материала

Документы

Содержание Вопрос №47 Понятие функционирования сети Петри. Рис. 1. Элементарная сеть. Вопрос №48. Задание автоматов с помощью таблиц переходов и выходов. Автомат Мили Вопрос №49. Построение закона функционирования управляющего автомата Мили по граф-схеме алгоритма.

Подобный материал:

• Е. В. Чепин московский инженерно-физический институт (государственный университет), 30.11kb.
• Рабочая программа учебной дисциплины (модуля) case-средства проектирования программного, 143.56kb.
• Технология программирования, 643.21kb.
• Базы данных, 3110.93kb.
• А. А. Дюмин московский инженерно-физический институт (государственный университет), 30.84kb.
• Учебно-методический комплекс дисциплины разработка и стандартизация программных средств, 362.73kb.
• Методика выбора программного обеспечения турфирмой Антон Россихин (само-софт), 34.31kb.
• С. Д. Романин московский инженерно-физический институт (государственный университет), 24.74kb.
• Примерная программа наименование дисциплины Проектирование и архитектура программных, 182.2kb.
• Рабочая программа учебной дисциплины "системы автоматизированного проектирования электроустановок, 119.83kb.

Вопрос №47 Понятие функционирования сети Петри.

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

Сети Петри были разработаны К.А.Петри в ФРГ в начале 60-х годов и используются для моделирования параллельных и асинхронных систем.

Сети Петри представляют собой двудольный ориентированный граф, в котором имеются вершины двух типов: вершины одного типа называются местами (узлами), а вершины другого типа - переходами. Элементарная сеть Петри изображена на рис. 1.



Рис. 1. Элементарная сеть.

В графическом представлении сетей переходы отображаются абстрактными символами "барьерами" (черточками), а места - кружками. Условия-места и события-переходы связаны отношением непосредственной зависимости, которое изображается с помощью направленных дуг, ведущих из мест в переходы и из переходов в места. Места, из которых выходят дуги, направленные к данному переходу, называются его входными местами. Места, в которые входят дуги, исходящие из данного перехода, называются его выходными местами. Так, в элементарной сети на рис.1 место p1 является входным для перехода t , а место p2 - выходным.

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

Состояния параллельной системы представляется наличием определенных меток у узлов, а конкретное состояние отображается конкретной конфигурацией меток. Такое распределение меток между местами называется разметкой. В примере сети, показанном на рис. 2, используются общепринятые графические обозначения. Узлы представлены в виде кружков, обозначенных р ... t, переходы представлены линиями В1 ... В4, а исходная разметка показана черными точками. Символы переходов показывают возможные изменения состояния параллельной системы. Переход может срабатывать (отображая смену состояния) только тогда, когда каждое из его входных мест имеет по меньшей мере одну метку (фишку). Когда переход срабатывает, происходит изъятие метки из каждого его входного места и пересылка по одной метке в каждое из его выходных мест. Таким образом, комбинация входных и выходных мест некоторого перехода отображает как условия, при которых может произойти изменение состояния, так и влияние этого изменения.

Срабатывание перехода — это неделимое событие, и потому одновременное срабатывание двух или более переходов невозможно. Когда состояние таково, что два и более переходов претендуют на срабатывание, каждый из них должен рассматриваться отдельно. Начиная с исходной разметки, которая соответствует исходному состоянию системы, и выполняя очевидную процедуру генерирования другой разметки, достижимой из исходной, можно исследовать возможные состояния системы и пути их достижения. Например, могут быть легко обнаружены тупиковые состояния и непродуктивные зацикливания и вообще всегда возможно установить, соответствует ли поведение системы ожидаемому. Хотя процедура генерации достижимой разметки довольно тривиальна, попытки исчерпывающего анализа поведения системы таким способом оказывается тщетными часто из-за уже одного только числа разметок, которое может быть бесконечным. Таким образом, главная задача, состоящая в определении достижимости данной разметки из заданного исходного состояния, оказывается неразрешимой.

На рис. 2 в исходной маркировке могут сработать переходы В1 и ВЗ. Предположим, что срабатывает В1. Тогда изымаются метки из мест р и t и пересылается единственная метка в место q, Теперь способен сработать только В2 (ВЗ этого сделать уже не может потому, что место t больше не имеет меток). Когда В2 срабатывает, метка изымается из места q и новые метки помещаются в р и t, в результате чего восстанавливается исходная разметка. Если бы теперь сработал переход ВЗ, то единственная метка оказалась бы помещенной в s, срабатывал бы В4 и снова восстанавливалась исходная разметка. (Эту сеть можно рассматривать как модель системы, в которой два процесса совместно используют общий разделяемый ресурс. Состояние готовности ресурса к использованию представляется наличием метки в t. Релевантные состояния одного процесса, владеющего либо не владеющего ресурсом, представляются метками в р и q, соответственно. Аналогично метки в r и s представляют релевантные состояния другого процесса.)

Дополнительно:

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

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

Фишка свидетельствует о том, что переменная/буфер имеет значение, а если место имеет, к примеру, 3 фишки, то это может интерпретироваться как наличие трех разных значений в буфере. Если место содержит фишку, то место маркировано и сеть называется маркированной. Начальное распределение фишек задает начальную маркировку М0 сети. Маркировка сети определяет ее текущее состояние.

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

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

Вопрос №48. Задание автоматов с помощью таблиц переходов и выходов.

Для представления конечного автомата S, необходимо описать все компоненты вектора S = (A, X, Y, σ, λ, a₁), т.е. входной и выходной алфавиты, алфавит состояний, а также функции переходов и выходов. Среди множества этих состояний пожалуй стоит выделить начальное состояние a₁, в котором автомат находится в момент времени t=0. После установления всех компонентов данной системы, словесное описание может быть формализовано при помощи таблицы, графа или матрицы. Таблица, граф и матрица - различные формы представления характеристических функций конечного автомата, который описывает данную систему.

Ниже рассмотрен табличный способ задания работы автомата на примере автоматов Мили и Мура.

Автомат Мили описывается с помощью двух таблиц: таблицы переходов и таблицы выходов. Таблица переходов задает функцию σ, таблица выходов – λ.



Слева изображена таблица переходов, а справа таблица выходов, с помощью которых мы задаем работу автомата Мили. Строки этих таблиц соответствуют входным сигналам, а столбцы - состояниям, причем крайний левый столбец обозначен начальным состоянием а₁. На пересечении столбца a_m и строки x_f в таблице переходов ставится состояние a_s= σ (a_m, x_f), в которое автомат переходит из состояния a_m под воздействием сигнала x_f, а в таблице выходов - соответствующий этому переходу сигнал y_g= λ (a_m, x_f). С помощью выше представленных таблиц мы описали полностью определенный автомат Мили S1 с тремя состояниями, двумя входными и двумя выходными сигналами. В случае частично определенного автомата на месте неопределенных состояний и выходных сигналов ставится прочерк.

Выходной сигнал в автомате Мура зависит только от состояния, поэтому он задается только одной отмеченной таблицей переходов, в которой каждому ее столбцу , кроме состояния a_m, приписан еще и выходной сигнал y_g= λ (a_m), соответствующий этому состоянию. Это также является полностью определенный автомат, если автомат частично определенный, то на месте неопределенных состояний также ставится прочерк.



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

Вопрос №49. Построение закона функционирования управляющего автомата Мили по граф-схеме алгоритма.

Определение закона функционирования автомата Мили. Пусть микропрограмма задана в виде закодированною графа (рис.1, а) и для ее интерпретации используется автомат Мили с законом функционирования.




где А = [a₁ ,..., а_N} - множество состояний автомата, t = 0, 1, 2, ..; А (0) = а₁ - начальное состояние автомата.

Микропрограмма оперирует с четырьмя логическими условиями X = {x_l,..., х₄} и пятью микрооперациями Y = {y_l,..., у₅}. Поэтому автомат, реализующий эту микропрограмму, должен иметь четыре входа х₁,..., х₄ и пять выходов y_l,…, у₅. Необходимый набор состояний автомата определяется путем отметки графа микропрограммы, которая производится в следующем порядке:

1. символом а₁ отмечается вход первой вершины, следующей за начальной, а также вход конечной вершины;
   
2. входы вершин, следующих за операторными вершинами, отмечаются символами a₂ а₃, ...;
   
3. входы двух различных вершин, за исключением конечной, не могут быть отмечены одинаковыми символами;
   
4. вход вершины может отмечаться только одним символом.
   

Пример отметки графа микропрограммы состояниями а₁, а₂, ... ..., a₆ автомата приведен на рис. 1, а. Предполагается, что в начальном состоянии a₁ автомат формирует нулевые значения на всех выходах у₁, ..., у₅. По окончании работы автомат возвращается в это же состояние.


Переход по графу микропрограммы из отметки а_l, в отметку а₁, в направления дуг графа определяет путь

, (1)

где = х, если путь проходит через выход условной вершины, отмеченный значением 1, и =, если путь проходит через выход, отмеченный значением 0; у_а, ..., y_w - множество микроопераций, указанное в единственной операторной вершине, через которую проходит данный путь. Например, на графе рис. 1, а из отметки а₁ в отметку a₂ можно перейти двумя путями: a₁y₁y₂a₂ и a₁x₁y₂a₂, а из отметки a₂, в а₄ - по единственному пути a₂x₂x₃y₁y₄a₄. Путь, не проходящий через условные вершины, содержит пустое множество логических условий a_ly_ay_b…y_wa_i. Некоторые пути, ведущие к отметке а₁ - конечной вершине графа, могут содержать пустое множество микроопераций

(2)

Очевидно, что все множество путей вида (1) или (2) определяет множество переходов между состояниями a_t и а₁, автомата Мили.

Если состояниям а₁, .., а_N, поставить в соответствие вершины графа, а путям (1) и (2) - дуги, направленные из вершины а₁, в вершину а₁, и отмеченные наборами значений входных и выходных сигналов, то полученный граф будет определять закон функционирования автомата Мили. Так, граф микропрограммы {рис. 1, а) порождает автомат Мили с законом функционирования (рис. 1, б). Заметим, что дуги на графе автомата отмечаются только теми входными сигналами X, которые определяют возможность перехода из состояния а₁, в состояние а₁, и теми выходными сигналами Y, которые в данной ситуации принимают значение 1. При этом предполагается, что все остальные выходные сигналы имеют нулевое значение.

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

Для запуска автомата используется специальный сигнал В, который относится к группе входных сигналов и имеет длительность, равную такту. Чтобы исключить возможность появления выходных сигналов Y в моменты, когда автомат находится в состоянии а₁, и не работает, дугам, исходящим из вершины a_l, дополнительно приписывается запускающий сигнал В (рис. 1, б), только при единичном значении которого выходным сигналам Y присваивается значение 1 и становится возможным переход автомата е следующее состояние. При В = 0 автомат сохраняет начальное состояние и все выходные сигналы имеют нулевые значения. Введение сигнала В в закон функционирования автомата соответствует включению ждущей вершины В в граф микропрограммы (рис. 1, в), с помощью которой отмечается тот факт, что выполнение микропрограммы начинается только при В = 1.

Автомат Мили может интерпретировать микропрограмму корректно только в том случае, если для всех переходов вида (1) выполняется условие независимости логических условий х_α, ..., х_ω от результатов выполнения микроопераций у_а, ..., у_w.

Условие независимости нарушается, если на некотором переходе наблюдается функциональная зависимость х_ρ = f (у_k). В таком случае выполнение микрооперации y_k может привести к изменению значения условия х_р, и автомат, реагируя на новый набор входных сигналов, сформирует набор выходных сигналов, не соответствующий микропрограмме. Во избежание этого отрицательного эффекта необходимо проанализировать все переходы, имеющие место в автомате, выявить входные сигналы х_р, х_σ,…, x_ψ, которые зависят от микроопераций, порождаемых ими, и структурными средствами исключить влияние этих сигналов на процесс выполнения микроопераций. Для этой цели можно использовать следующие способы:

1. запоминание значений сигналов х_р, ..., х_ψ на промежуток времени, равный длительности такта;
   
2. введение в автомат дополнительных состояний;
   
3. реализация автомата по схеме Мура.
   

Запоминание сигналов х_р, ..., х_ψ производится на триггерах, которые переключаются в состояния х_р, ..., х_ψ в конце такта, одновременно с переключением автомата в новое состояние. Порядок введения дополнительных состояний иллюстрируется рис. 2, а. Предполагается, что х_р = φ (у_а, у_b), т. е. условие независимости для данного фрагмента микропрограммы нарушается. Как видно из рис. 2, б, дополнительные состояния а_k и a_l исключают возможность переключения сигналов у_а и у_b при изменении значения х_р. Введение дополнительных состояний приводит к дополнительным затратам оборудования и увеличивает время выполнения микропрограммы.




Рис. 2. Способ введения дополнительных состояний