Concurrency technique for shared objects

Abstract

In some embodiments, a Hat Trick deque requires only a single DCAS for most pushes and pops. The left and right ends do not interfere with each other until there is one or fewer items in the queue, and then a DCAS adjudicates between competing pops. By choosing a granularity greater than a single node, the user can amortize the costs of adding additional storage over multiple push (and pop) operations that employ the added storage. A suitable removal strategy can provide similar amortization advantages. The technique of leaving spare nodes linked in the structure allows an indefinite number of pushes and pops at a given deque end to proceed without the need to invoke memory allocation or reclamation so long as the difference between the number of pushes and the number of pops remains within given bounds. Both garbage collection dependent and explicit reclamation implementations are described.

1 . A method of efficiently managing concurrent access to a double-ended data structure, the method comprising: 
 encoding the double-ended data structure using a subset of a bi-directional referencing chain of nodes instantiated in addressable memory storage;    distinguishing between nodes that encode current state of the data structure and at least one pool of one or more spare nodes thereof;    accessing the current state of the double-ended data structure in the course of plural concurrent computations, wherein two of the plural computations operate at opposing ends of the double-ended data structure; and    coordinating the accessing and any removal of nodes from the spare node pool using a synchronization mechanism that coordinates lock-free access to at least two independently addressable locations in the memory storage.    
   
   
       2 . The method of  claim 1 , 
 wherein the synchronization mechanism includes use of transactional memory.    
   
   
       3 . The method of  claim 1 , 
 wherein the synchronization mechanism includes use of an operation that linearizably updates N locations in the memory storage, N≧2.    
   
   
       4 . The method of  claim 1 , 
 wherein the synchronization mechanism employs a non-blocking software emulation.    
   
   
       5 . The method of  claim 1 , 
 wherein the synchronization mechanism employs a DCAS operation implemented in processor hardware.    
   
   
       6 . The method of  claim 1 , 
 employed in the implementation of a garbage collector.    
   
   
       7 . An implementation of a garbage collector, the implementation comprising: 
 a double-ended concurrent shared object organized as a dynamically-sized bi-directional referencing chain of nodes, the double-ended concurrent shared object distinguishing spare nodes thereof; and    a lock-free mechanism for coordinating adding and deleting the spare nodes with concurrent opposing-end accesses for states of two or more values.    
   
   
       8 . The garbage collector implementation of  claim 7 , 
 embodied as instruction sequences encoded in one or more computer readable media.    
   
   
       9 . The garbage collector implementation of  claim 7 , 
 embodied as a programmed computational machine.    
   
   
       10 . The garbage collector implementation of  claim 7 , 
 in combination with addressable memory storage in which the bi-directional referencing chain of nodes is instantiated,    wherein the lock-free mechanism coordinates access to at least two independently addressable locations in the memory storage.    
   
   
       11 . The garbage collector implementation of  claim 7 , 
 wherein the lock-free mechanism employs transactional memory.    
   
   
       12 . The garbage collector implementation of  claim 7 , 
 wherein the lock-free mechanism includes use of an operation that linearizably updates N locations in memory storage, N≧2.    
   
   
       13 . The garbage collector implementation of  claim 7 , 
 wherein the lock-free mechanism employs a software emulation.    
   
   
       14 . The garbage collector implementation of  claim 7 , 
 wherein the lock-free mechanism employs a DCAS operation implemented in processor hardware.