Abstract:
A computer system having a main memory for storing data in a compressed format and a processor cache for storing decompressed data, a method for converting the data of said main memory from compressed to uncompressed state, comprising the steps of reducing used portions of said main memory to a target value; disabling a compressor used for compressing the uncompressed data; decompressing said compressed data of said main memory; moving said decompressed data to physical addresses equal to real addresses; and releasing the memory occupied by a compressed memory director and data structures used in steps a. to d.

Description:
BACKGROUND  
         [0001]    1. Field of the Invention  
           [0002]    The present invention relates to a processing system and method for converting contents in a memory from one format to another; more particularly, a system and method for converting compressed contents to uncompressed format (morphing) or vice versa while concurrently removing the operating system and regularity applications.  
           [0003]    2. Discussion of Related Art  
           [0004]    In a paged operating system, the virtual address space, namely, the collection of addresses addressable by a program, is divided into pages, with collections of contiguous virtual addresses having fixed lengths. Typically a page contains 4 Kb. The virtual address space of a program is in general much larger than the available physical memory. The operating system provides a set of functionalities supporting this feature, functionalities that are collectively referred to as virtual memory manager. To support virtual address spaces larger than the physical memory, virtual memory managers stores virtual pages both in memory and on tertiary store, usually hard disks. When a virtual page is accessed, and is not in main memory, it is read from disk (page-in operation). If there is no available physical space for the page being read from disk, another virtual page is written to disk (page-out operation) and its space is released. When a virtual page is read from disk, it is assigned a starting real address, namely, an address as seen from the processor. The real memory (the address space of the processor) is divided into a collection of contiguous and pairwise disjoint real address ranges, having the same size as a logical page. These are called page frames. Hence, when a logical page is read from memory, it is stored within a page frame. The translation between logical and real pages relies on a directory structure divided into pages called page tables. Each logical page has a unique entry in a page table, called page table entry, which contains the starting real address of the page frame containing the page, or the position on disk, if the logical page is on tertiary store. Free page frames are managed using a separate data structure.  
           [0005]    The set of page frames used by processes (including those of the OS) is managed by appropriate modules of the operating system. Most operating systems provide virtual memory management, namely, offer each process an address space which is commonly significantly larger than the available physical memory. To accomplish this, the operating system maintains only a fraction of the pages of each process in memory, and stores the others on mass storage, such as hard disks. Hence a physical page, which is a set of contiguous physical addresses, can contain a virtual page of a process, or can be temporarily unused. A physical page is commonly called a page frame. When a process issues an operation on a page which is not in memory, the page is copied from disk into an unused page frame (similarly, if the page is a new one, that is, it is not stored on disk, an unused page frame is allocated to it). A page frame can be unused for at least three reasons: (1) because it has never been used since the machine was last started; (2) because the process that last used it has terminated; and (3) because the operating system frees it. In the last case, the operating system is also responsible to ensure that a copy of the content of the page frame to be freed is present on disk. Usually, mechanisms exist to detect if the content of the page frame has been modified since it has been allocated or copied from disk. If the page frame is unchanged, there is no need to copy it back. If the page frame content has been modified, it must be copied to disk, otherwise there is no need to do so.  
           [0006]    An emerging development in computer organization is the use of data compression in the main memory of a computer system. The data in the main memory is stored in a compressed format.  
           [0007]    [0007]FIG. 1 depicts an exemplary processing system having compressed contents in memory. In FIG. 1, a central processing unit (CPU) 102 reads data to and writes data from a cache  104 . Cache misses and stores results it reads from and writes to a compressed main memory  10  by means of a compression controller  106 . The real memory, namely, the set of processor addresses that correspond to data stored in memory, is typically divided into a number of pairwise disjoint segments corresponding to a fixed number of contiguous processor addresses. Pairwise disjoint means that each real address belongs to one and only one such segments. These segments are referred to as memory lines. Memory lines are the unit of compression. A memory line stored in the compressed memory is compressed and stored in a variable number of memory locations, which depends on how well its content compresses.  
           [0008]    U.S. Pat. Nos. 5,761,536 and 5,729,228 disclose computer systems where the contents of main memory are compressed.  
           [0009]    Referring again to FIG. 1, the compressed memory is divided into two parts: a data portion  108  and a directory  107 . The data portion is divided into pairwise disjoint sectors, which are fixed-size intervals of physical memory locations. For example, a sector may consist of 256 physical bytes having contiguous physical addresses. The content of a compressed memory line is stored in the minimum possible number of physical sectors. The physical sectors containing a compressed line need not have contiguous physical addresses, and can be located anywhere within the data portion of the compressed main memory. The translation between the real address of byte and the address of the physical sector containing it is performed via the directory  107 .  
           [0010]    [0010]FIG. 2 shows further details to better understand the operation of the compressed memory. The processor cache  240  contains uncompressed cache lines  241  and a cache directory  242 , which stores the real address of each cache line. In the following discussion, an assumption is made that a cache line has the same size as a memory line (the unit of compression). Upon a cache miss, the cache requests the corresponding line from memory, by providing real address  270  that caused the miss. The real address is divided into two parts: the log 2 (line length) least significant bits are the offset of the address within the line, where log 2 ( ) is the logarithm in base  2 . The other bits are used as index in the compressed memory directory  220 , which contains a line entry for each line in the supported real address range. Address A 1  ( 271 ) corresponds to line entry  1  ( 221 ), address A 2  ( 272 ) corresponds to line entry  2  ( 222 ), address A 3  ( 273 ) corresponds to line entry  3  ( 513 ) and address A 4  ( 274 ) corresponds to line entry  4  ( 514 ), and so on. Different addresses are used in the example to show different ways of storing compressed data in the compressed main memory. In this illustration, the line having address A 1  compresses very well (for example, a line consisting of all zeros). Such line is stored entirely in the directory entry  221 , and does not require memory sectors. The line at address A 2  compresses less well, and requires two memory sectors  231  and  232 , which are stored in the data section  230 . Line entry  222  contains pointers to the memory sectors  231  and  232 . Note that the last part of memory sector  232  is unused. The line having address A 3  requires 3 memory sectors,  233 ,  234  and  235 . The space left unused in sector  235  is large enough to store part of the compressed line having real address A 4 , which in turn uses sector  236  and part of 235. The lines at addresses A 4  and A 3  are called roommates. The compressor is used when so called dirty lines (e.g., lines previously used) in the cache are written back into memory. Upon a cache writeback, a dirty line is compressed. If it fits in the same amount of memory it used before the writeback, it is stored in place. Otherwise, its is written in the appropriate number of sectors. If the number of required sectors decreases, the unused sectors are added to a free-sector list. If the number of required sectors increases, they are retrieved from the free-sector list.  
           [0011]    [0011]FIG. 3 shows possible organizations of the entries in the compression directory  220 . The figure illustrates three different line organizations. Entry  1  ( 306 ) contains a set of flags ( 301 ), and the addresses of 4 sectors. If the line size is 1024 bytes, and the memory sector size is 256, the line requires at most 4 sectors. Entry  2  ( 307 ) contains a set of flags, the address of the first sector used by the line, the beginning of the compressed line, and the address of the last sector used by the line. If the line requires more than 2 memory sectors, the sectors are connected by a linked list of pointers (namely, each memory sector contains the address of the subsequent one). Entry  3  contains a set of flags, and a highly compressed line, which compresses to 120 bits or less. The flags in the example are flag  302 , indicating whether the line is stored in compressed format or uncompressed, flag  303  indicating if the line is highly compressible and is stored entirely in the directory entry, flag  304  (2 bits) indicating how many sectors the line uses, flag  305  (4 bits), containing the fragment information), namely what portion of the last used sector is occupied by the line (this information is used for roommating).  
           [0012]    The maximum compression ratio achievable in a system with memory compression that relies on the described compressed-memory organization depends on the size of the directory: the maximum number of real addresses is equal to the number of directory entries in the directory. Limiting the size of the directory to yield, say, a 2:1 compression is suboptimal for most computer applications, where higher compression ratios are usually observed. On the other hand, a large directory occupies a substantial amount of physical memory, which can impair the system performance if the content of memory happens to be poorly compressible. The memory compression schemes described in the art have a directory size which is fixed when the machine is booted, and cannot be changed while the machine operates.  
           [0013]    The cost of compressing and decompressing (i.e., the latency) is partially hidden by the cache. A large cache almost entirely hides these latencies for most typical workloads. However, for non-cache-friendly workloads, that do not have a strong locality of memory references, the cache cannot hide the latencies, and the performance of a system with memory compression is significantly worse than that of an analogous system without memory compression. If the characteristics of the workload are known a-priori, the memory compression scheme described in the art allow the computer system to be started and operate in uncompressed mode (as a standard computer, where real addresses correspond to physical address). However, if the machine is started in uncompressed mode, it cannot be converted back to a compressed mode without restarting it, and vice versa.  
           [0014]    When memory compression is used in a paged memory system, the number of page frames that can be used by processes varies dynamically. The page frames that can be used by processes are referred to herein as usable page frames. If the compressibility of the data increases, the number of usable page frames can be increased. Similarly, if the compressibility drops, more page frames can be made unavailable.  
           [0015]    In a computer system where the content of main memory is kept in compressed format, the translation between a real address as produced by the processor and the physical address of the memory cells containing the compressed data is performed using a directory, referred to herein as compressed-translation table (CTT). Data is compressed and stored into memory upon cache write-backs. Upon cache misses, the content of memory is decompressed. The latency of the decompression process are hidden by using a large cache memory.  
           [0016]    When the memory contains poorly compressible data, the number of different page frames in memory (the size of the real memory) can be smaller than the number of physical pages, and the performance of the compressed-memory system might be lower than that of a traditional system having the same amount of physical memory, due to an increase in page faults. When the workload is cache-unfriendly, namely, when it causes a large number of cache misses, the cache does not hide the decompression latency quite as well, and the performance of the system supporting memory compression suffers. If cache-unfriendly workloads are run for long periods of time, the reduced performance of the system becomes visible to the user.  
           [0017]    The above examples of cases where running the system in traditional mode with the content of memory uncompressed and without the additional cost of real-to-physical translation can be beneficial. The hardware of systems supporting memory compression therefore can also operate in traditional uncompressed mode. Typically, the decision of whether to run the system in compressed-memory mode or in traditional mode is based on knowledge of the intended workload or of the data. Once the decision is taken, the system runs in compressed-memory or uncompressed-memory mode until the next time it is rebooted: the mode of operation cannot be changed while the system is computing. A need therefore exists for a system and method for switching the mode of operation from compressed-memory to uncompressed-memory or vice versa without CTT, does not require either rebooting the system or halting operation of applications, or capable of dynamically changing the size of the compressed-memory directory.  
         SUMMARY OF THE INVENTION  
         [0018]    A computer system having a main memory for storing data in a compressed format and a processor cache for storing decompressed data, a method for converting the data of said main memory from compressed to uncompressed state, comprising the steps of reducing used portions of said main memory to a target value; disabling a compressor used for compressing the uncompressed data; decompressing said compressed data of said main memory; moving said decompressed data to physical addresses equal to real addresses; and releasing the memory occupied by a compressed memory director and data structures used in the above steps.  
           [0019]    A computer system in which main memory contents can be maintained in a compressed format and in uncompressed format, a method for converting the operating mode from uncompressed mode to compressed mode, not requiring stopping and restarting said computer system, comprising the steps of selecting a size for the compressed memory directory; removing the content of the portion of said main memory selected to contain said compressed memory directory; initializing said compressed memory directory, and enabling compressed-main memory mode.  
           [0020]    A computer system having a main memory for maintaining contents in a compressed format and a compressed memory directory, a method for increasing the size of the compressed-memory directory while not requiring stopping and restarting said computer system, comprising the steps of selecting a new size for the compressed memory directory; removing the content of the portion of said main memory selected to contain the additional portion of said compressed memory directory; and initializing the expanded portion of said compressed-memory directory.  
           [0021]    A device for storing codes executable by a processor in a computer system for performing a method for decreasing the size of compressed-memory director of a compressed contents in a main memory in the computer system, the method comprising the steps of selecting a new size for the compressed memory directory to contain entries for A page frames; reducing the number of page frames to said value M; and changing the address of page frames having addresses outside the range addressable by said compressed-memory directory with said selected new size, to address within said addressable range.  
           [0022]    A computer system having a main memory for storing data in a compressed format and a processor cache for strong decompressed data, a method for converting the data of said main memory from compressed to uncompressed state, comprising the steps of reducing used portions of said main memory to a target value; disabling a compressor used for compressing the uncompressed data; decompressing said compressed data of said main memory; moving said decompressed data to physical addresses equal to real addresses; and releasing the memory occupied by a compressed memory director and data structures used in steps a. to d. 
       
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
       [0023]    [0023]FIG. 1 shows a conventional computer system having compressed main memory.  
         [0024]    [0024]FIG. 2 shows a memory structure of the computer system of FIG. 1.  
         [0025]    [0025]FIG. 3 shows a structure of the entry of a memory directory in the computer system of FIG. 1.  
         [0026]    [0026]FIG. 4 shows a method for morphing the content of main memory from compressed to decompressed state without interrupting the normal operation of a computer system according to an embodiment of the present invention.  
         [0027]    [0027]FIG. 5 shows a method for reducing the used portion of compressed main memory to a desired value.  
         [0028]    [0028]FIG. 6 shows a method for changing the real addresses of pages used by processes to allowable regions and to decompress the content of the pages.  
         [0029]    [0029]FIG. 7 shows a method for changing the real addresses of pages used by processes to allowable regions and to decompress the content of said pages.  
         [0030]    [0030]FIG. 8 shows a method for moving the content of memory so that real addresses equal physical addresses.  
         [0031]    [0031]FIG. 9 shows a method for converting the content of main memory from uncompressed to compressed without interrupting the normal operation of a computer system according to a preferred embodiment of the present invention.  
         [0032]    [0032]FIG. 10 shows a method for addressing the content of main memory while the content is converted from uncompressed to compressed, and details of compressing the content without interrupting the normal operation.  
         [0033]    [0033]FIG. 11 shows a method for increasing the size of the memory compression directory without interrupting normal operation.  
         [0034]    [0034]FIG. 12 shows a method for decreasing the size of the memory compression directory without interrupting normal operation.  
         [0035]    [0035]FIG. 13 shows an implementation of an embodiment of the present invention.  
         [0036]    [0036]FIG. 14 shows an apparatus for removing free sector list sectors. 
     
    
     DETAILED DESCRIPTION OF PREFERRED EMBODIMENTS  
       [0037]    One aspect of preferred embodiments of the present invention dynamically changes the size of the real space of a computer supporting compressed-memory via a contiguous directory.  
         [0038]    [0038]FIG. 4 shows an exemplary flowchart of a method for morphing from compressed-memory operation to uncompressed-memory operation according to an embodiment of the present invention. The number of page frames that can be used by processes, hereinafter referred to as usable page frames is reduced to a value M, which depends on the specific embodiment of the invention (step  401 ). A 1  is smaller than the maximum number of page frames that could be contained in the physical memory. Step  402  disables the compressor which compresses memory. After step  402 , each logical page paged-in from disk is stored in main memory in uncompressed form, and occupies the maximum number of memory sectors, as described for FIG. 3. Similarly, each memory line written back from cache to memory is stored uncompressed. In step  403 , the entire content of memory is decompressed; preferably, decompressing the entire content of memory is accomplished by reading each memory line into cache and forcing a write-back. When the entire content of memory is decompressed, and each memory line is stored in the maximum number of sectors, step  404  copies the memory sectors to physical addresses equal to their real addresses. Step  404  terminates when all the sectors in the compressed memory  110  are stored uncompressed at physical addresses equal to their real addresses. Step  405  releases the memory occupied by the compressed memory directory and by the data structures used by the morphing module, which is returned to the operating system as unused page frames.  
         [0039]    [0039]FIG. 5 shows a preferred process of reducing the number of page frames to a desired value M of step  401 . Step  501  prevents increasing the number of usable page frames: the compressed-memory mechanism for making page frames usable if the compressibility improves (for instance, if the number of memory sectors on the free-sector list exceeds a threshold) is disabled. In an alternate embodiment, a control policy is used that does not prevent increasing the number of usable page frames, but limits the rate at which page frames are made usable, so that the overall effect of the procedure illustrated by FIG. 5 is to actually reduce the number of usable page frames. The subsequent steps of FIG. 5 may have the overall effect of increasing the number of sectors on the free-sector list. In a preferred embodiment, where morphing is triggered by a cache-unfriendly workload, step  501  also temporarily disables page-ins on user processes unless the number of sectors on the free-sector list is above an appropriate threshold. In this embodiment, page-ins are re-enabled at step  506 . In other embodiments, page-ins are not disabled.  
         [0040]    The operating system uses appropriate data structures, typically one or more lists, to keep track of usable page frames that are not used by any process. In particular, there is a data structure keeping track of available usable page frame (a usable page frame could be unavailable, for example, if it is not used by any process, its content has been modified but has not been written to disk yet). In some operating systems, this structure is called zero page list.  
         [0041]    Step  502  removes all usable page frames from the zero page list. In a preferred embodiment, these page frames are not associated with memory sectors: as described in FIG. 3, highly compressible memory lines are stored entirely in the corresponding CTT-entry. Removing all page frames from the zero page list has the effect of reducing the real memory. Steps  503  and  504  are repeatedly executed until the number of usable page frames in memory is reduced to or below the threshold M. Recall that a usable page frame is a page frame used by a process or unused and kept by the operating system in a data structure that makes it available to processes. One skilled in the art can readily appreciate how the definition of usable page frames can be easily adapted to paged operating systems that use different data structures for page-frame management. Step  503  takes pages used by processes, writes modified pages to disk, and adds them to the data strictures used to keep track of unused pages. This process is similar to the process of pruning the working set of processes in operating systems such as Windows  2000 . In a preferred embodiment the operations required by step  503  are performed by invoking the appropriate operating system modules. Step  504  takes unused page frames and makes then unavailable to processes. Step  503  and  504  can be executed concurrently.  
         [0042]    Step  505  controls the operations of Step  503  and  504 , and terminates their execution when the number of page frames equals the desired value M, or falls below M. In a prefer-ed embodiment, the value of M is selected using the following equation 
           M &lt;=(physical memory size—CTT size—morphing structure size)/ (page size) 
         [0043]    The number M must be large enough to contain the non-pageable code and data structures stored in memory. Note that all the code and data necessary for the operations of the computer system will be contained in these M pages, except for the data used by the morphing process, which resides outside said M pages.  
         [0044]    The method taught of FIG. 5 does not prevent page-ins. For example, if the number of memory sectors in the free-sector list is large enough, the appropriate operating system modules can reuse page frames on the standby and free page list, and add them to the working set of their original process. To ensure that the method of FIG. 5 terminates, the invoked operating system modules must have sufficiently high priority, the value of which can be modified during the morphing operation to remove page frames from memory at a desired rate.  
         [0045]    [0045]FIG. 6 shows a method of decompressing the content of memory  403  according to a preferred embodiment of this invention. In step  601  a threshold T is selected, which satisfies 2 constraints:  
         [0046]    (1) The threshold T is larger than the size of the CTT in bytes plus M times the size of a physical page, and (2) the threshold T is smaller than the size of the physical memory minus the size of the data structures used during morphing.  
         [0047]    Step  602  defines an allowable region of the real memory space, as the set of real addresses below the threshold T defined in step  601 , minus the set of physical addresses occupied by the CTT and by other data structures used by the memory compression management system. This allowable regions has two main purposes: in real space, it defines the set of real addresses that can be active at the time when morphing terminates; in physical space, it defines the set of physical addresses that are in use right after morphing terminates. Hence, two goals are accomplished: all active pages with real addresses outside the allowable region are removed from real space; and all memory sectors with physical address outside the allowable region and that are in use are reclaimed.  
         [0048]    Steps  603  and  604  deal with the free-sector list maintained by the memory-compression system. Step  603  prevents adding free-sectors that have physical addresses outside the allowable region to the free-sector list. In one way to accomplish this, the mechanism controlling the management of the free-sector list is modified appropriately. A preferred embodiment of such management control is shown in FIG. 13, to be described below. When a free sector that lies outside the allowed region is presented to the free-sector list manager, the manager does not add it to the list, and forgets its address. Hence, said sector is neither used by a page frame, nor is on the free-sector list. No pointer is maintained that contains its address, and therefore it is henceforth invisible, hence unusable, by the compressed-memory management system. Note that this is not a problem: eventually all memory-sectors residing outside the allowable region will be released; the morphing mechanism accesses directly (i.e., using physical addresses) memory locations outside the allowable region, and therefore there is no need to maintain pointers to the released sectors.  
         [0049]    Step  604  then analyzes the free-sector list maintained by the memory compression subsystem. It examines all its memory sectors and removes those with physical addresses outside the allowable region. As in step  603 , these sectors are simply released, and no pointer to them is maintained by the memory-compression manager. When step  604  terminates, step  605  analyzes all the processes in the system. In a preferred embodiment, the operating system maintains a unique process descriptor per each process, namely, a data structure containing the information relevant to said process. In this preferred embodiment, step  605  obtains a pointer to each process descriptor and uses said process descriptors to analyze each process. Step  605  controls the execution of steps  606  and  607 , and terminates the operation described in FIG. 6 when all the processes have been analyzed (step  608 ). In step  606 , the page frames associated with the process being analyzed are inspected, and page frames falling outside the allowable region are moved to the allowable region. In step  607 , all the lines of the resident pages of the process are decompressed by reading them in cache and forcing a write-back. FIG. 7 illustrate steps  606  and  607  according to a preferred embodiment of the present invention. Steps  701  and  702  are preferably executed once. They can be executed before step  601 , between step  601  and  602 , between step  603  and  604 , or after step  604  but before step  704 . In step  704  a pointer P is initialized to the first entry in the CTT. In a preferred embodiment, the pointer P is physically stored in a special-purpose register within the memory controller. In step  702 , the pointer is advanced until the first unused CTT entry is found. In a preferred embodiment, the information on whether a CTT entry is used or not is contained in the CTT entry itself. In another preferred embodiment, a list is maintained of unused CTT entries, and in this case step  701  initializes a pointer to the beginning of the list of unused CTT entries, and step  702  advances the pointer until the first unused CTT entry having real address within the allowable region defined in step  602  is encountered. Steps  703  to  709  are detailed explanations of steps  606  and  607  in the context of the current preferred embodiment. Step  704  analyzes each Page Table Entry (PTE) associated with the process being analyzed, and terminates when all the PTES of the process have been analyzed (step  705 ). If the PTE translates a virtual pages to a real page in memory, the below described steps are executed. Step  706  decompresses each line of the page. In a preferred embodiment, where memory lines are decompressed upon cache-misses, and stored entirely into cache, step  706  reads each line of the page into cache, and forces a write-back hence decompressing the content of the line (since the compressor was disabled in step  402 ). In a preferred embodiment, the forced write-back is assisted by hardware: the cache-controller is augmented with appropriate circuitry that would force the write-back (for example, hardware that would set on demand the modified-flag). In a different embodiment, step  706  is accomplished by software: the memory line is read into cache by a program, which also loads one of the bytes of the line, say the first, into a register of the processor, and writes back the byte into the same position within the cache line. With this method, the cache controller detects a write to the cache line, marks the line as modified, and therefore, when the line is evicted from cache, it is written back. Step  707  checks the real address of the page translated by the PTE. If the real address is in the allowed region, the next PTE is analyzed by step  704 . Otherwise step  708  copies the content of the CTT entry corresponding to the real page whose address is in the PTE to the unused CTT entry pointed by P, and changes the real address in the PTE to the real page translated by the CTT entry pointed by P. There is no need to add the old CTT-entry to the unused entry list, since it will not be reused. Step  709  advances the pointer P to the next unused CTT entry.  
         [0050]    In a preferred embodiment where the CTT-entries contain information on whether they are used or unused, the pointer P is simply incremented until an unused CTT-entry is found. In the preferred embodiment where the unused CTT entries belong to a list, the pointer P is advanced within the list, until a CTT entry is found which corresponds to a real page having address within the allowable region. It would be apparent to one skilled in the art that, depending on the specific operating system, further steps might need to be taken to prevent the operating system to allocate new page frames in the unallowed region. In operating systems like Windows NT and Windows 2000 this is not necessary, because all page frames not on the zero- or free-page list are still pointed to by the CTT entry of the process to which they belonged, or by a data structure associated with the process to which they belonged. In a preferred embodiment, where the operating system maintains such data structure, said data structure would be analyzed using the same method described in FIG. 7. In a preferred embodiment, the page frames on the zero list are analyzed before beginning step  703 , and removed from the zero list if their address is within the non-allowed region. In another embodiment, they are analyzed and modified using steps  707 ,  708  and  709 .  
         [0051]    According to still another embodiment of the present invention, the CTT can be positioned in a generic position within the physical memory, and can be potentially subdivided into a collection of contiguous intervals. The definition of the allowable region is formally identical, and the appropriate changes to the tests determining whether physical sectors and real addresses of page frames fall within the allowable region could be easily made by one skilled in the art.  
         [0052]    [0052]FIG. 8 describes a preferred embodiment of implementing step  404  of the present invention. Step  801  constructs a physical-to-real map of the memory sectors. Since at this point no new page frame is added to real memory and compression is disabled, the sectors associate with each page frame are now in a fixed position within physical memory, and their positions do not change during the computation. Constructing the physical-to-real map comprises the following steps:  
         [0053]    1. Allocate an array of pointer A containing one entry per each physical memory sector in the allowed region. This array of pointer is allocated in the portion of physical memory with addresses higher than the threshold T defined in step  601 .  
         [0054]    2. Walk the CTT: the following pseudo code describes the operations:  
                                                                                                               for each CTT-entry E do:                for each pointer P in CTT-entry E do:                copy the index of the CTT entry into the each entry o the                array A                corresponding to the address stored in P.                done                done                      
 
         [0055]    Once the physical-to-real map has been created, step  802  walks the CTT, for example, starting from the end of the CTT, and controls the execution of all the subsequent steps in the figure. One skilled in the art would appreciate that the algorithm can be easily modified to rearrange the content of the memory in order of increasing real address. While the CTT contains CTT-entries used by a page frame, steps  804  to  810  are executed. When the CTT no longer contains CTT-entries used by page frames, the method of FIG. 9 terminates at step  803 .  
         [0056]    Let E be the CTT-entry selected by step  902 . E corresponds to a real address range, which contains a certain number of sectors. In a preferred embodiment, where the size of a page is 4096 bytes and the size of a memory sector is 256 bytes, the real address range corresponding to a page frame contains 4096/256=16 memory sectors.  
         [0057]    Step  804  applies steps  805 ,  806  and  807  to each sector S in the physical address range equal to the real address range corresponding to E. Step  805  looks up in the physical-to-real map the real address using sector S, and retrieves the corresponding CTT-entry E s . Step  806  copies the content of sector S to an unused sector S′ obtained from the free-sector list. It would be apparent to one skilled in the art that steps  805  and  806  can be executed in any order. Step  807  copies the address of S′ in the pointer in the CTT-entry F s  that contains the address of S. When step  804  terminates the iteration, the physical address range corresponding to the real address range corresponding to the CTT-entry E can be overwritten without compromising data integrity. Step  808  iterates on the memory sectors containing the data indexed by E. Let S″ denote such sector. Step  809  copies the data contained in S″ to the sector having physical address equal to the real address of S″.  
         [0058]    In a preferred embodiment, the hardware and software for memory compression and morphing support a dual-addressing mode during morphing. More specifically, addresses in the morphed range (namely, addresses that already underwent the morphing process) are accessed directly through the page tables, without the further indirection of the CTT; addresses outside the morphed range (namely, addresses waiting to be morphed) are accessed through the additional indirection provided by the CTT. Preferably, once all the real pages in memory have been morphed, the morphing process is terminated by preferred steps of the physical memory occupied by the physical-to-real map is divided into page frames, which are added to the free page list; and the physical memory occupied by the CTT is divided into page frames, which are added to the free page list.  
         [0059]    [0059]FIG. 9 depicts a method for reconverting the content of main memory from uncompressed to compressed without the need for interrupting the normal operation of the computer system. According to this preferred method, the operating system controls the range of non-pageable pages for a) the kernel and b) I/O operations, when the I/O buffers reside in pinned pages.  
         [0060]    In step  901  the size of the CTT is selected. In a preferred embodiment, the size of the CTT is statically selected to equal a predefined value. In another embodiment, the compressor gathers statistics on compressibility of cache lines (but does not write compressed lines) when cache lines are written back, and the compressibility information is used to decide the size of the CTT. In a preferred embodiment, the CTT starts at a predefined address. In another embodiment, the starting address of the CTT can be selected using predefined strategies, and used as a parameter of the compressed memory management; in this embodiment, step  901  also selects a starting address of the CTT using said predefined strategies. The range of physical addresses starting at the starting address of the CTT and having length equal to the size of the CTT is called the CTT range in this invention. Step  902  pages out all page frames in the CTT range, and prevents the virtual memory manager from reusing said page frames. In a preferred embodiment, where the operating system is Windows NT, 2000, or an operating system having similar virtual memory management, Step  902  can be performed by the following examplary process:  
         [0061]    preventing the memory manager from adding page frames in the CTT-range to the modified and standby page list, by appropriately modifying the working set manager;  
         [0062]    analyzing the modified page, standby, free, and zero page list to identify page frames in the CTT-range;  
         [0063]    writing said identified pages on the modified page list to the page file, and removing them from the modified page list;  
         [0064]    removing said identified pages from the standby, free, and zero page list;  
         [0065]    searching the page tables of the processes for page frames in the CTT-range; and  
         [0066]    writing said identified page frames to the page file, and removing them from.  
         [0067]    The last two tasks can be accomplished by modifying the method of FIG. 7.  
         [0068]    Step  903  initializes the CTT; step  904  enables compression and compressed memory management; and step  905  populates the CTT.  
         [0069]    [0069]FIG. 10 shows a preferred embodiment. In step  1001  of performing steps  903 ,  904  and  905  the content of the CTT-entries are initialized to a value never used when the CTT-entry translates between real and physical addresses. By comparing the content of a CTT-entry with said value, it is therefore possible to determine if the CTT-entry is currently used for translation between real an physical addresses or if it has never been used. Step  1002  enables the compressor and initializes compressed memory management in an inverse-morphing mode, by setting a flag. Step  1003  initializes to zero the counter of the number of CTT-entries corresponding to inverse-morphed lines.  
         [0070]    Step  1004  checks the flag upon a cache write: if the flag is set to denote inverse-morphing mode, steps  1005  and  1006  are executed. In step  1005 , the compressed memory management system checks if the line being written back was converted prior to writing it back. If the line was not converted, step  1005  increases the counter, to denote that the line has now been converted. Step  1007  checks the flag upon a cache write: if the flag is set to denote inverse-morphing mode, steps  1008  is executed, which checks if the CTT-entry of the line has been modified, and the line converted. If the line has been converted, step  1011  continues the read operation by translating real addresses to physical addresses through the CTT-entry. If the line has not been converted, step  1009  continues the read operation by translating real addresses to physical addresses through the CTT-entry. To speed up the completion of inverse-morphing operations (for example, when the content of memory is mostly read and rarely written, as in data mining tasks), step  1010  modifies the CTT entry, by indicating that the line is stored uncompressed and by initializing the memory sector pointers to the physical locations of the memory sectors used by the line, and increases the counter. Step  1006  is invoked when the counter is increased, by either step  1005  or  1010 . If the counter equals the number of entries in the CTT, the inverse-morphing process terminates, and the flag is reset.  
         [0071]    [0071]FIG. 11 shows a preferred embodiment of a method for dynamically increasing the size of the CTT. In step  1101  the additional size of the CTT is computed. It would be apparent to one skilled in the art that adaptive control strategies can be used to determine the additional size of the CTT. The symbol S is used to denote this additional size, expressed in number of memory sectors, and A to denote the interval of addresses that will be used by the CTT. Step  1102  prevents freed sectors falling in the expanded CTT area (the set of physical memory addresses A), from being added to the free-sector list. In a preferred embodiment, step  1102  notify the compressed memory management module responsible for managing the free sectors that when a memory sector is freed, its address should be examined to determine if it falls within A, and that such memory sectors should not be added to the free-sector list. Step  1103  analyzes the free-sector list and removes from it all the sectors with address in A. In a preferred embodiment, the number S is decreased by the number of memory sectors removed by step  113 . Step  1104  is an iterator the purpose of which is to control steps  1105  and  1106 , which together obtain S unutilized memory sectors from the free-sector list. Step  1   104  terminates when S unutilized memory sectors are recovered. Step  1105  recovers sectors from the free-sector list. To avoid memory exhaustion, step  1105  always leaves a minimum number of free memory sectors on the free-sector list, as dictated by the compressed memory management policy. To allow step  1105  to gather free sectors, step  1106  forces the trimming of process working sets, which increases the size of the free-sector list. It can be readily appreciated by one skilled in the art that steps  1105  and  1106  can be executed in any order, and can also be executed concurrently. When S sectors have been retrieved from the free-sector list, step  1107  iterates on the CTT entries. Step  1107  iterates on each CTT-entry in the CTT. Step  1108  iterates on each sector pointer of the CTT-entry. If the sector is in region A, the content of the sector is copied to one of the S sectors recovered in steps  1101 - 1106 , and the pointer is upgraded (step  1109 ). To prevent problems with roommates, steps  1107 ,  1108  and  1109  could be executed atomically on all the entries of a cohort (the set of lines that are allowed to roommate), possibly while masking interrupts. One skilled in the art, can appreciate that the set of steps  1104 ,  1105 ,  1106  and the set of steps  1107 ,  1108  and  1109  need not be executed sequentially, but can be executed concurrently. When all the entries in the CTT have been analyzed, step  1110  expands the CTT and initializes its entries.  
         [0072]    [0072]FIG. 12 illustrates a preferred embodiment of the method for reducing the size of the compressed memory directory to the size required to index M page frames. The number M of page frames can be selected by analyzing the dynamic behavior of the compressibility of the data contained in memory. In step  1201 , the compressed-memory management system is prevented from allocating novel page frames having address larger than M times the size of an uncompressed page. Step  1202  prevents the addition of page frames having real address larger than M times the size of an uncompressed page, to the modified, standby, free and zero page lists. Instead of adding such page frame to the modified list, the compressed-memory management system adds said page to the head of the modified page list, forces a page write, and discards the page frame. Instead of adding such page frame to the standby, free and zero page list, the compressed memory management system discards such page frame. Step  1203  analyzes said lists searching for page frames having real address larger than M times the size of an uncompressed page. When such page frame is found on the modified list, it is moved to the head of the list and a write-to-disk operation is issued, and the page frame is discarded. In a different embodiment, the write operation is postponed until the entire modified-page list is analyzed. When such page frame is found on the other lists, it is discarded. Step  1204  reduces the number of page frames in memory to M, for example using the method of FIG. 5. Step  1205  sets a pointer P 1  to the beginning of the memory-compression directory. Step  1206  analyzes each process running on the computer system in turn. Step  1207  analyzes all the page entries of pages used by the process selected in step  1206 . Step  1208  compares the real address of the page indexed by the page table entry selected in step  1207  with a threshold equal to A times the size of an uncompressed page frame. If the address is larger than said threshold, step  1209  increases the pointer P 1  until it points to an unused entry in the CTT, step  1210  copies the CTT entry corresponding to the real address identified in step  1208 , and step  1211  modifies said address in the page table entry selected by step  1207  to the value contained in P 1 . Step  1207  terminates (done in the figure) when the last PTE of the process selected by step  1206  has been analyzes, while step  1206  terminates when the last process has been analyzed. It is apparent to one ordinary skilled in the art that step  1206  need only analyze processes that had been initialized before the execution of step  1204  terminates. Also, processes that terminate before step  1206  terminates need not be analyzed, since violating page frames are managed by the compressed-memory management components initialized in steps  1201  to  1203 .  
         [0073]    [0073]FIG. 13 illustrates an embodiment of an apparatus for preventing memory-sectors falling outside the allowable region to be added to the free-sector list. In this embodiment, the allowable region includes a collection of intervals of physical addresses. This collection contains at most K intervals. Each interval is identified by its lower and upper limit. In this embodiment, the free-sector list is managed in hardware by the free-sector list management logic ( 131   3 ). The part of logic  131   3  which adds memory sectors to the free-sector list is enabled by signal  1314 . For example, when signal is equal to 0, the logic does not add memory-sectors to the free-sector list, while when the signal is equal to 1, the logic is allowed to add memory sectors to the free-sector list. The starting address of the memory-sector to be added to the flee-sector list is stored in a register  1301 . The starting address of the first interval of the allowed region is stored in register  1302 , while the ending address of the first interval of the allowed region is stored in register  1303 . More specifically, the ending address is the starting address of the last memory-sector belonging to the corresponding interval. In this illustrative embodiment a pair of registers is used (for starting and ending address) for each interval of the allowed region. For illustration, only the first interval and those for the last interval, interval K (i.e., registers  1307  and  1308 ) are shown. For each pair of registers, the logic contains a pair of comparators. The first comparator is connected to register  1301  and to the register containing the start address of the interval. For example, comparator  1304  compares the values of registers  1301  and  1302 , while comparator  1309  compares the values stored in registers  1301  and  1307 . This comparator outputs a “1” if the value contained in register  1301  is larger than or equal to the value contained in the other register connected to the comparator. The second comparator is connected to register  1301  and to the register containing the end address of the interval. For example, comparator  1305  compares the values of registers  1301  and  1303 , while comparator  1310  compares the values stored in registers  1301  and  1308 . This comparator outputs a “1” if the value contained in register  1301  is smaller than or equal to the value contained in the other register connected to the comparator. The output of the two comparators are then used as input to an AND gate. For example, the output of comparators  1304  and  1305  are used as input to AND gate  1306  and the outputs of comparators  1309  and  1310  are used as input of AND gate  1311 . AND gate  1306  produces as output a “1” if both its inputs are equal to 1, and a “0” otherwise. Hence, AND gate  1306  produces a “1” if the value contained in register  1301  is larger than or equal to the value stored in register  1302  and smaller than or equal to the value stored in register  1303 , namely, only if the memory-sector whose starting address is stored in  1301  falls within the interval of the allowable region defined by the starting address stored in  1302  and the ending address stored in  1303 . According to this embodiment, if the number of intervals actually used by the allowable region is k, where k is smaller than the maximum value K, the AND gates of the last K-k register pairs are disabled. In a preferred embodiment, this is accomplished by adding a 1-bit flag to each register pair, which is set to 1 if the register pair corresponds to an interval of the allowable region, and to 0 other-wise; then this 1-bit flag is used as input to the AND gate, together with the outputs of the comparators. The output of all the AND gates are used as input to the OR gate  1312 , which produces a “1” it at least one of its inputs is equal to “1”, and a “0” otherwise. Therefore, the output  1314  of gate  1312  is equal to 1 if the memory sector whose address is stored in register  1301  belongs to one of the intervals of the allowable region.  
         [0074]    [0074]FIG. 14 describes an apparatus for removing firm the free-sector list sectors that lie outside the allowable region. Free memory-sectors can be located at any physical position within memory  1401 , with the constraint that the address of the first byte in the memory-sector be a multiple of the memory-sector size (here, we assume for sake of discussion, that the first byte in memory has address equal to 1; if the first byte in memory has address zero, the constraint is by dividing the address of the first byte of the memory-sector modulo the size of a memory sector one obtains zero). In this embodiment, free memory-sectors are organized in a linked list, as described in the patents listed as references. Preferably, each free memory-sector contains a pointer, which contains the address of the next memory-sector in the free list. For example, the pointer could be contained in the first four bytes of the memory-sector. As shown in FIG. 14, the memory-sector  1402  is at the head of the list, and its pointer  1406  contains the address of the second memory-sector  1403 . Continuing down the list, the pointer  1407  in  1403  contains the address of the third memory-sector in the list,  1404 , which is followed by the fourth memory sector,  1405 , and so on. The address of  1405  is stored in the pointer  1408  contained in  1404 .  
         [0075]    In this embodiment, the free-sector list is managed using 2 registers,  1410  and  1411 . For a 32-bit machine, both registers are 4 bytes long, while for a 64-bit machine they would be 8 bytes long. Register  1410  contains the address of the memory-sector at the head of the free-sector list. Register  1411  contains the address of the memory-sector that immediately follows the head. When a request for a free memory sector is received, and the list is not empty, the content of register  1410  is returned. At the same time, read/write unit  1412  reads the first four bytes of the memory-sector the address of which is in register  1411 . In this embodiments these four bytes contain the address of the next memory-sector on the free-sector list. One skilled in the art can appreciate how this scheme can be modified to accommodate pointers of different lengths, and having other positions within the free-sector list, and to adapt the scheme to the case where the free-sector list is managed by a data structure not resident in the free-sectors themselves. The circuit used to indicate that the free-sector list is empty, and to keep track of the number of free memory-sectors is also well known and is not shown. When the command to remove all memory sectors outside the allowable region from the free-sector list is received by the hardware, the logic  1413  is invoked. This logic performs the following operations:  
         [0076]    1. disable allocation of free-memory sectors from the free-memory sector list.  
         [0077]    2. compare the value of register  1410  to the description  1414  of the allowable region.  
         [0078]    3. if the head of the list is outside the allowable region, discard the sector by copying into  1410  the value contained in  1411 , invoke the operation of read/write unit  1412 , go back to step  2 .  
         [0079]    4. enable allocation of free-memory sectors from the free-memory sector list, copy the value of  1410  into register  1415  and of  1411  into register  1416 , and give control to list control logic  1417 .  
         [0080]    Note that disabling the allocation of free-memory sectors from the free-sector list in general would not stall the operation of the machine for a long time. The worst-case scenario occurs when all the memory-sectors outside the allowable region are on the free-sector list, and before any memory-sector inside the allowable region. Recall that only the portion of the unallowable region set aside to contain the physical-to-real map and supporting data structures is involved in this step: no free memory-sectors that overlap the CTT or data structures used by the memory compression can be on the free-memory list.  
         [0081]    The description  1414  of the allowable region can be implemented a pair of registers or a collection of register pairs.  
         [0082]    When  1413  gives control to the list cleaning control logic  1417 , the content of register  3  is an address within the allowable region.  
         [0083]    Logic  1417  performs the following operations:  
         [0084]    A. compares the value of register  3  ( 1415 ) to that of register  1  ( 1410 ). If the comparison is successful, disables the allocation of free-memory sectors from the free-memory sector list, otherwise leaves allocation enabled.  
         [0085]    B. In parallel to the previous operation, compares the value contained in register  4  ( 1416 ) with the description  1414  of the allowable region:  
         [0086]    If the address contained in  1416  is in the allowable region, it performs the following operations  
         [0087]    i. copies the value contained in  1416  into  1415   
         [0088]    ii. invokes the read/write unit  1412  and reads into  1416  the first four bytes of the memory-sector whose address is in  1416  during step  1  above.  
         [0089]    If the address contained in  1416  is not in the allowable region, then  
         [0090]    1. invokes the read/write unit  1412  and reads into  1416  the first four bytes of the memory-sector whose address is in  1416  during step  1  above,  
         [0091]    2. repeats step  1 . until the content of  1416  is inside the allowable region.  
         [0092]    3. copies the content of register  4  ( 1416 ) into the first four bytes of the memory-sector whose address is in register  3  ( 1415 ) using read/write unit  1412   
         [0093]    4. if the content of register  3  ( 1415 ) equals that of register  1  ( 1410 ), copies the content of register  4  ( 1416 ) into register  2  ( 1411 ).  
         [0094]    5. returns to Step B.  
         [0095]    The logic  1417  has also features for terminating appropriately the operations when the tail of the list is reached. While logic  1417  is active, register 3 always points to a memory-sector within the allowable region, while the content of register  4  changes until it equals an address within the allowable region. By copying the value of register  4  into the first 4 bytes of the sector whose address is in  1415 , the logic “detaches” from the free-sector list those memory-sectors lying outside the allowable region. By disallowing giving out free-sectors while the content of  1415  equals that of  1410 , the changes to the circuit for controlling the operations on the head of the free-sector list is minimized.  
         [0096]    Preferred embodiments of the present invention are described based a paged operating system, such as Windows95, Windows98, WindowsNT, Windows2000, Linux, AIX and all the other versions of UNIX, MacOS, IBM OS/400 etc. One of ordinary skill in the art readily appreciates that non-paged operating systems are equally applicable to the embodiments of the present invention.  
         [0097]    While the invention has been shown and described with reference to certain preferred embodiments thereof, it will be understood by those skilled in the art that various changes in form and detail may be made therein without departing from the spirit and scope of the invention as defined by the appended claims.