User-Level Native Thread Primitives (GThread) Library White Paper (G06.26+)

User-Level Native Thread Primitives (GThread Library) 03/31/2005
Hewlett-Packard Company--540065-001 Page 4 of 46
Typically, each thread has a stack at a distinct, static address within the virtual memory space of the
process. An alternative approach called "stack swapping" employs only a single stack area timeshared by
all active threads; the frame images of waiting stacks are swapped to separate holding spaces. Static
stacks have the advantage of much faster context switches, but they are impractical when the architecture
restricts total stack space. An advantage of stack swapping is that all threads share the special attributes
of one stack area, including its stack overflow detection mechanism. Stack swapping may also require
less total memory, because the swap area needs to hold only the frames of a waiting thread; an active
thread might call additional procedures that (without preemption) will exit before the thread waits.
When an individual thread stack becomes too big, it can be allocated a larger swap area, but moving a
static stack to a larger area is impractical. A key disadvantage of stack swapping is that local variables
on the thread stack cannot be passed by reference to other threads or used as I/O or message buffers in
operations that may proceed while the thread waits.
The active part of a stack component extends from the "stack origin" to the "stack tip." The origin is
anchored; the tip moves as procedures are entered and exited, causing the stack to grow and shrink.
The "stack root" is the set of activation records (stack frames) for procedures that were invoked before
multithreading was initialized and do not exit until after the last thread has terminated. These activation
records, along with the process globals and heap, remain visible to all threads in both "static" and
"swapped" models.
Another distinction in multithreading models is the relationship of the initial context of the process to all
other threads: it may be "peer" or "master." A peer protocol is symmetric; context can switch from any
thread directly to any other; the "Main" (initial) thread differs from others only in that the program does
not initiate or terminate it. In a master protocol, the original process context is considered "unthreaded"
and used when no thread is active; context switches occur only from the master to some thread and back.
The master protocol incurs more context switches than with peers, but in a stack-swapping model there
are no "Main-thread" activation records to swap. Individual thread stacks can be somewhat smaller with
this protocol because the "dispatch" function (choosing the next thread or waiting for something to do)
occurs only in the unthreaded master state.
1.3. Thread Model Variations
The simplest thread model utilizes static stacks: the thread context to be saved includes only the values of
certain processor registers. For swapped threads, the context also includes the procedure activation
records (stack frames) on the stack.
For a swapping model, part of the process stack is time-shared by all the threads. (These diagrams show
a single stack component growing from left to right.) With the peer protocol, the swapped portion of each
thread originates at the same point. The location of the swap origin is not critical; it is typically placed
just beyond the stack root, minimizing the amount of stack-frame data to be swapped for the main thread.
Diagram 1
|--- stack root ---|--- main thread ---|
|--- thread 1 ---|
|--- thread 2 ---------|