GPSS язык и система моделирования систем
Кто ищет, тому назначено блуждать.
В. Гете
Существует множество систем, процессы функционирования в которых могут быть представлены моделями информационных потоков, получившими название систем массового обслуживания (СМО). Это прежде всего процессы в технических системах - телефония, радиосвязь и телекоммуникации, вычислительные машины, системы и вычислительные сети. При их анализе наиболее важно определить скорость передачи или обработки информации, оценить пропускную способность, загрузку оборудования и т. д. При анализе транспортных систем важнейшими задачами являются определение скорости и объема перевозок, сокращение простоев и др. Процессы жизнедеятельности в биологических системах требуют прежде всего определения благоприятных условий жизни, размножения и развития отдельных особей или популяции (колонии, сообщества) в целом. Многие процессы деятельности человека (социальные, экономические, экологические) могут быть представлены моделями типа СМО. И даже обучение, представляемое как усваивание знаний и забывание, также может быть описано такими моделями.
Любая подобная система неизбежно испытывает различного рода возмущения, источниками которых могут быть либо внешние воздействия, обусловленные случайными или систематическими изменениями окружающих условий, либо внутренние флюктуации, возникающие в самой системе в результате взаимодействия элементов. При исследовании эти системы представляются в виде стохастических моделей дискретных процессов (СМДП). Несмотря на успешное развитие и применение методов аналитического моделирования СМДП, основным методом исследования таких систем остается имитационное моделирование на ЭВМ с применением специализированных языков программирования.
За всю историю развития вычислительной техники было создано более 300 языков моделирования дискретных процессов. Одним из первых языков описания СМДП, появившихся в начале 60-х годов, был язык блок-диаграмм, предложенный Гордоном, идеи которого оказались настолько плодотворны, что использовались во многих последующих разработках в нашей стране и за рубежом. На основе языка блок-диаграмм в 70-х годах был создан и в последующем адаптирован к ПК широко используемый в настоящее время для моделирования большого класса систем язык и система моделирования GPSS (General Purpose Simulation System - Система моделирования общего назначения).
КОНЦЕПЦИИ ЯЗЫКА И СИСТЕМЫ GPSS.
1. GPSS -язык блок-диаграмм.
Описание системы на GPSS представляет собой последовательность блоков, каждый из которых соответствует некоторому оператору (подпрограмме). Каждый блок имеет определенное количество реквизитов, называемых полями, которые отделяются друг от друга запятой (это аналоги параметров процедур и функций в языках программирования), но положение полей строго фиксировано, и отсутствие некоторого поля отмечается запятой.
2. Статические объекты, имитирующие средства обработки.
Это устройства накопления - память, очередь, переключения - логические ключи. Каждому объекту соответствует набор блоков, определяющих действия с объектом. Например:
- занятие (по правилу FIFO или с относительным приоритетом) и освобождение устройства CPU:
SEIZE CPU ... RELEASE CPU
- поступление в очередь и удаление из очереди Q1:
ENTER Q1 ... LEAVE Q1
- включение, выключение и переключение ключа KL5:
LOGIC_S KL5...LOGIC_R KL5...LOGIC_I KL5
3. Транзакт -динамический объект модели.
Процесс моделирования состоит в порождении, удалении из модели и в продвижении от блока к блоку модели по определенным правилам (см. ниже) так называемых транзактов, которые представляют собой совокупность ряда числовых и/или логических характеристик, определяющих, например, задачу в ЭВМ, запрос на обслуживание в ЭВМ или ВС, автомобиль в транспортной сети и т. д.
Порождение транзактов происходит в блоке
GENERATE A, B, C, D, E, F, G где поля означают:
A - среднее значение интервала времени создания транзакта;
B - отклонение от среднего, задающее интервал (AB, A+B) равновероятного распределения времени появления транзакта;
C - время появления первого транзакта (фаза смещения);
D - общее число генерируемых транзактов;
E - уровень приоритета транзакта (0 - минимальный, 127 - максимальный);
F - число параметров, назначаемых транзакту (по умолчанию 12);
G - тип параметров транзакта
(F - полнословный, H - полусловный). Удаление транзакта из модели происходит при поступлении его в блок
TERMINATE Ат где Ат - поле, содержащее число, вычитаемое из счетчика завершений As оператора START As: процесс моделирования прекращается, если As Ј 0.
4. Событийное моделирование.
Оно реализуется следующим образом.
- Организация модельного времени. Одним из базовых понятий в СМО является событие, определяемое как изменение состояния системы. Моделирование системы на GPSS, по существу, представляет собой имитацию последовательности переходов системы из одного состояния в другое в некоторые моменты времени, поэтому важнейшим является организация моделирования во времени. Время в GPSS-модели отображается в условных единицах (целыми числами), масштаб которых устанавливается исследователем. Приращение модельного времени на каждом шаге моделирования - величина случайная, равная интервалу времени между последовательными событиями.
- Обработка списков транзактов. Для имитации процессов, протекающих в моделируемой системе, в GPSS предусмотрены следующие механизмы:
- все транзакты, порождаемые в процессе моделирования, образуют списки, в которых транзакты отсортированы, во-первых, по времени, во-вторых, при равных временах у транзактов, по приоритетам;
- в процессе моделирования может быть образовано до пяти списков: список текущих событий содержит транзакты, которые должны перемещаться в текущий момент модельного времени; все они имеют одинаковое время, равное текущему, и если их приоритеты совпадают, то очередной транзакт для перемещения выбирается по правилу FIFO; список будущих событий содержит транзакты, которые будут перемещаться по модели в будущие моменты времени; в этот список попадают транзакты, вошедшие в блоки имитации задержки или заблокированные по каким-либо условиям (типа светофора или "пробки" для автомобиля); списки прерываний, синхронизации и пользователя содержат транзакты, обслуживание которых прервано по некоторым условиям, задаваемым блоками прерывания, синхронизации или находящимся под управлением пользователя.
- Алгоритм событийного моделирования состоит в фомировании, просмотре и изменении этих списков, в перемещении транзактов из одного списка в другой и в продвижении одного из транзактов (активного, находящегося на вершине списка текущих событий) по блокам модели.
Продвижение текущего транзакта продолжается по блокам модели до тех пор, пока не произойдет одно из следующих событий:
- транзакт входит в блок задержки ADVANCE A,B, в котором время транзакта увеличивается на значение, определяемое полями A и B так же, как и в блоке GENERATE, и транзакт переходит в список будущих событий;
- транзакт входит в один из блоков проверки условий типа if...then...else (GATE_R A, B или TEST_T A, B), и условие не позволяет транзакту перемещаться дальше (наступает условие блокировки), тогда транзакт переводится в список будущих событий;
- транзакт входит в блок удаления TERMINATE.
Затем выбирается из списка текущих событий следующий транзакт и начинается его продвижение по модели. Если становится невозможным продвижение всех транзактов из списка текущих событий, то изменяется текущий момент времени (т. е. наступает время следующего события или группы событий) и все сказанное выше повторяется.
5. Моделирование и синхронизация параллельных процессов
обеспечивается как механизмами и средствами продвижения транзактов по модели, так и дополнительными средствами размножения и синхронизации во времени:
1) программа моделирования может состоять из нескольких сегментов, в каждом из которых транзакты порождаются и перемещаются независимо от других сегментов;
2) существует блок копирования (размножения) семейства транзактов SPLIT A, B, C, D (где A - количество копий транзакта; B - блок, в который переходят копии транзактов; С - параметр, в котором хранятся номера копий транзактов; D - количество параметров, задаваемых копиям транзактов) с последующим перемещением их по ветвям модели и сборкой либо в блоке GATHER Ag (Ag - количество собираемых копий) с последующим перемещением по правилу FIFO, либо в блоке ASSEMBLE Aa c объединением Aa-транзактов в один транзакт для последующего его продвижения;
3) существуют блоки синхронизации перемещения транзактов по модели MATCH A (здесь A - имя блока, сопряженного с данным), и поступивший в него транзакт продолжит перемещаться только при условии поступления некоего другого транзакта в сопряженный блок.
6. Изменение последовательного перемещения транзакта по модели.
Оно может быть нарушено оператором блока TRANSFER, определяющим для данного транзакта номер следующего блока.
В GPSS предусмотрен сбор и обработка типовых статистических данных по каждому объекту (максимальная и средняя длина очереди, коэффициент загрузки устройства, памяти, среднее время обработки в устройстве и ожидания в очереди и dp.), а также дополнительной статистики, заложенной программистом в модели. Процесс имитации функционирования системы во времени (динамика процесса функционирования) может быть представлен и в графическом виде, что особенно эффективно для учебных целей.
Далее рассмотрим примеры моделей, иллюстрирующие некоторые из перечисленных возможностей SPSS. Приведенные модели не могут быть исследованы аналитическими методами.
Пример 1. Модель однопроцессорной вычислительной системы, управляющей технологическим процессом и решающей также текущие (фоновые) задачи. Предполагается, что показания датчиков имеют более высокий приоритет относительно фоновых задач, а некоторые сигналы, поступающие с датчиков, требуют немедленной обработки, т. е. характеризуются абсолютным приоритетом. В модели входные запросы имитируются тремя группами случайных последовательностей (например, имеющих пуассоновское распределение с интенсивностями 1/Т1, 1/Т2, 1/Т3): без приоритетов (фоновые), с относительным и с абсолютным приоритетом. Время обработки запроса в CPU - случайная величина, распределенная, например, по экспоненциальному закону с математическим ожиданием Trun. Схема модели представлена на рис. 1. Приведем текстовое описание модели, в котором объявление CPU, очередей Q1, Q2, Q3 и функции EXP, а также задание значений Т1, Т2, Т3, Trun опущены.
Рис.1. Модель однопроцессорной ВС с относительным и
абсолютным приоритетами
SIMULATE
* Сегмент 1:
GENERATE T1, FN$EXP ; генерация запросов первого типа
QUEUE Q1 ; постановка запроса в очередь Q1
SEIZE CPU ; занятие CPU
DEPART Q1 ; выход из очереди Q1
ADVANCE Trun,FN$EXP ; обработка запроса в CPU
RELEASE CPU ; освобождение CPU
TERMINATE ; удаление запроса из системы
* Сегмент 2:
GENERATE T2, FN$EXP
QUEUE Q2
SEIZE CPU
DEPART Q2
ADVANCE Trun, FN$EXP
RELEASE CPU
* Сегмент 3:
GENERATE T3, FN$EXP
QUEUE Q3
PROMPT CPU ; захват CPU c прерыванием предыдущего запроса
DEPART Q3
ADVANCE Trun, FN$EXP
RETURN ; освобождение CPU с дообработкой прерванного запроса
* Сегмент 4:
GENERATE 20000 ; сегмент, определяющий продолжительность моделирования
TERMINATE 1 ; в 20 000 единиц времени
* START 1
END
Пример 2. Модель компьютерного класса (рис. 2), содержащего не более N ПК. Каждый ПК находится в рабочем состоянии в течение некоторого случайного интервала времени, распределенного по некоторому произвольному закону, задаваемому в модели функцией F1 (математическое ожидание времени наработки на отказ Tnro). Ремонт выполняется К бригадами. Время ремонта ПК - случайная величина с некоторым распределением, задаваемым функцией F2. Цель моделирования - найти оптимальное число бригад, обеспечивающих при заданных характеристиках надежности и количества ПК в классе приемлемые условия работы класса ПК.
Рис.2. Модель работы класса ПК при отказах и ремонте
Модель имеет следующие особенности:
- работа класса и бригад имитируется с помощью объекта типа память, которая здесь используется как многоканальное устройство обработки;
- это модель замкнутого типа, т. е. количество транзактов в модели NT і N, создаваемое в начале моделирования, остается постоянным и только распределяется между классом, ремонтными бригадами и очередями на подготовку ПК к работе Q1 и в ремонт Q2. Объявление объектов KLASS, Q1,Q2 и функций F1,F2, а также задание конкретных значений Tnro,Trem опущены.
Приведем текстовое описание модели.
SIMULATE
GENERATE ; генерация NT-транзактов
MET1 QUEUE Q1 ; подготовка к работе или ожидание ПК в резерве
ENTER KLASS ; включение ПК в работу в классе
DEPART Q1
ADVANCE Tnro, FN$F1
LEAVE KLASS ; удаление ПК из класса из-за неисправности
QUEUE Q2 ; постановка в очередь на ремонт
ENTER REM ; начало ремонта
DEPART Q2
ADVANCE Trem, FN$F2
LEAVE REM ; завершение ремонта
TRANSFER , MET1 ; безусловный переход к очереди Q1
*
GENERATE 50000 ; сегмент, определяющий длительность
TERMINATE 1 ; моделирования в 50 000 единиц времени
START 1
END
Результаты моделирования здесь не приводятся, так как они зависят от численных значений исходных данных, задаваемых при решении конкретной задачи. При этом следует иметь в виду, что при исследовании таких моделей на ЭВМ возникает ряд проблем, связанных с организацией оптимального планирования эксперимента с моделями. Обсуждение этих проблем выходит за рамки настоящего сообщения.
Кажущаяся простота приведенных моделей обусловлена тем, что каждый блок представляет собой, по существу, имя процедуры с параметрами, а содержательная часть процедуры скрыта в алгоритме моделирования. В этом состоит одно из достоинств всякого проблемно-ориентированного языка, в том числе и GPSS.
Александр Дорошенко
