Some hints for Homework 1

You are required to do a discrete event simulation of a queueing network representing a computer system. The system consists of two servers - a CPU and a disk.

The status of a server is busy if there is a job being serviced at that server and free otherwise. A job arriving at the server is serviced immediately if the server is free, and enters a FIFO queue for 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 occur in the system:

1. Arrival of a job at either the CPU or the disk.
2. Completion of service at either the CPU or the disk.
3. 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 a given initial state at the start of the simulation until 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 separation of successive arrival events. When a job arrives at a server the time at which the job would leave the server can be computed if the server is not busy since the service times are also uniformly distributed random variables. Thus the departure event corresponding to an arrival can be determined at the time of arrival 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, at which time we can compute the time at which this job will depart from the server as described above.

It is assumed that the servers are free 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, and it supports at least 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.
• IsEmptyPQ(S): Determines if the priority queue is empty.

For this simulation 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 = w1l1 + w2l2 + ... + wnln
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.

For additional hints and the format of the log file look at the instructions provided by Dr.Ingargiola in the home page.

Data Structures for the program

// Type definitions //
EventType = (Arrival_C, Arrival_D, Departure_C, Departure_D, Termination)

structure Job
    JobId : Integer
    ArrivalTime : Real
    ArrivalToServer : 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 ServerInfo  //It contains information about both server and queeu //
    First : Event
    Last : Event
    LastUpdate : Real
    Busy : Boolean
    BusyFrom : Real
end ServerInfo

structure InputParameters 
    SEED : Integer
    INITTIME : Integer
    FINTIME : Integer
    SIGMA: Real
    AMIN : Integr
    AMAX : Integer
    S1MIN : Integer
    S1MAX : Integer
    S2MIN : Integer
    S2MAX : Integer
    LOG_FILENAME : Pointer to String
end InputParameters

Var Agenda : PriorityQueueInfo
    SERVER1, SERVER2 : ServerInfo

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 function Random

Function Random(Low, High : Real):Real

that returns a random number between Low and High. Random uses one of the built in random number generators like random() or rand().

Algorithm

procedure DiscreteEventSimulation
var CurrentEvent, NewEvent : Event
//Read SEED, INITTIME, FINTIME, SIGMA, AMIN, AMAX// 
//Read S1MIN, S1MAX, S2MIN, S2MAX, LOGFILE_NAME//

//Initialize Agenda with Arrival and Termination events //
//Initialize SERVER1 and SERVER2 to be empty //


repeat
  CurrentEvent = DeletePQ(Agenda)
  CurrentTime = CurrentEvent.EventTime

  switch(Currentevent.EventKind) //Events//

      case Arrival_C:  
          //Log event in the Log file//
          call CreateNextArrival(Agenda, CurrentTime, AMIN, AMAX)
          if SERVER1.Busy then
              [InsertFQ(SERVER1, CurrentEvent)
              //Update SERVER1 stats//]
          else
              [SERVER1.Busy = TRUE
               //Create a Departure_C event occuring 
               @CurrentTime + Random(S1MIN, S1MAX)
               Let NewEvent be this event//
               InsertPQ(Agenda, NewEvent)
               SERVER1.BusyFrom = CurrentTime] 
          break

      case Arrival_D:  
         //Log event in the Log file//
          call CreateNextArrival(Agenda, CurrentTime, AMIN, AMAX)
          if SERVER2.Busy then
             [InsertFQ(SERVER2, CurrentEvent)
             //Update SERVER2 stats//]
          else
             [SERVER2.Busy = TRUE
             //Create a Departure_D event occuring 
               @CurrentTime + Random(S2MIN, S2MAX)
               Let NewEvent be this event//
             InsertPQ(Agenda, NewEvent)
             SERVER2.BusyFrom = CurrentTime]
          break
      end    
      break

      case Departure_C: 
          //Log event in the Log file//
          //Compute response time for CPU, update stats//

          //Update response stats for C_jobs// 
          if IsEmptyFQ(SERVER1) then                
              SERVER1.Busy = FALSE
          else 
              [CurrentEvent = DeleteFQ(SERVER1)
             //Create a Departure_C event occuring 
               @CurrentTime + Random(S1MIN, S1MAX)
               Let NewEvent be this event//
               InsertPQ(Agenda, NewEvent)
               SERVER1.BusyFrom = CurrentTime]
          //When a job leaves the CPU it may go to the output
            or to disk.//
          if random choice using SIGMA says that the job terminates then
              [Collect statistics for this terminating job]
          else
              [Set EventKind of CurrentEvent to Arrival_D
               Goto the code handling the Arrival_D event]
          break
     
      case Departure_D: 
          //Log event in the Log file//
          //Compute response time for Disk, update stats//

          //Update response stats for D_jobss// 
          if IsEmptyFQ(SERVER2) then                
             SERVER2.Busy = FALSE
          else 
            [CurrentEvent = DeleteFQ(SERVER2)
             //Create a Departure_D event occuring 
               @CurrentTime + Random(S2MIN, S2MAX)
               Let NewEvent be this event//
             InsertPQ(Agenda, NewEvent)
             SERVER2.BusyFrom = currentTime]
             //Now this job will go to the CPU//
             [Set EventKind of CurrentEvent to Arrival_C
              Goto the code handling the Arrival_C event]
           break
      case Termination:
          //Log Event in the Log file//
          //check if CPU and/or Disk are busy
          if so, update busy time for CPU and/or Disk//
          //If the queues of SERVER1 and/or SERVER2 are not empty then
          update SERVER1 and/or SERVER2 queue size stats //
          break

  end //Events//

  until CurrentEvent.EventType = Termination
  //Compute Results//
end DiscreteEventSimulation


procedure CreateNextArrival(Var Agenda : AgendaInfo; CurrentTime, 
                    AMIN, AMAX : Real)
Var NewEvent : Event
  //Create a new event and assign it to Newevent
  The type of NewEvent is Arrival_C and 
  EventTime = CurrentTime + Random(AMIN, AMAX)//
  //Assign a type to the Job//
  InsertPQ(Agenda, NewEvent)
end CreateNextArrival

Mail queries to :