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

Вид материала

Содержание

3.1. Основные понятия имитационного моделирования.

Подобный материал:

1 2 3 4

Егоров Е.А.

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

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

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

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

АМ позволяют получать зависимость 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 и тогда он рассматривается как

Blog

Содержание