next up previous
Next: Barber simulation Up: November 6 Previous: November 6


Event-driven simulation

If events aren't guaranteed to occur at regular intervals, and we don't have a good bound on the time step (it shouldn't be so small as to make the simulation run too long, nor so large as to make the number of events unmanageable), then it's more appropriate to use an event-driven simulation. A typical example might be simulating a lineup at a bank, where customers don't arrive at regular time intervals, and may be deterred by a long lineup.

This approach uses a list of events that occur at various time, and handles them in order of increasing time. Handling an event may alter the list of later events. The simulation makes time ``jump'' to the time of the next event.

How do we stop? Again, we can stop when time reaches a certain point, or when the system reaches a certain state. Here is a generic event-driven algorithm:

  1. Initialize system state
  2. Initialize event list
  3. While (simulation not finished)
    1. Collect statistics from current state
    2. Remove first event from list, handle it
    3. Set time to the time of this event.

How is the list of events managed? It should be ordered by increasing time (a priority heap might be efficient). We don't generate all the events in the list at the beginning (this would be analogous to knowing the entire sequence of states of the simulation at the outset). Instead we initialize the simulation with certain events, with their associated times. Certain events may be handled by scheduling later events, which are inserted at the appropriate place in the event list.

As stated above, we could stop when time reaches or exceeds a certain point, or once the system reaches a certain state (the bank is lined up for two blocks...). Sometimes we want the stopping condition itself to be randomized: we can schedule a random pseudo-event which doesn't change the state of the model, but simply stops the simulation.


next up previous
Next: Barber simulation Up: November 6 Previous: November 6
Danny Heap 2002-12-16