Отмена событий во время моделирования дискретных событий

Question

У меня есть вопрос относительно механизма декомпрессии во время моделирования дискретных событий.

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

Может быть другое событие в очереди, чья метка времени больше, чем временная метка события, которое заблокировано ресурсом.

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

В таком сценарии как работает использование очереди приоритетов исключительно на основе временной метки --- и независимо от доступности ресурсов?

Answer 1

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

Когда клиент присоединяется к очереди, количество клиентов очереди увеличивается или клиент попадает в очередь кассира.

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

Эти очереди или счетчики не зависят от механизма планирования событий - запланированные события управляют этими очередями, они не зависят от них для планирования.

Answer 2

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

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

Для более полного объяснения того, как работают моделирование дискретных событий, посмотрите на это introductory tutorial paper.