Event-driven simulation class

Question

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 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.

Answer 1

(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.

Answer 2

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.

Answer 3

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.

Answer 4

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.

Answer 5

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?

Answer 6

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

Answer 7

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.

Answer 8

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.