Общие сведения о языке GPSS

КАФЕДРА БИОМЕДИЦИНСКОЙ И ПОЛУПРОВОДНИКОВОЙ ЭЛЕКТРОНИКИ

Электронные методические указания к лабораторным работам (ЭМУ)

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

Специальности 200401, 200402

«Биотехнические и медицинские аппараты и системы»,

«Инженерное дело в медико-биологической практике»,

Очная форма обучения

Рязань 2009

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

Электронные методические указания к лабораторным работам (ЭМУ)

Составители и разработчики (с долей участия в %):

к.т.н, доцент С.В. Челебаев – 50 %

к.т.н, доцент О.В. Мельник – 50 %

ЭМУ утверждено на заседании кафедры биомедицинской и полупроводниковой электроники

05.06.2009 г., протокол № 10

Заведующий кафедрой ______________________ С.П. Вихров

(подпись)

Регистрационный номер ЭУП ___________

Дата регистрации ЭУП ______________

Начальник ОМО ____________________________ С.А. Батуркин

(подпись)

Лабораторная работа № 3

Моделирование работы систем массового обслуживания

Цель работы: изучение принципов моделирования непрерывно-стохастических систем.

Краткие теоретические сведения

Основные понятия систем массового обслуживания

Типовыми непрерывно-стохастическими Q- схемами являются системы массового обслуживания (СМО) (англ. queueing system).

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

Потоком событий называется последовательность событий, происходящих одно за другим в какие-то случайные моменты времени. Различают потоки однородных и неоднородных событий. Поток событий называется однородным, если он характеризуется только моментами поступления этих событий (вызывающими моментами) и задается последовательностью { t_n } = {0 £ t ₁ £ t ₂ ... £ t_n £ … },где t_n – момент наступления п- го события – неотрицательное вещественное число. Однородный поток событий также может быть задан в виде последовательности промежутков времени между п- ми (n – 1)-м событиями {t _n }, которая однозначно связана с последовательностью вызывающих моментов { t_n }, где t _n = t_n - t_{n -1}, п ³ 1, t ₀ = 0, т.е. t₁ = t ₁. Потоком неоднородных событий называется последовательность { t_n, f_n }, где t_n – вызывающие моменты; f_n – набор признаков события. Например, применительно к процессу обслуживания для неоднородного потока заявок может быть задана принадлежность к тому или иному источнику заявок, наличие приоритета, возможность обслуживания тем или иным типом канала.

В любом элементарном акте обслуживания можно выделить две основные составляющие: ожидание обслуживания заявкой и собственно обслуживание заявки. Это можно изобразить в виде некоторого i -го прибора обслуживания П_i (рис. 1), состоящего из накопителя заявок H_i, в котором может одновременно находиться j_i =0, J_i^H заявок, где J_i^H — емкость i -гo накопителя, и канала обслуживания заявок (или просто канала) K_i. На каждый элемент прибора обслуживания П_i поступают потоки событий: в накопитель H_i поток заявок w_i, на канал K_i — поток обслуживаний и_i .

Заявки, обслуженные каналом K_i, и заявки, покинувшие прибор П_i по различным причинам необслуженными (например, из-за переполнения накопителя H_i), образуют выходной поток y_i Î Y, т.е. интервалы времени между моментами выхода заявок образуют подмножество выходных переменных.

Рисунок 1. Прибор обслуживания заявок

Обычно, поток заявок w_iÎW, т.е. интервалы времени между моментами появления заявок на входе K_i,образует подмножество неуправляемых переменных, а поток обслуживания u_iÎU, т.е. интервалы времени между началом и окончанием обслуживания заявки, образует подмножество управляемых переменных.

Процесс функционирования прибора обслуживания П_i, можно представить как процесс изменения состояний его элементоввовремени z_i (t). Переход в новое состояние для П_i, означает изменение количества заявок, которые в нем находятся (в канале K_i и в накопителе H_i). Таким образом, вектор состояний для П_i, имеет вид , где z_i^H - состояние накопителя H_i, (z_i^H = 0 - накопитель пуст, z_i^H = 1 – в накопителе имеется одна заявка,..., z_i^H = J_i^H –накопитель полностью заполнен); J_i^H – емкость накопителя Н_i, измеряемая числом заявок, которые в нем могут поместиться; z_i^k – состояние канала K_i (z_i^k= 0 – канал свободен, z_i^k = 1 – канал занят).

В практике моделирования систем, имеющих более сложные структурные связи и алгоритмы поведения, для формализации используются не отдельные приборы обслуживания, а Q- схемы, образуемые композицией многих элементарных приборов обслуживания П_i. Если каналы К_i различных приборов обслуживания соединены параллельно, то имеет место многоканальное обслуживание (многоканальная Q- схема), а если приборы П_i и их параллельные композиции соединены последовательно, то имеет место многофазное обслуживание (многофазная Q- схема). Таким образом, для задания Q- схемы. необходимо использовать оператор сопряжения R, отражающий взаимосвязь элементов структуры (каналов и накопителей) между собой.

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

Собственными (внутренними) параметрами Q -схемы будут являться количество фаз J_ф, количество каналов в каждой фазе J_kj, j = , количество накопителей каждой фазы J_Hk, k = , емкость i -го накопителя J_i^H. Следует отметить, что в теории массового обслуживания в зависимости от емкости накопителя применяют следующую терминологию для систем массового обслуживания:

- системы с потерями (J_i^H = 0, т.е. накопитель в приборе П_i -отсутствует, а имеется только канал обслуживания К_i),

- системы с ожиданием (J_i^H ®¥, т.е. накопитель Н_i имеет бесконечную емкость и очередь заявок не ограничивается),

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

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

В зависимости от динамики приоритетов в Q -схемах различают статические и динамические приоритеты. Статические приоритеты назначаются заранее и не зависят от состояний Q -схемы. Динамические приоритеты возникают при моделировании в зависимости от возникающих ситуаций. Исходя из правил выбора заявок из накопителя Н_i на обслуживание каналом К_i, можно выделить относительные и абсолютные приоритеты. Относительный приоритет означает, что заявка с более высоким приоритетом, поступившая в накопитель Н_i, ожидает окончания обслуживания предшествующей заявки каналом K_i и только после этого занимает канал. Абсолютный приоритет означает, что заявка с более высоким приоритетом, поступившая в накопитель H_i, прерывает обслуживание каналом К_i заявки с более низким приоритетом и сама занимает канал (при этом вытесненная из К_i заявка может либо покинуть систему, либо может быть снова записана на какое-то место в H_i).

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

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

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

где Т - среднее значение интервала между поступлением очередных требований.

Для многих реальных процессов поток требований достаточно хоро­шо описывается законом распределения Пуассона:

вероятность того, что в обслуживающую систему за время t поступит именно k требований:

где - среднее число требований, поступивших на обслуживание в единицу времени.

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

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

При показательном законе распределения времени обслуживания ве­роятность события, что время обслуживания продлиться не более чем t, равна:

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

,

где - среднее время обслуживания одного требования одним об­служивающим устройством.

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

где n - количество обслуживающих устройств.

Важным параметром СМО является коэффициент загрузки , который определяется как отношение интенсивности поступления требований к интенсивности обслуживания v.

где a - коэффициент загрузки; - интенсивность поступления тре­бований в систему; v - интенсивность обслуживания одного требования одним обслуживающим устройством.

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

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

Для СМО с ожиданием количество обслуживаемых устройств n должно быть строго больше коэффициента загрузки (требование установившегося или стационарного режима работы СМО):

.

В противном случае число поступающих требований будет больше суммар­ной производительности всех обслуживающих устройств, и очередь будет неограниченно расти.

Для СМО с отказами и смешанного типа это условие может быть ос­лаблено, для эффективной работы этих типов СМО достаточно потребо­вать, чтобы минимальное количество обслуживаемых устройств n было не меньше коэффициента загрузки :

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

Общие сведения о языке GPSS

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

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

1. Динамические объекты – транзакты (сообщения) моделируют заявки. Транзакты могут создаваться, перемещаться по объектам, представляющим в модели оборудование, расщепляться, ликвидироваться. Каждый транзакт может иметь атрибуты – параметры, доступные программисту.

2. Аппаратно-ориентированные объекты представляют в модели ресурсы вычислительной системы. Это устройства, память (многоканальные устройства) и логические переключатели. Устройство может быть свободно или занято определенным транзактом. Состояние памяти характеризуется только количеством свободных или занятых ячеек (их конкретные адреса не фиксируются). Логический переключатель может быть во включеном (S) или выключенном (R) состояниях.

3. Вычислительные объкты: арифметические переменные с фиксированной или плавающей точкой, булевые переменные, случайные функции.

4. Запоминающие объекты: ячейки.

5. Статистические объекты: очереди и таблицы для сбора статистических данных.

6. Группирующие объекты: группы и списки.

Программа моделирования, разрабатываемая пользователем состоит из операционных объектов (блоков, операторов) и управляющих операторов (карт).

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

Управляющие карты управляют работой интерпретатора (пуск, останов, очистка и т.д.).

Интерпретатор автоматически фиксирует для каждого объекта стандартные числовые атрибуты (СЧА). СЧА могут использоваться в качестве операндов, аргументов функций, таблиц, элементов переменных. Некоторые СЧА (параметры транзактов, значения сохраняемых ячеек памяти) можно изменять программно, основная часть СЧА доступна только для чтения, но не для записи.

Основные операторы GPSS

Оператор языка GPSS содержит 4 поля: метка (необязательное поле), операция, операнды, комментарий (необязательное поле). Комментарием считаются все символы, стоящие после символа ″;″. Операция может содержать до 9 операндов. Операнды обозначаются латинскими буквами: A, B, C, D, E, F, G, H, I. Часть операндов может быть опущена (если значения этих операндов берутся по умолчанию). Если опускаются не последние операнды, то запятые сохраняются. Если опускаются не последние операнды, то запяты сохраняются (пример: A,B,,D,E).

Далее приводятся основные операторы и их назначение (обязательные операнды подчеркнуты).

SEIZE A (занять). А – имя устройства. Занять можно только свободное устройство. Уже занятое устройство не впускает транзакты, перед ним организуется очередь на основе относительных приоритетов.

RELEASE A (освободить). A – имя устройства. Устройство должно быть освобождено тем же транзактом, который его занял.

PREEMPT A,B,C,D,E (захватить). A – имя устройства. B – возможность захвата занятого устройства. Если B =PR, то возможна любая глубина прерываний на основе абсолютных приоритетов. По умолчанию приоритеты не учитываются, прерывать обслуживание прерывающего транзакта нельзя. C – метка оператора к которому переходит прерванный транзакт. D – номер параметра, в который запишется остаток времени, оставшегося до конца обслуживания. E – признак снятия с обслуживания прерванного транзакта. Если E =RE, то транзакт снимается с обслуживания. По умолчанию прерванный транзакт дообслуживается после обслуживания предыдущего.

RETURN A (вернуть). A – имя захваченного устройства. Освобождать устройство должен тот же транзакт, который его занял.

GENERATE A,B,C,D,E,F,G,H,I (генерировать транзакты). A – среднее значение интервала. B – половина интервала разброса (пример: GENERATE 10,5 – интервал формирования транзактов от 5 до 15 единиц модельного времени равновероятен). C – время появления первого транзакта (по умолчанию C =1). D – максимальное число формируемых транзактов за время моделирования (по умолчанию D = ). E – приоритет транзактов (по умолчанию E =0). F ÷ I – не имеют значения.

TERMINATE A (завершить). Оператор ликвидирует вошедший в него транзакт, вычитает A единиц из счетчика завершений. По умолчанию A =0.

ADVANCE A,B (задержать). A – среднее время задержки. B – модификатор разброса или модификатор функции. Оператор может впускать сколько угодно транзактов.

QUEUE A,B (войти в очередь). A – имя очереди. B – количество занимаемых единиц (по умолчанию B =1).

DEPART A,B (выйти из очереди). A – имя очереди. B – количество занимаемых единиц (по умолчанию B =1). Оператор ставится после операторов SEIZE или PREEMPT.

PRIORITY A,B (назначить приоритет). A – назначаемый транзакту приоритет (в диапазоне от 0 до 127; наивысший приоритет = 127). B=BUFFER означает, что транзакт должен остановиться после изменения приоритета.

Основные понятия имитационного моделирования на GPSS. Главным элементом модели на GPSS является транзакт. Под транзактом понимается заявка, надлежащая обслуживанию.

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

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

Еще одним сегментом модели является прибор. Он обеспечивает продвижение дельного времени в системе.

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

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

Модель системы массового обслуживания с одним прибором. Такая модель состоит из генератора транзактов, обслуживающего прибора и блока, удаляющего транзакта из системы (рис. 2).

Рисунок 2. Модель СМО с 1 прибором

Для введения транзактов в систему используется блок Generate.

Оператор Generate A задает формирование транзактов с интервалом в A единиц модельного времени.

Пример. Generate 10

На рис. 3 показаны времена появления транзактов.

Рисунок 3. Модель появления транзактов

Транзакты появятся в системе в модельные времена 0, 10. 20, 30, …

Оператор Generate A, B задает появление заявок в системе: A – средняя длительность интервала появления заявок в системе, B – половина интервала разброса от среднего интервала появления заявок в системе.

Пример. Generate 20, 4

Интервал времени появления: 16 ≤ t ≤ 24

Времена возможного появления:

1. 16, 37, 54, …

2. 22, 41, … Возможны другие варианты.

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

Блок Terminate осуществляет удаление транзактов из системы

Блок Seize помещает транзакт в прибор. Seize используется с одним параметром: Seize A. Параметр A задает символьное или численное имя прибора.

Пример.

Seize Prib; Транзакт занимает прибор с именем Prib.

Блок Advance осуществляет задержку транзакта в приборе. Оператор Advance A, B задает задержку транзактов в приборе со средним временем задержки A и половиной разброса задержки B. По умолчанию B = 0.

Пример.

Advance 30, 2

Интервал времени обслуживания: 28 ≤ t ≤ 32.

Блок Release удаляет транзакт из прибора. Release A удаляет транзакт из прибора с именем A.

Пример. Release Prib;

На рис. 4 показан текст программы, реализующей модель (см. рис. 2):

Рисунок 4. Текст программы

Рисунок 5. Блок-схема модели СМО с 1 прибором (см. рис. 2)

Модель системы массового обслуживания с одним прибором и очередью. Модель показана на рис. 6.

Рисунок 6. Модель СМО с одним прибором и очередью

Блок Queue с одним параметром А помещает транзакт в очередь с именем А.

Блок Depart а извлекает транзакт из очереди с именем А.

Текст программы:

; 1-й сегмент модели – сегмент команд

Generate 100

Queue Och

Seize Prib

Depart Och

Advance 110

Release Prib

Terminate

; 2-й сегмент модели – сегмент таймера

Generate 1000

Terminate 1

Рисунок 6. Блок-схема модели СМО с одним прибором и очередью

Дата добавления: 2015-07-15