Browse Prior Art Database

Dispatcher Queue to Provide Processor Affinity in a Multiprocessor

IP.com Disclosure Number: IPCOM000111232D
Original Publication Date: 1994-Feb-01
Included in the Prior Art Database: 2005-Mar-26
Document File: 4 page(s) / 109K

Publishing Venue

IBM

Related People

Devarakonda, M: AUTHOR

Abstract

Disclosed is an efficient scheme for dispatcher queue management and process selection to implement affinity-based scheduling in a multiprocessor, where the term affinity-based scheduling refers to running a process on a processor that ran this process previously so that the contents of the processor cache can be re-used for high performance. Currently, most systems do not employ affinity-based scheduling and where it is employed per-processor queues are used. The scheme described here consists of a low cost mechanism for finding relevant processes quickly and a simple selection criteria for affinity-based scheduling.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 52% of the total text.

Dispatcher Queue to Provide Processor Affinity in a Multiprocessor

      Disclosed is an efficient scheme for dispatcher queue
management and process selection to implement affinity-based
scheduling in a multiprocessor, where the term affinity-based
scheduling refers to running a process on a processor that ran this
process previously so that the contents of the processor cache can be
re-used for high performance.  Currently, most systems do not employ
affinity-based scheduling and where it is employed per-processor
queues are used.  The scheme described here consists of a low cost
mechanism for finding relevant processes quickly and a simple
selection criteria for affinity-based scheduling.

      The disclosed scheme is described here as an extension to the
UNIX* dispatcher scheme, so this paragraph briefly reviews the UNIX
scheme.  The UNIX dispatcher scheme, for example as is used in 4.3
BSD Unix, consists of 32 run queues (Figure).  Every runnable process
is assigned a scheduling priority which determines its placement on
the run queues.  Priorities can range from 0 through 127, the
smallest value being the best.  Processes having priorities 0 through
3 are placed in run queue 0, 4 through 7 are placed in run queue 1,
and so on.  Each run queue is a linked list.  Dispatcher picks the
process at the front of the lowest-numbered run queue.  Processes are
always put at the back of a run queue and dispatched from the front,
thus using the round robin scheme.  Process priorities are updated
periodically based on their recent resource usage.  Priority of a
process is lowered (assigned a higher number) if the process received
CPU time recently or raised (assigned a lower number) if the process
has been waiting.

      When combined with such dynamic-priority based scheduling,
affinity can not be the only factor --- sometimes a process having
the highest priority overall may have to be run instead to avoid
starvation.  Dispatcher queue management in this case is a problem
since a processor needs to determine quickly the overall
highest-priority process and the highest-priority affinity process,
and choose between them.  Also, periodic priority re-calculation and
resulting re-arrangement of the dispatcher queue exacerbates the
problem.

      The disclosed scheme maintains an extra set of run queues for
each processor, which are called affinity run queues, and a process
is chosen either from an affinity run queue or from a main run queue
b...