Electrical computers and digital processing systems: memory – Storage accessing and control – Memory configuring
Reexamination Certificate
1999-01-06
2001-08-21
Lane, Jack A. (Department: 2185)
Electrical computers and digital processing systems: memory
Storage accessing and control
Memory configuring
Reexamination Certificate
active
06279092
ABSTRACT:
FIELD OF THE INVENTION
This invention relates in general to operating systems for computers, and in particular to managing compressed main memory in a computer system.
BACKGROUND OF THE INVENTION
An emerging development in computer organization is the use of data compression for the contents of main memory, that part of the random access memory hierarchy which is managed by the operating system (“OS”) and where typically the unit of allocation is a page.
In compressed memory systems, a page may occupy a variable amount of physical memory space. For example, as described in the aforementioned related patent application, pages occupy or share a variable number of fixed size blocks; pages may be of nominal 4K size and blocks of size 256 bytes. Generally, the number of such blocks occupied by a page will vary with its contents, due to changes in compressibility.
Typically, each cache line is compressed prior to being written into memory, using a standard sequential or a parallel compression algorithm. Examples of compression algorithms include Lempel-Ziv coding and its generalizations, Huffman coding and arithmetic coding. See, for example, J. Ziv and A. Lempel, “A Universal Algorithm for Sequential Data Compression,” IEEE Transactions on Information Theory, IT-23, pp. 337-343 (1977), which is hereby incorporated by reference in its entirety. A parallel approach is described in co-pending (allowed) U.S. patent application Ser. No. 08/498,948, entitled Parallel Compression and Decompression Using a Cooperative Dictionary, by Franaszek et al., filed on Jul. 6, 1995 (“Franaszek”). The Franaszek patent application is commonly assigned with the present invention to IBM Corporation, Armonk, N.Y. and is hereby incorporated herein by reference in its entirety. A convenient way to perform this compression is by automatically compressing the data using special-purpose hardware, with a minimum of intervention by the software or operating system. This permits compression/decompression to be done rapidly, avoiding what might otherwise be long delays associated with software compression/decompression.
Changes to a page stored in main memory occur on write backs from the cache. A changed cache line may require a larger number of blocks upon write back, than previously. If there are an insufficient number of free blocks to hold the changed line, the system abends. Thus, there is a need to maintain adequate free space under fluctuating compression efficiencies. The present invention addresses these needs.
Copending patent application Ser. No. 09/021,333 discloses a method for preventing system abends. That method requires that the hardware compression controller issue an emergency interrupt when the amount of physical free memory drops below a threshold T
0
(blocks).
T
0
is determined to be large enough so that physical memory cannot expand by more than T
0
blocks during the process of stopping all processing except that required to free up a sufficient amount of memory (by zeroing pages for which a valid copy exists on disk, and/or paging out pages to disk and then zeroing them) to permit continued operation.
The present invention also requires generating an interrupt but improves upon that method by being easier to implement.
SUMMARY OF THE INVENTION
Accordingly, the present invention is directed to an improved method, system, and a computer program storage device (e.g., including software embodied on a magnetic, electrical, optical, or other storage device) for management of compressed main memory allocation and utilization. The present invention has features which advantageously avoid system abends or inefficient operation that would otherwise result.
In accordance with this invention, we identify 3 types of addresses associated with a page: a virtual address, a real address, and a physical address. The OS is responsible for converting virtual addresses to real addresses via usual memory management techniques.
The memory controller is responsible for converting real addresses to the physical addresses where the compressed data are actually stored. We assume that the memory controller has the capability to store a page either compressed, or uncompressed.
Depending on the characteristics of the controller, this may be done either:
1. on a per page basis via an indicator bit that is settable by the OS
2. on a range of real addresses, i.e., all real addresses in a certain range (or ranges) are stored uncompressed and all other pages are stored compressed.
We further assume that the hardware is capable of separately counting the number of blocks that are stored in the compressed and uncompressed regions; we refer to these counts as NC and NU, respectively. If, for example, there are 16 256 byte blocks per 4K byte page, then NU=16 * the number of pages allocated uncompressed. These counts can be made available to the OS upon request to the hardware.
Using one of the above mechanisms, the OS assigns pages in the kernel (or a specified subset of the kernel) to be uncompressed. For example, in implementing 2 above, many OS's assign the kernel virtual addresses in a fixed, pre-determined and known range. Thus a request for a kernel page may be identified by the virtual address into which the real address is mapped. Thus, upon seeing a request for a virtual address in the kernel's virtual address range, the OS can assign a real address in the uncompressed range. By making this real address range at least as large as the kernel's virtual address range, any such request for a kernel page can always be satisfied by a page with a real address in the required range.
Alternatively, specific requests for kernel pages can be tagged when the request is made, thereby indicating that the page should be uncompressed. As such pages are already uncompressed, they cannot expand.
In a system with compressed main memory, the invention prevents system abends due to a deterioration in the compression ratio. The operating system identifies certain pages as being in a critical part of the kernel. These critical pages are either left uncompressed, or are compressed but their aggregate compression ratio is accounted for separately. The memory controller issues an emergency interrupt when the amount of free space drops below a certain level. The system responds to the interrupt by creating new free space (by writing pages to disk, if necessary, and zeroing them).
Additional features and advantages are realized through the techniques of the present invention. Other embodiments and aspects of the invention are described in detail herein and are considered a part of the claimed invention.
REFERENCES:
patent: 4646312 (1987-02-01), Goldsbury et al.
patent: 4747044 (1988-05-01), Schmidt et al.
patent: 4914570 (1990-04-01), Peacock
patent: 5490260 (1996-02-01), Miller et al.
patent: 5940871 (1999-08-01), Goyal et al.
Franaszek Peter A.
Heidelberger Philip
Poff Dan E.
International Business Machines - Corporation
Lane Jack A.
Scully Scott Murphy & Presser
Tassinari, Jr., Esq. Robert P.
LandOfFree
Kernel identification for space management in compressed... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Kernel identification for space management in compressed..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Kernel identification for space management in compressed... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2488008