Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
1998-08-25
2001-01-09
Kulik, Paul V. (Department: 2777)
Data processing: database and file management or data structures
Database design
Data structure types
Reexamination Certificate
active
06173294
ABSTRACT:
FIELD OF THE INVENTION
The present invention is in the general field of memory management and concerns more specifically garbage collected (GC) computer language and systems.
LIST OF PRIOR ART
In the description below, reference is occasionally made to the following publications:
REFERENCES
[1] R. E. Jones and R. D. Lins. Garbage Collection: Algorithms for Automatic Dynamic Memory Management. John Wiley & Sons, July 1996.
[2] U. Hölzle. A fast write barrier for generational garbage collectors. In Eliot Moss, Paul R. Wilson, and Benjamin Zorn, editors,
OOPSLA/ECOOP '
93
Workshop on Garbage Collections in Object
-
Oriented Systems,
October 1993
[3] A. L. Hosking and R. L. Hudson. Remembered Sets Can Also Play Cards. In
OOPSLA'
93
Workshop on Garbage Collection and Memory Management.
Washington, D.C., September 1993.
[4] R. L. Hudson and J. E. B. Moss. Incremental garbage collection for mature objects. In Yves Beakers and Jacques Cohen, editors. Proceeding of International Workshop on Memory Management, volume 637 of Lecture Notes in Computer Science, 1992. Springer-Verlag.
[5] H. Lieberman and C. E. Hewitt.
A Real Time Garbage Collector Based on the Lifetimes of Objects, Communications of the ACM
, 26(6), pages 419-429, 1983.
[6] J. Seligmann and S. Grarup. Incremental mature garbage collection using the train algorithm. In O. Nierstras, editor.
Proceedings of
1995
European Conference on Object
-
Oriented Programming,
Lecture Notes in Computer Science. Springer-Verlag, August 1995.
[7] Patrick Sobalvarro. A lifetime-based garbage collector for Lisp systems on general-purpose computers. Technical Report AITR-1417, MIT, AI Lab, February 1988.
[8] D. Ungar. Generation Scavenging: A Non-disruptive High Performance Storage Reclamation Algorithm.
Proceedings of the ACM Symposium on Practical Software Development Environments,
ACM SIGPLAN Notices Vol. 19, No. 5, May 1984, pp. 157-167.
[9] Paul R Wilson. Uniprocessor garbage collection techniques. In Yves Bekkers and Jacques Cohen, editors.
Proceedings of International Workshop on Memory Management,
volume 637 of Lecture Notes in Computer Science, 1992. Springer-Verlag.
[10] P. R. Wilson and T. G. Moher. A card-making scheme for controlling intergenerational references in generation-based garbage collection on stock hardware.
ACM SIGPLAN Notices,
24(5):87-92, 1989.
BACKGROUND OF THE INVENTION
In the context of memory management, garbage collection is an important task which identifies and collects memory objects that were previously allocated for a given computer application, and are no longer used thereby. Consider, for example, a continuous (and relatively large) heap (
10
) (see
FIG. 1
) and a smaller, so called “root memory module” (
12
), representative of memory currently in use by one or more computer applications.
All those objects (
14
) that are directly or indirectly reachable from the root by pointers are “alive” and should not be collected. In contrast thereto, all the objects (
16
) which have no reference pointers are effectively no longer in use and are therefore regarded as garbage that should be collected. After collection, only active objects are maintained in the heap and memory space that has just been released due to garbage collection, may be allocated for new applications.
The standard approach of scanning the entire heap in order to identify and collect garbage objects is time consuming and therefore an improved scheme called ‘generational collection’ (
5
) has been developed, and is now a well accepted solution for reducing pause times induced by garbage collection. Generational garbage collectors rely on the assumption that many objects die young. Under this assumption, it is useful to collect the garbage in the young area more frequently. Young objects that survive several collections are “prompted” to the older generation. Since the young generation is kept small, most collections are fast and do not stall the application for too long.
FIG. 2
illustrates schematically a generational garbage collection scheme, wherein the heap (
20
) is partitioned into two areas: young and old, (
21
) and (
22
), respectively. The young area (
21
) is scanned more frequently and after garbage objects therein are collected and some of the surviving objects are moved to the old area, objects may be allocated in the young area for new applications. The advantages of the generational garbage collection approach are:
1. Most collections are fast and efficient: they concentrate on the young area where it is expected to find a high percentage of garbage.
2. The heap is frequently collected. Thus the heap is frequently reused.
3. The collector uses a smaller working set since most collections only scan a small part of the heap.
4. The specified advantages (2 and 3) give rise to overall better system behavior with less paging: i.e. the collector traces through fewer pages and the program maintains a small working set since the heap is reused.
Since, only part of the heap is scanned, it is required to identify not only those pointers that reference objects from the root to the young area (e.g. pointer (
25
), but also inter-generational pointers (e.g. (
26
), i.e. pointers that originate from objects residing in the old generation and reference objects in the young generation. As will be explained in greater detail below, data structure are known in the literature which assist in rapidly identifying the inter-generational pointers for GC purposes.
In a multi-generation scheme (i.e. the heap is partitioned into more than two generations), typically, when a generation is subject to GC, all the younger generations are also collected. This reduces the bookkeeping for inter-generational pointers, so that only pointers from older to younger generations need to be maintained. Typically, the number of such pointers is relatively small and, thus, generational collections can use a data structure to maintain an (almost) updated list of these inter-generational pointers. Two possible data structures are suggested in the prior art [5], [7] and [8]: card marking and remembered sets. A combination of the two is suggested in [3].
One way to record inter-generational pointers for a given generation is to maintain a remembered set for the generation [5] and [8]. In the remember set of generation g, all locations of the inter-generational pointers that reference objects in generation g are kept. Maintenance of this set is done by the application whenever a pointer is stored, and by the collector when objects are promoted. Variations on this method are discussed in [1] and [9].
Maintaining the remembered set imposes a costly overhead on the application during normal operation seeing that any change of a pointer necessitates insertion and/or deletion of a member in the remembered set. Card marking reduces this cost [7]. Here, the heap is partitioned into cards of equal size, and whenever the application modifies an object in a card, it marks the card as dirty. Marking a card is a very short operation for the user program [2], [7], [10]. Depending on the specific processor, it may be implemented in 3 to 6 instructions. However, the collector performs more work in a card marking system. It must scan all the dirty cards to find the inter-generational pointers, instead of just getting the pointer from the remembered set. Dirty cards are cards that were recently modified by the application some of which contain inter-generational pointers, the latter being scanned repeatedly.
The advantage of combining these two methods is pointed out by Hosking and Moss [3]. After scanning a card once to find all modifications, the relevant inter-generational pointers can be kept in a remembered set and the card need not be scanned again unless it is modified. This keeps the advantage of low overhead on the application,
Azagury Alain
Kolodner Elliot K.
Petrank Erez
Yehudai Zvi
Browdy and Neimark
International Business Machines - Corporation
Kulik Paul V.
LandOfFree
Method for combining card marking with remembered set for... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method for combining card marking with remembered set for..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for combining card marking with remembered set for... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2443173