Browse Prior Art Database

Method and Apparatus for a Lockless FIFO Queue with m Queuers and n Dequeuers

IP.com Disclosure Number: IPCOM000034886D
Original Publication Date: 2005-Jan-19
Included in the Prior Art Database: 2005-Jan-19
Document File: 2 page(s) / 60K

Publishing Venue

IBM

Abstract

This invention provides a simplified mechanism to manipulate a strict FIFO queue that eliminates problems associated with the prior art. This particular implementation eliminates the serialization bottlenecks, the additional complicated recovery logic and excess storage consumption that is associated with the prior art.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 53% of the total text.

Page 1 of 2

Method and Apparatus for a Lockless FIFO Queue with m Queuers and n Dequeuers

This invention achieves its advantage by taking advantage of the PLO hardware instruction to serialize the addition and removal of elements from a FIFO queue without requiring a lock that blocks other callers or that requires a list of free elements that can build up if the queue is heavily used. The queue is a double headed and single threaded queue. The header has a pointer to the top element on the queue and a pointer to the last element on the queue. Each of the elements in the queue points to the next element on the queue. Callers that dequeue from the queue take elements from the front of the queue and set the element's queue status atomically. Callers that enqueue to the queue add elements to the end of the queue and set the element's queue status atomically. The queue has a PLO lock token that serializes concurrent PLO operations using that lock token against each other and also has a PLO sequence number associated with it that is incremented for each operation that is performed against the queue. The sequence number is used as the main serialization point to serialize the operations done against the queue. The following describes the algorithm in detail:

Enqueue Algorithm:

A PLO operation involving a compare and swap on the PLO sequence number field

is done to obtain the current sequence number which is then used to serialize the current enqueue operation to be performed against any other update to the queue. The following logic is performed until a success is received from the PLO operation:

If the queue is empty a PLO operation involving a Compare and Swap on the PLO sequence number and 3 distinct store operations is performed. The three store operations attempt to update of the top element pointer, end element pointer and the new element's status word using the PLO sequence number as the serialization point.

If the queue is not empty a PLO operation involving a Compare and Swap on the PLO sequence number and 3 di...