Electrical computers and digital processing systems: memory – Storage accessing and control – Memory configuring
Reexamination Certificate
2000-07-28
2002-06-04
Peikari, B. James (Department: 2186)
Electrical computers and digital processing systems: memory
Storage accessing and control
Memory configuring
C711S173000, C711S172000, C711S171000, C707S793000
Reexamination Certificate
active
06401181
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates generally to the field memory usage and organization in computer systems, and more specifically to a dynamic physical memory allocation and memory recovery system.
2. Discussion of the Prior Art
In computer systems it is customary that there be one-to-one correspondence between the memory address produced by the processor and a specific area in the physical memory of the system. It is an error for the processor to request access to an address which does not have an associated physical memory area. This limits the operating system and applications to an address space determined by the actual physical memory installed in the system. Modern computer systems have overcome this limitation through the use of virtual memory which implements a translation table (TT) to map program addresses to real memory addresses.
With virtual memory the program works in an address space limited only by the processor architecture. It is a function of the operating system to ensure that the data and code a program is currently using is in main memory and that the translation table can map the virtual address to the real address correctly. In a virtual memory system the allocation of memory is most commonly performed by the operating system software. This requires an interrupt of the instruction sequence so that the privileged kernel code can allocate physical memory to the area being accessed so that normal program flow can continue without error. This interrupt and the kernel processing to allocate physical memory requires a significant amount of processing time and upsets the normal pipelining of instructions through the CPU.
There currently exist schemes for reducing operating system process interruptions. For instance, the reference entitled “Design and Analysis of Internal Organizations for Compressed Random Access Memories” by Peter A. Franaszek and John T. Robinson, IBM Research Report RC21146(94535), dated Oct. 28, 1998, describes a low level main memory design for storing compressed data that includes a directory portion and a collection of fixed size blocks which are used to store lines in compressed format. In the memory storage scheme described herein, highly compressible lines may be stored entirely within a directory entry; otherwise, the directory entry points to one or more of the fixed size blocks which are used to store the line in compressed format. The system further makes use of page tables which translate virtual addresses to real addresses which correspond to the location in the directory of the directory entry for the line and which includes information pertaining to blocks holding a compressed line. Specifically, the information in a directory entry includes flags, fragment combining information, and, assuming fixed size entry structure pointers to one or more fixed size blocks. On a cache miss, the memory controller and decompression hardware finds the blocks allocated to store the compressed line and dynamically decompresses the line to handle the miss. Similarly, when a new or modified line is stored, the blocks currently allocated to the line are made free (if the line currently resides in the RAM), the line is compressed, and then stored in the RAM by allocating the required number of blocks.
Furthermore, U.S. Pat. No. 5,761,536 is directed to a memory organization technique utilizing a compression control device for storing variable length objects (compressed memory) in fixed-size storage blocks by enabling fixed size storage blocks to receive remaining portions (leftover compressed memory pieces or fragments) of variable length objects that take up less than a full fixed-size storage block. The system thus reduces memory fragmentation.
U.S. Pat. No. 5,864,859 is directed to a compression store addressing technique for storing variable length objects (compressed lines, each representing, e.g., ¼ of a page) in fixed size blocks so that accessing an individual line may be accomplished quickly and with little change to existing software. In particular, the beginning of any line within a page may be accessed with a single pointer plus an offset. Associated with the compression store is a list of free or available blocks (free list) which is accessed for enabling variable length object storage.
Notwithstanding the foregoing prior art systems, it would be highly desirable to provide a mechanism that enables the physical memory to be dynamically allocated in a manner such that the interruption in program flow is eliminated.
Furthermore, as a common task of memory managers such as those found in modern operating systems is to control pools of memory so that the various processes and users share the system resources fairly, it would be highly desirable to provide a mechanism for facilitating the management of these memory pools.
SUMMARY OF THE INVENTION
It is an object of the invention to provide a mechanism that enables computer system physical memory to be dynamically allocated in a manner such that the interruption in program flow can be eliminated.
It is another object of the invention to provide a mechanism under the control of hardware memory controller circuitry that enables computer system physical memory to be dynamically allocated without computer operating system execution time overhead.
It is a further object of the present invention to provide an indexing and dynamic memory allocation mechanism in the main memory addressing path, that exploits the spatial efficiencies of computer main memory indexing schemes to enable operating system and applications to be provided with real memory address spaces larger than the installed physical memory resources.
It is yet another object of the invention to provide in a system that enables computer system physical memory to be dynamically allocated, a mechanism for facilitating the management of these memory pools by grouping real memory pages into classes.
Thus, according to the principles of the invention, there is provided, a computing system implementing a processor device for generating real addresses associated with memory locations of an associated physical memory during memory read and write operations, the system comprising: a plurality of memory blocks in the physical memory storage for storing data, each memory block partitioned into one or more contiguous sectors; an index table structure in the physical memory having entries for associating a real address with a memory block of the physical memory, the table accessed for storing data in one or more allocated sectors for memory read and write operations initiated by the processor; and, a control device associated with the physical memory for dynamically allocating sectors for an associated memory block in an index table entry, and further calculating an offset of the real address in the memory block for indexing into an allocated sector of the memory block for a read and write operation. In this manner, processor memory read and write operations are expedited without external system interruption.
Such a method and apparatus of the invention may be implemented in the design of the compressed memory management systems for server devices, PCs and the like, implementing compression/decompression algorithms.
REFERENCES:
patent: 4121286 (1978-10-01), Venton et al.
patent: 5491808 (1996-02-01), Geist. Jr.
patent: 5761536 (1998-06-01), Franaszek
patent: 5802341 (1998-09-01), Kline et al.
patent: 5864859 (1999-01-01), Franaszek
patent: 5991775 (1999-11-01), Beardsley et al.
patent: 6247105 (2001-06-01), Goldstein et al.
“Research Report—Design Analysis of Internal Organizations for Compressed Random Access Memories”, by Peter A. Franaszek, et al., Computer Science/Mathematics, IBM Research Report RC 21146 (94535), Oct. 28, 1998, pp. 1-30.
Franaszek Peter A.
Hack Michel
Schulz Charles O.
Smith, III T. Basil
Tremaine R. Brett
International Business Machines - Corporation
Peikari B. James
Tassinari, Esq. Robert P.
LandOfFree
Dynamic allocation of physical memory space does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Dynamic allocation of physical memory space, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Dynamic allocation of physical memory space will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2931291