Electrical computers and digital processing systems: memory – Storage accessing and control – Memory configuring
Reexamination Certificate
2001-04-09
2003-02-04
Kim, Hong (Department: 2186)
Electrical computers and digital processing systems: memory
Storage accessing and control
Memory configuring
C711S173000, C711S159000, C709S241000, C709S247000
Reexamination Certificate
active
06516397
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to computer systems, and more particularly, to an improved method for implementing virtual memory.
BACKGROUND OF THE INVENTION
A data processing system typically consists of a processor, a volatile memory for storing instructions and data, and some form of permanent storage i.e. a magnetic disk. Due to ever increasing sizes in application programs, operating systems use virtual memory to extend the visible size of the real random access memory (RAM) by backing it with a region on a permanent storage device (Swap file or device). This procedure also allows multitasking systems to run multiple processes on the machine, where each process can be given access to the complete virtual address space of the processor. The address space is divided into page frames which are typically fixed in size. A translation mechanism is used to convert the virtual address issued by a running process to the physical page that contains the instructions or data required by the process. When the system runs low on physical pages, it writes less active pages to a permanent storage medium like a hard disk. The area of the disk reserved for this purpose is called the swap device or swap file. The newly freed page frame can now be supplied to this or another process.
However, if the page that was written to disk must be accessed, it has to be explicitly fetched from the swap device and put into a free physical page frame. This disk access is multiple orders of magnitude slower than direct memory access, i.e., tens of milliseconds for disk access versus tens of nanoseconds for access to memory. The operating system can try to hide the latency of this disk access by switching to another runnable process, or by aggressively prefetching pages from disk. In many environments, such as an engineering workstation dedicated to one main task (EDA/CAD/CAM), there may not be another process that can be run to hide disk access latencies. Prefetching of pages from disk will work perfectly only if the system can exactly predict the page reference pattern of the application. This is not possible or prohibitively expensive in terms of computational resources for the general case.
One method that has been suggested to enhance the performance of virtual memory systems utilizes compression techniques to increase the amount of data and/or code that can be kept in RAM. Data tends to have high redundancy once it is moved into RAM. This observation may be due to the occurrence of large runs of similar numbers in case of scientific code, or finite size vocabularies in case of text or databases. The executable code that is normally held in virtual memory also tends to be highly redundant since it consists of sequences of computer instructions. Hence, the space needed to store this material can be substantially reduced by utilizing data compression algorithms. A section of data and/or code that was too large to fit into RAM in its normally executable form may fit into the same RAM space in its compressed form. Sections of the compressed data and/or code can then be decompressed and sent to the computer process requesting the information without swapping information back and forth to a swap file.
Unfortunately, the prior art systems based on data compression require that the operating system kernel be modified, which is a complex and expensive process. This also requires customers to do significant software upgrades to their existing computers.
Prior art systems that utilize hardware compression engines in the memory path to improve performance have also been suggested. These systems not only require that the computer operating system be modified, but also that changes be made to the computer hardware. Hence, these systems are also unsuitable for the large installed base of engineering workstations. In addition, systems based on hardware compression cannot be easily changed to take advantage of particular compression algorithms that might provide significantly better compression with one type of program that is used on a particular system.
Broadly, it is the object of the present invention to provide an improved virtual memory system for use in data processing systems and the like.
It is a further object of the present invention to provide a virtual memory system that does not require that the operating system kernel be altered.
It is a still further object of the present invention to provide a virtual memory system that can utilize a variety of different compression algorithms.
These and other objects of the present invention will become apparent to those skilled in the art from the following detailed description of the invention and the accompanying drawings.
SUMMARY OF THE INVENTION
The present invention is a method of operating a data processing system having a main memory divided into memory pages that are swapped into and out of main memory when main memory becomes short. The data processing system has an operating system that sends “page store” commands specifying memory pages to be stored in a swap file and “page retrieve” commands specifying memory pages to be retrieved from the swap file and stored in the main memory. The present invention provides a swap driver that utilizes compression code for converting one of the memory pages that is to be swapped out of main memory to a compressed memory page. The data processing system's memory includes a compressed page region that is used to store the compressed memory pages. A page table in the compressed page region specifies the location of each compressed page and the page address corresponding to that page. The swap driver compresses at least one of the memory pages specified in one of the page store commands to provide a corresponding compressed memory page and causes that compressed memory page to be stored in the compressed page region. The swap driver also searches the page table for a page identified in one of the retrieve commands. The swap driver causes that page to be moved to a corresponding area of main memory after decompressing the page if the swap driver finds an entry in the page table indicating that the page is stored in the compressed page region. In the preferred embodiment of the present invention, the compression code includes a plurality of compression algorithms, and the swap driver determines which of the algorithms provides the most compression for each page. In this embodiment, the page table also stores information specifying the compression algorithm used to compress each stored compressed page. If there is insufficient space in the compressed page region to store one of the compressed memory pages, the swap driver causes one of the compressed memory pages stored in the compressed page region to be moved to an auxiliary storage device.
REFERENCES:
patent: 5394534 (1995-02-01), Kulakowski et al.
patent: 5479587 (1995-12-01), Campbell et al.
patent: 5559978 (1996-09-01), Spilo
patent: 5699539 (1997-12-01), Garber et al.
patent: 6002814 (1999-12-01), Chadez
patent: 2001/0038642 (2001-11-01), Alvarez et al.
patent: 2002/0097917 (2002-07-01), Nelson et al.
patent: 2002/0161932 (2002-10-01), Herger et al.
Kumar Rajendra
Prvulovic Milos
Roy Sumit
Wilson Kenneth Mark
LandOfFree
Virtual memory system utilizing data compression implemented... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Virtual memory system utilizing data compression implemented..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Virtual memory system utilizing data compression implemented... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3124912