Patent ID: 7447875

Claim:
A method for implementing a global queue, wherein the queue has a head pointer, a tail pointer, and a plurality of elements each having a next pointer, the head pointer functioning as a next pointer of a last element of the plurality of elements when the queue is empty, the method comprising: executing an add to end function for adding a new element to the tail end of the queue even when the queue is in a locked state immediately prior to execution of the add to end function in which the queue head pointer is null and a queue tail pointer does not point to the queue head pointer, the executing an add to end function including: setting a next pointer of the new element to null; as an atomic transaction, setting the queue tail pointer to point the new element while saving a location of the last element; and setting the next pointer of the last element to point to an address of the new element by using the last element's saved location.