Electrical computers and digital processing systems: memory – Storage accessing and control – Control technique
Reexamination Certificate
1997-05-21
2004-10-12
Bragdon, Reginald G. (Department: 2188)
Electrical computers and digital processing systems: memory
Storage accessing and control
Control technique
C711S163000, C711S159000, C711S208000
Reexamination Certificate
active
06804754
ABSTRACT:
TECHNICAL FIELD
This invention relates, in general, to computer architecture and, in particular, to the management of compressed main memory in a computer system.
BACKGROUND ART
An emerging development in computer organization is the use of data compression in main storage or memory. In such systems, each cache line is compressed prior to being written into memory, using, for instance, a standard compression algorithm, such as that described by J. Ziv and A. Lempel, “A Universal Algorithm For Sequential Data Compression,” IEEE Transactions on Information Theory, IT-23, pp. 337-343 (1997), which is hereby incorporated by reference in its entirety. A convenient way to perform this 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.
A problem with such compression of the main memory contents is that the amount of space occupied by a set of cache lines (or pages) may vary with time, as changes to the data they contain changes the resulting compression ratio. This means that the amount of space required for a given set of data cannot be known in advance. As a result, it is possible that at some point, a cache line cannot be written back into memory because there is insufficient space. This results in an abnormal end of processing (i.e., a system crash).
One possible approach to this problem is to initiate page-outs whenever the amount of free space is judged to be too low. However, in some systems, there is no guarantee that the standard paging mechanism will complete page-outs in time to avoid abnormal ends.
Based on the foregoing, there is a need for an enhanced mechanism to prevent uncontrolled expansion of the memory contents in systems which, for example, utilize main memory compression.
SUMMARY OF THE INVENTION
The shortcomings of the prior art are overcome and additional advantages are provided through the provision of a method of managing compressed memory. A subset of items in memory, which is a portion of the contents of memory, is designated. Prior to accessing a particular item that has been referenced, the item is transferred into the subset, if it is not already a member of the subset.
In one example, the transferring of the item into the subset includes determining whether an estimate of free space of the memory is acceptable to allow the transfer, and performing the transfer, when the estimate is acceptable.
In a further example, the transferring includes changing information in one or more page tables to reflect the transfer. Additionally, in one example, the transfer includes removing another item from the subset. The removing also includes changing status information in one or more page tables to reflect the removal. The removal is performed without invalidating any cache lines of the removed item, which may be in a cache coupled to the memory.
In yet another embodiment of the invention, a method of managing compressed memory is provided, in which a subset of items in memory is designated, and access to a particular item, which is referenced, is provided when the item is a member of the subset. When the item is not a member of the subset, access is denied.
In another aspect of the invention, a system of managing compressed memory is provided. The system includes a subset of items in memory, in which the subset is a portion of the contents of memory, and means for transferring a referenced item into the subset, when the item is not a member of the subset, prior to accessing the item.
In another embodiment of the present invention, a system of managing compressed memory is provided. The system includes a subset of items in memory, and means for providing access to an item when the item is a member of the subset and denying access when it is not a member.
In yet another aspect of the present invention, an article of manufacture is provided. The article of manufacture includes a computer useable medium having computer readable program code means embodied therein for causing the managing of compressed memory. The computer readable program code means in the article of manufacture includes computer readable program code means for causing a computer to effect designating a subset of items in memory, in which the subset is a portion of the contents of the memory; and computer readable program code means for causing a computer to effect transferring a referenced item into the subset, when the referenced item is not a member of the subset, prior to accessing the item.
In another embodiment of the present invention, an article of manufacture including a computer useable medium having computer readable program code means embodied therein for causing the managing of compressed memory is provided. The computer readable program code means in the article of manufacture includes computer readable program code means for causing a computer to effect designating a subset of items in memory, and computer readable program code means for causing a computer to effect providing access to an item when the item is a member of the subset and denying access when it is not a member.
The present invention advantageously controls expansion of memory contents especially in those systems where such contents are compressed. Such control is provided by imposing some restrictions to references outside a specified subset M of the memory contents, and by controlling the transfer of pages (or cache lines) into the subset M, as a function of parameters, which may include, for example, estimates of the amount of free space and the net compression ratio for the contents of M.
Additionally, page-outs from M do not require that any cache contents be invalidated. Also, read-only access to pages outside M may not require any transfers into M. Further, the amount of free space is actually not determinable, since delays in obtaining this quantity from the compression controller represent time during which changes in this quantity may occur. Thus, the control mechanism described here involves the formulation of an dependency on bounds for the amount of available free space.
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: 4972338 (1990-11-01), Crawford et al.
patent: 5012408 (1991-04-01), Conroy
patent: 5598553 (1997-01-01), Richter et al.
patent: 5696926 (1997-12-01), Culbert et al.
patent: 5696927 (1997-12-01), MacDonald et al.
patent: 5699539 (1997-12-01), Garber et al.
patent: 5761536 (1998-06-01), Franaszek
Helen Custer, “Inside Windows NT”, Microsoft Press, pp 184-202; 1993.*
A.S. Tanenbaum, “Modern Operating Systems,” SEC. 3.4.5 The Clock Page Replacement Algorithm, Prentice Hall, Englewood Cliffs, N.J., pp. 111 (1992).
J. Ziv & A. Lempel, “A Universal Algorithm for Sequential Data Compression,” IEEE Transactions On Information Theory, IT-23, pp. 337-343 (1977).
D.A. Patterson & J.L. Hennessy, “Computer Architecture A Quantitative Approach,” 2nd Edition, Morgan Kaufmann, Publishers, Inc., San Francisco, CA, pp. 445-446 (1996).
Franaszek Peter Anthony
Hack Michel Henri Theodore
Schulz Charles Otto
Smith, III Thomas Basil
Bragdon Reginald G.
Heslin Rothenberg Farley & & Mesiti P.C.
Jennings, P.A. Derek S.
LandOfFree
Space management in compressed main memory does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Space management in compressed main memory, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Space management in compressed main memory will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3276862