Starter code

We have begun to write a program that solves this problem. It has been broken down into several modules, described below. You can pick them up online, from files 148glob.tu, 148sim.tu, 148pq.tu, 148gen.tu, and 148perf.tu.

module Globals:

This module defines some types and constants that are used by every other module. It is already written.

module Simulate:

This module contains a procedure called Run that is the heart of the program; it performs one complete simulation. It loops through the time steps, and at each one does the following:

1. Use procedure TaskGenerator.nextTask to generate all information needed about those processes that are to arrive at the current time step, including the priority and CPU time required by each one. Each process is put into the priority queue, using procedure PriorityQueue.Arrive.
2. For each CPU that isn't currently busy, if there is a task waiting in the priority queue take one task out of the queue (using procedure PriorityQueue.Leave) and assign it to that CPU.
3. For each CPU that is currently busy, check whether its process is finished, or has used up its slice of time. If the process is finished, then record the fact that that CPU is now free. If the process has simply used up its slice of CPU time, then put the process back in the priority queue, and assign the CPU a new process from the priority queue (using procedure PriorityQueue.Leave).

After the simulation has been run to completion (i.e., no more processes are being generated because the time has gone past the chosen simulation duration, and there are no more processes running in a CPU or incomplete processes waiting in the queue), procedure Run prints out performance statistics as described earlier. These statistics are accumulated during the run of the simulation, by using subprograms within module PerfData.

Module Simulate may contain some other subprograms (that are called by Run), but they can be hidden from the rest of the program - i.e., they do not have to be exported outside the module.

The structure of this module has already been written, but you will have to fill in the body of procedure Run.

module PriorityQueue:

This module keeps track of the priority queue of processes that are waiting for a CPU. It is adapted from the example in section 7.3 of the text.

This module is already completely written for you.

module TaskGenerator:

This module randomly creates the processes for our simulation, using the exponential and uniform distributions described earlier, and average inter-arrival time and average required CPU time as given in the program's input. Procedure TaskGenerator.nextTask determines at what time the next process will occur, and how much CPU time it will need. Function TaskGenerator.isAnotherTask determines whether or not any further processes will be generated within the time limit of the simulation.

Before TaskGenerator.nextTask or TaskGenerator.isAnotherTask can be used, procedure TaskGenerator.Initialize must be called once to set things up.

This module is already completely written for you.

module PerfData:

This module contains everything to do with collecting performance data: the variables that store the information, and the subprograms that create, update, and print the information. Whenever a process gets a turn in the CPU, we know how long it has waited for that turn, and so we update the statistics at that point.

The structure of this module has already been written, but you will have to fill in the bodies of several procedures.