Computer workstation having demand-paged virtual memory and enhanced prefaulting

Abstract

A CTOS network comprised of a plurality of workstations provides for virtual demand paging transparently across the network in a manner which permits a large virtual memory to efficiently be provided for each of a plurality of concurrently running applications on a CTOS workstation. Each application running on the workstation is provided with assigned pages and a local clock which operates based on the well known clock algorithm. A unique combination of local policy and global policy is used for page replacement which results in significantly more efficient management of available memory pages. The global policy includes an "elbow room" enhancement which permits the global page replacement policy to better take into account the individual activity of the concurrently running applications. In addition, enhanced prefaulting and page cleaning are provided, whereby it is made significantly more likely that a running application will find a requested page in its local clock.

What is claimed is: 
     
       1. A method of controlling paging on a workstation capable of concurrently running a plurality of applications, said method comprising the steps of: providing a workstation memory;   dividing said workstation memory into a plurality of pages having files stored therein;   maintaining a page table for each running application indicating corresponding files and pages and also whether each page is present;   providing non-volatile storage for storing not present pages;   assigning pages of said workstation memory to each running application;   providing a page fault when a running application requests access to a page which said page table indicates is not present;   determining whether a free page is available for storing the not present page of the page faulting application;   when a free page is determined to be available to store the not present page, then examining the page table of the page faulting application with respect to adjacent pages both preceding and following the not present page which caused the page fault;   selecting as candidate pages for prefaulting consecutive not present adjacent pages both following and preceding said not present page which are also from the same file as the not present page;   searching said workstation memory to find an available block of contiguous pages for storing the not present page and the adjacent candidate pages; and   reading in from said non-volatile storage the not present page which produced the page fault and the maximum number of adjacent candidate pages that can be accommodated by the block found by said searching.   
     
     
       2. The method of claim 1, including the step of selectively providing a prefetching capability for a running application, and wherein the steps of examining, selecting, searching and reading are performed for an application when the application has been provided with a prefaulting capability. 
     
     
       3. The method of claim 1, including the step of: when the step of examining does not find any candidate pages for prefaulting, then reading the not present page from said non-volatile storage into the free page found by said determining without performing the steps of selecting and searching.   
     
     
       4. The method of claim 1, including the step of limiting said candidate pages to a predetermined maximum number. 
     
     
       5. The method of claim 4, wherein said predetermined maximum number is chosen based on the maximum number of pages which can be read from said non-volatile storage during a reading operation. 
     
     
       6. The method of claim 4, wherein the step of limiting chooses candidate pages for prefaulting such that candidate pages following the not present page are chosen ahead of those preceding the not present page. 
     
     
       7. The method of claim 1, including the steps of: when a free page is determined not to be available to store the not present page of a faulting application, then searching the pages of the page faulting application using a clock algorithm to locate a page which is replaceable; and   when said searching does not find a replaceable page in the page faulting application, then searching the pages of other running applications to locate a replaceable page for use by the page faulting application for storing the not present page;   said searching of said other running applications occurring in a selection order based on their page faulting activity; and   reading in from said non-volatile storage the not present page into the located replaceable page.   
     
     
       8. The method of claim 7, wherein said searching of said other running applications begins with the one of said other running applications which least recently experienced a page fault. 
     
     
       9. The method of claim 8, wherein said searching of said other running applications includes selecting a next one of said other running applications for searching when no available replaceable page is found in a previously searched application. 
     
     
       10. A method in accordance with claim 7, wherein said selection order is additionally based on whether any of said other running applications is running in the background foreground. 
     
     
       11. A method in accordance with claim 7, wherein said workstation is a CTOS workstation.