Object queues with concurrent updating

Details Object queues with concurrent updating Object queues with concurrent updating

1998-12-16

2002-03-19

Von Buhr, Maria N. (Department: 2171)

Data processing: database and file management or data structures

Database design

Data structure types

C707S793000, C710S052000, C711S133000, C711S159000

Reexamination Certificate

active

06360219

ABSTRACT:

FIELD OF THE INVENTION
The present invention relates to concurrency control management for data structures in multi-user systems and, in particular, to concurrency control management for object queues.
BACKGROUND AND SUMMARY OF THE INVENTION
In database systems, a transaction is a mechanism that allows multiple users to atomically perform in isolation database modifications that are guaranteed to be consistent and resilient when committed. With reference to database information in the form of software objects, for example, a write/write conflict occurs when an object modified in one transaction (e.g., by one user) is modified by another concurrent transaction (e.g., by another user). For example, when a transaction (e.g., by a first user) writes an object and executes complex behavior based upon the state of that object, the transaction cannot commit successfully if in the meantime another transaction (e.g., by a second user) has committed a modification of that object.
To prevent such concurrency conflicts, a database system implementer can either lock objects to prevent more than one user at a time from accessing the object or write complex application code to avoid the conflicts. A transaction can lock the objects being modified by the transaction to prevent conflicts with other transactions. However, locking can be expensive because it requires arbitration by a lock manager and deadlock detection. Locking objects also enforces an ordering of transactions such that the database remains in a consistent state, but this comes at the cost of decreased availability of the locked objects. When a transaction locks an object, other transactions are restricted from accessing the object until the transaction releases its lock on the object. Consequently, an implementor must typically balance the cost of pessimistic concurrency control (using locks) with the probability of conflict under optimistic (non-locking) concurrency control.
Transactional database systems can operate on a wide variety of data structures. Queues are a type of data structure that is sometimes used in database systems to model real world applications or environments having serial or sequential characteristics. A queue is a linear list for which all insertions are made at one end of the list and all deletions are made at the other. Queues are sometimes referred to as first-in-first-out (FIFO) lists. An example of an application or environment with serial or sequential characteristics is a manufacturing facility or factory in which products undergo successive manufacturing operations (e.g., the products move or flow from one work station to another or undergo one process after another).
In this type of application, typically one or more users, referred to as producers, add objects to a database queue and another user, referred to as a consumer, deletes objects from the queue. The producers are production units or processes that precede the consumer production unit or process. An addition to the queue represents addition of a product to the queue of objects to be acted upon by the consumer production unit or process. A deletion from the queue represents deletion of a product from the queue of objects to be acted upon by the consumer production unit or process. Deletion occurs, for example, when the consumer production unit or process receives the next product item on which to perform an operation. When it finishes its operation, the consumer production unit or process then adds the product to the queue of a subsequent production unit or process and passes the product to the subsequent unit or process. The subsequent production unit or process then becomes the consumer and the former consumer becomes the producer.
In accordance with the present invention, a queue data structure is stored on a computer-readable medium to represent a queue or list. The data structure includes a head pointer that points to the most recent list element to have been removed from the queue, and a tail pointer that points to the most recently added element in the queue. The head pointer and tail pointer are implemented as separate objects to avoid write/write conflicts.
A characteristic of this queue data structure is that neither the head pointer nor the tail pointer is NULL when the queue is empty. Adding an element to the queue modifies two objects: the tail pointer and the element previously referenced by the tail pointer. Removing an element from the queue modifies the head pointer, but not the tail pointer. As a result, adding and removal operations involve updates of non-intersecting sets of objects. This allows one user to add an element and another user to remove an element concurrently, without incurring a transaction conflict that can arise in prior art queue data structures without data locks or synchronization mechanisms. This is achieved by changing the definition of the data structure and the operations on it so that an operation that adds an element to the queue does not write the same object as an operation that removes an element from the queue.
The primary case of having concurrent modifications of the same object occurs when the queue is empty. Transaction conflicts are avoided by preventing the head pointer and the tail pointer from being NULL when the queue is empty or, conversely, by maintaining the most recently removed element in the queue even when it is empty. In one implementation, the present invention solves the problem of how to efficiently implement a queue in a transaction environment in which one user adds items to a queue (the producer) while another user concurrently removes or deletes items from the queue (the consumer) without using locking or other serialization mechanisms. The present invention may also be applied to shared memory architectures, as well as to other database systems that model queue behavior, such as relational databases.
Additional advantages of the present invention will be apparent from the detailed description of the preferred embodiment thereof, which proceeds with reference to the accompanying drawings.


REFERENCES:
patent: 5689693 (1997-11-01), White
patent: 5996067 (1999-11-01), White
patent: 6145061 (2000-11-01), Garcia et al.
Herlihy, M. “Apologizing versus Asking Permission: Optimistic Concurrency Control for Abstract Data Types”, ACM Transactions on Database Systems, 15(1), Mar. 1990.
Schwarz, P., and A. Spector. “Synchronizing Shared Absract Types”, ACM Transactions on Computing Systems 13(1), Aug. 1984.
Weihl, W.E. “Local Atomicity Properties: Modular Concurrency Control For Abstract Data Types,” ACM Transactions on Programming Languages and Systems, 11(2), Apr. 1992.
Almarode, J. and Bertl, R. “Reduced Conflict Objects”, Journal Of Object Oriented Programming pp. 40 Jan. 1998.
D. Knuth, The Art of Computer Programming, Addison-Wesley Publ. Co., Reading, Mass., 234-238, 1997.

Affiliated with

Also associated with

Rating

Object queues with concurrent updating does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Object queues with concurrent updating, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Object queues with concurrent updating will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2870351