Object model of application for simulation of cyclic queueing systems.pdf Системы массового обслуживания (СМО) [1, 2] являются стохастическими моделями реальных систем. Циклические СМО - это класс систем массового обслуживания, в которых обслуживающие приборы в определенном (циклическом) порядке подключаются к различным накопителям для обслуживания заявок, находящихся в этих накопителях [3, 4]. Заявки попадают в накопители из нескольких входящих в систему потоков заявок. Аналитическим исследованиям циклических систем обслуживания посвящено достаточно много научных трудов (см., например, [5]), но несмотря на это, по вполне понятным причинам во многих случаях не удается получить какие-либо аналитические результаты. Тогда применяют другие методы исследования, среди которых особое место занимает имитационное моделирование [6, 7]. Имитационный подход позволяет воспроизвести поведение системы и таким образом достичь требуемых результатов практически для любой конфигурации исследуемой системы. Конечно, имитационное моделирование имеет и свои недостатки - это в первую очередь числовой, возможно, качественный, но не аналитический характер результатов, что позволяет делать подтвержденные выводы только для модели, определенной с точностью до числовых значений, но не для класса систем. Также выполнение имитационного моделирования требует достаточно долгого времени для проведения комплексного исследования. Однако, несмотря на указанные недостатки, имитационный подход часто используется для решения конкретных задач в тех случаях, когда аналитические исследования невозможны либо возможны при больших упрощениях исходной модели. Для выполнения имитационного моделирования применяют специализированные программные средства, которые можно разделить на два типа: с полным контролем внутренней структуры со стороны аналитика (типа «белый ящик») и без такового (типа «черный ящик»). Системы первого типа наиболее удобно реализовать с помощью различных готовых программных продуктов, специально предназначенных для имитационного моделирования, например, с помощью систем GPSS [8, 9], MatLab [10], AnyLogic [11] и других программных продуктов. Иногда аналитик использует стандартные языки программирования (например, Fortran или C++) для создания такой программы. В любом из этих случаев от исследователя требуются владение на хорошем уровне навыками программирования и / или достаточно глубокие знания специального языка (GPSS) или устройства соответствующей системы (MatLab). Системы второго типа представляют собой закрытые приложения, в которых аналитику достаточно только выбрать конфигурацию из предложенного списка и задать параметры, не вдаваясь в подробности устройства программной системы и не написав ни строчки кода на каком-либо языке. В данном случае от пользователя приложения не требуется знания основ программирования и даже глубокого знания внутреннего устройства самого процесса имитационного моделирования. Каждый тип систем моделирования имеет свои положительные и отрицательные стороны. В настоящей работе представлено решение задачи разработки приложения закрытого типа для имитационного моделирования достаточно широкого класса циклических систем обслуживания. 1. Общее описание модели циклической системы массового обслуживания Рассматривается класс циклических систем массового обслуживания следующего вида (рис. 1). На вход системы поступает K> 1 входящих потоков A1, ..., AK, каждый из которых описывается заданной для него моделью случайного потока событий с определенными параметрами. Все заявки k-го входящего потока (k = 1, K) поступают в k-й накопитель (буфер), который может иметь заданный максимальный размер или может быть не ограничен в приеме заявок. Также имеется некоторое число N > 1 обслуживающих приборов (серверов) B1, ..., BN, которые подключаются к накопителям, забирают из них заявки в порядке, соответствующем некоторой дисциплине (например, FIFO - first in first out), и обслуживают эти заявки в соответствии с некоторым заданным для каждого прибора законом. После этого заявки покидают систему. Функция распределения времени обслуживания может определяться для каждого прибора независимо от накопителя (входящего потока), из которого взята заявка, но также для каждого прибора может быть задан индивидуальный набор из K функций распределения, определяющих продолжительность обслуживания заявок, поступивших из разных входящих потоков. Таким образом, при K входящих потоках (накопителях) и N обслуживающих приборах можно задать N х K функций распределения Bnk (х), n = 1, N, k = 1, K, определяющих продолжительность обслуживания разными приборами заявок из разных входящих потоков. Входящие потоки Накопители Узел подключения Приборы Рис. 1. Модель циклической системы A1 K Порядок, способ и длительность подключения приборов к накопителям определяется заданными параметрами, которые в дальнейшем будем называть параметрами подключения. В случае, когда количество серверов N > 1, возможны различные варианты их «группового» поведения. В качестве основных групповых дисциплин выделим три: 1. Жесткая группа. Все обслуживающие приборы системы образуют одну группу обслуживания: все приборы в один момент времени работают только с одним накопителем, переключение между накопителями и пребывание в состоянии переключения (см. далее) для всех приборов производится синхронно. 2. Одиночные приборы. Обслуживающие приборы подключаются к накопителям независимо друг от друга, причем с одним накопителем в один момент времени может работать только один прибор. В случае, если по окончании сеанса подключения прибора к накопителю следующий накопитель уже обслуживается другим сервером, то прибор ищет следующий по циклическому порядку свободный (не находящийся в сеансе подключения с другим сервером) накопитель и подключается к нему. Эта дисциплина подключения доступна только при условии, что количество серверов не превышает количество накопителей (N < K). 3. Гибкие группы. Обслуживающие приборы подключаются к накопителям независимо друг от друга, в один момент времени к накопителю может быть подключено любое число приборов. По окончании сеанса подключения прибор подключается к следующему накопителю независимо от того, обслуживается он другими серверами или нет. Кроме дисциплины подключения групп важными параметрами подключения являются параметры, определяющие продолжительность одного сеанса подключения сервера или группы серверов к накопителю. В данной работе будем называть их дисциплиной подключения и рассмотрим два типа: 1. С разделением времени. Продолжительность каждого подключения определяется заданной функцией распределения длительности сеанса. По окончании этого периода обслуживание всех заявок, производившееся в рамках данного подключения, прерывается, а сами заявки возвращаются в накопитель (в начало очереди, в порядке времени их поступления в систему). Продолжительность сеанса подключения может определяться одной функцией распределения для всех накопителей либо задаваться индивидуально для каждого накопителя. 2. До полного исчерпания. Подключение сохраняется до тех пор, пока не будет закончено обслуживание последней заявки в накопителе. При этом в случае жесткой группы все незадействованные приборы простаивают, пока последний из них не закончит обслуживание, но во время простоя могут принимать и обслуживать заявки, поступающие из текущего входящего потока. В случае гибких групп, если по окончании обслуживания на одном из приборов накопитель оказывается пуст, то сеанс подключения для данного прибора заканчивается и он переключается на другой накопитель. Когда прибор или группа приборов завершают обслуживание одного накопителя и должны переключиться к следующему, то параметрами задачи может быть задано, что это переключение требует некоторого времени. В случае применения дисциплины подключения «до полного исчерпания» это время должно быть обязательно больше нуля, так как в противном случае, если все накопители оказались временно пусты, модель перейдет в состояние «зацикливания», когда приборы мгновенно переключаются от очереди к очереди, а модельное время не изменяется. Для дисциплины с разделением времени этот параметр опционален. Если параметрами задачи указано, что переключение требует времени, то задается функция распределения, определяющая длительность состояния переключения, в которое прибор или группа приборов переходят по окончании сеанса подключения к одному накопителю. В этом состоянии приборы не выполняют никаких действий. По окончании времени переключения приборы подключаются к следующему накопителю. Функция распределения длительности времени переключения может определяться одной функцией распределения для всех накопителей либо задаваться индивидуально для каждого накопителя. 2. Объектная модель циклической системы обслуживания 2.1. Основные объекты циклической системы Для имитационного моделирования стохастических систем наиболее подходящим методом моделирования является дискретно-событийный подход [12, 13], основная идея которого заключается в определении событий, которые должны произойти в системе, и сдвиге модельного времени по моментам наступления этих событий. В настоящей работе в качестве платформы для реализации приложения имитационного моделирования циклических систем будут использованы библиотеки программного комплекса ODIS [14-16], предназначенного для имитационного моделирования сетей массового обслуживания. В этих библиотеках уже имеется базовый класс SimulationModel, который реализует основной цикл дискретно-событийного моделирования систем массового обслуживания. Исполнение цикла моделирования базируется на взаимодействии объектов событий, заявок и элементов системы. Объектная модель разрабатываемого приложения имитационного моделирования циклических СМО представлена на рис. 2, 3. Реализация механизма сеансов подключения и описание основных сценариев имитационного моделирования представлены в следующих подразделах. Классы Element, Source, PassiveBuffer реализованы каркасом ODIS и предназначены для моделирования элементов СМО общего вида. Классы InputSource, Server и ConnectionManager реализуют объекты, специфичные для циклических СМО. Класс Element представляет собой абстрактный класс, потомками которого будут любые элементы системы (например, входящий поток, накопитель, прибор обслуживания), которые могут принимать заявки с помощью операции accept(...), а также генерировать и / или обрабатывать события. Обработка событий производится с помощью операции processEvent(...). Класс Source представляет входящий поток заявок. В методе accept(...) генерируется исключение, так как этот элемент не может принимать заявки. А в методе processEvent(...) генерируются новые заявки. Рис. 2. Объектная модель циклической системы обслуживания Класс InputSource, в отличие от Source, включает в себя накопитель заявок (объект стандартного класса PassiveBuffer). Метод processEvent(...) вызывается автоматически каркасом платформы, если обрабатываемое системой событие сгенерировано данным объектом InputSource. В дальнейшем объекты класса InputSource будем называть источниками. Класс PassiveBuffer представляет собой реализацию объекта-накопителя заявок. Он имеет атрибут maxLength, который определяет максимальный объем накопителя (максимальное число заявок, которые можно в нем разместить). Значение maxLength = -1 означает, что накопитель не ограничен в размерах. Методы accept(...) и acceptReturned(...) используются для помещения заявки в накопитель. Если при вызове метода accept(...) оказалось, что накопитель заполнен до предела, то заявка получает отказ и немедленно покидает систему. В случае неограниченного объема накопителя или при вызове метода ac-ceptReturned(...) заявка будет помещена в накопитель в обязательном порядке. В этом случае считается, что накопитель всегда имеет небольшой резерв для размещения заявок, возвращенных в него в экстренных ситуациях (прерывание обслуживания). Все заявки в накопителе сортируются в порядке времени их первого поступления в накопитель (времени поступления в систему). Операция getCall(...) извлекает самую старую заявку из накопителя и возвращает ее в качестве результата. Объект Server реализует обслуживающий прибор и имеет два существенных отличия по сравнению с соответствующим объектом платформы, а именно: 1) может пребывать в трех состояниях (поле state): «Свободен», «Занят обслуживанием», «В режиме переключения»; 2) реализует возможность задания отдельных функций распределения для длительности обслуживания заявок из разных накопителей (входящих потоков). Для этого используется опция distribu-tionsType со значениями Single (одна функция распределения для всех накопителей) и ForEachBuffer (функции распределения вероятностей заданы для каждого накопителя в отдельности), а также массив distributions. Методы accept(...) и processEvent(...) используются соответственно для помещения заявки на обслуживание в данном приборе и для обработки события окончания обслуживания. Метод breakService(...) немедленно прерывает обслуживание заявки и возвращает ее в соответствующий накопитель с помощью метода PassiveBuffer.acceptReturned(...). Класс ConnectionManager (диспетчер подключений) - искусственно введенный объект, который хранит информацию и реализует логику подключения приборов к очередям. Диспетчер подключений содержит такие атрибуты, как тип соединения connectionType, дисциплина обслуживания очередей sessionType, способ задания функций распределения длительности подключения sessionDistributionsType, функции распределения длительности подключения приборов к накопителям sessionDistributions, флаг переключения приборов isPreconnectionRequired, способ задания функций распределения длительности времени переключения preconnectionDistributionsType, а также функции распределения длительности переключения приборов preconnectionDistributions. Метод processEvent(...) класса ConnectionManager обрабатывает событие окончания времени переключения прибора. Другие методы данного класса будут описаны ниже. 2.2. Механизм сеансов подключения В объектной модели все серверы системы собраны в одну коллекцию - пул серверов (объект класса ServersPool). Все входящие потоки с накопителями также образуют коллекцию. У модели имеется единственный объект класса ConnectionManager, которому предоставлен полный доступ к обеим коллекциям. Для организации моделирования подключений приборов к накопителям предлагается использовать механизм сеансов подключения. Сеанс подключения (объект Session) - это объект, создаваемый на время подключения пула приборов к одному накопителю (рис. 3). Данный объект отвечает за продолжительность подключения, управляет движением поступающих заявок, а также заявок, находящихся в накопителе и на обслуживании. Рис. 3. Структурная схема механизма сеансов подключения Объект Session реализует операцию processEvent(...) интерфейса Element, в ней обрабатывается событие окончания сеанса. Операции start(...) и finish() используются соответственно для старта и окончания сеанса. Метод serviceEnded(...) вызывается, когда обслуживающий прибор, находящийся в сеансе, закончил обслуживание и готов принять на обслуживание новую заявку. Операция acceptCall(...) используется объектами-источниками InputSource во время поступления заявки в систему для поиска сеанса со свободным прибором и передачи ему этой заявки. Атрибут buffer ссылается на объект-накопитель источника source. Управление сеансами полностью осуществляет объект ConnectionManager. Для этого он реализует методы (см. рис. 3) startNewSession(...) и sessionEnded(...) соответственно для создания сеанса и обработки события его окончания, а также метод startPreconnection(...) для создания события отложенного старта сеанса (так называемое время переключения). 2.3. Основные сценарии имитационного моделирования циклической системы Поскольку вся система построена на дискретно-событийной модели управления, то для выполнения полного цикла имитационного моделирования достаточно выделить типы событий системы, реализовать механизмы их генерации, записи в журнал событий, извлечения из него и процедуры обработки этих событий. Выделим основные типы системных событий: 1. Начало моделирования. Происходит однократно на старте всего процесса моделирования. Не требует записи в журнал. 2. Поступление заявки в систему в определенном входящем потоке. 3. Окончание времени переключения прибора или группы приборов (если задано, что переключение требует времени). 4. Окончание обслуживания заявки на приборе. 5. Завершение сеанса (для дисциплины подключения «с разделением времени»). Начало моделирования выполняется в методе onlnitialization класса PollingModel (рис. 4). Здесь создаются по одному событию на каждый источник заявок. Затем в методе инициализации диспетчера подключений производятся необходимые подготовительные действия в зависимости от заданных параметров моделируемой СМО. sd Model.onInitialization() ^ :ConnectionManager :PollingModel "Г InputSource -1-г loop [for each source in inputSources] I -_-1-/ addNewSourceEvent(soyrce) nextEvent() I t = nextTime() c:Call e:Event new(t) ->1 T newjtcall, squrce)^

Скачать электронную версию публикации