Electrical computers and digital data processing systems: input/ – Input/output data processing – Input/output data buffering
Reexamination Certificate
1999-02-02
2001-10-16
Shin, Christopher B. (Department: 2182)
Electrical computers and digital data processing systems: input/
Input/output data processing
Input/output data buffering
C711S110000, C370S412000
Reexamination Certificate
active
06304924
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention generally relates to efficient support of synchronization in parallel processing and, more particularly, to methods for building instances of two novel data structures that are optimal in that they permit simultaneous access to multiple readers and one writer without using any synchronization constructs such as locks and/or any special instructions.
2. Background Description
A concurrent data structure is highly concurrent if it permits more than one request to enter and access it simultaneously. Concurrent data structures that are not highly concurrent commonly require the use of a lock at the top of the data structure to serialize access to the data structure. Locking out simultaneous access to a data structure means that excepting one, each of multiple simultaneous access requests has to either wait actively for its access turn to come, or it has to wait passively for its turn to come. In active waiting, a request wastes computation cycles by polling or spinning on some condition till the condition becomes true. In passive waiting, a request tries to reduce computation wastage by say switching to useful computation before returning to attempt data-structure access, or by yielding or context switching the processor to some other computational thread or process. The trade off between active waiting and passive waiting lies between any shifts or context-switches overhead of the latter and active-computation wastage of the former. Independent of any cost incurred by a request in waiting for its turn is the cost always incurred by the request in at least acquiring and releasing the lock associated with the data structure. The overhead of lock usage is significant, especially when multiple, simultaneous attempts at data-structure access make the lock a hot spot of contention. The costs of active waiting, passive waiting, and lock manipulation are all a part of the synchronization cost incurred by a request in accessing a concurrent data structure. Providing high concurrency in data structures as opposed to serialized access is motivated by the goal of reducing synchronization cost in parallel computation. Success in achieving high concurrency has to be measured in terms of (any) gains made in reducing overall synchronization cost, which includes waiting cost, loss of parallel-computation opportunity in data structure access, and serialization cost that includes lock and/or other synchronization-primitive overhead.
It is straightforward to provide highly-concurrent versions of purely read-only data structures. Since such a data structure does not change, it is not necessary to provide a serialization of changes to the data structure. Thus, it does not matter how many requests access the data structure at the same time. Requests accessing the data structure do not have to acquire or release any locks or use other synchronization primitives in order to access the data structure. The introduction of mutability to a data structure changes the situation completely. Unintended and possibly ill-defined mutations and readings of the data structure by interacting concurrent requests, each of which may be behaving correctly if viewed in isolation, have to be ruled out. Taking the cue from the high concurrency of read-only data structures, a step towards making a highly-concurrent version of a mutable data structure is providing a multiple-reader-single-writer version of the data structure. At most, a multiple-reader-single-writer version of a data structure allows multiple readers and one writer to access the data structure at the same time. A multiple-reader-single-writer data structure can also restrict simultaneous access to either multiple readers at one time, or one writer alone at one time. A reader can be a pure reader, which means that it does not write any shared data at all, or it can be an impure reader, which means that it does some auxiliary shared-data writes for say bookkeeping purposes. A multiple-reader-single-writer structure basically supports a broadcast paradigm: One writer writes or broadcasts at one time and multiple readers receive the broadcast concurrently. Although the common multiple-reader-single-writer design often succeeds in increasing parallel access to a data structure, it does not necessarily succeed in reducing the synchronization overhead associated with that access. In fact, a multiple-reader-single-writer scheme can end up being abandoned due to an overall increase in synchronization cost due to increased overheads such as increased lock acquires and releases associated with it. See N. Carriero, “Implementation of Tuple Space Machines”,
Research Report
567, Yale University Department of Computer Science, December 1987 (also a 1987 Yale University Ph.D. Thesis).
SUMMARY OF THE INVENTION
It is therefore an object of the present invention to provide novel, highly-concurrent versions of a basic data structure, a constant-space queue, by providing two multiple-reader-single-writer versions of the data structure.
It is another object of the invention to provide, for each version, a method to build instances of the version so that the data structure instances are optimal in that they permit simultaneous access to multiple readers and one writer without using any synchronization constructs.
According to the invention, for each embodiment a first-in-first-out (FIFO) circular queue is utilized that provides increased parallel access along with an optimal lock and/or other synchronization-primitive overhead of zero lock/other primitive cost. Each version supports maximal multiple-read-single-write access by allowing both multiple readers and one writer to access inside it at the same time. The versions differ in the amount of queue memory that they can actually utilize in their operation. One version can make full use of all memory space that available in its queue, while the other version cannot make full use of all memory space that is available in its queue. The partial-space-utilizing version has the advantage that it is simple in terms of the bookkeeping effort (e.g., reader/writer pointers and manipulation) incurred by it. Prior work on providing highly-concurrent implementation of objects has often relied on the use of synchronization constructs such as locks, critical sections (A. Gottlieb, B. D. Lubachevsky and L. Rudolph, “Basic techniques for the efficient coordination of very large numbers of cooperating sequential processors”,
ACM Transactions on Programming Languages and Systems,
5(2):164-189, April 1983, and Pradeep Varma,
Compile-Time Analyses and Run-Time Support for a Higher Order, Distributed Data-Structures Based, Parallel Language
, University Microfilms International, Ann Arbor, Mich., 1995) and monitors, or on machine-specific special instructions such as replace&add (see Gottlieb et al., supra), fetch&add and swap (M. Herlihy and J. Wing, “Axioms for concurrent objects”, 14
th
ACM Symposium on Principles of Programming Languages
, pp. 13-26, January 1987), and universal primitive operations (Maurice Herlihy, “A Methodology for Implementing Highly Concurrent Data Objects”,
ACM Transactions on Programming Languages and Systems
, 15(5):745-770, November 1993).
In contrast, our structures rely on no synchronization constructs and/or special instructions. Our structures rely on atomicity of some reads and/or writes of simple integral values to memory that is shared, actually or by emulation, between concurrent threads/processes. Thus, our invention provides lock-free structures that are not tied to the existence of any specific primitive instructions on the machines, circuits, hardware, firmware, software and networks on which they can be built. In our structures, the waiting times of read and write requests are reduced: a reader waits primarily only when it has read all data in the queue and the writer has yet to write new data; a writer waits primarily only when it has no space left in the constant-space structure to write data into as some readers haven'
International Business Machines - Corporation
Kaufman Stephen C.
McGuireWoods LLP
Shin Christopher B.
LandOfFree
Two lock-free, constant-space, multiple-(impure)-reader,... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Two lock-free, constant-space, multiple-(impure)-reader,..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Two lock-free, constant-space, multiple-(impure)-reader,... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2572657