C. Mccann et al., A DYNAMIC PROCESSOR ALLOCATION POLICY FOR MULTIPROGRAMMED SHARED-MEMORY MULTIPROCESSORS, ACM transactions on computer systems, 11(2), 1993, pp. 146-178
We propose and evaluate empirically the performance of a dynamic proce
ssor-scheduling policy for multiprogrammed shared-memory multiprocesso
rs. The policy is dynamic in that it reallocates processors from one p
arallel job to another based on the currently realized parallelism of
those jobs. The policy is suitable for implementation in production sy
stems in that: It interacts well with very efficient user-level thread
packages, leaving to them many low-level thread operations that do no
t require kernel intervention. It deals with thread blocking due to us
er I/O and page faults. It ensures fairness in delivering resources to
jobs. Its performance, measured in terms of average job response time
, is superior to that of previously proposed schedulers, including tho
se implemented in existing systems. It provides good performance to ve
ry short, sequential (e.g., interactive) requests. We have evaluated o
ur scheduler and compared it to alternatives using a set of prototype
implementations running on a Sequent Symmetry multiprocessor. Using a
number of parallel applications with distinct qualitative behaviors, w
e have both evaluated the policies according to the major criterion of
overall performance and examined a number of more general policy issu
es, including the advantage of ''space sharing'' over ''time sharing''
the processors of a multiprocessor, and the importance of cooperation
between the kernel and the application in reallocating processors bet
ween jobs. We have also compared the policies according to other crite
ria important in real implementations, in particular, fairness and res
ponse time to short, sequential requests. We conclude that a combinati
on of performance and implementation considerations makes a compelling
case for our dynamic scheduling policy.