[Из песочницы] Простая система имитационного моделирования на Go14.04.2019 22:32

Введение

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

Уже порядка полувека при имитационном моделировании используются компьютерные модели. Для их разработки создано огромное множество различных программ и фреймворков, среди которых, на мой взгляд, наибольшее развитие получили средства для моделирования систем массового обслуживания (СМО). Одна из наиболее известных и простых программ для имитационного моделирования СМО — GPSS World (General Purpose Simulation System — система моделирования общего назначения), более подробно можно ознакомится по ссылкам [1], [2].

Концепция этой программы и была положена в основу фреймворка имитационного моделирования на Go.

Моделирование в GPSS

Модель в GPSS представляет собой последовательность блоков (команд), описывающих моделируемые объекты, между которыми перемещаются транзакты. При попадании транзакта в блок генерируются события, приводящие либо к изменению состояния моделируемого объекта, либо изменению состояния/параметров транзакта.

Основных блоков порядка десяти: GENERATE, TERMINATE, ASSIGN, SEIZE, RELEASE, QUEUE, ADVANCE, DEPART, START. Всего блоков порядка трёх десятков. Блоки имеют параметры, в качестве которых могут выступать числа, имена функций, метки в программе моделирования, имена переменных. Более подробно с блоками можно ознакомиться, например, здесь.

Объекты в GPSS имеют набор стандартных числовых атрибутов (СЧА) и стандартных логических атрибутов (СЛА). Например, для очереди, один из СЧА это текущая длина, а примером СЛА для некоего оборудования будет свободно (TRUE) или занято оно (FALSE).
В отдельных версиях GPSS присутствует визуализация процесса моделирования, но чаще всего она отсутствует. По результатам моделирования в GPSS формируется отчёт, с указанием СЧА и СЛА по всем объектам.

Реализация в Go

Реализация в Go представляет собой разработку набора объектов схожих по функциям с блоками GPSS. Первым был создан Pipeline — объект, в рамках которого выполняется симуляция.

За основу взят map, содержащий перечень компонентов для описания моделируемой системы. Поскольку при моделировании транзакты должны проходить последовательность блоков в строгом порядке, в методе добавления компонентов Append была реализована процедура добавления с одновременным указанием, адресатов транзактов от них. В качестве ключа map используется имя компонента, поэтому каждый компонент должен иметь уникальное имя.

После добавления всех компонентов, можно запустить моделирование с помощью метода Start. Внутри неё реализован циклический обход всех компонентов в течение заданного времени моделирования. По окончания моделирования можно напечатать отчёт, содержащий СЧА и СЛА.

Второй важный элемент это собственно компоненты для описания моделирования. Были реализованы: Generator — генерирует транзакты, Advance — создаёт задержки на пути транзакта, Queue — очереди транзактов, Facility — некое устройство, монопольно захватываемое транзактом на некоторое время, Hole — «дыра» в которую проваливаются транзакты в конце пути. Разумеется, такого набора недостаточно для создания сложных имитационных моделей, но для отработки решения и сравнения с результатами GPSS вполне хватает. Все компоненты реализуют интерфейс IBaseObj, который охватывает минимально необходимый функционал.

Каждый компонент имеет очередь транзактов. Непосредственно как очередь она используется только в Queue, для других компонентов это просто хранилище. Очередь реализована на основе map. В процесс моделирования компоненты проходят по своей очереди и проверяют готовность (выполнение некоторого условия) транзакта для передачи следующему компоненту. Передача выполняется через метод AppendTransact следующего компонента. Если передача прошла успешно, то транзакт удаляется из очереди, соответственно следующий компонент принимает его в свою очередь. Поскольку для каждого компонента определяется несколько адресатов, то если не удалось отправить транзакт одному адресату, пытаемся отправить другом.

Для генерации случайных величин при определении времени появления транзакта и создании задержек используются функции ГПСЧ в Go.

Так как при моделировании одновременно могут существовать множество транзактов, перемещающихся между различными компонентами, то возникла идея использовать внутри компонентов goroutines. Pipeline, проходя по компонентам, запускает для каждого из них обработчик HandleTransacts, внутри которого создаётся goroutine. После того как все goroutines отработают, увеличивается счётчик модельного времени и повторно вызывается HandleTransacts.

Последний ключевой объект это собственно сам транзакт. У него есть идентификатор, время рождения и смерти, владелец (в каком компоненте он сейчас), ряд параметров для вычисления СЧА и СЧЛ.

На рис. 1 приведена структурная схема взаимодействия основных объектов фреймворка при моделировании.

Рис. 1. Обобщённая структурная схема взаимодействия основных объектов при моделировании

Пример моделирования

Допустим надо смоделировать работу парикмахерской. Это известный пример из GPSS. Посетители идут хаотично, с периодичностью 18±6 минут, их количество заранее не известно. Парикмахер у нас один, на стрижку он тратит 16±4 минуты. Итак, сколько всего человек он пострижёт за рабочий день? Сколько будет людей в очереди? Сколько в среднем уйдёт времени на стрижку и сколько времени просидят люди в очереди? Много вопросов и простая симуляция. Структурная схема на рис. 2.

Рис. 2. Структурная схема моделирования парикмахерской

Код для построения модели будет следующий.

barbershop := NewPipeline("Barbershop", true) // Наша симуляция
clients := NewGenerator("Clients", 18, 6, 0, 0, nil) // Генератор клиентов
chairs := NewQueue("Chairs") // Очередь
master := NewFacility("Master", 16, 4) // Парикмахер
hole := NewHole("Out") // Выход
barbershop.Append(clients, chairs) // От генератора транзакты идут в очередь
barbershop.Append(chairs, master) // Из очереди идут в устройство
barbershop.Append(master, hole) // Из устройства в дыру
barbershop.Append(hole) // А из дыры транзакты никуда не уходят
barbershop.Start(480) // Моделируем рабочий день
<-barbershop.Done // Завершение симуляции
barbershop.PrintReport()

Обслужили 25 клиентов, 26-ой на момент завершения моделирования был ещё в кресле мастера. В очереди было не более 1 человека, 11 человек не ждали (нулевой проход) и сразу проходили на стрижку. В среднем в очереди люди провели 2,58 минуты, а из тех, кто ждал (не нулевой проход) 4,47 минуты. 89,17% своего времени парикмахер усиленно стриг.

Разумеется, если провести ещё одну симуляцию, результаты изменятся. Но при проведении серии симуляций будет видно общий уровень загрузки мастера и количество обслуженных клиентов. При проведении такой же симуляции в GPSS получаются близкие результаты.

Другой пример. Есть офис, в нём 10 сотрудников и один туалет. Люди желают пойти в туалет каждые 90±60 минут, идти до туалета 5±3 минуты, занимают туалет 15±10 минут, поход обратно в офис 5±3 минуты. Проведём симуляцию в течении 9 часов (8 часов работы + 1 час обед), на рис. 3 приведена структурная схема.

Рис. 3. Структурная схема модели занятости туалета: слева с одним туалетом, справа с двумя

Слева модель с одним туалетом, справа с двумя. Далее приведён код модели.

waterclosetsim := NewPipeline("Water Closet Simulation", false)
office := NewGenerator("Office", 0, 0, 0, 10, nil)
wantToToilet:= NewAdvance("Wanted to use the toilet", 90, 60)
pathToWC := NewAdvance("Path to WC", 5, 3)
queue := NewQueue("Queue to the WC")
pathFromWC := NewAdvance("Path from WC", 5, 3)
wc := NewFacility("WC", 15, 10)
pathToOffice:= NewAdvance("Path from WC", 5, 3)
waterclosetsim.Append(office, wantToToilet)
waterclosetsim.Append(wantToToilet, pathToWC)
waterclosetsim.Append(pathToWC, queue)
waterclosetsim.Append(queue, wc)
waterclosetsim.Append(wc, pathFromWC)
waterclosetsim.Append(pathFromWC, wantToToilet) 
waterclosetsim.Start(540) 
<-waterclosetsim.Done
waterclosetsim.PrintReport()

В очереди было до 4 человек, 8 раз человек сразу попал в туалет, в течении рабочего дня туалет используют на 87,04%. Самое существенное, на мой взгляд, это то, что люди ждут порядка получаса (31 минута) в очереди в туалет. Возможно, это связано с тем, туалет один, а возможно, с тем, что в среднем люди сидят в нём 14,69 минут.

Добавив ещё один туалет, я увидел, что очередь сократилась до 3 человек, 29 раз люди сразу попали в туалет. Но самое главное, почти в три раза уменьшилось ожидание.

Заключение

Созданный на коленке фреймворк достаточно простой и пока ещё ограниченный. В планах повысить его функциональность до уровня GPSS. Практическая ценность фреймворка в возможности просто и быстро собрать на Go имитационную модель и получить результаты.

Код выложен на GitHub.

© Habrahabr.ru