Trace-driven modeling and analysis of CPU scheduling in a multiprogramming system Sherman, Baskett, Browne 1972 Summary by Ed Swierk Claims to be the first study of CPU scheduling algorithms where each is considered in isolation but uses real data (trace-based modeling). Previous studies were done by changing algorithms on actual OSes, which involved altering other aspects of the OS, thus making it difficult to isolate the effectiveness of the algorithm. The study uses traces of CPU and IO activity gathered from an actual system. The system is limited to 5 concurrent processes and 5 simultaneous IO operations. Goal: minimize the total time it takes to execute a trace (== maximize the total throughput). Assumptions: the "best" way to schedule the CPU is to give the CPU to the process that will compute for the shortest period of time before issuing an IO request; the "worst" way is to select a process that will compute the longest; performance of actual scheduling algorithms lie somewhere between the performance of these theoretical best and worst methods. This is true whether scheduling is preemptive or nonpreemptive. (First-come-first-served can be though of as round-robin with a time quantum of infinity.) Hypothesis: when processes do not strictly follow a pattern of being CPU bound or IO bound (i.e. "autocorrelation coefficients" are small), a round-robin scheduling algorithm yields an improvement over first-come-first-served. Results: Assumptions about best and worst scheduling algorithms are valid. Throughput increases are highly correlated with increases in CPU efficiency (== the percentage of time the CPU spends busy) Round-robin is better than first-come-first-served. Predictive algorithms, which try to select the job that will use the CPU for the shortest period of time before issuing an IO request, also give better results than first-come-first-served. But since the prediction accuracy is fairly poor, these algorithms work well only when coupled with a limit on the amount of time a job can spend using the CPU before being preempted. Conclusion: Round-robin performs better than expected; trace-based modeling is good.