ИМИТАЦИОННОЕ МОДЕЛИРОВАНИЕ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ

План

1. Процедура имитационного моделирования

2. Обобщенные алгоритмы имитационного моделирования

1. Процедура имитационного моделирования

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

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

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

Функциональные взаимосвязи устройств определяют возможные пути продвижения заявок по системе от входных устройств к выходным. Они формируют функциональную структуру ВС.

Модель внешних воздействий — это правила определения моментов поступления входных сигналов (заявок) в систему, маршрута заявок в системе по каждому из потоков в соответствии с алгоритмами обработки, приоритетов обслуживания заявок одних потоков по отношению к другим, трудоемкости обслуживания заявок устройствами, допустимого времени пребывания заявок в системе и др.

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

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

Имитационное моделирование — это метод исследования, который основан на том, что анализируемая динамическая система заменяется имитатором и с ним проводятся эксперименты для получения информации об изучаемой системе. Роль имитатора зачастую выполняет специальная программа ВС.

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

где  — случайные величины с известными функциями распределения.

Для решения задач такого вида применяется следующий алгоритм:

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

2) используя найденные величины, определяется одно частное значение y_i по вышеприведенной зависимости;

3) предыдущие операции повторяются N раз, в результате чего определяется N значений случайной величины у;

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

Имитация функционирования системы. Предположим, что ВС состоит из процессора 1 с основной памятью, устройства ввода 4, печатающего устройства 2 и монитора 3. Через устройство ввода поступает поток заданий X₁. Процессор обрабатывает задания и результаты обработки выдает на печатающее устройство (принтер). Одновременно с этим ВС используется, например, как информационно-справочная система. Оператор-пользователь, работающий за монитором, посылает в систему запросы X₂, которые обрабатываются процессором, и ответы выводятся на монитор. Процессор работает в двух программном режиме: в одном разделе обрабатываются задания X₁, в другом, с более высоким относительным приоритетом, — запросы Х₂.

Представим данную ВС в упрощенном варианте в виде стохастической сети из четырех СМО. Потоки заданий и запросов будем называть потоками заявок. Считаем потоки X₁ и X₂ независимыми. Известны функции распределения периодов следования заявок  и  и длительностей обслуживания Т_1k и Т_2k заявок k-м устройством. Требуется определить времена загрузки каждого устройства и времена реакции по каждому из потоков.

{spoiler=Подробнее}

Рис. 1. Временная диаграмма функционирования ВС

В начале определяется момент поступления в систему первой заявки потока Х₁ по результатам случайного испытания в соответствии с функцией распределения периода следования заявок. На рис. 1 это момент времени  (здесь и далее верхний индекс обозначает порядковый номер заявки данного потока). То же самое делается для потока Х₂. На рис. 2 момент поступления первой заявки потока . Затем находится минимальное время, т.е. наиболее раннее событие. В примере— это время t₁. Для первой заявки потока X₁ определяется путем случайного испытания время обслуживания устройством ввода T¹₁₄ и отмечается момент окончания обслуживания  На рисунке показан ступенькой переход устройства 4 в состояние «занято». Одновременно определяется момент поступления следующей заявки потока .

Следующее минимальное время — это момент поступления заявки потока X₂-t₂. Для этой заявки находится время обслуживания на мониторе T¹₂₃ и отмечается время окончания обслуживания . Определяется момент поступления второй заявки потока . Снова выбирается минимальное время— это t_з. В этот момент заявка потока Х₂ начинает обрабатываться процессором. По результату случайного испытания определяется время ее обслуживания T¹₂₃ и отмечается момент  окончания обслуживания. Следующее минимальное время t₄ — момент завершения обслуживания заявки потока X₁ устройством 4. С этого момента заявка может начать обрабатываться процессором, но он занят обслуживанием заявки потока Х₂. Тогда заявка потока X₁ переходит в состояние ожидания, становится в очередь.

В следующий минимальный момент времени t₅ освобождается процессор. С этого момента процессор начинает обрабатывать заявку потока X₁, а заявка потока X₂ переходит на обслуживание монитором, т. е. ответ на запрос пользователя передается из основной памяти в буферный накопитель монитора. Далее определяются соответствующие времена обслуживания  и отмечаются моменты времени .  В момент t₆ полностью завершается обработка первой заявки потока Х₂. По разности времен t₆ и t₂ вычисляется время реакции по этой заявке:

Следующий минимальный момент времени t₇ — это поступление  второй заявки потока Х₂. Определяется время поступления очередной заявки этого потока . Затем вычисляется время обслуживания второй заявки на мониторе Т²₂₃ и отмечается момент  после чего заявка становится в очередь, так как процессор занят. Эта заявка поступает на обслуживание в процессор только после его освобождения в момент времени t₉. В этот же момент заявка потока Х₁ начинает обслуживаться принтер. Определяются времена обслуживания Т²₂₁ и T¹₁₂ по результатам случайных испытаний и отмечаются моменты окончания обслуживания  . В момент времени t₁₀ завершается полное обслуживание первой заявки потока X₁. Разность между этим моментом и моментом времени t₁ дает первое значение времени реакции по потоку .

Вторая заявка потока Х₂ в момент t₁₁ поступает с процессора на- монитор и обслуживается им в течение времени Т²₂₃, которое завершается в момент  Снова определяется очередное минимальное время. Это время — t₁₂ когда в систему поступает вторая заявка из потока Х₁. Тогда вычисляется время поступления третьей заявки потока  Вторая заявка обслуживается устройством ввода в течение времени Т²₁₄ (момент завершения — )  и процессором — T²₁₁ (момент завершения — ). В момент t₁₃ состояние системы не изменяется, но вычисляется второе значение времени реакции по потоку Х₂:

В момент времени t₁₅ систему поступает третья заявка потока Х₂. Определяется момент поступления четвертой заявки потока  (предполагается, что пользователь может посылать запросы, не дожидаясь ответов на предыдущие запросы). Третья заявка обслуживается монитором в течение времени T³₂₃, но с момента окончания обслуживания () переходит в состояние ожидания, так как занят процессор.

Следующее минимальное время t₁₇, — это время поступления четвертой заявки потока Х₂. После ее обслуживания монитором (момент завершения ) она также переходит в ожидание, т. е. образуется очередь из двух заявок. После освобождения процессора в момент t₁₉ начнется обслуживание процессором третьей заявки потока X₂, а затем с момента — монитором. По завершении этого обслуживания () можно будет вычислить третье значение времени реакции по потоку X₂:

С момента времени t₁₉ принтер начнет обслуживание второй заявки потока X₁ и завершит его к моменту , после чего определяется второе значение времени реакции по потоку X₁:

Указанные процедуры выполняются до истечения времени моделирования. В результате получается некоторое количество (выборка) случайных значений времен реакции {u₁} и {u₂} по первому и второму потокам. По этим значениям могут быть определены эмпирические функции распределения и вычислены количественные вероятностные характеристики времен реакции. В процессе моделирования можно суммировать продолжительности занятости каждого устройства обслуживанием всех потоков. Например, на рис. 1 занятость процессора 1 выделена заштрихованными ступеньками. Если результаты суммирования разделить на время моделирования, то получатся коэффициенты загрузки устройств.

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

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

2. Обобщенные алгоритмы имитационного моделирования

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

Рис. 3. Алгоритм моделирования по принципу особых состояний

Процесс имитации функционирования системы развивался во времени с использованием управляющих последовательностей, определяемых по функциям распределения вероятностей исходных данных путем проведения случайных испытаний. В качестве управляющих последовательностей использовались в примере последовательности значений периодов следования заявок по каждому i-му потоку {} и длительностей обслуживания заявок i-го потока k-м устройством {T_ik}. Моменты наступления будущих событий определялись по простым рекуррентным соотношениям. Эта особенность дает возможность построить простой циклический алгоритм моделирования, который сводится к следующим действиям:

1) определяется событие с минимальным временем — наиболее раннее событие;

2) модельному времени присваивается значение времени наступления наиболее раннего события;

3) определяется тип события;

4) в зависимости от типа события предпринимаются действия, направленные на загрузку устройств и продвижение заявок в соответствии с алгоритмами их обработки, и вычисляются моменты наступления будущих событий; эти действия называют реакцией модели на события;

5) перечисленные действия повторяются до истечения времени моделирования.

В процессе моделирования производится измерение и статистическая обработка значений выходных характеристик. Обобщенная схема алгоритма моделирования по принципу особых состояний (принцип ) изображена на рис. 2. Вначале производится инициализация моделирующей программы — подготавливаются массивы, вводятся и размещаются в оперативной памяти входные данные, настраиваются датчики случайных чисел. Затем генерируются первые заявки по каждому потоку — определяются моменты их поступления в систему и конкретизируются другие параметры.

Остальные операции выполняются в цикле. Определяется момент наступления наиболее раннего события и до этого момента смещается модельное время. После определения типа события реализуется соответствующая реакция на событие. В процессе этих действий могут возникать те или иные события в будущем, что фиксируется в массиве событий. Реакция на определенное событие, кроме всего прочего, приводит, как правило, к исключению его из массива событий. Кончается каждая реакция возвратом к определению события с минимальным временем.

Такой цикл повторяется до достижения конца моделирования, после чего завершается обработка статистики и выводятся результаты. На этом заканчивается модельный эксперимент.

В системе-оригинале могут протекать одновременно несколько процессов. Это приводит к тому, что в один и тот же момент времени в системе может возникнуть несколько особых событий. При моделировании на однопроцессорной ВС эти ситуации разрешаются таким образом: последовательно в установленном порядке реализуются реакции на все одновременно возникшие ситуации без продвижения модельного времени. Это называется псевдопараллельной имитацией нескольких процессов.

Рис. 3. Алгоритм моделирования по принципу временных приращений

Алгоритм моделирования по принципу . Укрупненная схема моделирующего алгоритма, который реализует принцип постоянного приращения модельного времени (принцип ), представлена на рис. 3. Как и в предыдущем алгоритме, вначале инициализируется программа, в частности, вводятся значения z_i(t₀), i= 1, ...,n, которые характеризуют состояние системы в n-мерном фазовом пространстве состояний в начальный момент времени t₀. Модельное время устанавливается t = t₀ = 0.

Основные операции, с помощью которых имитируется функционирование системы, выполняются в цикле. Функционирование системы отслеживается по последовательной смене состояний Z_i (t). Для этого модельному времени дается некоторое приращение . Затем по вектору текущих состояний определяются новые состояния z_i (t + ), которые становятся текущими. Для определения новых состояний по текущим в формализованном описании системы должны существовать необходимые математические зависимости. Такой цикл продолжается до тех пор, пока текущее модельное время меньше заданного времени моделирования Т,m.

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

При моделировании стохастических систем вместо новых состояний вычисляются распределения вероятностей для возможных состояний. Конкретные значения вектора текущего состояния определяются по результатам случайных испытаний. В результате проведения имитационного эксперимента получается одна из возможных реализации случайного многомерного процесса в заданном интервале времени (t_o, T_т).

Моделирующий алгоритм, основанный на принципе , применим для более широкого круга систем, чем алгоритм, построенный по принципу особых состояний. Однако при его реализации возникают проблемы с определением величины . Для моделирования ВС на системном уровне в основном применяется принцип особых состояний.

Контрольные вопросы

1. Общее определение имитационного моделирования.
2. Имитация фукнционирования ВС.
3. Алгоритм моделирование по принципу особых состояний.
4. Алгоритм моделирования по принципу временных приращений.

   {/spoilers}