Browse Prior Art Database

Method for Adding and Removing Elements From Aged Priority Queues

IP.com Disclosure Number: IPCOM000101753D
Original Publication Date: 1990-Aug-01
Included in the Prior Art Database: 2005-Mar-16
Document File: 7 page(s) / 291K

Publishing Venue

IBM

Related People

Gayek, PW: AUTHOR

Abstract

Real-time software systems frequently have to process incoming messages that have been assigned different priorities. At any given time, a number of messages have arrived but have not yet been processed. The system uses the messages' priorities to choose which message to process next; higher priority messages are processed first.

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

Method for Adding and Removing Elements From Aged Priority Queues

       Real-time software systems frequently have to process
incoming messages that have been assigned different priorities.  At
any given time, a number of messages have arrived but have not yet
been processed.  The system uses the messages' priorities to choose
which message to process next; higher priority messages are processed
first.

      If the system always processes the highest priority message
that is waiting and high-priority messages arrive constantly,
low-priority messages may never be processed. For most applications
this situation is not acceptable. Long wait times for low-priority
messages are expected, but the system must guarantee that all
messages will eventually be processed.

      A specific instance of this problem faced on this project was
as follows:
*    Messages with four different priority levels arrived
asynchronously.
*    The system's function was to transmit these messages serially on
a particular link to another node in the network.
*    The choice of which message(s) to send next on the link had to
be based on priority, but without leaving any message waiting
indefinitely.
*    Some messages had to be grouped with other messages at the same
priority; once sending the first message in that group began, all the
messages in that group had to be sent before sending a message
outside the group.
*    The number of messages to be sent at one time could vary from 1
to 7.
*    The software to queue up and later retrieve these messages had
to be extremely fast.

      High-Level Description of Solution For storing and retrieving
messages in the system, each of the four transmission priorities has
a queue.  One process places the arriving messages at the end of the
appropriate queues.  A separate process runs when the transmission
link is available.  This "remove process" takes messages from the
queues and sends them on the link.

      Initially, the remove process takes messages from the highest
priority non-empty queue.  The remove process keeps count of the
number of messages that have been removed from each queue.  As soon
as a certain number of messages have been removed from a queue, the
remove process must take one message from the next lower priority
non-empty queue.  The process may then resume taking messages from
the higher priority queue, with that queue's count of removed
messages reset to zero.  In time, the maximum permissible number of
messages will have been removed from the lower priority queue.  The
remove process must then take one message from an even lower priority
queue before returning to the highest priority queue.  Because this
pattern repeats itself for each queue, the algorithm guarantees that
even the lowest priority queue will be serviced.

      The algorithm also includes logic for the requirement of being
able to send uninterrupted groups of messages. When the remove...