The present invention relates generally to improved methods and apparatus for providing a demand-paged virtual memory in a computer workstation.
Modern-day workstations are typically capable of running a plurality of applications at one time. Each application normally requires its own memory in order to run the application. If a running application should use up all of the workstation's available memory, the application will usually be caused to wait or terminate, which may significantly slow up performance of the application, or require that the application be rerun when sufficient memory becomes available. An additional problem that can occur with a workstation running a plurality of applications is that, when a new application is initiated at the workstation and there is insufficient memory available, a running application will be forced to terminate and be swapped out in order to permit the new application to run. Such situations make it important that a workstation provide sufficient memory to run all of the applications which the user intends be run at the same time. As a result, a workstation normally has to be provided with sufficient total memory to run all of the applications that a user may wish to run at the same time without the workstation's memory becoming oversubscribed.
One known way of increasing the memory available to a computer workstation is to provide a virtual memory arrangement which permits the workstation to use memory which is not currently available in the workstation's main memory. For example, it is known to use a paging arrangement wherein the workstation's main memory is capable of storing a prescribed number of pages, one or more of which may be swapped with those contained, for example, on a disk drive attached to the workstation. When an application running on the workstation requests a page which is "not present" in the workstation's main memory, a situation commonly known as a page fault occurs. The workstation's operating system resolves this page fault by reading in the "not present" page from the disk into a free page (i.e., a page not currently in use) in the workstation's main memory. If the workstation does not have a free page, then the "not present" page is caused to replace a page in the workstation's memory. The particular workstation page which is replaced is determined based on an algorithm that attempts to choose for replacement a page which is not likely to be needed. One well known algorithm for this purpose is the "least recently used" (LRU) algorithm which replaces a page in a workstation's main memory based on the page which has been least recently used. This algorithm is typically implemented by providing a stack which links pages based upon usage.
A significant disadvantage of such an (LRU) algorithm is that it requires a significant amount of processing overhead for its implementation. In addition, this LRU algorithm does not work well when a workstation is running a plurality of applications, since the "least recently used" approach does not take application priorities into account and thus can cause pages to be replaced from a running application at an inappropriate time.
Another known type of page replacement algorithm is commonly referred to as a "clock" algorithm, wherein memory pages are arranged in a single circular list (like the circumference of a clock). The clock pointer (or hand) points to the last page replaced, and moves clockwise when the algorithm is invoked to find the next replacement page. When a page is tested for replacement, the access bit in the corresponding page table entry is tested and reset. If the page has been referenced since the last test, the page is considered to be part of the current working set, and the pointer is advanced to the next page. If the page has not been accessed, and is not "dirty" (i.e., does not need to be written back to its backup store) it is eligible for replacement. While this clock algorithm requires less overhead than the LRU algorithm, it still does not perform well for a workstation running a plurality of applications at the same time.