Хабрахабр

[Из песочницы] Простая система имитационного моделирования на Go

Введение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Pipeline, проходя по компонентам, запускает для каждого из них обработчик HandleTransacts, внутри которого создаётся goroutine. Так как при моделировании одновременно могут существовать множество транзактов, перемещающихся между различными компонентами, то возникла идея использовать внутри компонентов goroutines. После того как все 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()

Результаты моделирования можно посмотреть здесь.

Pipeline name " Barbershop "
Simulation time 480
Object name " Chairs "
Max content 1
Total entries 26
Zero entries 11
Persent zero entries 42.31%
In queue 0
Average time/trans 2.58
Average time/trans without zero entries 4.47

Object name " Clients "
Generated 26

46
Average utilization 89. Object name " Master "
Average advance 16. 00
Transact 26 in facility 17
Number entries 26.

56
Average life 19. Object name " Out "
Killed 25
Average advance 16. 44

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

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

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

Результаты моделирования следующие.

Pipeline name " Water Closet Simulation "
Simulation time 540
Object name " Office "
Generated 10

77 Object name " Path from WC "
Average advance 5.

22 Object name " Path to WC "
Average advance 5.

22%
Current contents 4
Average content 1. Object name " Queue to the WC "
Max content 4
Total entries 36
Zero entries 8
Persent zero entries 22. 11
Average time/trans without zero entries 31. 78
Average time/trans 24. 00

69
Average utilization 87. Object name " WC "
Average advance 14. 00
Transact 2 in facility 04
Number entries 32.

85
Object name " Wanted to use the toilet "
Average advance 95.

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

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

Заключение

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

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

Теги
Показать больше

Похожие статьи

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

Кнопка «Наверх»
Закрыть