Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
1998-06-06
2002-10-29
Jung, David (Department: 2175)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000, C707S793000, C717S116000
Reexamination Certificate
active
06473773
ABSTRACT:
FIELD OF THE INVENTION
This invention relates generally to the field of mixed programming environments, and provides, in particular, mechanisms for combining memory management disciplines and for managing object instances in a mixed programming environment.
BACKGROUND OF THE INVENTION
Modem operating systems and hardware platforms make available increasingly large addressable or dynamic memory spaces. Modem applications have correspondingly grown in size and complexity to take advantage of this available memory. Most applications today use a great deal of dynamic memory. Features such as multitasking and multi threading increase the demands on memory.
Where there isn't enough space in dynamic memory for an application to execute, execution time is considerably slowed down while data that another application is referencing is swapped out of dynamic memory to make room for the currently executing thread or process. Object oriented (OO) programming languages such as C++, in particular, use dynamic memory much more heavily than comparable serial programming languages like C, often for small, short-lived allocations.
The effective management of dynamic memory, to locate useable free blocks and to deallocate blocks no longer needed in an executing program, has become an important programing consideration.
The C and C++ languages use the memory allocation function malloc to manage the dynamic memory space. Malloc is a library function defined under the ANSI C standard, and in its usual form, it is a list of free blocks of memory. To allocate a specified number of bytes of memory for a process, the list is searched linearly until a suitably-sized block of free memory is located, and a pointer is returned to identify the address of the newly allocated block. A corresponding deallocation is made using the function free. This causes the space pointed to by the pointer to be deallocated and put back into the list of free memory.
There are modifications and additional allocation and deallocation functions that can be used, examples of which are discussed in:
“Advanced Programing in the UNIX® Environment”, W. Richard Stevens, 1992, Addison Wesley Publishing Co.; and
“Rethinking Memory Management”, Arthur D. Applegate,
Dr. Dobb's Journal
, June 1994, pp. 52-55.
However, for the most part, memory management under C and C++ is handled explicitly, for the reasons discussed below.
Contrasted with this is the implicit form of memory management to make excess memory available without having to run a deallocating routine. This is generally referred to as “garbage collection”, and is used in a number of interpreted OO programming languages such as Lisp, Smalltalk and Java.
C++ is a compiled OO language. Some of the differences between compiled and interpreted OO languages, as well as the differences between OO and serial programming technology are discussed in two co-pending Canadian Patent Applications, No. 2,204,971 titled “Uniform Access to and Interchange Between Objects Employing a Plurality of Access Methods” (IBM Docket No. CA997-013) and No. 2,204,974 titled “Transparent Use of Compiled or Interpreted Objects in an Object Oriented System” (IBM Docket No. CA997-014), which are commonly assigned.
Reference counting is a technique used to provide automatic garbage collection in some language implementations (for example, Lisp), and is also sometimes used explicitly by programmers in languages such as C++ that do not provide implicit garbage collection, in order to achieve a similar effect in that language domain. Embedded in each object is an integer field called a reference count. Whenever a reference to the object is duplicated, this count is required to be incremented. Conversely, when a reference is discarded or replaced by a reference to some other object, the count is required to be decremented. By means of this counting discipline, which may be enforced by the language implementation itself (as in the case of Lisp language) or by the programmer (as when this technique is used in C++), the reference count field indicates how many references exist to the object. If, after decrementing the count, it is found to have reached zero, then that object is known to be unreferenced and its storage can be freed.
Although reference counting has advantages of simplicity and scalability, it does not deal well with data structures containing circular references. These are collections of objects containing references to one other, such that the reference counts of all objects in the collection are nonzero even though the executing application no longer holds a reference to any of them and will not access them. Reference counting will not discover that these objects are garbage.
A block of memory is implicitly available to be deallocated or returned to the list of free memory whenever there are no references to it. In a runtime environment supporting implicit memory management, a garbage collector usually scans the dynamic memory from time to time looking for unreferenced blocks and returning them. The garbage collector starts at locations known to contain references to allocated blocks. These locations are called “roots”. The garbage collector examines the roots and when it finds a reference to an allocated block, it marks the block as referenced. If the block was unmarked, it recursively examines the block for references. When all the referenced blocks have been marked, a linear scan of all allocated memory is made and unreferenced blocks are swept into the free memory list. The memory may also be compacted by copying referenced blocks to lower memory locations that were occupied by unreferenced blocks and then updating references to point to the new locations for the allocated blocks. Because scanning collectors determine which objects are actually reachable, they are not fooled by circular references and will collect those objects when they are garbage.
Serious problems can arise if garbage collection of an allocated block occurs prematurely. For example, if a garbage collection occurs during processing, there would be no reference to the start of the allocated block and the collector would move the block to the free memory list. If the processor allocates memory, the block may end up being reallocated, destroying the current processing. This could result in a system failure.
Applications that use garbage collection sometimes need to defeat the collection mechanism in controlled ways in order to achieve a particular desired effect. A weak reference to an object is a reference that is intentionally overlooked by the garbage collection mechanism, with the result that an object will be considered garbage and subject to collection if it is unreferenced, or if it is reachable only through weak references. Ordinary references are considered by the garbage collector and are sometimes called strong references to distinguish them from the weak variety.
One use of weak references is to break circular reference chains. Another use is in implementing an instance manager, which is a software module that keeps track of the instances of a particular class or group of classes. The instance manager needs to hold a reference to each object in order to locate it, but it is not the intent that these references alone should prevent the objects from being garbage collected. These requirements can be met by having the instance manager hold weak references to the objects.
The destruction of an object and reclamation of its storage is often preceded by a finalization step, in which user-defined code associated with the object is executed so as to give it an opportunity to “clean up” before it is destroyed. This corresponds to the execution of destructor methods in C++.
The Java language requires that when the garbage collector has determined that an object is unreferenced, it must first execute the finalize( ) methods defined for that object before reclaiming its storage. If, after the object has been finalized, it is subsequently found to still
Cheng Michael
Hanson Tim Scott
Nash Simon Christopher
Rochat Kim Lawson
Thomson Brian Ward
Drumheller Ronald L.
International Business Machines - Corporation
Jung David
LandOfFree
Memory management in a partially garbage-collected... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Memory management in a partially garbage-collected..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Memory management in a partially garbage-collected... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2955992