Process Scheduling Simulation

Process Scheduling Simulation

Introduction

Simulation is a powerful tool that can be employed when designing and selecting scheduling strategies for an operating system. Such simulations allow the consideration of far more details and far more processes than manual or theoretical comparisons. In this project you will implement and test a simulation for round robin process scheduling.

Simulation Development

You will be implementing your scheduling strategies using the simulation framework provided below. This simulation framework accepts as input a specification of a collection of processes. The framework then simulates the system calls and interrupts that an OS kernel would receive when executing the specified processes. The following sub-sections provide an overview of the simulation framework and outline what you must do to complete this project.

Downloading the Simulator

In order to execute the simulator you will need to download each of the following Java files to a directory:

You should also download the following data files into the same directory as the simulator code:

Compiling the Simulator

To compile the simulator use the command:

javac *.java

Running the Simulator

The general form of the command line to run the simulator is:

java SystemDriver <processes file> <device file> <scheduler type>

The command line parameters have the following effects:

<processes file>: Filename of a file containing a list of the files that describe the processes to be executed by the simulator. For example, the processes.dat that you downloaded earlier contains two (non-comment) lines indicating that the processes in the files process1.dat, process2.dat and process3.dat should be executed by the simulator. Lines beginning with # are comments. All comments and all blank lines are ignored by the simulator. The format for the contents of process files will be described below.
<device file>: Filename of a file containing a list of the devices that the system supports. For example the file devices.dat that you downloaded earlier contains lines indicating three I/O devices (two disks and a cd-rom). Each line in this file specifies one device. Such a line must begin with I/O and must conclude with the name of the device. Device names may not contain spaces.
<scheduler type>: The type of scheduler to use when scheduling the processes. The value used here must be the name of a class that implements the Kernel interface. Currently, the FCFSnoIO class is the only such class that you have. As part of this project, you will create a new class that implements round robin scheduling.

To run the simulator with the data files downloaded above use the command line:

java SystemDriver processes.dat devices.dat FCFSnoIO

If you successfully downloaded and compiled all of the above files, the output of the program will appear as:

System Time: 64 Kernel Time: 12 User Time: 45 Idle Time: 7 CPU Utilization: 70.31%

This output indicates that the execution of the processes listed in the processes.dat file required a total of 64 time units. 12 of those time units were spent performing kernel operations (i.e. scheduling overhead), 45 were spent performing user operations and for 7 time units there were no runnable user processes and the Idle process was executed. The final line indicates that the CPU spent 70.31% of its time executing user code (i.e. not kernel code and not the idle process).

The Process Data Files

Each file listed in the <processes file> indicated by the command line parameter describes a single process to be executed during the simulation. The syntax of these process data files is documented in the process1.dat file. An example of such a file is shown below.

# Process name: must be unique among all # processes for any given simulation. PROCESS5 # Process arrival time: 15 # Process profile. This must begin with # START and end with EXIT. Also every process # must start and end with a CPU burst. That is, # the first line after START and the last line # before EXIT must be CPU bursts. In between # the lines may be: # CPU <time> # IO <device> <time> START CPU 25 IO DISK1 100 CPU 15 IO CDROM 50 CPU 25 EXIT

The above process file describes a process named PROCESS5. Each process in a simulation must have a unique name. PROCESSS5 arrives in the system at time 15. This means that the system call for creating PROCESS5 will occur at time 15. PROCESS5 then goes on to have a CPU burst of 25 time units, followed by an I/O burst on DISK1 of 100 time units, followed by another CPU burst of 15 time units. The process then has a 50 time unit I/O burst using the CDROM and a final CPU burst of 25 time units. PROCESS5 is an example of a very simple process. You will need to carefully create a variety of user processes such as this in order to verify that your round robin scheduling algorithm is working correctly.

The Kernel Interface

The file Kernel.java defines the interface that the system uses to interact with your scheduling strategies. Thus, all of the programming that you do for this project will take place in classes that implement the Kernel interface. You should study the FCFSnoIO class as a example. This class implements the Kernel interface and performs a simple First Come First Serve scheduling strategy with the assumption that none of the processes make I/O requests. You will need to write a similar class in order to implement round robin scheduling.

The methods defined in the Kernel interface are designed to emulate the way real processes interact with an operating system. The SystemDriver and the other classes provided above read the device and process data files and then make calls to the Kernel methods to simulate the system calls and interrupts that would occur when executing the processes. In addition to the methods defined in the Kernel interface, your scheduler code must contain a no-argument constructor. The purpose and use of each of the four methods defined by the Kernel interface is discussed below:

public void systemCall(int callID, String param, SystemTimer timer)

A Kernel's systemCall method will be invoked when the services of the kernel are required. More specifically the systemCall method is invoked in three circumstances:

At startup the SystemDriver invokes the systemCall method once for each device listed in the <devices file>. These system calls simulate the initialization of the system as would occur during the bootstrap process. System calls related to initializing new devices are indicated by a callID of MAKE_DEVICE. The kernel must respond to these system calls by creating a waiting queue for the device. The param will contain the name of the device as it was indicated in the <devices file>. The timer parameter will contain a reference to a SystemTimer object which provides access to timing information. The SystemTimer class is described in more detail below.
When a new process arrives in the system (as indicated by the arrival time in its process data file) the systemCall method will be invoked with callID of START_PROCESS. The param will contain the name of the new process as was indicated in the process' data file. The kernel must respond to this system call by creating a new process descriptor for the process and adding it to the ready queue.
Each time the currently executing process generates a system call (e.g. I/O request or exit) the systemCall method will be invoked with the appropriate callID and param. When a process makes an I/O request (callID will be IO_REQUEST) the process control block for that process must be moved to the end of the waiting queue associated with the I/O Device. For simplicity, you should assume that all devices process requests in FIFO order. Thus, the waiting queues for the I/O devices can be FIFO queues. When a process exits (i.e callID is TERMINATE_PROCESS) it should be removed from the running state and should no longer be considered by the scheduler.

The following table summarizes all of the callID and param values that may be passed to the systemCall method:

callID: param: ---------------------------------- MAKE_DEVICE Device ID START_PROCESS Process Name IO_REQUEST Device ID TERMINATE_PROCESS null

public void interrupt(String deviceId, SystemTimer timer)

The kernel's interrupt method is invoked under two conditions:

Each time one of the I/O devices in the system completes an I/O operation the interrupt method is invoked with the deviceId parameter set to the name of the device that generated the interrupt. The kernel must remove the process descriptor from the head of the device's waiting queue and move it to the appropriate location in the ready queue.
The interrupt method can be invoked by the system timer device. When invoked by the system timer the deviceID will be set to the string TIMER. The kernel will need to use the system timer to generate the interrupts necessary to implement the time-slicing for round robin scheduling. The method by which timer interrupts are set is described below when the details of the SystemTimer class are presented.

public String running(SystemTimer timer)

The running method must return the name of the process that is currently in the running state. If no process is currently ready to run this method must return the string "Idle" indicating that the idle process is running. This information is used by the simulator to keep track of how much CPU time has been allocated to each process.

public void terminate(SystemTimer timer)

The terminate method is called automatically when all of the processes in the simulation have completed. You should use the terminate method to calculate and report the statistics necessary for comparing your scheduling algorithms.

The SystemTimer Class

Each time a method in a Kernel class is called it is passed a reference to an object of type SystemTimer. This object contains a number of public methods that will be useful for performing scheduling and for computing the metrics that are useful for evaluating schedulers. These methods are:

getSystemTime(): This method returns the number of time units that have elapsed since the simulation began.
getKernelTime(): This method returns the number of time units that the CPU has been dedicated to kernel operations such as processing system calls and handling interrupts. For the purposes of this simulation, all system calls and interrupts are assumed to take two time units each.
getUserTime(): This method returns the number of time units that the CPU has been dedicated to processing user operations.
getIdleTime(): This method returns the number of time units that the CPU has been idle.
scheduleTimerInterrupt(int delay): This method sets the system timer to generate an interrupt delay time units in the future.
cancelTimerInterrupt(): This method cancels a pending system timer interrupt if there is one. If there is not a pending timer interrupt then this method does nothing.

The Assignment

Implement a Kernel class that performs round robin scheduling using the following policies:

Time-slices should be 50 time-units in length.
When a new process arrives it should preempt the currently running process. That is, the new process should immediately receive a time slice. The process that was preempted should then run in the time slice immediately following the new process.
Any process that becomes unblocked should preempt the currently running process. The process that was preempted should then run in the time slice immediately following the process that became unblocked.

Your simulation must also compute and display the following performance metrics when the simulation terminates: CPU Utilization, Throughput, Turnaround Time, Wait Time, Waiting Time and Response Time. For each of these metrics, use the definition given in the lecture slides, not the textbook.

Helpful Hint

To help with testing and debugging your scheduling strategies the simulator is capable of generating additional debugging output. To turn on this additional output set the debug variable to true in the SystemTimer class. When debug is set to true the simulator will display messages indicating what is happening at each time step of the simulation. These messages can be quite helpful in determining if your scheduling algorithm is working correctly.

Turning in Your Solution

Submit your solution by giving me your class that implements round robin scheduling, and your new version of ProcessControlBlock.java (if you changed it). Please submit both a hard copy and an electronic copy by e-mail.

Acknowledgment: this content is essentially identical to that developed by Professor Grant Braught for the Spring 2006 Operating Systems course, and I'm grateful for his permission to use it.