Файл: Конспект лекций Для студентов специальности 080801. 65 - приклад.doc

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

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

Часто рабочая нагрузка на систему определяется одним или не­сколькими распределениями вероятностей в отличие от заданных сценариев. Например, можно бросать монету каждые 15 мин на про­тяжении операции исследования системы, и если монета падает лице­вой стороной, то новая задача поступает в систему в этот момент времени. Если монета падает обратной стороной, то никакая задача не поступает в систему. Это пример метода розыгрыша случайной величины (метод Монте-Карло), который используется для модели­рования вероятностных систем.

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

Введем коэффициент вариации С как отношение стандартного отклонения к среднему:

гдеσ_x - среднеквадратичное отклонение для x.

Для экспоненциального закона распределенияС= 1, поскольку х и σ_x для этого закона равняется λ. Для регулярного детерминиро­ванного закона распределения С = О (σ_x =0).

Для системы G/G/1 среднее количество требований определяет­ся как

Используя результат Хинчина-Полячека, можно получить сред­нее время пребывания в одноканальной СМО по формуле

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

Обычно интересуются нормированным временем ожидания:

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

1.3. Основы дискретно-событийного моделирования смо

Определим основные понятия и термины, используемые в моде­лировании.

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

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

Состояние системы - множество переменных, которые содер­жат всю информацию, необходимую для описания свойств системы в любое время.

Объект - любой элемент или компонент в системе, который должен быть представлен в модели в явном виде (например, обслу­живающее устройство, клиент, машина).

Свойство или атрибут - свойства данного объекта (например, приоритет ожидающего клиента, маршрут процесса выполнения ра­бот в цеху).

Список - множество (постоянное или временное) связанных объектов, упорядоченное некоторым логическим способом (напри­мер, все клиенты, находящиеся в настоящее время в очереди ожида­ния, упорядочены по принципу «раньше прибыл, раньше обслужился» или по приоритету).

Событие - мгновенно возникающее изменение состояние сис­темы (например, прибытие нового требования).

Уведомление о событии - запись события, которое произойдет в потоке событий или в некотором будущем времени наряду с любы­ми связанными данными, необходимыми для обработки события (за­пись всегда включает тип события и время события).

Список событий - список намеченных будущих событий, упо­рядоченных по времени возникновения, известный также как список будущих событий (СБС).

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

Задержка - продолжительность времени неопределенного про­межутка, для которого неизвестно заранее, когда он заканчивается (например, задержка клиента в очереди по правилу «последний при­шел - первый обслужился», так как начало обслуживания зависит от будущих поступлений).

Модельное время - неотрицательная возрастающая величина, отражающая течение времени в имитационной модели.

Часы - переменная, отражающая протекание времени модели­рования, называется в примерах ЧАСЫ (CLOCK).

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

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

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

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

В табл. 1.1 представлены интервалы времени между приходами покупателей в магазин и требуемыми временами их обслуживания продавцом, а на рис. 1.3 проведено графическим методом «ручное» моделирование СМО с одним устройством.

С точки зрения объектного подхода имеются динамические объ­екты - требования (ПОКУПАТЕЛИ) и некоторый ресурс - устройст­во обслуживания (статический объект ПРОДАВЕЦ), которое они используют. Если требование претендует на ресурс, а он занят, то оно ' становится в ОЧЕРЕДЬ к ресурсу. ОЧЕРЕДЬ может быть отдельным объектом или просто списком, связанным с ресурсом. Примем за пра­вило обслуживания - FIFO.

Таблица 1.1

Для каждой пары «требование - ресурс» мы хотим определить, как долго требование j будет использовать ресурс R, т.е. необходимо определить интервал времени, когда требованию j назначен ресурс R и когда оно освободит этот ресурс. Однако, прежде чем ресурс будет назначен требованию j, он должен быть запрошен. В общем случае требование может ожидать в очереди до назначения ресурса.

Опишем алгоритм работы системы с точки зрения «жизненного цикла» ПОКУПАТЕЛЯ, т.е. от момента его прихода в магазин до мо­мента выхода из магазина. Так как покупатели непрерывно приходят в магазин на протяжении некоторого периода времени наблюдения за системой (время, в течении которого моделируется система), то необ­ходимо обеспечить поток ПОКУПАТЕЛЕЙ путем их создания в мо­дели (генерации в некоторые моменты времени - моменты их прихода в магазин). Для генерации ПОКУПАТЕЛЕЙ используем специаль­ную подпрограмму ГЕНЕРАТОР (в языке GPSS этой подпрограмме соответствует блок GENERATE). Алгоритм ее работы следующий:

1. Создать динамический объект ПОКУПАТЕЛЬ в виде струк­туры данных, включающей в себя поля: номер покупателя -j, момент его прихода –

t _j^вх, а также при необходимости свойства покупателя или его атрибуты (например, его приоритет). Запланировать событие - приход покупателя j на момент времени t _j^вх - т.е. создать уведом­ление о событии в СБС.

2. Запланировать следующее событие для покупателя j -ЗАПРОС-НАЗНАЧЕНИЕ ресурса R (ПРОДАВЦА) на момент време­ни t _j^вх. Запланировать приход следующего динамического объекта ПОКУПАТЕЛЬ j + 1, т.е. определить событие прихода следующего покупателя t _j+1^вх:= t _j^вх + t _j ^об.