Моделирование систем массового обслуживания
Методика построения программной модели
Для разработки программной модели исходная система должна быть представлена как стохастическая СМО. Это объясняется следующим: информация от внешней среды поступает в случайные моменты времени, длительность обработки различных типов информации в общем случае также является различной. Таким образом, внешняя среда может быть отображена как генератор сообщений, а комплекс ВС – обслуживающими устройствами.
Обобщенная структурная схема ВС.
![]()
![]()
![]()
![]()
![]()
![]()
![]()
![]()
![]()
![]()
![]()
![]()
![]()
![]()
![]()
![]()
![]()
![]()
![]()
![]()
![]()
![]()
![]()
![]()
![]()
![]()
![]()
![]()
![]()
![]()
![]()
![]()
![]()
![]()
![]()
ИИ – источники информации – выдают на вход буферной памяти независимые друг от друга сообщения. Закон появления сообщений - произвольный.
В БП (буферной памяти) сообщения записываются «в навал» и выбираются по одному в обслуживающий аппарат по принципу FIFO/LIFO. Длительность обработки одного сообщения в ОА (обслуживающий аппарат) в общем случае может быть случайной, но закон обработки всегда должен быть задан. Т.к. быстродействие ОА ограничено, то на входе системы в БП возможно сложение данных, ожидающих обработку.
ПБССт - программный блок сбора статистики.
Блок синхронизации необходим, чтобы система заработала.
Моделирование потока сообщений.
Поток сообщений обычно моделируется моментами появления очередного сообщения в потоке. Текущий момент времени появления очередного сообщения:
![]()
где Ti – интервал времени между появлением i-го и (i-1)-го сообщения.
Процедура.
обращение к процедуре выражения случайного числа Rnd

|
Вид распределения |
Выражение |
| равномерное на [a,b] |
|
| нормальное |
|
| экспоненциальное |
|
| Эрланга |
|
Моделирование работы Обслуживающего Аппарата.
Программа – имитатор работы ОА представляет собой комплекс, вырабатывающий случайные отрезки времени, соответствующие длительностям обслуживания требований. Например, если требования от источника обрабатываются в ОА по нормальному закону с параметрами Mx и sx, то длительность обработки i-ого требования:
![]()
Схема алгоритма имитатора.
Ri – случайное число с равномерным законом распределения
ТОБР – время обработки очередного сообщения
T – время освобождения ОА
XM – Мат ожидание для заданного закона обратки
DX – СКО для заданного закона обратоки
![]()
Моделирование работы абонента
Абонента можно рассматривать как ОА, поток информации на который поступает от процессора. Для моделирования работы абонентов необходимо вырабатывать длительности обслуживания требований. Кроме того, абонент сам может быть источником заявок, претендуя на те или иные ресурсы вычислительной системы. Эти заявки могут имитироваться с помощью генератора сообщений по наперед заданному закону. Таким образом, абонент либо имитируется как ОА, либо как генератор.
Моделирование работы буферной памяти
Блок буферной памяти должен производить запись и считывания числа, выдавать сигналы переполнения и отсутствия данных. В любой момент времени располагать сведениями о количестве требований в блоке. Сама запоминающая среда имитируется некоторым одномерным массивом, размер которого определяет размер БП. Каждый элемент этого массива может быть либо свободен, либо занят.
![]()
![]()
![]()
![]()
![]()
![]()
![]()
![]()
![]()
![]()
![]()
![]()
![]()
![]()
![]()
![]()
![]()
![]()
![]()
![]()
![]()
![]()
![]()
![]()
![]()
![]()
![]()
![]()
![]()
![]()
![]()
![]()
![]()
![]()
![]()
![]()
![]()
![]()
![]()
![]()
![]()
![]()
![]()
![]()
![]()
![]()
![]()
![]()
![]()
![]()
![]()
![]()
![]()
![]()
![]()
![]()
![]()
![]()
| P | массив сообщений | LM | объем буферной памяти |
| WYB |
признак обращения к буф. памяти = 1 – режим выборки сообщений = 0 – режим записи |
NPOS | номер последнего сообщения, поступившего в память |
| NP | число сообщений в памяти | NPER | номер первого сообщения в памяти |
| POLN |
признак переполнения памяти = 1 – нет свободных ячеек |
PUST |
признак отсутствия сообщений = 1 – в памяти нет сообщений |
| NPOS |
= NPOS + 1, если NPOS < LM = NPOS – LM + 1, иначе |
NPER |
= NPER – 1, если NPER < 1 = NPER – LM + 1, иначе |
| X | ячейка для сообщения |
Разработка программы сбора статистики
Задача блока статистики заключается в накоплении численных значений, необходимых для вычисления статистических оценок заданных параметров моделируемой системы.
При моделировании работы простейшей СМО обычно интерес представляет среднее время ожидания в очереди. Для каждого сообщения время ожидания в очереди равно разности между моментами времени, когда оно было выбрано на обработку ОА, и моментом времени, когда оно пришло в систему от источника информации.
Суммируя значения количества сообщений в БП через небольшие промежутки времени и разделив на число суммирований, получим среднее значение длины очереди в памяти.
Коэффициент загрузки ОА определяется как отношение времени работы ОА к общему времени моделирования.
Разработка управляющей программы имитационной модели
Если программа - имитатор работы источника обслуживающего аппарата или памяти моделирует работу отдельных устройств, то управляющая программа имитирует алгоритм взаимодействия элементов системы. Управляющая программа реализуется в основном по двум принципам:
принцип Dt
событийный принципПринцип Dt.
Принцип заключается в последовательном анализе состояний всех блоков в момент t+Dt по заданному состоянию блоков в момент t. При этом новое состояние блоков определяется в соответствии с их алгоритмическим описанием с учетом действия случайных факторов, задаваемых распределением вероятностей. В результате этого анализа принимается решение о том, какие общесистемные события должны имитироваться в программной модели на данный конкретный момент времени.
Основной недостаток в том, что происходят значительные затраты машинного времени на реализацию исследования системы. При недостаточно малом Dt появляется опасность пропуска отдельных событий в системе, что приводит к получению неправильных результатов.
Событийный принцип
Характерное свойство моделируемых систем – состояние отдельных устройств изменяется в дискретные моменты времени, которые совпадают с моментами поступления сообщений в систему, моментами окончания решения задач, моментами возникающих аварийных сигналов и т.д. Поэтому, моделирование и продвижение текущего времени в системе удобно проводить использую событийный принцип, при котором состояние всех блоков системы анализируется лишь в момент наступления какого-либо события. Момент наступления следующего события определяется минимальным значением из списка будущих событий, представляющих собой совокупность моментов ближайшего изменения состояний каждого из блоков системы.
t11, t12 – моменты появления сообщений на выходе генератора (источника информации)
b1 – интервал времени обслуживания первого сообщения
t3 n – момент сбора статистики
t41 – момент окончания моделирования
Методика реализации событийной модели
Для всех активных блоков (блоков, порождающих события) заводя свой элемент в одномерном массиве – списке будущих событий.
В качестве подготовительной операции в список будущих событий SBS заносят время ближайшего события от любого активного блока. Активизируя программу-имитатор, ИИ вырабатывает псевдослучайную величину a0, определяющую момент появления первого сообщения t11. Эту величину заносят в список будущих событий.
Активизируя программу-имитатор, ОА вырабатывает псевдослучайную величину b0, определяющую момент времени t21, которую также заносят в SBS.
Момент времени t31 (1ый сбор статистики) определяется равным стандартному шагу сбора tСТАТ, и заносится в SBS
В SBS заносится t41 – время окончания моделирования.
Подготовительная часть на этом закончена и начинается протяжка модельного времени.
В SBS определяется минимально числовое значение и его номер.
Реализуется событие, порождаемое блоком с соответствующим номером, т.е. модельное время = t11. Далее реализуется событие с номером 1, связанное с появлением нового сообщения в ИИ. Реализация этого события заключается в том, что само сообщение записывается в память, а с помощью имитатора ИИ, вырабатывается момент появления следующего события t12. Это время помещается в соответствующую ячейку SBS место t11.
Затем вновь организуется поиск минимального элемента в SBS. Для данного примера реализуется событие 3, после чего выражение момента времени t32 – новое время сбора статистики. Так до тех пор, пока минимально время не станет равным t41.
Философские аспекты моделирования
Объектом называется всё то, на что направлена человеческая деятельность.
В научном исследовании большую роль играет понятие гипотезы – определенное предсказание, основанное на небольшом количестве опытных данных, наблюдениях, догадках. Быстрая проверка гипотезы может быть проведена в ходе специально поставленных экспериментов.
При формировании и проверке правильности гипотезы в качестве метода суждения используется аналогия. Аналогией называется суждение о каком либо частном сходстве двух объектов.
Современные научные гипотезы создаются как правило по аналогии проверенным на практике положениям. Таким образом, аналогия связывает гипотезу с экспериментом.
Гипотезы и аналогии, отражающие реальный объктивно-существующий мир, должны обладать наглядностью или сводиться к удобным для исследования логическим схемам. Такие логические схемы, упрощающие рассуждения и позволяющие проводить эксперименты, уточняющие природу явлений, называются моделями.
Модель – объект - заместитель объекта оригинала, обеспечивающий изучение некоторых свойств оригинала.
Замещение одного объекта другим с целью получения информации о важнейших свойствах объекта-оригинала с помощью объекта-модели называется моделированием.
Классификация видов моделирования
В зависимости от характера изучаемых процессов в некоторой сложной системе все виды моделирования можно разделить.
Детерминированное Стохастическое
Статическое Динамическое
Дискретное Непрерывное
Дискретно-непрерывное
Математическое Физическое
Аналитическое Имитационное В реальном масштабе времени
Комбинированное В нереальном масштабе времени
Детерминированное моделирование отображает детерминированные процессы, т.е. такие, в которых отсутствуют всякие случайные воздействия.
Стохастическое моделирование отображает случайные, вероятностные процессы и события.
Статическое служит для описания сложной системы в конкретный момент времени.
Динамическое отражает поведение системы во времени.
Дискретное моделирование используется для описания процессов, происходящих в дискретные моменты времени.
Непрерывное используется для описание непрерывных во времени процессов.
Дискретно-непрерывное используется для тех случаев, когда хотят отразить наличие как дискретных, так и непрерывных процессов в системе.
Под математическом моделированием будем понимать процесс установления данному реальному объекту некоторого математического объекта, называемого математической моделью и исследование этой модели, позволяющее получить характеристики реального объекта. Любая математическая модель, как и всякая другая, описывает реальный объект лишь с некоторой степенью приближения.
Для аналитического моделирования характерным является то, что процессы функционирования элементов системы записываются в виде некоторых функциональных соотношений (алгебраических, интегрально-дифференциальных, конечно-разностных и т.д.) или логических условий.
Аналитические модели могут быть исследованы тремя способами:
Аналитическим. Получение в общем виде зависимости выходных характеристик от исходных.
Численным. Нельзя решить сложные уравнения в общем виде. Результаты получают для конкретных начальных данных.
Качественным. Нет возможности получения конкретных решений, но можно выделить некоторые свойства объектов или решений уравнений, например, оценить устойчивость решения.
При имитационном моделирование алгоритм, реализующий модель, воспроизводит процесс функционирования системы во времени. Имитируются элементарные явления, составляющие процесс, с сохранением логической структуры объекта и последовательности протекания процесса во времени. Это позволяет по исходным данным получить сведения о состоянии процесса в определенные моменты времени. Преимуществом имитационного моделирования является возможность решения более сложных задач.
Имитационные модели позволяют достаточно просто учитывать такие факторы, как наличие дискретных и непрерывных элементов, нелинейные характеристики системы, многочисленные случайные воздействия. Когда результаты, полученные имитационной моделью, являются реализацией случайных величин и функций, то для нахождения характеристик процесса функциональной системы необходимо его многократное воспроизведение с последующей статистической обработкой.
Комбинированное моделирования при анализе сложных систем позволяет объединить достоинства отдельных методов. В нем проводят декомпозицию процесса функционирования сложной системы на подпроцессы и для тех, где можно используют аналитические модели, где нельзя – имитационное моделирование.
Технические средства математического моделирования
Цифровая техника
Цифровая техника является дискретной. Основная проблема – быстродействие (не догнать реальное время) слишком сложен механизм.
Аналоговая техника.
В отличие от дискретной техники в основе аналоговой лежит принцип моделирования, а не счета. При использовании в качестве модели некоторой задачи электронных цепей, каждой переменной величине ставится в соответствие определенную переменную величину электрической цепи. При этом основой построения такой модели является изоморфизм - подобие исследуемой задачи и соответствующей электрической модели. При определении критерия подобия используют специальные приемы масштабирования, соответствующие заданным параметрам.
Согласно своим вычислительным возможностям АВМ наиболее приспособлены для исследования объектов, динамика которых описывается обыкновенными дифференциальными уравнениями и уравнениями в частных производных, реже - алгебраическими, следовательно, АВМ можно отнести к классу специальных машин.
В общем случае под АВМ понимаем совокупность электрических элементов, организованных с систему, позволяющих изоморфно моделировать динамику изучаемого объекта. Функциональные блоки АВМ должны реализовывать весь комплекс арифметико-логических операций.
АВМ делятся по мощности (степень дифференциальных уравнений):
малые ( n Ј 10 )
средние ( 10 Ј n Ј 20 )
большие ( n і 20 )
![]()
![]()
![]()
![]()
![]()



![]()
![]()
![]()



Гибридные ВМ
Широкий класс ВС, использующий как аналоговый, так и дискретный метод представления и обработки информации.
Подклассы гибридных ВМ:
АВМ с цифровыми методами численного анализа
АВМ, программируемые с помощью ЦВМ
АВМ с цифровым управлением и логикой
АВМ
с цифровыми
элементами
(цифровые
вольтметры,
память)
ЦВМ с аналоговыми арифметическими устройствами
ЦВМ, допускающие программирование аналогового типа.
![]()
В
АВМ накладывают
и складывают
сигналы.
АВМ
Ы система
сопряжения
АВМ –ЦВМ.
ЦВМ Ы электрическая система согласования
Сравнительная характеристика АВМ и ЦВМ
|
Показатель |
АВМ |
ЦВМ |
| Тип информации | Непрерывный | Дискретный |
| Изменение значений | Величиной напряжения | Числовым значением |
| Базовые операции | Арифметические операции и интегрирование | Арифметические операции |
| Принцип вычисления | Высокопараллельный | Последовательно-параллельный |
| Режим реального времени | Без ограничений | Ограничен |
| Динамическое изменение решаемой задачи | Посредством системы коммутации | В диалоговом режиме |
| Требования к пользователю | Профессиональные знания, методика моделирования | Знание основ ПО ЭВМ |
| Уровень формализации задачи | Ограничен моделью решаемой задачи | Высокий |
| Способность к решению логических задач | Ограничена | Высокая |
| Точность | Ограничена (10-4) | Ограничена разрядностью (10-40) |
| Диапазон представления чисел | 1 … 10-4 |
Зависит от разрядности 10-40 … 1040 |
| Класс решаемых задач | Алгебраические и дифф. уравнения. | Любые |
| Специальные функции | Ограниченный набор | Неограниченный набор |
| Уровень миниатюризации | Ограничен | Высокий |
| Сфера применения | Ограничена | Практически любая |
| Пользовательский интерфейс | Низкий уровень | Высочайший уровень |
Основные понятия теории моделирования
Пусть задана сложная дискретная система S.
![]()
![]()
![]()

![]()


