In this lab, you will use a simulation of an operating system scheduler. You will measure the effectiveness and tradeoffs of several scheduling algorithms, including:
cp ~weinman/courses/CSC105/labs/sim* .
cp ~weinman/courses/CSC105/labs/jobdata.txt .
You will be running scheduler simulations on a set of jobs with random arrival times, required processing times (job length), and priorities. The file jobdata.txt that you copied contains this information (each row is the data for one job). Below is a plot illustrating the data. The horizontal axis is an arbitrary time unit (say, milliseconds). Each line represents a job. The left endpoint of the line illustrates the start time and the right endpoint the end time. Thus, the length of the line is the processing time. Lines are organized vertically by arrival time so that it is easy to see overlapping requests. The color corresponds to priority--warmer being higher priority, and cooler being lower priority.
For instance, you should be able to see that at time 1500 there are a lot of short jobs arriving near the same time, and at about time 2250 several longer jobs arrive.
Recall that an operating system using non-preemptive scheduling has some mechanism for choosing jobs that have arrived to be processed but lets each task run to completion before choosing the next to run.
The first come first served (FCFS) scheduling method simply makes the jobs "get in line" as they arrive, and chooses the first job in line to be run. The shortest job next (SJN) scheduling method always selects the job requiring the least amount of running time from among those waiting.
Remember that there is some overhead in choosing the next job to run. That is, the scheduler itself takes time away from jobs that are asking for processing time. In this part, you will experiment with the effectiveness of these algorithms under varying amounts of overhead.
The program simfcfs simulates a FCFS operating system using the jobs in jobdata.txt. In your terminal window, the command to run the simulation has the form:
./simfcfs jobdata.txt overheadwhere overhead is a number representing the amount of time required by the scheduler to choose the next job to run.
For instance, you can run a simulation with an overhead of 1 ms with the command:
./simfcfs jobdata.txt 1
Run the program for an arbitrary value of overhead. (You may wish to know that the average job length in the list of jobs is about 34ms, and the median is 7ms. Presumably, scheduler overhead is much shorter than this.)
./simsjn jobdata.txt overheadRun the program for an arbitrary value of overhead.
A preemptive scheduler runs part of a job for some small portion of time (called the quantum), before reclaiming the processor for another job. Eventually, a partially run job will return to the CPU for processing. The exact ordering depends on the scheduling algorithm.
The round-robin (RR) scheduling algorithm rotates through all jobs waiting. In other words, everyone forms a line, just like FCFS, but the job using the CPU gets kicked out after a set amount of time and goes to the back of the line. Longer jobs will therefore have to get in line more times than shorter jobs.
The program simfcfs also simulates a round-robin operating system scheduler. In your terminal window, the command to run the simulation has the form:
./simfcfs jobdata.txt overhead quantumwhere overhead is a number representing the amount of time required by the scheduler to choose the next job to run, and quantum is the length of time a job runs before being preempted.
Run the program for arbitrary values of overhead and quantum. (You may wish to know that the average job length in the list of jobs is about 34ms, and the median is 7ms. Presumably, scheduler overhead is much shorter than this and the time quantum is longer than the overhead.)
Gather statistics on the number of context switches, system throughput, and average wait time for a range of values for the overhead and time quantum. Try at least: 0, 0.01, 0.02, 0.03, and 0.04 for the overhead and 0.05, 0.1, 0.15, and 0.2 for the quantum. Record these values in an organized fashion in your spreadsheet.
In other words, you should be able to fill in the following table for context switches, throughput, and average wait time:
| Time Quantum | ||||||
|---|---|---|---|---|---|---|
| 0.05 | 0.10 | 0.15 | 0.20 | |||
| Overhead | 0.00 | |||||
| 0.01 | ||||||
| 0.02 | ||||||
| 0.03 | ||||||
| 0.04 | ||||||
A priority scheduling algorithm also uses variation on the preemptive round-robin approach. Every job has a priority associated with it. We want high priority jobs to run sooner than low priority jobs. Therefore, we maintain separate lines for jobs of each priority. A job of a certain priority is selected to run ONLY when no jobs of higher priority are waiting. In addition, to ensure that high priority jobs don't wait very long, the time quantum for low priority jobs is shorter than the time quantum for high priority jobs.
The program simpri simulates a preemptive priority operating system scheduler. In your terminal window, the command to run the simulation has the form:
./simpri jobdata.txt overhead quantumwhere overhead is a number representing the amount of time required by the scheduler to choose the next job to run, and quantum is the length of time the highest priority jobs run before being preempted. Successively lower priorities receive half the time quantum.
Run the program for arbitrary values of overhead and quantum. (You may wish to know that the average job length in the list of jobs is about 34ms, and the median is 7ms. Presumably, scheduler overhead is much shorter than this and the time quantum is longer than the overhead.)
This work is licensed under a
Creative Commons Attribution-Noncommercial-Share Alike 3.0 United
States License
.