Лекция 8 Системное программирование. Системное проектирование взаимодействия процессов. Сети Петри. Флаговые и пусковые функции. Асинхронные протоколы

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

Лекция

Содержание I. Сети Петри. Асинхронно взаимодействующие процесы Элементарные ППФ(PN) Определение разметки 1.3 Интерпретация PN 1) Правила срабатывания PN 2) Правило изменения разметки 1.4. Семантика PN Семантика перехода t. Семантика события. Семантика сценариев Пример 3. Четыре обедающих философа. 1.5 Сети Петри для конвейерных (pipe-line) систем. Пример 5 Асинхронный конвейер 1.6. CASH – конвейер. CFN (cash flow net). Имитационное моделирование CFN. II.Метод пусковых и флаговых функций. Асинхронные Асинхронный протокол R. Потребитель считывает и обрабатывает сообщения, беря их из регистра R Пример 8. Сеть Петри системы А – запрос на посылку  а ... Полное содержание

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

• Рабочая программа учебной дисциплины (модуля) Системное программирование, 108.12kb.
• Техническое задание на выполнение курсовой работы по дисциплине "Системное программирование, 120.51kb.
• Асинхронные программы. Возможные некорректности в их работе. Сети Петри. Разметка сети, 70.35kb.
• Стэнли Янг системное управление организациейянг С. Системное управление организацией, 6260.5kb.
• Программа вступительного экзамена по специальности 05. 13. 18 Математическое моделирование,, 115.33kb.
• Общая характеристика и классификация программного обеспечения и базовых технологий, 132.64kb.
• М. В. Ломоносова Факультет вычислительной математики и кибернетики Н. В. Вдовикина,, 2124.49kb.
• Ые системы", "Операционные системы, среды и оболочки" и "Операционные системы и системное, 1294.27kb.
• Программа вступительного экзамена, 67.56kb.
• Лекция: Сети и сетевые операционные системы, 585.67kb.

Лекция 8

Системное программирование. Системное проектирование взаимодействия процессов. Сети Петри. Флаговые и пусковые функции. Асинхронные протоколы.


Под системой в этом случае понимают вычислительную систему (ВС), состоящую из процессоров (обычно разнородных) и запоминающих устройств. Например, процессоры: арифметическое устройство, устройство – шина, устройство управления памятью, устройство управления диском, устройство печати, устройство управления каналом и т.д.. Все эти устройства взаимодействуют между собой. Проектирование (программирование) такой ВС по сути дела имеет целью взаимоувязку процессов, происходящих в отдельных элементах системы, при выполнении конкретной нужной пользователю задачи. Для целей взаимоувязки (согласования) процессов в ВС служит специальный инструмент – операционная система, которая «прячет» от пользователя очень сложную логику взаимодействия процессов, оставляя ему только манипуляцию инструкциями, управляющими ОС. Иногда для объединения различных устройств в ВС нельзя воспользоваться штатной ОС, приходится создавать свою специализированную ОС. Пользователь, а тем более системный программист, должен понимать логику описания взаимодействия процессов в ВС. Одним из способов формализации такой логики могут служить сети Петри (PN).

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

Другим способом описания логики взаимодействия процессов может служить формальная система – асинхронный автомат, предложенная в 1967 г. Котовым – Нариньяни, которая в интерпретации к системному программированию носит название – «Метод пусковых и флаговых функций». По сути дела пусковые и флаговые функции специфицируют основные элементы сетей Петри. Таким образом, моделью взаимодействия общего вида служит сеть Петри, поведение которой управляется событиями.


I. Сети Петри. Асинхронно взаимодействующие процесы

1. Парадигмы последовательно-параллельных
   

процессов


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

а) Парадигма Клини.

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

б) Парадигма Ван-Хао (Вонга).

В сетях Ван-Хао (WN) события от вершины – инициатора распространяются «фронтально» (параллельно, независимо друг от друга). Для описания фронтального процесса WN представляется специальной ярусно-параллельной формой (ЯПФ), по которой строятся различные деревья (сценарии) фронтального распространения событий.

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

в) Парадигма Петри.(PN)

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

2. Формальная система для сетей Петри.
   

Формальная система определяет сеть Петри, где – множество позиций, – множество переходов; R – отношение, связывающее Р и Т в правильно построенные формулы (ППФ), L – разметка сети PN.

ППФ для PN суть картинка и задаётся направленным графом с двумя типами вершин Р и Т, при этом картинка PN понимается как некоторая формула, построенная по формальным правилам и называется ППФ(PN).

Процесс построения ППФ(PN) определяется индуктивно.

1) Элементарные ППФ(PN) – суть картинки следующего вида



где все P_i в бинарном отношении (P_i  t_j) называются входными позициями для перехода t_j, а P_k в бинарном отношении (t_j  P_k) называются выходными позициями для перехода t_j. Элементарная ППФ содержит ровно одну вершину типа t.

2) Операция композиции (конструирования) – отождествление вершин P в нескольких ППФ, дает снова ППФ. Пусть заданы две сети Петри PN₁ и PN₂. Из них можно сконструировать сложные сети Петри, показанные на примерах а), б), в).

а) отождествление (Р₃  Р₁ = Р₃) и отождествление (Р₁  Р₂ = Р₁)



б) отождествление (Р₁  Р₁ = Р₁) в) отождествление (Р₃  Р₂ = Р₃)




Определение разметки PN. Каждая позиция P  PN может быть пустой, либо содержать отметку (фишку), в этом случае говорят, что P  PN «занята». Для некоторых типов сетей позиция может содержать несколько фишек (может быть бесконечное число фишек). В настоящем рассмотрении позиция может быть в двух состояниях: «занята» / «не занята». В этом случае PN называется простой сетью Петри.

1.3 Интерпретация PN задает правила «срабатывания» переходов в PN и изменение разметок позиций, и тем самым определяет возникновение событий в PN, связанных с совершением переходов.

1) Правила срабатывания PN.

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



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




3) Правило единственного срабатывания определяется следующими картинками (формулами).







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

1. Семантика перехода t. С переходом t всегда связан некоторый процесс, который «включается» входными событиями, в результате процесса изменяется сущность (некоторая характеристика процесса), которая отмечается соответствующим выходным событием. С каждым переходом t (и, соответственно, с процессом) связан свой собственный процессор, который производит изменения сущности. Поэтому, когда срабатывает выходное событие, контролирующее изменение сущности, вообще говоря, процесс может продолжаться и дальше.
   

Таким образом семантика перехода S_t определяется , где C_t – концепт (сущность) изменение которого должно контролироваться некоторым событием _t, П_t – процесс (программа), приводящий к изменению C_t, П_t – процессор, который реализует процесс.

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

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

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

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

Пример 1.



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

Пример 2. PN аналог ЯПФ – две параллельные цепочки событий, два параллельных (независимых процесса), четыре сценария.

S₁ – t₁ t₂ t₃ t₄; S₂ – t₂ t₁ t₃ t₄; S₃ – t₁ t₂ t₄ t_3;; S₁ – t₂ t₂ t₄ t₃.


РN является формулой в формальной системе. Если ввести интерпретацию переходов t в сети в виде количества квантов времени исполнения перехода , то множество конкретных сценариев при всех возможных значениях  всех переходов не превысит множества цепочек событий в сети Петри. Таким образом формула (картинка) PN задает только логику взаимосвязи процессов. Конкретная реализация протекания процессов (сценарий) возникает при конкретных значениях времен переходов. (см. примеры 4, 5).

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

а) Содержательная модель


б) Сеть Петри




Процессы События


б₁–Ф₁ беседует

б₂–Ф₂ беседует

б₃–Ф₃ беседует

б₄–Ф₄ беседует е₁–Ф₁ ест

е₂–Ф₂ ест

е₃–Ф₃ ест

е₄–Ф₄ ест


КБ₁–Ф₁ закончил беседу

КБ₂–Ф₂ закончил беседу

КБ₃–Ф₃ закончил беседу

КБ₄–Ф₄ закончил беседу

КЕ₁–Ф₁ закончил есть

КЕ₂–Ф₂ закончил есть

КЕ₃–Ф₃ закончил есть

КЕ₄–Ф₄ закончил есть

В₁, В₂ – вилки свободны

Н₁, Н₂ – ножи свободны



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

Для примера 3 ЯПФ независимых (параллельных) процессов системы «четыре обедающих философа» имеет вид:





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

Процессы в ЯПФ связаны бинарным отношением «следует за», время работы каждого процесса может быть любым (в семантической модели каждый философ может тратить на еду и на беседу произвольное время). Если, в некотором смысле, «натянуть» граф ЯПФ на сетку физического времени, то процессы в процессорах Ф₁, Ф₂, Ф₃, Ф₄ – могут «скользить по процессорным стержням», а дуги «следуют за» должны быть «резиновыми». Процессы в каждом процессоре могут быть такими, что философы могут обгонять друг друга, приостанавливаться так, чтобы не рвать связи «следует за». Наделяя каждый элементарный процесс временем его «работы» можно моделировать поведение («гонки») в системе.


1.5 Сети Петри для конвейерных (pipe-line) систем.

Пример 4 Идеально сбалансированный синхронный конвейер. Модель RISC процессора. RISC-PN:

RISC (Reduced Instruction Set Computer) – буквально: вычислительная машина с сокращенным набором команд. Каждая команда раскладывается на элементарные операции, которые выполняются последовательно на станциях конвейера. Каждая конвейерная операция выполняется ровно за  квантов времени (такт конвейера). Входные данные поступают в каждом такте, выходные данные получаются через 4 такта. В RISC-конвейере обрабатываются одновременно данные поступившие за 4 последовательных такта.

Пример 5 Асинхронный конвейер. Информационный шлюз в Internet.

События в шлюзе:

HP_i – информация на входе станции есть; KP_i – станция свободна и готова к работе

Процессы на станциях обра-

ботки имеют времена:

₁ = 1 такт; ₂ = 3 т.; ₃ = 2 т.;

₄ = 4 т.





Диаграмма работы информационного шлюза.

1.6. CASH – конвейер. CFN (cash flow net).

Позиция в PN может быть «занята» более чем одной фишкой и таким образом может быть накопителем фишек (cash – позиция). В случае, когда cash –позиция является выходной для некоторого перехода t, правило срабатывания для t не требуют свободной позиции, после срабатывания перехода t фишка прибавляется к содержимому накопителя. PN с cash – позициями иногда называются cash flow net. (CFN) применяются для моделирования асинхронных взаимодействующих процессов, где идёт накопление вещества, энергии, информации. Процессы запускаются, если соответствующие накопители не пусты. На рисунке приводится пример банковского CFN – конвейера.

Пример 6: CFN – банковский конвейер «инвестирование бизнес – проектов».


t₄, t₅ – начальные стадии проектов (не дающие денежной отдачи),

t₆, t₇ – стадии самофинансирования и возврата долга в cash.

Имитационное моделирование CFN. Задаются времена процессов t₁, t₂, t₃, t₄, t₅, t₆, t₇. Задача моделирования – выделить кризисные ситуации, т.е. выделить такие комбинации времён процессов, которые приводят к заданному классу сценариев, например, тупиковых, когда cash не успевает наполняться и все процессы останавливаются, либо когда процессы возврата денег недопустимо затягиваются.

В имитационную модель CFN можно вводить неопределённость в виде предсказуемости/непредсказуемости поведения элементов системы.

II.Метод пусковых и флаговых функций. Асинхронные

протоколы.

Рассмотрим элементарную сеть Петри.



Сопоставим входным позициям флаговые функции (иногда говорят «флаги») , аналогично и выходным позициям флаги – . Введём интерпретацию – – флаг поднят; – флаг опущен (снят). Поднятые (опущенные) флаги соответствуют занятости (освобождению) позиции фишкой и таким образом определяют память о событиях, произошедших при срабатывании перехода. Каждому переходу t соответствует пусковая функция инициирующая процесс П_t, когда флаги всех входных позиций подняты, а выходных позиций опущены.

Асинхронный протокол для элементарной PN определяет запуск (начало) и окончание процесса П_t и задаётся правилами вида:

а) Начало П_t, если .

б) Окончание П_t -

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

Часто процессом называется процесс решения прикладной задачи пользователя. В этом случае несколько процессов такого рода требует для своей реализации одних и тех же ресурсов процессоров, памяти, каналов и т.д. С точки зрения операционной системы в ВС идут несколько прикладных задач (приложений) с разделяемыми ресурсами. При этом процесс П_t, погруженный в ОС, должен снабжаться дополнительными программными процедурами, работающими с флаговым регистром. Программа , где _ж – ожидание поднятия входных флагов (циклический опрос флагового регистра), _к – окончание процесса, опускание входных флагов и поднятие выходных флагов, обозначающих освобождение ресурсов, П – собственный вычислительный процесс. Если два процесса разделяют один и тот же ресурс R, и , то и – называются критическими участками соответствующих программ и не могут выполняться одновременно.

1. Асинхронное взаимодействие в мониторе (поставщик – потребитель) с одним общим разделяемым ресурсом.
   

Пример 7.. Система «поставщик – потребитель».




Поставщик генерирует сообщения и помещает их в регистр R. Потребитель считывает и обрабатывает сообщения, беря их из регистра R.

Процессы: П_1п – программа на процессоре П₁ использует печать; П_1Д – программа на процессоре П₁ использует диск; П_2Д – программа на процессоре П₂ использует диск; П_2п – программа использует печать. PN для системы «поставщик – потребитель» приведена ниже.

Пример 8. Сеть Петри системы (поставщик – потребитель).



Процессы События

 а₁ – подготовка сообщений  3 А – запрос на посылку

 а₂ – запись сообщений в R сообщений.

 b₁ – считывание сообщений  ЕА₂ – разрешение на сообще-

из R ние.

 b₂ – обработка сообщений  ЕА₁ – сообщения подготовле-

ны.

 R – регистр свободен (занят).

 ЗВ – запрос на приём сообще-

ний.

 ЕВ₂ – разрешение на прём

сообщений.

 ЕВ₁ – сообщения считаны из R.

Асинхронный протокол системы «поставщик – потребитель».

Флаговые функции:

флаговая функция принимает значение = 1 (флаг поднят, если произошло событие), иначе =0 (флаг опущен)

Пусковые функции:

.

Правила протокола:

1)

2)

3)



4)

2.2 Модели тупиковых ситуаций. (Тупики).

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

Следующий пример описывает логику взаимосвязи двух процессов, которая может привести к тупику.

Пример 9. Два процесса П₁и П₂ имеют два разделяемых ресурса – «печать» и «диск», которые используют так, как показано в соответствующей PN. – программы, требующие печать, – программы, требующие диск.

а) Начальная ситуация б) Тупиковая ситуация




События: П₁ – захват диска, П₂ – захват печати, Р_п – освобождение печати, Р_Д – освобождение диска.

Программа П₁, – «захватила» печать, а П₂ – «захватила» диск, далее система перешла в тупиковую ситуацию. До сих пор проблема тупиков («смертельных объятий») не имеет универсального решения. В каждом конкретном случае для разрешения проблемы тупиков применяются эвристики. Но всегда существует самый плохой выход избежать тупиковой ситуации. Это способ создания безтупиковой системы с правилом использования ресурсов – «всё или ничего». Процессы в системе «закрываются» флагами в соответствии с PN₂, приведенной на рисунке.



Либо П₁ либо П₂ захватит все ресурсы. Программы П₁; П₂ могут работать только последовательно, но не параллельно. Проблема тупиков заключается в решении следующих задач: 1) распознавание тупиковых ситуаций и 2) введение защиты от тупиков. И распознавание и защита от тупиков (расстановка флаговых и пусковых функций) решаются эвристическими методами (набором правил, полученным от экспертов и имитационным моделированием).

2.3 Семафоры Дейкстры для синхронизации потоковых процессов

В системных программах очень часто встречаются ситуации, когда используются буферы (накопители) информации, при этом один процесс наполняет буфер данными, а другой процесс забирает данные из буфера. Очевидно, что такая логика взаимодействия может быть промоделирована PN с позицией типа cash. В этом случае принимается, что cash имеет неограниченный объем (может хранить бесконечно большое количество фишек). На самом деле в реальности объем cash всегда ограничен. Дейкстра предложил ввести в процессы, «наливающие» в cash данные, и «выкачивающие» данные из cash, специальные контролирующие процедуры (семафоры). Далее на рисунке показана модель такого «cаsh» и приведены программы и процедуры, которые носят название «семафоров Дейкстры».

Семафоры и семафорные функции Дейкстры.



Входной кран K₁ закрывается,

когда S_св = 0;

выходной кран K₂ закрывается,

когда S_n = 0.


Процедура для процесса Процедура для процесса

«наливающего» cash «выкачивающего» cash

begin begin

while S_св > 0 DO while S_п > 0 DO

begin begin

P: S_св: = S_св – 1 P: S_n: = S_n – 1

V: S_n: = S_n+ 1 V: S_св: = S_св + 1

end end

end end

Закрой кран K₁ Закрой кран K₂

Переменные S_св, S_n – называются семафорами, а P, V – семафорными функциями Дейкстры.

Пример 10. Монитор Хоара для почтового ящика сообщений между двумя процессами.

1. Содержательная задача.
   

Два процесса: А – готовит и посылает сообщения в почтовый ящик (ПЯ), В – вынимает сообщения из ПЯ и их обрабатывает. Общий ресурс – ПЯ, доступ к которому имеют либо А либо В, но не оба вместе. «А» складывает сообщения в ПЯ, пока он не переполнится. «В» выбирает сообщения, пока ПЯ не будет пустым.

2. Математическая модель.
   

Сеть Петри, совмещенная с семафорами Дейкстры.

Семафоры

S_св – число свободных ячеек ПЯ

S_n – число ячеек ПЯ, занятых

сообщениями

S_ПЯ – ёмкость ПЯ, (число ячеек

ПЯ)

S_св = S_ПЯ – S_n

Процессы События

• а₁ – подготовка сообщений  3А – запрос на засылку
  
• а₂ – запись сообщений в ПЯ сообщений в ПЯ
  
• b₁ – считывание сообщений  ЕА₂ – разрешение на
  

из ПЯ сообщение

• b₂ – обработка сообщений  ЕА₁ – сообщения
  

подготовлены

 ПЯ – ПЯ свободен (занят)

 ЗВ – запрос на прием

сообщений

 ЕВ₂ – разрешение на

прием сообщений

 ЕВ₁ – сообщения считаны

из ПЯ

Семафорные процедуры

Procedure посылка Procedure выемка

begin begin

while S_св >0 do while S_n >0 do

begin begin

процесс а₂; процесс b₁;

P: S_cв: = S_св – 1; P: S_n: = S_n – 1;

V: S_n = S_n + 1; V: S_св = S_св+ 1;`

end end

end end

3. Асинхронный протокол монитора Хоара.
   

Флаговые функции: (3А, ЕА₂, ПЯ, 3В, ЕВ₂, ЕВ₁) = 1 (флаг поднят, если произошло событие ), иначе = 0 (флаг опущен).

Пусковые функции: а₁  а₁; а₂  procedure посылка; b₁ – procedure выемка; b₂  b₂.

Правила протокола:

1. (а_{1 =} _3АЕА₂ЕА₁) а₁; 3А: = 0; ЕА₂: = 0; ЕА₂: = 1.
   
2. (а_{2 =} ЕА₁ЕА₂)  procedure посылка; ЕА₁:=0; ЕА₂:=1; ПЯ:=1.
   
3. (b₁ = 3BEB₂ПЯEB₁)  procedure выемка; 3В: = 0; ЕВ₂: = 0; ЕВ₁: = 1.
   
4. (b₂ = ЕB₁ЕВ₂)  b₂; ЕВ₁: = 0; ЕВ₂: = 1.