Небольшой гайд, описывающий основы моделирования в среде GPSS World. Буду краток, если надо подробнее --- смотрите презентации. Сначала немного про основные моменты, потом разбор одной (или более ;) ;) ;) ;)) задачи.
Основные конструкции
Если вам лень смотреть презентации, то давайте я кратко изложу суть. GPSS предоставляет различные штуки:
- СтатистическиеОчередь
Таблица - Аппаратно-ориентированныеЛогический переключатель
Многоканальное устройство
Обслуживающее устройство
Первое нужно для сбора статистики, в задачах может не понадобиться (у меня не было), так что подробнее можно почитать, например, тут.
Логических переключателей я нигде не видел, в презентации они тоже упоминаются незначительно: при прохождении транзакта меняет свое состояние с “включено” на “выключено” или наоборот.
Различные устройства можно рассматривать как примитивы синхронизации. Многоканальное устройство --- устройство, которое может обрабатывать несколько запросов одновременно (максимальное количество конечно и задаётся с помощью специального оператора). Параллельщики могут увидеть тут семафор и я могу их понять. Обслуживающее устройство может обрабатывать максимум один запрос. Мьютекс какой-то.
Схема работы всего этого дела
Описываются транзакты, которые взаимодействуют с описанными выше конструкциями. Создаются и уничтожаются они автоматически, в соответствии с описанными правилами.
GENERATE A,B,C,D,E
- A - средняя величина интервала между генерацией транзактов
- B - половина длины отрезка [A-B,A+B] при задании равномерного распределения интервала между генерацией (всё станет понятно чуть позже)
- C - задержка начала генерации
- D - число сгенерированных транзактов
- E - приоритет транзактов
GENERATE начинает блок кода, который надо завершить командой TERMINATE. Пример:
GENERATE 10, 2
QUEUE 1
ADVANCE 10
DEPART 1
TERMINATE
Этот код будет генерировать транзакты с периодом [8,12] единиц времени. После каждой генерации будет выбираться число из этого отрезка, которое станет временем до генерации следующего транзакта.
Внутри блока расположены команды для постановки транзакта в очередь, вывода из неё и ожидания 10 единиц времени между ними. Об этом чуть позже.
Операции транзактов
Задержка продвижения
Можно считать, что транзакт просто засыпает на определённое количество времени. Этим можно моделировать продолжительный процесс обработки какого-то запроса, например.
Реализуется это всё с помощью оператора ADVACE:
ADVANCE A,B
- A - средняя величина интервала задержки транзактов
- B - половина длины отрезка при задании равномерного интервала.
Немного примеров:
ADVANCE 10
;транзакт ждёт 10 единиц времени
ADVANCE 15, 5
; транзакт ждёт от 10 до 20 единиц (выбирается случайно и равномерно)
ADVANCE (Exponential(1,0,300))
; ждём промежуток времени, выбранный из какого-то хитрого распределения (об этом позже)
Работа с устройствами
Многоканальные
Эти устройства могут работать с несколькими транзактами одновременно. Можно моделировать продавцов: один канал = один продавец.
устройство STORAGE A: задаёт число каналов
- устройство - имя устройства (числовое или символьное)
- A - число каналов
ENTER A,B: занять каналы
- A - имя устройства
- B - число занимаемых каналов (1 по умолчанию)
LEAVE A,B: освободить каналы
- A - имя устройство
- B - число освобождаемых каналов (1 по умолчанию)
Одноканальные
Частный случай многоканальных устройств, но вы поняли, в чём подвох.
SEIZE A: занять устройство
- A - имя
RELEASE A: освободить
- A - имя
Переменные
Очень хитрая штука, хранится само выражение, которое каждый раз вычисляется заново. Здесь я затрону основные моменты, которых должно хватить для задач. Если не хватит --- дайте знать или гуглите.
Существует куча уже определённых переменных, которые называются атрибутами, например:
- F12 - состояние устройства 12
- F$ASD - состояние устройства ASD
- P33 - значение параметра 33 транзакта
Могут быть полезны:
- S R - текущее число занятых и свободных каналов
- RN1 - псевдослучайное число из равномерного распределения на [0,999]
- V - значение арифметического выражения
Например, чтобы получить случайное число от 10 до 20, мы пишем:
RAND VARIABLE 10+10#RN1/1000
Красота. # - умножение. Тоже здорово.
Сохраняемые величины
Играют роль статических переменных, доступны везде. Статические, я так понимаю, в том смысле, что значение не считается каждый раз, а хранится вычисленным. Есть скалярные величины (префикс X) и массивы (префикс MX).
SAVEVALUE A,B: изменить значение
- A - имя величины. Если заканчивается на + или -, то вместо установки значения, оно будет изменено на величину, указанную в B
- B - значение для замещения, добавления или вычитания
Примеры:
SAVEVALUE 1,1
SAVEVALUE X1,1
SAVEVALUE Income-,X$Expenses
SAVEVALUE X1+,X2
Как я понимаю, первые два примера эквивалентны, ведь X - префикс скалярной величины.
INITIAL A,B: установка начального значения скалярной величины. Используется так же, как и предыдущий оператор, но теперь нет добавлений и вычитаний.
Штуки, которые мне не понадобились
Мне не понадобились, так что я не разбирался с ними. Приведу тут их список, но дайте знать, если понадобится расписать что-то.
- Параметры транзактов
- Ссылки на объекты
- Функции
Запуск модели
START A,B: начать моделирование
- A - начальное значение счётчика числа завершений
- B - можно передать NP, чтобы запретить печать отчётов
TERMINATE A: уничтожение транзакта
- A - величина, которая будет вычтена из счётчика числа завершений (по умолчанию 0)
Примерная схема:
- Определить все переменные
- Написать блоки генерации транзактов
- Установить параметры типа числа каналов устройств
- Начать моделирование
Значения, которые надо передавать в START и TERMINATE зависят от задачи. В следующем разделе я привожу пример своей задачи.
Пример решения задачи
У меня была задача 4:
Обслуживание каждого клиента в компьютерном супермаркете включает оформление и выдачу его заказа. В супермаркете работает 10 специалистов, каждый из которых может выполнять любую работу по обслуживанию клиента. Известно, что клиенты пребывают с интервалом 15 ± 10 мин., а оформление и выдача заказа одним работником занимают соответственно 20 ± 15 и 30 ± 25 мин. Каждый клиент приносит супермаркету доход 100 ± 80 руб., а использование работника на оформлении и выдаче заказов приводит к соответственным затратам 100 и 150 руб. в день. Требуется так распределить специалистов между отделами оформления и выдачи, чтобы обеспечить максимальную разность между доходом и расходом за неделю при условии ежедневной работы супермаркета с 10.00 до 21.00.
Мне повезло, решение этой задачи есть в презентации. Вот что получилось у меня:
Income VARIABLE 20+160#RN1/1000
Cost VARIABLE 700#(S$CHECKOUT + R$CHECKOUT) + 1050#(S$HANDOUT + R$HANDOUT)
GENERATE 15,10
ENTER CHECKOUT
ADVANCE 20,15
LEAVE CHECKOUT
ENTER HANDOUT
ADVANCE 30,25
LEAVE HANDOUT
SAVEVALUE INCOME+,V$Income
TERMINATE
GENERATE 4620
SAVEVALUE INCOME-,V$Cost
TERMINATE 1
CHECKOUT STORAGE 3
HANDOUT STORAGE 7
START 1
Первые две строки определяют переменные, вычисление которых даёт значения для дохода с клиента и стоимости труда.
Первая переменная выдаёт значение от 20 до 180, не обязательно целое. На каком-нибудь привычном языке выражение справа выглядит так
20 + 160 * random(0,999) / 1000
Вторая переменная будет выдавать значения, зависящие от количества людей в отделах. Умножаем 700 (зарплата в отеделе продаж за неделю) на сумму количества свободных и занятых каналов (продавцов). Судя по всему, нет способа просто получить число каналов. Или есть, но я не искал. У Кривулина так.
Первый блок GENERATE генерирует транзакты каждые 5-15 минут. Транзакт представляет собой покупателя, который сначала идёт в отдел оформления, ждёт освобождения продавца, тусит от 5 до 35 минут, освобождает продавца и идёт в отдел выдачи, где проводит от 5 до 55 минут. В конце всего этого мы обновляем значение INCOME, в котором хранится общий доход на данный момент. Обновление заключается в прибавлении значения случайной величины Income, заданной в первой переменной.
Второй блок будет сгенерирован через 4620 единиц времени. Это общее время моделирования, эквивалетное неделе работы магазина. Сгенерированный транзакт вычтет из дохода оплату рабочих, после чего завершит выполнение модели (обратите внимание на аргумент оператора TERMINATE).
В последних трёх строках мы задаём количество людей в отделах оформления и выдачи и начинаем моделирование. В моём случае получилось, что выгоднее всего поставить троих на оформление и 7 на выдачу.
В этой задаче известно время окончания моделирования, так что был транзакт, который появлялся в нужный момент и всё завершал. Поэтому в START была передана единица, которая вычиталась в этом транзакте-убийце.
PLUS - The Programming Language Under Simulation
Штуковина для расширения возможностей, предоставляемых средой. Всё, за что вы так любите императивное программирование: переменные, циклы, процедуры и т.д.
Организация кода
Код PLUS может располагаться
- в отдельных процедурах;
- вперемешку со всем, описанным выше.
Судя по всему, PLUS лояльнее относится к пробелам и всему такому, так что развлекайтесь. Напомню, что в стандартном GPSS пробелы между аргументами оператора, перечисленными через запятую, недопустимы.
ВАЖНО: все определения плюсовых процедур должны идти в самом начале кода. По какой-то причине в противном случае ломаются некоторые части модели. В моём случае это были переменные, о которых я писал выше.
Каждую команду внутри процедур надо заканчивать символом ";".
Если надо использовать всю эту радость внутри обычных операторов GPSS, то надо окружить её скобками, например:
GENERATE (Exponential(1,0,1000))
ADVANCE (Exponential(1,0,300))
ASSIGN 1,(Normal(1,10,2))
SAVEVALUE 1,(LOG(X2))
Да, во всех этих случаях идёт просто вызов процедуры. Но нужно ли что-то ещё?
Многие конструкции языка позволяют использовать как простые, так и составные выражения. Для определения составных операторов (блоков кода) используется
BEGIN <Операторы> END;
Разумеется, это всё можно разбивать по строкам и всё такое. Вы ребята взрослые, всё поймёте.
Процедуры
Определяются так:
PROCEDURE Название(список аргументов)
BEGIN
код процедуры
END;
Список аргументов - имена, разделённые запятыми. С помощью оператора RETURN можно возвращать значения любого вида.
Вызов процедур происходит привычным образом:
TestProcedure(1,2,3);
TestProcedure2("asd", 1, "qwe");
Переменные
Не требуют объявления и не имеют фиксированного типа. Можно использовать оператор TEMPORARY, чтобы объявить переменную локальной, однако это почти не имеет смысла и несёт с собой только сложности, используйте по вкусу.
Для задания значения используется привычный нам оператор присваивания (=):
Time=0;
Cost=V$Expenses/ABS(Time-10);
Управляющие конструкции
Всё просто и привычно.
IF (условие) THEN оператор1 [ELSE оператор2];
WHILE (условие) DO оператор;
Условие может быть выражено через операторы сравнения <, <=, >, >=,
Оператором может выступать как одна инструкция, так и блок.
Взаимодействие с базовым GPSS
Для использования инструкций типа SHOW или START внутри плюсов нужна процедура
DoCommand(команда);
DoCommand("START 1");
DoCommand("SHOW X$INCOME");
Сохраняемые величины и переменные доступны в PLUS без всяких танцев:
WeekIncome=X$INCOME;
Эксперименты
Особый тип процедур, необходимый для хитрого прогона модели. Определяется аналогично:
EXPERIMENT Название(аргументы)
BEGIN
тело
END;
Тоже могут возвращать значения, но нужно ли оно? Едва ли.
Запуск экспериментов - не совсем автоматизируемое дело. Вообще, для запуска экспериментов используется оператор CONDUCT, но если попытаться вставить его в файл с кодом, то что-то пойдёт не так. Так что делаем так:
- Command - Create Simulation
- Command - CONDUCT
- Указываете имя эксперимента и аргументы (в скобках)
Полезные процедуры (конкатенация строк и распределения)
Catenate(str1, str2) - склеивает две строки и возвращает результат
Catenate("asd", "123") = "asd123"
PolyCatenate(str1, ..., strn) - склеивает произвольное число строк
PolyCatenate("wow", "so", "gpss") = "wowsogpss"
Что касается распределений, то их там очень много всяких разных. Я посмотрел ваши задачи, мне показалось, что там нужно только экспоненциальное, так что напишу только про него. Обращайтесь ко мне или документации, если нужно другое, там ничего сложного.
Экспоненциальная случайная величина представлена следующей процедурой:
Exponential(Steam, Locate, Scale)
- Stream - используемый генератор псевдослучайных чисел. Целое, больше 0. Просто пишите 1.
- Locate - сдвиг случайной величины. Судя по всему, можно оставлять 0.
- Scale - параметр случайной величины. Также будет её математическим ожиданием. Сюда писать среднее значение, как я понимаю.
Если я что-то упустил - дайте знать.
Обновлённый пример решения задачи
В новом варианте эксперименты будут прогоняться иначе: один прогон модели будет соответствовать одному дню работы магазина со сбором статистики и поиском лучшего распределения рабочих.
Вот весь код:
PROCEDURE SimulateWeek(CHK,HND)
BEGIN
TEMPORARY DAY;
TEMPORARY RES;
DAY=0;
DoCommand(Catenate("CHECKOUT STORAGE ",CHK));
DoCommand(Catenate("HANDOUT STORAGE ",HND));
WHILE (DAY < 7) DO BEGIN
DoCommand("START 1,NP");
DoCommand("CLEAR OFF");
DAY=DAY+1;
END;
RES=X$Income;
DoCommand("CLEAR");
RETURN RES;
END;
EXPERIMENT PCStore(TOTAL)
BEGIN
TEMPORARY CHK;
TEMPORARY MAXINCOME;
TEMPORARY MAXCHK;
CHK=1;
MAXINCOME=0;
MAXCHK=-1;
WHILE (CHK < TOTAL) DO BEGIN
TEMPORARY RES;
TEMPORARY REPORTSTR;
RES=SimulateWeek(CHK,TOTAL-CHK);
REPORTSTR=PolyCatenate(
"""Checkout: ",CHK,
" Handout: ",TOTAL-CHK,
" Income: ",
RES,"""");
DoCommand(Catenate("SHOW ", REPORTSTR));
IF(RES > MAXINCOME) THEN BEGIN
MAXINCOME=RES;
MAXCHK=CHK;
END;
CHK=CHK+1;
END;
MAXSTR=PolyCatenate(
"Best result: Checkout: ", MAXCHK,
" Handout: ",TOTAL-MAXCHK,
" Income: ",MAXINCOME);
DoCommand("SHOW MAXSTR");
END;
Income VARIABLE 20+160#RN1/1000
Cost VARIABLE 100#(S$CHECKOUT + R$CHECKOUT) + 150#(S$HANDOUT + R$HANDOUT)
GENERATE 15,10
ENTER CHECKOUT
ADVANCE 20,15
LEAVE CHECKOUT
ENTER HANDOUT
ADVANCE 30,25
LEAVE HANDOUT
SAVEVALUE INCOME+,V$Income
TERMINATE
GENERATE 660
SAVEVALUE INCOME-,V$Cost
TERMINATE 1
Тут многое требует объяснения, но постараюсь быть краток.
Сначала немного про саму модель. Изменился только моделируемый отрезок времени: теперь день вместо недели. Делим на 7 затраты на оплату труда и частоту генерации убийцы-транзакта. Успех.
Теперь по коду. В самом начале определяется процедур симуляции недели работы магазина. Для этого 7 раз в цикле выполняются команды "START 1,NP" и "CLEAR OFF". Первая прогоняет модель, не создавая окно с отчётом, потому что иначе их будет очень вери много. Вторая очищает состояние модели кроме сохраняемых величин (на самом деле, немного не так, но в наших целях достаточно такого понимания). Таким образом мы прогоним модель 7 раз, освобождая все устройства между прогонами (без второй команды мы бы получили ошибку в духе "выходов из устройства больше, чем входов"). В конце процедуры возвращается значение сохраняемой величины INCOME, отображающей доход за неделю.
Далее идёт определение эксперимента. Параметром передаётся общее количество рабочих (в моей задаче их 10). Так как у меня разбиение на две части, то я просто иду в цикле по количеству людей в первом отделе, попутно считая "населённость" второго. В переменную RES закидываю прибыль при такой конфигурации, вывожу информацию о результатах прогона и обновляю известное максимальное значение для прибыли и конфигурации, при которой оно достигается. После завершения цикла выводится лучший результат.
Немного о выводе в журнал. Я не искал, как это можно делать иначе и можно ли вообще, но использую стандартный оператор SHOW, который может работать как с литеральными строками (внутри цикла), так и с нелокальными переменными (вывод лучшего, заметьте, что нигде нет строки "TEMPORARY MAXSTR").
У меня кидало кучу ошибок, когда я выполнял команду "SHOW %локальная переменная%", так что пришлось добавить кавычек вокруг и приписать это всё к команде. То есть в первом случае оператор SHOW ничего не знает ни о каких переменных, получая обычную строку для вывода. Думаю, что локальные переменные доступны только в своём плюсовом блоке или что-то такое. Так что лучше пользуйтесь нелокальными для формирования сообщений.