COMPUTER WORKSTATION HAVING DEMAND-PAGED VIRTUAL MEMORY

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 terminate, which may then 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 th-3 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 particularly 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 the 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 application, since the "least recently used" approach can cause pages to be replaced from a running application at a 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.

SUMMARY OF THE INVENTION

A broad object of the present invention is to provide improved methods and apparatus for providing memory in a workstation capable of running a plurality of applications. A more specific object of the invention in accordance with the foregoing object is to provide demand- paged virtual memory for a workstation running a plurality of applications.

Another object of the invention, in accordance with one or more of the foregoing objects, is to provide a demand-paged virtual memory for a workstation connected in a network comprised of a plurality of workstations.

A further object of the invention, in accordance with one or more of the foregoing objects, is to provide a demand-paged virtual memory in a CTOS network comprised of a plurality of workstations.

A particular preferred embodiment of the present invention which accomplishes the foregoing objects is described herein as applied to a CTOS network of workstations wherein the networking capability is built into the operating system. An operating system of this type is currently available from Unisys Corporation, Blue Bell, Pennsylvania, and is designated by the registered trademark CTOS ®. Hardware, software and programming details for CTOS are available from Unisys Corporation. Also, a basic description of CTOS can be found in the book. Exploring CTOS, by E. I. Miller, et al.,Prentice Hall, Englewood Cliffs, New Jersey, 1991. The contents of this book are incorporated herein. In the described preferred embodiment, a virtual demand-paged virtual memory is transparently provided for

a workstation in a CTOS operating system. Each application running on the workstation is provided with assigned pages and a local clock. A unique combination of local policy and global policy is then used for page replacement in a manner which permits an efficient, very large virtual memory employing demand paging to be seamlessly provided for each of a plurality of applications running on the workstation. In addition, pages which are not present at the workstation may be transparently obtained across the network from a disk drive located at a server. This facilitates use of a diskless CTOS workstation if desired.

The specific nature of the inventions well as other objects, features, advantages and uses thereof will become evident from the following description of a preferred embodiment taken in conjunction with the accompanying drawings.

BRIEF DESCRIPTION OF THE DRAWINGS

Fig. 1 is a block diagram of a CTOS cluster comprising a plurality of workstations.

Fig. 2 is a block and schematic diagram illustrating a preferred embodiment of a CTOS workstation having a demand-paged virtual memory of a CTOS workstation in accordance with the invention.

Fig. 3 illustrates a typical page table used by each application running on the CTOS workstation in Fig. 2.

Fig. 4 schematically illustrates the arrangement of a local clock provided for each application running on the CTOS workstation in Fig. 2.

Fig. 5 is a flowchart illustrating the operation of the local clock illustrated in Fig. 4.

Fig. 6 is a flowchart illustrating the occurrence of a page fault as a result of an application requesting a "not present" memory page.

Fig. 7 is a flowchart illustrating operations occurring in response to the occurrence of a page fault.

Fig. 8 is a flowchart illustrating how a page fault is handled when the application which caused the page fault has reached its maximum number of assigned pages.

Fig. 9 is a flowchart illustrating how a page fault is handled when an application which causes a page fault has not reached its page maximum, but the workstation has used up its maximum number of assignable pages.

DESCRIPTION OF A PREFERRED EMBODIMENT

Like numbers and characters, correspond to like elements throughout the figures of the drawings.

Initially, reference is directed to Fig. 1 which illustrates a CTOS cluster comprised of a network of N desktop workstations WS#1 WS#N_, wherein one of the workstations (e.g., WS#1) is designated as the server workstation. CTOS runs on these workstations using the Intel ^® family of 80X86 microprocessors. CTOS is a modular, message-based operating system having a built-in networking capability which is transparent to the user.

The CTOS cluster illustrated in Fig. 1 is implemented through a simple bus topology B with RS-422/485 connections. Alternatively, the CTOS cluster may be implemented using twisted pair (telephone wiring) as described in U.S. Patent No. 4,918,688.

CTOS has a very small kernel, or group of primitive operations. Most of the CTOS system environment is made up of modules called system services. These system services manage resources (the file system, communication, etc.) and provide services that are requested by application program processes and by other system service processes.

A system running CTOS has multiple processes or threads of execution. A process is an independent thread of execution, together with the hardware and software context necessary to that thread. A message is passed from one process to another via an exchange. An exchange is like a mailbox where processes wait to receive messages, or where messages are deposited to wait to be processed. Each process is allocated an exchange when it is created. CTOS uses a special type of message, the request for service.

which is the most commonly used CTOS message. These requests are specially formatted messages that include a request block header having a request code which identifies the desired system service, along with other information that will be needed by the service, such as where to send the response and who is sending the request. With the help of the CTOS kernel, the request travels transparently to the user or application program across the network to locate any special service. An application running on a CTOS workstation may include a plurality of processes. For example, an electronic mail application may typically have at least two processes. One process allows the user to edit a mail message, while the other process monitors incoming mail. These electronic mail processes compete with each other for use of the workstation microprocessor as well as with processes from other running applications (such as a word processor application and a compiler application) . Since a CTOS workstation typically contains only a single microprocessor (e.g., a 80486 Intel processor), process scheduling is required in order to permit a plurality of applications to run on the workstation at the same time. This is performed by the CTOS kernel scheduler. Each process (thread of execution) within CTOS is assigned a priority and is scheduled for execution by the microprocessor based upon that priority. Process scheduling is driven by events. Whenever an event occurs during execution of a process, such as an input/output event, the executing process can lose control of the processor in favor of a higher-priority process. This type of scheduling is called event-driven, priority-ordered scheduling.

In CTOS, the functions normally associated with an operating system are performed by system services which manage resources and provide services that are requested by application program processes and other system service processes. They communicate with their application program clients using the previously described messages. Examples of CTOS system services include opening or closing disk files or accepting keyboard input. Because of their standard message-based interfaces, system services can be loaded dynamically, substituted for, or removed as desired.

The manner of providing a system service in a CTOS operating system is well known to those familiar with CTOS.

A particular advantage made possible by CTOS's built-in networking is that a system service can operate transparently across a network to the process that requests its service. For example, an application process on one workstation can send off a request message to a system service to have a certain job performed without knowledge of where the system service resides. If the service does not reside on the local workstation, the request message is automatically routed across the network to the workstation where the service resides. The response message returns in the same way.

In prior art CTOS systems, each application running on a workstation resides in a particular assigned partition of the workstation memory. In addition, a particular portion of the workstation memory is assigned to each application for use in running the application. Although it has been generally recognized that virtual demand-paging could be provided on CTOS systems using 80386 Intel ® (and later) microprocessors, it was not provided due to the belief that overall performance would not be

sufficiently enhanced. While the particular virtual demand-paging provided by the present invention is applicable to other types of operating systems, it is particularly advantageous when used in a CTOS system, since it significantly enhances CTOS performance at a workstation running a plurality of applications.

A preferred manner for providing virtual demand- paging for a CTOS workstation in accordance with the invention will now be described. Preferably, this paging capability is provided for CTOS as a system service that is used by all applications running at a workstation. The manner in which such a CTOS system service may be designed for implementing virtual demand paging in accordance with the invention will become evident from the description provided herein. For this purpose, all available physical memory may be considered as divided, for example, into 4KB (4,000-byte) pages.

Fig. 2 schematically illustrates three application Al, A2 and A3 and their associated pages running on a CTOS workstation WS having a main memory M and a local disk D. For example, Al may be a word processor application program, A2 may be a compiler application program (such as used by a programmer for program development), and A3 may be a mail program for sending and receiving messages.

Each application (A1,A2,A3) is provided with a respective page table (P1,P2,P3) and a respective local clock (C1,C2,C3). Each application typically is allowed a maximum number of assignable memory pages which it may use during execution. For example, word processor application program Al may be allowed a maximum of 100 assigned pages, compiler application program A2 may be allowed a maximum

of 70 assigned pages, and mail application program A3 may be allowed a maximum of 50 assigned pages. If memory M has a total of 120 assignable pages, the sum of the pages assigned to all running applications at any time cannot exceed 120 pages, regardless of whether an application has been assigned its number of maximum pages. Note that workstation WS in Fig. 2 also illustrates a free page list FPL for keeping track of page assignment, a cleaning queue CQ for cleaning dirty pages, and an activity queue AQ for indicating relative application activity. These will be further described hereinafter.

Fig. 3 illustrates a typical page table (P1,P2,P3) which may be used by each application. As shown, each entry in the page table includes page identifying data p^ identifying a particular assigned memory page, an access bit a^ which indicating whether the page was referenced by its application since the last test, and a "dirty" page bit d^ indicating whether the page contains written-to data which must be written back to its source location, such as a disk drive. Each page table entry may also include other information indicated by o^.

CTOS allocates a maximum number of assignable pages to an application when the application is started.

CTOS also creates a local clock for the application at that time for use in determining which page of the application should be replaced when replacement is required. The basic arrangement of such a local clock is schematically illustrated in Fig. 4, wherein memory pages Pgl, Pg2, PgN designate pages which have been assigned to the application are arranged in a circular list, like the circumference of a clock. The number of assigned memory pages is not permitted to exceed the maximum assignable pages for that

application. The clock pointer (or hand) cp points to the last page replaced, and advances clockwise when the local clock is invoked to search for a replaceable page.

Operation during a local clock search for a replaceable page is illustrated by the flowchart in Fig. 5. When the clock pointer cp is advanced to the next page (step 500), the setting of the access bit a^ in the corresponding page table entry is tested (step 502) to determine whether the page was referenced by the application since the last test. If this access bit a^ is found to be set (step 502), the page is considered to be a page of the currently active working pages of the application, and is thereby not eligible for replacement. In such case, this access bit a.^ is reset (step 504), the flow proceeds back to step 500 to continue the search.

If, on the other hand, access bit a^ of the next page is found not to be set in step 502, the setting of the dirty page bit d^ is then examined (step 506). If bit d^ is not set, indicating that the page is clean (i.e., it need not be written back to its source location, such as a disk), then the page is designated as being eligible for replacement (step 506). However, if it is found in step 506, that bit d^ is set, indicating that the page is dirty, then the page is placed on the cleaning queue CQ (Fig. 2) and the flow returns to step 500 to continue the search. A priority may be provided for pages in the cleaning queue CQ so that certain pages in CQ are cleaned ahead of others. After a page is cleaned, its bit d^ in the page table of its respective application is reset to indicate that the page is now clean.

Next to be described is a preferred implementation of a combined global and local page

replacement policy in accordance with the invention using a local clock for the running application, as described above in connection with Figs.4 and 5. For this purpose it will be assumed, as before, that a CTOS workstation having a maximum of 120 assignable pages has concurrently running thereon a word processor application Al, a compiler application A2 and a mail application A3 having assigned page maximums of 100, 50 and 30, respectively. It will be understood that, when all three of these application are running on a workstation, one of the application will be running in the foreground (the foreground application being the one which controls the keyboard and usually at least some portion of the display screen)_, while the other two applications will be running in the background. For example, the word processor application could be running in the foreground permitting a user to control the keyboard and display, so as to thereby perform word processing operations as if no other applications wee running. The compiler and mail application would then be running in the background. The compiler application could, for example, be compiling a special-purpose program previously developed by a user, while the mail application could be waiting for receipt of a mail message. If a mail message arrives, the user could be signaled of the receipt of this message by a flashing marker on the screen. The user may then, by appropriate keyboard entry, switch to the mail application program to read the message. The mail application would then be in the foreground while the word processor application would run in the background along with the compiler application.

As illustrated in the flowchart of Fig. 6, whenever one of the running application requests a memory

access, the page table is checked (step 600) to determine whether the page containing the information to be accessed is present in one of the- application's assigned pages. If the page is found to be present (step 602), the page is accessed by the application (step 604). Otherwise, a page fault occurs causing operation to proceed to the flowchart of Fig. 7, which illustrates how a page fault is handled. As illustrated in Fig. 7, the occurrence of a page fault invokes the virtual demand-paging service (step 700) which suspends performance of the application which caused the fault (step 702). The paging service then checks to determine whether either the application or workstation page maximum has been reached (step 704). If not, the paging service causes a free (unassigned) workstation memory page (indicated in the free page list FPL in Fig. 2) to be assigned to the application which experienced the fault, following which the requested page is read into this newly assigned page (step 706) the application is then restarted (step 708). Since a CTOS system is being used, this page may advantageously be obtained from a local disk at the workstation or transparently across the network from the server workstation.

If, on the other hand, step 704 in Fig. 8 finds that either an application or workstation page maximum had been reached, then page replacement is required, which is performed as illustrated in Fig. 8 or Fig. 9, depending on whether a page maximum was found for the application (Fig. 8) or for the workstation (Fig. 9). The application page maximum situation illustrated in Fig. 8 will be considered first.

As illustrated in Fig. 8, page replacement for the situation where the application has reached its assigned page maximum begins with the search for a replaceable page in the application's local clock (step 800). This search is accomplished as previously described in connection with Figs. 4 and 5. If a replaceable page is found in the application 's local clock (step 802), the "not present" page requested by the application is obtained (e.g., from the local or server disk) and read into the designated replaceable page (step 804), following which the application is restarted (step 806) .

If, on the other hand, step 802 in Fig. 7 finds no replaceable page after going all the way around the application's local clock, a second go-around of the local clock is initiated (step 808). Since each page access bit aj_ was reset during the first go-around, the search for a replaceable page on the second go-around is based on finding the first occurring clean page (i.e., a page which does not have di set). If a clean page is found, it is designated as a replaceable page (step 810). The flow then proceeds to the previously described steps 804 and 806, wherein the "not present" page is read in to replace the found replaceable page, and the application restarted. As illustrated in Fig. 8, if step 810 indicates that no clean page was found during the second go-around of the application's local clock, the flow then proceeds to step 812 to determine whether there is a page in the cleaning queue CQ (Fig. 2) which the application can wait to be cleaned. If so, the application waits (step 814) until the page is cleaned. The cleaned page is then designated as replaceable and the flow then proceeds to

steps 804 and 806, as before, to read in the requested "not present" page to replace this designated replaceable page, and to restart the application. However, if step 812 indicates that there is no page being cleaned which the application can wait for, an error indication is provided. Fig. 9 illustrates how page replacement is handled for the second type of replacement situation where a page fault cannot be satisfied (even though the application's assigned page maximum has not been reached) because the workstation has used up its maximum number of assignable pages. It will be remembered that the previous example assumed that the workstation had a maximum of 120 assignable pages, while the word processor application Al was allowed a maximum of 100 assigned pages, the compiler application A2 was allowed a maximum of 50 assigned pages and the mail application A3 was allowed a maximum of 30 assigned pages. For example, if applications Al, A2 and A3 have been assigned 80 pages, 30 pages and 10 pages, respectively, and a page fault occurs because the word processor application Al requests a "not present" page, the workstation will not be able to satisfy this page fault because the workstation page maximum of 120 pages (80+30+10) has been reached. This is the type of page replacement situation to which Fig. 9 is directed. Basically, the flow in Fig. 9 tries to steal a page from another application. For this purpose, the workstation activity queue AQ (Fig. 2) is first checked (step 900) to determine which of the other applications running on the workstation is the least active. In the preferred embodiment being described, this activity queue AQ is designed to queue running applications in an order based on which application least recently experienced a

page fault. For example, if word processor application Al most recently has a page fault, and mail application A3 least recently had a page fault, then A3 will be the least active application, followed by A2 and lastly by Al. In such case, step 900 in Fig. 9 will select A3 as the least active application from which to try to steal a page.

Step 902 in Fig. 9 checks whether the least active application selected in step 900 is in the foreground (i.e., currently being used by the user) and, if so, chooses the next most active application (step 904) from which to steal a page. The reason for not using a foreground application is that a foreground application, because of its foreground use, may imminently require access to its pages, and thus should not be subject to having one of its pages stolen.

Having thus identified the application from which a page is to be stolen (steps 900,902,904), the flow in Fig. 9 proceeds to the chosen application's local clock (step 906) to search for a replaceable page, which may be accomplished in a similar manner to that previously described in connection with Figs. 4, 5 and 7. This search may be modified in various respects. For example, for the purpose of step 906 in Fig. 9, the local clock page replacement search may be limited to just a single go-around of the local clock.

If a replaceable page is found (step 908) the flow proceeds to step 910 wherein the replaceable page found in step 906 is stolen and assigned to the application which caused the page fault. The requested "not present" page is then read into this newly assigned page, and the application which caused the page fault is then restarted (step 912) .

If no replaceable page is found is step 908, an attempt is made to steal a page from another applicat.ion (step 914). This is preferably accomplished by searching the local clocks of other applications (in a manner similar to that performed in step 906) beginning with the next least active application which is not a foreground application, and so on to other applications until a replaceable page is found. The flow then returns to step 910 to complete the steal. If a replaceable page is still not found (step 916), then an attempt is made to find a replaceable page in the local clock of the application which caused the page fault (step 918), as previously described in connection with Fig. 7. If even this does not result in finding a replaceable page (step 920), an error indication is provided. Alternatively, another search of the other applications could be made, as before, since a page that was previously not replaceable could have become replaceable. Such a repeat search could be performed before searching the local clock of the application which caused the fault.

It is to be understood that the above description of combined global and local virtual demand-paging in a CTOS system is only exemplary, since many modifications and variations in construction, arrangement and use are possible within the scope of the invention. For example, the invention is applicable to operating systems other than CTOS. Also, significantly different implementations and algorithms may be provided without departing from the true scope and spirit of the invention. Accordingly, the present invention is to be considered as encompassing all possible modifications and variations coming within the scope of the appended claims.