A Comparison of Basic CPU
Stephen Curran, Michael Stumm · 1990
In this paper, we present the results of a simulation study comparing three basic algorithms that schedule independent tasks in multiprocessor versions of UNIX. Two of these algorithms, namely Central Queue and Initial Placement, are obvious extensions to the standard uniprocessor scheduling algorithm and are in use in a number of multipro- cessor systems. A third algorithm, Take, is a varia- tion on Initial Placement, where processors are allowed to raid the task queues of the other proces- sors. Our simulation results show the difference between the performance of the three algorithms to be small when scheduling a typical UNIX workload running on a small, bus-based, shared memory mul- tiprocessor. They also show that the Take algo- rithm performs best for those multiprocessors on which tasks incur overhead each time they migrate. In particular, the Take algorithm appears to be more stable than the other two algorithms under extreme conditions.