4     28. Графический способ описания  ПП (сети Петри)

      5     29. Основные направления анализа  сети Петри.

Моделирование параллельных процессов.

25. Виды параллельных процессов в сложных системах

 

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

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

      Асинхронный параллельный процесс — такой процесс, состояние которого не зависит от состояния другого параллельного процесса (ПП).

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

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

      Пример  синхронного ПП: работа торговой организации  и доставка товара со склада (нет  товара — нет торговли).

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

      Подчиненный ПП — создается и управляется другим процессом (более высокого уровня).

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

      Независимый ПП — не является подчиненным ни для одного из процессов.

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

      Способ  организации параллельных процессов  в системе зависит от физической сущности этой системы.

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

      Для организации взаимодействия параллельных процессов в ВС используются три основных подхода:

      • на основе «взаимного исключения»;

      • на основе синхронизации  посредством сигналов;

      • на основе обмена информацией (сообщениями).

      •«Взаимное исключением предполагает запрет доступа к общим ресурсам (общим данным) для всех ПП, кроме одного, на время его работы с этими ресурсами (данными).

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

      Перечисленные механизмы реализуются в ВС на двух уровнях — системном и прикладном.

      Механизм  взаимодействия между ПП на системном  уровне определяется еще на этапе разработки ВС и реализуется в основном средствами операционной системы (частично — с использованием аппаратных средств).

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

      Наибольшими возможностями в этом отношении  обладают так называемые языки реального времени (ЯРВ) и языки моделирования.

      Языки реального времени — это языки, предназначенные для создания программного обеспечения, работающего в реальном масштабе времени, например для разработки различных автоматизированных систем управления (предприятием, воздушным движением и т. д.). К ним, в частности, относятся: язык Ада, язык Модула и практически единственный отечественный язык реального времени — Эль-76 (использовавшийся в многопроцессорных вычислительных комплексах семейства «Эльбрус»).

26. Общие механизмы реализации параллельных процессов на основе транзактов

 

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

      Рассмотрим  его применительно к моделированию  на основе тракзактов.

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

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

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

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

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

      В списке текущих событий транзакты расположены в порядке убывания приоритета соответствующих событий; при равных приоритетах — в порядке поступления в список.

      Каждое  событие (транзакт) в  списке текущих событий  может находиться либо в активном состоянии, либо в состоянии задержки. Если событие активно, то соответствующий транзакт может быть продвинут по системе; если продвижение невозможно (например, из-за занятости устройства), то событие (и транзакт) переводится в состояние задержки.

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

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

27. Применение сетевых моделей для описания ПП 

      Этапу программной реализации модели должен предшествовать так называемый этап алгоритмизации. Работа ИМ должна быть описана  каким-либо менее  формальным и более  наглядным языком, т.е. д.б. описана логика работы модели.

      Для описания логики работы модели могут  быть использованы различные средства: либо русский язык (устный или письменный), либо традиционные схемы алгоритмов, либо какие-то другие «подручные» средства.

      Наиболее  приемлем для этих целей и весьма распространен метод описания параллельных процессов с помощью сетей Петри.

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

28. Графический способ описания ПП (сети Петри) 

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

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

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

      

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

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

                           
 
 

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

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

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

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

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

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

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

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

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

 

       План лекции №5

      1     30. Планирование модельных экспериментов

      2     31. Стратегическое планирование имитационного эксперимента

      3     32. Частичный факторный эксперимент  (ЧФЭ).

      4     33. Тактическое  планирование  экспериментов

      5    34. Методы понижения дисперсии 

30. Планирование модельных экспериментов 

      Исследователь должен помнить:

      Во-первых - какому классу относится моделируемая система (статическая или динамическая, детерминированная или стохастическая и т. д.).