Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
2001-06-27
2002-03-05
Homere, Jean R. (Department: 2177)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000, C707S793000
Reexamination Certificate
active
06353838
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates generally to computer systems and more specifically to managing the memory portions of such systems.
BACKGROUND OF THE INVENTION
Many computer systems manage information by the use of objects. An object is data that share a particular attribute and occupy a region of random access memory (RAM). Objects are not permitted to overlap in memory. Live objects are those needed in the computational process currently being performed by a computer system. If all objects in a system are live at all times, then there is no concern about memory management. The space assigned to each object at system startup need never be reclaimed. In most systems, however, live objects have varying lifetimes that cannot be predicted in advance. In such systems, some method of recognizing expired or dead objects and evicting them from memory is necessary if memory resources are to be conserved.
Garbage refers to data stored in computer system memory that is no longer being used in the performance of a program, method, function, or subroutine that allocated such data. For purposes of convenience, a program, method, function, or subroutine that allocates data will be referred to simply as a program or function. Garbage collection is the process of locating data in dynamically-allocated memory that is no longer being used and reclaiming the memory to satisfy future memory allocation requests. Garbage collection offers the potential of significant programmer productivity gains because with garbage collection, programmers need not worry about removing data from memory when no longer needed when the program is ended. Hence, garbage collection encourages programmers and system designers to dedicate their efforts to higher-level pursuits, such as the design of fundamental algorithms, user interfaces, and general program functionality. Also, by eliminating many low-level programming concerns, garbage collection reduces the likelihood of programming errors. These benefits of garbage collection combine together to offer improved software functionality and reliability for lower development costs.
Garbage collection can occur in a number of situations. For example, when the amount of memory remaining in available memory falls below some pre-defined level, garbage collection is performed to regain whatever memory is recoverable. Also, a program or function can force garbage collection by calling the garbage collector. Finally, the garbage collector may run as a background task that searches for objects to be reclaimed. But however they may be invoked, traditional garbage collectors work by periodically halting execution of system programs in order to traverse all of memory in search of memory regions that are no longer in use. Traditional garbage collectors have a number of major shortcomings. One such shortcoming is that, in terms of rates of allocation and deallocation of objects, storage throughput is generally much lower than, for example, stack allocation. Also, the times required to allocate memory are only very loosely bounded X the bounds on allocation times are not tight enough to allow reliable programming of highly-interactive or real-time systems such as mouse tracking, interactive multimedia device control, and viral reality systems. Finally, in some garbage collectors, the performance penalties associated with memory reads and writes are so high that overall system performance may be unacceptably slow.
These concerns are further exacerbated in systems with inherent limitations and particularities. For example, Microsoft Windows CE is a compact, efficient and scalable operating system that may be used in a wide variety of embedded products, from hand-held PCS to specialized industrial controllers and consumer electronic devices. Many devices that utilize Microsoft Windows CE are intended to have a relatively low amount of random-access memory (RAM), such as one megabyte, to ensure that the devices remain low in cost, compact in size, and efficient in the usage of power. Moreover, devices designed to utilize Microsoft Windows CE typically have less powerful processors than what is typically found on computers designed to run more powerful operating systems like Microsoft Windows NT. For systems with such inherent limitations and particularities, it is essential to maximize the amount of memory available. There is a need to effectively and efficiently maximize the amount of memory available in such systems.
SUMMARY OF THE INVENTION
The present invention is directed to a method for removing as many temporary objects as possible during the execution of a program or function so that a main garbage collector is not triggered.
Certain commands in the program allocate objects, whereas other commands do not. Typically, such objects are allocated from a heap. In one aspect of the present invention, if a program command does allocate an object, information is stored on such object that will facilitate its identification at a later time after the program terminates. Such information comprises, for example, thread identification, stack number, and a mark bit.
The present invention allows for the reclamation of such space without waiting for the main garbage collector. During the execution of a program, if an allocated object is never stored into another object such object can be discarded and the space that it occupied can be reclaimed. In other words, if the main garbage collector is activated, the space occupied by such object would be reclaimed. Hence, one of the advantages of the present invention is the freeing up of memory at a time sooner than when the garbage collector performs its task, because as noted above the present invention allows for the reclaiming of space as soon as the program that allocated such space is terminated. Furthermore, instead of scanning the whole heap, as the garbage collector would, the incremental garbage collector of the present invention allows for the scanning of only the allocated portion of the heap, instead of the entire heap.
REFERENCES:
patent: 4797810 (1989-01-01), McEntee et al.
patent: 5088036 (1992-02-01), Ellis et al.
patent: 5136706 (1992-08-01), Hildebrant
patent: 5535390 (1996-07-01), Hildebrandt
patent: 5560003 (1996-09-01), Nilsen et al.
patent: 5848423 (1998-12-01), Ebrahim et al.
patent: 5873104 (1999-02-01), Tremblay et al.
patent: 5893121 (1999-04-01), Ebrahim et al.
patent: 5960087 (1999-09-01), Tribble et al.
patent: 6047295 (2000-04-01), Endicott et al.
patent: 6070173 (2000-05-01), Huber et al.
“International Search Report for International Application No. PCT/US 98/26769”,Completion Date--Apr. 9, 1999; Authorized Officer Ahmed Soliman, 7 Pages, (Apr. 19, 1999).
Katzberg, J. D., et al., “Garbage Collection Software Integrated with the System Swapper in a Virtual Memory System”,IEEE WESCANEX 93, Communications, computers and power in the modern environment, pp. 184-191, (May 17, 1993).
Shapiro, M., “A fault-tolerant, scalable, low-overhead distributed garbage detection protocol”,IEEE, pp. 208-217, (Jun. 1991).
Gilbert Mark
Markley Michael E.
Sauntry David M.
Homere Jean R.
Microsoft Corporation
Robinson Greta
Workman & Nydegger & Seeley
LandOfFree
Incremental garbage collection does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Incremental garbage collection, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Incremental garbage collection will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2844994