c++ - 事件驱动模拟类

Question

我正在完成 Bjarne Stroustrup 在 The C++ Programming Language 中的一些练习。我对第 12 章末尾的问题 11 感到困惑：

(*5) 设计并实现一个用于编写事件驱动模拟的库。提示：<task.h>。...类任务的对象应该能够保存其状态并恢复该状态，以便它可以作为协程运行。特定任务可以定义为从任务派生的类的对象。一个任务要执行的程序可能被定义为一个虚函数。...应该有一个调度程序实现虚拟时间的概念。...任务需要沟通。为此设计一个班级队列。...

我不确定这到底是什么要求。任务是一个单独的线程吗？（据我所知，没有系统调用就不可能创建一个新线程，而且由于这是一本关于 C++ 的书，我不相信这是意图。）没有中断，如何启动和停止运行功能？我认为这将涉及忙等待（也就是说，不断循环并检查条件），尽管我看不出如何将其应用于可能在一段时间内不会终止的函数（例如，如果它包含无限循环） .

编辑：请在下面查看我的帖子以获取更多信息。

score 5 · Accepted Answer

这是我对“事件驱动模拟”的理解：

控制器处理事件队列，安排事件在特定时间发生，然后执行队列中的顶部事件。
事件在预定时间瞬间发生。例如，“移动”事件将更新模拟中实体的位置和状态，以使状态向量在当前模拟时间有效。“感知”事件必须确保所有实体的状态都在当前时间，然后使用一些数学模型来评估当前实体对其他实体的感知能力。（想想机器人在板上移动。）
因此，时间是不连续的，从一个事件跳到另一个事件。将此与时间驱动的仿真进行对比，其中时间以离散的步长移动，并且所有实体的状态在每个时间步长（大多数 Simulink 模型）都会更新。
然后事件可以按其自然速率发生。在模拟中以最佳速率重新计算所有数据通常没有意义。

大多数生产事件驱动的模拟在单线程中运行。它们本质上可能很复杂，因此尝试同步多线程模拟往往会增加指数层的复杂性。话虽如此，有一个称为分布式交互式模拟（DIS）的多进程军事模拟标准，它使用预定义的 TCP 消息在进程之间传输数据。

编辑：定义建模和仿真之间的区别很重要。模型是系统或过程的数学表示。模拟是从一个或多个在一段时间内执行的模型构建的。同样，事件驱动的模拟从一个事件跳到另一个事件，而时间驱动的模拟以恒定的时间步长进行。

score 3 · Accepted Answer

提示：<task.h>。

是对早期版本的 CFront附带的旧协作式多任务库的引用（您也可以在该页面下载）。

如果您阅读论文“ A Set of C++ Classes for Co-routine Style Programming ”，事情会变得更有意义。

补充一点：

我不是一个使用任务库的足够老的程序员。但是，我知道 C++ 是在 Stroustrup 在 Simula 中编写了一个模拟后设计的，该模拟具有许多与任务库相同的属性，所以我一直对它很好奇。

如果我要实现书中的练习，我可能会这样做（请注意，我没有测试过这段代码，甚至没有尝试编译它）：

class Scheduler {
    std::list<*ITask> tasks;
  public:
    void run()
    {
        while (1) // or at least until some message is sent to stop running
            for (std::list<*ITask>::iterator itor = tasks.begin()
                      , std::list<*ITask>::iterator end = tasks.end()
                    ; itor != end
                    ; ++itor)
                (*itor)->run(); // yes, two dereferences
    }

    void add_task(ITask* task)
    {
        tasks.push_back(task);
    }
};

struct ITask {
    virtual ~ITask() { }
    virtual void run() = 0;
};

我知道人们会不同意我的一些选择。例如，为接口使用结构；但是结构的行为默认情况下从它们继承是公共的（默认情况下从类继承是私有的），并且我看不到从接口私有继承的任何价值，那么为什么不将公共继承设为默认值呢？

这个想法是，对 ITask::run() 的调用将阻塞调度程序，直到任务到达可以中断的点，此时任务将从 run 方法返回，并等待调度程序再次调用 run继续。“cooperative multitasking”中的“cooperative”是指“任务说什么时候可以被中断”（“coroutine”通常是指“cooperative multitasking”）。一个简单的任务可能只在它的 run() 方法中做一件事，一个更复杂的任务可能会实现一个状态机，并可能使用它的 run() 方法来确定对象当前处于什么状态，并根据它调用其他方法在那个状态。任务必须偶尔放弃控制以使其发挥作用，因为这就是“合作多任务”的定义。这也是所有现代操作系统不使用协作多任务处理的原因。

此实现不（1）遵循公平调度（可能保持在任务的 run() 方法中花费的时钟滴答总数，并跳过相对于其他任务使用太多时间的任务，直到其他任务“赶上”） , (2) 允许删除任务，甚至 (3) 允许停止调度程序。

至于任务之间的通信，您可以考虑查看Plan 9 的 libtask或Rob Pike 的 newsqueak以获得灵感（“Newsqueak 的 UNIX 实现”下载包括一篇论文“Newsqueak 的实现”，该论文讨论了有趣的虚拟机中的消息传递）。

但我相信这是 Stroustrup 心目中的基本骨架。

score 2 · Accepted Answer

在我看来，这个练习要求你实现一个协作式多任务调度程序。调度程序以虚拟时间运行（您定义/实现的任何级别的时间滴答），根据队列选择要运行的任务（请注意，您需要实现的描述）以及当前任务何时运行完成后，调度程序选择下一个并开始运行。

score 2 · Accepted Answer

离散事件模拟的通用结构基于以时间值为键的优先级队列。在广义上它是这样的：

    虽然（不是结束条件）：
        从优先级队列中弹出下一个事件（时间最短的事件）
        处理该事件，这可能会产生更多事件
        如果生成新事件：
            将其放置在其生成时间键控的优先级队列中

协同程序将模型的视图从以事件为中心变为以实体为中心。实体可以经历一些生命周期（例如接受作业、获取资源 X、处理作业、释放资源 X、将作业放入队列以进行下一步）。这更容易编程，因为抓取资源是使用类似信号量的同步原语处理的。作业和同步原语在幕后生成事件并将它们排队。

这给出了一个在概念上类似于操作系统中的进程的模型，并且当进程的输入或它所请求的共享资源可用时，调度程序唤醒进程。协程模型使仿真更容易理解，这对于仿真复杂系统很有用。

score 1 · Accepted Answer

（我不是 C++ 开发人员）

可能这意味着您需要创建一个类 Task（如在 Event 中），该类主要由回调函数指针和预定时间组成，并且可以存储在 Scheduler 类的列表中，而后者基本上应该保留跟踪计时器并在时间到达时调用每个任务的函数。这些任务应该由模拟的对象创建。

如果您在离散模拟方面需要帮助，请继续编辑问题。

score 1 · Accepted Answer

这是对 Titandecoy 对 SottieT812 回答的评论的回应。它对于评论来说太大了，所以我决定让它成为另一个答案。

从某种意义上说，它是事件驱动的，模拟状态仅响应事件而改变。例如，假设您有两个事件导弹发射和导弹撞击。当启动事件执行时，它会计算出影响的时间和地点，并在适当的时间安排影响事件。导弹的位置不是在发射和撞击之间计算的，尽管它可能会有一个方法可以被其他对象调用以获取特定时间的位置。

这与时间驱动的模拟形成对比，其中导弹（以及模拟中的每个其他对象）的确切位置是在每个时间步长之后计算的，比如 1 秒。

根据模型的特性、所需答案的保真度以及许多其他因素，事件驱动或时间驱动的仿真可能会表现得更好。

编辑：如果有人有兴趣了解更多信息，请查看冬季模拟会议的论文

score 1 · Accepted Answer

有一本书和名为DEMOS（Simula 上的离散事件建模）的框架描述了一个基于协程的框架（同名的 DEMOS）。尽管已经 30 岁左右，DEMOS 实际上是一个相当不错的系统，而Graham Birtwistle是一个非常好的人。

如果你在 C++ 上实现协同例程（想想 setjump/longjump），你应该看看这本书，了解一个非常非常优雅的离散事件建模框架。虽然它已经 30 年了，但它有点永恒的经典，并且仍然拥有粉丝群。

score 0 · Accepted Answer

在“me.yahoo.com/...”链接的论文中，描述了 task.h 类：

任务并行执行
任务可能会暂停并稍后恢复

该库被描述为一种多道程序设计方法。

是否可以在不使用线程或单独进程的情况下做到这一点？

c++ - 事件驱动模拟类

8 回答 8

Related

Reference