Paper Details

Reference:

Stephen Curran and Michael Stumm,,
Scheduling a Unix workload on small-scale, shared memory multiprocessors",
Computing Systems, 3(4), October, 1990, pp. 551–579.

Download:

PDF

Abstract:

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 obviousextensions 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.

Keywords:

Operating systems, Shared memory multiprocessors, scheduling algorithms

BibTeX:

@article(Curran-CompSys90,
    author = {Stephen Curran and Michael Stumm,},
    title = {Scheduling a Unix workload on small-scale, shared memory multiprocessors},
    volume = {3},
    number = {4},
    month = {October},
    year = {1990},
    pages = {551-579},
    keywords = {Operating systems, Shared memory multiprocessors, scheduling algorithms}
)