User Guide

Learning about the NetWare Server 13
Server Operating System Administration Guide
103-000148-001
August 30, 2001
Novell Confidential
Manual 99a38 July 17, 2001
The Run Queue
A thread is a stream of control that can execute its instructions independently.
A simpler definition is that a thread is a unit of execution. It is not the code
itself.
HINT: For more information on threads, see Bil Lewis and Daniel J. Berg’s
Threads Primer: A Guide to Multithreaded Programming © Sun Microsystems, Inc.
Their definition of "thread" has been quoted above.
The kernel maintains a data structure called the run queue which contains
threads that are in a state of readiness. In a uniprocessor system, there is only
one run queue from which the processor can pick up threads for execution.
In a multiprocessing system where more than one processor is available, there
is more than one possible solution. The distribution of threads to multiple
processors could be handled by a global run queue (all processors sharing a
single run queue) or by per-processor run queues (known also as local run
queues or distributed run queues). Or by some combination of both.
To compare the two approaches:
 Global run queue. This approach to distributing threads has the
advantage of automatic load balancing. The reason is that no processor
remains idle as long as the run queue has threads ready. However, the
global solution has the drawback of becoming a bottleneck as the number
of processors increases in a system, although under certain scheduling
policies (such as a real time scheduling policy), a global queue might be
necessary.
 Per-processor run queue. This approach has the advantage of being able
to exploit cache affinity—where threads are preferentially scheduled on
the processor on which they last ran. In addition, this approach does not
have the bottleneck problem associated with the global run queue
approach.
With local queues, however, it becomes necessary to ensure that the load
on the processors—the number of threads in the queue—does not become
severely imbalanced. A load balancing mechanism is required to handle
load imbalances so that threads do not pile up at one processor while
another processor remains idle.
The NetWare kernel uses the per-processor run queue. As implemented, a
processor can pick up threads for execution only from its local run queue. This
makes the NetWare scheduler highly scalable compared to an implementation
using a global run queue. To address load imbalance, NetWare uses a
sophisticated load balancing algorithm.