Queuing Theory: basic examples
Let's start learning the library's tools EventSimulation for the analytical study of models of discrete event logic and queuing systems (QMS).
Task description
Queuing theory includes tools for analyzing complex systems that work with stochastic events that occur repeatedly and allow you to evaluate system characteristics such as queues, average waiting time before starting maintenance, or average equipment downtime.
The common components of any queuing system are the presence of an incoming flow of requests, a given system structure (number and capacity of storage devices, queues and other service devices), time for servicing requests and service discipline (algorithm for distributing requests between handlers, selecting requests from the queue and forming queues).
EventSimulation Library
Library EventSimulation allows you to program systems based on discrete event logic. In such systems, the time between events can be expressed in relative terms, and the simulation is based on events, rather than on an explicitly defined continuous time vector, as in the simulation of graphical models created from blocks.
To begin with, we will install this library in our system (this step is performed once, comment out the following line when restarting).
Pkg.add( "EventSimulation" )
Let's consider the simplest situation - when five clients "came" to our system with an interval of 1 * unit of time* between them, and the maintenance of each of them took 1.5 * units of time*.
using EventSimulation
function arrival(s)
t = s.now
println("$(s.now): New customer")
register!(s, x -> println(" $(x.now): The departure of a customer who came to $t"), 1.5)
end
s = Scheduler()
for t in 1.0:5.0
register!(s, arrival, t)
end
go!(s)
Inside the function arrival The arrival time is recorded for each client and a departure event is created, which is saved to the dispatcher (Scheduler) along with an anonymous function that will be called by the dispatcher when the time is right.
Meaning x.now it is taken from the dispatcher's state vector.
If we want to analyze the situation with an unlimited number of objects or events coming to the meeting, it will not be enough for us to process clients in a loop. We will need an event source, which we will create using repeat_register.
using EventSimulation
function arrival(s)
t = s.now
println("$(s.now): New customer")
register!(s, x -> println(" $(x.now): The departure of a customer who came to $t"), 1.5)
end
s = Scheduler()
repeat_register!(s, arrival, x -> 1.0)
go!(s, 7)
Customers still arrive once every 1 unit of time, but now their queue is endless. The duration of the simulation is defined in the command go!(s, 7) like 7 units of time.
Let's add a customer counter** to our model. To do this, we will need to define the structure CounterState, which will be initialized for the dispatcher Scheduler when creating it.
It is worth considering that redefining already created structures usually requires a reboot of the Julia kernel (for example, using the Engee GUI).
using EventSimulation
using Random
mutable struct CounterState <: AbstractState
count::Int
end
function arrival(s)
function departure(x)
x.state.count -= 1
println(" $(round(x.now,digits=2)): Departure of the customer who came to $(round(t,digits=2)) (customers in the queue $(x.state.count + 1))" )
end
t = s.now
println( "$(round(s.now,digits=2)): New customer (customers in the queue $(s.state.count+1))")
register!( s, departure, 1.0 )
s.state.count += 1
end
s = Scheduler( CounterState(0) )
Random.seed!(1)
repeat_register!(s, arrival, x -> rand())
go!(s, 5)
The M/M/1 system
Finally, we implement a classical system with the following parameters:
- the incoming flow of applications has a Poisson distribution
- Service time distribution exponential
- the number of serving servers/application processors is 1
- the queue for service is endless,
- The service discipline is called FCFS (FIFO) from first come, first served or first in, first out.
Just in case, we'll install libraries that may not be in the system by default.
Pkg.add( ["Distributions", "Statistics", "Random"] )
After installing them in the system, we can simulate the M/M/1 CFR using the following algorithm.
Structure MMQueue accumulates statistics on the current work of the dispatcher (during the current simulation) and allows us to get functions at the output run! the average value of the difference between the time of arrival and the time of departure of each specific object (mean( d-a )) that passed through the system during the simulation 1 000 000 time units.
using EventSimulation
using Distributions
using Statistics
using Random
mutable struct MMQueue <: AbstractState
sp::Exponential{Float64} # service rate
qlen::Int # queue length
busy::Bool # is the handler (server) busy?
arrival_times::Vector{Float64} # the time when the client arrived
departure_times::Vector{Float64} # the time when the client left
end
# The "customer has arrived" event
function arrival(s)
push!(s.state.arrival_times, s.now)
if s.state.busy # server is working?
s.state.qlen += 1
else
s.state.busy = true
register!(s, leave, rand(s.state.sp))
end
end
# The "client has left the system" event
function leave(s)
push!(s.state.departure_times, s.now)
if s.state.qlen > 0 # Are there any customers waiting?
s.state.qlen -= 1
register!(s, leave, rand(s.state.sp))
else
s.state.busy = false
end
end
# Starting the M/M/1 system with the specified parameters
# ar: average time between customer appearances
# sr: average time spent on maintenance
function run(ar, sr)
q = MMQueue( Exponential(1 / sr), 0, false, Float64[], Float64[] )
s = Scheduler( q, Float64 )
repeat_register!( s, arrival, x -> rand(Exponential(1/ar)) )
go!( s, 1_000_000 )
mean( d-a for (a,d) in zip(s.state.arrival_times, s.state.departure_times) )
end
# Let's run a simulation of a system with a variable average
# the time between receipt of requests for processing
# (from 1/0.1 to 1/0.9 time units)
plot()
arrival_rates = 0.1:0.1:0.9
rates = []
for seed in 1:20
Random.seed!(seed)
r = [ abs(run(ar, 1.0)*(1-ar)-1) for ar in arrival_rates ]
plot!( arrival_rates, r )
append!( rates, r )
end
hline!( [0.03], c="red", ls=:dash, legend=false )
plot!( title="Average service time" )
We see that with an event frequency of 1.11, 3 out of 20 launches resulted in exceeding the set average maintenance time.
count( last.(hcat(rates...)) .> 0.03 )
More examples can be found in the library developers repository: https://github.com/bkamins/EventSimulation.jl/tree/master/examples .
The English-language documentation for the EventSimulation library is located at https://bkamins.github.io/EventSimulation.jl/stable /.
Conclusion
We have studied the basic techniques of queuing systems modeling. Engee allows you to insert access to external information systems or run models placed on a canvas into simulation cycles, so queuing theory tools can become an important part of the system reliability analysis chain.