Atomic operations on data structures

Details Atomic operations on data structures Atomic operations on data structures

1999-04-05

2002-11-19

Vu, Kim (Department: 2172)

Data processing: database and file management or data structures

Database design

Data structure types

C707S793000, C707S793000, C707S793000, C707S793000, C707S793000

Reexamination Certificate

active

06484185

ABSTRACT:

FIELD OF THE INVENTION
This invention relates generally to computer systems, and more particularly to performing atomic operations on a data structure.
COPYRIGHT NOTICE/PERMISSION
A portion of the disclosure of this patent document contains material which is subject to copyright protection. The copyright owner has no objection to the facsimile reproduction by anyone of the patent document or the patent disclosure as it appears in the Patent and Trademark Office patent file or records, but otherwise reserves all copyright rights whatsoever. The following notice applies to the software and data as described below and in the drawing hereto: Copyright 8 1998, 1999, Microsoft Corporation, All Rights Reserved.
BACKGROUND
It is common in today's multiprocessing and multithreaded computing environments for various executable units running on a computer system to share data by reading and writing data structures residing in shared memory. Sharing data in this manner provides an efficient mechanism for threads to communicate information with one another.
A common problem associated with using data structures in shared memory is managing multiple simultaneous requests to access the data structures and ensuring that accesses to the data are atomic. Guaranteeing atomic access is important because it ensures that the data structure is completely updated before another thread attempts to use the data. As an example, consider a data structure that is 32 bytes long. Without atomic access, one thread may have updated 16 bytes of the data structure when a second thread reads the data structure. The reading thread will read a corrupt version of the data structure, because the first 16 bytes will be new data while the last 16 bytes will be old data.
Atomic access to a data structure can be guaranteed by the hardware when the data structure meets size and alignment restrictions imposed by the particular hardware (typically the size of a machine word or floating point number). Atomic access cannot be guaranteed by the hardware for data structures that do not meet these restrictions. For example, on the Intel IA32 and IA32 compatible architectures, a data structure can only be read atomically by the hardware if it is 64 bits or smaller. In addition, a 64-bit data structure must be aligned on a 64 bit memory boundary and 32 bit data structures must be aligned on a 32 bit memory boundary to be read atomically.
In order to allow for atomic reads of data structures larger than that supported by the hardware, previous systems have provided software mechanisms to guarantee atomic reads of data structures. One such system involves the use of a lock mechanism. In systems using a lock, a thread that requires access to a shared data structure first acquires a lock on the data structure, typically using a function provided by the operating system. The process then updates the data structure. After the data structure is updated, the requesting thread releases the lock. Other threads that require access to the data structure may also attempt to acquire a lock on the data structure. If an attempt occurs while another thread has the data structure locked, the attempt will fail, and the requesting thread will block or wait until the lock becomes available.
Two types of locks are typically provided, exclusive locks and shared locks. An exclusive lock is used by threads that are writing a data structure. The writing thread has exclusive access during the lock period, no other thread may read from or write to the data structure. A shared lock is typically used by a thread that is reading a data structure. A shared lock allows other threads to read the data structure, but does not allow any thread to write to the data structure while the shared lock is in effect.
While software locks allow exclusive and atomic access to data structures, locks are expensive in terms of CPU (Central Processing Unit) and memory resources. The locking mechanisms are routines built around simpler data structures that can be atomically updated via hardware or firmware mechanisms. In addition to the overhead involved in the software used to implement the lock, the accesses to the lock data structures can cause pipeline stalls, poor memory-bus utilization, and cache memory misses. The problems listed above can occur regardless of whether the lock is an exclusive or shared lock. In addition, the problems listed above are compounded when a large number of threads need to access the same shared data structure.
Therefore there is a need in the art for a way to atomically access a data structure that is more efficient than the software lock mechanism used in previous systems.
SUMMARY
The above-mentioned shortcomings, disadvantages and problems are addressed by the present invention, which will be understood by reading and studying the following specification.
The systems and methods presented perform atomic operations on data entities having an arbitrary size. This includes data structures that cannot be atomically read by the hardware. The operations include read and write operations on the data entities.
Version data is associated with the data entities that are operated on. The version data is generated such that no simultaneously executing program units can erroneously determine that two different versions of a data entity are the same.
In one method, a program unit writes, or updates, the data entity. The write program unit acquires exclusive access to the version data associated with a data entity, sets the version data to a predetermined invalid value, and then updates the data entity. The write program unit then updates the version data to a new value and terminates exclusive access to the version data.
In another method, a program unit reads, or accesses, the data entity. The read program unit saves the version data associated with the data entity, reads the data entity, and then compares the current version data to the saved version data. If the current version data is set to a predetermined invalid value, the read program unit determines that a write program unit is in the middle of updating the data entity. This causes the read program unit to restart the attempt to read the data entity.
If the current version data is not equal to the saved version data, the read program unit determines that a write program unit has updated the data entity in the middle of the read program unit's attempt to read the data entity. This also causes the read program unit to restart the attempt to read the data entity.
The systems and methods summarized above, and various other methods for performing atomic operations on data entities will be described in detail in the next section.
The present invention describes systems, clients, servers, methods, and computer-readable media of varying scope. In addition to the aspects and advantages of the present invention described in this summary, further aspects and advantages of the invention will become apparent by reference to the drawings and by reading the detailed description that follows.


REFERENCES:
patent: 5327556 (1994-07-01), Mohan et al.
patent: 5452448 (1995-09-01), Sakuraba et al.
patent: 5761677 (1998-06-01), Senator et al.
patent: 5806078 (1998-09-01), Hug et al.
patent: 5918229 (1999-06-01), Davis et al.
patent: 5950201 (1999-09-01), Van Huben et al.
patent: 5956480 (1999-09-01), Kurihara
patent: 5960406 (1999-09-01), Rasansky et al.
patent: 6009428 (1999-12-01), Kleewein et al.
patent: 6026474 (2000-02-01), Carter et al.
patent: 6067550 (2000-05-01), Lomet
patent: 6247027 (2001-06-01), Chaudhry et al.

Affiliated with

Also associated with

Rating

Atomic operations on data structures does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Atomic operations on data structures, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Atomic operations on data structures will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2941840