А С В x

Общий случай треугольного распределения вероятностей

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

Пример. Предположим, что база данных находится на ком­пьютере, не входящем в состав какой-либо вычислительной сети. Поэтому пользователь, работающий с этой базой, имеет во время работы монопольный доступ к ней. Известны структуры и частоты запросов пользователей к этой базе данных. Рассмотрим три случая физической организации базы данных (рис. 4).

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

• наиболее вероятное время ответа на запрос близко к 0 с;

• минимальное вероятное время ответа не менее 0 с;

• максимальное вероятное время ответа не превышает 15 с;

• распределение вероятностей представлено линией 1 на рис. 4.

Этот системный программист обеспечил минимальное время для наиболее вероятных запросов за счет увеличения времени для менеевероятных. Среднее время получения ответа в этом случае t = 5 с.

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

• наиболее вероятное время ответа на запрос равно 5 с;

• минимальное вероятное время ответа не менее 0 с;

• максимальное вероятное время ответа не превышает 10 с;

• распределение вероятностей показано линией 2 на рис. 4.

График плотности вероятностей для треугольного распределения:

1 - максимум слева; 2 - максимум в центре; 3 - максимум справа

Таким образом, системный программист обеспечил снижение времени ответа для менее вероятных запросов за счет увеличения времени ответа для наиболее вероятных. Среднее время получения ответа осталось тем же: t = 5 с.

Третий случай. Администратор базы данных решил еще более уменьшить время ответа на менее вероятные запросы. Для этого он опять переделал физическую организацию данных и получил сле­дующие свойства:

• наиболее вероятное время ответа на запрос равно 7,5 с;

• минимальное вероятное время ответа не менее 0 с;

• максимальное вероятное время ответа не превышает 7,5;

• распределение вероятностей изображено линией 3 на рис. 4.

Этот системный программист обеспечил дальнейшее снижение времени ответа для менее вероятных запросов за счет увеличения времени ответа для более вероятных. Среднее время получения от­вета и в этом случае не изменилось: t=5 с.

Возникает естественный вопрос: «Какая физическая организация лучше?». Если отбросить факторы, определяющие большую или меньшую важность запросов, и вспомнить, что база данных не имеет множественного доступа из вычислительной сети, то можно утвер­ждать, что все три способа организации данных одинаковы, так как пользователи этой базы имеют одно и то же среднее время ответа.

Однако если подключить компьютер с нашей базой к локаль­ной вычислительной сети и разрешить доступ к базе данных боль­шому числу пользователей этой сети из рабочих компьютеров этих пользователей, то необходимо учитывать возникновение очереди запросов к базе данных при ее монопольном использовании. Пред­положим, что число пользователей довольно велико и выполняют­ся условия предельной теоремы о суперпозиции потоков событий (в нашем случае возникновение запроса к базе данных - это событие). Тогда поток запросов к базе простейший (экспоненци­альное распределение интервала поступления). Поэтому выполня­ются условия, при которых справедлива следующая формула для оценки средней задержки запросов в очереди (формула Поллачека-Хинчина):

,

где t_q - искомая средняя задержка в очереди;

t_s - среднее время обслуживания;

r - загрузка обслуживающего узла;

с_s - коэффициент вариации времени обслуживания.

Если известно среднеквадратичное отклонение времени обслу­живания s_s, то с_s=s_s/t_s. В трех рассмотренных случаях t_s=5 с.

Загрузка не изменяется, так как поток запросов к базе данных тот же самый. Однако разброс значений в первом случае примерно в 3 раза больше, чем в третьем. Соответственно может быть больше при­близительно в 9 раз (т.е. на порядок!), а это часть множителя в чис­лителе формулы.

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

5. Инструментальные средства моделирования

Универсальным инструментальным средством создания моделей являются языки программирования общего пользования (Pascal, C/C++ и др.). На основе этих языков в настоящее время бурное развитие получили средства визуального проектирования программ (Delphi, Visual C++), облегчающие выполнение некоторых трудоемких операций, например, создание интерфейса программы. Наряду с этим существует множество специализированных средств моделирования, позволяющих быстрее и с меньшими затратами (по сравнению с универсальными языками программирования) создавать и исследовать модели. В развитии специализированных средств можно выделить два направления:

1. Средства моделирования для анализа достаточно широкого класса систем. К ним относятся языки имитационного моделирования (GPSS, SIMSCRIPT и др.), пакеты прикладных программ, использующих для моделирования аналитические методы, такие как MathCad, MathLab, SAS и др. Основным недостатком этих средств является то, что их применение требует от исследователя специальной подготовки.

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

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

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

1. Формулирование проблемы: описание исследуемой проблемы, установление границ и ограничений моделируемой системы, определение целей исследования.

2. Разработка модели: переход от реальной системы к некоторой логической схеме (абстрагирование).

3. Подготовка данных: отбор данных, необходимых для построения модели, и представление их в соответствующей форме.

4. Трансляция модели: описание модели на языке имитационного моделирования.

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

6. Планирование: определение условий проведения машинного эксперимента с имитационной моделью.

7. Экспериментирование: многократный прогон имитационной модели на компьютере для получения требуемой информации.

8. Анализ результатов: изучение результатов имитационного эксперимента для подготовки выводов и рекомендаций по решению проблемы.

9. Реализация и документирование: реализация рекомендаций, полученных на основе имитации, и составление документации по модели и ее использованию.

Таким образом, языки имитационного моделирования позволяют за сравнительно короткий срок составлять программные модели довольно сложных систем. К сожалению, такие модели обладают низкой способностью отвечать на вопросы типа "а что, если...", поскольку это именно те вопросы, которые наиболее полезны, так как они способствуют более глубокому пониманию проблемы и поиску лучших способов оценки возможных действий. Для ответа на подобные вопросы часто приходится непосредственно изменять программный код модели, что повышает затраты времени на анализ системы. При использовании языков имитационного моделирования возникает также другая проблема: затраты на изучение и освоение языка, тем более, что эти языки оперируют абстрактными понятиями, в то время как экспериментатор часто является специалистом в той области, которой принадлежит моделируемая система, и применяет специфическую терминологию, что может значительно осложнить освоение языка исследователем.

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

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

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

Архитектуру языка имитационного моделирования можно представить следующим образом:

1. Объекты моделирования описываются с помощью некоторых атрибутов языка;

2. Атрибуты взаимодействуют с процессами, адекватным реально протекающим явлениям в моделируемой системе;

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

4. Условия влияют на события, имеющие место внутри объекта моделирования и при взаимодействии с внешней средой;

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

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

Основные функции моделирующей системы:

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

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

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

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

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

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

Транзакт может выполнять следующие действия:

· Порождать группы (семейства) других транзактов;

· Поглощать другие транзакты конкретного семейства;

· Захватывать ресурсы и использовать их некоторое время, а затем освобождать;

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

Основные параметры транзактов:

· Уникальный идентификатор транзакта;

· Идентификатор (номер) семейства, к которому принадлежит транзакт;

· Наборы различных ресурсов, которые транзакт может захватывать и использовать какое-то время;

· Время жизни транзакта;

· Приоритет – неотрицательное число;

· Параметры обслуживания в каком-либо обслуживающем устройстве (включая вероятностные характеристики).

Примеры транзактов:

- телекоммуникационный пакет;

- покупатель;

- заявка на товар;

- автомобиль;

- обрабатываемая деталь;

- работник и т.д.

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

4. Событие – факт входа из узла одного транзакта. Разработчик модели практически не может управлять событиями вручную. Функция управления событиями отдана специально управляющей программе – координатору, автоматически внедряемому в состав модели.

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

6. Пространство – географическое, декартова плоскость. Узлы, транзакты и ресурсы могут быть привязаны к точкам пространства и мигрировать в нем.

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

Управление модельным временем

Одной из наиболее важных задач при создании модели является реализация двух функций: 1) корректировка временной координаты состояния системы ("продвижение" времени, организация "часов"); 2) обеспечение согласованности различных блоков и событий в системе (синхронизация во времени, координация с другими блоками).

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

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

Состояние системы характеризуется вектором состояний Z(t). Организуем счетчик системного времени, который в начальный момент показывает время t₀. Прибавим интервал времени Dt, тогда счетчик будет показывать t₁= t₀ +Dt. Вычислим значения Z(t₀ +Dt), затем перейдем к моменту времени t₂= t₁ +Dt и т.д. Если шаг Dt достаточно мал, то таким путем можно получать приближенные значения Z.

Рассмотренный принцип построения моделирующих алгоритмов называется принципом Dt. Это наиболее универсальный принцип, позволяющий определить последовательные состояния процесса функционирования системы через заданные интервалы времени Dt. Но с точки зрения затрат машинного времени он иногда оказы­вается неэкономичным.

При рассмотрении процессов функционирования некоторых си­стем можно обнаружить, что для них характерны два типа состоя­ний: 1) особые, присущие процессу функционирования системы то­лько в некоторые моменты времени (моменты поступления входных или управляющих воздействий, возмущений внешней среды и т. п.);

2) неособые, в которых процесс находится все остальное время. Особые состояния характерны еще и тем обстоятельством, что функции состояний Z(t) в эти моменты времени изменяются скач­ком, а между особыми состояниями изменение координат Z(t) происходит плавно и непрерывно или не происходит совсем. Таким образом, следя при моделировании системы только за ее особыми состояниями в те моменты времени, когда эти состояния имеют место, можно получить информацию, необходимую для построения функций Z(t). Очевидно, для описанного типа систем могут быть построены моделирующие алгоритмы по «принципу особых состо­яний». Обозначим скачкообразное (релейное) изменение состояния z как dz, а «принцип особых состояний» — как принцип dz.

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

Отметим, что характеристики процесса функционирования таких систем с особыми состояниями оцениваются по информации об особых состояниях, а неособые состояния при моделировании не рассматриваются. «Принцип dz » дает возможность для ряда систем существенно уменьшить затраты машинного времени на реализа­цию моделирующих алгоритмов по сравнению с «принципом Dt». Логика построения моделирующего алгоритма, реализующего «принцип dz», отличается от рассмотренной для «принципа Dt» только тем, что включает в себя процедуру определения момента времени t_d, соответствующего следующему особому состоянию си­стемы. Для исследования процесса функционирования больших систем рационально использование комбинированного принципа построения моделирующих алгоритмов, сочетающего в себе пре­имущества каждого из рассмотренных принципов.

Рассмотрим соответствующие способы управления временем в модели системы на примере, показанном на рис. 5.2, где по оси реального времени отложена последовательность событий в системе {s_i} во времени, причем события s₄ и s₅, происходят одновременно (рис. 5.2, а). Под действием событий s_i, изменяются состояния модели z_i, в момент времени t_zi, причем такое изменение происходит скачком dz.

В модели, построенной по принципу Dt (рис. 5.2, б), моменты системного времени будут последовательно прини­мать значения t^’₁ = Dt, t^’₂ =2 Dt, t^’₃ =3 Dt, t^’₄ =4 Dt, t^’₅ =5 Dt. Эти моменты систем­ного времени t^’_j(Dt) никак не связаны с моментами появления событий, ко­торые имитируются в модели системы. Системное время при этом получает постоянное приращение, выбираемое и задаваемое перед началом имитаци­онного эксперимента.

В модели, построенной по «принципу dz» (рис. 5.2, в), изменение времени наступает в момент смены состояния системы, и последовательность моментов системного времени имеет вид t^’’₁ = t_z1, t^’’₂ = t_z2, t^’’₃ = t_z3, t^’’₄ = t_z4, t^’’₅ = t_z5, т.е. моменты системного времени t^’’_k (dz) непосредственно связаны с моментами появления событий в системе s_i.

У каждого из этих методов есть свои преимущества с точки зрения адекватного отражения реальных событий в системе и за­трат машинных ресурсов на моделирование. При использовании «принципа dz» события обрабатываются последовательно и время смещается каждый раз вперед до начала следующего события. В модели, построенной по «принципу Dt», обработка событий про­исходит по группам, пакетам или множествам событий. При этом выбор Dt оказывает существенное влияние на ход процесса и резуль­таты моделирования, и если Dt задана неправильно, то результаты могут получиться недостоверными, так как все события появляются в точке, соответствующей верхней границе каждого интервала мо­делирования. При применении «принципа dz» одновременная об­работка событий в модели имеет место только тогда, когда эти события появляются одновременно и в реальной системе. Это позволяет избежать необходимости искусственного введения ран­жирования событий при их обработке в конце интервала Dt.

При моделировании по «принципу Dt» можно добиться хорошей аппроксимации: для этого Dt должно быть малым, чтобы два неодновременных события не попали в один и тот же временной интервал. Но уменьшение Dt приводит к увеличению затрат машин­ного времени на моделирование, так как значительная часть тратит­ся на корректировку «часов» и отслеживание событий, которых в большинстве интервалов может и не быть. При этом даже при сильном «сжатии» Dt два неодновременных события могут попасть в один и тот же временной интервал Dt, что создает ложное представление об их одновременности.

Для выбора принципа построения машинной модели необходимо знать: цель и назначение модели; требуемую точность результатов моделирования; затраты машин­ного времени при использовании того или иного принципа; не­обходимый объем машинной памяти для реализации модели, построенной по принципу Dt и dz; трудоемкость программирования и отладки.

Способы управления временем в модели системы

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

Рассмотрим, как реализован механизм протяжки модельного времени в системе СИМПАС. С понятием "модельное время" связана переменная SYSTIME, значе­ние которой показывает модельное время. При моделировании модель­ное время может меняться быстрее или медленнее, чем в реальной сис­теме. Это зависит от степени детализации модели и сложности описа­ния изучаемого процесса. В любом случае модельное время изменяется при выполнении некоторых событий, а события в системе моделирова­ния возникают в результате перемещения транзактов. Причиной изме­нения модельного времени может послужить явная задержка транзакта на некоторый отрезок модельного времени в процедуре DELAYT. Алгоритм изменения модельного времени реализован процедурой PLAN. Приведем общую схему протяжки модельного времени.

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

Рассмотрим транзакт, проходящий некоторую цепочку событий. Речь идет об активном транзакте, таким может быть только один тран­закт в модели, а именно тот, который продвигается в настоящий мо­мент времени по модели. Активный транзакт может перемещаться от события к событию, вызывая выполнение связанных с событиями дей­ствий (рис. 8). Значение модельного времени SYSTIME изменяться не будет до тех пор, пока транзакт остается активным. Прекратить актив­ность транзакта может некоторое событие. Таким событием, например, может быть явная задержка транзакта процедурой DELAYT. В этом случае активный транзакт помещается в список будущих событий (FUTURE), где он занимает место среди транзактов, ожидающих своего времени продвижения. Другим событием, прекращающим активность транзакта, может быть попытка поступить в занятый прибор. В этом случае транзакт должен быть помещен в список ожидающих освобождения прибора. Некоторые другие события могут также прекращать активность транзакта. После того, как такое событие произош­ло, активным должен стать другой транзакт.

Если в системе имеются другие транзакты, способные к продвиже­нию в данный момент времени, то они находятся в списке CURRENT; если этот список не пуст, то из него извлекается первый находящийся в нем транзакт и он ста­новится активным, по­сле чего продвигается по модели. Наконец наступит такой мо­мент, что ни одного транзакта в списке CURRENT не останет­ся; тогда и просматри­вается список FUTURE. Из него вы­бирается транзакт с минимальным "буду­щим временем про­движения", модельное время устанавливается равным времени продвижения этого тран­закта, а сам транзакт перемещается в спи­сок CURRENT. Вместе с ним в список CURRENT перемещаются все транзакты с таким же временем продвижения. После этого первый транзакт из списка CURRENT становится активным, и процесс моделирования продолжа­ется. Эта схема протяжки модельного времени далеко не полна, но тем не менее она отражает принцип изменения модельного времени.

Да

Нет

Да

Нет

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

Событийный и процессно-ориентированный подход к построению моделей

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

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

Событийный подход основан на формировании потока событий (рис. 5). Такой поток образует сгруппированные последовательности действий:

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

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

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