Имитационное моделирование систем массового обслуживания в GPSS

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

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

В любом элементарном акте обслуживания можно выделить две  основные составляющие: ожидание обслуживания заявкой и само обслуживание заявки.

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

СМО классифицируют по следующим  признакам:

• по количеству каналов обслуживания они делятся на одноканальные и многоканальные СМО;
• по организации ожидания заявки – на системы с отказами и системы с ожиданием или с очередями (накопителями);
• СМО с накопителями, в свою очередь, делятся на системы с приоритетами и без приоритетов;
• по количеству фаз обслуживания – на однофазные и многофазные;
• по взаимосвязи с потоками заявок – на разомкнутые и замкнутые.

Эффективность работы СМО  характеризуется следующими основными  показателями:

• абсолютная пропускная способность – среднее количество заявок, которое может обслужить система в единицу времени;
• относительная пропускная способность – отношение среднего числа заявок, обслуженных СМО в единицу времени, к среднему числу всех заявок, поступивших в СМО за это же время;
• коэффициент занятости – отношение среднего числа занятых каналов к общему числу каналов;
• коэффициент простоя – отношение среднего числа свободных каналов к общему числу каналов.

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

 

 

 

 

1.3 Система имитационного  обслуживания GPSS

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

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

1.3.1 Операторы языка GPSS используемые в работе

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

GENERATE - вводит транзакты в модель.

Формат: GENERATE А, В, С, D, E, F, G

А - среднее значение интервала  времени;

В - разброс или модификатор  среднего значения (по умолчанию ноль);

С - время появления первого  транзакта;

D - общее число генерируемых транзактов;

Е - уровень приоритета каждого  транзакта; (от 0 до 127, значение по умолчанию 0);

F - число параметров (по умолчанию 12);

G - тип параметра (F - полнословный, Н - полусловный - по умолчанию).

Вводит транзакты в модель, посылая их в следующий по порядку блок. Если в поле В не указана функция, то интервал между поступлением транзактов определяется случайным числом, равномерно распределенным в диапазоне от (А - В) до (А + В). Если поле В является функцией (FN$), то этот интервал определяется произведением поля А на значение функции, заданной в поле В.

 

QUEUE - помещает транзакт в конец бесконечной очереди.

Формат: QUEUE А, В

А - номер очереди (числовое или символьное имя очереди);

В - число добавляемых  к очереди элементов (по умолчанию 1).

Увеличивает текущее содержимое очереди, указанной в поле А, на значение в поле В. Если поле В не определено, увеличивает содержимое очереди на единицу. Транзакт может находиться в двух различных очередях одновременно.

 

DEPART - удаляет транзакт из бесконечной очереди.

Формат: DEPART А, В

А - номер (имя) очереди;

В - число удаляемых из очереди элементов.

Удаляет текущий транзакт из очереди, указанной в поле А, и уменьшает содержимое очереди на значение поля В. Транзакт может находиться одновременно в двух различных очередях.

 

SEIZE - занимает устройство.

Формат: SEIZE A

А - номер устройства.

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

 

RELEASE - освобождает устройство.

Формат: RELEASE A

А - номер устройства (числовое или символьное имя освобождаемого устройства).

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

 

ADVANCE – задерживает транзакт.

Формат: ADVANCE А, В

А – среднее время задержки (константа, если В не задано);

В – разброс относительно среднего значения, должен быть меньше или равен А.

Блок ADVANCE моделирует временную задержку транзакта в течение определенного интервала. Значение задержки по умолчанию равно нулю. Если поле В не является FN$, то время задержки является случайным числом, распределенным равномерно на интервале от (А + В) до (А - В). Если поле В является функцией FN$, то время задержки определяете произведением поля А на значение функции в поле В.

Функция может быть использована для задания времени задержки с определенным средним значением  и отклонением, зависящим от А.

 

Блок STORAGE – память.

Формат: имя STORAGE A

имя —имя многоканальных устройств (МКУ), используемое для ссылок на него;

A —емкость (количество каналов  обслуживания) МКУ, задаваемая константой.

 

ENTER  - для занятия обслуживания  МКУ используется пара блоков.

Формат: ENTER   A,B

A - указывается номер или  имя МКУ;

B - число каналов МКУ, занимаемых при входе в блок ENTER.

 При входе транзакта в блок ENTER текущее содержимое МКУ увеличивается на число единиц, указанное в поле B. Если свободная емкость МКУ меньше значения поля B, то транзакт не может войти в блок ENTER и остается в предыдущем блоке, образуя очередь в списке текущих событий.

 

LEAVE - для освобождения памяти.

Формат: LEAVE A,B

A указывается номер или  имя МКУ;

B - число каналов МКУ освобождаемых при входе в блок LEAVE.

При входе транзакта в блок LEAVE текущее содержимое МКУ уменьшается на число единиц, указанное в поле B. Не обязательно освобождается такое же число каналов МКУ, какое занималось при входе данного транзакта в блок ENTER, однако текущее содержимое МКУ не должно становиться отрицательным.

 

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

Формат: TRANSFER А, В, С, D

А - режим передачи (" ",., ALL, BOTH, FN, P, PICK, SBR, SIM);

В - номер блока;

С – номер блока;

D — значение индекса, используемое в режиме ALL.

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

 

START - управление процессом моделирования.

Формат: STAR[T] А, В, С, D

А - счетчик числа завершений;

В - подавление вывода на печать (В = NP);

С - промежуточный вывод  статистики; 0 - распечатка списков.

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

Формат: TERMINATE A

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

 

TEST – перемещае транзакт согласно сравнению.

Формат: TEST Х А, В, С

Х – условный оператор может  принимать значения:

• G – больше;
• GE – больше или равно;
• L – меньше;
• LE – меньше или равно;
• E – равно;
• NE – не равно.

А и В – сравниваемые величины.

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

2. Формализация модели  и написание программы

2.1 Концептуальная модель

Концептуальная модель представлена на рис.2.1

 

 

 

 

 

 

 

 

Рис.1. Концептуальная модель задачи

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

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

 

2.2. Таблица определений

В таблице 1 приведены определения, используемые в работе модели.

 

Таблица 1

GPSS	Характеристика
1 усл.ед.вр.	1 мкс
Транзакты
1 сегмент	сигналы
Устройства
CAN	входной буфер канала
1EVM	1ая ЭВМ
2EVM	2ая ЭВМ
3EVM	3ья ЭВМ
Очереди
CANOCH	буфер канала
OCH1	входной накопитель 1
OCH2	входной накопитель 2
OCH3	входной накопитель 3
OCH	общая очередь в миниЭВМ

 

 

 

 

 

 

 

 

 

 

 

 

 

2.3. Листинг программы

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

 

GENERATE 10,5  ;генерация сигналов

QUEUE CANOCH  ;вход в очередь в канал

SEIZE CAN  ;вход на обработку в канал

DEPART CANOCH  ;выход из очереди

ADVANCE 10,3  ;обработка в канале

RELEASE CAN  ;выход из канала

TEST L Q$OCH1,10,MET3  ;не превышает ли 10 единиц очередь OCH1

TEST L Q$OCH2,10,MET3  ;не превышает ли 10 единиц очередь OCH2

TEST L Q$OCH3,10,MET3  ;не превышает ли 10 единиц очередь OCH3

TEST L Q$OCH1,Q$OCH2,MET1;сравнение объёмов очередей ОСН1 и ОСН2

TEST L Q$OCH1,Q$OCH3,MET2;сравнение объёмов очередей ОСН1 и ОСН3

QUEUE OCH  ;вход в общую очередь

QUEUE OCH1  ;вход в очередь к миниЭВМ 1

SEIZE EVM1  ;вход в миниЭВМ 1

DEPART OCH  ;выход из общей очереди

DEPART OCH1  ;выход из очереди к миниЭВМ 1

TEST L Q$OCH,25,MET4  ;сравнение объёма общей очереди

ADVANCE 33                ;обработка в миниЭВМ 1

          TRANSFER ,MET7 

MET4 ADVANCE 25 ;обработка в миниЭВМ 1 в случае                     п                                     переполнении общей очереди

MET7 RELEASE EVM1 ;выход из миниЭВМ 1

TERMINATE 1 

MET1 TEST L Q$OCH2,Q$OCH3,MET2 ;сравнение объёмов очередей ОСН2 и ОСН3

QUEUE OCH ;вход в общую очередь

QUEUE OCH2 ;вход в очередь к миниЭВМ 2

SEIZE EVM2 ;вход в миниЭВМ 2

DEPART OCH ;выход из общей очереди