На основе событийного способа имитации

Пример построения моделирующего алгоритма

На примере имитационного моделирования простейшей вычислительной системы проиллюстрируем методику разработки ИМ на основе событийного способа имитации (раздел 3.3.2). Разработка ИМ включает этапы Э1, Э2 (из раздела 3.3.1). Опишем подробно действия, осуществляемые разработчиком на каждом из этапов.

Задание. На основе событийного способа имитации разработать ИМ вычислительной системы (ВС) S, обслуживающей пакеты заданий пользователей в течение t единиц времени; обеспечить вычисление количества поступивших, обслуживаемых и потерянных (вследствие переполнения оперативной памяти ВС) заданий. Реализовать ИМ на универсальном языке программирования.

Содержательное описание системы

ВС содержит процессор и запоминающее устройство с памятью, разделенной на m блоков. При выполнении задание занимает все процессорное время. Если в момент поступления очередного задания процессор занят, но имеются свободные блоки памяти, задание становится в очередь на выполнение. Если же все блоки памяти заняты, то задание не может поступить в ВС и теряется. Если по окончании времени моделирования ВС выполняется задание, то время моделирования увеличивается на величину , необходимую для полного обслуживания задания (т.е. фактическое время моделирования будет Т_ф = Т + ). Интервалы поступления и выполнения задания – случайные величины с экспоненциальным законом распределения (с параметрами и соответственно).

Математическая (концептуальная) модель (Э1).

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

Итак, будем рассматривать S как систему массового обслуживания (СМО), состоящую из одного прибора обслуживания(рис.3.12), включающего накопитель заявок Н (память) емкостью m и канал К обслуживания заявок.

Н u …

В данной СМО имеются следующие потоки:

- поток заявок v (последовательность интервалов времени между моментами поступления заданий в ВС);

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

- выходной поток y (последовательность интервалов времени между моментами выхода заданий (выполненных и потерянных) из системы).

Законы распределения L{v}, L{u} случайных величин v, u известны (v и u имеют экспоненциальное распределение с параметрами и соответственно).

В качестве вектора параметров системы S возьмем вектор

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

По условию задания показателями КЦФ системы являются средние значения таких величин, как: число поступивших в систему заявок q₁ заявок q₂ и число потерянных заявок q₃. В качестве оценок этих показателей будем использовать статистики {Q_i}, вычисляемые по результатам N прогонов ИМ для интервала моделирования [0, T]:

где - значение i -го ПЭ на j –м прогоне ИМ.

Процесс функционирования системы S – это процесс изменения состояний ее компонент во времени. Состояние системы S в момент времени будем описывать вектором

где x₁(t) – количество заявок в накопителе, 0;

Целью имитационного моделирования системы S является решение задачи 1 (из раздела 4.3.1), т.е. нахождение оценок Q_1, Q_2, Q₃ при некотором фиксированном значении

Моделирующий алгоритм (Э2).

Для построения ИМ системы S будем использовать событийный способ имитации (раздел 3.3.2) с изменением модельного времени по принципу (пункт Б 3.3.1). Процесс разработки моделирующего алгоритма включает следующие этапы.

Э 2.1. Выделение элементов системы, подлежащих моделированию, и определение типов событий.

Э 2.2. Определение условий перехода от одного события к другому, а также действий в конфликтных ситуациях.

Э 2.3.Определение условий моделирования.

Э 2.4. Для каждого типа событий описание действий, приводящих к изменению состояния системы и вычислению показателей эффективности.

Э 2.5. Разработка логической схемы (блок – схемы) модели.

Реализуем каждый из данных этапов при разработке моделирующего алгоритма системы S.

Э 2.1. Будем рассматривать S как систему, состоящую из двух элементов, поведение которых подлежит моделированию:

- А⁽¹⁾ поток заявок на обслуживание, А⁽²⁾ - поток обслуживаний. Тогда в ИМ системы S = { А⁽¹⁾, А⁽²⁾} возможны следующие типы событий (особых) и действий.

Для А⁽¹⁾: события – «поступление j-й заявки», к которым приводят действия

– «генерация j – й заявки (j = 1, 2,…).

Для А⁽²⁾: события – «окончание обслуживания j–й заявки», к которой приводят действия – «обслуживание j–й заявки» (j = 1, 2,…).

Будем называть их событиями типа А⁽¹⁾ и А⁽²⁾. Помимо этих особых событий целесообразно ввести еще два события («псевдоособых»), возникающих только однажды: А⁽⁰⁾ - «поступление 1-ой заявки» (А⁽⁰⁾ ), и А⁽³⁾ - «завершение моделирования». Поскольку число различных типов событий невелико (L = 4), то выбор событийного способа имитации оправдан.

Э 2.2. Для разрабатываемой ИМ выделено четыре типа событий А⁽⁰⁾, А⁽¹⁾, А⁽²⁾, А⁽³⁾. События А⁽⁰⁾, А⁽³⁾ (первое и последнее события в ИМ наступают всегда один раз. События типа А⁽¹⁾, А⁽²⁾ всегда наступают в последовательности .

В процессе моделирования моменты наступления событий разных типов могут совпадать. Такие события называются одновременными, а подобные ситуации конфликтными. Действия в конфликтных ситуациях подобного типа предусматривают задания последовательности наступления событий в ИМ из числа одновременных и реализацию данной последовательности в моделирующем алгоритме. Для моделируемой системы будем полагать, что одновременные события типа А⁽¹⁾, А⁽²⁾, А⁽³⁾ всегда наступают в последовательности А⁽³⁾, А⁽²⁾, А⁽¹⁾.

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

Э 2.3. Определение условий моделирования включает: задание законов распределения моделируемых в ИМ случайных величин и значений параметров системы S; выбор единицы измерения модельного времени; описание начального состояния системы S и условий завершения моделирования.

Будем предполагать, что в начальный момент времени (t = 0) состояние системы следующее: прибор свободен (канал свободен, накопитель пуст); обнулены переменные для накопления результатов моделирования. Будем также считать, что время моделирования t выбрано так, что с вероятностью 1 выполняется соотношение: < T.

Э 2.4. Прежде чем переходить к описанию последовательностей действий в ИМ, запишем для рассматриваемой ИМ правило изменения модельного времени по принципу «».

<Т,

t(r + 1) = min (3.8)

где r = r₁ + r₂(r_1, r₂ = 0, 1, 2, …) и согласно (3.6)

(k = 1, 2). (3.9)

Здесь: r_1, r₂ - количества, а - моменты наступления в ИМ событий типа A⁽¹⁾,A⁽²⁾;-j-ые реализации случайных величин, моделируемых по экспоненциальному закону с параметрами соответственно.

Обозначим - номер типа (r + 1)-го события в ИМ, определяемый на основании (3.8) по формуле:

(3.10)

Наступление событий различных типов порождает последовательности действий из G\D, не требующих затрат модельного времени, но приводящих к изменению состояния системы S, т.е. к изменению вектора x и вычислению показателей эффективности w. Опишем эти последовательности для каждого типа событий на l -м (l = ) прогоне ИМ.

Действия для события A⁽⁰⁾.

1. Установление начальных значений:

(k =1,2), t (0) = 0, x(0) =

2. Имитация по формуле (3.9) и присваивается t(1) = .

3. Увеличение числа поступивших требований:

4. Переход канала из свободного состояния в занятое: x₂ = 1.

5. Имитация по формуле (3.9).

6. Имитация по формуле (3.9).

7. Вычисление t(2) по формуле (3.8)

8. Определение типа будущего события по формуле (3.10):

«ДА»9. Выполнение действий для события А.

«НЕТ» 10.

«ДА» 11. Выполнение действий для события А.

«НЕТ» 12. Выполнение действий для события А⁽³⁾.

Действия для событий

1.Увеличение числа поступивших заявок:

2.Проверка состояния канала: x₂ = 0?

«ДА» 3. Переход канала из свободного состояния в занятое:

4. Имитация по формуле (3.9) и переход к действию 8.

«НЕТ» 5. Проверка длины очереди: x₁ > m?

«ДА» 6. Занесение заявки в очередь: x₁ +1 и переход к действию 8.

«НЕТ» 7. Потеря заявки:

8. Имитация по формуле (3.9).

9. Вычисление момента t (r +1) наступления будущего события по формуле (3.8) (где )

t (r +1)=min

10. Определение типа будущего события по формуле (3.10)

«ДА» 11. Выполнение действий для A

«НЕТ» 12.

«ДА» 13. Выполнение действий для A

«НЕТ» 14. Выполнение действий для A⁽³⁾.

Действия для событий A

1. Увеличение числа обслуженных заявок:

2. Проверка состояния накопителя: x₁ > 0?

«ДА» 3. Продолжение заявки в очереди:

4.Имитация по формуле (3.9) и переход к действиям 6,7.

«НЕТ» 5. Переход канала из занятого состояния в свободное:

6, 7. Выполнение действий 9, 10 для состояния А

Замечание. При выполнении действий 6,7 после действия 5 может оказаться, что переменная в формуле не определена (канал свободен x₂ = 0). В подобных случаях целесообразно полагать, что .

Действия для события A⁽³⁾.

Событие «завершения моделирования» требует специальных действий, связанных с увеличением интервала моделирования [0, T] на величину , необходимую для завершения обслуживания заявки, находящейся в канале обслуживания (если таковая в момент Т модельного времени имеется), и предотвращением поступления новых требований. Последнее достигается переходом к обработке и выводу результатов. Поэтому последовательность действий для A⁽³⁾ следующая.

1. Проверка состояния канала: x₂ = 1?

«ДА» 2. Увеличение числа обслуженных заявок:

3. Переход канала из занятого состояния в свободное: x₂ = 0.

4.Увеличение интервала моделирования: (т.е. ).

«НЕТ» 5. Вывод результатов l –го прогона ИМ:

6. Переход к (l + 1)-му прогону ИМ.

Пример. Пусть m = 1в результате имитационного моделирования рассматриваемой системы S на интервале для l –го прогона получена последовательность событий, изображенная на временной диаграмме (рис.3.12). Тогда в результате выполнения описанных выше последовательностей действий будут получены фазовая траектория

и показатели КЦФ, приведенные в табл.3.3

Э2.5. Логическая схема (блок-схема) моделирующего алгоритма строится на основании действий, разработанных на этапе Э2.2 с учетом предположений, сделанных на этапах Э2.3, Э2.4. Разработкой логической схемы заканчивается построение моделирующего алгоритма. На основании логической схемы в соответствии с требованием задания разрабатывается ИМ (программа) системы S.