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

Размещено на http://www.allbest.ru/

Федеральное агентство по образованию РФ

Рязанский Государственный Радиотехнический Университет

Кафедра АСУ

Курсовой проект

по дисциплине: "Моделирование систем"

на тему: "Три подхода к дискретному моделированию"

Выполнил: ст. гр. 7030

Юдаев А.И.

Проверил:

Одиноков В. Ф.

Рязань 2011г.



Введение

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

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

Сканирование активностей - это способ определения момента возникновения структурных (дополнительных) событий путем проверки выполнения оговоренных условий в течение всего времени имитационного прогона.

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

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



СОБЫТИЙНОЕ МОДЕЛИРОВАНИЕ

Для построения дискретно-событийной модели необходимо определить все основные события, при которых может измениться состояние системы, и сгруппировать их в классы по способу (алгоритму) реализации (свершения). Каждое событие должно характеризоваться, кроме класса, набором параметров (атрибутов), используемых в модели, и временем свершения TSOB (или интервалом свершения DTIME, отсчитываемого, как правило, от текущего момента TNOW).

Планирование и реализация событий, разделенных временными интервалами, требуют хранения запланированных событий. Это делается с помощью специализированного файла-календаря или списка. Поскольку календарь используется не только для хранения событий, но и для анализа состояния имитационного процесса, события в нем расположены в порядке возрастания времени свершения. По ходу имитации события выбираются из календаря и реализуются по очереди. Имитационное время TNOW обновляется только после извлечения очередного события из календаря, когда становится известным время его свершения TSOB. Алгоритм задания модельного времени в этом случае, как было сказано ранее, соответствует явному оператору TNOW=TSOB. В ходе имитации календарь поддерживается в должном состоянии особой подпрограммой GRUP, вызываемой после любого обращения к календарю, сопровождающегося нарушением порядка расположения его записей.

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

Если очередной (NNRS) прогон заканчивается, вызывается подпрограмма оформления отчета OTPUTN по данному прогону и определяется направление действия: продолжать проведение новых прогонов или закончить имитацию.

После завершения всех NNRNS прогонов вызывается процедура обработки результатов всех прогонов и оформления итогового отчета OTPUT.

Сбор данных ведется в любом месте программы моделирования и при любом TNOW в соответствии с разработанным алгоритмом.

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

АЛГОРИТМ ДИСКРЕТНО-СОБЫТИЙНОЙ ИМИТАЦИИ

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

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

Модуль SCHDL передает в календарь все сведения о будущем событии: его атрибуты, код класса KEVNT и время свершения TSOB (содержит две части - известное время и приращение DTIME, рассчитываемое в зависимости от события. Поскольку известная часть обычно является текущим временем TNOW, планировать можно не само время TSOB, а только его приращение DTIME. Учитывая важность понятия "времени свершения", в дальнейшем будем оперировать в основном его символическим эквивалентом TSOB).

Собственно имитация работы моделируемого объекта (системы) начинается с выбора из календаря первого события с минимальным временем свершения TSOB. Информация об извлеченном событии используется для проведения ряда операций. Так, например, TSOB дает возможность обновить системное время (TNOW=TSOB). Код класса KEVNT необходим для поиска соответствующего алгоритма реализации события. Атрибуты события используются для определения направления действий при имитации.

Поиск программы реализации события осуществляет специализированная процедура EVENT, в которую при ее вызове передается код события. По коду события программа EVENT либо вызывает саму подпрограмму реализации, либо ищет у себя внутри встроенный блок алгоритма свершения события.

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

Нетрудно заметить, что все основные шаги по дискретно-событийной имитации будут повторяться для любых моделируемых объектов. Поэтому управление ходом имитации независимо от задачи поручают отдельной процедуре системного типа - процессору имитации СЛАМ, вызываемому из главного модуля перед первым прогоном (рис. 4.1).

Размещено на http://www.allbest.ru/

Рис. 4.1. Блок-схема алгоритма управления событийной моделью



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

ПРИМЕР СОБЫТИЙНОЙ МОДЕЛИ

В качестве примера событийной модели рассмотрим часть информационной системы, куда поступают заявки, которые затем обрабатываются и транслируются дальше. Интервалы поступления распределены случайно экспоненциально с математическим ожиданием =20.0 единиц. Время обработки распределено также случайно равномерно от 10 до 25 единиц. Имитируется работа сети в течение 480 единиц времени.

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

Группировка событий. Из всех возможных типов событий (поступление заявок, постановка их в очередь, обработка заявок, пересылка) ограничимся двумя классами - поступление (приход) и обработка (обслуживание), так как именно они регламентированы временными данными. Начало обслуживания и постановку в очередь (если еще не закончена обработка предыдущей заявки) совместим с моментом поступления заявки, а пересылку - с окончанием обработки. Никаких особых операций по постановке в очередь и пересылке заявок не предусматривается.

Атрибуты событий. Исходные данные никак не характеризуют поступающие заявки, кроме момента появления. Таким образом, атрибуты событий "приход" могут быть исключены из рассмотрения. Однако с целью иллюстрации работы с атрибутами сохраним их формально с числом MATR=1. В качестве единственного атрибута примем время поступления заявки (хотя этот параметр уже имеет свой отдельный статус и обозначение TSOB). Что касается обслуживания, то эти события, также не обнаруживающие никаких особых характеристик, могут иметь, в частности, тот же атрибут, что и атрибут предшествующих им событий "приход", поскольку целесообразно обрабатывать заявки с указанием их времени поступления. Другое использование назначенного атрибута не планируется, хотя он позволяет, например, автоматизировать контроль хода операций (пар операций по реализации событий "приход" и "обслуживание" с одним и тем же атрибутом).

Процедура планирования. Подпрограмма планирования SCHDL является системной и должна иметь три формальных параметра - код планируемого события KEVNT, время свершения (реализации) TSOB и массив A1, который принимает все атрибуты планируемого события при вызове SCHDL. Организуем SCHDL следующим образом (язык ФОРТРАН):

SUBROUTINE SCHDL(KEVNT, TSOB, A1)

DIMENSION A1(MATR), A2(MATR+2), A3(MATR+2, NNQ1)

COMMON /COM/…

DO 1 N=1, MATR

1A2(N)=A1(N)

A2(MATR+1)=KEVNT

A2(MATR+2)=TSOB

READ(1'1) A3

DO 2 J=1, NNQ1

2IF(A3(MATR+1, J).EQ.0) GOTO 3

3WRITE(1'J) A2

CALL GRUP

RETURN

END

Здесь A2 - массив предварительной компоновки записи для ее дальнейшей пересылки в календарь событий (размерности всех массивов должны быть заданы); A3 - массив для копирования всего календаря в электронную память из внешнего носителя (файла); NNQ1 - максимальное число записей календаря. Поскольку планируемое событие содержит, кроме атрибутов события, также код класса и время свершения TSOB, размерность массива A2 выше такого же параметра для массива A1. Процедура SCHDL получает информацию из оператора ее вызова и из области COMMON (многоточие после COMMON означает другие идентификаторы, используемые в данной процедуре для связи с другими программами).

С оператора DO 1 (цикл) начинается формирование записи календаря (пока массива A2), в которую поступают данные из A1. После этого в A2 копируются код и время свершения события. Оператор READ переписывает в массив A3 файл календаря (номер один с прямым доступом, чтение - с первой записи) с внешнего носителя для работы с календарем. Оператор DO 2 проводит поиск первой свободной записи в календаре по коду события (запись свободна, если код отсутствует, что требует предварительного обнуления кодов в начале имитации), после чего оператор WRITE выводит в файл календаря (номер один с прямым доступом, вывод - начиная с записи с номером J) данные из массива A2.

Оператор вызова процедуры планирования:

CALL SCHDL (KEVNTZ, TSOBZ, ATRIB)

Здесь KEVNTZ - выражение или число, определяющее KEVNT, TSOBZ - выражение для расчета TSOB, ATRIB - системный специализированный массив: при планировании события он передает информацию (в данном случае атрибуты планируемого события) в календарь, при извлечении записи из календаря принимает необходимые данные. Очевидно, что элементы массива ATRIB при планировании должны быть известны или они не должны влиять на дальнейшие действия.

Сортировка записей в календаре. Процедура поддержания порядка записей в календаре может иметь следующий вид:

SUBROUTINE GRUP

DIMENSION A2(MATR+2), A3(MATR+2, NNQ1)

COMMON /COM1/ MATR, …

READ(1'1) A3

IF(A3(MATR+1, 1).EQ.0) GOTO 1

DO 2 J=1, NNQ1 -1

IF(A3(MATR+1, J).EQ.0) GOTO 3

K=J

Z=A3(MATR+2, J)

DO 4 L=J+1, NNQ1

IF(A3(MATR+1, L).EQ.0) GOTO 8

IF(A3(MATR+2, L).GE.Z) GOTO 4

Z=A3(MATR+2, L)

K=L

4 CONTINUE

DO 2 I=1, MATR+2

A2(I)=A3(I, J)

A3(I, J)=A3(I, K)

A3(I, K)=A2(I)

WRITE(1'1) A3

RETURN

DO 6 J=1, NNQ1 -1

DO 6 I=1, MATR+2

A3(I, J)=A3(I, J+1)

A3(I, J+1)=0

GOTO 3

RETURN

END

Как видно из приведенного фрагмента, после копирования в A3 календаря осуществляется проверка состояния первой записи. Если она пустая, ясно, что из календаря ранее выбрано событие с минимальным временем свершения и, следовательно, достаточно сдвинуть календарь на одну запись влево. Это делает блок с меткой 1, обнуляющий последним оператором с меткой 6 запись A3(I, J+1), используемую потом для планирования очередного события. Далее действие передается по метке 3, где производится вывод сформированного календаря из массива A3 в файл 1.

Если первая запись календаря не пуста, значит, процедура вызвана после планирования какого-то события и необходимо расставить записи по возрастанию их времени свершения (запланированное событие могло иметь любое время свершения). Для этого с оператора DO 2 J=1, NNQ1 -1 начинаются сравнение времени свершения J-й записи с аналогичным параметром остальных записей и перемещение этой записи на нужное место календаря (массива A3). Перед каждой такой последовательностью действий оператором IF(A3(MATR+1, J).EQ.0) GOTO 3 J-я запись проверяется по коду события. Если он равен нулю, календарь кончился и управление передается метке 3 для вывода готового календаря в файл.

Перед сортировкой календаря оператор K=J запоминает номер J-й записи, а оператор Z=A3(MATR+2, J) - ее время свершения. Следующий за ними блок DO 4: а) проверяет код очередной, сопоставляемой с J, записи L; б) сравнивает время двух записей; в) запоминает (обновляет K, Z) номер и время свершения записи L. Если проверяемый код записи L равен нулю, календарь кончился и управление передается на метку 8 для обмена данными между записями J и L (K), так как в цикле DO 4 нормальный ход действий приводит к отысканию записи с временем, меньшим, чем у записи J. Если время свершения записи L оказывается больше или равным тому же для записи J, управление передается метке 4 с переходом к следующей записи календаря (цикл DO 4).

После обработки всего календаря циклом DO 2 J=1, NNQ1 очередной оператор WRITE(1'1) A3 выводит данные в файл 1.

Извлечение первой записи. Пример процедуры извлечения первой записи из календаря:

SUBROUTINE RMOVE

DIMENSION A3(MATR+2, NNQ1), ATRIB(MATR)

COMMON /COM1/ MATR,…

READ(1'1) A3

TSOB=A3(MATR+2, 1)

I=A3(MATR+1, 1)

DO 1 N=1, MATR

1 ATRIB(N)=A3(N,1)

A3(MATR+1, 1)=0

WRITE(1'1) A3

CALL GRUP

RETURN

END

После копирования календаря в массив A3 из его первой записи извлекаются и запоминаются (сортируются по назначению) для передачи через COMMON-область: время свершения (в виде TSOB), код события I и атрибуты события (цикл DO 1). Затем код события первой записи обнуляется (запись становится условно пустой). Измененный календарь выводится в файл 1, а для восстановления порядка записей вызывается процедура GRUP.

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

SUBROUTINE SLAM

DIMENSION A2(MATR+2)

COMMON /COM1/ MATR,…

CALL INTLC

CALL RMOVE

TNOW=TSOB

CALL EVENT(I)

READ(1'1) A2

IF((TNOW.LT.TTFIN).AND.(A2(MATR+1).GT.0)) GOTO 1

CALL OTPUTN

IF(NRNS.LT.NNRNS) GOTO 2

CALL OTPUT

RETURN

END

Обновление системного времени происходит сразу после извлечения записи из календаря (при этом, как показано выше, поля извлеченной записи разделяются по назначению). Время события TSOB передается в SLAM через COMMON-область, как и другая информация. Реализация события происходит после поиска соответствующей программы процедурой EVENT(J) по коду I извлеченного события (J - формальный параметр, получающий значение J=I при вызове процедуры EVENT). Оператор READ(1'1) A2 копирует первую запись файла календаря для определения одного из двух параметров, участвующих в анализе условия окончания прогона - кода записи. Проверку этого условия ведет оператор IF((TNOW.LT.TTFIN).AND.(A2(MATR+1).GT.0)) GOTO 1. Отчет по прогону и итоговый отчет оформляются соответственно процедурами OTPUTN и OTPUT. Для различения отчетов по прогонам в процедуре OTPUTN должен быть отображен номер прогона NRNS. Вызов OTPUT осуществляется по результату сравнения NRNS и NNRNS в операторе IF(NRNS.LT.NNRNS) GOTO 2.

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

SUBROUTINE INTLC

DIMENSION A3(MATR+2, NNQ1), ATRIB(MATR)

COMMON /COM1/ MATR,…

TNOW=TTBEG

NRNS=NRNS+1

LO=0

MLO=0

NI=0

NL=0

READ(1'1) A3

DO 1 J=1, NNQ1

A3(MATR+1, J)=0

WRITE(1'1) A3

BUSY=0

TSOBZ=TNOW+EXPONS(20.0) (EXPONS(20.0) - случайная величина)

ATRIB(1)=TSOBZ

CALL SCHDL(1,TSOBZ,ATRIB)

RETURN

END

Здесь устанавливаются: время TNOW начала очередного прогона, номер прогона NRNS, текущая длина LO очереди для событий "приход", максимальное значение MLO длины очереди (MLO увеличивается при LOMLO и не меняется, если LOMLO или LO=MLO), номер NL постановки события "приход" в очередь (позволяет фиксировать общее количество заявок, находившихся то или иное время в очереди в течение прогона), номер NI изъятия события из очереди (может использоваться для контроля обращения к файлу), содержание полей массива A3 (предназначенных для кодов событий), состояние программы обслуживания: BUSY=0 (свободен). Последним рабочим оператором производится планирование события “приход”, где в качестве KEVNTZ употреблен код класса, а TSOBZ рассчитывается по формуле, включающей интервал DTIMEZ (фактический параметр интервала DTIME) в виде экспоненты, содержащей аргумент =20.0. Массив ATRIB в операторе планирования в общем случае должен содержать MATR атрибутов. В нашем примере MATR=1, и единственный атрибут ATRIB(1) задан как время реализации планируемого события в операторе ATRIB(1) =TSOBZ.

Главный модуль. Зависит от языка программирования. Пример на фортране:

COMMON /COM1/ MATR,…

DEFINE FILE 1(K1…NZ), 2(K2…NK)

MATR=1

NNQ1=K1

TTFIN=480

TTBEG=0

NRNS=0

NNRNS=10

I1=0

I2=0

M=20.

CALL SLAM

STOP

END

Цифры 1, 2 в операторах объявления файлов - их номера; K1, K2 - количество планируемых записей; NZ, NK - указатели рабочих записей. Переменные I1, I2 - параметры генератора случайных чисел (зависит от ЭВМ). CALL SLAM - оператор вызова процессора управления.

Обработка событий. Алгоритмы обработки (реализации) событий создаются применительно к особенностям моделируемого объекта. Рассмотрим, например, вариант модуля реализации событий класса 1 - “приход”:

SUBROUTINE ARVL

DEFINE FILE ATRIB(MATR)

COMMON /COM1/ MATR,…

TSOBZ=TNOW+EXPONS(20.0)

ATRIB(1)=TSOBZ

CALL SCHDL(1,TSOBZ,ATRIB)

ATRIB(1)=TNOW

IF(BUSY.EQ.0) GOTO 10

LO=LO+1

IF(LO.GT.MLO) MLO=LO

NL=NL+1

WRITE(2'NL) ATRIB

RETURN

10 BUSY=1

TSOBZ=TNOW+(10+15RAN(I1,I2)) (RAN(I1,I2) - случайное число)

CALL SCHDL(2, TSOBZ, ATRIB)

RETURN

END

Оператор CALL SCHDL(1, TSOBZ, ATRIB) при всех известных данных планирует приход следующей заявки (очередное событие "приход").

Следующий оператор ATRIB(1)=TNOW переопределяет массив ATRIB (ATRIB(1)=TSOBZ, заданный выше, относился к будущему событию "приход") для обрабатываемого события. Атрибут ATRIB(1) обрабатываемого события потребуется для постановки данного события "приход" в очередь или последующего обслуживания. В рассматриваемом случае ATRIB(1) должен быть равен TSOB обрабатываемого события. Но время TNOW, установленное оператором TNOW=TSOB в модуле SLAM после извлечения данного события из календаря, также соответствует требуемому значению. Поэтому для обрабатываемого события достаточно указать ATRIB(1) =TNOW.

Оператор IF(BUSY.EQ.0) GOTO 10 по состоянию переменной BUSY проверяет возможность планирования события "обслуживание" заявки, соответствующей данному событию "приход". Если программа обслуживания свободна (BUSY=0), осуществляется переход на метку 10. При этом переменная BUSY принимает необходимое значение 1 (программа обслуживания задействована), и производится расчет времени TSOBZ, который далее используется в операторе вызова процедуры планирования событий класса 2 (TSOBZ можно рассчитать и в операторе CALL SCHDL).

Если в рассматриваемый момент TNOW (момент обработки данного события "приход") BUSY=1 (программа обслуживания занята), заявка (событие "приход'') ставится в очередь, длина последней увеличивается (LO=LO+1), корректируется переменная MLO и возрастает общее число NL находившихся в очереди заявок (событий "приход").

Оператор WRITE(2'NL) ATRIB заносит данные о заявке с номером NL, которую нельзя пока обслужить, в файл очереди (второй файл).

Ниже дан пример процедуры обслуживания ENDSV:

SUBROUTINE ENDSV

DEFINE FILE ATRIB(MATR)

COMMON /COM1/ MATR,…

BUSY=0

IF(LO.GT.0) GOTO 10

RETURN

10 LO=LO -1

NI=NI+1

READ(2'NI) ATRIB

BUSY=1

CALL SCHDL(2, TNOW+(10+15RAN(I1,I2)), ATRIB)

RETURN

END

Поскольку процедура ENDSV, как и любые другие модули обработки событий, означает окончание обработки (реализации) события, программа обслуживания освобождается и BUSY становится равной нулю. Затем проверяется наличие заявок (событий "приход") в очереди: IF(LO.GT.0) GOTO 10. Если очередь не пуста, с метки 10 производятся уменьшение очереди (LO=LO-1), увеличение номера изъятия из очереди (NI=NI+1) и чтение из соответствующей записи файла 2 атрибута события с номером NI (READ(2'NI) ATRIB).

Далее оператор BUSY=1 определяет новое состояние системы - проведение операции по очередному обслуживанию. Планирование операции начинается с вызова процедуры SCHDL, куда передаются фактические параметры, в том числе время окончания обслуживания TNOW+(10+15RAN(I1,I2)), рассчитываемое, в отличие от предыдущего примера, в операторе вызова. Атрибуты планируемого события заданы в массиве ATRIB упомянутым выше оператором чтения READ(2'NI) ATRIB.

Поиск алгоритма обработки. Основываясь на приведенных выше процедурах ARVL и ENDSV, организуем поиск программы обработки событий через вызов этих модулей:

SUBROUTINE EVENT(J)

GOTO(1,2), J

CALL ARVL

RETURN

CALL ENDSV

RETURN

END

Код события I передается в процедуру EVENT при ее вызове (область COMMON при этом можно не указывать). Это число в операторе GOTO(1,2), J задает метку оператора вызова соответствующей программы.

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

SUBROUTINE OTPUTN

COMMON /COM1/…

WRITE (5,NRNS) NRNS

1 FORMAT ('NRNS=', I2)

WRITE (5,NRNS) MLO

2 FORMAT ('MLO=', I2)

RETURN

END

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

Размещено на Allbest.ru

...