Время прочтения: 6 мин.

Концептуально модель симуляции может состоять из 5 элементов – сущностей, атрибутов, переменных состояния, событий и действий.

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

Атрибуты – это локальные переменные, которые хранят состояние динамической сущности. Например, для человека в очереди это будет время, когда он встал в очередь, время, когда он ее покинул, и выпил ли он кофе. Атрибуты могут принимать как дискретные, так и непрерывные значения.

Переменные состояния используются для хранения состояния системы и ее изменения во времени. Так, в каждый момент времени кофе-машина включена или нет, варит кофе или греет воду. Как и атрибуты, переменные состояния могут принимать как дискретные (ON/OFF), так им непрерывные (температура воды) значения.

Переменная состояния изменяет свое значение под влиянием происходящих в системе событий.

Событие – это появление чего-то внутри системы, что представляет для системы какой-то интерес. Например, Событие «нажатие на кнопку включения кофе-машины» изменяет значение переменной состояния ON  с False на True, вход на кухню нового человека увеличивает значение состояния на 1. Так же события можно использовать для перемещения объектов в системе. Например, событие «Прибыл» означает, что объект прибыл на узел и готов к обработке, а событие «Убыл» освобождает узел для обработки следующего пакета.

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

Кофе-машиной в один момент может пользоваться только один пользователь, а остальным приходится ждать в очереди. Это явление может возникать в банках, магазинах, аэропортах, компьютерных сетях и системах.

Прежде чем создавать модель, нам необходимо построить эту модель у себя в голове.

Например:

Каждое утро сотрудник приходит на работу к 9 утра и направляется на кухню налить себе кофе. Там стоит одна кофе-машина. Если кто-то уже пользуется ей, то приходится ждать. Люди пользуются машиной в порядке, в котором прибывают. Человек ждет ненулевое значение времени, прежде чем воспользоваться кофе-машиной.

Давайте определимся с элементами этой модели.

В модели представлены 3 сущности: очередь, сервер, пользователь. Очередь и сервер являются статическими сущностями, а пользователь – динамической сущностью.

В системе имеются 3 события – прибытие пользователя, начало обслуживания и уход из системы. Эти события используются для перемещения пользователя по системе.

Определяем две переменные состояния, чтобы отслеживать количество людей в очереди (Q) и состояние сервера (S). В момент, когда пользователь входит в систему, проверяется переменная S. Если S = Free, то сервер может обслуживать прибывшего человека, если же Busy, то пользователь становится в очередь. Когда сервер освобождается, он берет очередного пользователя из очереди. Если Q = 0, сервер простаивает.

В системе имеется 4 действия – генерация пользователя, ожидание, обслуживание и задержка.

В первом действии пользователи генерируются в систему. Действие ограничено двумя событиями прибытия пользователя, время между прибытиями является случайным. Продолжительность действия назовем Inter-Arrival Time (IAT).

Следующее действие – это ожидание. Оно начинается с момента генерации пользователя и завершается событием Начало обслуживания. Характеризуется временем ожидания — Waiting Time (WT).

Действие «Обслуживание» — это происходящее между началом обслуживания и завершением обслуживания. Время действия — это Service Time (ST).

Задержка – это промежуток между прибытием пользователя и завершением его обслуживания. Продолжительность последнего действия – это общее время, которое пользователь провел в системе — Response Time (RT).

IAT и ST могут быть смоделированы как случайные величины с учетом распределения вероятностей, а распределение RT и WT заранее неизвестны, и их нахождение является одной из задач моделирования.

Давайте попробуем создать простую версию симулятора очереди.

from math import inf as Infinity
from random import expovariate
from statistics import mean 

# Parameters
lamda = 1.3         # Частота прибытия (Lambda)  
mu = 2.0            # Частота убытия (Mu) 
num_packets = 100     # Число симулируемых кейсов
count = 0           # Счетчик кейсов
clock = 0
N = 0                # Переменная состояния. Число пакетов в системе

Arrival_Time = expovariate(lamda) 
Departure_Time = Infinity             

# Output Variables
Arrival_Time_List = []   # Данные о времени входа в систему
Departure_Time_List = []   # Данные о времеи убытия из системы
Delay_List = []        # Данные о задержках

while count < num_packets:
    if Arrival_Time < Departure_Time:     # Событие прибытия
        clock = Arrival_Time
        Arrival_Time_List.append(clock)
        N = N + 1.0
        Arrival_Time = clock + expovariate(lamda) 
        if N == 1:
            Departure_Time = clock + expovariate(mu)
    else:                         # Событие убытия
        clock = Departure_Time 
        Departure_Time_List.append(clock)
        N = N - 1.0
        count = count + 1    # Packet Simulated
        if N > 0:
            Departure_Time = clock + expovariate(mu)
        else:
            Departure_Time = Infinity

for i in range(num_packets):
    d = Departure_Time_List[i] - Arrival_Time_List[i]
    Delay_List.append(d)

print( "Average Delay = ", round( mean(Delay_List), 4) )

Программа симулирует поступление пакетов в систему и подсчитывает среднюю задержку для симуляции.

Для генерации пакетов используем процесс Пуассона, описывающий количество наступивших случайных событий, происходящих с постоянной интенсивностью (https://ru.wikipedia.org/wiki/Процесс_Пуассона). Процесс выхода из системы так же описывается процессом Пуассона. Для этого используется метод expovariate библиотеки random. За частоту событий отвечают переменные и mu. Этот процесс является частным случаем так называемых Birth-Death (BD) процессов, в котором происходит либо рождение (Arrival), либо смерть (Departure).

Пакеты в среднем прибывают каждые 1.3 единицы времени, покидают систему каждые 2 единицы времени. Симуляция обработает100 пакетов, что задано переменной Num_Pkts.

В процессе моделирования генерируются события прибытия и выбытия. В одну итерацию происходит либо событие Arrival, либо Departure. Во время события Arrival количество пакетов в очереди увеличивается с вероятностью lamda, а Departure уменьшается с вероятностью mu. В случае, если в очереди N пусто, генерируется событие Arrival.

Информация о событиях попадает в списки Arr_Time_Data, Dep_Time_Data, Delay_Data. Для покинувших процесс пакетов выводится среднее время задержки.

Используя эту модель, мы можем посчитать и другие показатели:

  • пропускную способность системы;
  • загрузку сервера – доля времени моделирования, в течение которой сервер занят обслуживанием;
  • количество пакетов в системе в момент времени t;
  • вероятность, что в системе находится ровно k пакетов.

Для подробного погружения в тему рекомендую к прочтению следующую книгу издательства CRC Press: Yahya E. Osais.  “Computer Simulation. A Foundational Approach Using Python”, на базе которой написана данная статья.