Discrete event simulation is concerned with processes and systems that change at discrete instants. For example, pushing an elevator button, starting of a motor, stopping of a motor, and turning on a light, are all discrete events because there is an instant of time at which each occurs. Activities such as moving a train from point A to point B are not discrete events because they have a time duration. However, we can model an event like this as two separate discrete events: the event of the train leaving point A, and the event of the train arriving at point B. If we associate a time value with each discrete event,then we can model the duration activities as the difference between the times associated with the events marking the beginning and the end of each activity. For example, we can specify that the arrival at point B occurs 3 hours and 37 minutes after leaving point A. Therefore, we can see that if the train leaves point A at 7:53pm, then it will arrives at point B at 11:30pm.
The purpose of a discrete event simulation is to study a complex system by computing the times that would be associated with real events in a real-life situation. In the train example above, suppose that we know that when the train arrives at point B, a load is transferred to a second train that arrives at point C after 45 minutes. That is, the second train's departure from point B is triggered by the first train's arrival, and the arrival at point C occurs with a delay of 45 minutes after the departure from point B. In this simple example, we can use discrete event simulation to determine that the second train will arrive at point C at 12:15am.
Use priority queues to build the Future Event Set. After computing an event, all we need to do is INSERT() it into our data structure. The next event can be extracted easily with the operation DELETE_MIN.
Fig. 1.1 A future Event Set
For any furhter information on this subject, please refer to topic #17 of the lecture notes.
An operating system is a program that manages, among other things, the usage of the CPU in an environment with many processes (multi-user, multi-tasking, UNIX, etc.). Each process can only be executed for a short amount of time, after which, if its time limit is up without having terminated its task, the process will be placed on the queue again. A good implementation for this type of queue would be a priority queue, to optimize the overall processing time of jobs. The priority could be set de pending on how long the process has been waiting (to avoid starvation), and could also depend on who started the process (e.g. a process started by the root would have higher priority than a process started by a user).
Fig. 2.1 Operating system using a priority queue method.
Fig. 2.2 Operating system using the Round Robin method.
Priority queues can also be used to sort in a very efficient manner.
Here is a generic sorting algorithm:
for all input items x do :
insert(x, priority queue);
while NOT EMPTY(priority queue) do
output deletemin (priority queue);
(* they come out in order *)
Note how this algorithm is very short (4 lines), thus easy to
remember, as well as very efficient, since it can sort in worst-case 
(n log n).
(see next topic on heaps
for more information)
