Patent Document

FIELD OF THE INVENTION 
     The present invention pertains in general to the implementation and control of concurrent non-blocking queues used in parallel software applications having a shared data structure, and more particularly, but not by way of limitation, to a method and apparatus for selectively incrementing count numbers associated with addresses of nodes used in concurrent non-blocking queues. 
     BACKGROUND OF THE INVENTION 
     Computer systems are increasingly incorporating multiprocessing architectures which execute parallel software applications that share access to common data structures. Concurrent queues are used in multiprocessing computing environments. To insure “correctness,” concurrent access to shared queues is synchronized. Traditional approaches to synchronizing access to critical regions have incorporated preemptive based spinlocks. These approaches are “blocking” and are not suitable for providing multiprocessor safe synchronization of critical regions between multiple threads of execution in user space (i.e. application software). The blocking characteristic of spinlock methods also reduces software scalability in situations of high contention in critical regions of a multiprocessor environment. 
     A set of concurrent non-blocking methods which demonstrate superior performance over traditional spinlock methods of multiprocessor synchronization have been developed by Maged M. Michael and Michael L. Scott. These methods allow multiple processors to gain concurrent non-blocking access to shared First In First Out (FIFO) queues with immunity from inopportune preemption and are especially useful for parallel software applications requiring shared access to FIFO queues. Furthermore, these methods demonstrate nearly linear scalability under high contention of critical regions in a multiprocessor environment and are incorporated directly in application software. These methods do not affect processor interrupts and do not require spinlock methods to provide mutual exclusion to a shared critical region. These methods are presented and described in greater detail in a publication authored by Maged M. Michael and Michael L. Scott, entitled “ Simple, Fast, and Practical Non - Blocking and Blocking Concurrent Queue Algorithms ,” published in the 15th ACM Symposium on Principles of Distributed Computing (PODC), May 1996. 
     Following is pseudo-code for implementing these methods as presented in the publication: 
     
       
         
               
             
               
               
             
               
             
               
               
               
             
               
             
               
               
               
             
               
               
               
             
               
               
               
             
               
               
             
               
               
               
             
               
               
             
               
               
               
             
               
               
             
               
               
             
               
               
               
             
               
             
               
               
               
             
               
               
               
             
               
               
               
             
               
               
               
             
               
               
               
             
               
               
               
             
               
               
               
             
               
               
             
               
               
               
             
               
               
               
             
               
               
             
               
               
             
               
               
             
               
               
               
             
           
               
                   
               
             
             
               
                   structure  pointer_t {ptr:  pointer to  node_t, count:  undersigned integer } 
               
             
          
           
               
                   structure  node_t 
                 {value: data type, next pointer_t} 
               
             
          
           
               
                   structure  queue_t  {Head: pointer_t, Tail: pointer_t} 
               
               
                 initialize(Q:  pointer to  queue_t) 
               
             
          
           
               
                   
                 node=new_node() 
                 # Allocate a free node 
               
               
                   
                 node−&gt;next.ptr=NULL 
                 # Make it the only node in the linked list 
               
               
                   
                 Q−&gt;Head=Q−&gt;Tail=node 
                 # Both Head and Tail point to it 
               
             
          
           
               
                 enqueue(Q: pointer to  queue_t, value: data type) 
               
             
          
           
               
                 E1: 
                 node=new_node() 
                 # Allocate a new node from the free list 
               
               
                 E2: 
                 node−&gt;value=value 
                 # Copy equenced value into node 
               
               
                 E3: 
                 node−&gt;next.ptr=NULL 
                 # Set next pointer of node to NULL 
               
               
                 E4: 
                 
                   loop 
                 
                 # Keep trying until Enqueue is done 
               
             
          
           
               
                 E5: 
                 tail=Q−&gt;Tail 
                 # Read Tail.ptr and Tail.count together 
               
               
                 E6: 
                 next=tail.ptr−&gt;next 
                 # Read next ptr and count fields together 
               
               
                 E7: 
                   if  tail ==Q−&gt;Tail 
                 # Are tail and next consistent? 
               
             
          
           
               
                 E8: 
                   if  next.ptr==NULL 
                 # Was Tail pointing to the last node? 
               
             
          
           
               
                 E9: 
                   if  CAS(&amp;tai1.ptr−&gt;next, next, &lt;node, next.count+1&gt;)# Try to link node at the end of the linked list 
               
             
          
           
               
                 E10: 
                 
                   break 
                 
                 # Enqueue is done. Exit loop 
               
             
          
           
               
                 E11: 
                 
                   endif 
                 
               
             
          
           
               
                 E12: 
                 
                   else 
                 
                 # Tail was not pointing to the last node 
               
             
          
           
               
                 E13: 
                 CAS(&amp;Q−&gt;Tail, tail, &lt;next.ptr, tail.count+1&gt;) # Try to swing Tail to the next node 
               
               
                 E14: 
                 
                   endif 
                 
               
             
          
           
               
                 E15: 
                 
                   endif 
                 
               
             
          
           
               
                 E16: 
                 
                   endloop 
                 
                   
               
               
                 E17: 
                 CAS(&amp;Q−&gt;Tail, tail, &lt;node, tail.count+1) 
                 # Enqueue is done. Try to swing to the 
               
               
                   
                   
                 inserted node 
               
             
          
           
               
                 dequeue(Q:  pointer to  queue_t, pvalue:  pointer to  data type):  boolean   
               
             
          
           
               
                 D1: 
                 
                   loop 
                 
                 # Keep trying until Dequeue is done 
               
             
          
           
               
                 D2: 
                 head=Q−&gt;Head 
                 # Read Head 
               
               
                 D3: 
                 tail=Q−&gt;Tail 
                 # Read Tail 
               
               
                 D4: 
                 next=head−&gt;next 
                 # Read Head.ptr−&gt;next 
               
               
                 D5: 
                   if  head == Q−&gt;Head 
                 # Are head, tail, and next consistent? 
               
             
          
           
               
                 D6: 
                   if  head.ptr==tail.ptr 
                 # Is queue empty or Tail falling behind? 
               
             
          
           
               
                 D7: 
                   if  next.ptr==NULL 
                 # Is queue empty? 
               
             
          
           
               
                 D8: 
                   return  FALSE 
                 # Queue is empty, couldn&#39;t dequeue 
               
             
          
           
               
                 D9: 
                 
                   endif 
                 
                   
               
               
                 D10: 
                 CAS(&amp;Q−&gt;Tail, tail, &lt;next.ptr, tail.count+1&gt;) 
                 # Tail is falling behind. Try to advance it 
               
             
          
           
               
                 D11: 
                 
                   else 
                 
                 # No need to deal with Tail 
               
             
          
           
               
                   
                 # Read value before CAS, otherwise another dequeue might free the next node 
               
             
          
           
               
                 D12: 
                   * pvalue=next.ptr−&gt;value 
                   
               
               
                 D13: 
                   if  CAS(&amp;Q−&gt;Head, head, &lt;next.ptr, head.count+1&gt;) 
                 # Try to swing Head to the next node 
               
             
          
           
               
                 D14: 
                 
                   break 
                 
                 # Dequeue is done. Exit loop 
               
             
          
           
               
                 D15: 
                 
                   endif 
                 
               
             
          
           
               
                 D16: 
                 
                   endif 
                 
               
             
          
           
               
                 D17: 
                 
                   endif 
                 
               
             
          
           
               
                 D18: 
                 
                   endloop 
                 
                   
               
               
                 D19: 
                 free(head.ptr) 
                 # It is safe now to free the old dummy node 
               
               
                 D20: 
                   return  TRUE 
                 # Queue was not empty, dequeue succeeded 
               
               
                   
               
             
          
         
       
     
     One shortcomings of these queuing methods, however, involves a condition referred to as an “ABA” condition. The “ABA” condition occurs on computing platforms, such as the Intel 486 and the Pentium class lines of processors, which utilize a Compare-And-Swap (CAS) atomic primitive. The “ABA” condition occurs when a process reads a value “A” from a shared memory location, computes a new value and then attempts the CAS operation. In certain circumstances, the CAS operation may succeed when it should have failed. Such a situation arises when, between the memory read and the CAS operation, some other process or processes change the value “A” to value “B” and then back to value “A.” Although the CAS operation succeeds since the value of the shared memory location has returned to value “A,” the value in the memory location to which “A” points may have changed. To reduce the probability of encountering the “ABA” condition, the aforementioned queuing methods implement a sequence or count number as part of node address associated with the shared memory location. The count number is incremented with every successful CAS operation so that a determination can be made as to whether the contents of the shared memory location has been altered. While the use of count numbers reduces the probability of encountering the “ABA” condition, the method falls short on the previously mentioned Intel processors due to the frequent incrementing of the count number which causes the count to wrap around and possibly end up at the original count number. The probability of a wrap around condition occurring is especially likely in high contention situations and increases as the speed of the processor increases and the total number of nodes in the queue decreases. 
     It would be advantageous therefore, to devise a method and apparatus which selectively increments count numbers associated with nodes in a queue to reduce the number of times the count numbers are incremented. Such a method and apparatus would increase the time between the occurrence of wrap around conditions and thereby, reduce the likelihood of encountering an “ABA” condition. 
     SUMMARY OF THE INVENTION 
     The present invention comprises a method and apparatus for selectively incrementing a count number associated with a node which is subject to a compare and swap operation in a concurrent non-blocking queue. A memory stores data in a plurality of nodes residing in at least one queue. The plurality of nodes store both data and references to other nodes within the queue. An address of each node includes a pointer and a count number. A plurality of processors access the memory and operate on the plurality of nodes including performing a compare and swap operation. The count number of a node is selectively incremented only upon a successful compare and swap operation when the node is put in use by removing the node from an available source of free nodes and placing the node on the queue. Otherwise, the count number of the node is preserved. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     A more complete understanding of the present invention may be had by reference to the following Detailed Description and appended claims, when taken in conjunction with the accompanying Drawings wherein: 
     FIG. 1 is a functional block diagram of a computer system for incrementing count numbers associated with addresses of nodes used in concurrent non-blocking queues and depicts the movement of nodes from a free list queue to a FIFO list queue and back to the free list queue; 
     FIG. 2A is a block diagram of the free list queue and the FIFO list queue including a pointer and count number associated with each node in the queues at an initial queue state; 
     FIG. 2B is a block diagram of the free list queue and the FIFO list queue including the pointer and count number associated with each node in the queues following the enqueuing of a first item to the FIFO queue; 
     FIG. 2C is a block diagram of the free list queue and the FIFO list queue including the pointer and count number associated with each node in the queues following the dequeueing of the first item from the FIFO queue; 
     FIG. 2D is a block diagram of the free list queue and the FIFO list queue including the pointer and count number associated with each node in the queues following the enqueuing of a second item to the FIFO queue; 
     FIG. 2E is a block diagram of the free list queue and the FIFO list queue including the pointer and count number associated with each node in the queues following the dequeueing of the second item from the FIFO queue; and 
     FIG. 3 is a flow diagram of a method for incrementing count numbers associated with addresses of nodes used in concurrent non-blocking queues consistent with the preferred embodiment described in FIG.  1 . 
    
    
     DETAILED DESCRIPTION 
     The present invention hereby incorporates by reference a publication authored by Maged M. Michael and Michael L. Scott, entitled “ Simple, Fast, and Practical Non - Blocking and Blocking Concurrent Queue Algorithms ,” published in the 15th ACM Symposium on Principles of Distributed Computing (PODC), May 1996. 
     Instead of viewing the “ABA” condition as attributable to a change in any memory cell resulting from a CAS operation as the current methods do, the present invention views the condition as resulting from an explicit reuse of a node. Therefore, the present invention tracks node reuse instead of memory cell reuse. The present invention increments the count number once per node only when the node is removed from a free list and placed on a FIFO list. In a first embodiment of the present invention, the count number is incremented when the node is removed from the free list. In an alternative embodiment of the present invention, the count number is incremented when the node is placed on the FIFO list. Therefore, while the current methods indiscriminately increment the count number in conjunction with each successful CAS operation, the present invention increments the count number only when the node is reused. 
     Referring now to FIG. 1, there is illustrated a functional block diagram of a computer system for incrementing count numbers associated with addresses of nodes used in concurrent non-blocking queues and depicts the movement of nodes from a free list queue to a FIFO list queue and back to the free list queue. A computer system shown generally at  100  comprises a plurality of processors  110 , which execute parallel software applications, and a shared memory  120  accessible by the plurality of processors  110 . The memory  120  is partitioned to include at least a free list  130  and a FIFO list  140 . The free list  130  and the FIFO list  140  comprise a plurality of nodes  150 A-E. Each node  150 A-E is a memory packet used to hold both data and a reference to the next node in a list of nodes. The free list  130  is a Last in First Out (LIFO) based concurrent non-blocking stack used to hold free nodes available to queue data onto the FIFO list  140 . The FIFO list is a First In First Out based concurrent non-blocking queue used to hold nodes containing data. Both the free list  130  and the FIFO list  140  contain an extra node, referred to as a dummy node, which prevents head pointers and tail pointers associated with the free list  130  and the FIFO list  140  from assuming a null value. The plurality of nodes  150 A-E include an associated plurality of pointers  153 A-E, an associated plurality of count numbers  156 A-E and an associated plurality of data storage locations  157 A-E. The pointer  153  and the count number  156  of a given node  150  together form a node address for a next node in a list of nodes with the pointer  153  pointing to the next node and the count number  156  indicative of the reuse of the next node. 
     In FIG. 1, nodes  150 A-B are shown as residing in the free list  130  while nodes  150 C-E are shown as residing in the FIFO list  140 . The free list  130  further comprises a free list head pointer  160  and a free list tail pointer  170 . Similarly, the FIFO list  140  further comprises a FIFO list head pointer  180  and a FIFO list tail pointer  190 . The free list head pointer  160  and the FIFO list head pointer  180  represent tops of the respective lists and point to the first node on the respective lists. The free list tail pointer  170  and the FIFO list tail pointer  190  represent bottoms of the respective lists and point to the last node on the respective lists. 
     Nodes  150 A-B in the free list  130  are organized as a Last In First Out (LIFO) queue also referred to as a stack with the nodes  150 A-B relating to one another in a single linked list using the node addresses comprised of the associated pointers  153 A-B and count numbers  156 A-B. Node  150 A is at the top of the stack and is, therefore, referred to as the free list head while node  150 B is at the bottom of the stack and is, therefore, referred to as the free list tail. The pointer  153 A of node  150 A points to the next node in the free list  130 , in this example node  150 B, while the pointer  153 B of node  150 B points to null since node  150 B is the tail of the free list  130 . In this instance, the queue is a LIFO queue and therefore, the free list tail, node  150 B is the dummy node for the free list  130 . Although FIG. 1, depicts the free list  130  as including two nodes,  150 A-B, it is understood that the free list  130  can include any number of nodes and needs only to contain the one dummy node. 
     Nodes  150 C-E in the FIFO list  140  are organized as a First In First Out (FIFO) queue with the nodes  150 C-E relating to one another in a single linked list using the node addresses comprised of the associated pointers  153 C-E and count numbers  156 C-E. Node  150 E is at the beginning of the FIFO list  140  and is, therefore, referred to as the FIFO list head while node  150 C is at the end of the FIFO list  140  and is, therefore, referred to as a FIFO list tail. The pointer  153 E of node  150 E points to the next node in the FIFO list  140 , node  150 D, while the pointer  153 D of node  150 D points to the following node in the FIFO list  140 , node  150 C. The pointer  153 C of node  150 C points to null since node  150 C is the tail of the FIFO list  140 . Nodes  150 C-D have been placed on the FIFO list  140  and, therefore, contain data in the respective data storage locations  157 C-D. In this instance, the queue is a FIFO queue and therefore, the FIFO list head, node  150 E, is the dummy node and contains no data in its data storage location  157 E. Although FIG. 1, depicts the FIFO list  140  as including three nodes  150 C-E, it is understood that the FIFO list  140  can include any number of nodes and needs only to contain the one dummy node. 
     The free list head pointer  160  contains the node address for the free list head, node  150 A, and is comprised of a head node pointer  163 , which points to the free list head, node  150 A, and an associated count number  166 . Likewise, the free list tail pointer  170  contains the node address for the free list tail, node  150 B, and is comprised of a tail node pointer  173 , which points to the free list tail, node  150 B, and an associated count number  176 . 
     The FIFO list head pointer  180  contains the node address for the FIFO list head, node  150 E, and is comprised of a head node pointer  183 , which points to the FIFO list head, node  150 E, and an associated count number  186 . Likewise, the FIFO list tail pointer  190  contains the node address for the FIFO list tail, node  150 C, and is comprised of a tail node pointer  193 , which points to the FIFO list tail, node  150 C, and an associated count number  196 . 
     A node address for a given node contains a pointer and a count number. Furthermore, the node address for the node does not reside in the pointer and count number forming the memory packet which constitutes the node. Instead, the node address for the node is found in the pointer and count number of other nodes which point to the given node. For example, the node address formed by the pointer  153 D and  156 D of node  150 D is not the node address of node  150 D but rather, is the node address of node  150 C, the node to which node  150 D points. 
     When node  150 A is removed from the free list  130  to be placed on the FIFO list  140  as shown by path  200 , the count number contained in the node address of node  150 A is incremented. In accordance with the present invention, this is the only situation in which the count number is incremented. In a first embodiment of the present invention the count number is incremented when the node at the top of the free list  130  is dequeued from the free list  130 . In an alternative embodiment, the count number is incremented when the node at the top of the free list  130  is enqueued to the FIFO list  140 . In addition to incrementing the count number, data is stored in the data storage location  157 A of node  150 A when node  150 A is dequeued from the free list  130  and node  150 A is enqueued to the FIFO list  140 . Since node  150 A is no longer the free list head and node  150 C is no longer the FIFO list tail, several node address changes occur. 
     The node address contained in the FIFO list tail pointer  190  and the node address contained in node  150 C are modified to point to node  150 A. The node address for node  150 A is obtained from the free list head pointer  160  with the count number being incremented since the free list head, node  150 A, is being dequeued from the free list  130  and enqueued to the FIFO list  140  in accordance with the present invention. The node address contained in the free list head pointer  160  is modified to point to node  150 B, the new free list head. The node address for node  150 B is obtained from node  150 A which previously pointed to node  150 B. The node address contained in node  150 A is modified to point to null since node  150 A is the new FIFO list tail. 
     When node  150 E is removed from the FIFO list  140  and placed on the free list  130  as shown by path  203 , the node address of  150 E is not incremented in accordance with the present invention. Since node  150 E is no longer the FIFO list head and node  150 B is no longer the free list head, several node address changes occur. The node address contained in the FIFO list head pointer  180  is modified to point to node  150 D. The node address for node  150 D is obtained from node  150 E. The node address contained in node  150 E is modified to point to node  150 B. The node address for node  150 B is obtained from the free list head pointer  160 . The node address contained in the free list head pointer  160  is modified to point to node  150 E. The node address for node  150 E can be obtained from the previous node address contained in the FIFO list head pointer  180 . The previous node address contained in the FIFO list head pointer  180  can be temporarily stored in any manner, for example, temporarily storing the value in one of the processors  110 . 
     Referring additionally now to FIG. 2A, there is illustrated a block diagram of the free list queue  130  and the FIFO list queue  140  including a pointer and count number associated with each node in the queues at an initial queue state. In addition to the components and functionality described in FIG. 1, FIGS.  2 A-E further include reference numbers  1 - 5  associated with nodes  150 A-E corresponding to locations or addresses of the nodes  150 A-E in the memory  120 . The reference numbers  1 - 5  are used in the examples as the pointer values. Although FIGS.  2 A-E depict the values of the pointers used in the free list  130  and the FIFO list  140 , for purposes of clarity, a description of the transitions in their values is not provided. It is understood that the methods in which the transitions in the values of the pointers occur is well known and is described in FIG. 1, as well as in the publication incorporated by reference. 
     In the initial queue state, the free list  130  contains four nodes, nodes  150 A-D including dummy node  150 D and the FIFO list  140  contains a single dummy node, node  150 E. Each of the count numbers  156 A-E.  166 , 176 ,  186  and  196  are set to a certain initial value which, in this example, is the value zero. 
     Referring additionally now to FIG. 2B, there is illustrated a block diagram of the free list queue  130  and the FIFO list queue  140  including the pointer and count number associated with each node in the queues following the enqueuing of a first item to the FIFO queue  140 . When the head node of the free list  130 , node  150 A, is removed from the free list  130  and placed on the FIFO list  140  due to the enqueuing of the first item (A), the count number contained in the node address of node  150 A is incremented. As is shown in FIG. 2B, the count number  156 A is not incremented since it is not part of the node address of node  150 A. Instead, the count numbers,  156 E and  196  of node  150 E and FIFO list tail pointer  190  reflect the incrementing since they contain the node address which point to node  150 A. In accordance with the present invention, this is the only situation in which count numbers of a node are incremented. 
     Referring additionally now to FIG. 2C, there is illustrated a block diagram of the free list queue  130  and the FIFO list queue  140  including the pointer and count number associated with each node in the queues following the dequeueing of the first item from the FIFO queue  140 . When the node at the head of the FIFO list  140 , node  150 E, is removed from the FIFO list  140  and placed on the free list  130  due to the dequeueing of the first item (A), no count number is incremented. Node  150 E is removed from the FIFO list  140  and placed on the free list  130  and the first data item (A) is removed from node  150 A. 
     Referring additionally now to FIG. 2D, there is illustrated a block diagram of the free list queue  130  and the FIFO list queue  140  including the pointer and count number associated with each node in the queues following the enqueuing of a second item to the FIFO queue  140 . When a node at the head of the free list  130 , node  150 E, is removed from the free list  130  and placed on the FIFO list  140  due to the enqueuing of a second item (B), the count number contained in the node address of node  150 E is incremented. As is shown in FIG. 2B, the count number  156 E is not incremented since it is not part of the node address of node  150 E. Instead, the count number,  156 A and  196  of the node  150 A and FIFO list tail pointer  190  are incremented since they form part of the node addresses which point to node  150 E. In accordance with the present invention, this is the only situation in which count numbers of a node are incremented. 
     Referring additionally now to FIG. 2E, there is illustrated a block diagram of the free list queue  130  and the FIFO list queue  140  including the pointer and count number associated with each node in the queues following the dequeueing of the second item from the FIFO queue  140 . When the node at the head of the FIFO list  140 , node  150 A, is removed from the FIFO list  140  and placed on the free list  130  due to the dequeueing of the second item (B), no count number is incremented. Node  150 A is removed from the FIFO list  140  and placed on the free list  130  and the second data item (B) is removed from node  150 E. 
     Referring additionally now to FIG. 3, there is illustrated a flow diagram of a method for incrementing count numbers  156 A-E associated with nodes  150 A-E in concurrent non-blocking queues consistent with the preferred embodiment described in FIG.  1 . The computer system  100  establishes a free list  130  (step  300 ) and establishes a FIFO list  140  (step  310 ). During the operation of the processors  110 , a condition is encountered which requires a node, from the plurality of nodes  150 A-E, to be inserted onto or removed from either the free list  130  or the FIFO list  140  (step  320 ). In accordance with the encountered condition, the node is either removed from the free list  130  (step  330 ), inserted onto the FIFO list  140  (step  340 ), removed from the FIFO list  140  (step  350 ) or inserted onto the free list  130  (step  360 ) and a compare and swap operation is encountered (step  370 ). A determination is made as to whether the compare and swap operation was successful and whether the node which was the subject of the compare and swap operation was removed from the free list  130  (step  380 ). If the compare and swap operation was unsuccessful or if the node which was the subject of the compare and swap operation was not removed from the free list  130 , the count number of the node is preserved (step  390 ). If, on the other hand, the compare and swap operation was successful and the node which was the subject of the compare and swap operation was removed from the free list  130 , the count number of the node is incremented (step  400 ). 
     In an alternative embodiment, in step  380  a determination is made as to whether the compare and swap operation was successful and whether the node which was the subject of the compare and swap operation was placed on the FIFO list  140 . If the compare and swap operation was unsuccessful or if the node which was the subject of the compare and swap operation was not placed on the FIFO list  140 , the count number of the node is preserved in step  390 . Otherwise, if the compare and swap operation was successful and the node which was the subject of the compare and swap operation was placed on the FIFO list  140 , the count number of the node is incremented in step  400 . 
     The following pseudo-code is provided as an example of one way in which the method described in FIG. 2, may be implemented. 
     
       
         
               
             
               
               
             
               
               
             
               
               
             
               
               
             
               
               
             
               
               
             
               
               
             
               
               
             
               
               
             
               
               
             
               
               
             
               
               
             
               
               
             
               
               
             
               
               
             
               
             
               
               
             
               
               
             
               
               
             
               
               
             
               
               
             
               
               
             
               
               
             
               
               
             
               
               
             
               
               
             
               
               
             
               
               
             
               
               
             
               
             
               
               
             
               
               
             
               
               
             
               
               
             
               
               
             
               
               
             
               
               
             
               
               
             
               
               
             
               
             
               
               
             
               
               
             
               
               
             
               
               
             
               
               
             
           
               
                   
               
             
             
               
                 ENQUEUE (Q: pointer to QUEUE, Data):BOOLEAN 
               
             
          
           
               
                 E1: 
                   if  NEWNODE (Q, &amp;node) == TRUE 
               
             
          
           
               
                 E2: 
                 node.ptr−&gt;data=Data 
               
               
                 E3: 
                 node.ptr−&gt;next.ptr = NULL // this could also be node.ptr−&gt;next = NULL 
               
               
                 E4: 
                 
                   loop 
                 
               
             
          
           
               
                 E5: 
                 tail = Q−&gt;fifolist−&gt;tail 
               
               
                 E6: 
                 next = tailnode.ptr−&gt;next 
               
               
                 E7: 
                   if  tail == Q−&gt;fifolist−&gt;tail 
               
             
          
           
               
                 E8: 
                   if  next.ptr == NULL 
               
             
          
           
               
                 E9: 
                   if  CAS (&amp;tail.ptr−&gt;next, next, node) == TRUE 
               
             
          
           
               
                 E10: 
                 
                   break 
                 
               
             
          
           
               
                 E11: 
                 
                   endif 
                 
               
             
          
           
               
                 E12: 
                 
                   else 
                 
               
             
          
           
               
                 E13: 
                 CAS (&amp;Q−&gt;fifolist−&gt;tail, tail, next) 
               
             
          
           
               
                 E14: 
                 
                   endif 
                 
               
             
          
           
               
                 E15: 
                 
                   endif 
                 
               
             
          
           
               
                 E16: 
                 
                   endloop 
                 
               
               
                 E17: 
                 CAS (&amp;Q−&gt;fifolist−&gt;tail, tail, node) 
               
               
                 E18: 
                   return  TRUE 
               
             
          
           
               
                 E19: 
                 
                   else 
                 
               
             
          
           
               
                 E20: 
                   return  FALSE 
               
             
          
           
               
                 E21: 
                 
                   endif 
                 
               
             
          
           
               
                 DEQUEUE (Q: pointer to QUEUE.pData):BOOLEAN 
               
             
          
           
               
                 D1: 
                 
                   loop 
                 
               
             
          
           
               
                 D2: 
                 head = Q−&gt;fifolist−&gt;head 
               
               
                 D3: 
                 tail = Q−&gt;fifolist−&gt;tail 
               
               
                 D4: 
                 next = head.ptr−&gt;next 
               
               
                 D5: 
                   if  head == Q−&gt;fifolist−&gt;head 
               
             
          
           
               
                 D6: 
                   if  head.ptr == tail.ptr 
               
             
          
           
               
                 D7: 
                   if  next.ptr == NULL 
               
             
          
           
               
                 D8: 
                   return  FALSE 
               
             
          
           
               
                 D9: 
                 
                   endif 
                 
               
               
                 D10: 
                 CAS (&amp;Q−&gt;fifolist−&gt;tail, tail, next) 
               
             
          
           
               
                 D11: 
                 
                   else 
                 
               
             
          
           
               
                 D12: 
                   * pData = next.ptr−&gt;data 
               
               
                 D13: 
                 if CAS (&amp;Q−&gt;fifolist−&gt;head, head, next) == TRUE 
               
             
          
           
               
                 D14: 
                 
                   break 
                 
               
             
          
           
               
                 D15: 
                 
                   endif 
                 
               
             
          
           
               
                 D16: 
                 
                   endif 
                 
               
             
          
           
               
                 D17: 
                 
                   endif 
                 
               
             
          
           
               
                 D18: 
                 
                   endloop 
                 
               
               
                 D19: 
                 FREENODE (Q, head) 
               
               
                 D20: 
                   return  TRUE 
               
             
          
           
               
                 NEWNODE(Q: pointer to QUEUE, pNode: pointer to NODE):BOOLEAN 
               
             
          
           
               
                 N1: 
                 
                   loop 
                 
               
             
          
           
               
                 N2: 
                 head = Q−&gt;freelist−&gt;head 
               
               
                 N3: 
                 next = head.ptr−&gt;next 
               
               
                 N4: 
                   if  head == Q−&gt;freelist−&gt;head 
               
             
          
           
               
                 N5: 
                   if  next.ptr == NULL 
               
             
          
           
               
                 N6: 
                   return  FALSE 
               
             
          
           
               
                 N7: 
                 
                   endif 
                 
               
               
                 N8: 
                   if  CAS (&amp;Q−&gt;freelist−&gt;head, head, next) == TRUE 
               
             
          
           
               
                 N9: 
                   * pNode = [head.ptr,head.count+1] 
               
               
                 N10: 
                   return  TRUE 
               
             
          
           
               
                 N11: 
                 
                   endif 
                 
               
             
          
           
               
                 N12: 
                 
                   endif 
                 
               
             
          
           
               
                 N13: 
                 
                   endloop 
                 
               
             
          
           
               
                 FREENODE (Q: pointer to QUEUE, Node: NODE) 
               
             
          
           
               
                 F1: 
                 
                   loop 
                 
               
             
          
           
               
                 F2: 
                 head = Q−&gt;freelist−&gt;head 
               
               
                 F3: 
                 node.ptr−&gt;next = head 
               
               
                 F4: 
                   if  CAS (&amp;Q−&gt;freelist−&gt;head,head,Node) == TRUE 
               
             
          
           
               
                 F5: 
                 
                   return 
                 
               
             
          
           
               
                 F6: 
                 
                   endif 
                 
               
             
          
           
               
                 F7: 
                 
                   endloop 
                 
               
               
                   
               
             
          
         
       
     
     As has been described, the count number  153 A-E, for any given node in the plurality of nodes  150 A-E, is incremented only once during a cycle of removing the node from the free list  130 , inserting the node on the FIFO list  140 , removing the node from the FIFO list  140  and inserting the node on the free list  130 . This is in contrast to incrementing the count number  153  on every successful compare and swap operation as has previously been done. Reducing the number of times the count number  153  is incremented reduces the number of times the count number  153  wraps around and, therefore, reduces the probability that the “ABA” condition is encountered. 
     The present invention has been described as being preformed using a single read operation to read data from memory locations, for example preforming a thirty-two bit compare and swap operation on a processor capable of performing a thirty-two bit read operation. It is understood, however, that the present invention is equally applicable to situations where two or more read operations are required to read a memory location such as on a processor which requires two thirty-two bit read operations to read a sixty-four bit memory location which is the subject of a sixty-four bit compare and swap operation. 
     Although the preferred embodiments of the present invention have been illustrated in the accompanying Drawings and described in the foregoing Detailed Description, it is understood that the invention is not limited to the embodiments disclosed, but is capable of numerous rearrangements, modifications and substitutions without departing from the spirit of the invention as set forth and defined by the following claims. For example, while the Detailed Description and accompanying Drawings describe the memory as partitioned into a free list and a FIFO list, the memory can further be partitioned into other data structures which employ the method and apparatus of the present invention.

Technology Category: g