Hints on Homework 1: Discrete-Event Simulation

• What is an Event
• What is Discrete Event Simulation
• Simulation and Global Time
• Event Queue and Server Queues
• Generating Random Numbers

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 is an event. When it occurs the state of the system changes and we have to take a number of actions, like: if the CPU is busy, the job waits in the CPU's queue, otherwise it starts service immediately on the CPU. Another event is the completion of service at the CPU. When that happens we have to decide if the job goes out, or to disk1, or to disk2; if to disk1 we have to determine if it goes in the queue or starts service. Here is something that is not an event: the routing decision for a job at the Switch. 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 job 7" 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 system in your homework can be described in terms of what it does when there is an Arrival event, or a CPU Service completion event [departure], or a Disk1 Service completion event [departure], or ...
  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 at some time G1 equal to INITTIME. The first event that can occur is the arrival of the first job. [Certainly no job can complete service at the CPU or a disk since initially no job is in the system.] When will this arrival take place? For simplicity we assume that it occurs exactly at G1. Now that the first event, the first arrival, has occurred, what will happen next? Two events are going to happen:
  • There will be a next arrival. When? At time G1 plus a random value A2 between AMIN and AMAX.
  • The first job will terminate service at the CPU after a random time interval S1 in the range S1MIN .. S1MAX.
  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 next 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 a 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 time stamps of expected occurrence. New events will be enqueued in the agenda at the place indicated by the time stamp of the event. We dequeue the event that has the smallest time stamp.

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 some specified value.

If in Unix you execute

• man rand
you will be told about the functions rand, rand_r, and srand.
If you execute
• man random
you will be told about the functions random, srandom, initstate, and setstate.
Here is an example of use of random and initstate:

/* myran.c - Testing random and initstate */

#include 
#define SIZE 1000

void initrandom(unsigned seed){
  /* This function must be called before we can generate random numbers.
   * You can choose as seed any number, say, 1, 123, 357, ...
   */
#define RANDSIZE 256
  static char randstate[RANDSIZE];
  initstate(seed, randstate, RANDSIZE);
}

int myrandom(int low, int high){
  /* It returns a random number in the interval [a,b]
   */
  return (low + random()%(high-low+1));
}

int main() {
  /* It generates and prints SIZE random numbers in the interval [10,20]. 
   * Then prints out their average (it should be close to 15).
   */
    int i;
    int table[SIZE];
    int sum = 0;

    initrandom(1357);
    for (i=0; i<SIZE; i++) {
      table[i] = myrandom(10,20);
      sum += table[i];
      printf("%2d\n", table[i]);
    }
    printf("the average is %f\n", sum/(float)SIZE);
    exit(0);
}

ingargiola@cis.temple.edu