Hints on Homework 1: Discrete-Event Simulation

What is an Event

 It is an an action that occurs at an instant in time and changes the state of a system. For example, in our homework, the arrival of a new job it is an event. When it occurs the state of the system changes and we have to take a number of actions, like: if this job goes to the CPU or to the disk; once there, if it waits in the queue or starts service. Another event is the completion of service at the CPU [same for the disk]. When that happens we have to decide what the job does next; if it goes to the CPU we have to determine if he goes in the queue or starts service. Here is something that is not an event: the routing decision for a job at Switch 2 if to go or not to the output. It is so since the routing decision is an integral part of what is done for the event when the job leaves the CPU. Note that there is a distinction between "Event type" and "Event instance". "Arrival of a job" is an Event type. "Arrival of a specific job" is an Event instance.

What is Discrete Event Simulation

 It is a way of simulating [i.e. of analysing models of] systems. It can be done for systems whose behavior can be expressed in terms of what they do in correspondence to a certain number of event types. For example, the example in your homework can be described in terms of what the system does when there is an Arrival event, or a CPU Service completion event [departure], or a disk Service completion event [departure].
Discrete event simulation is used extensively when trying to predict or analyze the behavior of computer systems. Systems like chemical plants where the process being carried out is continuous [i.e. does not have discrete times where the state changes] cannot be simulated this way.

Simulation and Global Time

 The simulation starts at some time G0 equal to INITTIME. For simplicity, we assume that this is also the arrival of the first job. Thus the first arrival is at time G1 equal to INITTIME. Now that the first event, the first arrival, has occurred, what will happen next? Two things are going to happen:
  1. There will be a next arrival. When? At time G1 plus a random value A2 between AMIN and AMAX.
  2. The first job will terminate service at the CPU after a random time interval S1 in the range S1MIN .. S1MAX. Let's call S1* the time when the service will terminate.
Then the two events are going to happen, respectively, at time G1+A2 and G1+S1*. Say that G2 is the smaller of these two values [if the two values are equal one is chosen in some fashion]. Then the next event occurs at time G2 and the global time jumps from G1 to G2. No change of state is possible between two successive events.
This is how the simulation proceeds. We consider what events are going to happen next, we choose the event that will occur the sooner, and we advance the global clock to the time of this next event. When an event occurs we do all the things implied by that event.

Event Queue and Server Queues

 We have seen that we keep in a queue the events that are expected to occur next. And we have seen that jobs wait in a queue to be served by the CPU or by the disk. BUT the two kinds of queues are very different.

The queue for events, called Event Queue or Agenda, is a priority queue where events are kept in sorted order for ascending timestamps of expected occurrence. New events will be enqueued in the agenda at the place indicated by the timestamp of the event. We dequeue the event that has the smallest timestamp.

Instead server queues are FIFOs where we store "jobs" in the order of arrival.

Generating Random Numbers

Random numbers are used extensively when programming. Thus each system, application, and language has some means to generate random number. The random number generators that we usually find produce numbers that are uniformly distributed in some specified range. For example we may find a generator of real numbers uniformly distributed in the interval (0.0, 1.0) or a generator of integer numbers uniformly distributed in the range (0, MAXVAL), where MAXVAL is a user specified value.

If in Unix you execute

you will be told about the functions rand, rand_r, and srand.
If you execute you will be told about the functions random, srandom, initstate, and setstate.
If you decide to use the function random, you will get integer values uniformly distributed in the interval (0, (2**31)-1). Using random you can easily define a function, say,myrandom, that returns real numbers in the interval (0.0, 1.0). You just call random, float its result and divide it by (2**31)-1.
Once you have a value in the interval (0.0, 1.0) you can determine a random number uniformly distributed in any interval (a,b) with the formula
ingargiola@cis.temple.edu