Дискретно-событийное моделирование в см Марс для курса «Системы массового обслуживания»

УДК 004.492 Т.Е. Григорьева

Дискретно-событийное моделирование в СМ МАРС для курса «Системы массового обслуживания»

Рассмотрен алгоритм передачи сообщений, реализованный в имитационном ядре среды моделирования МАРС, в котором в формате метода компонентных цепей (МКЦ) реализуется алгоритм имитационного моделирования. Построена компьютерная модель «Светофор», представленная на трех взаимосвязанных уровнях: объектном, логическом и визуальном. Ключевые слова: системы массового обслуживания, дискретно-событийное моделирование, алгоритм передачи сообщений, многоуровневое моделирование.

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

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

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

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

В случае если пространственные координаты и время непрерывны - временная траектория системы (?, х(?)) определяет бесконечное, несчетное множество событий, случившихся за время наблюдения за системой на промежутке [0, Т] на множестве [хтт, хтах] всех наблюдавшихся явлений. В непрерывном случае говорят не о всем множестве событий, а лишь об отдельных событиях, называя их особыми, подчеркивая тем самым нечто важное для нас и системы.

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

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

Алгоритм передачи сообщений. Алгоритм передачи сообщений представляет собой программно-инструментальный аппарат, реализованный в имитационном ядре среды МАРС, в котором в формате метода компонентных цепей (МКЦ) реализуются методы имитационного моделирования алгоритмов. Их работа основана на обмене данными различных типов в виде сообщений соединенными друг с другом компонентами. На основе алгоритма передачи сообщений организована работа блоков функционирования виртуальных инструментов и приборов. Он также может лежать в основе моделирования информационных процессов между основными блоками технически сложной системы (ТСС).

Алгоритмы функционирования ТСС могут быть представлены имитационными компонентны -ми цепями (КЦ) вида

Сл=

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

Ка =

В — множество ветвей КЦ, образованных связями компонентов; N — множество узлов цепи СА; М — множество передаваемых по связям сообщений с данными, полученными на основе математической модели компонента:

У=ЩРА,Х),

где Ра — параметры компонента множества КА; X — входные данные компонента множества КА.

Каждый компонент множества КА представляет собой совокупность множеств:

Ка=

где Ра — набор параметров компонента, которые не зависят от данных, принятых в сообщении; Ъ — массив номеров ветвей компонента, заданных в локальном координатном базисе (ЛКБ) компонента; п — массив полюсов компонента в ЛКБ, предназначенных для образования соединений с другими компонентами; М - массив сообщений, размер которого соответствует количеству ветвей компонента.

Каждая ветвь Ъ., заданная в ЛКБ компонента множества КА, идентифицируется своим уникальным номером В. в глобальном координатном базисе (ГКБ) КЦ (1), хранящемся в массиве В размером сВ.

Каждый полюс множества п компонента КА может быть соединен только с одним узлом N. цепи СА, заданным в ГКБ. Набор номеров всех узлов в ГКБ представляется массивом номеров узлов N размером CN.

Каждое сообщение множества М представляется в виде

М =

где Б — данные любого типа, передаваемые в сообщении между компонентами; Т — тип передаваемых в сообщении данных; В — номер ветви в ГКБ цепи (1), с которой передается сообщение М узлу N N — номер узла в ГКБ КЦ (1), которому передается сообщение.

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

1) во время запуска или останова эксперимента, а также начала и завершения очередного вычислительного эксперимента при решении задач, основанных на многовариантном анализе модели объекта;

2) если пришло сообщение хотя бы на один из его входов от других компонентов множества КА;

3) если пришли сообщения на каждый из входов компонентов;

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

В перечисленных случаях выполняется алгоритм передачи сообщений (рис. 3), реализуемый в имитационном ядре среды МАРС. Алгоритм построен на основе анализа топологических свойств компонентов множества КА, которые описываются узловой матрицей А размером CNxCB, формируемой по следующему правилу:

А, . ={1 если ветвь г инцидентна узлу /,

} |0 если ветвь . не инцидентна узлу

где г = 1, СВ — номер соответствующей ветви; . = 1, CN - номер узла.

Алгоритм передачи сообщений [2] (рис. 1), позволяющий передавать данные различных типов между компонентами, математические модели которых могут быть записаны в явном виде, реализуется в имитационном ядре среды МАРС.

Во время запуска на моделирование один раз для всех алгоритмов производится формирование узловой матрицы А для компонентов множества КА с. СА (1).

В компоненте, в котором произошло срабатывание, формируется сообщение М (5), содержащее всю необходимую для передачи информацию М.Б типа М.Т. Также указываются топологические

признаки: ветвь И.В, с которой отправляется сообщение, и узел И.М, которому передается сообщение И.

Начало

Формирование узловой матрицы А для компонентов множества F

Путем проверки всех элементов столбца M.N матрицы A на равенство (1) производится выявление всех ветвей NB, которые подключены к узлу с номером M.N. При обнаружении каждой такой ветви с помощью функции SearchCompo-nent производится поиск компонента K1, кото -рому принадлежит ветвь с номером NB, заданным в ГБК цепи CA (1). С целью передачи сообщения М на определенную связь компонен-та с помощью функции NumberLKB производится поиск номера nb в ЛКБ компонента K1, соответствующего номеру NB в ГКБ цепи. После чего путем операции присваивания K1.M[nb] = M производится непосредственная передача сообщения присоединенному к узлу M.N компоненту. Данный алгоритм заканчивает работу после того, как были просмотрены все элементы столбца с номером M.N матрицы A.

С целью реализации данного алгоритма рассмотрим программно-алгоритмическую структуру обобщенного компонента множества KA и его связь с блоком моделирования процесса передачи сообщений.

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

- объектном уровне, представляющем модель «Светофор» в виде компонентной цепи (рис. 2), состоящей из таких компонентов, как: G - «Генератор фишек» - подает по одной фишке, через определенный промежуток времени; P - «Переключатель» - переключает кнопки через определенный промежуток времени; S - «Хранилище фишек» - хранит в себе фишки; A - «Кнопки» - кнопки с присвоением определенного цвета в данном случае (красного, желтого, зеленого);

- логическом уровне, на котором отображается текстовое или графическое (компонентное) представление алгоритма работы модели «Светофор».

Алгоритм передачи сообщений

Рис. 2. Компонентная цепь, моделирующая принцип работы модели «Светофор»

Текстовое отображение позволяет представить алгоритм работы модели «Светофор» в виде периодической функции light: light (i+T) = light(i), T = 3, I = 1, 2, 3, ...

green, i = 1; light(i) = < yellow, i = 2;

red, i = 3.

Графическое представление алгоритма работы модели «Светофор» приводится в виде графа, изображенного на рис. 3, где 1 - зеленый цвет, 2 - красный, 3 - желтый.

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

- визуальном уровне, где отображается модель «Светофор» (рис. 4).

Цвет фишек Предикат Цвет фишек

Р и с. 4. Принцип работы модели «Светофор»

Предикат

Цвет фишек

3

Рис. 3. Граф, отображающий принцип работы модели «Светофор»

Заключение. Аппарат сетей Петри интерпретирован в метод компонентных цепей (МКЦ) и реализован в среде моделирования МАРС [3], что позволяет решать как задачу о светофоре в сложной ситуации, так и построение других алгоритмов сложных технических объектов. Данная модель используется в качестве примера имитационного моделирования при обучении студентов по дисциплинам «Компьютерное моделирование» и «Моделирование систем» в автоматизированном учебно-методическом комплексе (АУМК) [4].

Литература

1. Колесов Ю.Б. Моделирование систем. Объектно-ориентированный подход / Ю.Б. Колесов, Ю.Б. Сениченков. - СПб.: БХВ-Петербург, 2006. - 192 с.

2. Дмитриев В.М. Компьютерная модель управляемых технически сложных объектов / В.М. Дмитриев, Т.В. Ганджа // Информатика и системы управления. - 2012. - № 3 (33). - С. 47-59.

3. Дмитриев В.М. Система визуализации и управления вычислительным экспериментом в среде многоуровневого моделирования МАРС / В.М. Дмитриев, Т.В. Ганджа, Т.Ю. Коротина // Доклады ТУСУРа. - 2010. - № 1 (21), ч. 2. - С. 149-155.

4. Дмитриев В.М. Принципы построения и реализации автоматизированного учебно-методического комплекса по техническим дисциплинам / В.М. Дмитриев, Т.В. Ганджа, В.В. Ганджа // Доклады ТУСУРа. - 2010. - № 2 (22), ч. 2. - С. 266-270.

Григорьева Татьяна Евгеньевна

Магистрант каф. моделирования и системного анализа (МиСА) ТУСУРа

Тел.: 8 (382-2) 41-39-15

Эл. почта: tanya_grig_1991@mail.ru

Grigorieva T.E.

Discrete-event simulation in CM MARS for a «Mass service system» course

The article describes the algorithm of message transmission implemented in an imitating kernel of the MARS modeling environment, in which the simulation modeling algorithm is developed in the method of component chains (MCC). The computer model of «Traffic light» is constructed at three interconnected levels: object, logical and visual.

Keywords: mass service systems, discrete - event modeling, algorithm of message transmission, multilevel modeling.