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

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

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

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

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

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

122

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

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

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

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

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

В пакете Matlab имеется собственный язык моделирования, позволяющий моделировать параллельные процессы.

Рассмотрим механизм реализации ПП на основе тран-зактов.

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

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

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

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

123

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

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

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

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

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

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

124

На рисунке события, относящиеся к процессу Р1, обозначены как C1i; относящиеся к Р2 и к Р3 соответственно как С2і и С3і.

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

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

C11

C1 2 „

C13

t1

C21

C22

C23

*t2

C31

C32

C33

't3

t11 t21 t31

t22 t32

t33

tm

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

125

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

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

Одним из наиболее элегантных и весьма распространенных средств описания параллельных процессов являются так называемые сети Петри.

127