Original Publication Date: 1983-Jul-01
Included in the Prior Art Database: 2005-Feb-07
AbstractFewer instructions and storage references are permitted, without an increase in queue head and queued element storage requirements, when circular queueing is employed.
Fewer instructions and storage references are permitted, without an increase in queue head and queued element storage requirements, when circular queueing is employed.
With traditional FIFO (first-in, first-out) queueing, a queue head consists of a single word which contains the address of the first element in the queue, or zero if the queue is empty. Each element in the queue contains a single (chain) word which contains the address of the next element in the queue. The chain word of the last element in the queue is zero.
This approach facilitates rapid removal of elements from the queue. Very simply, the contents of the queue head are obtained and tested for zero to detect an empty queue. If there is no empty queue, the chain address in the first element is moved to the queue head. However, disadvantages exist. For example, it can be very expensive to add a new element to the end of the queue. First, the entire queue must be scanned until the end is found. Then, the address of the element to be added is stored in the chain word of the previous last element. As the number of elements in the queue increases, more and more processing cycles are required. Also, if a demand paging system is in use, there is great potential for extensive page references each time the queue is scanned.
An alternate approach involves the use of two queue head words.
The first contains the address of the first element in the queue, and the second contains the address of the last element in the queue. Eliminated with this approach is the requ...