Устройство для исследования сетей петри

 

Изобретение относится к вычислительной технике и может быть использовано при моделировании посредством сетей Петри. Техническим результатом является расширение функциональных возможностей за счет задания величин неопреде ценностей. Устройство содержит модели вершин, каждая из которых состоит из элементов ИЛИ и реверсивного счетчика, модели переходов, каждая из которых состоит из элементов И, генератор одиночных импульсов, регистры сдвига, две группы элементов И, регистр, триггер, генератор тактовых импульсов, элемент И, элементы ИЛИ, счетчик, блок индикации, группу регистров, группу датчиков случайных чисел и группу схем сравнения. 1 ил.

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

Известно устройство для исследования СП (Авторское свидетельство СССР N 1 171 803, кл. G 06 F 15/20, 1983), содержащее модели вершин, три триггера, шесть элементов И, два элемента ИЛИ, счетчик и генератор импульсов. Недостатком данного устройства является отсутствие возможности определения тупиковых разметок в СП.

Наиболее близким по технической сущности к изобретению является устройство для исследования СП (Авторское свидетельство СССР N 1 345 208, кл. G 06 F 15/20, 1987), содержащее модели вершин и переходов, генератор одиночных импульсов, формирователь импульса, два генератора импульсов, два регистра сдвига, две группы элементов И, группу элементов ИЛИ, шесть элементов И, два элемента ИЛИ, два элемента задержки, три триггера, два счетчика, дешифратор, три элемента НЕ, блок индикации. При помощи данного устройства можно моделировать различные вычислительные системы и процессы с элементами неопределенности, описанные посредством аппарата СП и выявлять в них тупиковые ситуации. Недостатком устройства является отсутствие возможности задавать конкретные величины, характеризующие неопределенность. Данный недостаток не позволяет строить адекватные модели реальных систем и процессов, а значит, и получать достоверные результаты моделирования.

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

Поставленная задача возникает при моделировании стохастических процессов и моделей вычислительных систем.

Сущность изобретения заключается в том, что устройство для исследования сетей Петри содержит H моделей вершин, каждая из которых включает вход начальной загрузки разметки, вход признака начальной загрузки разметки, первый, второй и третий элементы ИЛИ, реверсивный счетчик, M входов приема фишек, M входов изъятия фишек и выход признака наличия фишек, M моделей переходов, каждая из которых включает первый и второй элементы И, H входов условий перехода, выход признака возможности выполнения перехода, вход признака разрешения выполнения перехода и H выходов признака выполнения перехода, генератор одиночных импульсов, первый регистр сдвига, первую и вторую группы элементов И, регистр, триггер, генератор тактовых импульсов, элемент И, первый и второй элементы ИЛИ, счетчик, блок индикации, вход признака записи начальной разметки устройства и вход задания начальной разметки устройства, причем модели вершин и переходов соединены согласно топологии сети Петри, вход задания начальной разметки устройства соединен с информационным входом регистра, выход которого соединен с входами начальной загрузки разметки всех моделей вершин, входы признака записи начальной загрузки разметки которых соединены с выходами элементов И первой группы, первые входы которых соединены с входом признака сдвига первого регистра сдвига и с входом признака записи начальной разметки устройства для разрешения записи начальной разметки в одноименные модели вершин согласно поочередно устанавливаемым в единичное состояние разрядам первого регистра сдвига при наличии сигнала разрешения на входе признака записи начальной разметки устройства, вход синхронизации первого регистра сдвига соединен с выходом генератора одиночных импульсов, j-й вход приема фишки i-й модели вершины соединен с j-м входом первого элемента ИЛИ i-й модели вершины, выход которого соединен с суммирующим входом реверсивного счетчика i-й модели вершины, вычитающий вход которого соединен с выходом второго элемента ИЛИ i-й модели вершины, j-й вход которого соединен с j-м входом изъятия фишек i-й модели вершины, вход начальной загрузки разметки которой соединен информационным входом реверсивного счетчика i-й модели вершины, выход признака наличия фишек которой соединен с выходом третьего элемента ИЛИ i-й модели вершины, входы которого соединены с выходами реверсивного счетчика i-й модели вершины, i-й вход условия перехода j-й модели перехода соединен с i-м входом первого элемента И j-й модели перехода, выход которого соединен с вторым входом второго элемента И j-й модели перехода и является выходом признака возможности выполнения перехода j-й модели перехода, первый вход которого является входом признака разрешения выполнения перехода i-й модели перехода, выход которого соединен с H выходами j-й модели перехода, в него дополнительно введены второй регистр сдвига, группа регистров, группа датчиков случайных чисел и группа схем сравнения, причем вход признака записи начальной разметки устройства соединен с вторым входом элемента И, первый вход которого соединен с H-м выходом первого регистра сдвига, выход элемента И соединен с вторым входом первого элемента ИЛИ и входом установки в "1" триггера, вход установки в "0" которого, объединенный с входом блока индикации, соединен с выходом переполнения счетчика, информационный вход которого, объединенный с входом синхроимпульсов второго регистра сдвига, соединен с выходом генератора тактовых импульсов, вход которого соединен с выходом триггера, выход переполнения второго регистра сдвига соединен с первым входом первого элемента ИЛИ, выход которого соединен с информационным входом второго регистра сдвига, j-й выход которого соединен с вторым входом j-ого элемента И второй группы, первый вход которого соединен с выходом возможности выполнения перехода j-й модели перехода, выход j-ого элемента И второй группы соединен с входом j-ого датчика случайных чисел группы, выход которого соединен с вторым входом j-й схемы сравнения группы, первый вход которой соединен с выходом j-ого регистра группы, вход сброса счетчика соединен с выходом второго элемента ИЛИ, j-й вход которого, объединенный с входом признака разрешения выполнения перехода j-й модели перехода, соединен с выходом j-й схемы сравнения группы.

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

Устройство для исследования сетей Петри содержит модели вершин I(I), I(2),..., I(H), каждая из которых включает вход 2 начальной загрузки разметки, вход 3 признака записи начальной загрузки разметки, первый 4, второй 5, третий 6 элементы ИЛИ, реверсивный счетчик 7, входы 8(1), 8(2),..., 8(M) приема фишек, входы 9(1),...,9(M) изъятия фишек и выход 10 признака наличия фишек, модели переходов II(1), II(2), ..., II(M), каждая из которых включает первый 12, второй 13 элементы И, входы 14(1), 14(2),...,14(H) условий перехода, выход 15 признака возможности выполнения перехода, вход 16 признака разрешения выполнения перехода и выходы 17(1), 17(2),...,17(H) признака выполнения перехода, генератор 18 одиночных импульсов, первый 19 регистр сдвига, первую 20 и вторую 21 группы элементов И, регистр 22, триггер 23, генератор 24 тактовых импульсов, элемент И 25, первый 26 и второй 27 элементы ИЛИ, счетчик 28, блок 29 индикации, вход 30 признака записи начальной разметки, вход 31 задания начальной разметки, второй 32 регистр сдвига, группа 33 регистров, группа 34 датчиков случайных чисел, группа 35 схем сравнения.

Модели вершин I(I), I(2),...,I(H) и переходов II(I), II(2),...,II(M) соединены согласно топологии сети Петри, вход 31 задания начальной разметки устройства соединен с информационным входом регистра 22, выход которого соединен с входами 2 начальной загрузки разметки всех моделей вершин I(I), I(2), . ..,I(H), входы 3 признака записи начальной загрузки разметки которых соединены с выходами элементов И первой 20 группы, первые входы которых соединены с входом признака сдвига первого 19 регистра сдвига и с входом 30 признака записи начальной разметки устройства для разрешения записи начальной разметки в одноименные модели вершин I согласно поочередно устанавливаемым в единичное состояние разрядам первого 18 регистра сдвига при наличии сигнала разрешения на входе 30 признака записи начальной разметки устройства, вход синхронизации первого 19 регистра сдвига соединен с выходом генератора 18 одиночных импульсов, j-й вход 8 приема фишки i-й модели вершины I соединен с j-м входом первого 4 элемента ИЛИ i-й модели вершины I, выход которого соединен с суммирующим входом реверсивного счетчика 7 i-й модели вершины I, вычитающий вход которого соединен с выходом второго 5 элемента ИЛИ i-й модели вершины I, j-й вход которого соединен с j-м входом 9 изъятия фишек i-й модели вершины I, вход 2 начальной загрузки разметки которой соединен с информационным входом реверсивного счетчика 7 i-й модели вершины I, выход 10 признака наличия фишек которой соединен с выходом третьего 6 элемента ИЛИ i-й модели вершины I, входы которого соединены с выходами реверсивного счетчика 7 i-й модели вершины I, i-й вход 14 условия перехода j-й модели перехода II соединен с i-м входом первого 12 элемента И j-й модели перехода II, выход которого соединен с вторым входом второго 13 элемента И j-й модели перехода II и является выходом 15 признака возможности выполнения перехода j-й модели перехода II, первый вход которого является входом 16 признака разрешения выполнения перехода i-й модели перехода II, выход которого соединен с H выходами j-й модели перехода II, вход 30 признака записи начальной разметки устройства соединен с вторым входом элемента И 25, первый вход которого соединен с H-м выходом первого 19 регистра сдвига, выход элемента И 25 соединен с вторым входом первого 26 элемента ИЛИ и входом установки в "I" триггера 23, вход установки в "0" которого, объединенный с входом блока 29 индикации, соединен с выходом переполнения счетчика 28, информационный вход которого, объединенный с входом синхроимпульсов второго 32 регистра сдвига, соединен с выходом генератора 24 тактовых импульсов, вход которого соединен с выходом триггера 23, выход переполнения второго 32 регистра сдвига соединен с первым входом первого 26 элемента ИЛИ, выход которого соединен с информационным входом второго 32 регистра сдвига, j-й выход которого соединен с вторым входом j-ого элемента И второй 21 группы, первый вход которого соединен с выходом 15 признака возможности выполнения перехода j-й модели перехода, выход j-ого элемента И второй 21 группы соединен с входом j-ого датчика 34 случайных чисел группы, выход которого соединен с вторым входом j-ой схемы 35 сравнения группы, первый вход которой соединен с выходом j-ого регистра 33 группы, вход сброса счетчика 28 соединен с выходом второго 27 элемента ИЛИ, j-й вход которого, объединенный с входом 16 признака разрешения выполнения перехода j-й модели перехода, соединен с выходом j-й схемы сравнения 25 группы.

Устройство работает следующим образом: коммутацией входов 8(I)...8(M) приема фишек, 9(I)...9(M) изъятия фишек, выходов 10 признака наличия фишек моделей I(I)...I(H) вершин и входов 14(I)...14(M) условий перехода, выходов 17(I). . .17(M) признака выполнения перехода моделей II(I)...II(M) переходов между собой согласно топологии исследуемой сети Петри осуществляется подготовка устройства к работе. В каждый регистр группы 33 регистров заносятся случайные величины, характеризующие вероятность срабатывания для каждого перехода.

При включении устройства генератор 18 одиночного импульса вырабатывает импульс, который устанавливает первый разряд первого 19 регистра сдвига в единичное состояние. В регистре 22 через вход 31 задания начальной разметки устройства устанавливается в двоичном коде значение начальной разметки для первого места (вершины). С входа 30 признака записи начальной разметки устройства выдается сигнал разрешения записи начальной разметки для первой вершины, который одновременно устанавливает в единицу разряд первого 19 регистра сдвига. Аналогично производится запись начальной разметки для второй вершины. При записи начальной разметки для последней вершины производится через элемент И 25 установка в единичное состояние триггера 23, который запускает генератор 24 тактовых импульсов, и запись единицы в первый разряд второго 32 регистра сдвига через элемент ИЛИ 26. С приходом импульсов с генератора 24 на тактовый вход второго 32 регистра сдвига происходит последовательный сдвиг первоначально записанной в данный регистр единицы, а в счетчике 28 подсчет сдвигов. Емкость счетчика 28 соответствует количеству описанных переходов в модели.

При поступлении первой единицы в первый разряд второго 32 регистра сдвига происходит во второй 21 группе элементов И опрос на возможность срабатывания первого перехода в соответствии с сигналом с выхода 15 признака возможности выполнения перехода. Если первый переход готов к срабатыванию, то с первого элемента И группы 21 выдается сигнал на первый датчик случайных чисел группы 34, который вырабатывает случайное число "a", и происходит его сравнение в первой схеме сравнения группы 35 с числом "b", записанным в первом регистре группы 33. Если в результате сравнения окажется, что "a<b", то данный переход считается сработавшим. При этом через вход 16 признака разрешения выполнения перехода подается разрешающий сигнал на первый вход второго элемента И 13 блока моделей переходов II, на второй вход которого приходит сигнал с первого 12 элемента И, характеризующий готовность данного перехода к срабатыванию. По сигналу с второго 13 элемента И происходит соответствующее вычитание и прибавление фишек в блоках моделей вершин I при помощи подачи сигналов на входы вычитания и сложения реверсивных счетчиков 7. Подача данных сигналов обеспечивается определенными соединениями блоков моделей вершин I(I),...,I(H) и переходов II(I),...,II(M), описывающих топологию моделируемой сети Петри.

При срабатывании определенного перехода сигнал с выхода элемента ИЛИ 27 также поступает на вход сброса счетчика 28 для установки его в нуль.

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

Формула изобретения

Устройство для исследования сетей Петри, содержащее Н моделей вершин, каждая из которых включает вход начальной загрузки разметки, вход признака записи начальной загрузки разметки, первый, второй, третий элементы ИЛИ, реверсивный счетчик, М входов приема фишек, М входов изъятия фишек и выход признака наличия фишек, М моделей переходов, каждая из которых включает первый и второй элементы И, Н входов условий перехода, выход признака возможности выполнения перехода, вход признака разрешения выполнения перехода и Н выходов признака выполнения перехода, генератор одиночных импульсов, первый регистр сдвига, первую и вторую группы элементов И, регистр, триггер, генератор тактовых импульсов, элемент И, первый и второй элементы ИЛИ, счетчик, блок индикации, вход признака записи начальной разметки устройства и вход задания начальной разметки устройства, причем модели вершин и переходов соединены согласно топологии сети Петри, вход задания начальной разметки устройства соединен с информационным входом регистра, выход которого соединен с входами начальной загрузки разметки всех моделей вершин, входы признака записи начальной загрузки разметки которых соединены с выходами элементов И первой группы, первые входы которых соединены с входом признака сдвига первого регистра сдвига и входом признака записи начальной разметки устройства для разрешения записи начальной разметки в одноименные модели вершин согласно поочередно устанавливаемым в единичное состояние разрядам первого регистра сдвига при наличии сигнала разрешения на входе признака записи начальной разметки устройства, вход синхронизации первого регистра сдвига соединен с выходом генератора одиночных импульсов, j-й вход приема фишки i-й модели вершины соединен с j-м входом первого элемента ИЛИ i-й модели вершины, выход которого соединен с суммирующим входом реверсивного счетчика i-й модели вершины, вычитающий вход которого соединен с выходом второго элемента ИЛИ i-й модели вершины, j-й вход которого соединен с j-м входом изъятия фишек i-й модели вершины, вход начальной загрузки разметки которой соединен с информационным входом реверсивного счетчика i-й модели вершины, выход признака наличия фишек которой соединен с выходом третьего элемента ИЛИ i-й модели вершины, входы которого соединены с выходами реверсивного счетчика i-й модели вершины, i-й вход условия перехода j-й модели перехода соединен с i-м входом первого элемента И j-й модели перехода, выход которого соединен с вторым входом второго элемента И j-й модели перехода и является выходом признака возможности выполнения перехода j-й модели перехода, первый вход которого является входом признака разрешения выполнения перехода i-й модели перехода, выход которого соединен с Н выходами j-й модели перехода, отличающееся тем, что в него дополнительно введены второй регистр сдвига, группа регистров, группа датчиков случайных чисел и группа схем сравнения, причем вход признака записи начальной разметки устройства соединен с вторым входом элемента И, первый вход которого соединен с Н-м выходом первого регистра сдвига, выход элемента И соединен с вторым входом первого элемента ИЛИ и входом установки в "1" триггера, вход установки в "0" которого, объединенный с входом блока индикации, соединен с выходом переполнения счетчика, информационный вход которого, объединенный с входом синхроимпульсов второго регистра сдвига, соединен с выходом генератора тактовых импульсов, вход которого соединен с выходом триггера, выход переполнения второго регистра сдвига соединен с первым входом первого элемента ИЛИ, выход которого соединен с информационным входом второго регистра сдвига, j-й выход которого соединен с вторым входом j-го элемента И второй группы, первый вход которого соединен с выходом признака возможности выполнения перехода j-й модели перехода, выход j-го элемента И второй группы соединен с входом j-го датчика случайных чисел группы, выход которого соединен с вторым входом j-й схемы сравнения группы, первый вход которой соединен с выходом j-го регистра группы, вход сброса счетчика соединен с выходом второго элемента ИЛИ, j-й вход которого, объединенный с входом признака разрешения выполнения перехода j-й модели перехода, соединен с выходом j-й схемы сравнения группы.

РИСУНКИ

Рисунок 1