Программная реализация алгоритмов

· 8. Программная реализация алгоритмов
имитационного моделирования систем

· 8.1. Формирование и обработка наборов данных имитационного моделирования

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

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

Алгоритмы формирования наборов данных и обработки данных могут быть реализованы на языках программирования общего назначения (Си, Паскаль, Фортран и др.) или на специализированных языках имитационного моделирования систем (Модула, GPSS и др.).

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

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

Остановимся более подробно на транзактно-ориентированном языке GPSS.

· 8.2. Общая характеристика языка GPSS

Рекомендуемые материалы

Основой GPSS являются программы, описывающие функционирование выделенного конечного набора объектов и специальная диспетчирующая программа- симулятор, имеющая следующие основные функции.

1. Обеспечение заданных программистом маршрутов продвижения транзактов (сообщения, заявки).

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

3. Регистрация статистической информации о функционировании модели.

4. Продвижение модельного времени в процессе моделирования сис­темы.

Формальными основными моделями, для имитации которых используется GPSS, являются системы массового обслуживания (Q-схемы), конечные и вероятностные автоматы (F- и P-схемы), сети Петри (N-схемы), агрегаты (A-схемы).

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

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

5. Создание или уничтожение транзактов.

6. Изменение числового атрибута объекта.

7. Задержка транзакта на  определенный период времени.

8. Изменение маршрута  транзакта.

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

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

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

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

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

MARK TIME - значение модельного времени, когда транзакт впервые появился в системе.

ASSEBMLY SET – совокупность объединенных в группу тразактов.

DELAY INDIKATOR – номер блока, перед которым находится транзакт, не имея возможности войти в него.

TRACE  INDIKATOR – указывает номера блоков, которые проходятся активным транзактом.

CURRENT BLOCK – номер блока, в котором находится активный транзакт.

NEXT BLOCK – следующий блок, номер блока, следующего за текущим блоком на пути движения активного транзакта.

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

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

ACTIVE – активное, в котором  транзакт имеет наивысший приоритет в списке текущих событий.

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

PASSIVE – транзакт временно пнрнводится в список пользователя, список задержки или список ожидания.

TERMINATE – транзакт уничтожен и больше не выполняется в текущей модели.

PREEMTED – обработка транзакта некоторым устройством прерывания и его перевод в один или более списков прерывания.

Аналогами обслуживающих приборов в реальных системах в GPSS являются объекты типа «оборудование» - одноканальные устройства, многоканальные устройства и логические ключи.

Одноканальное устройство – оборудование, которое в любой момент времени может быть занято только одним транзактом.

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

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

Транзакт может устанавливать логические ключи в состояние «включено» или «выключено».

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

Реальной системе сопоставляется GPSS-модель. Структура GPSS-модели имеет вид следующей блок-диаграммы

Блок GENERATE генерирует и продвигает транзакты, он имеет только выход. Блок TERMINATE выводит транзакты из модели, он имеет только вход.

· 8.3. Описание и применение языка GPSS

Пример 1. Заявки поступают в систему массового обслуживания через фиксированное время (7 единиц времени). Обслуживание заявки занимает фиксированное время (5 единиц времени). После обслуживания заявки покидают систему. Провести обработку 100 заявок.

Программа для примера 1 имеет следующий вид.

SIMULATE

10  GENERATE 7; Генерация транзактов каждые 7 минут.

20  SEIZE 1

30  ADVANCE 5

40  RELEASE 1

50  TERMINATE 1; Уничтожение транзактов.

START 100

END

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

SIMULATE – вызов интерпретатора (симулятора).

Заявки (транзакты) генерируются блоком  GENERATE 7 каждые 7 минут, захватываются на обслуживание устройством 1 (блок SEIZE 1), удерживаются на обслуживании в течении 5 мин. (блок ADVANCE 5) и освобождают устройство 1 (блок RELEASE 1). Вывод транзактов осуществляет блок TERMINATE 1. Оператор START 100 повторяет процесс моделирования 100 раз. Оператор END осуществляет задание прогона модели и завершает работу программы.

Стандартный отчет программы GPSS. Результаты моделирования представлены в следующем файле стандартного отчета, который автоматически формируется программой GPSS

Комментарий стандартному отчету.

start time – начало моделирования.

end time – окончание моделирования.

blocks – количество используемых в программе блоков.

facilities – количество установленных устройств.

storages – количество многоканальных устройств, для которых определяется заданная емкость накопителя.

free memory – емкость оперативной памяти, которая доступна для дальнейшего использования.

line – номера блоков в порядке возрастания.

loc – номера блоков, которые определяются системой.

block type – названия блоков.

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

current count – текущее количество транзактов, задержанных в блоке на момент окончания моделирования.

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

facility – номер устройства.

entries – количество транзактов, прошедших через устройство с данным номером.

util – коэффициент использования устройства с данным номером.

ave. time – среднее время обработки или задержки транзакта в устройстве с данным номером.

available – состояние готовности устройства в конце моделирования (1- готово к работе).

owner – номер последнего транзакта, занимавшего устройство (0 – устройство не занималось).

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

inter – количество транзактов, прерывающих устройство в данный момент.

Информация в лекции "7 Алгоритмы параллельной обработки" поможет Вам.

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

delay - количество транзактов, ожидающих занятия или освобождения устройства.

В системе GPSS могут быть объекты типа «группа сообщений». Статистика по таким объектам отражается в следующих полях.

xact group – имя или номер группы сообщений.

group size - количество транзактов в группе в конце моделирования.

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