Принципы организации системы GPSS

Классификация языков имитационного моделирования

Классификация и краткая характеристика языков имитационного моделирования. Среда и функциональная структура языка моделирования GPSS

Специализированные языки имитационного моделирования делятся на языки схемных символов и операторные языки. Соответственно двум видам имитации они также классифицируются на:

· языки моделирования непрерывных процессов;

· языки моделирования дискретных процессов.

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

Языки моделирования дискретных процессов делятся на 4 категории:

- языки, ориентированные на события,

- языки, ориентированные на действия,

- языки, ориентированные на процессы,

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

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

В языках, ориентированных на зависящие от времени действия, эти действия представляются в модельном времени как мгновенные. Программируя на этих языках, пользователь не регламентирует действия программы, а лишь указывает на условия, при которых они могут произойти. В подобных языках программа составляется из двух частей: обеспечивающей проверку и обеспечивающей действие. Исполнительные программы, просматривают набор всех условий перед сдвигом времени на очередной интервал, что позволяет определить, могут ли произойти какие-либо события. Перед очередным сдвигом модельного времени происходит сканирование всех программ по действиям для определения, какая из них включена в работу. Исполнение команд изменения состояния и сдвига времени в той части программы, которая обеспечивает действие, разрешается тогда, когда выполняются все контролируемые условия. Если хоть одно из них осталось невыполненным, команды действия пропускаются. Циклическое сканирование всех программ имитации действий дает возможность учитывать вероятности включения каждой из них и все возможные взаимодействия. Языки, ориентированные на действия: CSL, ESP, Форсим IV, GSP и Милитран.

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

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

К языкам этой категории принадлежат GPSS и BOSS. Язык моделирования дискретных систем GPSS (General Purpose System Simulator) является одним из самых распространенных в мире языков имитационного моделирования. Данный язык был разработан фирмой IBM в начале 70-х годов XX в., а в настоящее время система моделирования GPSS/PC (различных версий) является торговой маркой фирмы MINUTEMAN Software.

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

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

Блоки. Для задания объектов моделируемой системы и операций над ними в моделирующей системе GPSSиспользуется совокупность блоков, имеющих специальное обозначение и формат описания (записи). Каждому блоку соответствует графическое изображение на блок-схеме, а чтобы применить язык моделирования GPSS, блоки блок-схемы заменяются соответствующими операторами GPSS. Каждый блок системы имеет входы и выходы, с помощью которых осуществляется их связь в модели. Блок является обязательным элементом любой модели на GPSS. В системе GPSS/PCверсии 2.0 всего имеется 46 блоков.

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

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

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

3. Задержка сообщения на определенный период времени;

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

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

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

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

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

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

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

Список прерываний содержит транзакты, обслуживание которых (дальнейшее продвижение по модели) прервано на одном или более устройствах. В списке прерываний транзакты расположены в порядке поступления. Транзакты находятся в списке прерываний до тех пор, пока не будут сняты все условия прерываний.

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

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

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

Оборудование. Для того, чтобы моделировать обслуживающие приборы реальных систем,в GPSS используются объекты типа «оборудование». К объектам этого типа относятся:

· устройства,

· логические ключи.

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

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

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

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

Также к объектам GPSS относятся арифметические и булевские переменные, функции, ячейки сохраняемых величин и матрицы ячеек сохраняемых величин, а также очереди:

· арифметические переменныепозволяют вычислять арифметические выражения. В выражении переменной используют операторы, арифметические действия и вызовы библиотечных функций;

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

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

· ячейки сохраняемых величин и матрицы ячеек сохраняемых величин используются для хранения некоторой числовой информации. Например, значение, занесенное в ячейку, может представлять собой длину очереди в какой-то конкретной точке модели. Любое сообщение может произвести запись информации в эти объекты. Впоследствии записанную в эти объекты информацию может считывать любое сообщение. Например, в случае моделирования работы порта для построения зависимости ожидания судов в очереди определенной длины от времени достаточно через каждые Х единиц времени (Х задается пользователем) заносить значение длины очереди в ячейки (каждое значение в отдельную ячейку). В конце счета значения этих ячеек будут распечатаны, и по ним можно построить искомую зависимость;

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

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

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

Для того, чтобы обеспечить правильную временную последовательность событий в модели исследуемой системы, организованы часы, хранящие значения текущего момента в модели. В отличие от обычных часов, часы в GPSSменяют значение только для того, чтобы указать время наступления ближайшего события. Например, если текущее значение часов модели равно 2, а очередное событие должно наступить в момент времени 7, то значение часов увеличивается сразу на 5 единиц. Единицы времени в модели не обязательно должны быть конкретными единицами времени, такими, как секунда или час. Основной единицей времени в модели можно выбрать любую единицу, которая позволит получить необходимую точность моделирования.

Литература к главе 3: