Topics in Performance Evaluation – Exercise 2a

Topics in Performance Evaluation

Exercise 2a – Basic Event-Driven Simulation

We will use event-driven simulation in several exercises. In this one your assignment is to get a handle on the basics.

Background

Simulation is perhaps the most common method to evaluate computing systems. In particular, event driven simulation is used to trace activities in the system and how they affect each other.

Event-driven simulation is suitable for computer systems because it is discrete: it is based on the assumption that the system does not change in a continuous manner, but rather in discrete events. For example, events may be

a user submitted a new job
a user clicks on a mouse button
an interrupt occurs indicating that a disk I/O operation has finished
a packet has arrived to a router
etc.

Typically, each event is identified by its type, it has a timestamp of when it occurs, and perhaps some additional specific data (e.g. the resource requirements of the submitted job).

Event-driven simulation is based on a queue of pending events. The queue is sorted in timestamp order. The simulation proceeds as follows:

Take the first event from the queue (meaning the one with the earliest timestamp).
Advance the simulation time to the time of this event.
"Do" the event. This typically means making some changes to the state of the system.
If the event is related to something we are trying to measure using the simulation, record this.
If the event causes new events to be generated, insert them into the event queue with the appropriate timestamps.
Return to step 1.

The simulation ends when the event queue empties, or when it has been run for "long enough". Thus the initialization includes the creation of at least one initial event.

Assignment

Your assignment is to design and implement the core of an event-driven simulator, i.e. the event queue and mechanism that drives the simulation.

The main design decision you need to make involves the event queue. You need to be able to insert events for arbitrary future times, and retrieve the event with the smallest time. What is a good data structure?

To verify that your engine works, build a small simulation that uses it. For example, define two simple types of events. Event A does nothing except to schedule another event of the same type 2 time units later. Event B likewise does nothing, but schedules another event of the same type 5 time units later. Initially schedule an event A at time 1 and an event B at time 2. Then start the simulation, and keep track of how many events occur at each time instant. Terminate the simulation when simulation time hits 20. Did you get the right results?

Submit

You don't need to submit this exercise – it is just a prelude to future exercises. But doing it will help you understand what we'll be doing better. Moreover, what you write here will serve you in several additional exercise and save time later.

Also, when you work on this think about the following points:

How should events with the same timestamp be sorted? What are the implications?
Is it permissible to create new events with timestamps equal to the current simulation time? What are the implications?
When you use a random number generator in your simulation (for example: create a new event after 2 time units on average, instead of deterministically), what happens when you run the simulation several times? Is this good or bad? Why?

We'll discuss these points in class.

To the course home page