| Due: | Friday, February 18, 2000 at the start of class |
|---|---|
| Purpose: | To give you experience with the behavior of CPU scheduling algorithms |
For this project, you will be modifying and experimenting with the CPU scheduler of a simulated operating system. You will run various versions of your scheduler under different simulated workloads to see how well different algorithms handle the tradeoffs between scheduler goals such as maximizing throughput, minimizing waiting time, and fairness.
Your scheduler will consist of a collection of routines that are called by a main program that runs the actual simulation. Your routines will be responsible for keeping track of the state of a set of processes (simulated by the main program), and for choosing which member of the set of processes is to be allowed to use the CPU at any given time.
You will compile a source file that contains your routines, and will then link it with the simulator, which will be supplied in object form. To get started on the project, you should copy the following files to your directory.
Download Instructions: You can download these files Netscape by holding down the SHIFT key and left-clicking on the appropriate link. You can also find these files in the directory /usr/gc/cs322/p1 on the SGI cluster.
irix6.5/p1test.o for IRIX 6.5, linux/i386/p1test.o for Linux 2.2 (Intel) or linux/ppc/p1test.o for Linux 2.2 (PPC). This is the object file for the simulator main program. You need only one of these.
proj1.h. This is the header file that defines the interface between your scheduler and the simulator.
fcfs.c or fcfs.cc. A version of the scheduler that uses the "first come first served" algorithm. This file can be compiled and linked with the simulator and run as it stands, though its performance will not generally be good.
(Get the .c version if you choose to do the project in C; the .cc version if you choose to do the project in C++)
You should study the header file proj1.h carefully (especially the comments) along with the FCFS file you copied to understand the interface between the scheduler and the rest of the system.
When you run a copy of the program, the simulator will prompt you for the following simulation variables:
Enter a file name, or press return for no log file. Warning: the log is voluminous, so only enable logging for short runs!
Enter an integer between 1 and 10,000
Enter an integer between 0 and 100. In addition to the number of processes you specify, the simulator will also create a "system initialization" process that will run at system startup, plus a "null process" that can be run if no other process is runnable.
Enter a number between 0 and the number you answered for the previous question. (This question will be omitted if previous answer was 0.)
Enter a number between 0 and the number of processes you answered initially minus the number of io-bound processes you specified. (This question will be omitted if there are 0 processes or all are specified as io-bound.)
At this point, the simulator will indicate that the number of remaining processes (if any) will exhibit mixed behavior.
Enter an integer between 1 and 10,000
Enter 0 to ignore this value for the FCFS algorithm. For time-slicing algorithms this is where you enter the number of ticks in a time slice. It must be a multiple of 10.
The simulator will then create a set of simulated processes as specified, and will run the simulation for the specified amount of simulated time, logging various significant events to the log file (if there is one) as they occur. As individual processes terminate, they will be replaced by new processes to keep the system load at the specified level. Upon termination of the simulation, the simulator will terminate the remaining processes and report the following summary statistics to your screen:
Total throughput (number of processes that were able to run to completion)
Overall performance score, computed as discussed below
The simulator will internally measure (simulated) time in "clock ticks" of 0.0001 second. The value returned by the simulator function CurrentTime() will be an integer representing the number of ticks since simulation startup. (For example, a return value of 10,000 will mean that the simulation has been running for one simulated second.)
The timer provided by the simulator will generate calls to the scheduler TimerInterrupt() at intervals of 0.001 second - i.e. every 10 "ticks".
All input parameters to the simulator and results reported by the simulator will be in seconds.
Although the simulated processes will not actually perform any ordinary computation or IO activity, they will behave as if they are doing so. The simulator will assign randomly-chosen lengths to each cpu burst and io burst for each process. The means used in generating these values are as follows:
| Burst Type | Process bound by | Time |
|---|---|---|
| CPU | IO | 0.01 second (100 ticks) |
| CPU | 0.25 second (2500 ticks) | |
| both IO and CPU | 70% of the time same as IO-bound 30% of the time same as CPU-bound |
|
| IO | (any kind of process) | 0.05 second (500 ticks) |
The average lifetime of a process is a simulation parameter, and will be used as the mean for generating random lifetimes for each process as it is created. A process will terminate when it has accumulated this amount of time in cpu activity + io activity, or when the end of the simulation time comes - whichever occurs first.
Each context switch will result in the passage of 0.001 seconds (10 ticks) of CPU time during which no useful computation occurs.
At the end of each run, the simulator will calculate a performance score, based on credits and penalties assigned for each process.
Each process that terminates will earn a credit equal to the sum of the lengths of its cpu and io bursts. (I.e. its actual lifetime). A process that has not completed by shutdown time will receive credit for work actually completed as of that time.
A process whose total time spent waiting for the cpu exceeds 1.5 x (total number of processes) x (actual cpu time used) will be penalized. (This is a process whose time spent waiting for the cpu is at least 50% greater than what would be the case if all processes were treated equally in terms of the ratio of cpu wait time to cpu time used.) The penalty will be calculated as (wait-time / number-of-processes) - 1.5 x (cpu time). This penalty applies whether or not the process has completed.
The overall performance score will be (sum of credits - sum of penalties) divided by length of the simulation. Note that, on a system with only one process, the performance score should be close to 1, since it will either be doing computation or io continually throughout the simulation. (The score will be slightly less than 1 due to time lost to context switches). An efficient system with more than one process should earn a score higher than 1, since io operations can overlap each other and computation. The upper limit on the score will be the number of processes - which would occur if all processes were busy all the time. Naturally, this limit will not be attainable.
Compile the FCFS version of the scheduler as supplied, link it with the simulator, and run the resulting program. Use the following commands to compile and link the program:
if using C: if using C++: $ cc -o fcfs fcfs.c p1test.o -lm $ CC -o fcfs fcfs.cc p1test.o -lm
Specify the following simulation parameters when you run the program:
Make note of the information reported by the simulator.
Note: If you so choose, you can pass all parameters to the program at one time from the command line. So, to run the program with the above parameters you would use the command line:
fcfs /dev/null 25 10 7 3 1 0
Note that the name of an output file must be specified. If you don't want to save the logging information use the filename /dev/null.
Copy fcfs.c (or fcfs.cc) into a new file called rr.c (or rr.cc). Modify this scheduler to use a "round robin" algorithm, with a time quantum to be entered by the user when the program is run. (Because the granularity of the timer is 10 ticks, the quantum will have to be a multiple of 10 ticks.)
This will entail making the TimerInterrupt() routine force a context switch if the current process has received at least a full quantum of time since it was given the cpu. (However, if there are no other ready processes other than the null process, then let the current process keep running. The simulator will consider it an error for the null process to be running when some other process is ready.)
Run this program with the same parameters as above, and with the following quantum values:
10, 20, 50, 100, 200, 500, 1000, 2500
The simulations with small quanta may run for a while, so be patient! Record the reported information for each run. If you want to automate the testing with different time quanta you may want to read about how to use bash programming and Unix pipes.
Turn in a printout of rr.c (or rr.cc) with the lines changed or added from fcfs.c (or fcfs.cc) highlighted. (You can use the Unix diff command to easily find these lines.) On a separate sheet, report the parameter and quantum values you observed. Compare and discuss the information reported by the round-robin scheduling program with the data reported by the first-come first-served program. Note well: this discussion is very important!
Make sure that there is an executable copy in your home directory under the name rr. You can do this with the command
cp rr ~/rr
Create a new version of the scheduler called best.c (or best.cc) which achieves the best possible performance for the situation specified. (This will require giving some sort of priority to io-bound processes. Since IO goes on in parallel with CPU activity, you can be earning multiple points at every tick.)
Note that you may want to experiment with a scheduler that has one or more parameters that can be entered at run-time. However, the version your turn in must be "hard-wired" with the set of parameters that you find give the best results.
Test your scheduler using the following sets of simulation parameters, to be sure it works correctly and exhibits reasonable performance in all cases.
| Simulation Time | Number of Processes | IO bound Processes | CPU bound Processes | Average lifetime |
|---|---|---|---|---|
| 25 seconds | 0 | 0 | 0 | 1 second |
| 25 seconds | 1 | 1 | 0 | 1 second |
| 25 seconds | 1 | 0 | 1 | 1 second |
| 25 seconds | 1 | 0 | 0 | 1 second |
| 25 seconds | 10 | 7 | 3 | 1 second |
| 100 seconds | 10 | 4 | 3 | 1 second |
Turn in a copy of best.c (or best.cc), and also leave an executable copy in your home directory under the name best. The performance of your simulation on one or more test runs of the professor's choosing will be compared to scores earned by other students on a competitive basis to assign part of the final grade. This test will be administered by the professor.