- •Математическая индукция. Принципы простой индукции, модифицированной простой индукции, строгой индукции.
- •1) Доказать, что справедливо s(1);
- •Основные принципы доказательства правильности для блок-схем с использованием индукции. Инварианты цикла при доказательстве правильности.
- •Метод индуктивных утверждений как обобщение метода доказательства правильности с использованием индукции. Верификация программ.
- •Метод индуктивных утверждений.
- •Метод индуктивных утверждений
- •Надежность программных средств
- •Доказательство правильности программы
- •Формализация доказательства с помощью индуктивных утверждений. Множество условий верификации.
- •Аксиоматический подход к доказательству частичной правильности и его идентичность методу индуктивных утверждений.
- •Рекурсивные программы. Доказательство их правильности методом структурной индукции. Рекурсия
- •Метод структурной индукции
- •Моделирование. Природа моделируемых систем. Применение теории сетей Петри. Прикладная и чистая теории сетей Петри.
- •Структура сетей Петри. Способы задания сетей Петри. Графы сетей Петри.
- •Маркировка сетей Петри. Правила выполнения сетей Петри. Пространство состояний сетей Петри.
- •События и условия. Моделирование процесса сетью Петри. Примитивные и непримитивные события. Одновременность и конфликт.
- •Сети Петри для моделирования. Моделирование аппаратного обеспечения сетями Петри (конечные автоматы, эвм с конвейерной обработкой, кратные функциональные блоки).
- •Сети Петри для моделирования. Моделирование программного обеспечения сетями Петри (блок-схемы, обеспечение параллелизма).
- •Сети Петри в решении задач синхронизации: задача о взаимном исключении, задача о производителе/потребителе, задача об обедающих мудрецах, задача о чтении/записи, p- и V-системы и др.
- •Задачи анализа сетей Петри: безопасность, ограниченность, сохранение, активность, покрываемость.
- •Дерево достижимости сети Петри.
- •Использование дерева достижимости для анализа сетей Петри.
- •Матричные уравнения и их использование для анализа сетей Петри.
- •Сети Петри с ограничениями и подклассы сетей Петри.
- •1) Автоматные сети Петри
- •2) Маркированные графы
- •3) Сети свободного выбора
- •4) Правильные сети Петри
- •Расширенные модели сетей Петри (области ограничения, переходы исключающее или, сети со сдерживающими дугами, сети с приоритетами, временные сети)
- •Взаимосвязь мощности моделирования и мощности разрешения сетей Петри
Сети Петри в решении задач синхронизации: задача о взаимном исключении, задача о производителе/потребителе, задача об обедающих мудрецах, задача о чтении/записи, p- и V-системы и др.
Задача о взаимном исключении
Данная задача возникает в условиях, когда несколько процессов разделяют общую переменную. Каждый процесс может вначале считать значение переменной, затем вычислить новое значение и записать его на то же место. Если два процесса одновременно будут выполнять указанную последовательность действий, то может возникнуть неправильная работа системы. Например, оба процесса считают по очереди старое значение переменной, а при записи одно из новых значений записанное первым будет уничтожено. Таким образом, результат работы одного из двух процессов будет утерян.
Процесс I Процесс 2
Рис. 5.4. Механизм взаимного исключения
Для правильной работы системы необходимо обеспечить механизм взаимного исключения, при котором одновременно не более чем один процесс имеет доступ к разделяемой переменной. Часть программного кода процесса, в котором выполняется доступ к разделяемой переменной и при этом требуется защита от доступа к разделяемой переменной другого процесса, называется критической секцией. Механизм взаимного исключения работает таким образом, что при выполнении критической секции какого-либо процесса, критические секции других процессов блокируются. Взаимодействие двух процессов через механизм взаимного исключения критических секций представлен сетью Петри на рис.5.4.
Переходы и находятся в конфликте за метку в позиции . Запуск, например, перехода , вынуждает 1-ый процесс ждать, пока 2-ой процесс выйдет из своей критической секции и возвратит метку в позицию .
Задача о производителе/потребителе
В этой задаче разделяемым объектом является буфер. Процесс производитель порождает компоненту информации и размещает ее в буфер. Процесс потребитель ждет пока компонента информации разместится в буфере, после этого он может ее удалить из буфера и использовать. Как правило используется буфер ограниченной емкости, то есть имеется возможность разместить в нем не более компонентов данных. В этом случае скорость заполнения буфера процессами-производителями и скорость извлечения данных процессами - потребителями должны быть сопоставимы. На рис.5.5 представлена сеть Петри, отражающая рассматриваемое действие процессов.
Производитель Потребитель
Рис.5.5. Механизм обмена через буфер
Буферу сопоставлены две позиции: В − указывает на количество компонентов данных размещенных в буфере, но еще не использованных, В° − количество свободных мест в буфере для размещения компонентов данных. Первоначально позиция В° имеет меток, а позиция В не имеет. Если буфер будет полностью заполнен, то в позиции В будет меток, а в В° − 0 меток. Таким образом, доступ процесса-производителя в заполненный буфер невозможен, так как в позиции В° будет 0 меток.
Задача об обедающих мудрецах
Задача об обедающих мудрецах была предложена Дейкстрой в и связана мудрецами сидящими за круглым столом и каждый из них может пребывать в одном из двух состояний: думает или обедает. На столе блюда китайской кухни, а между мудрецами лежит по одной палочке. Для приема пищи мудрец должен взять палочку слева и палочку справа. В этом случае соседи обедающего мудреца могут только думать и ждать, когда освободятся палочки, чтобы приступить к обеду. На рис.5.6 сетью Петри представлено взаимодействие трех процессов (трех мудрецов), состояния которых отражены позициями и : −обедает, − думает. Позиции представляют палочки для еды (разделяемые ресурсы). В исходной маркировке мудрецы думают, а все палочки свободны. При такой исходной маркировке любой из трех мудрецов может приступить к обеду, захватив палочки слева и справа.
Рис.5.6. Механизм разделения ресурса
Задача о чтении/записи
Рассматривается взаимодействие процессов двух типов: процессы чтения и процессы записи. Все процессы совместно используют общий файл или переменную или элемент данных. Процессы чтения не изменяют объект, а процессы записи изменяют. Поэтому процессы записи должны взаимно исключать (см. рис. 5.4) все другие процессы чтения и записи, в то время как несколько процессов чтения могут иметь доступ к разделяемым данным одновременно. Взаимодействие процессов необходимо организовывать так, чтобы не могла возникнуть тупиковая ситуация и был обеспечен механизм взаимного исключения со стороны процессов записи.
Чтение
Запись
Рис.5.7. Механизм взаимодействия процессов чтения и записи
На рис.5.7 представлена сеть Петри, имитирующая взаимодействие процессов чтения и записи при условии, что число процессов чтения и записи ограничено величиной . Это означает, что и при неограниченном числе процессов чтения, одновременно могут выполняться не более процессов. Начальное маркирование сети предполагает наличие процессов чтения и процессов записи. Из данной сети видно, что процессы находятся в конфликте за метку в позиции . При захвате меток процессом записи позиция остается без меток, тем самым блокируется запуск процессов чтения, до тех пор пока процесс записи не возвратит меток в позицию .
Следует обратить внимание на то, что в данной сети позиция после завершения процессов чтения всегда будет иметь меток и тем самым разрешает запуск процессов записи.
В тех случаях, когда число одновременно читающих процессов не ограничено, моделировать взаимодействие процессов чтения и записи с помощью сети Петри оказывается невозможным. Проблема заключается в отсутствии механизма блокировки неограниченного числа одновременно читающих процессов при выполнении процессов записи. Для хранения числа читающих процессов можно ввести специальную позицию счетчик. При запуске каждого процесса чтения в счетчик добавляется единица, а по окончании единица вычитается. Однако это не решает проблему, так как для запуска процесса записи необходимо, чтобы в позиции-счетчике отсутствовали метки. Механизма проверки неограниченной позиции на нуль в сетях Петри нет. Это показывает, что возможности сетей Петри для отображения взаимодействия процессов далеко не безграничны.
Р − и V − операции над семафорами
Одним из распространенных механизмов синхронизации процессов являются Р - и V - операции над семафорами. Семафор − это переменная, которая может принимать только неотрицательные целые значения. V - операция увеличивает значение на единицу, а Р-операция уменьшает его на единицу. Р-операция может выполняться только в том случае, когда полученное значение семафора остается неотрицательным. Таким образом, если значение семафора равно 0, то Р-операция должна ждать, пока какой-нибудь другой процесс не выполнит V -операцию. Р- и V -операции определены как примитивные, то есть никакая другая операция не может изменять значения семафора одновременно с ними. На рис.5.8 показано как такие операции моделируются сетью Петри. Каждый семафор моделируется позицией, количество меток r в позиции показывает значение семафора. Р-операции используют позицию семафора в качестве входа, а V-операции в качестве выхода.
r
Рис.5.8. Механизм семафоров