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 theoretical comparisons. In this project you will implement and perform simulation experiments to compare the performance of two scheduling strategies for interactive time-sharing systems: Round Robin and Linux OTHER.

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:



• SystemDriver.java
• SystemTimer.java
• Event.java
• EventQueue.java
• Process.java
• ProcessOperation.java
• Kernel.java
• DeviceDescriptor.java
• FCFS.java

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



• processes.dat
• process1.dat
• process2.dat
• devices.dat

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 and process2.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 FCFS class is the only such class that you have. As part of this project, you will create new classes that implement the round robin and Linux OTHER strategies.

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

java SystemDriver processes.dat devices.dat FCFS

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

System Time: 443 Kernel Time: 20 User Time: 350 Idle Time: 73 CPU Utilization: 79.01%

This output indicates that the execution of the processes listed in the processes.dat file required a total of 443 time units. 20 of those time units were spent performing kernel operations, 350 were spent performing user operations and for 73 time units there were no runnable user processes and the Idle process was executed. The final line indicates that the CPU spent 79.01% 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, which is shown below.

# Process name: must be unique among all # processes for any given simulation. PROCESS1 # Process arrival time: 0 # 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 100 IO DISK1 100 CPU 100 IO CDROM 50 CPU 25 EXIT

This process1.dat file describes a process named PROCESS1. Each process in a simulation must have a unique name. PROCESSS1 arrives in the system at time 0. This means that the system call for creating PROCESS1 will occur at time 0. PROCESS1 then goes on to have a CPU burst of 100 time units, followed by an I/O burst on DISK1 of 100 time units, followed by another CPU burst of 100 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. PROCESS1 is an example of a very simple process. You will use several processes such as this to verify that your round robin and Linux OTHER scheduling algorithms are working correctly. In addition, you will want to use many more processes when comparing the performance of your scheduling strategies. Some minimal requirements for the processes that you must use are given at the end of this document.

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 FCFS class as a example. This class implements the Kernel interface and performs a simple First Come First Serve scheduling strategy. You will need to write similar classes to implement the Round Robin and Linux OTHER scheduling strategies.

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:



1. 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 and are indicated by a callID of MAKE_DEVICE. The kernel must respond to these system calls by creating device descriptor and an associated 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.
   
   
2. 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 at the appropriate location in the ready queue. (Note: Where a process is added may depend on the scheduling strategy that is being used!)
   
   
3. 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 descriptor for that process must be moved to the end of the waiting queue associated with the I/O Device. For simplicity, the waiting queues for the I/O devices should 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 scheduling strategy.

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:



1. 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.
   
   
2. 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 the Round Robin and Linux OTHER scheduling algorithms. 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 you will need to compare your scheduling algorithms. 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 Kernel classes that perform Round Robin and Linux OTHER scheduling. When you have implemented and tested these strategies, execute simulations to compare their performance on three types of process mixes: I/O Bound Processes, CPU Bound Processes and a mix of I/O and CPU Bound Processes. Write a brief (~2 pages) summary of the experiments you performed and the results you observed.

The Scheduling Strategies & Test Cases

This section contains a brief description of each of the scheduling strategies that you are to implement and the types of test cases that you should use for your experiments.

The Round Robin Strategy

For the Round Robin strategy when a process is moved to the Running state it should be allowed to execute until it terminates, requests an I/O, its time-slice expires or it is preempted by another process becoming ready to run. New processes and processes completing I/O operations should preempt the currently running process. Use a time-slice of 50 time-units when implementing this strategy.

The Linux OTHER Strategy

The Linux OTHER strategy is described in this set of PowerPoint slides (Scheduling Strategies). When implementing this strategy use a time-slice of 50 time-units and a default priority of 5.

The Test Cases

You should begin by creating sets of processes that test the specific functionality of your scheduling algorithm. For example, for round robin you should be sure to test that the time slicing is working correctly, that processes are preempted when new processes are created and when processes return from I/O. You will also want to be sure that you handle I/O requests properly.

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 will be quite helpful in determining if your scheduling algorithms are working correctly.

After you are sure that your implementations of the Round Robin and Linux OTHER schedulers is correct you will want to create test cases to compare their performance. You will want to have three distinct sets of test processes I/O Bound, CPU Bound and Mixed. Each set of test processes should contain at least 10 processes with a variety of arrival times. Each process should perform at least 5 CPU bursts and 4 I/O operations. You will want to select the durations of the I/O and CPU bursts to produce CPU bound and I/O bound process. For the Mixed case you can select half of the processes from your CPU bound processes and half from your I/O bound processes. Also, your processes should make use of at least two different I/O devices, though not every process needs to use both devices.

Project Write-up

You will turn in a short write-up for this project. The write-up needs to briefly explain the simulations you have performed and summarize your results. In particular you will want to be sure to compare the strategies using the standard performance metrics discussed in the PowerPoint slides (Scheduling Strategies): CPU Utilization, Throughput, Turnaround Time, Wait Time, Waiting Time and Response Time. Note that to calculate some of these metrics you will need to maintain some additional information about each process in its Process Descriptor.