Electrical computers and digital processing systems: memory – Storage accessing and control – Shared memory area
Reexamination Certificate
2011-01-11
2011-01-11
Thai, Tuan V. (Department: 2185)
Electrical computers and digital processing systems: memory
Storage accessing and control
Shared memory area
C711S100000, C711S154000
Reexamination Certificate
active
07870344
ABSTRACT:
The design of nonblocking linked data structures using single-location synchronization primitives such as compare-and-swap (CAS) is a complex affair that often requires severe restrictions on the way pointers are used. One way to address this problem is to provide stronger synchronization operations, for example, ones that atomically modify one memory location while simultaneously verifying the contents of others. We provide a simple and highly efficient nonblocking implementation of such an operation: an atomic k-word-compare single-swap operation (KCSS). Our implementation is obstruction-free. As a result, it is highly efficient in the uncontended case and relies on contention management mechanisms in the contended cases. It allows linked data structure manipulation without the complexity and restrictions of other solutions. Additionally, as a building block of some implementations of our techniques, we have developed the first nonblocking software implementation of load-linked/store-conditional that does not severely restrict word size.
REFERENCES:
patent: 4584640 (1986-04-01), MacGregor et al.
patent: 4847754 (1989-07-01), Obermarck et al.
patent: 5224215 (1993-06-01), Disbrow
patent: 5428761 (1995-06-01), Herlihy et al.
patent: 6128710 (2000-10-01), Greenspan et al.
patent: 6144965 (2000-11-01), Olivier
patent: 6178423 (2001-01-01), Douceur et al.
patent: 6223335 (2001-04-01), Cartwright et al.
patent: 6360219 (2002-03-01), Bretl et al.
patent: 6360220 (2002-03-01), Forin
patent: 6366932 (2002-04-01), Christenson
patent: 6581063 (2003-06-01), Kirkman
patent: 6651146 (2003-11-01), Srinicas et al.
patent: 6826757 (2004-11-01), Steele, Jr. et al.
patent: 7293143 (2007-11-01), Shavit et al.
patent: 2001/0047361 (2001-11-01), Martin et al.
patent: 2003/0065892 (2003-04-01), Bonola
patent: 2003/0105943 (2003-06-01), Yeh et al.
patent: 2003/0140085 (2003-07-01), Moir et al.
patent: 2003/0174572 (2003-09-01), Moir et al.
patent: 2003/0182462 (2003-09-01), Moir et al.
patent: 2003/0182465 (2003-09-01), Moir et al.
patent: 2003/0217115 (2003-11-01), Rowlands
patent: 2004/0015510 (2004-01-01), Moir et al.
patent: 2004/0015642 (2004-01-01), Moir et al.
patent: 2004/0034673 (2004-02-01), Moir et al.
patent: 2004/0153687 (2004-08-01), Moir et al.
patent: 2006/0218556 (2006-09-01), Nemirovsky et al.
patent: 0366585 (1990-05-01), None
patent: 0466339 (1992-01-01), None
patent: 86/00434 (1986-01-01), None
patent: 01/53942 (2001-07-01), None
patent: 01/53943 (2001-07-01), None
patent: 01/80015 (2001-10-01), None
patent: 01/82057 (2001-11-01), None
patent: 03/060705 (2003-07-01), None
patent: 03/060715 (2003-07-01), None
Agesen, et al., “DCAS-Based Concurrent Deques,” SPAA 2000. Proceedings of the 12th Annual ACM Symposium on Parallel Algorithms and Architectures, pp. 137, 146, ACM Press, ISBN: 1-58113-185-2, 2000.
Detlefs, et al., “Even Better DCAS-Based Concurrent Deques,” Lecture Notes in Computer Science, vol. 1914, pp. 59-73, Springer-Verlag, Berlin, German, ISBN: 3-540-41143-7, 2000.
Herlihy, et al., “Linearizability: A Correctness Condition For Con-Current Objects,” ACM Transactions on Programming Languages and Systems, 12(3): 463-492, Jul. 1990.
Herlihy, “Wait-Free Synchronization,” ACM Transactions on Programming Languages and Systems, 11(1): 124-149, Jan. 1991.
Massalin, et al., “A Lock-Free Multiprocessor OS Kernel,” Technical Report TR CUCS-005-9, Columbia Univ., New York, NY, 1991, 21 pages.
Massalin, “Synthesis: An Efficient Implementation of Fundamental Operating System Services,” 158 pages, 1992.
Bershad, “Practical Considerations for Highly Concurrent Data Objects,” Proceedings 13th IEEE International Conference on Distributed Computing Systems, pp. 264-273, IEEE Computer Society Press, 1993.
Herlihy, “A Methodology for Implementing Highly Concurrent Data Objects,” ACM Transactions on Programming Languages and Systems, 15(5):745-770, Nov. 1993.
Attiya, et al., “Are Wait-Free Algorithms Fast?,” Journal of the ACM, 41(4):725-763, Jul. 1994.
Lamarca, “A Performance Evaluation of Lock-Free Synchronization Protocols,” Proceedings of the 13th Annual ACM Symposium on Principles of Distributed Computing, pp. 130-140, ACM Press, 1994.
Michael, et al., “Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms,” Proceedings of PODC, pp. 267-275, May 1996.
Attiya, et al., “Universal Operations: Unary Versus Binary,” Proceedings of the 15th Annual ACM Symposium on Principles of Distributed Computing, pp. 223-232, ACM Press, 1996.
Greenwald, et al., “The Synergy Between Non-Blocking Synchronization and Operating System Structure,” Proceedings of the 2nd Symposium on Operating Systems Design and Implementation, pp. 123-136, Usenix Association, 1996.
Afek, et al., “Disentangling Multi-Object Operations,” Proceedings of the 16th Annual ACM Symposium on Principles of Distributed Computing, pp. 111-120, Aug. 1997.
Arora, et al., “Thread Scheduling for Multiprogrammed Multiprocessors,” Proceedings of the 10th Annual ACM Symposium on Parallel Algorithms and Architecture, pp. 119-129, ACM Press, 1998.
Attiya, et al., “Atomic Snapshots in O(n log n) Operations,” SIAM Journal on Computing, 27(2):319-340, Apr. 1998.
Greenwald, “Non-Blocking Synchronization and System Design,” PhD Thesis, Technical Report STAN-CS-TR-99-1624, Aug. 1999, 241 pages.
Turek, John et al., “Locking without Blocking: Making Lock Based Concurrent Data Structure Algorithms Nonblocking”, 11th ACM SIGACT—SIGMOND-SIGART Symposium on Principles of Database Systems, 1992.
Afek, Yehuda et al., “Long-Lived Renaming made Adaptive”, 18th Annual ACM Symposium on Principles of Distributed Computing, pp. 91-104, 1999.
Agesen, Ole et al., “An Efficient Meta-Lock for Implementing Ubiquitous Synchronization,” ACM SIGPLAN Notices, vol. 34, No. 10, pp. 207-222, Oct. 1999.
Attiya Hagit et al., “An Adaptive Collect Algorithm with Applications”, Dept. of Computing Science, The Technion, Israel, May 10, 2001.
Barnes, Greg, “A Method for Implementing Lock-Free Shared Data Structures”, 5th Annual ACM Symposium on Parallel Algorithms and Architectures, pp. 261-270, 1993.
Herlihy, Maurice, “Dynamic-Sized Lockfree Data Structures”, Sun Microsysems Technical Report SMLI TR-2002-112, Jun. 2002.
Herlihy, Maurice et al., “The Repeat Offender Problem: A Mechanism for Supporting Dynamic-Sized Lock-Free Data Structures”, Sun Microsystems Technical Report SMLI TR-2002-112, Jun. 2002.
Herlihy, Maurice et al., “Obstruction-Free Synchronization: Double-Ended Queues as an Example” 23rd International Conference on Distributed computing, May 2003.
Israeli, Amos et al., “Disjoint-Access-Parallel Implementations of Strong Shared Memory Primitives”, 13th Annual ACM Symposium on Principles of Distributed Computing, pp. 151-160, 1994.
More, et al., “Wait-Free Algorithms for Fast, Long-Lived Renaming,” Science of Computer Programming, vol. 25, No. 1, pp. 1-39, Aug. 1995.
More, “Practical Implementation of NOn-Blocking Synchronization Primitives,” Proceedings of the 16th Annual Symposium on Principles of Distributed Computing, pp. 219-228, ACM Press, 1997.
More, “Transparent Support for Wait-Free Transactions,” Proceedings of the 11th International Workshop on Distributed Algorithms, pp. 305-319, Springer-Verlag, 1997.
More, “Laziness Pays! Using Lazy Synchronization Mechanisms to Improve Non-Blocking Constructions,” Proc. 19th Annual ACM Symposium on Principles of Distributed Computing, pp. 61-70, ACM Press, 2000.
Shavit, et al., “Software Transactional Memory,” Distributed Computing, vol. 10, No. 2, pp. 99-116, Feb. 1997.
Shavit, et al., “Combining Funnels: A New Twist on an Old Tale . . . ,” Proce
Luchangco Victor M.
Moir Mark S.
Shavit Nir N.
Kowert Robert C.
Meyertons Hood Kivlin Kowert & Goetzel P.C.
Oracle America Inc.
Thai Tuan V.
LandOfFree
Method and apparatus for emulating... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for emulating..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for emulating... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2657402