Electrical computers and digital processing systems: memory – Storage accessing and control – Memory configuring
Reexamination Certificate
1999-03-25
2002-12-17
Gossage, Glenn (Department: 2187)
Electrical computers and digital processing systems: memory
Storage accessing and control
Memory configuring
C711S173000, C711S159000
Reexamination Certificate
active
06496912
ABSTRACT:
TECHNICAL FIELD
This invention concerns memory management systems for computer systems, particularly methods of trimming, or reducing, working sets.
BACKGROUND OF THE INVENTION
Personal computers allow users to do an almost unlimited number of tasks. Examples include drafting term papers and letters, organizing recipes and addresses, tracking checking accounts and stock portfolios, communicating via electronic mail with other computer users, and drawing blueprints for home improvements. To accomplish these and other tasks, the typical computer system includes application programs—specific sets of instructions—that work with other components of the computer system to provide specific functions. Application programs are often called software to distinguish from the physical equipment, or hardware, of a computer system.
The computer system typically includes a processor, a short-term memory, a long-term memory, a keyboard, a visual display, and an operating system. The operating system is a special kind of software that facilitates execution of application programs. Application programs logically combine functions or services of the operating system with those of the processor to achieve their more complex functions. Examples of typical operating-system functions include initial interpretation of inputs from the keyboard and managing memory for application programs.
One facet of memory management concerns the allocation of short-term memory during start up and execution of application programs. Starting an application program generally entails retrieving some instructions making up the program from a long-term memory, such as a magnetic or optical disk, and copying them into portions of a short-term memory, such as a random-access memory (RAM), before the processor begins executing the program instructions. Short-term memory devices are generally faster than long-term memory devices and allow the processor to more quickly fetch and execute individual program instructions. The short-term memory is organized typically as a set of memory pages, each having the same storage capacity, for example, 4096 bytes.
As each application program starts, a memory manager within the operating system allocates a set of short-term memory pages to each application program, with the objective of reducing the number of times the processor needs to access the slower, long-term memory during execution of the application program. The set of pages allocated, or assigned, to an application program is called its working set. As application programs execute, the memory manager detects page faults—conditions indicating that applications need certain data or program instructions initially left behind in long-term memory—and eventually expands corresponding working sets to include these data or instructions if there is sufficient short-term memory available. The amount of available short-term memory is called free memory. However, if there is insufficient free memory to allow expansion of working sets, the memory manager attempts to increase the amount of free memory by re-assigning memory pages from other working sets to free memory.
This process of re-assigning pages from working sets to free memory is known as trimming the working sets. Trimming in the Microsoft WINDOWS NT 4.0 brand operating system, for example, requires the memory manager to compare the current size of one working set to its minimum allowable size every six seconds during a free-memory shortage. When the memory manager finds a working set that is larger than its minimum allowable size and that has not had too many recent page faults, the manager trims a limited number of pages from its working set, adding the pages to free memory and thus making them available for the working sets of other application programs. If there is still a free memory shortage, the memory manager looks for the next working set that is larger than its minimum allowable sizes and trims pages from it. This process of sequentially checking for larger-than-necessary working sets repeats until the memory manager trims enough pages to end the memory shortage.
In trimming pages from a specific working set, the memory manager typically tries to trim pages that have not been accessed recently. It does this by checking the access bit for each page of a working set to see whether the page has been accessed (since the last time it was checked). If the access bit is zero, indicating that the page has not been accessed, the manager re-assigns the page to free memory. If the bit is one, indicating that the page has been accessed, the memory manager resets it to zero. (If the bit for this page is still zero the next time the manager checks the page, the memory manager will trim the page.) The memory manager then similarly checks the access bit for the next page of the working set, trimming the page if it has not been accessed or resetting the access bit to zero if it has. This page-by-page search for trimmable pages continues through the working set and onto the next working set until either enough pages have been trimmed to end the free-memory shortage or each working set has been checked. (For further details, see David A. Solomon, Inside Windows NT, Second Edition (ISBN 1-57231-677-2) pages 217-304 (1998).)
In devising the present invention, the inventors recognized that this trimming method suffers from at least two problems. First, because it lacks accurate information about the relative use of specific pages, it severely limits the rate pages can be trimmed from working sets and thus reduces how fast the operating system can respond to changing memory needs of application programs, ultimately forcing them to resort to slower, long-term memory more often than may be necessary. Second, because the method treats each working set that has trimmable pages equally and in sequence, it can sometimes incorrectly and disproportionately distribute the trimming burden across a few working sets, ignoring other working sets better suited for trimming, that is, working sets having larger numbers of pages that have not been accessed recently. Accordingly, there is a need for better ways of trimming working sets.
SUMMARY OF THE INVENTION
To address these and other needs, the inventors devised a memory management system, method, and software that facilitates faster, more intelligent trimming of working sets. Specifically, in one implementation, or embodiment, the method includes assigning working sets of memory pages to corresponding application programs; estimating numbers of memory pages eligible for trimming from the working sets; and trimming the working sets based on the estimated numbers of memory pages eligible for trimming.
In an exemplary implementation, the method entails tracking the age of the memory pages of each working set using a two-bit age counter that permits classifying the pages of each working set into four classes based on how recently they were last accessed. In this implementation, estimating the numbers of memory pages eligible for trimming includes summing the number of pages in the three oldest of the four classes. Additionally, trimming the working sets entails sorting at least some of the estimates based on magnitude and trimming working sets with larger estimates before trimming those with small ones.
REFERENCES:
patent: 4035778 (1977-07-01), Ghanem
patent: 5101485 (1992-03-01), Perazzoli, Jr.
patent: 5493663 (1996-02-01), Parikh
patent: 5517643 (1996-05-01), Davy
patent: 5664191 (1997-09-01), Davidson et al.
patent: 5721917 (1998-02-01), Elliot et al.
Bach, M.J., “Memory Management Policies”,The Design of the Unix Operating System, Prentice-Hall, Inc., Englewood Wood, New Jersey, 271-311, (1986).
Solomon, D.A., “Memory Management”,Inside Windows NT, Second Edition, Microsoft Press, pp. 217-304, (1998).
Tsichritzis, D.C., et al.,Operating Systems, Academic Press, New York, pp. 69-95, 96-119, (1974).
Fields, Jr. Mahlon David
Sechrest Stuart
Gossage Glenn
Leydig Voit & Mayer Ltd
Microsoft Corporation
LandOfFree
System, method, and software for memory management with... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System, method, and software for memory management with..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System, method, and software for memory management with... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2995358