Electrical computers and digital processing systems: memory – Storage accessing and control – Shared memory area
Reexamination Certificate
2004-10-14
2008-08-12
Bragdon, Reginald G. (Department: 2189)
Electrical computers and digital processing systems: memory
Storage accessing and control
Shared memory area
C711S167000, C709S213000
Reexamination Certificate
active
07412572
ABSTRACT:
A multiple-location read, single-location write operation is implemented using transient blocking synchronization support. The multiple-location read, single-location write operation involves first acquiring transient ownership of a memory location to be modified and then acquiring transient ownership of at least one other memory location, the contents of which are read and used to modify the memory location first acquired.
REFERENCES:
patent: 4561051 (1985-12-01), Rodman et al.
patent: 4858116 (1989-08-01), Gillett et al.
patent: 5301290 (1994-04-01), Tetzlaff et al.
patent: 5428761 (1995-06-01), Herlihy et al.
patent: 5875342 (1999-02-01), Temple
patent: 5892955 (1999-04-01), Ofer
patent: 5991845 (1999-11-01), Bohannon et al.
patent: 6370625 (2002-04-01), Carmean et al.
patent: 6745274 (2004-06-01), Snyder et al.
patent: 6782452 (2004-08-01), Williams, III
patent: 6958507 (2005-10-01), Atwood et al.
patent: 2002/0078307 (2002-06-01), Zahir
patent: 2002/0188590 (2002-12-01), Curran et al.
patent: 2004/0015642 (2004-01-01), Moir et al.
patent: 2005/0038964 (2005-02-01), Hooper et al.
patent: 2006/0036850 (2006-02-01), Enokida
Maurice Herlihy, A Methodology for Implementing Highly Concurrent Data Objects, ACM Transactions on Programming Languages and Systems, vol. 15, No. 5, Nov. 1993, pp. 745-770.
Nir Shavit, et al., Elimination Trees and The Contraction of Pools and Stacks, 7th Annual Symposium on Parallel Algorithms and Architectures (SPAA), Feb. 28, 1996, 30 pages.
Thomas E. Anderson, The Performance of Spin Lock Alternatives for Shared-Memory Multiprocessors, IEEE Transactions on Parallel and Distributed Systems, vol. 1, No. 1, Jan. 1990, pp. 6-16.
Maged M. Michael. Safe Memory Reclamation for Dynamic Lock-Free Objects Using Atomic Reads and Writes. PODC 2002 Jul. 21-24, 2002.
John M. Mellor-Crummey, et al. Algorithms for Scalable Synchronization on Shared-Memory Multiprocessors. ACM Transactions on Computer Systems, vol. 9, No. 1, Feb. 1991, pp. 21-65.
Maged M. Michael, et al. Nonblocking Algorithms and Preemption-Safe Locking on Multiprogrammed Shred Memory Multiprocessors. Journal of Prallel and Distributed Computing 51, Article No. PC981446, 1998, pp. 1-26.
Maurice P. Herlihy, et al. Linearizability: A Correctness Condition for Concurrent Objects. ACM Transactions on programming Languages and Systems, vol. 12, No. 3, Jul. 1990, pp. 463-492.
Maurice Herlihy, et al. The Repeat Offender Problem: A Mechanism for Supporting Dynamic-Sized Lock-Free Data Structures. Jul. 2002, 15 pages.
Maurice Herlihy, et al. Scalable Concurrent Counting. In the Proceedings of the 3rd Annual ACM Symposium on Parallel Algorithms and Architectures, Jul. 1992, pp. 1-31.
Nir Shavit, et al. A Steady State Analysis of Diffracting Trees. Jul. 15, 1997, pp. 1-26.
Nir Shavit, et al. Diffracting Trees. In the Proceedings of the Annual Symposium on Parallel Algorithms and Architectures (SPAA), Jun. 1994, p. 0-49.
Nir Shavit, et al. Combining Funnels: A Dynamic Approach To Software Combining. Principals of Distributed Computing (PODC98). Jul. 6, 1999, pp. 1-30.
Beng-Hong Lim, et al. Waiting Algorithms for Synchronization in Large-Scale Multiprocessors. ACM Transactions on Computer Systems, vol. 11, No. 3, Aug. 1993, pp. 1-39.
Maged M. Michael, et al. Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms. Feb. 1996, 8 pages.
Ravi Rajwar, et al. Speculative Lock Elision: Enabling Highly Concurrent Multithreaded Execution. In the proceedings of the 34th International Symposium on Microarchitechture (MICRO), Dec. 3-5, 2001, 12 pages.
John D. Valois. Implementing Lock-Free Queues. In proceedings of the Seventh International Conference on Parallel and Distributed Computing Systems, Las Vegas, NV, Oct. 1994, pp. 1-9.
Sundeep Prakash, et al. Non-Blocking Algorithms for Concurrent Data Structures. Jul. 1, 1991, pp. 1-40.
John M. Mellor-Crummey, et al. Algorithms for Scalable Synchronization on Shared-Memory Multiprocessors. Jan. 1991, 42 pages.
Peter Magnusson, et al. Queue Locks on Cache Coherent Multiprocessors. 1994, 7 pages.
Travis S. Craig. Building FIFO and Priority-Queuing Spin Locks from Atomic Swap. Feb. 1, 1993, pp. 1-29.
Yehuda Afek, et al. Atomic Snapshots of Shred Memory. pp. 1-21. A Preliminary version of this paper appeared In theProceedings of the 9th Annual ACM Symposium on Principles of Distributed Computing, (Quebec City, Quebec, August) ACM, New York, 1990, pp. 1-14.
Ole Agesen, et al. DCAS-Based Concurrent Deques. Jul. 2000, 10 pages.
Maurice Herlihy. Wait-Free Synchronization. ACM Transactions on Programming Languages and Systems, vol. 11, No. 1, Jan. 1991, pp. 124-149.
Mark Moir. Practical Implementations of Non- Blocking Synchronization Primitives. Aug. 1997, 10 pages.
Maurice Herlihy, et al. Obstruction-Free Synchronization: Double-Ended Queues as an Example. 2003, 8 pages.
Gray, et al.; “Leases: An Efficient Fault-Tolerant Mechanism for Distributed File Cache Consistency”; ACM pp. 202-204, 1989.
Handy, J., the Cache Memory book, 2nd edition, 1998, pp. 29-31, 67, 138-141, 146-147.
Shalev Ori
Shavit Nir N.
Bragdon Reginald G.
Dinh Ngoc V
Osha-Liang LLP
Sun Microsystems Inc.
LandOfFree
Multiple-location read, single-location write operations... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Multiple-location read, single-location write operations..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Multiple-location read, single-location write operations... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-4006628