Single-word lock-free reference counting

Details Single-word lock-free reference counting Single-word lock-free reference counting

2007-11-20

2007-11-20

Bullock, Jr., Lewis A. (Department: 2195)

Data processing: database and file management or data structures

Database design

Data structure types

C707S793000, C719S315000, C718S100000, C718S102000

Reexamination Certificate

active

10340150

ABSTRACT:
Solutions to a value recycling problem that we define herein facilitate implementations of computer programs that may execute as multithreaded computations in multiprocessor computers, as well as implementations of related shared data structures. Some exploitations of the techniques described herein allow non-blocking, shared data structures to be implemented using standard dynamic allocation mechanisms (such as malloc and free). A class of general solutions to value recycling is described in the context of an illustration we call the Repeat Offender Problem (ROP), including illustrative Application Program Interfaces (APIs) defined in terms of the ROP terminology. Furthermore, specific solutions, implementations and algorithm, including a Pass-The-Buck (PTB) implementation are also described. Solutions to the proposed value recycling problem have a variety of uses. For example, a single-word lock-free reference counting (SLFRC) technique may build on any of a variety of value recycling solutions to transform, in a straight-forward manner, many lock-free data structure implementations that assume garbage collection (i.e., which do not explicitly free memory) into dynamic-sized data structures.

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: 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: 6615216 (2003-09-01), Hu
patent: 6651146 (2003-11-01), Srinivas et al.
patent: 6826757 (2004-11-01), Steele, Jr. et al.
patent: 6848033 (2005-01-01), Joseph
patent: 2001/0047361 (2001-11-01), Martin 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
Michael, Maged M. et al. “Correction of a Memory Management Method for Lock-Free Data Structures.” Dec. 1995.
Michael, Maged M. et al., “Non-Blocking Algorithms and Preemption-Safe Locking on Multiprogrammed Shared Memory Multiprocessors”, Journal of Parallel and Distributed Computing, 51 (1), pp. 1-26, 1998.
Trieber, R, “Systems Programming: Coping with Parallelism”, IBM Technical Report RJ5118, Apr. 23, 1986.
Valois, John D., “Lock-Free Linked Lists Using Compare-and-Swap”, in Proceedings of the 14thAnnual ACM Symposium on Principles of Distributed Computing, pp. 214-222, 1995.
U.S. Appl. No. 09/837,671, titled “Lock Free Reference Counting” filed Apr. 18, 2001, naming as inventors David L. Detlefs et al.
Agesen, Ole et al., “DCAS-Based Concurrent Deques”, 12thAnnual ACM Symposium on Parallel Algorithms and Architectures, Jul. 2000.
Arora, Nimar S. et al., “Thread Scheduling for Multiprogrammed Multiprocessors”, 10thAnnual ACM Symposium on Parallel Algorithms and Architectures, Jul. 1998.
Herlihy, Maurice et al., “Transactional Memory: Architectural Support for Lock-Free Data Structures”, Annual International Symposium on Computer Architecture, May 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 et al., “An Efficient Meta-Lock for Implementing Ubiquitous Synchronization,” ACM SIGPLAN Notices, vol. 34, No. 10, pp. 207-222, Oct. 1999.
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, “Garbage Collection and Run-time Typing as a C++Library,”Proceedings of the 1992 Usenix C++ Conference, Digital Equipment Corporation Systems Research Center, 20 pages, Jun. 18, 1992 [URL: <http://citeseer.ist.psu.edu/detlefs92garbage.html>].
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, 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.
Hesselink, W.H. et al., “Waitfree distributed memory management by Create, and Read Until Deletion ({CRUD}),” Technical Report: SEN-R9811, Dept. of Math. and Computing Science, University of Groningen, The Netherlands, 21 pages, Dec. 31, 1998 [URL: <http://citeseer.ist.psu.edu/hesselink98waitfree.html>].
Jones, Richard, et al.,Garbage Collection Algorithms for Automatic Dynamic Memory Management, pp. 19-25, 200-202, John Wiley & Sons, Ltd. Chichester, England, 1996.
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.
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 Constructions,”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 Computers, vol. 43, No. 5, pp. 548-559, May 1994.
Shann, Chien-Hua et al., “A Practical Nonblocking Queue Algorithm Using Compare-and-Swap,”Proceedings of the Seventh International Conference on Parallel and Distributed Systemsp. 470, IEEE Computer Society, Washington, D.C., 2000.
Shavit, N., et al., “Software Transactional Memory,”Distributed Computing, vol. 10, No. 2, pp. 99-116, Feb. 1997.
Shavit, Nir,

Affiliated with

Also associated with

Rating

Single-word lock-free reference counting does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Single-word lock-free reference counting, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Single-word lock-free reference counting will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3883484