Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
1999-09-29
2002-02-19
Shah, Sanjiv (Department: 2172)
Data processing: database and file management or data structures
Database design
Data structure types
C711S165000
Reexamination Certificate
active
06349314
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates generally to memory management in an interactive system, and in particular, the present invention relates to adaptive scheduling of a mark and sweep garbage collection process in an interactive system.
BACKGROUND OF THE INVENTION
Efficient use of memory and memory management strategies are important factors to be considered in an interactive system that utilizes a programming language with automatic memory management, such as Java for example. In such an interactive system, certain portions of memory are allocated to define objects, such as mouse events, user interface components, database records, and so forth, to enable those objects to be stored. Since the amount of memory of the system is limited, it is important to identify and reclaim memory allocated to obsolete objects, or previously defined objects that are no longer required for use by existing objects, in order to enable the memory associated with the obsolete objects to be re-used to perform other functions, such as creating new objects. This process of identifying and reclaiming memory previously allocated to objects that have become obsolete is commonly referred to as “garbage collection”. Implementation of the garbage collection process is typically accomplished using a garbage collection algorithm.
One such conventional garbage collection algorithm, referred to as mark and sweep garbage collection, involves the combined operation of a mark phase and a sweep phase. During operations of the system, a tree of objects, starting at a root object that is retained while the system is running, is stored in the system memory. During the mark phase, the tree is traversed, and all objects that are part of the tree are marked as being in use. Base objects, or root objects of trees are identified or marked as not being garbage and therefore not to be collected. Relationships between the root objects and all secondary objects referenced by the root objects are defined. By being part of a tree, secondary objects that are implicitly referenced by a root object of the tree are required for use by that root object and are therefore be marked so as not to be collected. On the other hand, any secondary objects that are not implicitly referenced by an object of the tree are not required for use and are therefore left unmarked. Once the mark phase is completed, it is assumed that any unmarked object in memory is no longer referenced and is therefore garbage that can be collected. During the sweep phase that follows, enumerated objects in memory that are unmarked are deallocated to enable the corresponding memory to be recovered and reused.
In order to ensure accuracy in the marking of objects during the mark phase, changes to the tree cannot be allowed to occur while the mark operation is performed. If changes were to take place during the mark operation, objects could possibly be incorrectly marked as being in use when they are no longer referenced, or left unmarked when in fact they are referenced and therefore should be marked as objects in use. As a result, all threads or operations of the system, other than the one performing garbage collection, must be halted during the garbage collection operation to ensure that the tree remains stable and the mark phase is accurate.
A user of an interactive system tends to have certain expectations of how quickly the system responds when certain input events are performed, and these expectations vary between input events. For example, a user will typically expect an instantaneous response from the system when performing certain input commands, such as during input events relating to the creation or editing of text, scrolling through a list, playing a game, and so forth. On the other hand, the user will not expect instantaneous response from the system during other input events, such as switching between screens or programs, for example.
Conventional interface devices that employ a mark and sweep garbage collection operation include an algorithm for determining when to perform the garbage collection process. Conventional algorithms are designed to invoke the mark and sweep garbage collection either after a certain amount of memory has been allocated or after less than a certain amount of memory is free or available. Since memory allocation tends to be unpredictable, it is possible that the garbage collection process of the conventional interface device will be invoked at any time, including during those time periods when the user is performing an input event for which there is a user expectation of instantaneous response from the system.
For example, due to the non-deterministic nature of memory allocation, it is possible that the garbage collection process of conventional interface devices could sometimes take place while the user is scrolling through a list. As a result, for reasons described above, all threads or operations, including operations associated with the scrolling operation being performed by the user, must necessarily be stopped to enable the garbage collection process to be performed. This halting of operations associated with the scrolling performed by the user will directly impact the user since the scrolling will be momentarily halted, contradicting user expectations of an instantaneous response from the system. As a result, the user will tend to view the garbage collection process as an unacceptable and annoying interruption that corrupts user expectations and enjoyment of the system.
Accordingly, what is needed is a garbage collection scheduling scheme that lessens the impact of the garbage collection process on the user.
REFERENCES:
patent: 5088036 (1992-02-01), Ellis et al.
patent: 5241673 (1993-08-01), Schelvis
patent: 5446901 (1995-08-01), Owicki et al.
patent: 5560003 (1996-09-01), Nilsen et al.
patent: 5790778 (1998-08-01), Bush et al.
patent: 5799185 (1998-08-01), Watanabe
patent: 5819299 (1998-10-01), Bejar
patent: 5845298 (1998-12-01), O'Connor et al.
patent: 5857210 (1999-01-01), Tremblay et al.
patent: 5873105 (1999-02-01), Tremblay et al.
patent: 5903899 (1999-05-01), Steele, Jr.
patent: 6052699 (2000-04-01), Huelsbergen et al.
patent: 6065020 (2000-05-01), Dussud
patent: 6101580 (2000-08-01), Agesen et al.
patent: 6226761 (2001-05-01), Berstis
patent: 6247027 (2001-06-01), Chaudhry et al.
patent: 6289360 (2001-09-01), Kolodner et al.
Roger Henriksson, Dept. of Computer Science, Lund University, May 1996, “Adaptive Scheduling of Incremental Copying Garbage Collection for Interactive Applications”, pp. 1-8.
Roger Henriksson, Dept. of Computer Science, Lund University, Jun. 1994, “Scheduling Real Time Garbage Collection”, pp. 1-14.
Shah Sanjiv
Soldner Michael C.
Vaas Randall S.
LandOfFree
Adaptive scheduler for mark and sweep garbage collection in... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Adaptive scheduler for mark and sweep garbage collection in..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Adaptive scheduler for mark and sweep garbage collection in... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2940891