Electrical computers and digital processing systems: memory – Address formation – Address mapping
Reexamination Certificate
1998-12-01
2002-10-22
Verbrugge, Kevin (Department: 2187)
Electrical computers and digital processing systems: memory
Address formation
Address mapping
C711S209000
Reexamination Certificate
active
06470436
ABSTRACT:
There are no Cross References to Related Applications.
There is no Federally Sponsored R & D related to this application.
There is no Microfiche Appendix related to this application.
BACKGROUND OF THE INVENTION
This invention relates to efficiently managing the dynamic allocation, access, and release of memory used in a computational environment. This memory may be used to store data or commands for a computational unit, such as a computer. This invention particularly applies to memory used in typical computational environments in which high utilization rates impair the performance of the computational unit, largely due to the need for memory management functions such as compaction and garbage collection, on behalf of the applications. More particularly, this invention relates to dynamic memory management, in which memory allocations and releases, as well as housekeeping functions in general, do not have substantially deterministic responses during execution of an application of the computational unit in the prior art.
Historically, memory used in a computational environment, such as a computer, has been expensive and of questionable reliability. The general belief was that this memory should be utilized or “packed” as fully as possible. Methods for the efficient, here used in the sense of fully utilized, use of memory became standard, and have not been seriously questioned before this invention, though attempts have been made to reduce the impact on performance of such usage, and to make the operations more deterministic. Kevin D. Nilsen, U.S. Pat. No. 5,687,368, teaches the conventional view of the methods for efficient memory implementation. The '368 patent addresses a major shortcoming of the prior art, which is loss of computational performance due to the need for memory management, also called housekeeping, to achieve efficient use of memory. The '368 patent teaches the use of a hardware implementation to alleviate the problem of loss of performance in the computational unit. However, the '368 patent does not teach reducing or eliminating housekeeping functions or mapping large, sparsely populated logical memory address space onto smaller, denser physical memory address space as in this invention. The '368 patent also does not teach making housekeeping functions more deterministic in the way or to the extent that the present invention does. The traditional methods of the prior art, even when implemented in a hardware structure like that of the '368 patent, copy data from memory location to memory location in order to compact and “garbage collect” the data. Garbage collection is a term used to describe the processes in a computer which recover previously used memory space when it is no longer in use. Garbage collection also consists of re-organizing memory to reduce the unused spaces created within the stored information when unused memory space is recovered, a condition known as fragmentation. The prior art inherently reduces the performance of the computational unit, due to the need to perform these operations and the time consumed thereby. Further, these operations are inherently not substantially deterministic, since the iterative steps required have no easily determinable limit in the number of iterations. Basic assumptions in the prior art have been that memory should be optimized with respect to the utilization of the memory address space, rather than of the actual memory itself. Reliability was also considered to be a factor in utilizing available memory space as efficiently as possible. As a consequence, the atomic memory management data size was set in small blocks; usually 1024 bytes. Memory management systems (MMS) of the prior art then searched for memory not in use, often down to the individual block, in order that memory space could be freed as expeditiously and to as small a unit size as possible. This process is one of the housekeeping functions, and is commonly referred to as “garbage collection”. This process often requires the use of substantially indefinite numbers of iterations, making the loss in performance substantially not deterministic. The small size of the atomic memory unit often causes small pieces of memory, which are being used, to be interspersed with unused, or “garbage” locations, a process known as “fragmentation” of memory. Since this could result in significant problems in accessing streams of data due to the necessity to access small locations which are not contiguous, a technique known as “compaction” or “defragmentation” has been employed. This causes special commands and routines to be required and frequently used. In the UNIX operating system environment, when programming in ANSI C, for example, function calls that directly or indirectly invoke these representative routines by allocating and releasing dynamic memory are known as “malloc( )”, “calloc( )”, “realloc( )”, and “free( )”. Again, these functions and the directly or indirectly invoked representative routines require a substantially indefinite number of iterations, and are substantially not deterministic. Additionally, to aid the functions above and to better utilize available memory, various concepts such as “relocatable memory” were developed and implemented, thereby allowing for more efficient routines for memory management functions such as compaction and defragmentation. Memory management functions, using relocatable memory, work by copying memory atomic units (objects) from one location in memory to another, to allow garbage fragments between valid objects to be combined into larger free memory areas. However, while improving the flexibility of the allocation process, relocatable memory also requires indefinite numbers of iterations, and further makes the time required for housekeeping functions substantially not deterministic.
The present invention recognizes the fact that computational systems are becoming larger, and garbage collection is becoming less deterministic, more complex, and requires a substantial amount of computational time to be expended that would otherwise be available for productive work by the computational unit.
SUMMARY OF THE INVENTION
It is an object of this invention to map a large, normally contiguous, section of the logical memory address space used to store dynamically created objects accessed by a computational unit such as a computer to a smaller physical memory address space. The need for housekeeping functions is reduced and may be preferably eliminated. Examples of housekeeping functions hereby reduced or eliminated are garbage collection and memory compaction. It is a further object of this invention to translate or map the addresses of a computational unit such as a computer, which may have a very large and sparsely populated logical memory address space, to the much smaller and denser physical memory address space of a physical memory. The physical memory address space of this invention is preferably of fixed size and statically located. Because housekeeping functions, which reduce system performance, are reduced and can be eliminated, the computational unit performance is thereby improved, and the execution of dynamic memory management processes becomes deterministic.
In accordance with a first embodiment of the present invention, a computational memory consisting of fixed sized modules of physical memory is formed. This is also referred to as “private memory address space” herein. The associated physical memory is interfaced to a CPU and the “logical memory address space” the CPU controls by means of a memory address mapping interface, referred to herein as a Dynamic Memory Manager (DMM).
The logical memory address space in today's microprocessor based systems is defined by the size of the address bus. Large microprocessor systems tend to be 32 bits or 64 bits wide. Note that 32 bits can define a space of nearly 4.3 billion bytes (2**32) and 64 bits can define a space of nearly 185,000 trillion bytes (2**64). In contrast, the physical memory connected to the same system substantially ranges in size
Croft Walter E.
Henderson Alex
Fast-Chip, Inc.
Fenwick & West LLP
Verbrugge Kevin
LandOfFree
Eliminating memory fragmentation and garbage collection from... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Eliminating memory fragmentation and garbage collection from..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Eliminating memory fragmentation and garbage collection from... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2922587