МОДЕЛИРОВАНИЕ ПАРАЛЛЕЛЬНЫХ ПРОЦЕССОВ

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

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

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

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

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

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

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

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

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

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

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

Вместе с тем, реализация параллельных процессов в ВС имеет свои особенности;

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

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

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

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

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

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

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

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

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

Часто возникает необходимость передавать от одного ПП другому более подробную информацию, чем просто «сигнал-событие». В этом случае процессы согласуют свою работу на основе обмена сообщениями.

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

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

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

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

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

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

Языки моделирования по сравнению с языками реального времени требуют от разработчика значительно менее высокого уровня подготовки в области программирования, что обусловлено двумя обстоятельствами:

средства моделирования изначально ориентированы на квазипараллельную обработку параллельных процессов;

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

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

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

Моделирование на основе транзактов

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

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

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

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

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

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

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

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

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

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

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

 

 

1			"15	-гГ		»>
	С	21	to&wi с	( 22	с	tl 23
						1                  ^ ь
		С	31	С	»	Сзз
1 г 1						ъ

P              tn            tjl             tji             tjg         tJ2             t33.23      tfl,

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

Ha рисунке события, относящиеся к процессу Р1 обозначены как С1i, относящиеся к Р2 и к Р3 — соответственно как C2i и С3i. Время t:06спуж соответствует времени обслуживания транзакта.

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

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

 

Значения модельного времени	Список будущих событий	Список текущих событий
0	C11  C21  C31	0
T11	C21  С31  С12	C11
T21	C31  С12  С22	C21
Т31	C12  С22  С32	C31
T12	С22  С32  С13	C12
T22	С32 С13 С23	С22
T32	С13 С23 С33	С32
T13	С23 С33	С13
T23		С23 С33

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