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): Новый клиент")
register!(s, x -> println(" $(x.now): Уход клиента, который пришел в $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): Новый клиент")
register!(s, x -> println(" $(x.now): Уход клиента, который пришел в $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)): Уход клиента, который пришел в $(round(t,digits=2)) (клиентов в очереди $(x.state.count + 1))" )
end
t = s.now
println( "$(round(s.now,digits=2)): Новый клиент (клиентов в очереди $(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/request 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 # занят ли обработчик (сервер)?
arrival_times::Vector{Float64} # время когда клиент пришел
departure_times::Vector{Float64} # время когда клиент ушел
end
# Событие "клиент пришел"
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
# Событие "клиент покинул систему"
function leave(s)
push!(s.state.departure_times, s.now)
if s.state.qlen > 0 # есть ли ожидающие клиенты?
s.state.qlen -= 1
register!(s, leave, rand(s.state.sp))
else
s.state.busy = false
end
end
# Запуск системы M/M/1 с заданным параметрами
# ar: среднее время между появлениями клиентов
# sr: среднее время, затраченное на обслуживание
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
# Запустим симуляцию системы с изменяемым средним
# временем между поступлением заявок на обработку
# (от 1/0.1 до 1/0.9 временных единиц)
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="Среднее время обслуживания" )
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.