Concurrent, lock-free object copying

Details Concurrent, lock-free object copying Concurrent, lock-free object copying

2010-03-24

2011-10-18

Breene, John E (Department: 2162)

Data processing: database and file management or data structures

Garbage collection

C707S816000, C707S820000, C711S108000, C711S170000, C711S171000

Reexamination Certificate

active

08041752

ABSTRACT:
Described is a technology by which a real-time data relocating mechanism is provided for multiprocessing environments, including supporting lock-free programs that run in parallel. The relocating mechanism moves an object by using a status field related to the data field, possibly in an interim (wide) object space, which is then copied to a to-space object. The status information for each data field of the original object contains information indicating where a current version of the data for each field is present, that is, in the original, wide or to-space object. In one example, a handshake mechanism of a garbage collector establishes preparation and copy phases between the mechanism and other threads that determine where memory accesses occur. Also described is support for program thread compare-and-swap (CAS) operations and/or multi-word atomic operations.

REFERENCES:
patent: 5088036 (1992-02-01), Ellis et al.
patent: 5170480 (1992-12-01), Mohan et al.
patent: 6098080 (2000-08-01), Endicott et al.
patent: 6192517 (2001-02-01), Agesen et al.
patent: 6247025 (2001-06-01), Bacon
patent: 6430580 (2002-08-01), Azagury et al.
patent: 6502111 (2002-12-01), Dussud
patent: 6567905 (2003-05-01), Otis
patent: 6671707 (2003-12-01), Hudson et al.
patent: 6721865 (2004-04-01), Lewis
patent: 6826583 (2004-11-01), Flood et al.
patent: 6845385 (2005-01-01), Hennessey
patent: 7062519 (2006-06-01), Garthwaite
patent: 7136887 (2006-11-01), Garthwaite et al.
patent: 7174354 (2007-02-01), Andreasson
patent: 7328316 (2008-02-01), Moir et al.
patent: 7529752 (2009-05-01), Hinshaw et al.
patent: 2001/0047361 (2001-11-01), Martin et al.
patent: 2001/0056420 (2001-12-01), Steele, Jr. et al.
patent: 2003/0217058 (2003-11-01), Ladan-Mozes et al.
patent: 2004/0015642 (2004-01-01), Moir et al.
patent: 2004/0034673 (2004-02-01), Moir et al.
patent: 2004/0122874 (2004-06-01), Garthwaite
patent: 2005/0071335 (2005-03-01), Kadatch
patent: 2005/0132374 (2005-06-01), Flood et al.
patent: 2006/0037026 (2006-02-01), Doherty et al.
patent: 2006/0173885 (2006-08-01), Moir et al.
patent: 2008/0163220 (2008-07-01), Wang et al.
patent: 2008/0183958 (2008-07-01), Cheriton
patent: 2008/0228784 (2008-09-01), Dempsey
patent: 2010/0262636 (2010-10-01), Bacon et al.
Appel et al.—“Real-Time Concurrent Collection on Stock Multiprocessors”—Proceedings of the ACM SIGPLAN 1988 conference on Progamming Language Design and Implementation—vol. 23, Issue 7, Jul. 1988 (pp. 11-20).
Anderson et al.—“Lock-Free Transactions for Realtime Systems”—Series in Engineering, 1997—NSF contract CCR 9216421, Intel and IBM (pp. 1-8).
Gao, H. et al.; “Lock-free Parallel Garbage Collection by Mark&Sweep”; Technische Universiteit Eindhoven, The Netherlands; 2004; pp. 1-38.
Huelsbergen, Lorenz et al.; “A Concurrent Copying Garbage Collector for Languages that Distinguish (Im)mutable Data”; ACM Press, New York, USA; 1993; pp. 73-82.
Michael, Maged M.; “Safe Memory Reclamation for Dynamic Lock-Free Objects Using Atomic Reads and Writes”; IBM Thomas J. Watson Research Centre, P.O. Box 218, Yorktown Heights, NY 10598 USA; Jul. 21-24, 2002; pp. 1-10.
Fraser, Kair; “Practical Lock-freedom”; University of Cambridge; Feb. 2004; pp. 1-116.
Ram, et al.; “Parallel garbage collection without synchronization overhead”; ACM SIGARCH Computer Architecture News; vol. 13, Issue 3; Proceedings of the 12th Annual International Symposium on Computer Architecture (ISCA '85); Jun. 1985; pp. 84-90.
Herlihy, Maurice et al.; “Nonblocking Memory Management Support for Dynamic-Sized Data Structures”; ACM Transactions on Computer Systems; vol. 23, No. 2; May 2005; pp. 146-196.

Affiliated with

Also associated with

Rating

Concurrent, lock-free object copying does not yet have a rating. At this time, there are no reviews or comments for this patent.

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

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-4274542