Space-adaptive lock-free queue using pointer-sized...

Details Space-adaptive lock-free queue using pointer-sized... Space-adaptive lock-free queue using pointer-sized...

2004-12-30

2009-08-18

Tsai, Sheng-Jen (Department: 2186)

Electrical computers and digital processing systems: memory

Storage accessing and control

Shared memory area

Reexamination Certificate

active

07577798

ABSTRACT:
Many conventional lock-free data structures exploit techniques that are possible only because state-of-the-art 64-bit processors are still running 32-bit operating systems and applications. As software catches up to hardware, “64-bit-clean” lock-free data structures, which cannot use such techniques, are needed. We present several 64-bit-clean lock-free implementations: including load-linked/store conditional variables of arbitrary size, a FIFO queue, and a freelist. In addition to being portable to 64-bit software (or more generally full-architectural-width pointer operations), our implementations also improve on existing techniques in that they are (or can be) space-adaptive and do not require a priori knowledge of the number of threads that will access them.

REFERENCES:
patent: 4584640 (1986-04-01), MacGregor et al.
patent: 4847754 (1989-07-01), Obermarck et al.
patent: 5224215 (1993-06-01), Disbrow
patent: 5319778 (1994-06-01), Catino
patent: 5428761 (1995-06-01), Herlihy et al.
patent: 5553267 (1996-09-01), Herlihy
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: 6505283 (2003-01-01), Stoney
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/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.
U.S. Appl. No. 10/653,828, filed Sep. 3, 2003 and naming as inventor(s) Martin et al.
U.S. Appl. No. 10/669,948, filed Sep. 24, 2003 and naming as inventor(s) Dice et al.
U.S. Appl. No. 10/670,495, filed Sep. 24, 2003 and naming as inventor(s) Shavit et al.
U.S. Appl. No. 10/894,828, filed Jul. 20, 2004 and naming as inventor(s) Moir et al.
U.S. Appl. No. 10/894,829, filed Jul. 20, 2004 and naming as inventor(s) Moir et al.
U.S. Appl. No. 10/915,502, filed Aug. 10, 2004 and naming as inventor(s) Moir.
U.S. Appl. No. 10/966,465, filed Oct. 15, 2004 and naming as inventor(s) Moir et al.
U.S. Appl. No. 10/995,885, filed Nov. 23, 2004 and naming as inventor(s) Shavit et al.
U.S. Appl. No. 11/008,692, filed Dec. 9, 2004 and naming as inventor(s) Lev et al.
U.S. Appl. No. 11/026,849, filed Dec. 30, 2004 and naming as inventor(s) Moir et al.
U.S. Appl. No. 11/026,850, filed Dec. 30, 2004 and naming as inventor(s) Doherty et al.
Afek, Yehuda, “Wait-Free Made Fast,” Proc. 27th Annual ACM Symposium on the Theory of Computing, pp. 538-547, ACM Press, New York, NY 1995.
Anderson, James H. et al., “Using Local-Spin k-Exclusion Algorithms to Improve Wait-Free Object Implementations,”Distributed Computing, vol. 11, No. 1, pp. 1-20 1997.
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.
Dice, David et al., “Mostly Lock-Free Malloc,”Proceedings of the 3rd International Symposium on Memory Management, pp. 163-174, ACM Press, New York, NY, 2002.
Farook, Mohammad et al., “Managing Long Linked Lists Using Lock Free Techniques” InHigh Performance Computing Systems and Applications, Chapter 37(pp. 407-422), Kluwer Academic Publishers, Oct. 1998.
Harris, T., et al., “Language Support for Lightweight Transactions,”Proc. 18th Annual ACM SIGPLAN Conf. on Object-Oriented Programming Systesm, Languages, and Applications, pp. 388-402, ACM Press, New York, NY, 2003.
Hendler, Danny, et al., “A Scalable Lock-Free Stack Algorithm,”Proceedings of the 16th Annual ACM Symposium on Parallelism in Algorithms and Architectures, pp. 206-215, ACM Press, New York, NY, 2004.
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 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,”Proceedings of the 23rd International Conference on Distributed Computing, p. 522, IEEE Computer Society, Washington, D.C., 2003.
Israeli, Amos et al., “Disjoint-Access-Parallel Implementations of Strong Shared Memory Primitives,”Proc. 13th Annual ACM Symposium on Principles of Distributed Computing, pp. 151-160, ACM Press, New York, NY, 1994.
Jayanti, P., et al., “Efficient and Practical Contructions of LL/SC Variables,”Proceedings of the 22nd Annual ACM Symposium on the Principles of Distributed Computing, pp. 285-294, ACM Press, New York, NY, 2003.
Laden-Mozes, E., et al., “An Optimistic Approach to Lock-free FIFO Queues,”Lecture Notes in Computer Science, vol. 3274, pp. 117-131, Springer-Verlag Berlin Heidelberg 2004.
Martin, Paul et al., “DCAS-Based Concurrent Deques Supporting Bulk Allocation,” Sun Microsystems, Inc. Technical Report SMI TR-2002-111, Oct. 2002.
Michael, Maged M. et al., “Non-Blocking Algorithms and Preemption Safe Locking on Multiprogrammed Shared Memory Multiprocessors,”Journal of Parallel and Distributed Computing, vol. 51, No. 1, pp. 1-26, May 25, 1998.
Michael, Maged M. et al., “Safe Memory Reclamation for Dynamic Lock-Free Objects Using Atomic Reads and Writes,”Proceedings of the 21st Annual ACM Symposium on the Principles of Distributed Computing, pp. 21-30, ACM Press, New York, NY, 2002.
Michael, M., “Scalable Lock-Free Dynamic Memory Allocation,”Proceedings of the ACM SIGPLAN 2004 Conference on Programming Language Design and Implementation, pp. 35-46, ACM Press, New York, NY, 2004.
Moir, Mark et al., “Wait-Free Algorithms for Fast, Long-Lived Renaming,”Science of Computer Programming, vol. 25, No. 1, pp. 1-39, Aug. 1995.
Moir, Mark, “Practical implementation of non-blocking synchronization primitives,”Proceedings of the Sixteenth Annual ACM Symposium on Principles of Distributed Computing, pp. 219-228, ACM Press, New York, NY, 1997.
Moir, Mark, “Transparent Support for Wait-Free Transactions,”Proceedings of the 11th International Workshop on Distributed Algorithms, pp. 305-319, Springer-Verlag, London, UK, 1997.
Moir, Mark, “Laziness Pays! Using Lazy Synchronization Mechanisms to Improve Non-Blocking Contructions,”Proc. 19th Annual ACM Symposium on Principles of Distributed Computing, pp. 61-70, ACM Press, New York, NY, 2000.
Prakash, Sundeep et al., “Non-Blocking Algorithms for Concurrent Data Structures,” Technical Report 91-002, University of Florida, Jul. 1, 1991 [URL: http://citeseer.ist.psu.edu/prakash91nonblocking.html].
Prakash, Sundeep et al., “A Nonblocking Algorithm for Shared Queues Using Compare-and-Swap,”IEEE Transactions on Compute

Affiliated with

Also associated with

Rating

Space-adaptive lock-free queue using pointer-sized... does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Space-adaptive lock-free queue using pointer-sized..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Space-adaptive lock-free queue using pointer-sized... will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-4129851