Lock free reference counting

Details Lock free reference counting Lock free reference counting

2006-01-31

2006-01-31

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

Electrical computers and digital processing systems: interprogra

Interprogram communication using message

Object oriented message

C707S793000

Reexamination Certificate

active

06993770

ABSTRACT:
We present a methodology for transforming concurrent data structure implementations that depend on garbage collection to equivalent implementations that do not. Assuming the existence of garbage collection makes it easier to design implementations of concurrent data structures, particularly because it eliminates the well-known ABA problem. However, this assumption limits their applicability. Our results demonstrate that, for a significant class of data structures, designers can first tackle the easier problem of an implementation that does depend on garbage collection, and then apply our methodology to achieve a garbage-collection-independent implementation. Our methodology is based on the well-known reference counting technique, and employs the double compare-and-swap operation.

REFERENCES:
patent: 4775932 (1988-10-01), Oxley et al.
patent: 4912629 (1990-03-01), Shuler, Jr.
patent: 6144965 (2000-11-01), Oliver
patent: 6560619 (2003-05-01), Flood et al.
patent: 6668310 (2003-12-01), McKenney
patent: 2001/0047361 (2001-11-01), Martin et al.
patent: 2001/0056420 (2001-12-01), Steele, Jr. et al.
Farook, Mohammad et al. “Managing Long Linked Lists Using Lock Free Techniques.” Oct. 1998.
Valois, John D. “Implementing Lock-Free Queues.” Oct. 1994.
Micahel, Maged M. “Safe Memory Reclamation for Dynamic Lock-Free Objects Using Atomic Reads and Writes.” ACM. Jul. 21-24, 2002.
Michael, Maged M. et al. “Non-Blocking Algorithms and Preemption Safe Locking on Multiprogrammed Shared Memory Multiprocessors.” Mar. 1997.
Stone, Janice M. “A simple and correct shared-queue algorithm using compare-and-swap.” IEEE. May 1990.
Michael, Maged M. et al. “Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms.” Dec. 1995.
Prakash, Sundeep et al. “Non-Blocking Algorithms for Concurrent Data Structures.” Jul. 1, 1991.
Valois, John D. “Lock-Free Linked Lists Using Compare-and-Swap.” 1995.
Chappell, David. “Understanding ActiveX and OLE.” Microsoft Press, 1996, p. 51-52.
Brown, Jeremy Hanford. “Memory Management on a Massively Parallel Capability Architecture.” Dec. 3, 1999.
Ben-Ari, Mordechai, “On-the-Fly Garbage Collection: New Algorithms Inspired by Program Proofs,” Automata, Languages and Programming, 9th Colloquium, Lectures Notes in Computer Science, vol. 140, pp. 14-22, Springer-Verlag, Jul. 12-16, 1982.
Barnes, Greg, “A Method for Implementing Lock-Free Shared Data Structures,” inProceedings of the 5th ACM Symposium on Parallel Algorithms and Architectures, pp. 261-270, Velen, Germany, Jun. 1993.
Ben-Ari, Mordechai, “Algorithms for On-the-Fly Garbage Collection”, ACM Transactions on Programming Languages and Systems, vol. 6, No. 3, Jul. 1984, pp. 333-344.
Detlefs, David, “Garbage Collection and Run-time Typing as a C++ Library,” inProceedings of the 1992 Usenix C++Conference, Digital Equipment Corporation Systems Research Center, Jun. 18, 1992, 20 pp. (online) [downloaded from the internet Mar. 29, 2002: url:<http://citeseer.nj.nec.com/ellis93safe.html>].
DeTreville, John, “Experience with Concurrent Garbage Collectors for Modula-2+”,Digital Equipment Corporation Systems Research Center Tech Report, No. 64, Nov. 22, 1990 (online) [downloaded from the internet Apr. 1, 2002: url: <ftp://gatekeeper:research.compaq.com/pub/DEC/SRC/research-reports/SRC-064.pdf>.
Herlihy, Maurice and Moss, J. Eliot B., “Transactional Memory: Architectural Support for Lock-Free Data Structures,” Technical Report CRL 92/07, Digital Equipment Corporation, Cambridge Research Lab, 1993, pp. 289-300 (online) [downloaded from the internet Mar. 29, 2002: url: <http://www.cs.brown.edu/people/mph/isca93.html>].
Hesselink, W. H. and Grotte, J. F., “Waitfree distributed memory management by Create, and Read Until Deletion ({CRUD}),” Dept. of Math. and Computing Science, University of Groningen, The Netherlands, pp. 1-21, Dec. 31, 1998, (online) [downloaded from the internet Mar. 29, 2002: url: <http://citeseer.nj.nec.com/groote98waitfree.html>].
Jones, Richard and Lins, Rafael, “Garbage Collection Algorithms for Automatic Dynamic Memory Management,” John Wiley & Sons, Ltd. England, 1996, pp. 19-25, 200-202.
Shavit, Nir and Touitou, Dan, “Software Transactional Memory,” Distributed Computing, Feb. 1997, Springer-Verlag, vol. 10(2), pp. 99-116.
van de Snepscheut, Jan L. A., “Algorithms for On-the-Fly Garbage Collection—Revisited,”Information Processing Letters, vol. 24, No. 4, pp. 211-216, Elsevier Science Publishers, Mar. 2, 1987, The Netherlands.

Affiliated with

Also associated with

Rating

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 Lock free reference counting, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Lock free reference counting will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3596545