Letysite.ru

IT Новости с интернет пространства
0 просмотров
Рейтинг статьи
1 звезда2 звезды3 звезды4 звезды5 звезд
Загрузка...

Безопасность сети петри

Задачи анализа сетей Петри

Безопасность

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

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

Если pi I(tj) и pi О(tj), тогда добавить pi к О(tj).

Если pi О(tj) и pi I(tj), тогда добавить pi к I(tj).

Простая сеть Петри на рис. 4.1 преобразована в безопасную на рис. 4.2.

Рис. 3.1. Небезопасная сеть Петри. Рис. 3.2 Безопасная сеть Петри

Ограниченность

Безопасность – это частный случай более общего свойства ограниченности. Позиция является k-безопасной или k-ограниченной, если количество фишек в ней не может превышать целое число k.

1-безопасная позиция называется просто безопасной. Заметим, что граница k‘ по числу фишек, которые могут находиться в позиции, может быть функцией от позиции (например, позиция p1 может быть 3-безопасной, тогда как позиция р2 – 8-безопасной). Однако, если позиция pi k -безопасна, то она также и k‘-безопасна для всех k‘ ≥ k. Поскольку число позиций конечно, можно выбрать k, равное максимуму из границ каждой позиции, и определить сеть Петри k-безопасной, если каждая позиция сети k-безопасна.

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

Сохранение

Определение 4.3. Сеть Петри С = (Р, Т, I, О) с начальной маркировкой μ называется строго сохраняющей, если для всех μ’ R(C, μ )

.

Строгое сохранение – это очень сильное ограничение. Например, из него немедленно следует, что число входов в каждый переход должно равняться числу выходов, |I(tj)| = |О(tj)| . Если бы это было не так, запуск перехода изменил бы число фишек в сети.

Однако для более общего представления о свойстве сохранения рассмотрим рис. 4.3. Изображенная на нем сеть Петри не является строго сохраняющей, поскольку запуск перехода t1 или t2 уменьшит число фишек на 1, а запуск перехода t3 или t4 добавит фишку к маркировке. Мы можем тем не менее преобразовать эту сеть Петри в сеть на рис. 4.4, являющуюся строго сохраняющей.

Рис. 3.3. Не строго сохраняющая сеть Петри Рис. 3.4. Строго сохраняющая сеть Петри

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

Фишка определяется ее позицией в сети, все фишки в позиции неразличимы. Следовательно, веса связываются с каждой позицией сети. Вектор взвешивания w = (w 1, w 2, . w n) определяет вес w i для каждой позиции pi P.

Сеть Петри С = (Р, Т, I, О) с начальной маркировкой μ называется сохраняющей по отношению к вектору взвешивания w, w = (w 1, w 2, . w n), n = |Р|, w i ≥ 0, если для всех μ’ R(C, μ )

.

Строго сохраняющая сеть Петри является сохраняющей по отношению к вектору взвешивания (1, 1, . 1). Все сети Петри являются сохраняющими по отношению к вектору взвешивания (0, 0, . 0). Поэтому сеть Петри будем называть сохраняющей, если она сохраняющая по отношению к некоторому положительному ненулевому вектору взвешивания w > 0 (с положительными ненулевыми весами, wi > 0). Так сеть Петри с рис. 4.3 является поэтому сохраняющей, поскольку она сохраняющая по отношению к (1, 1, 2, 2, 1). Сеть Петри с рис. 3.4 не является сохраняющей.

Активность

Тупик в сети Петри – это переход (или множество переходов), которые не могут быть запущены. Переход называется активным, если он не заблокирован (нетупиковый). Это не означает, что переход разрешен, скорее он может быть разрешенным. Переход tj сети Петри С называется потенциально запустимым в маркировке μ, если существует маркировка μ’ R(C, μ), в которой tj разрешен. Переход активен в маркировке μ, если потенциально запустим во всякой маркировке из R(C, μ). Следовательно, если переход активен, то всегда возможно перевести сети Петри из ее текущей маркировки в маркировку, в которой запуск перехода станет разрешенным.

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

Уровень 0: Переход tj обладает активностью уровня 0, если он никогда не может быть запущен.

Уровень 1: Переход tj обладает активностью уровня 1, если он потенциально запустим, т.е. если существует такая tj μ’ R(C, μ), что tj разрешен в μ’.

Уровень 2: Переход tj обладает активностью уровня 2, если для всякого целого n существует последовательность запусков, в которой tj присутствует по крайней мере n раз.

Уровень 3: Переход tj обладает активностью уровня 3, если существует бесконечная последовательность запусков, в которой tj присутствует неограниченно часто.

Уровень 4: Переход tj обладает активностью уровня 4, если для всякой μ’ R(C, μ) существует такая последовательность запусков σ, что tj разрешен в δ(μ’, σ).

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

В качестве примера, иллюстрирующего уровни активности, рассмотрим сеть Петри на рис. 3.5.

Переход t не может быть запущен никогда; он пассивен. Переход t1 можно запустить точно один раз; он обладает активностью уровня 1. Переход t2 может быть запущен произвольное число раз, но это число зависит от числа запусков перехода t3. Если мы хотим запустить t2 пять раз, мы запускаем пять раз t3, затем t1 и после этого пять раз t2. Однако, как только запустится t1 (t1 должен быть запущен до того, как будет как будет запущен t2), число возможных запусков t2 станет фиксированным. Следовательно, t2 обладает активностью уровня 2, но не уровня 3. С другой стороны, переход t3 можно запускать бесконечное число раз, и поэтому он обладает активностью уровня 3, но не уровня 4, поскольку, как только запустится t1, t3 больше запустить будет нельзя.

Безопасность сетей Петри. Задача о взаимном исключении

Безопасность сетей Петри. Задача о взаимном исключении.

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

Определение 4.1. Позиция pi P сети Петри С= (Р, Т, I, О)

с начальной маркировкой μ является безопасной, если μ(рi) 1 Для любой μ’ R(C, μ.). Сеть Петри безопасна, если безопасна каждая ее позиция.

Безопасность — очень важное свойство для устройств аппарат­ного обеспечения. Если позиция безопасна, то число фишек в ней равно 0 или 1. Следовательно, позицию можно реализовать одним Триггером.

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

Если позиция не является кратной входной или кратной выход­ной для перехода, ее можно сделать безопасной. К позиции *рi которую необходимо сделать безопасной, добавляется новая пози­ция p’i. Переходы, в которых pi используется в качестве входной или выходной, модифицируются следующим образом:

Читать еще:  Антивирус удаляет игру что делать

Если Pi I(tj) и Pi 0(tj), тогда добавить p’i к 0(tj).

Если Pi 0(tj) и Pi I (tj), тогда добавить р’i к I (tj).

Цель введения этой новой позиции pi — представить условие «рi пуста». Следовательно, pi и pi, дополнительны; pi имеет фишку, только если рi— не имеет фишки и наоборот. Любой переход, удаля-

ющий фишку из рi должен помещать фишку в pi, а всякий переход, удаляющий фишку из pi, должен помещать фишку в pi. Начальная маркировка также должна быть модифицирована для обеспечения того, чтобы точно одна фишка была либо в либо в рi. (Мы допускаем, что начальная маркировка безопасна.) За­метим, что такая принудительная безопасность возможна только для позиций, которые в начальной маркировке являются безопасными и входная и выходная кратность которых равна О или 1 для всех переходов. Позиция, имеющая для некоторого перехода выходную кратность 2, будет получать при его запуске две фишки и, следова­тельно, не может быть безопасной. Простая сеть Петри на рис. 4.1 преобразована в безопасную, как показано на рис. 4.2.

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

Первый процесс считывает значение x из разделяемого объекта;

Второй процесс считывает значение х из разделяемого объекта;

Первый процесс вычисляет новое значение x/ = f(х);

Второй процесс вычисляет новое значение хn = g(x);

Первый процесс записывает х’ е разделяемый объект;

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

Результат вычисления первого процесса потерян, так как теперь значением разделяемого объекта является g(x), в то время как им Должно быть либо g(f(x)), либо f(g(x)). (Представьте себе, что g(x) — «снять со счета х 1000 долл.», f(x) — «поместить на счет х 1000 долл.», а процессы 1 и 2 — банковские операции.)

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

Эта задача может быть решена сетью Петри, как показано на рис. 3.28. Позиция T представляет собой разрешение для входа в критическую секцию. Для того чтобы какой-либо процесс вошел в критическую секцию, он должен иметь фишку в p1 или в р2 соот­ветственно, свидетельствующую о желании попасть в критическую секцию, а также должна существовать фишка в t1, дающая раз­решение на вход. Если оба процесса пытаются войти в критическую секцию одновременно, то переходы t1 и t2 вступят в конфликт, и только один из них сможет запуститься. Запуск tt запретит переход t2, вынуждая процесс 2 ждать, пока первый процесс выйдет из своей критической секции и возвратит фишку обратно в позицию T.

Сети Петри как инструмент анализа системы защиты конфиденциальной информации Текст научной статьи по специальности «Компьютерные и информационные науки»

Аннотация научной статьи по компьютерным и информационным наукам, автор научной работы — Миронова Валентина Григорьевна, Шелупанов Александр Александрович

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

Похожие темы научных работ по компьютерным и информационным наукам , автор научной работы — Миронова Валентина Григорьевна, Шелупанов Александр Александрович

PETRI NETS AS A TOOL FOR THE ANALYSIS OF THE PROTECTION CONFIDENTIAL INFORMATION

Building security is a prerequisite for the security of confidential information stored and processed in the information system . System requirements of information security are formed based on the results of the survey and information system aimed at neutralizing the vulnerabilities of the system. One way of security analysis system is the construction of colored Petri nets. With the help of Petri nets functioning of the survey is conducted of the implemented system security and identify its weaknesses.

Текст научной работы на тему «Сети Петри как инструмент анализа системы защиты конфиденциальной информации»

Цыбулин Анатолий Михайлович

Федеральное государственное бюджете образовательное учреждение высшего профессионального образования «Волгоградский государственный университет». E-mail: anatsybulin@yandex.ru.

400062, г. Волгоград, пр. Университетский, 100.

Зав. кафедрой информационной безопасности.

Tsybulin Anatoly Mihaylovich

Volgograd State University.

100, Universitetsky Pr., Volgograd, 400062, Russia.

Head of Department of Information Security.

ВТ. Миронова, АЛ. Шелупанов

СЕТИ ПЕТРИ КАК ИНСТРУМЕНТ АНАЛИЗА СИСТЕМЫ ЗАЩИТЫ КОНФИДЕНЦИАЛЬНОЙ ИНФОРМАЦИИ

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

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

Система защиты конфиденциальной информации; информационная система; сети .

V.G. Mironova, A.A. Shelupanov

PETRI NETS AS A TOOL FOR THE ANALYSIS OF THE PROTECTION CONFIDENTIAL INFORMATION

Building security is a prerequisite for the security of confidential information stored and processed in the information system. System requirements of information security are formed based on the results of the survey and information system aimed at neutralizing the vulnerabilities of the system. One way of security analysis system is the construction of colored Petri nets. With the help of Petri nets functioning of the survey is conducted of the implemented system security and identify its weaknesses.

System to protect confidential information; information system; Petri net.

Развитие информационных систем обработки и хранения конфиденциальной информации диктует необходимость построения надежной системы защиты конфиденциальной информации (СЗКИ).

Построение СЗКИ проводится в несколько этапов. Первым этапом является

а также составляются требования к СЗКИ.

Требования к СЗКИ, в зависимости от вида КИ определяются согласно нор- ( ).

«О персональных данных» от 27 июля 2006 г., для всех информационных систем персональных данных (ИСПДн) должны быть построены СЗКИ [1]. При построе-

ждении методов и способов защиты персональных данных, обрабатываемых в ин-

Воспользуемся аппаратом раскрашенных сетей Петри, как инструментом анализа СЗКИ, реализованной в системе. Требования к ИСПДн установлены в [2]. Сеть Петри представляет собой двудольный граф вида:

П = , где A — множество позиций сети Петри, моделирующих состояние рассматриваемого процесса;

T — множество переходов сети Петри, моделирующих условия перехода из состояние в состояние;

Читать еще:  Законодательные основы обеспечения безопасности

щая множество T в множество A [3].

Существует несколько видов сетей Петри:

♦ временные сети — для учета временных характеристик;

♦ раскрашенные сети — интерпретация реальных систем.

Однако в раскрашенных сетях не допускается представление эффектов размножения и синхронизации. Меткам раскрашенной сети Петри приписывают ат, . -, . -ния процессов обработки ПДн в ИСПДн и формирования требований к СЗКИ будем использовать аппарат раскрашенных сетей Петри.

Пусть в ИСПДн №1 обрабатываются сведения о фамилии, имени, отчестве, адресе места жительства сотрудника, объем ПДн не превышает 1000 записей. Согласно [4], ПДн, обрабатываемые в ИСПДн №1 относятся к 3-й категории и 3-му объему, поэтому ИСПДн №1 присвоен класс 3.

1 : , -, , связи общего пользования, ИСПДн находится на территории РФ.

Идентификация пользователя при входе в ИСПДн №1 производится по паролю, требований к которому в организации не установлено. Регистрация пользователя при входе (выходе) в систему (из системы) производится по идентификатору , -мы и ее программного останова не производится.

Пользователь осуществляет ввод/изменение данных в ИСПДн №1.

На рис. 1 представлена блок-схема алгоритма и сеть Петри входа пользователя в ИСПДн №1 и используются следующие обозначения:

pass — пароль, введенный пользователем для аутентификации (фишка типа 1

1ёеп — идентификатор, который использует пользователь для идентификации в системе (фишка типа 2 — идентификатор корректен и удовлетворяет всем условиям; фишки другого типа — неправильные и (юга) некорректные идентификаторы); а1 — пароль введен пользователем в окно запроса пароля; а2 — идентификатор введен пользователем;

а3 — предъявленный идентификатор подтвержден введенным паролем, аутентификация прошла успешно;

Рис. 1. Блок-схема алгоритма и сеть Петри вход пользователя в ИСПДн №1

а4 — пользователь санкционировано вошел в ИСПДн №1; а5 — пользователь не получил право доступа в ИСПДн №1; t1 — ввод пароля и идентификатора пользователем; t2 — ввод идентификатора пользователем; t3 — аутентификация пользователя в системе;

mistake — предъявленный идентификатор не соответствует введенному паролю; vivod oshibki — вывод ошибки на экран; vhod — идентификатор и пароль приняты.

Согласно [2] СЗКИ для ИСПДн №1 должна удовлетворять требованиям, указанным в табл. 1.

Т ребования к ИСПДн № 1

№ п/п Наименование подсистемы Требования

1. Управление доступом ♦ идентификация и про верка подлинности пользователя при входе в систему ИС по паролю условно-постоянного действия длиной не менее шести буквенно-цифровых символов;

2. Регистрация и учет ♦ регистрация входа (выхода) пользователя в систему (из системы) либо регистрация загрузки и инициализации операционной системы и ее программного останова; ♦ с помощью их маркировки и занесение учетных данных в журнал учета;

3. Обеспечение целостности ♦ СЗКИ, обрабатываемой информации, а также неизменность программной среды; ♦ при изменении программной среды и пользователей ИС с помощью тест-программ, имитирующих попытки несанкционированного дос; ♦ наличие средств восстановления СЗКИ, предусматривающих ведение двух копий программных компонентов СЗКИ, их периодическое обновление и контроль работоспособности

На рис. 2 показана блок-схема алгоритма и сеть Петри для реализации требования к СЗКИ по управлению доступом и использованы следующие обозначения: pass — пароль, введенный пользователем для аутентификации (фишка типа 1

— правильный пароль, который соответствует всем требованиям; фишки другого типа — неправильные и (или) некорректные пароли);

iden — идентификатор, который использует пользователь для идентификации в ( 2 — ;

A1 — пароль введен пользователем в окно запроса пароля;

A2 — пароль, введенный пользователем, единственный в БД паролей;

A3 — пароль содержит не менее шести символов, среди которых имеются буквы и цифры;

A4 — идентификатор введен пользователем;

A5 — предъявленный идентификатор подтвержден введенным паролем, аутентификация прошла успешно;

T1 — ввод пароля в окно запроса пароля;

T2 — проверка единственности пароля в БД паролей;

mistake — предъявленный идентификатор не соответствует введенному паролю; vivod oshibki — вывод ошибки на экран; vhod — идентификатор и пароль приняты.

Рис. 2. Блок-схема критерия и сеть Петри

Цвет фишек сети Петри, построенной для реализованной в ИСПДн №1 подсистемы управления доступом красный, а для подсистемы управления доступом согласно требованиям нормативно-законодательной базы — зеленый.

На рис. 3 фишками красного цвета отмечены требования, реализованные в ИСПДн №1, а зеленого цвета — требования согласно [2].

На рис. 3 показано, что подсистема управления доступом, которая используется в ИСПДн №1, имеет ряд недостатков относительно требований законодательной базы РФ. А именно, в подсистеме управления доступом не реализовано требование по проверке пароля на содержание в нем не менее шести символов, среди которых имеются буквы и цифры. Поэтому используемые механизмы защиты в подсистеме управления доступом в ИСПДн №1 являются противоречивыми и недостаточными. Проектируя СЗКИ необходимо учесть недостатки ранее реализованной подсистемы управления доступом и устранить их.

Рис. 3. Раскрашенная сеть Петри для подсистемы управления доступом Выводы:

1. Согласно [5] существует несколько видов конфиденциальной информа-

для системы обработки ПДн, который показал недостаточность применяемых мер защиты.

2. Аппарат сети Петри является средством моделирования различных ИС и СЗКИ, и дает возможность получить информацию о структуре и динамическом поведении ИС, СЗКИ и тем самым спроектировать надежную СЗКИ, а использование фишек различных цветов при проведении обследования СЗКИ позволяет выявить уязвимые места ИС и СЗКИ.

1. Шелупанов А А., Миронова ВТ. и др. Автоматизированная си стема предпроектного обследования информационной системы персональных данных «АИСТ-П» // Докл. Том. гос. ун-та систем управления и радиоэлектроники. — 2010. — № 1 (21). — Ч. 1. — С. 14-22.

» // -му и экспертному контролю Российской Федерации от 5 февраля 2010 г. № 58.

3. Котов В.Е. Сети Петри. — М: Наука, 1984.

4. Приказ Федеральной службы по техническому и экспортному контролю, ФСБ РФ и Министерства информационных технологий и связи РФ от 13 февраля 2008 г. № 55/86/20 «Об утверждении Порядка проведения классификации информационных систем персональных данных».

5. Указ Президента Российской Федерации от 23.09.2005 г. №1111 «Перечень сведений

6. Миронова ВТ., Шелупанов А.А. Предпроектное проектирование информационных систем

ун-та систем управления и радиоэлектроники. — 2010. — № 2 (22). — Ч. 1. — С. 257-259. Статью рекомендовал к опубликованию к.ф.-м.н. ГА. Афонин.

Миронова Валентина Григорьевна

Томский государственный университет систем управления и радиоэлектроники. E-mail: mvg@security.tomsk.ru.

Кафедра комплексного обеспечения информационной безопасности электронновычислительных систем; аспирант.

Шелупанов Александр Александрович E-mail: saa@udcs.ru.

Проректор по научной работе; д.т.н.; профессор.

Mironova Valentina Grigor’evna

Tomsk State University of Control Systems and Radioelectronics.

40, Lenin Pr., Tomsk, 634050, Russia.

The Departmant of Integrated Information Security Computer Systems; Postgraduate Student.

Shelupanov Alexander Alexandrovich

Vice Rector for Research; Dr. of Eng. Sc.; Professor.

О.М. Лепешкин, Р.С. Гаппоев

МАНДАТНАЯ МОДЕЛЬ РАЗГРАНИЧЕНИЯ ДОСТУПА НА ОСНОВЕ

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

доступа на основе мандатной политики безопасности: «Белла — Лападула» и «Китайской стены», для систем реального времени. Выявлены основные недостатки и противоречия (деклассификация объектов) этих моделей, которые потенциально могут нарушать безо. -доставления прав доступа на основе «полномочий субъекта» и «дотска полномочий у объ-». , -вой которых являются предикаты.

Читать еще:  Психологические аспекты безопасности

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

Сети Петри

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

При графической интерпретации сеть Петри представляет собой граф особого вида, состоящий из вершин двух типов — позиций и переходов, соединенных ориентированными дугами, причем каждая дуга может связывать лишь разнотипные вершины (позицию с переходом или переход с позицией). Вершины-позиции обозначаются кружками, вершины-переходы — черточками. С содержательной точки зрения переходы соответствуют событиям, присущим исследуемой системе, а позиции — условиям их возникновения. Таким образом, совокупность переходов, позиций и дуг позволяет описать причинно-следственные связи, присущие системе, но в статике. Чтобы сеть Петри «ожила», вводят еще один вид объектов сети — так называемые фишки, или метки позиций. Переход считается активным (событие может произойти), если в каждой его входной позиции есть хотя бы одна фишка [3].

Расположение фишек в позициях сети называетсяразметкой сети (пример перемещения фишек по сети приведен на рисунке 14.1.).

Рис. 14.1. Пример изменения разметки сети Петри при срабатывании переходов

В аналитической форме сеть Петри может быть представлена следующим образом:

где В = i> — конечное непустое множество позиций;

D = i > — конечное непустое множество переходов;

I: BxD → 0,1 — входная функция (прямая функция инцидентности), которая для каждого перехода задает множество его входных позиций;

О: DxB→ 0,1 — выходная функция (обратная функция инцидентности), которая для каждого перехода задает множество его входных позиций;

М — функция разметки сети, т.е. М: В0, 1, 2. — ставит каждой позиции сети в соответствие неотрицательное целое число.

Срабатывание перехода dj изменяет разметку сети М(В) на разметку M'(B) по следующему правилу:

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

Основные направления анализа сети Петри следующие:

1. Проблема достижимости: в сети Петри с начальной разметкой М. Требуется определить, достижима ли принципиально некоторая разметка М’ из М

С точки зрения исследования моделируемой системы, эта проблема интерпретируется как проблема достижимости (реализуемости) некоторого состояния системы.

2. Свойство живости. Под живостью перехода понимают возможность его срабатывания в данной сети при начальной разметке M.

Анализ модели на свойство живости позволяет выявить невозможные состояния в моделируемой системе (например, неисполняемые ветви в программе).

3. Безопасность сети. Безопасной является такая сеть Петри, в которой ни при каких условиях не может появиться более одной метки в каждой из позиций.

Для исследуемой системы это означает возможность функционирования ее в стационарном режиме. На основе анализа данного свойства могут быть определены требования к буферным накопителям в системе.

Итак, достоинства сетей Петри заключаются в том, что они:

1. позволяют моделировать ПП всех возможных типов с учетом вероятных конфликтов между ними;

2. обладают наглядностью и обеспечивают возможность автоматизированного анализа;

3. позволяют переходить от одного уровня детализации описания системы к другому (за счет раскрытия/закрытия переходов).

Контрольные вопросы

1. Дайте формальное определение сети Петри?

2. Что такое разметка сети?

3. Укажите основные направления анализа сетей Петри.

4. Перечислите достоинства и недостатки сетей Петри.

Сохранение сетей Петри. P- и V- системы. Пример.

Дата добавления: 2013-12-23 ; просмотров: 2896 ; Нарушение авторских прав

Ограниченность сетей Петри. Задача об обедающих мудрецах.

Сеть Петри безопасна, если число фишек в каждой позиции не может превысить 1; сеть Петри ограниченна, если существует такое целое k, что число фишек в любой позиции не может превысить k. Оба этих свойства можно проверить с помощью дерева достижимо­сти. Сеть Петри ограниченна тогда и только тогда, когда символ ω отсутствует в ее дереве достижимости. Присутствие символа ω в дереве достижимости означает, что число фишек потенциально не ограничено; существует последовательность запусков переходов, которую можно повторить произвольное число раз, увеличивая ко­личество фишек до произвольно большого числа. Таким образом, если имеется символ ω, сеть неограниченна. Кроме того, поло­жение символа ω показывает, какие позиции

Обратное утверждение также является верным, если сеть Петри неограниченна, то число достижимых маркировок бесконечно. По­скольку дерево достижимости конечно, бесконечное число дости­жимых маркировок отражает присутствие символа ω.

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

Найденное значение является границей числа фишек для заданной позиции. Если граница для всех позиций равна (1), сеть безопасна.

На рис. 4.17 демонстрируется использование дерева достижи­мости для определения ограниченности.

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

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

На рис. 3.32 показано решение этой задачи с помощью сети Петри. Позиции С1,…,C5 представляют палочки для еды, и так как каждая из них первоначально свободна, то в начальной мар­кировке в каждой из этих позиций имеется фишка. Каждый мудрец представлен двумя позициями Mi и Ei для состояний размышления и принятия пищи соответственно. Для того чтобы мудрец перешел из состояния размышления в состояние принятия пищи, обе па­лочки (слева и справа) должны быть свободны. Это легко модели­руется сетью Петри.

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

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

Определение 4.3. Сеть Петри С — (Р, Т, I, О) с начальной маркировкой μ называется строго сохраняющей, если для всех μ’ R(С, μ)

μ'(pi)= μ (pi)

Строгое сохранение — это очень сильное ограничение. На­пример, из него немедленно следует,

Ссылка на основную публикацию
Adblock
detector