573 (интерпретатор GPSS и описание к нему)

Государственный комитет Российской федерации по высшему образованию

Ульяновский государственный технический университет

ИМИТАЦИОННОЕ МОДЕЛИРОВАНИЕ НА ЯЗЫКЕ GPSS

методические указания

Составители: О.Н.Евсеева В.В.Шишкин

Ульяновск 1995

- 2 -

УДК 681.03

Имитационное моделирование на языке GPSS : Метод. указ. / О.Н.Евсеева, В.В.Шишкин. - Ульяновск: УлГТУ, 1995. - 40 с.

Настоящие методические указания разработаны в соответствии с программой курса "Моделирование" и предназначены для студентов специальности 2201, 5528.

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

Рецензент

Рекомендован к изданию методической комиссией РТФ

Ульяновский политехнический институт, 1995.

- 3 -

С О Д Е Р Ж А Н И Е

ВВЕДЕНИЕ 4

1. ОСНОВНЫЕ СВЕДЕНИЯ О СИСТЕМЕ МОДЕЛИРОВАНИЯ

1. Модели массового обслуживания 4

2. Назначение и состав системы моделирования 7

3. Сокращенное описание объектов GPSS 8

4. Протокол и результаты работы программы на GPSS 10

2. ПРИМЕНЕНИЕ GPSS ДЛЯ МОДЕЛИРОВАНИЯ
ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ 12

1. Моделирование ВС, представленных как одноканальные сис­темы массового обслуживания 13

2. Модель мультипрограммной ВСколлективного пользования 19

3. Модели ВС с изменяемой интенсивностью обслуживания за­дач и случайным выбором программы обработки 21

4. Модели ВС с различными дисциплинами обслуживания 24

5. Модель последовательной ВС 26

6. Модель параллельной ВС 27

3. ПРАКТИКУМ ПО МОДЕЛИРОВАНИЮ ВС НА GPSS 28

3.1. Общий порядок выполнения заданий 28

1. Самостоятельная подготовка студентов 28

2. Содержание отчета 28

3.2. Задания практикума 29

1. Моделирование случайных величин 29

2. Моделирование ВС как СМО с одним обслуживающим прибором 34

3.2.3. Моделирование многопроцессорных ВС с перераспределе­
нием потока заявок 35

3.2.4. Формирование потоков заявок ВС 37
ЛИТЕРАТУРА 40

- 4 -В В Е Д Е Н И Е

Имитационное моделирование - это процесс конструирования мо­дели реальной системы и постановки экспериментов на этой модели с целью либо понять поведение системы, либо оценить различие стратегии управления, обеспечивающие функционирование системы в заданных границах [6].

Реализация имитационных моделей на ЭВМ производится в насто ящее время, как правило, с помощью общецелевых или специализированных языков моделирования. К общецелевым языкам моделирования относится язык GPSS, ориентированный на исследование систем массового обслуживания (СМО). GPSS является самым распространенным в мире языком моделирования (уступает лишь СИМУЛе) [7].

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

Имитационная модель позволяет воспроизвести обслуживание в системе множества задач при любых заданных статистических сведениях о входных потоках и ресурсах ВС.

1. ОСНОВНЫЕ СВЕДЕНИЯ О СИСТЕМЕ МОДЕЛИРОВАНИЯ 1.1. Модели массового обслуживания

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

Системы массового обслуживания делятся на одноканальные - с одним обслуживающим прибором (ресурсом) и многоканальные -содержащие несколько обслуживающих приборов (рис 1.1). Для создания СМО необходимо задать:

- распределение длительности интервалов времени между заяв­ками входного потока;

- 5 -

а)

Поток ] Очередь Поток

заданий на обработанных

на обработку ] обработку заданий

+ +

| |обслу-|
|живаю-+ >

" " "" "!щий":
|прибор|
+ +

Дисциплина выбора из очереди
б)
Поток ] Очередь Поток

заданий на обработанных

на обработку ] обработку заданий

+ +

| |обслу-1
|живаю- + >

"" "Т :Т:"щ"ий ::

! !! [прибор1] |
]! + +!

Дисциплина выбора! + + !

из очереди ] [обслу-]] +-1живаю- +-|

!! щий !!

| |npn6op2j ]

+ + ]

] + +!

| |обслу-1 |

+-1живаю- +-+

|щий ]

jnpn6opNj
+ +

Рис. 1.1. Системы массового обслуживания: а) одноканальная; б) многоканальная

- 6 -

• число обслуживающих приборов;

• распределение длительности обслуживания заявок обслуживаю­щими приборами;

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

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

Очевидно, что поскольку как минимум один из параметров моде­ли имеет вероятностный характер, то и характеристики СМО также будут вероятностными. То есть могут быть представлены как минимум на двух уровнях: статистического ряда и среднего значения. Обычно для характеристики типа СМО используют обозначение вида X/Y/k, где первый параметр обозначает закон распределения времени между поступлением заявок, второй параметр - закон распределения длительности обслуживания заявок и третий параметр - число обслуживающих приборов. При задании законов распределения традиционно М обозначает экспоненциальный, а G - произвольный закон распределения. Кроме экспоненциального и произвольного законов распределения могут применяться эрланговский, нормальный и другие законы.

В теории массового обслуживания СМО могут объединяться путем передачи заявок с выходов одних на входы других СМО, образуя таким образом сети массового обслуживания. Для задания сети массового обслуживания требуется определить все входящие в нее СМО, а также определить конфигурацию связей систем и вероятности передачи заявок между ними. Естественно, что сумма вероятностей передачи заявок из любой СМО должна равняться 1.

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

- 7 -
+ +

! СМО4 j
+ +

входной поток j j
заявок + + + +

; СМО1 +-—| | выходной поток

+ + | СМОЗ j + +заявок

+ + ; +.—; СМО5 +-—

j СМО2 +-—j j + +

+ + + +

Рис. 1.2. Сеть массового обслуживания

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

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

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

1.2. Назначение и состав системы моделирования

Общецелевая система моделирования GPSS (GENERAL PURPOSE

SIMULATING SYSTEM) предназначена для построения имитационных моделей дискретных сложных систем различной физической природы.

В состав системы GPSS входят: язык моделирования GPSS; ин­терпретатор.

- 8 -

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

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

Объекты языка GPSS могут быть разделены на четыре класса: (1) динамические, (2) статические или оборудование, (3) статисти­ческие, (4) операционные.

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

Статические объекты служат для описания аппаратных средств
системы, моделируемой на GPSS. К ним относятся:
одноканальные устройства, многоканальные устройства

(накопители или память).

Одноканальное устройство может обслуживать только один транзакт.Накопитель может обслуживать одновременно несколько транзактов. Статистические объекты (очереди и таблицы) служат для оценки поведения моделируемой системы. В очереди хранится перечень транзактов, задержанных в каком-либо месте исследуемой системы и длительности этих задержек. Таблицы, в основном, предназначены для использования при построении статистических распределений выбранных для анализа величин.

Операционные объекты задают логику работы модели и определяют пути следования и действия транзактов.

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

Развитие любой реальной системы происходит во времени. В от-

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

В GPSS-моделях транзакт в любой момент времени может нахо­дится в одном из пяти списков.

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

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

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

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

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

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

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