Browse Prior Art Database

Method to remove queue element from the queue first position using Perform Locked Operation Disclosure Number: IPCOM000013171D
Original Publication Date: 2003-Jun-17
Included in the Prior Art Database: 2003-Jun-17
Document File: 5 page(s) / 45K

Publishing Venue



Disclosed is a method to remove the first element from a double headed double threaded queue in a multi-processing environment. This method employes the Perform Locked Operation (PLO) to atomically update the queue with proper serialization.

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

Page 1 of 5

  Method to remove queue element from the queue first position using Perform Locked Operation

  Removing a queue element from the first position of a queue that is used concurrently by more than one program thread requires serialization. The serialization is used to ensure that only one thread performs the update, and it also ensures that the top element remains accessible while the update is being performed. Ensuring that the top element remains accessible is necessary since the top element needs to be accessed in order to obtain the link pointer to the next element. Without the serialization, the top element could be removed and freemained, and this could led to an error if another program thread tries to access the storage under the assumption that the element had not yet been removed. This might occur if the address of the element had been obtained from the queue head before the element was removed. An additional concern is ensuring that the queue is properly updated when the queue is double threaded which requires that the second queue element back link be set to zero when it becomes the first element after the current first element is removed. In order to prevent an illegal access of the elements and to ensure that the queue is properly updated, a serialization scheme is used that typically involves obtaining a lock, or a latch, or an ENQ. These serialization techniques, however, may not offer good performance characteristics and may be difficult to implement with proper recovery. An additional solution is needed to provide serialization that has better performance and is easier to implement for a double threaded queue.

This invention uses two perform locked operation (PLO) instructions to remove the top queue element from a double headed double threaded queue such that the elements remains accessible and the queue is updated correctly. By using two PLO instructions, performance is greatly improved over the typical serialization techniques that involve locks, latches, or ENQs.

The following diagrams illustrate how the two PLO instructions are used to achieve the removal of the top queue element.



Time: t0 - this is how the queue anchor and the first two elements appear at the start of the operation. The queue head points

Q anchor First Element,addr = x Second Element, addr = y
+----------------+ +----------------+ +----------------+

| | Head - x | | Next - y | | Next - w |

+----------------+ +----------------+ +----------------+

| Tail - w | | Prev - 0 | | Prev - x |
+----------------+ +----------------+ +----------------+

| Seq# - n |


local Seq# | |



replacement Seq# | |



Page 2 of 5



Time: t1 - a local copy of the seq# is obtained

Q anchor First Element,addr...