Browse Prior Art Database

On-Demand Enqueueing of Tasks using an Auxiliary Queue

IP.com Disclosure Number: IPCOM000116305D
Original Publication Date: 1995-Aug-01
Included in the Prior Art Database: 2005-Mar-30
Document File: 2 page(s) / 61K

Publishing Venue

IBM

Related People

Armstrong, WJ: AUTHOR [+2]

Abstract

The enqueueing of tasks to an unordered auxiliary queue eliminates the overhead of sorting the task onto the dispatching queue and allows the currently executing task to continue to perform productive work.

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

On-Demand Enqueueing of Tasks using an Auxiliary Queue

      The enqueueing of tasks to an unordered auxiliary queue
eliminates the overhead of sorting the task onto the dispatching
queue and allows the currently executing task to continue to perform
productive work.

      In order to prevent the currently executing task, (in a
multi-tasking system), from incurring the cost of enqueueing another
task to the dispatching queue, the enqueueing operation can be
postponed until it is necessary.  The new task does, however, need to
be saved somewhere until such a time as it will be enqueued.
Furthermore, the process of saving the new task must not require a
significant amount of time, nor cause undue resource contention
resulting in hold-off.  The structure chosen is a single linked list
of new tasks.  This linked list is named the auxiliary queue, and it
is associated with a particular dispatching queue.  The tasks on the
auxiliary queue are waiting to be enqueued onto the dispatching queue
with which it is associated.

      The auxiliary queue is an unsorted list of new tasks.  Thus
there is no overhead incurred trying to sort the task into the proper
location.  When a new task is added to the auxiliary queue, it is
added to the front of the list which is pointed to from the
dispatching queue to which it is associated.  The insertion to the
front of the auxiliary queue is made atomic using the ldarx and stdcx
instructions of the reduced instruction set computer/cycles (RISC)
architecture.  This will minimize any contention for the pointer...