Теория массового обслуживания: базовые примеры

Начнем осваивать инструментарий библиотеки EventSimulation для аналитического изучения моделей дискретной событийной логики и систем массового обслуживания (СМО).

Описание задачи

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

Общие компоненты любой системы массового обслуживания - это наличие входящего потока заявок, заданная структура системы (количество и емкость накопителей, очередей и других приборов обслуживания), время обслуживания заявок и дисциплина обслуживания (алгоритм распределения заявок между обработчиками, выбора заявок из очереди и формирования очередей).

Библиотека EventSimulation

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

Для начала, установим эту библиотеку в нашу систему (этот шаг выполняется однократно, при повторном запуске закомментируйте следующую строку).

Pkg.add( "EventSimulation" )

Рассмотрим самую простую ситуацию - когда пять клиентов "пришли" в нашу систему с интервалом 1 единица времени между ними, а обслуживание каждого из них заняло 1.5 единицы времени.

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)

1.0: Новый клиент
2.0: Новый клиент
    2.5: Уход клиента, который пришел в 1.0
3.0: Новый клиент
    3.5: Уход клиента, который пришел в 2.0
4.0: Новый клиент
    4.5: Уход клиента, который пришел в 3.0
5.0: Новый клиент
    5.5: Уход клиента, который пришел в 4.0
    6.5: Уход клиента, который пришел в 5.0

Внутри функции arrival для каждого клиента регистрируется время прихода и создается событие ухода, которое сохраняется в диспетчер (Scheduler) вместе с анонимной функцией, которая будет вызвана диспетчером когда настанет время.

Значение x.now берется из вектора состояния диспетчера.

Если мы хотим проанализировать ситуацию с неограниченным количеством поступающих на сход объектов или событий, то нам будет недостаточно обрабатывать клиентов в цикле. Нам нужен будет источник событий, который мы создадим при помощи 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)

1.0: Новый клиент
2.0: Новый клиент
    2.5: Уход клиента, который пришел в 1.0
3.0: Новый клиент
    3.5: Уход клиента, который пришел в 2.0
4.0: Новый клиент
    4.5: Уход клиента, который пришел в 3.0
5.0: Новый клиент
    5.5: Уход клиента, который пришел в 4.0
6.0: Новый клиент
    6.5: Уход клиента, который пришел в 5.0
7.0: Новый клиент

Клиенты по-прежнему приходят раз в 1 единицу времени, но теперь их очередь бесконечна. Длительность симуляции определена в команде go!(s, 7) как 7 единиц времени.

Добавим в нашу модель счетчик клиентов. Для этого нам понадобится определить структуру CounterState, которая будет инициализироваться для диспетчера Scheduler при его создании.

Стоит учесть, что переопределение уже созданных структур обычно требует перезагрузки ядра Julia (например средствами GUI Engee).

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)

0.07: Новый клиент (клиентов в очереди 1)
0.42: Новый клиент (клиентов в очереди 2)
    1.07: Уход клиента, который пришел в 0.07 (клиентов в очереди 2)
1.12: Новый клиент (клиентов в очереди 2)
    1.42: Уход клиента, который пришел в 0.42 (клиентов в очереди 2)
1.75: Новый клиент (клиентов в очереди 2)
    2.12: Уход клиента, который пришел в 1.12 (клиентов в очереди 2)
2.66: Новый клиент (клиентов в очереди 2)
    2.75: Уход клиента, который пришел в 1.75 (клиентов в очереди 2)
2.86: Новый клиент (клиентов в очереди 2)
3.63: Новый клиент (клиентов в очереди 3)
    3.66: Уход клиента, который пришел в 2.66 (клиентов в очереди 3)
    3.86: Уход клиента, который пришел в 2.86 (клиентов в очереди 2)
4.41: Новый клиент (клиентов в очереди 2)
    4.63: Уход клиента, который пришел в 3.63 (клиентов в очереди 2)

Система M/M/1

Напоследок реализуем классическую систему со следующими параметрами:

входящий поток заявок имеет пуассоновское распределение
распределение времени обслуживания экспоненциальное
число обслуживающих серверов/обработчиков заявок равно 1
очередь на обслуживание бесконечна,
дисциплина обслуживания называется FCFS (FIFO) от first come, first served или first in, first out.

На всякий случай поставим библиотеки, которых может по умолчанию не быть в системе.

Pkg.add( ["Distributions", "Statistics", "Random"] )

После их установки в систему мы можем симулировать СМО M/M/1 при помощи следующего алгоритма.

Структура MMQueue накапливает статистику по текущей работе диспетчера (по ходу текущей симуляции) и позволяет нам получить на выходе функции run! среднее значение разницы между временем поступления и временем ухода каждого конкретного объекта (mean( d-a )), прошедших через систему в ходе симуляции 1 000 000 временных единиц.

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="Среднее время обслуживания" )

Мы видим, что при частоте наступления событий равной 1.11, 3 из 20 запусков привели к превышению заданного среднего времени обслуживания.

count( last.(hcat(rates...)) .> 0.03 )

3

Больше примеров можно найти в репозитории разработчиков библиотеки: https://github.com/bkamins/EventSimulation.jl/tree/master/examples.

Англоязычная документация на библиотеку EventSimulation находится по адресу https://bkamins.github.io/EventSimulation.jl/stable/.

Заключение

Мы изучили базовые приемы моделирования систем массового обслуживания. Engee позволяет вставлять в циклы симуляции обращение к внешним информационным системам или запуск моделей, размещенных на холсте, поэтому инструменты теории массового обслуживания могут стать важной частью цепочки анализа надежности систем.

Теория массового обслуживания: Базовые примеры и M/M/1