Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
2000-06-29
2003-09-02
Metjahic, Safet (Department: 2171)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000, C709S241000
Reexamination Certificate
active
06615216
ABSTRACT:
FIELD OF THE INVENTION
The present invention concerns a data structure for use with a computer and more particularly to a data structure that can be maintained by multiple processes running at the same time without loss of data structure integrity.
BACKGROUND ART
Updating or maintenance of data structures in a computer system becomes more difficult when the system has multiple processes running on multiple processors which are allowed access to the same data structure. In these so called shared memory systems, memory is accessible to all processors and the processors communicate through shared variables. One way of insuring that a data structure is properly maintained or updated in a shared memory system is to lock out processes and grant exclusive access to the shared memory to a single process. This so-called locking or blocking results in inefficient utilization of processor resources.
In a lock free shared memory scheme the multiple processes communicate through shared data structures but synchronization techniques are needed to guarantee the consistency of these data structures under simultaneous update conditions. In a PhD thesis entitled “Reducing the Overhead of Sharing on shared Memory Multiprocessors” by Michael from the Department of Computer Science, University of Rochester 1997, a shared queue process is discussed. A paper to Michael et al entitled “Simple, Fast, and Practical Non-Blocking Concurrent Queue Algorithms” also discusses the process of updating a queue using a lock free update process.
In setting up the shared queue the Michael thesis discusses an update problem known as the ABA problem. If a first process reads a value A in a shared memory location, then computes a new value, and then attempts a compare and swap operation to insert the new value into the shared location, the operation may succeed when it should not. Assume that after the reading of the shared memory but before the compare and swap, a second process having access to the shared memory location changes the value of the shared memory from A to B and then back to A The compare and swap performed by the first process should fail but it does not. A way of solving the ABA problem is to associate a modification counter with a pointer and to always access the counter with the pointer in any read-modify compare and swap operation.
The queue mentioned in the Michael thesis is implemented as a singly linked list having a tail pointer and a head pointer and uses a so called compare_and_swap instruction with modification counters to avoid the ABA problem.
SUMMARY OF THE INVENTION
The present invention concerns an efficient lockless data structure particularly suited for use in a multithreaded operating system that may include multiple processors executing stored program instructions for updating or maintaining the data structure. In one exemplary embodiment of the invention the data structure is a list structure. A queue such as the queue discussed in the Michael thesis is a specific form of a list data structure for storing data items (integers, floats, strings etc or structures made up of combinations of such data elements) in a first in, first out manner so that the data items can be added to and retrieved from the queue. On a multiprocessor system that uses shared memory data structures, there can be a single list that is accessed by multiple different processors executing multiple different processes or threads. The invention maintains the integrity of the queue list without resort to locking out threads from the multiple processors accessing the shared data structure.
The invention allocates data structure nodes from available memory and does not deallocate the nodes until the data structure (a queue for example) is released. Each node has a two part 64 bit (8 byte) unique identifying number. One part of the number is a pointer to a next queue node (32 bits) and the second part of the number (32 bits) is an integer that is an identifier or counter for that node which exists for the life of the data structure. The combination of the pointer and identifier are unique. A 64 bit compare_and_swap (CAS) instruction used with the invention is a hardware implemented operation that is more efficient than a comparable software technique. Use of this 64 bit compare and swap instruction allows any of a possible large number of multiprocessor threads to efficiently check the integrity of the contents of a node and take steps to properly implement an addition to the data structure or a deletion from the data structure even if a node is ‘simultaneously’ changed by another thread running on another processor. This integrity check is performed with the help of the pointer/counter combination (64 bits).
Access violations are avoided by keeping all nodes alive by means of a stack that is formed of nodes taken from the data structure by a processor thread. The stack is only released when its corresponding list data structure is released. Furthermore, nodes can be popped from the stack and reused as nodes on the list data structure without compromising the integrity checking since their identifier survives. Furthermore, reusing nodes from the stack is much faster to achieve than allocating a new node for use by means of the relatively slow C++ ‘new’ operator, for example.
An exemplary method performed in accordance with the invention maintains a list structure having data nodes within a computer memory. The list is maintained by the steps of maintaining a pool of available data nodes for use in maintaining the list structure. Data is added to the list structure by adding a nodes to the list structure. Each data node includes a data portion, a link for addressing other data nodes in the queue structure, and an identifier. Data within the list is accessed and then removed from the list but the data nodes are preserved in memory by adding them to the pool of available data nodes.
These and other objects, advantages and features of the invention will become better understood from the accompanying detailed description of one exemplary embodiment of the present invention.
REFERENCES:
patent: 5319778 (1994-06-01), Catino
patent: 5485626 (1996-01-01), Lawlor et al.
patent: 6247108 (2001-06-01), Long
patent: 6470344 (2002-10-01), Kothuri et al.
Article entitled “Relative Performance of Preemption-Safe Locking and Non-Blocking Synchronization on Multiprogrammed Shared Memory Multiprocessors”, by Maged M. Michael and Michael L.Scott, University of Rochester, Department of Science, date unknown.
Article entitled “Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms”, by Maged M. Michael and Michael L. Scott, University of Rochester, Department of Science, Jul. 1995.
Article entitled “Reducing the Overhead of Sharing on Shared Memory Multiprocessors” by Maged M. Michael, University of Rochester, Department of Computer Science, dated 1997.
Filipczyk Marcin
Metjahic Safet
Microsoft Corporation
Watts, Hoffmann, Fisher & Heinke Co. L.P.A.
LandOfFree
Lock free data structure maintenance does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Lock free data structure maintenance, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Lock free data structure maintenance will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3040684