Simple simulation system on Go

Introduction

Simulation is a method in which the model under study is replaced by a model for conducting experiments. In this model, you can play as individual situations, and many of them. The collected statistics can help draw conclusions about the processes in the system, as well as outline ways to optimize.

Simulation modeling is often considered as a kind of experimental tests, but at the same time it is less expensive, it allows you to quickly change the parameters and observe the simulated system over time.

Already about half a century in the simulation modeling computer models are used. For their development, a huge number of various programs and frameworks have been created, among which, in my opinion, the means for simulating queuing systems (QS) have received the greatest development. One of the most well-known and simple programs for simulation of QS - GPSS World (General Purpose Simulation System - a general-purpose simulation system), can be found in more detail on the links [1] , [2] .
')
The concept of this program was the basis for the simulation framework for Go.

GPSS Modeling

A model in GPSS is a sequence of blocks (commands) describing the simulated objects between which transaction transactions are moved. When a transaction enters the block, events are generated that lead either to a change in the state of the modeled object or to a change in the state / parameters of the transaction.

The basic blocks of the order of ten: GENERATE, TERMINATE, ASSIGN, SEIZE, RELEASE, QUEUE, ADVANCE, DEPART, START. Total blocks of the order of three dozen. Blocks have parameters that can be numbers, function names, labels in the modeling program, variable names. More details on the blocks can be found, for example, here .

Objects in GPSS have a set of standard numeric attributes (NAV) and standard logical attributes (ALS). For example, for a queue, one of the NAV is the current length, and an example of an ALS for some equipment will be free (TRUE) or it is occupied (FALSE).
In some versions of GPSS there is a visualization of the modeling process, but more often it is absent. According to the results of modeling in GPSS, a report is generated, indicating the NAV and ALS for all objects.

Implementation in go

The implementation in Go is a development of a set of objects of similar functionality with GPSS blocks. The first was created Pipeline - the object in which the simulation is performed.

The map based on a list of components for describing the system being modeled. Since the simulation of transaction must pass a sequence of blocks in a strict order, in the method of adding the Append components, the procedure of adding with the simultaneous indication of the destination of transactions from them was implemented. The name of the component is used as the map key; therefore, each component must have a unique name.

After adding all the components, you can run a simulation using the Start method. Inside it is implemented a cyclic crawl of all components for a given simulation time. At the end of the simulation, you can print a report containing the NAV and ALS.

The second important element is the actual components for describing the simulation. The following were implemented: Generator - generates tranzakty, Advance - creates delays on the transaction path, Queue - queue transacts, Facility - a device monopolistically captured by transact for some time, Hole - “hole” in which transacts fail at the end of the road. Of course, such a set is not enough to create complex simulation models, but to work out the solution and compare with the GPSS results is enough. All components implement the IBaseObj interface, which covers the minimum necessary functionality.

Each component has a queue of transactions. Directly as a queue, it is used only in Queue, for other components it is just storage. The queue is based on a map . In the process of modeling the components pass through their turn and check the readiness (fulfillment of a certain condition) of the transaction for transfer to the next component. Passing is done through the AppendTransact method of the next component. If the transfer is successful, then the transaction is removed from the queue, respectively, the next component takes it in turn. Since for each component is determined by several destinations, then if it was not possible to send a transaction to one destination, we try to send to a friend.

To generate random variables when determining the time of the appearance of a transaction and the creation of delays, the PRNG functions in Go are used.

Since, at the same time, during simulation, there can be a number of transacts moving between different components, the idea arose to use goroutines inside components. Pipeline, passing through the components, runs for each of them a HandleTransacts handler, inside of which a goroutine is created. After all goroutines work out, the model time counter is increased and HandleTransacts is called HandleTransacts .

The last key object is actually the transaction itself. He has an identifier, the time of birth and death, the owner (in which component he is now), a number of parameters for calculating the NAV and NAV.

In fig. 1 shows the structural diagram of the interaction of the main objects of the framework during modeling.


Fig. 1. A generalized structural diagram of the interaction of the main objects in the simulation

Simulation example

Suppose you need to simulate the work of a barber shop. This is a famous example of GPSS. Visitors walk erratically, with a frequency of 18 ± 6 minutes, their number is not known in advance. We have one hairdresser, he spends 16 ± 4 minutes on a haircut. So, how many people will he cut for a working day? How many people will be in line? How much time will it take to cut and on average how long will people stay in line? Many questions and simple simulation. The block diagram in fig. 2


Fig. 2. The structural scheme of modeling barbershop

The code for building the model will be as follows.

 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() 

Served 25 customers, the 26th at the time of completion of the simulation was still in the chair of the master. The queue was no more than 1 person, 11 people did not wait (zero pass) and immediately went to the haircut. On average, people spent 2.58 minutes in the queue, and of those who waited (not a zero pass), 4.47 minutes. 89.17% of his time hairdresser strenuously cut.

Of course, if you do another simulation, the results will change. But when conducting a series of simulations, you will see the overall level of the master download and the number of clients served. When conducting the same simulation in GPSS, similar results are obtained.

Another example. There is an office, it has 10 employees and one toilet. People want to go to the toilet every 90 ± 60 minutes, go to the toilet for 5 ± 3 minutes, take a toilet for 15 ± 10 minutes, go back to the office for 5 ± 3 minutes. Let's carry out simulation within 9 hours (8 business hours + 1 hour lunch), on fig. 3 shows the structural scheme.


Fig. 3. Block diagram of the model of employment of the toilet: left with one toilet, right with two

On the left is a model with one toilet, on the right with two. The following is the model code.

 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() 

In the queue there were up to 4 people, 8 times a person immediately went to the toilet, during the working day the toilet is used by 87.04%. The most significant thing, in my opinion, is that people are waiting for the order of half an hour (31 minutes) in the queue for the toilet. Perhaps this is due to the fact that the toilet is one, and perhaps due to the fact that, on average, people sit in it for 14.69 minutes.

Adding another toilet, I saw that the line was reduced to 3 people, 29 people immediately went to the toilet. But most importantly, the expectation has decreased almost three times.

Conclusion

The framework created on the knee is fairly simple and as yet limited. Plans to increase its functionality to the level of GPSS. The practical value of the framework is the ability to easily and quickly build a simulation model on Go and get results.

The code is posted on github .