Data processing: database and file management or data structures – Database design – Data structure types
Patent
1997-04-23
1998-12-08
Black, Thomas G.
Data processing: database and file management or data structures
Database design
Data structure types
G06F 900
Patent
active
058484230
ABSTRACT:
In an object oriented computer system, a root set of object references includes object references stored in the computer system's registers, as well as object references stored in activation records in the program stack. Whenever a method is invoked, a corresponding activation record is stored on the program stack. The activation record includes the invocation address for the method called as well as parameters passed to the called method. A class loader, which loads object classes into memory, determines the locations of the object references in the activation records associated with each method in a loaded object class. A list of offset values for each method activation record is stored by the class loader in a hash table data structure at a location in the hash table data structure determined by hashing the unique invocation address assigned to the method. At the beginning of each garbage collection cycle, a root set locator procedure processes each activation record in the program stack by applying a hash function to the invocation address in the activation record to determine where in the hash table data structure to locate the object reference offsets for that activation record. Using the located object reference offsets, each of the object references in the activation record is added to a root set list. The number of processor cycles required to locate and copy all the object references in activation records in the program stack is a linear function of the number of such object references.
REFERENCES:
patent: 4757438 (1988-07-01), Thatte et al.
patent: 4907151 (1990-03-01), Bartlett
patent: 4920483 (1990-04-01), Pogue et al.
patent: 4989134 (1991-01-01), Shaw
patent: 5088036 (1992-02-01), Ellis et al.
patent: 5222221 (1993-06-01), Houri et al.
patent: 5301288 (1994-04-01), Newman et al.
patent: 5355483 (1994-10-01), Serlet
patent: 5408650 (1995-04-01), Arsenault
patent: 5535329 (1996-07-01), Hastings
patent: 5560003 (1996-09-01), Nilsen et al.
patent: 5561786 (1996-10-01), Morse
patent: 5566321 (1996-10-01), Pase et al.
patent: 5687368 (1997-11-01), Nilsen
patent: 5692185 (1997-11-01), Nilsen et al.
Moon, David A., "Garbage Collection in a Large Lisp System", ACM (1984), pp. 235-246.
Aho, Alfred V., et al., "Compilers Principles, Techniques, and Tools," Addison-Wesley, Mar. 1988, Ch. 10, pp. 585-586, 592-599, 605-607.
Karen, et al., "Garbage Collection for Prolog Based on WAM", Communications of the ACM, vol. 31, Issue 6 (Jun. 1, 1988).
Courts, Robert, "Improving Locality of Reference in a Garbage-Collecting Memory Management System", Communications of the ACM, vo. 31, No. 9 (1988), pp. 1128-1138.
Grehan, Rick, "Hands On, Some Assembly Required; If Memory Serves . . . ", Byte (Aug. 1989), pp. 279-280, 282, 284, 337.
Grehan, Rick, "Hands On, Some Assembly Required; Virtually Virtual Memory", Byte (Sep. 1990), pp. 455-456, 458, 460, 462, 464.
Kuechlin, Wolfgang W., "On Multi-Threaded List-Processing and Garbage Collection", IEEE (1991), pp. 894-897.
Booch, Grady, "Object Oriented Design with Applications", Benjamin/Cummings (1991).
Imai, Akira, et al., "Evaluation of Parallel Copying Garbage Collection on a Shared-Memory Multiprocessor", IEEE (1993), pp. 1030-1040.
Holzle, Urs, et al., "A Fast Write Barrier for Generational Garbage Collectors"Oopsla '93 Garbage Collection Workshop (Oct. 1993).
Bott, Ed. Windows; Windows' Invisible Wall: The 64K Barrier, System Resources are the Hidden Memory Limit that Microsoft Forgot:, PCContact (Mar. 1994), pp. 210, 212.
Shaw, Richard Hale, "An Introduction to the Win32 API", PC Magazine vol. 13, No. 8, pp. 291-295.
Barrett, David A., "Improving the Performance of Conservative Generational Garbage Collection", 1995 Thesis.
Wilson, Paul R., et al., "Dynamic Storage Allocation: A Survey and Critical Review", University of Texas at Austin, 1995.
Jones, Richard et al., "Garbage Collection, Algorithms for Automatic Dynamic Memory Management", John Wiley & Sons (1996).
Gadbois, David et al., "GC FAQ", http://www.centerline.com/people/chase/GC/GC-faq.html (Jan. 6, 1997).
Caro, Alejandro, "A Novel 64 Bit Data Representation for Garbage Collection and Synchronizing Memory", Computation Structures Group Memo 396 (Apr. 9, 1997).
Harbaugh, Sam et al., "HeapGuard.TM., Eliminating Garbage Collection in Real-Time Ada Systems", Integrated Software, Inc., pp. 704-708.
Wallace, David Vinayak et al., "Simple Garbage Collection in G++", Draft, Rev. 1.1.
Jones, Richard et al., "Garbage Collection, Algorithms for Automatic Dynamic Memory Management", John Wiley & Sons, Chs. 6, 7 and 8.
Ebrahim Zahir
Mohamed Ahmed H.
Black Thomas G.
Mills, III John G.
Sun Microsystems Inc.
Williams Gary S.
LandOfFree
Garbage collection system and method for locating root set point does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Garbage collection system and method for locating root set point, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Garbage collection system and method for locating root set point will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-190576