Моделирование на GPSS

БОЛЬШАЯ ЛЕНИНГРАДСКАЯ БИБЛИОТЕКА - РЕФЕРАТЫ - Моделирование на GPSS

Моделирование на GPSS

ОСНОВЫ МОДЕЛИРОВАНИЯ НА GPSS/PC

ОГЛАВЛЕНИЕ

ВВЕДЕНИЕ .................................................... 1

1. ОБЩИЕ СВЕДЕНИЯ О GPSS/PC ................................. 2

2. ОСНОВНЫЕ БЛОКИ GPSS/PC И СВЯЗАННЫЕ С НИМИ ОБЪЕКТЫ ........ 6

2.1. Блоки, связанные с транзактами .................... 6

2.2. Блоки, связанные с аппаратными объектами .......... 13

2.3. Блоки для сбора статистических данных ............. 15

2.4. Блоки, изменяющие маршруты транзактов ............. 18

2.5. Блоки, работающие с памятью ....................... 21

2.6. Блоки для работы со списками пользователя ......... 23

3. УПРАВЛЯЮШИЕ ОПЕРАТОРЫ GPSS/PC ............................ 25

4. НЕКОТОРЫЕ ПРИЕМЫ КОНСТРУИРОВАНИЯ GPSS-МОДЕЛЕЙ ............ 42

4.1. Косвенная адресация ............................... 42

4.2. Обработка одновременных событий ................... 44

5. КОМАНДЫ GPSS/PC И ТЕХНОЛОГИЯ РАБОТЫ С ПАКЕТОМ ............ 47

5.1. Загрузка интегрированной среды .................... 47

5.2. Ввод новой модели ................................. 47

5.3. Редактирование текста модели ...................... 48

5.4. Запись и считывание модели с диска ................ 49

5.5. Прогон модели и наблюдение за моделированием ...... 49

5.6. Получение и интерпретация стандартного отчета ..... 53

СПИСОК ЛИТЕРАТУРЫ ........................................... 58

ВВЕДЕНИЕ

Процессы функционирования различных систем и сетей связи могут

быть представлены той или иной совокупностью систем массового

обслуживания (СМО) - стохастических, динамических, дискретно-непре-

рывных математических моделей. Исследование характеристик таких мо-

делей может проводиться либо аналитическими методами, либо путем

имитационного моделирования [1-6].

Имитационная модель отображает стохастический процесс смены

дискретных состояний СМО в непрерывном времени в форме моделирующе-

го алгоритма. При его реализации на ЭВМ производится накопление

статистических данных по тем атрибутам модели, характеристики кото-

рых являются предметом исследований. По окончании моделирования на-

копленная статистика обрабатывается, и результаты моделирования по-

лучаются в виде выборочных распределений исследуемых величин или их

выборочных моментов. Таким образом, при имитационном моделировании

систем массового обслуживания речь всегда идет о статистическом

имитационном моделировании [5;6].

Сложные функции моделирующего алгоритма могут быть реализованы

средствами универсальных языков программирования (Паскаль, Си), что

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

использовании модели. Однако подобная гибкость приобретается ценой

больших усилий, затрачиваемых на разработку и программирование

весьма сложных моделирующих алгоритмов, оперирующих со списковыми

структурами данных. Альтернативой этому является использование спе-

циализированных языков имитационного моделирования [5-7].

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

процесса функционирования моделируемой системы, что значительно об-

легчает и упрощает программирование имитационных моделей, поскольку

основные функциии моделирующего алгоритма при этом реализуются ав-

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

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

естественном языке, что позволяет конструировать сложные имитацион-

ные модели пользователям, не являющимся профессиональными програм-

мистами.

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

лирования сложных дискретных систем является в настоящее время язык

GPSS [1;4;7]. Он может быть с наибольшим успехом использован для

моделирования систем, формализуемых в виде систем массового обслу-

живания. В качестве объектов языка используются аналоги таких стан-

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

и т.п. Достаточный набор подобных компонентов позволяет конструиро-

вать сложные имитационные модели, сохраняя привычную терминологию

СМО.

На персональных компьютерах (ПК) типа IBM/PC язык GPSS реали-

зован в рамках пакета прикладных программ GPSS/PC [8]. Основной мо-

дуль пакета представляет собой интегрированную среду, включающую

помимо транслятора со входного языка средства ввода и редактирова-

ния текста модели, ее отладки и наблюдения за процессом моделирова-

ния, графические средства отображения атрибутов модели, а также

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

статистической обработки. Кроме основного модуля в состав пакета

входит модуль создания стандартного отчета GPSS/PC, а также ряд до-

полнительных модулей и файлов.

В данном издании, состоящем из двух частей, излагаются основы

моделирования систем и сетей связи с использованием пакета GPSS/PC.

В первой части рассматриваются основные понятия и средства GPSS/PC,

приемы конструирования GPSS-моделей и технология работы с пакетом.

Изложение материала сопровождается небольшими учебными примерами.

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

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

Во второй части рассматриваются примеры GPSS-моделей различных

систем и сетей массового обслуживания, используемых для формализа-

ции процессов функционирования систем и сетей связи. Приводится

также ряд примеров моделирования систем и сетей связи с использова-

нием GPSS/PC. Подробно комментируются тексты GPSS-моделей и резуль-

таты моделирования.

1. ОБЩИЕ СВЕДЕНИЯ О GPSS/PC

Исходная программа на языке GPSS/PC, как и программа на любом

языке программирования, представляет собой последовательность опе-

раторов. Операторы GPSS/PC записываются и вводятся в ПК в следующем

формате:

номер _строки имя операция операнды ; комментарии

Все операторы исходной программы должны начинаться с номе-

ра 0_строки - целого положительного числа от 1 до 9999999. Пос-

ле ввода операторов они располагаются в исходной программе в соот-

ветствии с нумерацией строк. Обычно нумерация производится с неко-

торым шагом, отличным от 1, чтобы иметь возможность добавления опе-

раторов в нужное место исходной программы.Некоторые операторы удо-

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

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

В настоящем издании при описании формата операторов и в примерах

моделей номера строк будут опускаться для лучшей читаемости текста.

Отдельные операторы могут иметь имя для ссылки на эти операторы

в других операторах. Если такие ссылки отсутствуют, то этот элемент

оператора не является обязательным.

В поле операции записывается ключевое слово (название операто-

ра), указывающее конкретную функцию, выполняемую данным оператором.

Это поле оператора является обязательным. У некоторых операторов

поле операции включает в себя также вспомогательный операнд.

В полях операндов записывается информация, уточняющая и конк-

ретизирующая выполнение функции, определенной в поле операции. Эти

поля в зависимости от типа операции содержат до семи операндов,

расположенных в определенной последовательности и обозначаемых

обычно первыми буквами латинского алфавита от A до G. Некоторые

операторы вообще не имеют операндов, а в некоторых операнды могут

быть опущены, при этом устанавливаются их стандартные значения (по

умолчанию). При записи операндов используется позиционный принцип:

пропуск операнда отмечается запятой.

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

поля операндов точкой с запятой. Комментарии не могут содержать

букв русского алфавита.

Операторы GPSS/PC записываются, начиная с первой позиции, в

свободном формате, т.е. отдельные поля разделяются произвольным ко-

личеством пробелов. При вводе исходной программы в интегрированной

среде GPSS/PC размещение отдельных полей операторов с определенным

количеством интервалов между ними производится автоматически.

Каждый оператор GPSS/PC относится к одному из четырех типов:

операторы-блоки, операторы определения объектов, управляющие опера-

торы и операторы-команды.

Операторы-блоки формируют логику модели. В GPSS/PC имеется

около 50 различных видов блоков, каждый из которых выполняет свою

конкретную функцию. За каждым из таких блоков стоит соответствующая

подпрограмма транслятора, а операнды каждого блока служат парамет-

рами этой подпрограммы.

Операторы определения объектов служат для описания пара-

метров некоторых объектов GPSS/PC (о самих объектах речь пойдет

дальше).

Примерами параметров объектов могут быть количество каналов в мно-

гоканальной системе массового обслуживания, количество строк и

столбцов матрицы и т.п.

Управляющие операторы служат для управления процессом модели-

рования (прогоном модели). Операторы-команды позволяют управлять

работой интегрированной среды GPSS/PC. Управляющие операторы и

операторы-команды обычно не включаются в исходную программу, а

вводятся непосредственно с клавиатуры ПК в процессе интерактив-

ного взаимодействия с интегрированной средой.

После трансляции исходной программы в памяти ПК создается так

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

объектов, каждый из которых представляет собой некоторый набор

чисел в памяти ПК, описывающих свойства и текущее состояние объекта.

Объекты GPSS/PC можно разделить на семь классов:

динамические, операционные, аппаратные, статистические, вычислитель-

ные, запоминающие и группирующие.

Динамические объекты, соответствующие заявкам в системах

массового обслуживания, называются в GPSS/PC транзактами. Они

"создаются" и "уничтожаются" так, как это необходимо по логике моде-

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

произвольное число параметров, несущих в себе необходимую информа-

цию об этом транзакте. Кроме того, транзакты могут иметь различные

приоритеты.

Операционные объекты GPSS/PC, называемые блоками, соответствуют

операторам-блокам исходной программы. Они, как уже говорилось,

формируют логику модели, давая транзактам указания: куда идти и что

делать дальше. Модель системы на GPSS/PC можно представить совокуп-

ностью блоков, объединенных в соответствии с логикой работы реаль-

ной системы в так называемую блок-схему. Блок-схема модели

может быть изображена графически, наглядно показывая взаимодействие

блоков в процессе моделирования.

Аппаратные объекты GPSS/PC - это абстрактные элементы, на ко-

торые может быть расчленено (декомпозировано) оборудование реальной

системы. К ним относятся одноканальные и многоканальные устрой-

ства и логические переключатели. Многоканальное устройство иногда

называют памятью.

Одноканальные и многоканальные устройства соответствуют обслу-

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

краткости далее будем называть просто устройством, может обслужи-

вать одновременно только один транзакт. Многоканальное устройство

(МКУ) может обслуживать одновременно несколько транзактов. Логи-

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

состояний логического или физического характера. ЛП может нахо-

диться в двух состояниях: включено и выключено. Его состояние может

изменяться в процессе моделирования, а также опрашиваться для при-

нятия определенных решений.

Статистические объекты GPSS/PC служат для сбора и обработки

статистических данных о функционировании модели. К ним относятся

очереди и таблицы .

Каждая очередь обеспечивает сбор и обработку данных о транзак-

тах, задержанных в какой-либо точке модели, например перед однока-

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

распределений некоторых случайных величин, например времени пребы-

вания транзакта в модели.

К вычислительным объектам GPSS/PC относятся переменные (ариф-

метические и булевские) и функции. Они используются для вычис-

ления некоторых величин, заданных арифметическими или логическими

выражениями либо табличными зависимостями.

Запоминающие объекты GPSS/PC обеспечивают хранение в памяти ПК

отдельных величин, используемых в модели, а также массивов таких

величин. К ним относятся так называемые сохраняемые величины и

матрицы сохраняемых величин.

К объектам группирующего класса относятся списки пользователя

и группы. Списки пользователя используются для организации очере-

дей с дисциплинами, отличными от дисциплины "раньше пришел – раньше

обслужен". Группы в данном издании рассматриваться не будут.

Каждому объекту того или иного класса соответствуют числовые

атрибуты, описывающие его состояние в данный момент модельного вре-

мени. Кроме того, имеется ряд так называемых системных атрибутов,

относящихся не к отдельным объектам, а к модели в целом.

Значения атрибутов всех объектов модели по окончании моделирования

Выводятся в стандартный отчет GPSS/PC. Большая часть атрибутов дос-

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

вые атрибуты (СЧА), 0которые могут использоваться в качестве опе-

рандов операторов исходной программы. Все СЧА в GPSS/PC являются це-

лыми числами.

Каждый объект GPSS/PC имеет имя и номер. Имена объектам

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

им номера транслятор присваивает автоматически. Имя объекта предста-

вляет собой начинающуюся с буквы последовательность букв латинского

алфавита, цифр и символа "подчеркивание". При необходимости имени

любого объекта, кроме имени блока, можно поставить в соответствие

любой номер с помощью оператора описания EQU, имеющего следующий

формат:

имя EQU номер

Блокам присваиваются их порядковые номера в исходной программе

(непутать с номерами строк!).

Для ссылки 0на какой-либо стандартный числовой атрибут некото-

рого объекта соответствующий операнд оператора исходной программы

записывается одним из следующих способов:

СЧА $имя ;

СЧА j ,

где СЧА - системное обозначение (название) конкретного стандар-

тного числового атрибута данного объекта; имя - имя объекта;

j - номер объекта; $ - символ-разделитель.

Прогон текущей модели, т.е. собственно моделирование, выполня-

ется с помощью специальной управляющей программы, которую называют

симулятором (от английского SIMULATE - моделировать, имитировать).

Работа GPSS-модели под управлением симулятора заключается в переме-

щении транзактов от одних блоков к другим, аналогично тому, как в

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

В начальный момент времени в GPSS-модели нет ни одного тран-

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

определенные моменты времени в соответствии с теми логическими пот-

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

образом транзакты покидают модель в определенные моменты времени в

зависимости от специфики моделируемой системы. В общем случае в мо-

дели одновременно существует большое число транзактов, однако в

каждый момент времени симулятор осуществляет продвижение только ка-

кого-либо одного транзакта.

Если транзакт начал свое движение, он перемещается от блока к

блоку по пути, предписанному блок-схемой. В тот момент, когда тран-

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

симулятора, соответствующая типу этого блока, а после ее выполне-

ния, при котором реализуется функция данного блока, транзакт "пыта-

ется" войти в следующий блок. Такое продвижение транзакта продолжа-

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

бытий:

1) транзакт входит в блок, функцией которого является удаление

транзакта из модели;

2) транзакт входит в блок, функцией которого является задержка

транзакта на некоторое определенное в модели время;

3) транзакт "пытается" войти в следующий блок, однако блок

"отказывается" принять его. В этом случае транзакт остается в том

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

в следующий блок. Когда условия в модели изменятся, такая попытка

может оказаться успешной, и транзакт сможет продолжить свое переме-

щение по блок-схеме.

Если возникло одно из описанных выше условий, обработка данного

транзакта прекращается, и начинается перемещение другого транзакта.

Таким образом, выполнение моделирования симулятором продолжается

постоянно.

Проходя через блоки модели, каждый транзакт вносит вклад в со-

держимое счетчиков блоков. Значения этих счетчиков доступны

программисту через СЧА блоков: W - текущее содержимое блока и N –

общее количество входов в блок.

Каждое продвижение транзакта в модели является событием, кото-

рое должно произойти в определенный момент модельного времени. Для

того, чтобы поддерживать правильную временную последовательность

событий, симулятор имеет таймер модельного времени, который ав-

томатически корректируется в соответствии с логикой, предписанной

моделью.

Таймер GPSS/PC имеет следующие особенности:

1) регистрируются только целые значения (все временные интер-

валы в модели изображаются целыми числами);

2) единица модельного времени определяется разработчиком моде-

ли, который задает все временные интервалы в одних и тех

же, выбранных им единицах;

3) симулятор не анализирует состояние модели в каждый следую-

щий момент модельного времени (отстоящий от текущего на

единицу модельного времени), а продвигает таймер к моме-

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

Значения таймера доступны программисту через системные СЧА C1

(относительное время) и AC1 (абсолютное время).

Центральной задачей, выполняемой симулятором, является опреде-

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

модели, когда его предшественник прекратил свое продвижение. С этой

целью симулятор рассматривает каждый транзакт как элемент некоторо-

го списка. В относительно простых моделях используются лишь два

основных списка: список текущих событий и список будущих событий.

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

время продвижения которых равно или меньше текущего модельного

времени (к последним относятся транзакты, движение которых было

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

тов транзактов, а в пределах каждого уровня приоритета - в порядке

поступления транзактов.

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

время продвижения которых больше текущего времени, т.е. события,

связанные с продвижением этих транзактов, должны произойти в буду-

щем. Этот список организуется в порядке возрастания планируемого

времени продвижения транзактов.

Симулятор GPSS/PC помещает транзакты в зависимости от условий

в модели в тот или иной список и переносит транзакты из списка в

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

ботки, корректирует таймер модельного времени после обработки всех

транзактов в списке текущих событий.

2. ОСНОВНЫЕ БЛОКИ GPSS/PC И СВЯЗАННЫЕ С НИМИ ОБЪЕКТЫ

2.1. Блоки, связанные с транзактами

С транзактами связаны блоки создания, уничтожения, задержки

транзактов, изменения их атрибутов и создания копий транзактов.

Для создания транзактов, входящих в модель, служит блок

GENERATE (генерировать), имеющий следующий формат:

имя GENERATE A,B,C,D,E

В поле A задается среднее значение интервала времени между мо-

ментами поступления в модель двух последовательных транзактов. Если

этот интервал постоянен, то поле B не используется. Если же интер-

вал поступления является случайной величиной, то в поле B указыва-

ется модификатор среднего значения, который может быть задан в виде

модификатора-интервала или модификатора-функции.

Модификатор-интервал используется, когда интервал поступления

транзактов является случайной величиной с равномерным законом расп-

ределения вероятностей. В этом случае в поле B может быть задан лю-

бой СЧА, кроме ссылки на функцию, а диапазон изменения интервала

поступления имеет границы A-B, A+B.

Например, блок

GENERATE 100,40

создает транзакты через случайные интервалы времени, равномерно

распределенные на отрезке [60;140].

Модификатор-функция используется, если закон распределения ин-

тервала поступления отличен от равномерного. В этом случае в поле B

должна быть записана ссылка на функцию (ее СЧА), описывающую этот

закон, и случайный интервал поступления определяется, как целая

часть произведения поля A (среднего значения) на вычисленное значе-

ние функции.

В поле C задается момент поступления в модель первого транзак-

та. Если это поле пусто или равно 0, то момент появления первого

транзакта определяется операндами A и B.

Поле D задает общее число транзактов, которое должно быть соз-

дано блоком GENERATE. Если это поле пусто, то блок генерирует неог-

раниченное число транзактов до завершения моделирования.

В поле E задается приоритет, присваиваемый генерируемым транзак-

там. Число уровней приоритетов неограничено, причем самый низкий

приоритет - нулевой. Если поле E пусто, то генерируемые транзакты

имеют нулевой приоритет.

Транзакты имеют ряд стандартных числовых атрибутов. Например,

СЧА с названием PR позволяет ссылаться на приоритет транзакта. СЧА

с названием M1 содержит так называемое резидентное время транзакта,

т.е. время, прошедшее с момента входа транзакта в модель через блок

GENERATE. СЧА с названием XN1 содержит внутренний номер транзакта,

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

один транзакт от другого. В отличие от СЧА других объектов, СЧА

транзактов не содержат ссылки на имя или номер транзакта. Ссылка

на СЧА транзакта всегда относится к активному транзакту, т.е. тра-

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

Важными стандартными числовыми атрибутами транзактов являются

значения их параметров. Любой транзакт может иметь неограниченное

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

на этот СЧА транзактов всегда относится к активному транзакту и

имеет вид Pj или Р$ имя, где j и имя - номер и имя параметра

соответственно. Такая ссылка возможна только в том случае,

если параметр с указанным номером или именем существует, т.е. в него

занесено какое-либо значение.

Для присваивания параметрам начальных значений или изменения

этих значений служит блок ASSIGN (присваивать), имеющий следущий

формат:

имя ASSIGN A,B,C

В поле A указывается номер или имя параметра, в который за-

носится значение операнда B. Если в поле A после имени (номера) па-

раметра стоит знак + или -, то значение операнда B добавляется или

вычитается из текущего содержимого параметра. В поле С может быть

указано имя или номер функции-модификатора, действующей аналогично

функции-модификатору в поле B блока GENERATE.

Например, блок

ASSIGN 5,0

записывает в параметр с номером 5 значение 0, а блок

ASSIGN COUNT+,1

добавляет 1 к текущему значению параметра с именем COUNT.

Для записи текущего модельного времени в заданный параметр

транзакта служит блок MARK (отметить), имеющий следующий формат:

имя MARK A

В поле A указывается номер или имя параметра транзакта, в ко-

торый заносится текущее модельное время при входе этого транзакта в

блок MARK. Содержимое этого параметра может быть позднее использо-

вано для определения транзитного времени 0пребывания транзакта в

какой-то части модели с помощью СЧА с названием MP.

Например, если на входе участка модели поместить блок

MARK MARKER ,

то на выходе этого участка СЧА MP$MARKER будет содержать разность

между текущим модельным временем и временем, занесенным в параметр

MARKER блоком MARK.

Если поле A блока MARK пусто, то текущее время заносится на

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

определении резидентного времени транзакта с помощью СЧА M1.

Для изменения приоритета транзакта служит блок PRIORITY (прио-

ритет), имеющий следующий формат:

имя PRIORITY A,B

В поле A записывается новый приоритет транзакта. В поле B мо-

жет содержаться ключевое слово BU, при наличии которого транзакт,

вошедший в блок, помещается в списке текущих событий после всех

остальных транзактов новой приоритетной группы, и список текущих

событий просматривается с начала. Использование такой возможности

будет рассмотрено ниже.

Для удаления транзактов из модели служит блок TERMINATE (за-

вершить), имеющий следующий формат:

имя TERMINATE A

Значение поля A указывает, на сколько единиц уменьшается со-

держимое так называемого счетчика завершений при входе транзакта в

данный блок TERMINATE. Если поле A не определено, то оно считается

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

содержимого счетчика завершений.

Начальное значение счетчика завершений устанавливается управ-

ляющим оператором START (начать), предназначенным для запуска про-