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

Егоров Е.А.

ИМИТАЦИОННОЕ МОДЕЛИРОВАНИЕ


Аналитические модели (АМ) - предполагают наличие математичес-

кого описания процессов, протекающих в оригинале. Обычно строятся при

жесткий ограничениях на параметры оригинала и внешней среды.

АМ позволяют получать зависимость Pi = f(ALFA1,..,ALFAn).

Пример. Модели массового обслуживания в основном строятся в предполо-

жении простейших потоков событий.

Имитационные модели (ИМ) - являются более универсальными и

могут быть построены при отсутствии математической модели оригинала.

Идея имитационного моделирования очень проста, заключается в том, что

строится некий алгоритм поведения подсистем и отдельных элементов сис-

тем во времени. При анализе производительности интересно только состо-

яние подсистем (работает / не работает). Этот алгоритм может быть реа-

лизован в виде программы для ЭВМ. Многократно "прогоняя" ИМ в условиях

случайных потоков событий на входе и в самой системе, можно накопить

статистическую информацию об изменении существенных переменных состоя-

ния ИМ. Статистическая обработка этой информации позволяет получить

статистические оценки показателей эффективности. В отличие от АМ, ИМ

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

щей от объема выборки и, соответственно, от времени наблюдения за ИМ.


Пример. MU

+--------+ o

LA --->|ЦП - ОП |---> LA Оригинал - однопроцессорная система опе-

| +--------+ п ративной обработки без буферирования за-

----------------> LA просов.


Аналитическая модель. Имитационная модель.


+--+ LA +--+ o^ C1 C2

|S0|----->|S1| п| ^ C3^ ^

+--+<-----+--+ Вых. поток +----+---+-+---

MU ^ +--+ +--+

| |C1| |C2|

1 ЦП - ОП +-+--+--+--+---

P0 = ----; ^

1+RO |

RO Вх. поток +--------------

Р1 = RO * Р0 = ----; ^ ^^

1+RO | ||

C1 C2C3


^ 3.1. ОСНОВНЫЕ ПОНЯТИЯ ИМИТАЦИОННОГО МОДЕЛИРОВАНИЯ.


ИМ строится в том случае, если нет математического описания

процессов, протекающих в исследуемом объекте. Суть имитационного

моделирования:

- воспроизведение с необходимой достоверностью поведения отдель-

ных элементов системы в процессе реализации ею функции системы;

- накопление статистических данных о поведении элементов;

- последующая статистическая обработка этих данных для

получения статистических оценок количественных характеристик

законов распределения оцениваемых показателей эффективности.

ВС - сложная система со стохастическим поведением. Возможны

различные аспекты анализа поведения ВС:

- при анализе производительности случайным является поток

запросов на обслуживание, случайна также трудоемкость запроса,

определяемая числом операций, которые необходимы для выполнения

программы, обрабатывающей запрос пользователя;

- при анализе надежности случайны процессы отказов элементов

ВС (процесс деградации ВС), случайны также интервалы времени, необ-

ходимого для ремонта отказавших элементов (процессы восстановления).


Уровни моделирования:

- системное моделирование - моделирование на уровне системы

(анализ производительности отдельных элементов и системы в целом);

- моделирование на уровне архитектуры (анализ эффективности

системы команд, точностной анализ);

- моделирование на уровне регистровых передач (анализ коррект-

ности микропрограмм операций);

- логическое моделирование - моделирование на уровне логических

схем (анализ корректности ЛС, выявление критических состояний,

вызванных задержками ЛЭ (статический риск, динамический риск)).

- схемо-техническое моделирование - моделирование на уровне прин-

ципиальных схем логических элементов с учетом топологии и конкретной

технологии производства БИС, СБИС, ССБИС,....


Основное внимание в курсе уделено системному моделированию, при

котором исследуется такой важный показатель эффективности как

производительность. Введем ряд понятий ИМ системного уровня.

+ +

Производительность---| работа | индексы

| |--------| производительности

| | время |

| + +

+--- время индекс

реактивности


Активность - элементарная работа, рассматриваемая в рамках

данной ИМ, как неделимая.

Процесс - логически связанная некоторой функцией

последовательность активностей.

Событие - факт начала или завершения некоторой активности. По-

нятие активности и процесса взаимосвязаны. Переходя с одного уровня

детализации на другой, можно рассматривать активность как процесс

более низкого уровня и, напротив, рассматривать процесс как актив-

ность более высокого уровня.


Уровень ОС


Процесс- A1 A2 A3 A1 - инициация задания

задание -+----+----+----+----+--> A2 - исполнение

/ \ A3 - завершение

/ \

/ \

/ \

Процесс- /A21 A22 A23 \ A21 - акт-сть счета (ЦП, ОП)

программа -+----+----+----+----+--> A22 - обмен (ОП <-> диск)

ЦП / \ A23 - счет ЦП - ОП

/ \

/ \

Процесс- /A221 A222 A223\ A221 - позиционирование

программа -+----+----+----+----+--> A222 - ожидание зоны

обмена A223 - обмен данными


ИМ системного уровня предполагает описание функционирования

системы в терминах активности, событий или процессов на некотором

языке программирования. В принципе модель может быть построена на

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

соответственно время разработки модели возрастают по мере специали-

зации языка. Часто специализация обеспечивается расширением универ-

сального языка высокого уровня (FORTRAN, PASCAL, C) специальными

операторами. Существует много специальных языков моделирования, час-

то имеющих проблемную ориентацию. Языки моделирования относят к раз-

личным группам в зависимости от основных объектов языка:

- языки, ориентированные на активности,

- языки, ориентированные на события,

- языки, ориентированные на процессы.


Общая проблема реализации языков моделирования различных типов:

Необходимость реализации в ИМ параллелизма, характерного для

сложных ВС. В системах с мультипрограммным режимом обработки может

развиваться параллельно несколько процессов, связанных с различными

заданиями. ОС реализует алгоритмы диспетчеризации, т.е. управления

вычислительным процессом и распределения ресурсов между конкурирую-

щими процессами т.о., чтобы обеспечить наилучшее качество функциони-

рования (для систем с диалоговым режимом обработки цель - минимиза-

ция времени обработки, для систем с пакетным режимом обработки -

максимизация загрузка оборудования).

Проблема псевдопараллелизма вызвана тем, что реально параллель-

ные процессы в оригинале необходимо имитировать на инструментальной

ЭВМ, которая может реализовать лишь последовательные процессы (расс-

матриваются однопроцессорные ЭВМ). Для реализации псевдопараллелизма

надо определенным образом организовать последовательное выполнение

процедур, относящихся к различным активностям, процессам или событи-

ям, протекающим параллельно во времени.


Время в ИМ


Физическое tф, реальное tр - время в объекте моделирования.

Модельное tм - системное время.

Инструментальное tи - в инструментальной ЭВМ, на которой

реализуется ИМ.

tф - непрерывное время.

tм - дискретное время(иногда удобно рассматривать его как без-

размерное: tм = 0, 1, 2, 3, 4, ...).


Масштаб времени.


^ tм

4| tф

| | Mt = ----

3| +---+ tм

| |

2| +---+ Mt = 1 - реальное время

| | Mt > 1 - ускоренное время

1| +---+ DELTAt Mt < 1 - замедленное время

| | |<->| DELTAt - шаг квантования

0+---+---+---+---+----

1 2 3 4 tф


Соотношения между tи и tм определяется степенью детализации

процессов и характеристиками инструментальной ЭВМ.

Рассмотрим взаимосвязь трех видов времени. Пусть в исследуемой

системе наступают события трех типов. Каждому из событий в ИМ

будут соответствовать определенные процедуры, требующие выполнения

на инструментальной ЭВМ соответствующих программ.


А1 А2 А3 А4 Приоритеты

+-+---+-----+---+------- tф

| B > C > A

| b1 b2 b3 b4

+----+----+---+---+----- tф Квантование приводит к тому, что

| события, происходящие в разные

| c1 c2 c3 c4 моменты физического времени, могут

+--+----+--+-----+------ tф быть отнесены к одному моменту мо-

| a1 a2 b2 a3 b4 дельного времени. Последователь-

| c1 b1 c2 c3 b3 a4 c4 ность обработки этих событий в ин-

+--+--+--+--+--+--+--+-- tм струментальном времени определя-

| |c1 3 4 5 6 7 ется приоритетами событий.

| |a1

| |b1

| |a2

| |c2

| |b2

| |c3

|tи

V

Проблема псевдопараллелизма.


Решение этой проблемы связано с реализацией системы модельного

(системного) времени TIME (системных часов).

Известна реализация системы времени по методу "DELTA t", в кото-

рой системные часы получают приращение с постоянным шагом DELTAt,

причем для каждого нового значения TIME выполняется проверка на на-

личие событий из множества возможных событий {E1, E2, ..., En}, от-

носящихся к данному моменту времени. Часы останавливаются по условию

TIME > TLIM, где TLIM - длина интервала моделирования.


+------+

|начало|

+---+--+

+----------+-----------+

| TIME:=0; |

+----------+-----------+

+------------------------>|

| /\

| /TIME\ Да

| / > \-----------------------+

| \ TLIM / |

| \ / +---------+--------+

| \/ |обработка(статис.)|

| | Нет | формирование про-|

| +------+------+ | токола испытаний |

| | i = 1 | +---------+--------+

| +------+------+ |

| +----------------->| +---+---+

| | /\ | конец |

| | / \ +-------+

| | / P(Ei) \

| | \ /

| | \ /

| | \/

| | +----------+---------+

| | +----+----+ +----+----+

| | |процедура| |процедура|

| | | E1 | | En |

| | +----+----+ +----+----+

| | +----------+---------+

| | +---------------+-----------------+

| | |планирование событий, логически|

| | |следующих за реализуемым событием|

| | | ПС(E, атрибуты события, DELTAt) |

| | +---------------+-----------------+

| | +------+------+

| | | i = 1 |

| | +------+------+

| | /\

| | Да / \

| +------------ / i <= n \

| \ /

| \ /

| \/

| +----------+---------+

| |TIME = TIME + DELTAt|

| +----------+---------+

+-------------------------+


Этот механизм прост в реализации, но не эффективен из-за того,

что приходится выполнять проверки, результаты которых с большой ве-

роятностью отрицательны. Причем эта вероятность тем больше, чем

меньше квант DELTAt.

Псевдопараллелизм в большинстве используемых систем моделирова-

ния решается с помощью планирования событий, по так называемому ме-

тоду "DELTA Z". Для этого в системах моделирования формируется спи-

сок (календарь) событий. Обычно - односвязный список событий из мно-

жества возможных событий {E1, E2, ..., En}, , упорядоченных по вре-

мени.

+--+----------------+-+-+

Календарь событий (КС) |Ei|атрибуты события|T|.|

Т - время наступления +--+----------------+-+++

события. +-------------------------+

В голове списка должен быть | +--+----------------+-+-+

элемент с миниимальным | |Ej|атрибуты события|T| |

Т, содержащий сведения | +--+----------------+-+-+

о ближайшем по времени | ^

событии. | +---------------------+

| +--+----------------+-+++

+->|Ek|атрибуты события|T|.|

+--+----------------+-+-+


Операции над КС.


1. Планирование будущего события. Реализуется процедурой

ПС {E,атрибуты события, DELTAt (приращение t)}

с параметрами:

Е - номер планируемого события;

DELTAt - время, через которое должно наступить планируемое собы-

тие по отнощению к текущему времени TIME.


TIME T TIME -текущее время

--+-----+--- T - планируемый момент наступления

|<--->| события.

DELTAt

2. Удаление из списка ближайшего события. Реализуется процедурой

УБС{E, атрибуты события, Т}

которая возвращает в вызывающую программу параметры:

E - номер ближайшего события;

T - время наступления ближайшего события.

Организация псевдопараллелизма по методу "DELTA Z" представляет-

ся следующим алгоритмом.


+------+

|начало|

+---+--+

+------------+-------------+

| TIME = 0; планирование |

| начального события |

| ПС(E1,атрибуты Е1,DELTAt)|

+------------+-------------+

+-------------------->|

| +------------+-------------+

| | удаление ближайшего |

| | события |

| | УБС(E,атрибуты E,T) |

| +------------+-------------+

| /\

| /TIME\ Да

| / > \-----------------+

| \ TLIM / |

| \ / +---------+--------+

| \/ |обработка(статис.)|

| | Нет | формирование про-|

| | | токола испытаний |

| +------+------+ +---------+--------+

| | TIME := T | |

| +------+------+ +---+---+

| | | конец |

| /\ +-------+

| / \

| / E \

| \ /

| \ /

| \/

| +----------+---------+

| +----+----+ +----+----+

| |процедура| |процедура|

| | E1 | | En |

| +----+----+ +----+----+

| +----------+---------+

| +---------------+-----------------+

| |планирование событий, логически|

| |следующих за реализуемым событием|

| | ПС(E, атрибуты события, DELTAt) |

| +---------------+-----------------+

+---------------------+

Приведенная БСА соответствует переводу часов в дискретные

моменты времени, соответствующие возможным событиям в системе.

Достоинством этого метода является более эффективное использование

ресурсов инструментальной ЭВМ.


Основные этапы ИМ.


+->1. Постановка задачи.

|+>2. Формирование и построение концептуальной модели

|| (КМ). На этом этапе должны быть приняты

|| принципиальные решения об ограничениях,

|| принимаемых для построения моделей ОМ

|| (объект моделирования). При исследовании

|| производительности ВС концептуальной моделью

|| является обычно СМО. Для формализации может быть

|| применен язык Q-схем или схем с очередями.

||

|| Объекты: источники заявок +-+

|| |И|--->

|| +-+ LA

|| каналы обслуживания +-+

|| --->|K|--->

|| +-+ MU

|| очереди (накопители) +-----+

|| --->|||||||---

|| +-----+n=const

||

|| с бесконечным числом мест n: -----+ n=бесконеч-

|| ---> ||||||---

|| -----+ ность

||

||>3. Выбор языка ИМ и построение модели.

|+-4. Тестирование ИМ.

+->5. Планирование эксперимента.

| Цель: построить план эксперимента,

| обеспечивающий получение максимальной информации

| об объекте с минимальными затратами ресурсов

| инструментальной ЭВМ.

+->6. Модельный эксперимент.

| (накопление и статистическая обработка

| результатов моделирования).

+--7. Интерпретация результатов модельного

эксперимента.


3.2. Основные сведение о языке ИМ GPSS

(General Purpose System Simulator).


Язык разработан в 1961 году фирмой IBM вслед за разработкой

компилятора с языка ФОРТРАН. Представляет собой Фортран-ориентиро-

ванную версию языка ИМ. Первые реализации GPSS строились в виде

препроцессора, т. е. выходным текстом программ, анализирующих пред-

ложения GPSS, были тексты на Фортране. Существует много версий GPSS,

являющегося наиболее распространенным языком данного класса. В нас-

тоящее время разработаны полные версии GPSS для ПЭВМ.

GPSS предназначен для моделирования систем с материальными и

информационными потоками. Можно описывать систему и управлять марш-

рутами прохождения через объекты систем специальных динамических

элементов - транзактов (транзакт, транзакция - сообщение). Транзакт

может восприниматься как динамическая единица материального или ин-

формационного потока, способная перемещаться от объекта к объекту и

имитировать последовательность обслуживания, которую получает тран-

закт за время пребывания его в системе.

Все операторы GPSS условно делятся на классы.

- динамические (связанные с транзактами);

- аппаратно-ориентированные - им в исследуемой системе соот-

ветствует устройство, занятое обслуживанием, т. е. выполнением рабо-

ты того или иного свойства (связаны с активностями);

- статистические - реализуют сбор и обработку статистической

информации;

- операционные - предназначены для управления потоками транзак-

тов;

- разные (не связанные определенной функцией).


Общий формат предложений GPSS.


Номер строки___{Метка}___Оператор___Операнды;{Комментарии}

до 10 цифр до 20симво- A, B, C,

лов: цифры,_. D, E


Каждому исполняемому оператору может быть сопоставлен блок со

стандартизованным графическим изображением. Это позволяет на этапе

построения моделей до написания текстов программ построить блок ди-

аграмм, отображающих последовательность продвижения динамических

объектов.


3.2.1. Динамические объекты GPSS. Транзактно-

ориентированные блоки (операторы).


Транзакт - динамический объект, соответствующий заявке на обс-

луживание в СМО.

GPSS располагает средствами для порождения (генерации) транзак-

тов, последовательного продвижения их от объекта к объекту, их за-

держки на время, соответствующее длительности активности, уничтоже-

ние (удаление из системы) транзактов.


Оператор GENERATE

-----------------


Q-схема Блок-диаграмма Оператор Примечание

+-----+

+--+ LA | +--------+ GENERATE_A,B,C,D,E

|ИС+------> |A, B, С, D, E |

+--+ +-----+--------+

V

Оператор GENERATE позволяет описывать входной поток, операнды харак-

теризуют свойства входного потока транзактов. Следует иметь в виду,

что модельное время в GPSS - целое без знака 0, 1, 2, ... Следова-

тельно, все параметры закона распределения случайных интервалов меж-

ду соседними событиями в потоке, имеющие смысл времени, должны быть

с помощью масштаба времени приведены к целому формату.

Если параметры А,В - const, то оператор GENERATE описывает рав-

нономерный закон распределения длины интервала между соседними собы-

тиями в потоке.

1

--- +-------------+ А - среднее (МО) = 1 / LA

2*В | S - площадь | А >= В

0 +------+------+

А-В А А+В S = 2B*h = 1, h = 1 / (2*B)


В - может быть отличен от const и тогда он рассматривается как

модификатор, в этом случае длина интервала определяется как А*В.


С - задержка начала генерации.

D - число генерируемых транзактов (емкость источника).

---------->

Е - приоритет транзактов. Целое без знака 0, 1, 2 ...


Операнды могут быть опущены, тогда по умолчанию:А=В=С=E=0, D=0-0


Пример.


GENERATE_10, 2, 20, , 3 0.25 +-------+

С | |

+------+-------> t ---+---+---+----

0 20 8 10 12

Момент начала генерации A-B А A+B


ПРИМЕЧАНИЕ: Если бы операнд С отсутствовал, первый транзакт появился

бы в момент времени, определяемый операндом А (в нашем примере 10).


Оператор ADVANCE

----------------


Q-схема Блок-диаграмма Оператор Примечания

+---+ |

-->| K |--> V ADVANCE A,B задержка на

+---+ +-------+ случайное время

Активность, | A, B | со средним зна-

имеющая слу- +---+---+ чением А = 1/LA

чайную дли- | и равномерным

тельность V распределением


Оператор TERMINATE

------------------


Q-схема Блок-диаграмма Оператор Примечания


вых. поток | Уничтожение тран-

---------> V закта, входящего

удаление тран- /--\____ TERMINATE [A] в блок TERMINATE

закта из сис- | | A |

темы \--/---+


В общем случае может быть несколько операторов TERMINATE,

хотя обычно только один из них может иметь операнд [A]. В GPSS

реализована простая схема завершения процесса моделирования. В

системе моделирования есть специальная переменная целого типа,

называемая счетчиком завершения. Если в операторе TERMINATE указан

ненулевой операнд, то при каждом входе транзакта в этот блок

счетчик уменьшается на величину операнда. Когда содержимое счетчика

становится =< 0, процесс моделирования завершается. Перед началом

моделирования счетчик должен быть установлен в начальное состояние.

Для этого используются специальные управляющие карты.


Управляющие карты.

-----------------


1. SIMULATE Начинает процесс интерпретации программы на GPSS.

2. START A Заносит в счетчик завершения const = A

3. END Завершение моделирования, выход из системы

моделирования


Рекомендуемые способы выхода из процесса моделирования.


Способ 1. Используется, если известна длина интервала TLIM.

Тогда в тексте выделяется специальная таймерная секция, в

которой создается поток вспомогательных транзактов,

обеспечивающих измерение времени моделирования.


SIMULATE

GENERATE A, B, C, D

....................

ADVANCE A, B

....................

TERMINATE

;таймерная секция

GENERATE ,,TLIM,1 ; Начало генерации в момент времени TLIM

TERMINATE 1 ; A <> 0

START 1

END


Примечание.

Оператор в таймерной секции может быть использован в другой форме:

GENERATE TLIM,,,1 ; Первый транзакт появится в момент времени TLIM


Способ 2. Позволяет завершить моделирование после удаления

из системы определенного числа транзактов N.


SIMULATE

GENERATE A, B, C, D

....................

ADVANCE A, B

....................

TERMINATE 1 ; A <> 0

START N ; N - объем выборки

END


ПРИМЕЧАНИЕ.

В комментариях не используются КИРИЛЛИЦА.


3.2.2. Аппаратно-ориентированные блоки.


Описывают действия по занятию и освобождению ресурсов (каналов

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


Операторы SEIZE и RELEASE

-------------------------


Q-схема Блок-диаграмма Оператор Примечание


-----+ +---+ | Занять канал

||||||==>| K | +-+-+ / \ SEIZE A с номером А,

-----+ +---+ | |/ А \ при занятом

+-+-+----- канале занять

| место в очереди

o

--+ +----+ LA |

||=>| K |==> +-+-+----- RELEASE A Освободить канал

--+ +----+ | |\ А / с номером А, на-

+-+-+ \/ значить на обслу-

| живание транзакт

из головы очереди


С устройством(каналом обслуживания) связано обслуживание опре-

деленного вида или активность.

Особенностью блока SEIZE является то, что транзакт может войти

в этот блок только в том случае, если устройство свободно,

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

образованию на входе устройства очереди с неограниченным числом

мест. В реальной системе моделирования длина очереди ограничена ре-

сурсами, выделяемыми системой моделирования для организации очередей.

Чтобы не было бесконечного возрастания длины очереди, надо

обеспечить выполнение условия, при котором существует

установившийся режим в системе с чистым ожиданием.


RO < 1, RO = LA / MU


Пример.

Построить ИМ для случая, когда концептуальной моделью объекта-

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

моделирования в этом случае может быть однопроцессорная ЭВМ, обраба-

тывающая в оперативном режиме запросы пользователя для случая,

когда область памяти, выделенная для буферизации запросов, настолько

велика, что влиянием ее размера на характеристики системы можно пре-

небречь.


Q-схема Q MU

+---+LA ------+ +---+ o LA = 20с**-1

| И |---> |||||+--->| K +---> LA MU = 40с**-1

+---+ ------+ +---+ RO = LA/MU = 0,5 < 1


Будем считать, что входной поток и поток обслуживания имеют

равномерно-распределенные длины интервалов с 20%-ым отклонением

от средних длин (не простейшие потоки).


Распределение интервалов.


Входящий поток Поток обслуживания

+-------------+ +-------------+

||||||||||||||| |||||||||||||||

---+------+------+---> t ---+------+------+---> t

40мс 50мс 60мс 20мс 25мс 30мс


DELTAt = 1мс

Масштаб Mt = 1*10**-3 с = 1 мс


Блок-диаграмма

+----+ +----+

| +------+ | +------+

|50,10 | |TLIM |

+---+-------+ +--+--------+

V V

+-----+ / \ +-----+-----+

|SEIZE|/ 1 \ | TER | |

+-----+------ +-----+-----+

V Таймерная

+-------+ секция

|ADVANCE|

| 25,5 | N - объем выборки

+-------+ TLIM = N*(1/LA) =

V 1000

+-------+----- = ----------- = 50*10**3

|RELEAZE|\ 1 / 20*10**-3

+-------+ \ /

V

+---+---+

|TER| |

+---+---+


Программа


10 SIMULATE

20 GENERATE 50,10

30 SEIZE 1

40 ADVANCE 25,5

50 RELEASE 1

60 TERMINATE

; Time Section

80 GENERATE 50000

90 TERMINATE 1

100 START 1

110 END


Многофазное обслуживание.

Q1 Q2

+---+ +------+ +---+ +------+ +---+

| И |--->||||||||--->| K1|--->| ||||--->| K2|---> .......

+---+ +------+ +---+ +------+ +---+

Аи Ак1 Ак2

Ви Вк1 Вк2

---------------- -----------------

фаза1 фаза 2


+---+

| +---+ SIMULATE

|Аи, Ви | ; фаза 1

+---+---+ + GENERATE Аи, Ви

+---+---+ / \ | SEIZE 1

| |/ 1 \ | ADVANCE Ак1, Вк1

+---+---+------ |1-я RELEASE 1

+---+---+ | ф ; фаза 2

|Ак1,Вк1| | а SEIZE 2

+---+---+ | з ADVANCE Ак2, Вк2

+---+---+------ | а RELEASE 2

| |\ 1 / | ..............................

+---+---+ \ / | TERMINATE 1

| + START N ; N - объем выборки

| + END

+---+---+ / \ |

| |/ 2 \ |

+---+---+------ |2-я

+---+---+ | ф

|Ак2,Вк2| | а

+---+---+ | з

+---+---+------ | а

| |\ 2 / |

+---+---+ \ / |

. +

V

+---+---+

|TER| 1 |

+---+---+


Моделирование систем с несколькими типами транзактов


Q - схема


Аи1 Ви1 Q

+----+ LA1 -------+ +---+

PR1 | И1 +-----+--->|||||||+---| К |--->

+----+ | -------+ +---+

Аи2 Ви2 | Ак1 Вк1 (MU1)

+----+ LA2 | Aк2 Вк2 (MU2)

PR2 | И2 +-----| Ак3 Вк3 (MU3)

+----+ |

Аи3 Ви3 | Характерная особенность: заявки нескольких

+----+ LA3 | типов претендуют на общий ресурс, для ожи-

PR3 | И3 +-----+ дания освобождения ресурса используется

+----+ общая очередь.


3

RO = SUMMA ROi < 1 условие существования

i = 1 установившегося режима


Дисциплина FIFO

+---+ +---+ +---+

| +---+ | +---+ | +---+

|Aи1,Ви1| |Аи2,Ви2| |Аи3,Ви3|

+---+---+ +---+---+ +---+---+

+---+---+ / \ +---+---+ / \ +---+---+ / \

| SEIZE |/ 1 \ | SEIZE |/ 1 \ | SEIZE |/ 1 \

+---+---+------ +---+---+------ +---+---+------

+---+---+ +---+---+ +---+---+

|Ак1,Вк1| |Ак2,Вк2| |Ак3,Вк3|

+---+---+ +---+---+ +---+---+

+---+---+------ +---+---+------ +---+---+------

|RELEASE|\ 1 / |RELEASE|\ 1 / |RELEASE|\ 1 /

+---+---+ \ / +---+---+ \ / +---+---+ \ /

+---+---+ +---+---+ +---+---+

|TER| | |TER| | |TER| 1 |

+---+---+ +---+---+ +---+---+


Примечание.

1. GPSS позволяет создать независимые процессы для каждого типа

транзактов, автоматически выявляя конфликты на общих ресурсах и об-

разуя очереди к ним.

2. Программа строится в виде последовательности фрагментов, на-

чинающихся оператором GENERATE и завершающихся оператором TERMINATE.


Дисциплина с относительными приоритетами (ОП)


Реализуется с использованием тех же операторов с добавлением в

список операндов GENERATE операнда Е, задающего приоритет. По умол-

чанию дисциплина ожидания организует очередь с учетом PRi. Внутри

каждого приоритета транзакты располагаются в соответствии с дисцип-

линой FIFO. Блок-диаграмма строится аналогично предыдущему случаю,

изменяются лишь операторы GENERATE в каждой из ветвей за счет добав-

ления операнда Е, задающего приоритет соответствующих транзактов

(PR1/2/3).


SIMULATE

; секция транзактов 1-го типа

GENERATE Аи1, Ви1, , , PR1

SEIZE 1

ADVANCE Ак1, Вк1

RELEASE 1

ТERMINATE

; секция транзактов 2-го типа

GENERATE Аи2, Ви2, , , PR2

SEIZE 1

ADVANCE Ак2, Вк2

RELEASE 1

ТERMINATE

; секция транзактов 3-го типа

GENERATE Аи3, Ви3, , , PR3

SEIZE 1

ADVANCE Ак3, Вк3

RELEASE 1

ТERMINATE 1

START N3 ; N3 - объем выборки для транзактов 3-го типа

END


Дисциплина с абсолютными приоритетами (АП)


Для реализации этой дисциплины необходимы специальные операторы.


Операторы PREEMPT, RETURN

--------------------------


Q-схема Прер. Блок-диаграмма Оператор Примечание

Q |

-----+ +---+ | /\ Захватить (за-

||||||==>| K | +-+-+ //\\ PREEMPTE A,[PR] нять с прерыва-

-----+ +---+ | |//A \\ нием) канал с

+-+-+----- номером А, иначе

Прер. | занять место в Q

Q | o

--+ +----+ LA | Снять прерывание с

||=>| K |==> +-+-+----- RETURN A канала А, назна-

--+ +----+ | |\\A // чить на обслужива-

+-+-+ \\// ние транзакт из

| \/ головы очереди


Если в операторе PREEMPT не указывается второй операнд (сим-

вольная константа PR), то реализуется одноуровневое прерывание, т.

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

транзактом. Если указан операнд PR, то разрешается прерывание, если

устройство захвачено транзактом с более низким приоритетом. Для

транзактов с наименьшим приоритетом должны быть использованы опера-

торы SEIZE и RELEASE.


SIMULATE

; секция транзактов 1-го типа

GENERATE Аи1, Ви1, , , PR1

PREEMPT 1, PR

ADVANCE Ак1, Вк1

RETURN 1

ТERMINATE

; секция транзактов 2-го типа

GENERATE Аи2, Ви2, , , PR2

PREEMPT 1, PR

ADVANCE Ак2, Вк2

RETURN 1

ТERMINATE

; секция транзактов 3-го типа

GENERATE Аи3, Ви3, , , PR3

SEIZE 1

ADVANCE Ак3, Вк3

RELEASE 1

ТERMINATE 1

START N3 ; N3 - объем транзактов 3-го типа; PR1, PR2 > PR3

END


Многоканальное обслуживание


Для моделирования многоканального обслуживания в GPSS использу-

ются специальные объекты, называемые накопителями.

Накопители (многоканальные устройства) в отличие от устройства

(канала обслуживания) позволяют моделировать сложный ресурс, который

может выделяться частями, причем отдельными частями накопителя (ка-

налами) может одновременно обслуживаться несколько транзактов.


Операторы ENTER, LEAVE, STORAGE

-------------------------------


Q-схема A Блок-диаграмма Оператор Примечание

Q +----+

-----+ | К1 | | Войти в накопи-

||||||==>|....| +-+-+ _ ENTER A,B тель с именем

-----+ | Кm | | В |/ A \ A, заняв В единиц

+----+ +-+-+----- ресурса, иначе

A | занять место в Q

Q +----+ o

--+ | K1 | LA | Выйти из накопителя с

||=>|....|==> +-+-+----- LEAVE A,B именем А, освободить

--+ | Km | | В |\ A / В единиц ресурса, на-

+----+ +-+-+ _ значить транзакт из

| головы очереди

А - имя (номер) накопителя (памяти)

В - число единиц ресурса, занимаемых при входе в накопитель и

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

ПРИМЕЧАНИЕ. По умолчанию В = 1.


Для определения накопителя используется оператор STORAGE:

NAME STORAGE A

где NAME - имя накопителя, указываемое в поле метки

A - емкость накопителя.

Смысл единицы емкости определяется тем, что моделирует, в дан-

ном конкретном случае, накопитель. Если моделируется многоканальное

устройство обслуживания, то единица емкости - 1 канал. Если накопи-

тель моделирует очередь с конечным числом мест, то единице емкости

соответствует 1 место в очереди. Можно моделировать такой разделяемый

ресурс ВС, как основная память (ОП) или внешняя память. Емкость памяти -

Кбайт, Мбайт, ... Единице емкости накопителя в этом случае можно со-

поставить размер кванта памяти, выделяемой операционной системой

конкретному заданию.


Пример.

------

QUE_1 STORAGE 10

Оператор описывает накопитель с емкостью 10, моделируюший оче-

редь с ограниченным числом мест, равным 10.


Пример.

------

Необходимо разработать имитационную модель многопроцессорной ВС

с "чистым" ожиданием, которая предполагает, что для хранения

запросов, которые не могут быть назначены на обслуживание из-за

отсутствия свободного процессора, выделена память настолько

большого объема, что увеличение ее размера не будет сказываться на

характеристиках производительности системы.

Накопитель

------------------

Q - схема многока- | +----+ MU |

нальной СМО с | +---| К1 +---+ |

"чистым" ожиданием | | +----+ | |

| | +----+ MU| |

Q | +---| К2 +---| |

+---+ LA ----------+ | | +----+ | | o

| И +-----> |||||||||+-|-| +-|- LA

+---+ ----------+ | | | |

| | +----+ MU| |

| +---| Кm +---+ |

| +----+ |

------------------

Каналу обслуживания Ki соответствует процессор Пpi, каждый запрос

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


SIMULATE

S_K STORAGE m

GENERATE Аи, Ви

ENTER S_K, 1

ADVANCE Ак, Вк

LEAVE S_K, 1

ТERMINATE 1

START N

END


Рассмотренные операторы аппаратной категории SEIZE,

RELEASE, PREEMPT, RETURN, ENTER, LEAVE автоматически собирают

статистику о прохождении транзактов через устройства (1 - 4) или

накопители (5, 6). Подсчитывается число транзактов, измеряется

время их пребывания в аппаратно-ориентированных блоках, что поз-

воляет по завершении моделирования обработать накопленный статис-

тический материал и создать протокол испытаний, содержащий количе-

ственные характеристики законов распределения показателей эффек-

тивности.


3.2.3. СТАТИСТИЧЕСКИЕ БЛОКИ GPSS.


Используются для сбора дополнительной статистики, которая

не собирается блоками операционной категории по умолчанию. Для

этой цели в GPSS имеются специальные средства, называемые регист-

раторами очереди (РО) и таблицами (Т).


Регистраторы очереди (РО)


Блоки РО предназначены для сбора статистики о транзактах,

ожидающих в очереди входа в блок, моделирующий разделяемый ресурс в

объекте-оригинале. Очередь на входе формируется по умолчанию испол-

няющей подсистемой GPSS, но для сбора статистики о процессе ожидания

надо специально включать в текст программы операторы для регистра-

тора очереди (РО).


Операторы QUEUE, DEPART

-----------------------


Q-схема Блок-диаграмма Оператор Примечание

Q

-------+ +--+--+/\ Зарегистрировать

==> ||||||| | B |А | QUEUE А, В вход транзакта в

-------+ +--+--+\/ очередь A, занять

В мест очереди

Q

-------+ +--+--+/\ Зарегистрировать

|||||||==> | В |А | DEPART A, В выход транзакта из

-------+ +--+--+\/ очереди A, освобо-

дить В мест очереди

ПРИМЕЧАНИЕ. По умолчанию В = 1.


Один и тот же транзакт может регистрироваться в нескольких

очередях, что позволяет собирать как частные статистики, так и

общую статистику.

Например, если моделируется система с несколькими типами

транзактов, то можно собрать статистику о процессах ожидания как

для каждого типа транзактов в отдельности, так и в различных

объединениях транзактов различных типов, вплоть до статистики о

суммарных потоках транзактов.

Если транзакты регистрируются в нескольких очередях, то

пары операторов QUEUE и DEPART должны быть вложенными.


Пример.

-------

Рассмотрим имитационную модель СМО с "чистым" ожиданием.

Q

+---+ LA ------+ +---+ MU

| И +------ ||||||+---| К +--->

+---+ ------+ +---+


SIMULATE

GENERATE Аи, Ви

QUEUE 1 ; вход в очередь

SEIZE 1 ; занятие канала

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

ADVANCE Ак, Вк ; задержка в канале

RELEASE 1 ; освобождение канала

ТERMINATE 1

START N

END


ПРИМЕЧАНИЕ. Вследствие того, что транзакт входит в блок QUEUE неза-

висимо от состояния устройства, возможно нулевое время пребывания

в очереди транзакта


Пример.

------

Рассмотрим m-канальную СМО с двумя типами транзактов.


+----+ LA1

| И1 +-------+

+----+ | Q +----+

| ------+ | K1 | MU1

+--->||||||+--|....+--->

| ------+ | Km | MU2

| +----+

+----+ LA2 |

| И2 +-------+

+----+


SIMULATE

S_K STORAGE m

; транзакты 1-го типа

GENERATE Аи1, Ви1

QUEUE 1 ; частная статистика

QUEUE 3 ; общая статистика

ENTER S_K

DEPART 3 ; общая статистика

DEPART 1 ; частная статистика

ADVANCE Ан1, Вн1

LEAVE S_K

ТERMINATE

; транзакты 2-го типа

GENERATE Аи2, Ви2

QUEUE 2 ; частная статистика

QUEUE 3 ; общая статистика

ENTER S_K

DEPART 3 ; общая статистика

DEPART 2 ; частная статистика

ADVANCE Ан2, Вн2

LEAVE S_K

ТERMINATE 1

START N2 ; N2 - объем выборки транзактов 2-го типа

END


Таблицы (Т).


Они позволяют получать оценочные распределения случайных вели-

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


Структура оценочной функции распределения F' (X)


| | | | ***** 100%

| | | *******

n1 | n2 | n3 | ****n(m-1)| n(m)

--- | --- | --- | | --- | ---

N | N | N | | N | N

| | | . . . | |

n1 | n2 | n3 *** |n(m-1)| n(m)

| ******* | |

******* | | |