Browse Prior Art Database

Collated Keyed Queue

IP.com Disclosure Number: IPCOM000108758D
Original Publication Date: 1992-Jun-01
Included in the Prior Art Database: 2005-Mar-22
Document File: 3 page(s) / 108K

Publishing Venue

IBM

Related People

Knipfer, DL: AUTHOR [+5]

Abstract

A method is disclosed for dispatching only the processes waiting on a keyed message queue that will be satisfied by an arriving message. Processes that will not be satisfied by an arriving message remain on the wait queue. This reduces the overhead associated with maintaining keyed message queues since processes that cannot take advantage of an arriving message are not dispatched only to be placed back on the wait queue when they discover a message is not the one for which they are waiting.

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

Collated Keyed Queue

       A method is disclosed for dispatching only the processes
waiting on a keyed message queue that will be satisfied by an
arriving message.  Processes that will not be satisfied by an
arriving message remain on the wait queue.  This reduces the overhead
associated with maintaining keyed message queues since processes that
cannot take advantage of an arriving message are not dispatched only
to be placed back on the wait queue when they discover a message is
not the one for which they are waiting.

      A new queue called a Collated Keyed Queue is described. The
interface to the queue is defined as follows:
1. All messages placed on the queue must be placed in ascending key
sequence.
2. Permitted receive operations on the queue include Receive Equal
(=), Receive Less Than (<), Receive Greater Than (>), Receive Not
Less Than (>=) and Receive Not Greater Than (<=).  If no key
satisfies the specified receive, the requesting process will wait
until a message arrives that does satisfy the request. If multiple
processes are satisfied by a single message, the highest priority
process among them will receive the message.

      Keys are three bytes, but only one byte of the key is saved for
each waiting process.  Several messages are enqueued to the queue, in
key order.  The header points to the last message to facilitate fast
enqueuing of keys greater than all those present.  Since the last
message points to the first, operations at the head of the queue are
fast as well.

      Waiting processes are arranged in two groups, depending on the
relational operator used to receive a key.  The "Req:" field
indicates the original receive request, but only the "Saved:"
information is actually recorded in the chain elements.  The "=",
">", and ">"= requests are queued first, in ascending key order.  A
skip link is used to chain the first of this group to the last, for
fast addition of a requester with a higher key than all in the group
(a common occurrence).

      When a message is sent to the queue, this first group need only
be e...