CIS307: Some hints for Homework 1

You are required to do a discrete event simulation of a computer system. The system consists of three servers - a CPU and two disks.

The status of a server is busy if there is a job being serviced by the server and free otherwise. A job arriving at the server starts being serviced immediately if the server is free and enters a FIFO queue that is associated with the server if the server is busy. A state of the system is a snapshot of the system that captures information relevant to the activities of the system at an instant in time. The state includes the status of each server and the contents of their queues. The following are the types of events that can occur in the system:

  1. Arrival of a job to the system.
  2. Completion of service at CPU (server 1).
  3. Completion of service at Disk1 (server 2).
  4. Completion of service at Disk2 (server 3).
  5. Termination of the simulation.

Whenever an event occurs the system undergoes a state transition and enters a state determined completely by the type of the event and the state of the system at the time of occurence of the event. The simulation process consists of tracing the state transitions that the system undergoes in chronological order from the initial state at the start of the simulation until termination at the end of the simulation period.

Arrival events are fundamental to the system as they give rise to subsequent departure events. Since the time between successive arrivals is uniformly distributed in the interval AMIN..AMAX, we may use a random number generator to approximate the distribution and determine the temporal distance between successive arrival events. We can compute the time a job leaves a server when we know the time when that job started service at the server. This is so since the service times are also uniformly distributed random variables. When a job arrives to a server it starts service if the server is free and there are no jobs waiting for the server at that time. Otherwise the job enters the queue for that server. The job leaves the queue to receive service when the job ahead of it leaves the server.

It is assumed that the servers are free and the queues are empty at the start of the simulation. It is also assumed that the first arrival coincides with the start of the simulation.

Priority Queue

A priority queue is a data structure for maintaining a set S of elements, each with an associated value called a key.
A priority queue supports the following operations.
InsertPQ(S,x) : Inserts the element x into the set S.
DeletePQ(S): Removes and returns the element of S with the largest/smallest key as required.

For this homework the key field in each event of the priority queue is the time of occurence of that event. The events will be stored in the priority queue in ascending order of the value of the key field i.e., in ascending order of their times of occurence. When it is time to remove an event from the priority queue the event with the smallest key field value is removed. The priority queue may be implemented as a doubly linked list or a MIN heap.

Computing the Average size of a Queue

Avg. queue size = w1*l1 + w2*l2 + ... + wn*ln
where wi = (Period of time for which length of the queue was li)/(Total time of simulation)

In the above formula the summation is over the number of sucessive periods with distinct queue lengths in adjacent periods till the end of the simulation.

I suggest that you read the input parameters for the simulation from a file so that as you modify your program and test it you don't have to enter all the input parameters every time you run your program.

Data Structures for the program

// Type definitions //
EventType = (Arrival, Departure_1, Departure_2, Departure_3, Termination);

structure Job
    JobId : Integer     //Each job has an id, one of: 1, 2, 3, ..
    ArrivalTime : Real
end Job;

structure Event
    EventKind : EventType
    EventTime : Real
    JobInfo : Pointer to Job
    Next : Pointer to Event
end Event;

structure PriorityQueueInfo
    First : Event
    Last : Event
end PriorityQueueInfo;

structure ServerQueueInfo
    First : Event
    Last : Event
    LastUpdate : Real
end ServerQueueInfo;

structure InputParameters 
    SEED : Integer
    INITTIME : Integer
    FINTIME : Integer
    AMIN : Integr
    AMAX : Integer
    S1MIN : Integer
    S1MAX : Integer
    S2MIN : Integer
    S2MAX : Integer
    S3MIN : Integer
    S3MAX : Integer
    POUT  : Integer  // For simplicity, we assume that the routing decision
    P1    : Integer  // at SWITCH is done comparing a random number ROUTVAL
                     // between 0 and 100 with the values POUT and POUT+P1.
                     // Then job goes out if ROUTVAL is less than POUT, goes
                     // to Disk1 if greater than POUT but less than POUT+P1
                     // and to Disk2 otherwise.
    LOG_FILENAME : Pointer to String
end InputParameters;

Assume that the operations CreateFQ, InsertFQ, DeleteFQ, and IsemptyFQ for the abstract data type FIFO queue, and their counterparts CreatePQ, InsertPQ, DeletePQ and IsemptyPQ for the abstract data type priority queue are already defined.

The algorithm also invokes the functions

Function InitRandom(Seed : integer): void Function MyRandom(Low, High : integer):integer

MyRandom returns a random number between Low and High. InitRandom must be called before we can use MyRandom.

Algorithm

procedure DiscreteEventSimulation
var 
    Agenda : PriorityQueueInfo
    QUEUE1, QUEUE2, QUEUE3 : ServerQueueInfo
    NewEvent : Event;
    Server1BusyFrom, Server2BusyFrom, Server3BusyFrom: Real; 
    ROUTVAL : integer

//Read SEED, POUT, P1, INITTIME, FINTIME, AMIN, AMAX// 
//Read S1MIN, S1MAX, S2MIN, S2MAX, S3MIN, S3MAX, LOGFILE_NAME//

//Initialize Agenda with Arrival and Termination events //
//Initialize QUEUE1, QUEUE2, and QUEUE3 to be empty //
InitRandom(SEED);

Server1Busy = Server2Busy = Server3Busy = FALSE

repeat
  CurrentEvent = DeletePQ(Agenda)
  CurrentTime = CurrentEvent.EventTime
  //Log event in the Log file//

  switch(Currentevent.EventKind)

      case Arrival:  
        //Record arrival time @CPU//
        //Create a new event and assign it to Newevent
          The type of NewEvent is Arrival and 
          EventTime = CurrentTime + Random(AMIN, AMAX)//
        InsertPQ(Agenda, NewEvent)

        if Server1Busy then
              [InsertFQ(QUEUE1, CurrentEvent)
              //Update QUEUE1 stats//]
        else
              [Server1Busy = TRUE
               //Create a Departure_1 event occuring 
                 @CurrentTime + Random(S1MIN, S1MAX)
                 Let NewEvent be this event//
               InsertPQ(Agenda, NewEvent)
               Server1BusyFrom = CurrentTime]
        break;

      case Departure_1: /*job is leaving CPU*/
          //Compute response time for CPU, update stats//
          /*CPU is now free - take care of it*/
          if IsEmptyFQ(QUEUE1) then                
              Server1Busy = FALSE
          else 
              [CurrentEvent = DeleteFQ(QUEUE1)
              //Update QUEUE1 stats//
              //Create a Departure_1 event occuring 
                @CurrentTime + Random(S1MIN, S1MAX)
                Let NewEvent be this event//
              InsertPQ(Agenda, NewEvent)
              Server1BusyFrom = currentTime]

          /*See what happens to this job*/
          ROUTVAL = MyRandom(0,100)
          if ROUTVAL less or equal POUT then  /*job going out*/
              [//Update stats; remove this job and event//]
          else if ROUTVAL less or equal POUT+P1 then /*job going to Disk1*/
              [if Server2Busy then                
                  [InsertFQ(QUEUE2, CurrentEvent)
                   //Update QUEUE2 stats//]
               else 
                  [Server2Busy = TRUE
                  //Create a Departure_2 event occuring 
                    @CurrentTime + Random(S2MIN, S2MAX)
                    Let NewEvent be this event//
                  InsertPQ(Agenda, NewEvent)
                  Server2BusyFrom = CurrentTime]
          else /*Going to Disk2*/
              [if Server3Busy then                
                  [InsertFQ(QUEUE3, CurrentEvent)
                   //Update QUEUE3 stats//]
               else 
                  [Server3Busy = TRUE
                  //Create a Departure_3 event occuring 
                    @CurrentTime + Random(S3MIN, S3MAX)
                    Let NewEvent be this event//
                  InsertPQ(Agenda, NewEvent)
                  Server3BusyFrom = CurrentTime]
          break
     
      case Departure_2: 
          //Compute response time for Disk1, update stats//
          /*Disk1 is now free - take care of it*/
	  if IsEmptyFQ(QUEUE2) then
  	     [Server2Busy = FALSE]
  	  else
             [CurrentEvent = DeleteFQ(QUEUE2)
             //Update QUEUE2 stats//
	     //Create a Departure_2 event occuring
               @CurrentTime + Random(S2MIN, S2MAX)
               Let NewEvent be this event// 
             InsertPQ(Agenda, NewEvent)
             Server2BusyFrom = CurrentTime]

          /*The job now goes back to the CPU*/
          if Server1Busy then
             [InsertFQ(QUEUE1, CurrentEvent)
             //Update QUEUE1 size stats//]
          else 
              [Server1Busy = TRUE
               //Create a Departure_1 event occuring 
               @CurrentTime + Random(S1MIN, S1MAX)
               Let NewEvent be this event//
               InsertPQ(Agenda, NewEvent)
               Server1BusyFrom = CurrentTime]
          break

      case Departure_3: 
          //Compute response time for Disk2, update stats//
          /*Disk2 is now free - take care of it*/
	  if IsEmptyFQ(QUEUE3) then
  	     [Server3Busy = FALSE]
  	  else
             [CurrentEvent = DeleteFQ(QUEUE3)
             //Update QUEUE3 stats//
	     //Create a Departure_3 event occuring
               @CurrentTime + Random(S3MIN, S3MAX)
               Let NewEvent be this event// 
             InsertPQ(Agenda, NewEvent)
             Server3BusyFrom = CurrentTime]

          /*The job now goes back to the CPU*/
          if Server1Busy then
             [InsertFQ(QUEUE1, CurrentEvent)
             //Update QUEUE1 size stats//]
          else 
              [Server1Busy = TRUE
               //Create a Departure_1 event occuring 
               @CurrentTime + Random(S1MIN, S1MAX)
               Let NewEvent be this event//
             InsertPQ(Agenda, NewEvent)
             Server1BusyFrom = CurrentTime]
          break

      case Termination:
          //Log Event in the Log file//
          //check if CPU and Disks are busy
          if so, update their busy times //
          //If the queues are not empty then
          update their size stats //
          //Compute Results//
          exit
forever;
In writing this homework be sure to partition your program into a number of files. For example, it would be appropriate to put the code for the FIFO queue in files fifo.h and fifo.c. For example, code for the priority queue could go in files agenda.h and agenda.c. If you are accustomed to writing C++ code, you can in C create an .h and .c file for each class.