functional-programming - 没有全局队列的离散事件模拟？

Question

我正在考虑对物质流网络进行建模。有些进程以一定的速度运行，缓冲区可以上溢或下溢，以及它们之间的连接。

我认为使用全局事件队列以经典的离散事件模拟 (DES) 方式对此进行建模没有任何问题。我尝试在没有队列的情况下对系统进行建模，但在早期阶段失败了。我仍然不明白为什么需要队列的根本原因，至少对于源自网络“内部”的事件。

无队列 DES 的思想是将整个网络视为一个函数，它从外部世界获取事件流并返回状态变化流。网络中的每个节点都应该只受到与其直接相连的节点的影响。总的来说，我对 Haskell 的箭头和函数式响应式(Reactive)编程 (FRP) 寄予厚望，但我仍在学习。

事件队列对我来说看起来太“全局化”了。如果我的网络分成两个子网，它们之间没有连接，我只询问一个子网的状态变化，另一个子网根本不应该做任何计算。在这种情况下，我可以使用两个事件队列。但是，一旦我连接了两个子网，我就必须将所有事件放入一个队列中。我不喜欢这样的想法，即我需要知道网络的拓扑才能设置我的队列。

所以

有人知道不需要全局队列的 DES 算法吗？

这有什么困难甚至不可能的原因吗？

FRP 在 DES 环境中有用吗？

Answer 1

为了回答第一点，不，我不知道任何不需要全局事件队列的离散事件模拟 (DES) 算法。可以有一个事件队列的层次结构，其中每个事件队列在其父事件队列中表示为一个事件(对应于其下一个事件的时间)。如果将一个新事件添加到事件队列中，使其成为队列的下一个事件，则需要在其父级中重新安排事件队列以保持事件执行的顺序。但是，您最终仍将归结为一个全局事件队列，它是层次结构中所有其他事件的父级，并调度每个事件。

或者，您可以省去 DES 并执行一些更类似于可编程逻辑 Controller (PLC) 的操作，该 Controller 每隔一小段时间就会重新评估整个网络的状态。但是，通常情况下，这会慢很多(它甚至可能不如实时运行快)，因为大多数时候它无事可做。如果您选择的时间增量太大，模拟可能会失去准确性。

对第二点最简单的回答是，最终，据我所知，没有全局事件队列是不可能的。每个模拟事件都需要在正确的时间执行，并且 - 由于时间不能倒退 - 事件的调度顺序很重要。当前仿真时间由当前事件执行的时间定义。如果你有单独的事件队列，你也有单独的时钟，至少可以说这会让事情变得非常困惑。

在您的情况下，如果您的子网是完全独立的，您可以单独模拟每个子网。然而，如果一个子网的状态影响整个网络的状态，并且整个网络的状态影响每个子网的状态，那么 - 由于一个事件受到它之前的事件的影响，所以只能影响那些发生在它之前的事件跟随，但不能影响它之前的内容 - 您必须使用全局事件队列模拟整个网络。

如果有任何安慰的话，真正的 DES 模拟不会在事件之间执行任何处理(除了确定下一个事件是什么)，因此如果所有操作都发生在另一个子网中，则不应在一个子网中浪费处理。

最后，函数响应式(Reactive)编程 (FRP) 在 DES 的上下文中绝对有用。事实上，我现在使用这种方法在 Scala 中编写了很多我的 DES 模拟。

我希望这有帮助!

更新 : 自从写了上面的内容，我用过 Sodium (一个优秀的 FRP 库，OP 在下面的评论中引用了它)，并且可以添加一些进一步的解释:Sodium 提供了一种订阅事件的方法，以及在这些事件发生时执行操作的方法。但是，这里我使用的术语是一般意义上的事件，例如用户在 GUI 中单击了按钮，或者网络包到达等。换句话说，事件不一定是模拟事件。

您仍然可以使用钠——或任何其他 FRP 库——作为模拟的一部分，订阅模拟事件并在它们发生时执行操作；然而，这些工具通常没有内置的仿真支持，因此您必须将仿真引擎作为仿真事件的来源，就像将 GUI 作为用户交互事件的来源一样。全局事件队列必须驻留在该引擎中。

顺便说一句，如果您尝试执行并行或分布式仿真模型执行，事情会变得相当复杂。在这些情况下，您有多个事件队列，但它们必须同步(呈现单个队列的外观)。两种基本方法是保守同步和乐观同步。