Browse Prior Art Database

Sharing a Single Stack Among Multiple Concurrent Threads

IP.com Disclosure Number: IPCOM000106222D
Original Publication Date: 1993-Oct-01
Included in the Prior Art Database: 2005-Mar-20
Document File: 4 page(s) / 171K

Publishing Venue

IBM

Related People

Hammersley, SD: AUTHOR [+2]

Abstract

Disclosed is a method that allows multiple threads running within an application to share the same physical stack. New STACK and UNSTACK instructions are defined that allow the stack frames for different threads to be interleaved within the same memory block (or stack). Those stack frames belonging to a particular thread are linked together via a set of pointers maintained by the STACK and UNSTACK instructions in order to give each thread the illusion of having its own private stack.

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

Sharing a Single Stack Among Multiple Concurrent Threads

      Disclosed is a method that allows multiple threads running
within an application to share the same physical stack.  New STACK
and UNSTACK instructions are defined that allow the stack frames for
different threads to be interleaved within the same memory block (or
stack).  Those stack frames belonging to a particular thread are
linked together via a set of pointers maintained by the STACK and
UNSTACK instructions in order to give each thread the illusion of
having its own private stack.

      All known current implementations of threads allocate and
deallocate a separate stack area for each thread when the thread
starts and ends.  Providing a way for threads to share a single stack
as though it were logically many stacks could significantly increase
thread performance by decreasing the overhead of initiating and
terminating threads as well as improve paging performance while the
threads are running.

A compiler normally generates code that uses the stack for two
things:

o     allocating space for automatic variables used by a procedure

o     passing arguments to and return values from a called procedure

      Both of these uses can be lumped into a single operation: the
allocation of a STACK FRAME for use by an invocation of a procedure
within a program.  To make a single stack usable by multiple threads,
we require:

o     A single stack pointer that always points to the "top" of the
    physical stack, that is, the area above which all the rest of the
    stack is currently unused.

o     One basing register per executing thread, each of which point
    to the stack frames corresponding to the procedures that are
    currently executing.

o     A STACK operation which is used by a thread when it wishes to
    allocate a stack frame.

o     An UNSTACK operation which is used by a thread when it is
    finished using a stack frame.

      Each stack frame contains the space for the thread's automatic
storage plus an additional STACK ENTRY record which links that stack
entry to the next and previous entries in the physical stack
(regardless of the thread that "owns" them) plus a pointer to the
previous stack entry for that thread.

      When a new stack frame needs to be allocated because a
procedure within a thread is about to call another procedure, the
following logic sequence must be done to implement the STACK
operation:

1.    The new stack frame will  be allocated right after the current
    TOP of stack and will contain space for the frame data as well as
    the frame entry.
2.    The new frame entry fields must be filled in as follows:

    o     The pointer to the previous stack frame for the thread (BL)
        must be set to the thread's current basing register.

    o     The pointer to the previous physical stack frame (BP) must
        be set to the TOP of a stack. ...