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

 

Существуют следующие виды параллельных процессов.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

В качестве иллюстрации к изложенному рассмотрим небольшой пример.

Пусть в систему поступают транзакты трех типов, каждый из которых обслуживается отдельным устройством. Известны законы поступления транзактов всистему и длительность их обслуживания. Таким образом, в системе существуют три параллельных независимых процесса (P1, Р2, РЗ).

Временная диаграмма работы системы при обслуживании одного транзакта каждого типа показана на рисунке 13.1.

На рисунке события, относящиеся к процессу Р1, обозначены как С1, относящиеся к Р2 и к РЗ — соответственно как С2 и СЗ. Моменты времени t_вх и t_вых соответствуют началу и окончанию обслуживания транзакта [10].

 

Рис. 13.1. Временная диаграмма параллельных процессов

Для каждого процесса строится своя цепь событий, однако списки событий являются общими для всей модели. Формирование списков начинается с заполнения списка будущих событий. Как было отмечено выше, в этот список помещаются события, время наступления которых превышает текущее значение модельного времени. Очевидно, что на момент заполнения списка время наступления прогнозируемых событий должно быть известно. На первом шаге tм=0, и в список будущих событий заносятся события С11, С21, С31. Затем событие с наименьшим временем наступления С11 переносится в список текущих событий; если одновременных с ним событий нет, то оно обрабатывается и исключается из списка текущих событий. После этого вновь корректируется список будущих событий и т.д., пока не истечет заданный интервал моделирования.

Динамика изменения списков текущих и будущих событий для рассмотренного примера отражена в приведенной ниже таблице:

Та6лица 13.1. Изменение списков событий

T	Список текущих событий	Список будущих событий
		С11
0	0	С21
		С31
		С21
t11	С11	С31
		С12
		С31
t21	С21	С12
		C32
		С12
t31	С31	С22
		С32
		С22
t12	С12	С32
		С13
		С32
t22	С22	С13
		С23
		С13
t32	С32	С23
		СЗЗ
t13	С13	С23 СЗЗ
t2З	С23 СЗЗ

 

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

1. Где на практике встречаются параллельные процессы?

2. Чем отличается синхронный процесс от асинхронного?

3. Что такое список будущих событий?

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

5. В чем недостатки моделирования через список будущих событий?

 

Сети Петри

 

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

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

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

 

 

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

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

P=(B,D,I,0,M),

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

D = {d_i } — конечное непустое множество переходов;

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

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

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

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

М'(В) = М(В) – I(d_j) + O(d_j),

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

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

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

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

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

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

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

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

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

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

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

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

 

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

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

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

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

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

5. Где можно применять сети Петри?