Electrical computers and digital data processing systems: input/ – Access locking
Reexamination Certificate
1999-12-15
2003-04-08
Ray, Gopal C. (Department: 2181)
Electrical computers and digital data processing systems: input/
Access locking
C710S108000, C714S015000
Reexamination Certificate
active
06546443
ABSTRACT:
A portion of the disclosure of this patent document is submitted on one compact disc and is hereby incorporated herein by reference. The compact disc contains exactly one file, created on Jul. 2, 2002, which is named “source-txt” and is 75,040 bytes in size. An additional, identical compact disc is also included, for a total of two compact discs.
TECHNICAL FIELD
The invention relates to providing synchronization services for maintaining integrity of data accessed concurrently by both readers and writers.
BACKGROUND OF THE INVENTION
In many information processing applications, multiple executing entities attempt to access data concurrently. For example, in a database program, multiple users may attempt to access the same database tables, records, and fields at the same time. Common examples of such database programs include software for processing class registrations at a university, travel reservations, money transfers at a bank, and sales at a retail business. In these examples, the programs may update databases of class schedules, hotel reservations, account balances, product shipments, payments, or inventory for actions initiated by the individual users. Sometimes a single program executes multiple threads accessing the same data concurrently. For example, one thread may watch for changes in data made by another thread.
However, data corruption may result when concurrent data access is uncontrolled. For example, consider the following scenario in which two computers, A and B, both attempt to remove one item from inventory by subtracting one from an inventory field in a database:
1. The inventory field value is “2”
2. Computer A reads the inventory field (“2”) to its local storage
3. Computer B reads the inventory field (“2”) to its local storage
4. Computer A subtracts “1” from its local storage, yielding “1”
5. Computer B subtracts “1” from its local storage, yielding “1”
6. Computer A writes its local storage (“1”) to the inventory field
7. Computer B writes its local storage (“1”) to the inventory field
8. The inventory field value is “1”
One would expect the value “2” to become “0” after two computers attempt to subtract “1” from it, but in the illustrated scenario, the result is instead “1.” Since the algorithm failed to take concurrency into account, the database has been corrupted. Such concurrency problems can arise whenever multiple executing entities (e.g., processes, tasks, threads, processors, or programming objects) access the same data.
Programmers have advanced a variety of approaches to address problems arising from concurrent processing. On a general level, many programming systems provide synchronization services to provide certain guarantees even in the face of concurrency. For example, some programming environments support simple synchronization mechanisms such as semaphores, locks, critical sections, and mutual exclusion objects (mutexes); each of these mechanisms controls concurrent access to a resource.
One particular concurrency scenario poses a special set of problems: sharing a resource between readers and writers. Since the readers do not modify the resource, it is commonly acceptable (and generally more efficient) to allow more than one of the readers to access the resource concurrently because there is no chance of data corruption. However, a writer is not permitted to write to (i.e., modify) the resource concurrently while another reader or writer is accessing the resource. Otherwise, the data may become corrupted as shown in the above example.
One approach to solving the reader/writer problem is to employ a synchronization mechanism called a semaphore. A semaphore is a value that multiple processes can check and change simultaneously, and logic associated with the semaphore guarantees the semaphore will not be corrupted. So, for example, the semaphore can be set to on (i.e., 1) or off (i.e., 0) to indicate whether or not a process is accessing the protected resource. Logic associated with the semaphore protects the semaphore from corruption by guaranteeing that two processes cannot simultaneously set the semaphore to on. Thus, a software developer can include logic referencing the semaphore in programming code. For example, a programmer could include logic that waits until a semaphore is off (i.e., 0) before writing to a resource. Thus, a later-in-time process must wait until a first-in-time process is finished with the resource; the later-in-time process then updates the semaphore accordingly to prevent others from writing to the resource.
Specifically, in the reader/writer context, a pair of semaphores can be used for each protected resource to track how many readers access the resource and whether there is a writer accessing the resource. Readers check the “whether there is a writer” semaphore before proceeding, and writers check both the “whether there is a writer” and “how many readers” semaphores before proceeding. However, the semaphore approach has several drawbacks.
First, in a system with many resources to protect, maintaining a pair of semaphores for each of the protected resources may consume excessive system resources. For example, in large database systems, it may require considerable computing power to administer the semaphores for the large number of database fields and tables in the system.
Second, the semaphore approach can lead to a problem called deadlock. Deadlock occurs when two or more processes (or threads) vie for two or more protected resources. For example, consider process A and process B, both of which require writing to fields Y and Z to update a database. Deadlock occurs under the following scenario:
1. Process A updates a semaphore protecting field Y to indicate Y is unavailable to other processes
2. Process B updates a semaphore protecting field Z to indicate Z is unavailable to other processes
3. Process A examines the semaphore protecting field Z and determines Z is unavailable (as noted by B), so process A waits for process B to release field Z
4. Process B examines the semaphore protecting field Y and determines Y is unavailable (as noted by A), so process B waits for process A to release field Y
5. Both processes wait forever
Although there are ways of dealing with the deadlock problem, such as conventional deadlock detection and conventional deadlock avoidance, again, considerable computing power is typically required to implement such solutions. Also, none of the solutions completely solves the problem. In light of the difficulty of solving the deadlock problem and the relative rarity of deadlock conditions, some systems ignore the deadlock problem altogether. However, such an approach can lead to a subtle software defect that is difficult to detect and debug.
Thus, an efficient synchronization mechanism for addressing the reader/writer scenario is needed, and a mechanism for avoiding the deadlock problem is needed.
SUMMARY OF THE INVENTION
The invention includes a method and system for providing reader/writer synchronization services using interlocked operations. Various features provided by the synchronization services lead to better use of resources and improved performance. The synchronization services manage the details of lock operation, freeing programmers from devoting time and resources to develop their own synchronization logic.
Data structures for implementing the reader/writer services can be maintained using an interlocked operation (e.g., an interlocked compare and exchange operation). Such an implementation is sometimes called “lockless” since logic to lock the data structures is not necessary. In addition, by maintaining some data structure elements in storage local to a thread, the lock services can more efficiently access lock state information.
In one arrangement, the system uses an execution suspension mechanism known as an event. The arrangement can thus be implemented on a variety of execution environments that support events.
In a just-in-time event creation feature, the system avoids excessive resource consumption by waiting until there is contention for a lock before creating an
Cutler David N.
Kakivaya Gopala Krishna R.
Lyon James M.
Klarquist & Sparkman, LLP
Microsoft Corporation
Ray Gopal C.
LandOfFree
Concurrency-safe reader-writer lock with time out support does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Concurrency-safe reader-writer lock with time out support, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Concurrency-safe reader-writer lock with time out support will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3025144