GPSS (General Purpose Simulation System)

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 23:38, 8 июня 2016.
GPSS
Парадигма язык симуляции
Спроектировано Джеффри Гордон
Печать дисциплины

строгая,

статическая
OS UNIX, Linux, Windows, DOS и другие
Главная реализация

GPSS/H GPSS/PC,

GPSS/World
Диалект
HGPSS, aGPSS, JGPSS

GPSS (General Purpose Simulation System — система моделирования общего назначения) — язык моделирования, используемый для имитационного моделирования различных систем, в основном систем массового обслуживания.

История

Система GPSS была разработана сотрудником фирмы IBM Джефри Гордоном в 1961 году. Гордоном были созданы 5 первых версий языка: GPSS (1961), GPSS II (1963), GPSS III (1965), GPSS/360 (1967) и GPSS V (1971). Известный ранее только специалистам, в нашей стране этот программный пакет завоевал популярность после издания в СССР в 1980 году монографии Т Дж. Шрайбера. В ней была рассмотрена одна из ранних версий языка — GPSS/360, а также основные особенности более мощной версии — GPSS V, поддерживаемой компанией IBM, у нас она была более известна как пакет моделирования дискретных систем (ПМДС). Этот пакет работал в среде подсистемы диалоговой обработки системы виртуальных машин единой серии (ПДО СВМ ЕС) ЭВМ. После окончания поддержки GPSS V компанией IBM следующей версией стала система GPSS/H компании Wolverine Software разработанная в 1978 году под руководством Дж. Хенриксена. В 1984 году появилась первая версия GPSS для персональных компьютеров с операционной системой DOS — GPSS/PC. Она была разработана компанией Minuteman Software под руководством С. Кокса. Конец XX века ознаменовался разработкой компанией Minuteman Software программного продукта GPSS World, увидевшей свет в 1993 году. За сравнительно небольшой период времени было выпущено несколько его версий, причем в каждой последующей возможности системы моделирования наращивались. Помимо этих основных версий существует также Micro-GPSS, разработанная Ингольфом Сталлом в Швеции, — это упрощенная версия, предназначенная для изучения языка GPSS, и WebGPSS, также предназначенная для изучения работы системы и разработки простейших имитационных моделей в сети интернет.

Описание

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

Симуляция с помощью языка GPSS обеспечивает следующие действия:

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

Объекты

Объекты GPSS подразделяются на следующие подкатегории:

  1. Динамические объекты – транзакты (создаются, перемещаются по блокам, уничтожаются);
  2. Операционные блоки – задают логику функционирования модели системы и определяют пути следования транзактов. В блоках могут происходить события:
    • создание и уничтожение транзактов;
    • изменение числового атрибута объекта;
    • задержка транзакта на определенный период времени;
    • изменение маршрута движения транзакта.
  3. Объекты аппаратной категории;
  4. Объекты вычислительной категории;
  5. Запоминающие объекты;
  6. Группирующие объекты;
  7. Статистические объекты.

Блоки

Блок - базовый структурный элемент GPSS. Модель представляется неким набором блоков. К наиболее часто используемым блокам относятся:

  1. GENERATE
  2. TERMINATE
  3. ASSIGN
  4. SEIZE
  5. RELEASE
  6. QUEUE
  7. ADVANCE
  8. DEPART
  9. START
  10. END

Операторы (блоки) GPSS имеют следующий формат:

<метка> <имя_оператора> <поле_операндов> [<комментарий>]

Общая структура программы на GPSS имеет вид:

      SIMULATE
      описания, в том числе функций, накопителей, массивов и т.п.
      операторы, моделирующие движение транзактов
      START      A,B,C
      END.

Транзакты

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

Объекты аппаратной категории

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

  1. Одноканальные устройства (ОКУ) - оборудование, которое в любой момент времени может быть занято только одним транзактом. Например, один канал передачи данных, одноканальный ремонтный орган, один станок изготовления деталей, одно транспортное средство.
  2. Многоканальные устройства (МКУ) - имитируют оборудование, осуществляющее параллельную обработку. Они могут быть использованы одновременно несколькими транзактами. МКУ можно использовать в качестве аналога, например, многоканального ремонтного органа, нескольких каналов связи.
  3. Логические ключи - моделируют переключатели, имеющие только два состояния.

Вычислительные объекты

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

  1. Переменные представляют собой сложные выражения, которые включают константы, системные числовые атрибуты (СЧА), библиотечные арифметические функции, арифметические и логические операции. Выражения могут применяться в переменных и операторах GPSS. При применении в переменных выражения определяются командами GPSS.
  2. Булевы переменные позволяют пользователю проверять в одном блоке GPSS одновременно несколько условий, исходя из состояния или значения этих условий и их атрибутов.
  3. Функции позволяют производить вычисления непрерывных или дискретных функциональных зависимостей между аргументом функции (независимая величина) и зависимым значением функции.

Кроме библиотечных арифметических функций GPSS имеет генератор случайных чисел.

Запоминающие объекты

Объекты запоминающей категории обеспечивают обращения к сохраняемым значениям. К ним относятся

  1. Ячейки сохраняемых величин;
  2. Mатрицы ячеек сохраняемых величин.

Они используются для сохранения некоторой числовой информации. Любой активный транзакт может произвести запись информации в эти объекты. Впоследствии записанную в эти объекты информацию может считать любой транзакт. Матрицы могут иметь до шести измерений.

Статистические объекты

К статистическим объектам относятся

  1. Очереди;
  2. Таблицы.

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

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

Группирующие объекты

К группирующей категории относятся три типа объектов: числовая группа, группа транзактов и списки.

Списки

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

  1. текущих событий;
  2. будущих событий;
  3. задержки ОКУ или МКУ;
  4. отложенных прерываний ОКУ;
  5. пользователя.

Одноканальное устройство имеет:

  1. список отложенных прерываний - список транзактов, ожидающих занятия ОКУ по приоритету;
  2. список прерываний - список транзактов, обслуживание которых данным ОКУ было прервано;
  3. список задержки - список транзактов, ожидающих занятия ОКУ в порядке приоритета;
  4. список повторных попыток - список транзактов, ожидающих изменения состояния ОКУ.

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

  1. список задержки - список транзактов в порядке приоритета, ожидающих возможность занять освободившиеся каналы МКУ;
  2. список повторных попыток - список транзактов, ожидающих изменения состояния МКУ.

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

Пример

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

 
       SIMULATE               ; Define model
 *
 *  Model segment 1
 * 
       GENERATE 18,6          ; Customer arrive every 18±6 mn
       QUEUE    Chairs        ; Enter the line
       SEIZE    Master        ; Capture the barber
       DEPART   Chairs        ; Leave the line
       ADVANCE  16,4          ; Get a hair cut in 16±4 mn
       RELEASE  Master        ; Free the barber
       TERMINATE              ; Leave the shop
 *
 *  Model segment 2
 *
       GENERATE 480           ; Timer arrives at time = 480 mn = 8h
       TERMINATE 1            ; Shut off the run
 *
 *  Control cards
 *
       START     1            ; Start one run
       END                    ; End model

Первый сегмент кода моделирует работу парикамахерской. Оператор GENERATE создает поток транзакций и отправляет их на вход модели каждые 18±6 единиц времени. Транзакции начинают свое существование после оператора GENERATE, проходят следующие операторы, и уходят из модели на операторе TERMINATE.

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

После оператора QUEUE Сhairs транзакт попытается пройти оператор SEIZE Master, симулирующий захват "прибора" - парикмахера. Прибор имеет размерность один: если он уже занят, то SEIZE не пропустит следующий транзакт. В данном примере клиент продолжит ждать в очереди. Как только прибор освободится, следующий транзакт захватит его и обозначит как недоступный последующий транзактам. Каждому оператору SEIZE должен быть поставлен в соответствие оператор RELEASE, который запускается тогда, когда прибор оканчивает обрабатывать транзакт.

Следующий оператор - ADVANCE 16,4, замораживает объект на 16±4 единиц времени. На этом месте также могут быть любые другие операторы захвата времени. В течение этого времени другие транзакты могут свободно перемещаться через модель, но не через прибор Master, так как он уже занят.

Параллельно первому сегменту, симулирующему поведение клиентов, второй сегмент симулирует длительность рабочего дня. Через 480 единиц времени (480 минут = 8 часов) будет создан объект, который затем уничтожится на следующем операторе. В этот раз, у оператора TERMINATE есть параметр 1, означающий уменьшение специального счетчика на 1. Когда этот счетчик достигнет нуля, моделирование завершится и будет выведен результат. Этот счетчик устанавливается оператором START. В данной программе он установлен на единицу, а потому программа завершится через 480 единиц времени.

Программа даст следующий вывод:

FACILITY           AVERAGE           NUMBER         AVERAGE         SEIZING      PREEMPTING 
                UTILIZATION          ENTRIES       TIME/TRAN       TRANS. NO.    TRANS. NO.
       Master            .860               26          15.884              26

QUEUE       MAXIMUM   AVERAGE    TOTAL     ZERO     PERCENT   AVERAGE   $AVERAGE     TABLE    CURRENT
           CONTENTS   CONTENT   ENTRIES   ENTRIES    ZEROS  TIME/TRANS TIME/TRANS   NUMBER   CONTENTS
  Chairs          1      .160       27        12      44.4      2.851      5.133                    1
$AVERAGE TIME/TRANS = AVERAGE TIME/TRANS EXCLUDING ZERO ENTITIES

Он показывает, что Мастер был занят 86% всего времени, постриг 26 клиентов и потратил в среднем 15.88 единиц времени на стрижку. Также он показывает, что не более одного клиента ждало своей очереди, и в среднем число ожидающих клиентов было равно 0.160. Всего 27 клиентов сидело в очереди, т.е. 27 клиент все еще ожидал, когда парикмахерская закрылась. Из этих 27 клиентов 12 были обслужены сразу, и очередь была пуста 44.4% времени. Среднее время ожидания было равно 2.851 единицам времени, а среднее время ожидания для 15=27-12 клиентов, действительно отсидевших в очереди, было равно 5.133 единицам времени.

Полезные ссылки

  1. всякая полезная инфа
  2. удобная версия GPSS, чтобы начать работать
  3. годная презентация по операторам GPSS
  4. средней годности методичка по операторам GPSS
  5. большая, но годная методичка по GPSS и по основам имитационного моделирования. Если в моделировании полный ноль, лучше начать с нее.

Литература

  1. Армстронг Дж. Моделирование цифровых систем на языке VHDL. 1992
  2. Бусленко Н.П. Моделирование сложных систем. М.: Наука, 1978
  3. Васильев В.И.,Романов Л.Г., Червоный А.А. Основы теории систем: конспект лекций. М.: МГТУ ГА, 1994
  4. Васильев В.И., Иванюк А.И., Свириденко В.А. Моделирование систем гражданской авиации. М.: Транспорт, 1988
  5. Веников В.А., Веников Г.В. Теория подобия и моделирования. М.: Высш. шк., 1984
  6. Гнеденко Б.В., Коваленко И.Н. Введение в теорию массового обслуживания. М.: Наука, 1987
  7. Ермаков С..М., Мелас В.Б. Математический эксперимент с моделями сложных стохастических систем. 1993
  8. Калашников В.В., Рачев С.Т. Математические методы построения стохастических моделей обслуживания. М.:Наука, 1988
  9. Киндлер Е. Языки моделирования. М.: Энергоатомиздат, 1985
  10. Клейнен Дж. Статистические методы в имитационном моделировании: [в 2-х вып.] М.: Статистика, 1978
  11. Четвериков В.Н., Баканович Э.А. Стохастические вычислительные устройства систем моделирования. М.: Машиностроение, 1989
  12. Шеннон Р.Ю. Имитационное моделирование систем - искусство и наука. М.: Машиностроение, 1989
  13. Шрайбер Т. Дж. Моделирование на GPSS.