Electrical computers and digital processing systems: multicomput – Computer-to-computer data routing – Least weight routing
Reexamination Certificate
1998-06-24
2001-12-04
Banankhah, Majid A. (Department: 2151)
Electrical computers and digital processing systems: multicomput
Computer-to-computer data routing
Least weight routing
C711S001000, C711S005000, C707S793000
Reexamination Certificate
active
06327606
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to computer systems and more particularly to memory management techniques for complex objects returned from a procedure call.
BACKGROUND OF THE INVENTION
A complex object is an instance of a data type or objected-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. 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.
A routine is a self-consistent set of computer instructions for performing particular tasks. Routines are also known as procedures, functions, and subroutines. The computer instructions can be low-level machine language instructions or high-level instructions in a programming language such as a C or C++ that are ultimately translated into machine language instructions, for example, by compiling or interpreting. Calling or invoking a routine involves passing arguments to the routines, if necessary, and causing the instructions to be executed. A routine may also return one or more results to the calling routine, and these results can be complex objects. Non-complex objects have a predetermined size, and space to hold the returned results of non-complex objects is reserved on the stack frame or register set for the calling routine. Memory management for stack-based objects is straightforward because the entire stack frame for a routine is automatically deallocated when execution of the routine is finished (i.e. when the routine “returns”). Thus, simple, stack-based objects do not need to be deallocated explicitly.
Complex objects, on the other hand, usually do not have a predetermined size; thus, complex objects that are returned from a routine are dynamically allocated from heap memory. The dynamic memory allocation 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, because, after many allocations and deallocation, the heap is fragmented. For example, in
FIG. 6
, a call to routine “f” in step
600
causes a complex object “p” to be returned. Complex object “p” comprises five non-contiguous areas of memory in heap
610
, each labeled “p.” In addition, a subsequent call to routine “g” in step
602
causes complex object “q” to be returned, consuming four non-contiguous areas of memory in the heap. Heap
612
illustrates the heap
610
after memory has been allocated for complex object “q”.
Unlike the memory occupied by the stack frame, which is automatically deallocated upon a routine's return, heap-allocated memory for a complex object must be explicitly deallocated when the complex object is no longer needed by the program. This deallocation 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. Referring again
FIG. 6
, the complex object “p” is deallocated 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 alloacted memory areas that belong to “p” are freed (step
604
). 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. 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, the following function call is made before calling 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 performed by a rpc_ss_disable_allocate( ) function call.
Referring the
FIG. 7
, a new memory management system is instantiated by calling 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 returned from function “f”, memory for complex object “p” is allocated by the registered memory allocation routine from memory area
720
as shown in heap
712
. When function “g” is called 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 new memory management system can be disabled in step
706
, 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
Banankhah Majid A.
Ditthavong & Carlson, P.C
Oracle Corp.
LandOfFree
Memory management of complex objects returned from procedure... 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 of complex objects returned from procedure..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Memory management of complex objects returned from procedure... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2577048