Efficient non-blocking k-compare-single-swap operation

Details Efficient non-blocking k-compare-single-swap operation Efficient non-blocking k-compare-single-swap operation

2007-11-06

2007-11-06

Portka, Gary (Department: 2188)

Electrical computers and digital processing systems: memory

Storage accessing and control

Shared memory area

C711S159000, C711S162000, C707S793000

Reexamination Certificate

active

10670495

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: 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), Srinivas et al.
patent: 6826757 (2004-11-01), Steele, Jr. 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: 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: 0 366 585 (1990-05-01), None
patent: 0 466 339 (1992-01-01), None
patent: WO 86/00434 (1986-01-01), None
patent: WO 01/53942 (2001-07-01), None
patent: WO 01/53943 (2001-07-01), None
patent: WO 01/80015 (2001-10-01), None
patent: WO 01/82057 (2001-11-01), None
patent: WO 03/060705 (2003-07-01), None
patent: WO 03/060715 (2003-07-01), None
U.S. Appl. No. 09/547,288, filed Apr. 11, 2000 and naming as inventor(s) Shavit et al.
U.S. Appl. No. 09/547,290, filed Apr. 11. 2000 and naming as inventor(s) Shavit et al.
U.S. Appl. No. 09/710,218, filed Nov. 10, 2000 and naming as inventor(s) Harris, Timothy.
U.S. Appl. No. 09/837,671, filed Apr. 18, 2001 and naming as inventor(s) Detlefs et al.
Herlihy, M.P. et al., “Linearizability: A Correctness Condition For Con-Current Objects,”ACM Transactions On Programming Languages and Systems, 12(3):463-492, Jul. 1990.
Herlihy, M.P., “Wait-Free Synchronization,”ACM Transactions On Programming Languages and Systems, 11(1):124-149, Jan. 1991.
Massalin, H., et al., “A Lock-Free Multiprocessor OS Kemel,” Technical Report TR CUCS-005-9, Columbia University, New York, NY, 1991, 21 pages.
Massalin, Henry, “Synthesis: An Efficient Implementation of Fundamental Operating System Services,” Dissertation submitted in partial fulfillment of the requirements for the Degree of Doctor of Philosophy in the Graduate School of Arts and Sciences, Columbia University, New York, NY, online, 158 pages, 1992 [retrieved from the Internet on Jul. 13, 2001: URL:ftp://ftp.cs.columbia.edu/reports/reports-1992/cucs-039-92.ps.gz].
Bershad, B. N., “Practical Considerations For Non-Blocking Concurrent Objects,”Proceedings 13th IEEE International Conference on Distributed Computing Systems, pp. 264-273, IEEE Computer Society Press, Washington, D.C., 1993.
Herlihy, M., “A Methodology For Implementing Highly Concurrent Data Objects,”ACM Transactions on Programming Languages and Systems, 15(5):745-770, Nov. 1993.
Attiya, Hagit, et al., “Are Wait-Free Algorithms Fast?”Journal of the ACM, 41(4):725-763, Jul. 1994.
Lamarca, A., “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, New York, NY, 1994.
Michael, Maged M. et al., “Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms,” Proceedings of PODC, pp. 267-275, May 1996.
Attiya, H., et al., “Universal Operations: Unary versus Binary,”Proceedings of the 15th Annual ACM Symposium on Principles of Distributed Computing, pp. 223-232, ACM Press, New York, NY, 1996.
Greenwald, M. B., 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, Berkeley, CA, 1996.
Afek, Y., et al., “Disentangling Multi-Object Operations,”Proceedings of the 16th Annual ACM Symposium on Principles of Distributed Computing, pp. 111-120, Aug. 1997. Santa Barbara, CA.
Arora, N. S., et al., “Thread Scheduling For Multiprogrammed Multiprocessors,”Proceedings of the 10th Annual ACM Symposium on Parallel Algorithms and Architectures, pp. 119-129, ACM Press, New York, NY, 1998.
Attiya, Hagit, et al., “Atomic Snapshots In O(n log n)Operations,”SIAM Journal in Computing, 27(2):319-340, Apr. 1998.
Greenwald, M., “Non-Blocking Synchronization and System Design,” PhD thesis, Stanford University Technical Report STAN-CS-TR-99-1624, Palo Alto, CA, Aug. 1999, 241 pages.
Agesen, Ole, 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, New York, NY, ISBN: 1-58113-185-2, 2000.
Detlefs, David L., et al., “Even Better DCAS-Based Concurrent Deques,”Lecture Notes in Computer Science, vol. 1914, pp. 59-73, Springer-Verlag, Berlin, Germany, ISBN: 3-540-41143-7, 2000.
Afek, Yehuda, “Atomic Snapshots of Shared Memory,” Journal of the ACM, vol. 40, No. 4, pp. 873-890, 1993.
Afek, Yehuda et al., “Long-Lived Renaming Made Adaptive,” Proceedings of the 18th Annual ACM Symposium on Principles of Distributed Computing, pp. 91-103, ACM Press, New York, NY, 1999.
Agesen, Ole at el., “An Efficient Meta-Lock for Implementing Ubiquitous Synchronization,” ACM SIGPLAN Notices, vol. 34, No. 10, pp. 207-222, Oct. 1999.
Agesen, Ole, et al.: “DCAS-Based Concurrent Deques,”Theory of Computing Systems, vol. 35, No. 3, pp. 349-386, May 2002.
Anderson, James H. et al., “Universal Constructions for Large Objects,”IEEE Transactions on Parallel and Distributed Systems, vol. 10, No. 12, pp. 1317-1332, 1999.
Attiya, Hagit et al., “An Adaptive Collect Algorithm with Applications,”Distributed Computing, vol. 15, No. 2, pp. 87-96, Apr. 2002.
Barnes, G., “A Method for Implementing Lock-Free Shared Data Structures,”Proceedings of the 5th ACM Symposium on Parallel Algorithms and Architectures, pp. 261-270, ACM Press, New York, NY 1993.
Detlefs, David L. et al., “Lock-Free Reference Counting,”Proc. 20th Annual ACM Symposium on Principles of Distributed Computing, pp. 190-199, ACM Press, New York, NY, 2001.
Herlihy, M., et al., “Transactional Memory: Architectural Support for Lock-Free Data Structures,”Proc. 20th International Symposium in Computer Architecture, pp. 289-200, IEEE Computer Society, Washington, D.C., 1993.
Herlihy, Maurice, “Dynamic-Sized Lockfree Data Structures,” Sun Microsystems Technical Report SMLI TR-2002-112, Jun. 2002.
Herlihy, Maurice et al., “The Repeat Offender Problem: A Mechanism for Supporting Dynamic-Sized

Affiliated with

Also associated with

Rating

Efficient non-blocking k-compare-single-swap operation does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Efficient non-blocking k-compare-single-swap operation, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Efficient non-blocking k-compare-single-swap operation will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3833340