Browse Prior Art Database

Circular Stacks

IP.com Disclosure Number: IPCOM000099928D
Original Publication Date: 1990-Mar-01
Included in the Prior Art Database: 2005-Mar-15
Document File: 6 page(s) / 196K

Publishing Venue

IBM

Related People

Manners, DC: AUTHOR [+2]

Abstract

Disclosed is a method for managing a software stack for the purpose of allocating and deallocating abstract elements. Features include: Elements can be allocated and returned to the stack concurrently by different processors. The allocation and deallocation processes execute unlocked using "compare and swap" logic only for short instruction spans. No separate element counts are necessary as the number of available elements in the stack is inherent in the position of the cursors used to manage the stack. Elements can be allocated and deallocated in groups of one or more.

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

Circular Stacks

       Disclosed is a method for managing a software stack for
the purpose of allocating and deallocating abstract elements.
Features include:
      Elements can be allocated and returned to the stack
concurrently by different processors.
      The allocation and deallocation processes execute unlocked
using "compare and swap" logic only for short instruction spans.
      No separate element counts are necessary as the number of
available elements in the stack is inherent in the position of the
cursors used to manage the stack.
      Elements can be allocated and deallocated in groups of one or
more.

      The stack described herein is a first-in, first-out (FIFO)
circular stack consisting of x entries of equal size. When
"non-empty", a stack entry represents a unique element that can be
allocated from the stack.  When "empty", a stack entry does not
represent any allocatable element and is available to receive an
element that is being deallocated (returned).  The number of entries
x is equal to the maximum number of elements to be managed by the
stack plus one. Therefore, there is always at least one empty entry
in the stack.  The stack is considered "full" when there is exactly
one empty entry.

      Management of the stack also includes three pointers as
follows:
1.   Allocation Pointer consisting of an allocation cursor and a
sequence number.

      The allocation cursor is used to indicate the next non-empty
entry in the stack.  The allocation cursor will always point to a
non-empty entry except in the case when the entire stack is empty.
Each time an element is allocated from the stack, it is allocated
from the entry pointed to by the allocation cursor (thus making that
entry empty) and the allocation cursor is advanced in the stack to
the next entry (which will be non-empty unless the entire stack is
now empty).  The sequence number, initially zero, counts the number
of times that the allocation cursor has progressed through the stack
and has returned (wrapped) to its original position.
2.   Deallocation Pointer consisting of a deallocation cursor and a
request count.

      The deallocation cursor is used to indicate the next empty
entry in the stack.  The deallocation cursor will always point to an
empty entry.  When an element is returned (deallocated) to the stack,
it is returned to the entry indicated by the deallocation cursor, in
conjunction with the reserve cursor (see next), and the deallocation
cursor is advanced in the stack to the next entry (which must be
empty).  The request count is a count of the deallocation requests
currently in progress for the stack.  The request count is a count of
the deallocation requests currently in progress for the stack.  The
deallocation cursor is not advanced until all concurrent
deallocations are complete.
3.   Reserve Cursor

      The reserve cursor is used to indicate empty entries that may
be used for deall...