Duration-based memory management of complex objects

Details Duration-based memory management of complex objects Duration-based memory management of complex objects

1998-06-24

2001-06-26

Banankhah, Majid A. (Department: 2151)

Electrical computers and digital processing systems: multicomput

Computer-to-computer data routing

Least weight routing

C711S005000, C711S102000, C711S103000, C711S001000, C707S793000, C707S793000

Reexamination Certificate

active

06253226

ABSTRACT:

FIELD OF THE INVENTION
The present invention relates to computer systems and more particularly to memory management techniques for complex objects within a database system.
BACKGROUND OF THE INVENTION
A complex object is an instance of a data type or object-oriented class that contains zero or more scalar attributes (e.g. integers, characters, etc.) and one or more attributes that can point to or reference other complex objects. An attribute capable of pointing to or referencing another object is referred to herein as a “pointer.” Thus, a complex object may be mapped to a top-level data structure with one or more pointers to other data structures that in turn may have pointers to other data structures. Examples of complex objects include linked lists, trees, and graphs.
Memory to store complex objects is typically dynamically allocated from an area of memory available to a program called a “heap.” More specifically, each data structure in the complex object, including the complex objects to which the complex object has pointers, is individually allocated from the heap and referenced by a pointer. Thus, a top-level data structure of a complex object includes pointers to secondarily allocated data structures. The dynamic memory allocation for a complex may be performed by a vendor-supplied operating system or run-time library call, such as malloc(3) on Unix operating system platforms, or by a user-supplied memory allocation routine that ultimately makes an independent call to a vendor-supplied memory allocation routine. This type of memory allocation typically results in the dispersion of a complex object over many non-contiguous areas of the heap, due to piecemeal allocation of the complex object and heap fragmentation after many allocations and deallocations.
For example, in
FIG. 6
, complex object p is created in step
600
by making n calls to a dynamic memory allocation routine called “alloc.” Complex object p uses five non-contiguous areas of memory in heap
610
, labeled p
1
, p
2
, p
3
, p
4
, and p
5
, respectively. In addition, another complex object q is created in step
602
, consuming four non-contiguous areas of memory in the heap, labeled q
1
, q
2
, q
3
, and q
4
. Heap
612
illustrates the heap
610
after memory has been allocated for complex object q.
When a complex object is no longer needed by the program, the individually allocated data structures of the complex object are deallocated or “freed” to allow the memory currently being used to store the complex object to be recycled (i.e. to be made available for other purposes). Thus, freeing a complex object involves freeing each allocated data structure belonging to the complex object. Deallocation of a complex object typically involves traversing the structure of the complex object by following pointers stored in the various data structures that make up the complex object. These pointers are followed to locate and deallocate the various non-contiguous areas of the heap used to store the data structures belonging to the complex parameter.
Since traversing a complex data structure is type-dependent, a deallocation routine is written for each complex object type. Referring again to
FIG. 6
, the complex object p is deallocated in step
604
by calling a type-specific deallocation routine called “P_free( )” with the complex object p passed in as a parameter. In response, the complex object p is traversed and each of the dynamically allocated memory areas that belong to p is freed by a separate call to free(p
n
). Heap
614
illustrates the state of heap
612
after memory for p is no longer allocated. Likewise, complex object q is deallocated by calling a different “Q_free( )” routine in step
606
. The “Q_free( )” routine traverses the data structures of complex object q and frees the individually allocated memory areas of the complex object with individual calls to free(q
n
). Heap
616
illustrates heap
614
after complex object q has been deallocated. Therefore, this “per-object” deallocation approach can be computationally expensive, and the computational cost for performing deallocation for a complex object increases with the complexity of the object.
A “per-client” memory management approach that may reduce the computational expense in deallocating complex objects is available in the Distributed Computing Environment (DCE) defined by the Open Software Foundation (OSF). According to this approach, an application programmer codes the following function call before a call to one or more client stub routines that return complex objects:
rpc_ss_set_client_alloc_free(rpc_ss_allocate, rpc_ss_free);
When called, this routine instantiates a new dynamic memory management system for the process and registers new memory allocation and deallocation routines. When the called client stub routines return complex objects, the client stub routines invoke the registered memory allocation routine, rpc_ss_allocate, to dynamically allocate memory for the complex objects within the new memory management system. When all of the complex objects are no longer needed outside the client stub routines that created them, the entire new memory management system may be torn down, releasing all the memory allocated for the complex objects. This process may be coded by an application program with a rpc_ss_disable_allocate( ) function call.
Referring the
FIG. 7
, an application programmer instantiates a new memory management system with a call to the enable routine in step
700
, which registers an appropriate memory allocation routine for the new memory management system and sets up an area
720
in heap
710
for allocating memory. In step
702
, when complex object p is instantiated, memory for complex object p is allocated by the registered memory allocation routine from memory area
720
as shown in heap
712
. When complex object q is created in step
704
, memory for complex object q is also allocated from memory area
720
as shown in heap
714
. Finally, after both complex object p and complex object q are no longer needed, the application programmer disables the new memory management system in step
706
by coding an appropriate disable call, thereby releasing the memory for all the allocated memory, including complex objects p and q. Heap
716
depicts heap
714
after the disable call routine is executed.
Although the process of tearing down the memory management system to release the memory for all the allocated complex objects can be less computationally expensive than the “per-object” deallocation approach, the “per-client” approach is less flexible because different complex objects typically have different and overlapping lifetimes. The lifetime of a complex object is the period from the creation of the complex object until the last use of the complex object. For example, referring back to
FIG. 7
, the lifetime
732
of complex object q commences at step
704
and ends when it is no longer needs at step
706
, where it can be safely deallocated. In this example, the lifetime
730
of complex object p commences at step
702
, extends beyond the creation of complex object q in step
704
, and ends some time before the end of the lifetime
732
of complex object q. Consequently, the lifetime
730
of complex object p overlaps the lifetime
732
of complex object q because complex object q was created after complex object p was created but before complex object p was terminated.
In this situation, the “per-client” memory management system cannot be taken down at the end of the lifetime
730
of complex object p because deallocation of memory area
720
will prematurely release the allocated memory for complex object q. In contrast, the “per-object” deallocation allows the complex object to be freed at the end of its lifetime. Referring again to
FIG. 6
, complex object p is freed in step
604
at the end of its lifetime
620
, and complex object q is freed in step
606
at the end of its lifetime
622
.
One conventional attempt to handle overlapping lifetimes is convert a complex object from a “per-client” memory managem

Affiliated with

Also associated with

Rating

Duration-based memory management of complex objects does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Duration-based memory management of complex objects, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Duration-based memory management of complex objects will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2505282