 |
Схемы построения моделирующего алгоритма
|
|
|
|
Наряду с рассмотренной выше схемой событий, большое распространение получила и схема процессов. Прежде чем рассматривать эту схему процессов, сформулируем необходимые понятия: событие, работа, процесс и др.
Событие - это изменение в системе, относящееся к какому-то моменту времени. Применительно к модели это - скачкообразное изменение одной или нескольких дискретных величин либо достижение непрерывно.изменяющихся величиной заданной границы. Примеры событий: поступление заявки, освобождение прибора, наступление срока хранения скоропортящегося продукта.
Работа - действие, происходящее в моделируемой системе в течение определенного промежутка времени. Примеры: подготовка заявки, обслуживание заявки в приборе. Время, требующееся для работы, может быть случайной величиной, но к моменту имитации работы случайная величина должна получить конкретное значение (с помощью датчика случайных чисел). Работа начинается и заканчиваются событиями.
Отвлечемся слегка, чтобы на основе понятий работы и события подчеркнуть различие между системным временем и машинным временем. В моделируемой системе событие происходит мгновенно, а работа требует времени (системного). В имитационной модели картина обратная: на имитацию события затрачивается некоторое машинное время, а имитация работы практически не требует машинного времени, так как имитируется не сама работа, а завершающее ее событие.
Как правило, для начала работы требуется наличие определенных условий. Например, чтобы начать кирпичную кладку, требуются кирпичи, раствор и рабочий-каменщик. При моделировании дискретных процессов в качестве условий чаще всего рассматривается наличие ресурсов. Например, чтобы начать обслуживание заявки, требуется наличие свободного прибора. Ресурс можно понимать как оборудование, необходимое для выполнения работы (станок, прибор), но это может быть и работник. Для ресурса характерно, что он занимается в момент начала работы (или заранее) и освобождается в момент ее окончания.
|
|
|
Процесс - последовательность событий и работ, описывающая поведение во времени какого-либо объекта в моделируемой системе. Приведем три примера.
Процесс "генерирование заявок источником":
подготовка заявки (работа);
выдача заявки (событие).
Процесс "прохождение заявки":
занятие прибора (событие);
обслуживание заявки в приборе (работа),
освобождение прибора (событие).
Процесс "обработка детали на станке":
занятие рабочего (событие),
занятие станка (событие);
обработка детали (работа);
освобождение станка (событие),
контрольные измерения (работа)",
освобождение рабочего (событие).
Каждая работа или событие - это фаза процесса. Имитация процесса на ЭВМ производится по фазам. Фаза имитируется без прерывания, но по окончании имитации фазы возможно прерывание и переход к имитации другого процесса.
Опираясь на введенные понятия, рассмотрим основные черты схемы событий и схемы процессов, их положительные и отрицательные стороны.
При моделировании по схеме событий понятия работы и процесса не используются. Выделяется несколько событий так, чтобы они исключали друг друга и в совокупности охватывали все возможные изменения в системе. это напоминает разбиение множества элементарных событий на непересекающиеся подмножества (события) в теории вероятностей с той разницей, что событие - это не только подмножество элементарных событий, но и причинно-следственные связи между элементарными событиями. Например, при моделировании СМО событие "поступление заявки" охватывает несколько элементарных событий: выдача заявки источником, занятие прибора, начало обслуживания, потеря заявки (в случае отсутствия свободного прибора). Видно, что элементарные события взаимосвязаны; если не удастся занять прибор, то обслуживание не начнется, а произойдет потеря заявки. В алгоритме имитации отражаются не все элементарные события, а только те, без которых невозможно построение реализации, обеспечивающее нахождение искомых характеристик.
|
|
|
Основная трудность при разработке модели по схеме событий - выделение типов событий и составление алгоритмов для каждого типа так, чтобы не упустить каких-то нужных элементарных событий и правильно учесть взаимосвязи.
Каждому типу события соответствует блок в алгоритме имитации, а каждому событию - определенное место в календаре. Алгоритм шага состоит в выяснении типа очередном события (с помощью календаря) и выполнении тех блоков алгоритма, которые соответствуют этому типу события
При моделировании по схеме процессов за основу берется понятие процесса. Процесс отражает поведение одного объекта (источника, заявки, детали, рыси, зайца и т.п.), а объектов в системе много. Поэтому параллельно развиваются несколько процессов. Их имитация производится поочередно (на одном процессоре). Если бы процессы были независимы, можно было бы имитировать до конца один процесс, а потом переходить к имитации другого процесса. Однако процессы пользуются общими ресурсами. Если очередная фаза процесса состоит в занятии ресурса, а свободного ресурса нет, процесс приостанавливается и ждет освобождения ресурса. При этом ЭВМ переходит к имитации другого процесса. Таким образом, ЭВМ поочередно продвигает процессы на одну или несколько фаз, учитывая их взаимодействие во времени и в использовании общих ресурсов.
Продвижение процессов по системному времени можно осуществлять по принципу Dt или по принципу особых моментов. По тем же соображениям, что приводились выше, будем придерживаться принципа особых моментов. Какому процессу отводится место в календаре, где указывается, с какой фазы надо начать или продолжить имитацию процесса и к какому моменту системного времени это событие относится.
|
|
|
Процессы могут быть постоянными (т.е. развиваться бесконечно долго) и временными. Временный процесс создается в некоторый момент времени, существует какое-то время, после чего ликвидируется. Одна из фаз процесса может представлять собой создание нового процесса. В связи с существованием временных процессов количество заполненных мест в календаре оказывается переменным. Признаком свободного места в календаре может быть нуль в ячейке, отведенной для обозначения (метки) очередной фазы процесса. Если число одновременно существующих временных процессов не имеет ограничения сверху, число мест в календаре отводится с большим запасом, а в случае переполнения календаря должно выдаваться соответствующее сообщение. При создании процесса отыскивается свободное место в календаре, и номер этого места становится номером процесса. После ликвидации процесса его место в календаре освобождается.
За один шаг (основной цикл в алгоритме) производится поочередный просмотр всех процессов и имитация тех из них, для которых созрели условия, в частности наступило время исполнения очередной фазы. В ходе имитации очередной фазы процесса мотет освободиться ресурс которого не хватало для имитации ранее просмотренных процессов. Кроме того, может быть создан процесс и помещен на свободное место в календаре под меньшим номером, чем текущий процесс. В обоих случаях требуется повторный просмотр процессов в рамках того же шага. Для организации повторного просмотра удобно использовать флаг - двоичную переменную. Этой переменной перед началом просмотра присваивается значение единицы ("подъем" флага). Освобождение ресурса или создание нового процесса влечет за собой "сброс" флага в нуль. Завершение шага и переход к следующему шагу производится только если флаг остался поднятым.
Отметим теперь, что термин "процесс" имеет два разных смысла: процесс как алгоритм и процесс как структура данных. Процесс как алгоритм относится ко всему множеству процессов одинакового типа, а процесс как структура данных описывает конкретного представителя этого множества. Например, процесс "генерирование заявок J-м источником" может отражаться следующими величинами (их часто называют атрибутами процесса):
|
|
|
- номер источника (J);
- емкость источника (максимальное число заявок в нем);
- приоритет, присвоенный, заявками этого источника;
- среднее время подготовки заявки источником;
- среднее время обслуживания заявки этого источника в приборе;
- число заявок в источнике в данный момент
- предстоящий момент выдачи очередной заявки.
- метка очередной фазы процесса.
Первые пять величин постоянны (но у каждого источника имеют свои значения), остальные три меняются в ходе имитации. Две последние - компоненты календаря, эта совокупность данных занимает определенную группу ячеек в памяти ЭВМ. Номер этой группы - это номер процесса. О требуемом количестве групп можно сказать то же, что сказано выше о требуемом числе мест в календаре и о возможности переполнения.
Процесс "генерирование заявок источником", понимаемый как алгоритм, существует в виде части программы моделирования. Когда эта часть программы выполняется, она использует значения атрибутов для конкретного источника. Создание процесса - это заполнение группы ячеек атрибутами этого процесса. Имитация процесса сопровождается изменением переменных атрибутов. Ликвидация процесса означает освобождение группы ячеек, занятых атрибутами.
Чтобы различать указанные два смысла, можно поступить двояко. Первый путь: термин процесс оставить за алгоритмом, а структуру данных называть экземпляром процесса. Второй путь: термин процесс применять к структуре данных, а алгоритм называть классом процессов. Будем далее придерживаться второго пути. В языках моделирования применяется и другие термины, но они не использует слово процесс, которое желательно сохранить.
Часть программы, управляющая динамикой модели, т.е. последовательностью выполнения отдельных блоков программы в процессе имитации, носит название монитор. Рассматриваемые схемы построения моделирующего алгоритма (схема событий и схема процессов) имеют существенные различия, но принцип построения монитора у них одинаковый - повелительный. Повелительный (императивный) принцип состоит в том, что для предстоящих событий заранее определяется время их наступления (оно записываются в календарь), и события имитируются, когда приходит их время. Календарь как бы предписывает, в какие моменты должны происходить события, в каком порядке их имитировать - отсюда и название принципа. События, которые запланированы на один и тот же момент времени, могут имитироваться в любом порядке. То обстоятельство, что при использовании принципа процессов некоторые события "забегают вперед", не меняет сути монитора: в пределах одного процесса последовательность событий не нарушается, а ее нарушение между событиями носит временный характер (сначала один процесс забегает вперед, потом другой). Главное - для всех событий указано время, когда они должны произойти.
|
|
|
С целью дополнительного пояснения заметим, что повелительный принцип ассоциируется с синхронными процессами. Синхронные процессы управляются внешними часами: события в них происходят в заранее заданные моменты времени. Повелительный принцип построения монитора применен в алгоритме моделирования СМО по схеме событий и достаточно ясен из этого примера.
После сказанного о принципах событий и процессов естественно посмотреть, как будут выглядеть алгоритмы моделирования, составленные по схеме событий и по схеме процессов. Рассмотрим примеры этих алгоритмов.
|
|
|
