Trace-Driven Modeling and Analysis of CPU Scheduling in a Multiprogramming System
Sherman, et. al
Paper studied a number of different process scheduling strategies.
Method: instead of modifying the scheduler in an OS an re-running some set of jobs, authors captured trace data about jobs running on a real system, and used a simulator to predict how long the entire set of jobs in the trace would have taken. The program that captured the trace data did not cause any observable changes on the function of the running system.
Authors were interesting is solely studying the affect of scheduling algorithms in isolation, without having results be affected by other factors as well. Hence, the trace-driven approach. (So, what were all of these “other factors?” Did all of the other papers test different scheduling algorithms, with different sets of jobs and different times of arrival for each of these jobs?)
Trace data gathered was: CPU burst times, I/O service times
They tested both dynamic predictor algorithms (where they algorithms attempted to predict how much time the next process would run before doing an I/O), and traditional algorithms: round-robin (RR), first-come-first-serve (FCFS), and theoretic “best” and “worst” policies.
Here is what they learned:
Essential factors for a successful scheduling algorithm: preemption, and bounding CPU burst time. (CPU burst time is just the amount of time that a process runs on a CPU without doing an I/O.)
Hardware they experimented on: CDC 6600, UT-1 OS. 128K main memory, 1 CPU (very fast), 10 peripheral processors (PPU; used to I/Os). 1 PPU ran a monitor that scheduled jobs. Software probe that gathered traces was installed on the monitor PPU. System could do 5 user I/Os at a time. Information for 800 jobs was gathered over two data sets.
“Best” preemptive scheduling time: give CPU to process that will run the shortest amount of time before I/O request.
“Worst” preemptive scheduling time: give CPU to process that will hog the CPU the longest before making an I/O.
Main criterion they used were throughput, and cpu utilization.
“Best” gave 12.89% more throughput, and 11.19% more utilization than worst.
Worst utilization was 80.33%.
All results for other scheduling policies fell in between these numbers.
First experiment was to do non-preemptive scheduling (don’t interrupt or switch out a process until it does an I/O). Non-preemptive best gave 3.06% better throughput and 2.43% better utilization than worst non-preemptive. So, authors concluded that preemption was necessary to achieve good scheduling performance.
Round-robin scheduling with small time quanta (8ms) gave throughput increase of 10.08% and cpu utilization increase 8.75% compared to worst preemptive. (Assumed no overhead to switch jobs, but in reality is was 32 us (microseconds), and was negligible. Smaller time quanta (4ms) gave slightly worse results. As time quanta was increased beyond 8ms (more closely approximating FCFS), performance degraded significantly.
Last experiment: preemptive predictive scheduling. Idea: predict length of a process’ next CPU usage time (before it makes another I/O) based on past behavior, and run shortest prediction first. Four different such algorithms were tested (they all predicted correctly “best” process to run about 75% of the time), and all of them only achieved performance gains in the 5-7% range. (Worse than round robin! J)
Exponential smoothing was one example of such a dynamic predictor:
Xhat(n) = alpha*X(n-1) + (1 – alpha)*Xhat(n-1)
Xhat(i) = prediction of ith CPU usage
X(i) = actual time of ith CPU usage
Conclusions: