Patent
1996-11-01
1998-03-10
Kim, Matthew M.
395474, 395486, G06F 930, G06F 1212
Patent
active
057272093
ABSTRACT:
A substantially zero overhead mutual-exclusion apparatus and method (90, 120) is provided that allows concurrent reading and updating data while maintaining data coherency. That is, a data reading process executes the same sequence of instructions that would be executed if the data were never updated. Rather than depending exclusively on overhead-imposing locks, this mutual-exclusion mechanism tracks an execution history (138) of a thread (16, 112) to determine safe times for processing a current generation (108, 130, 131) of data updates while a next generation (110, 132, 133) of data updates is concurrently being saved. A thread is any locus of control, such as a processor. A summary of thread activity (106, 122) tracks which threads have passed through a quiescent state after the current generation of updates was started. When the last thread related to the current generation passes through a quiescent state, the summary of thread activity signals a callback processor (104, 124) that it is safe to end the current generation of updates. The callback processor then processes and erases all updates in the current generation. The next generation of updates then becomes the current generation of updates. The callback processor restarts the summary of thread activity and initiates a new next generation of updates. All data-updating threads pass through a quiescent state between the time they attempt to update data and the time the data are actually updated.
REFERENCES:
patent: 4747043 (1988-05-01), Rodman
patent: 4965719 (1990-10-01), Shoens et al.
patent: 5027316 (1991-06-01), Frantz et al.
patent: 5185861 (1993-02-01), Valencia
patent: 5214766 (1993-05-01), Liu
patent: 5226143 (1993-07-01), Baird et al.
patent: 5241664 (1993-08-01), Ohba et al.
patent: 5249283 (1993-09-01), Boland
patent: 5261053 (1993-11-01), Valencia
patent: 5303362 (1994-04-01), Butts, Jr. et al.
patent: 5428761 (1995-06-01), Herlihy et al.
patent: 5469549 (1995-11-01), Simpson et al.
Cache Coherence Protocols: Evaluation Using a Multiprocessor Simulation Model, James Archibald and Jean-Loup Baer, ACM Transactions on Computer Systems, vol. 4, No. 4, pp. 273-298, Nov., 1986.
An Economical Solution to the Cache Coherence Problem, James Archibald and Jean-Loup Baer, Proc. 11th Annual Symposium on Computer Architecture, IEEE, pp. 355-362, 1984.
A New Solution to Coherence Problems in Multicache Systems, Lucien M. Censier and Paul Feautrier, IEEE Transactions on Computers, vol. C-27, No. 12, pp. 1112-1118, Dec. 1978.
Computer Architecture and Design, A.J. van de Goor, Addison-Wesley Publishers Limited, Workingham, England, pp. 473-506, 1989.
Symmetry Technical Summary, Sequent Computer Systems, Inc., Beaverton, Oregon, pp. 1.18, 1.19, 2.8, 2.9, 5.2-5.4, and A.4-A9, 1987.
The Design of the UNIX Operating System, Maurice J. Bach, Prentice-Hall, Inc., Englewood Cliffs, New Jersey, pp. 30, 31, 77, 96-103, and 391-410, 1986.
McKenney Paul E.
Slingwine John D.
Kim Matthew M.
Sequent Computer Systems, Inc.
LandOfFree
Apparatus and method for achieving reduced overhead mutual-exclu does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Apparatus and method for achieving reduced overhead mutual-exclu, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Apparatus and method for achieving reduced overhead mutual-exclu will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-149863