Electrical computers and digital processing systems: memory – Storage accessing and control – Memory configuring
Reexamination Certificate
2000-05-30
2004-01-20
Kim, Matthew (Department: 2186)
Electrical computers and digital processing systems: memory
Storage accessing and control
Memory configuring
C711S002000, C711S202000
Reexamination Certificate
active
06681305
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to computing system with hardware compression of main memory content, and more particularly to the management of the dynamically changing memory size that is due to hardware main memory compression.
BACKGROUND OF THE INVENTION
Data compression techniques are extensively used in computer systems to save storage space or bandwidth. Both hardware and software based compression schemes are used for storing data on magnetic media or for transmitting data over network links. Memory footprints of large number of applications show that main memory contents can be compressed by 2 to 1 or more in most cases. Only few applications' data, which are already compressed or encrypted, cannot be further compressed. Two to one compression effectively doubles the amount of memory at the same cost, or in cost sensitive applications gives the same amount of memory at ½ the cost.
Main memory compression is a technique that utilizes transparent, real-time, on-the-fly compression of data access to reduce the physical memory requirement or to expand the physical memory usage. Due to the variable length record problem that results from compressing data blocks or pages, random access of compressed pages of data was thought to be impractical until recently. However advances in parallel compression-decompression algorithms described in U.S. Pat. No. 5,729,228 coupled with improvements in silicon density and speed now makes main memory compression practical.
Shown in
FIG. 1
is a computer system that supports main memory compression in accordance with the current invention. It consists of one or a plurality of CPUs each with associated caches
100
, communicating over a bus
101
to the memory controller
112
. The compressed memory architecture adds one additional level to the conventional memory hierarchy. A distinction between “real” and “physical” addresses is made. Real addresses
104
are the conventional memory addresses seen on the processor chip's external bus. Physical addresses
105
are used for addressing the compressed physical memory. The memory controller typically embodies/controls an L3 cache
106
which looks to the CPUs just like memory. Further I/O device
103
addressing is controlled by the memory controller. The following terms are interchangeably used in the literature: “expanded memory” for the “real memory,” since compression increases the effective memory size and “compressed memory” for the “physical memory” backing this expanded memory.
In such systems the operating system manages the real memory space and is oblivious to the physical memory itself. The compression engine
107
within the memory controller chip compresses a cache line upon a cacheline store and decompresses upon a load. The various variable length data records of the compression stored in physical memory
102
is accessed through a real to physical address translation which are maintained as part of the compression state
108
. We expect the system and in particular the memory controller to export a set of utilization registers
109
that allow the operating system to monitor
110
the physical memory utilization. Optionally, the memory controller may have a set of threshold registers
109
that can be set and if physical memory utilization exceeds the threshold, the memory controller will issue an interrupt.
The compressability CR(t) of the data under the control of the operating system at any given time t determines how much real memory RM(t) the system can sustain at that time without exhausting the fixed amount of physical memory PM. Standard operating systems describe their real memory via a set of page frame descriptors. This is typically a fixed number. In general systems without main memory compression support, real memory is equal the physical memory. However in systems with main memory compression support, the memory management is governed by the following equation:
RM
(
t
)=
CR
(
t
)*
PM
(Eq. 1)
The effective real memory size, i.e. the number of pages that are handed out by the OS for applications and OS specific tasks (e.g. file system cache), depends on the current compression ratio CR(t) which may constantly change dependent on the various application states.
Standard operating systems have no means to dynamically adjust their real memory size, based on a constantly changing run time state, here the compression ratio CR(t). As the page frame descriptors have to be permanently accessible in memory, most OS allocate a fixed number of page frame descriptors at boot time and manage the memory through their usage. Hence, if the system were to be configured with a fixed ratio, then one must guarantee that the compression ratio will never fall below this fixed ratio otherwise the physical memory will be exhausted and the system will fail.
In order to take full advantage of main memory compression systems, a method is needed for effective virtual memory management within an operating system to dynamically adjust the expanded real memory size that the operating system considers for its operation, as a function of the physical memory utilization at a given time, such that physical memory will never be exhausted. In other words, physical memory utilization shall never exceeds 100%.
In the prior art, there are several patents and publications that utilize software compression techniques to increase free physical memory availability, rather than incurring page-out operations. They pose some relevance to this invention, although neither of the systems deals with main memory compression and therefore encounters the dynamic real memory sizing and physical memory exhaustion problem pertinent to systems with main memory compression.
U.S. Pat. No. 5,559,978 describes a method for increasing the efficiency of a virtual memory system by selective compression of RAM memory content. In particular, this patent identifies non-critical regions of memory (e.g. least frequently accessed memory pages), combines them and compresses them via well known software compression techniques. The combined portions occupy less physical memory resources, thus enlarging the pool of available memory resources. Compressed pages are unmapped from an applications virtual memory translation table and upon access of the virtual address, the virtual memory system, must decompress the compressed page into new pages and remap the decompressed pages to the access virtual address. By compressing non-critical pages and thus increasing physical memory availability, page-out operations are avoided.
U.S. Pat. No. 5,544,349 describes a method for reducing paging activity by dividing the memory into two areas, active list portion and free list portion. When a page is taken away from a process, the mapping of that page in the process page table is removed, the page is compressed into a different container and then placed on the free list. At subsequent access to the data by the process, the page fault handler searches the free list and if it finds the page compressed, it will decompress it into a new frame and remap that page. In essence, this patent is a more limited case of U.S. Pat. No. 5,559,978 where a non-critical region is defined to be a page on the free list.
Wilson et al. in “The Case for Compressed Caching in Virtual Memory Systems” describe a different software approach that utilizes compression for reducing paging activity, but does not require modifications to the operating system. It is based on a compressed virtual paging filesystem. This requires that a part of the physical memory is set aside for the compressed paging filesystem. The virtual management system (VMM) of the operating system decides what pages to page out and hands them over the paging module. But rather than sending the page to disk, the page is compressed within the paging filesystem and only if the paging module exhausts its dedicated memory, it will start paging out compressed pages, thus potentially reducing the number of page-out/page-in operations.
Note that the prior art does
Abali Bulent
Franke Hubertus
Herger Lorraine M.
Poff Dan E.
Saccone, Jr. Robert A.
Anderson Matthew D.
Cameron Esq. Douglas W.
International Business Machines - Corporation
Kim Matthew
Scully Scott Murphy & Presser
LandOfFree
Method for operating system support for memory compression does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method for operating system support for memory compression, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for operating system support for memory compression will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3258067