Portal de Periódicos da CAPES

A Comparison of basic CPU Scheduling Algorithms for Multiprocessor Unix

1990; Volume: 3; Linguagem: Inglês

0895-6340

Stephan Curran, Michael Stumm,

Real-Time Systems Scheduling

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 multiprocessor systems. A third algorithm, Take, is a variation on Initial Placement, where processors are allowed to raid the task queues of the other processors. 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 multiprocessor. They also show that the Take algorithm 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. In this paper, we consider ways to organize and manage the ready tasks in a shared memory multiprocessor. The uniprocessor Unix kernel uses a single priority queue for this purpose: A task is added to the ready queue behind all tasks of higher or equal priority, and the CPU is allocated to the task with the highest priority which is at the head of the queue. For the shared memory multiprocessor case, we consider three basic scheduling algorithms in a simulation study, and compare their behavior and performance in scheduling a Unix workload of tasks. We focus on bus-based multiprocessors that incur extra overhead each time a task is migrated from one processor to another. Many existing multiprocessors belong to this class, including the Encore Multimax [MNO86], the Sequent Symmetry [LT88], and the DEC Firefly [TSS88]. Two of the scheduling algorithms we study are obvious extensions of the method used in the uniprocessor case: Central Queue (CQ): All processors of the multiprocessor share a single ready queue. (This requires that accesses to the queue be synchronized.)