事件驱动模拟类

发布于 07-09 23:57 字数 533 浏览 17 评论 0原文

我正在完成 Bjarne Stroustrup 所著《C++ 编程语言》中的一些练习。 我对第 12 章末尾的问题 11 感到困惑:

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

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

编辑:请参阅我下面的帖子了解更多信息。

I am working through some of the exercises in The C++ Programming Language by Bjarne Stroustrup. I am confused by problem 11 at the end of Chapter 12:

(*5) Design and implement a library for writing event-driven simulations. Hint: <task.h>. ... An object of class task should be able to save its state and to have that state restored so that it can operate as a coroutine. Specific tasks can be defined as objects of classes derived from task. The program to be executed by a task might be defined as a virtual function. ... There should be a scheduler implementing a concept of virtual time. ... The tasks will need to communicate. Design a class queue for that. ...

I am not sure exactly what this is asking for. Is a task a separate thread? (As far as I know it is not possible to create a new thread without system calls, and since this is a book about C++ I do not believe that is the intent.) Without interrupts, how is it possible to start and stop a running function? I assume this would involve busy waiting (which is to say, continually loop and check a condition) although I cannot see how that could be applied to a function that might not terminate for some time (if it contains an infinite loop, for example).

EDIT: Please see my post below with more information.

如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。

评论(8

知足的幸福2024-07-16 23:57:15

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

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

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

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

Here's my understanding of an "event-driven simulation":

  • A controller handles an event queue, scheduling events to occur at certain times, then executing the top event on the queue.
  • Events ocur instantaneously at the scheduled time. For example, a "move" event would update the position and state of an entity in the simulation such that the state vector is valid at the current simulation time. A "sense" event would have to make sure all entities' states are at the current time, then use some mathematical model to evaluate how well the current entity can sense the other entities. (Think robots moving around on a board.)
  • Thus time progresses discontinuously, jumping from event to event. Contrast this with a time-driven simulation, where time moves in discrete steps and all entities' states are updated every time step (a la most Simulink models).
  • Events can then occur at their natural rate. It usually doesn't make sense to recompute all data at the finest rate in the simulation.

Most production event-driven simulations run in a single thread. They can be complex by their very nature, so trying to synchronize a multi-threaded simulation tends to add exponential layers of complexity. With that said, there's a standard for multi-process military simulations called Distributive Interactive Simulation (DIS) that uses predefined TCP messages to transmit data between processes.

EDIT: It's important to define a difference between modeling and simulation. A model is a mathematical representation of a system or process. A simulation is built from one or more models that are executed over a period of time. Again, an event driven simulation hops from event to event, while a time driven simulation proceeds at a constant time step.

惯饮孤独2024-07-16 23:57:15

提示:

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

如果您阅读论文“A Set of C++ Classes for Co-常规风格编程”的事情会变得更有意义。


添加一点:

我还不是一个足够老的程序员,无法使用任务库。 然而,我知道 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 来执行任务。继续。 “协作多任务处理”中的“协作”意思是“任务说何时可以被中断”(“协程”通常意味着“协作多任务处理”)。 一个简单的任务可能只在它的 run() 方法中做一件事,一个更复杂的任务可能会实现一个状态机,并且可能使用它的 run() 方法来确定对象当前处于什么状态,并根据情况调用其他方法就那个状态。 为了使其发挥作用,任务必须偶尔放弃控制权,因为这就是“协作多任务处理”的定义。 这也是所有现代操作系统不使用协作多任务处理的原因。

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

至于任务之间的通信,您可以考虑查看 Plan 9 的 libtaskRob Pike 的 newsqueak 获取灵感(“Newsqueak 的 UNIX 实现”下载包括一篇论文“Newsqueak 的实现”,该论文以有趣的方式讨论了消息传递)虚拟机)。

但我相信这就是斯特鲁斯特鲁普心目中的基本骨架。

Hint: <task.h>.

is a reference to an old cooperative multi-tasking library that shipped with early versions of CFront (you can also download at that page).

If you read the paper "A Set of C++ Classes for Co-routine Style Programming" things will make a lot more sense.


Adding a bit:

I'm not an old enough programmer to have used the task library. However, I know that C++ was designed after Stroustrup wrote a simulation in Simula that had many of the same properties as the task library, so I've always been curious about it.

If I were to implement the exercise from the book, I would probably do it like this (please note, I haven't tested this code or even tried to compile it):

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;
};

I know people will disagree with some of my choices. For instance, using a struct for the interface; but structs have the behavior that inheriting from them is public by default (where inheriting from classes is private by default), and I don't see any value in inheriting privately from an interface, so why not make public inheritance the default?

The idea is that calls to ITask::run() will block the scheduler until the task arrives at a point where it can be interrupted, at which point the task will return from the run method, and wait until the scheduler calls run again to continue. The "cooperative" in "cooperative multitasking" means "tasks say when they can be interrupted" ("coroutine" usually means "cooperative multitasking"). A simple task may only do one thing in its run() method, a more complex task may implement a state machine, and may use its run() method to figure out what state the object is currently in and make calls to other methods based on that state. The tasks must relinquish control once in a while for this to work, because that is the definition of "cooperative multitasking." It's also the reason why all modern operating systems don't use cooperative multitasking.

This implementation does not (1) follow fair scheduling (maybe keeping a running total of clock ticks spent in in task's run() method, and skipping tasks that have used too much time relative to the others until the other tasks "catch up"), (2) allow for tasks to be removed, or even (3) allow for the scheduler to be stopped.

As for communicating between tasks, you may consider looking at Plan 9's libtask or Rob Pike's newsqueak for inspiration (the "UNIX implementation of Newsqueak" download includes a paper, "The Implementation of Newsqueak" that discusses message passing in an interesting virtual machine).

But I believe this is the basic skeleton Stroustrup had in mind.

盛夏尉蓝2024-07-16 23:57:15

在我看来,这个练习是要求你实现一个协作式多任务调度程序。 调度程序在虚拟时间中运行(您在所需的任何级别定义/实现的时间标记),根据队列选择要运行的任务(请注意,提到的描述您需要实现一个),并且当前任务何时运行完成后,调度程序选择下一个并开始运行。

Sounds to me like the exercise is asking you to implement a cooperative multi-tasking scheduler. The scheduler operates in virtual time (time ticks you define/implement at whatever level you want), chooses a task to run based on the queue (note that the description mentioned you'd need to implement one), and when the current task is done, the scheduler selects the next one and starts it running.

波浪屿的海角声2024-07-16 23:57:15

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

    While (not end condition):
        Pop next event (one with the lowest time) from the priority queue
        Process that event, which may generate more events
        If a new event is generated:
            Place this on the priority queue keyed at its generated time

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

这提供了一个概念上类似于操作系统中的进程的模型,以及当进程的输入或它请求的共享资源可用时唤醒进程的调度程序。 协同例程模型使仿真变得更容易理解,这对于仿真复杂系统很有用。

The generalised structure of a discrete event simulation is based on a priority queue keyed on a time value. At a broad level it goes like:

    While (not end condition):
        Pop next event (one with the lowest time) from the priority queue
        Process that event, which may generate more events
        If a new event is generated:
            Place this on the priority queue keyed at its generated time

Co-routines change the view of the model from being event-centric to being entity-centric. Entities can go through some life-cycle (e.g. accept job, grab resource X, process job, release resource X, place job in queue for next step). This is somewhat easier to program as the grab resources are handled with semaphore-like synchronisation primitives. The jobs and synchronisation primitives generate the events and queue them behind the scenes.

This gives a model conceptually similar to processes in an operating system and a scheduler waking the process up when its input or a shared resource it has requested is available. The co-routine model makes the simulation quite a lot easier to understand, which is useful for simulating complex systems.

埖埖迣鎅2024-07-16 23:57:15

(我不是 C++ 开发人员)

这可能意味着您需要创建一个类 Task(如在 Event 中),该类主要由回调函数指针和计划时间组成,并且可以存储在列表中调度程序类,它基本上应该跟踪时间计数器并在时间到达时调用每个任务的函数。 这些任务应该由模拟对象创建。

如果您需要离散仿真方面的帮助,请继续编辑问题。

(I'm not a C++ dev)

Probably what it means is that you need to create a class Task (as in Event) that will consist mostly of a callback function pointer and a scheduled time, and can be stored in a list in the Scheduler class, which in turn basically should keep track of a time counter and call each Task's function when the time arrives. These tasks should be created by the Objects of the simulation.

If you need help on the discrete simulation side, go ahead and edit the question.

吃颗糖壮壮胆2024-07-16 23:57:15

这是对 titandecoy 对 SottieT812 的回答的评论的回应。 它对于评论来说太大了,所以我决定将其作为另一个答案。

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

这与时间驱动模拟形成对比,在时间驱动模拟中,导弹(以及模拟中的所有其他对象)的确切位置是在每个时间步长(例如 1 秒)后计算的。

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

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

This is in response to titaniumdecoy's comment to SottieT812's answer. Its much too large for a comment, so I decided to make it another answer.

It is event driven in the sense that simulation state only changes in response to an event. For example, assume that you have two events missile launch and missile impact. When the launch event is executed, it figures out when and where it will impact, and schedules an impact event for the appropriate time. The position of the missile is not calculated between the launch and impact, although it will probably have a method that can be called by other objects to get the position at a particular time.

This is in contrast to a time driven simulation, where the exact position of the missile (and every other object in the simulation) is calculated after every time step, say 1 second.

Depending on the characteristics of the model, the fidelity of the answer required, and many other factors, either event driven or time driven simulation may perform better.

Edit: If anyone is interested in learning more, check out the papers from the Winter Simulation Conference

栖竹2024-07-16 23:57:15

有一本名为 DEMOS (离散事件在 Simula 上建模)描述了基于协同例程的框架(同名 DEMOS)。 尽管已有 30 年左右的历史,DEMOS 实际上是一个相当不错的系统,Graham Birtwistle 是一个非常好的人。

如果您在 C++ 上实现协同例程(例如 setjump/longjump),您应该看看这本书,了解非常非常优雅的离散事件建模框架。 虽然已经有30年的历史了,但它仍然是永恒的经典,仍然拥有一批粉丝。

There is a book and framework called DEMOS (Discrete Event Modelling on Simula) that describes a co-routine based framework (the eponymous DEMOS). Despite being 30 years or so old DEMOS is actually quite a nice system, and Graham Birtwistle is a really nice guy.

If you implement co-routines on C++ (think setjump/longjump) you should take a look at this book for a description of a really, really elegant discrete event modelling framework. Although it's 30 years old it's a bit of a timeless classic and still has a fan base.

分分钟2024-07-16 23:57:15

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

  1. 任务并行执行
  2. 任务可以暂停并稍后恢复

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

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

In the paper linked to by "me.yahoo.com/..." which describes the task.h class:

  1. Tasks execute in parallel
  2. A task may be suspended and resumed later

The library is described as a method of multiprogramming.

Is it possible to do this without using threads or separate processes?

~没有更多了~
我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站,即表示您同意使用 Cookies 和您的相关数据。
原文