The page management algorithm (system working set method, SYS-WS) manages the main memory pages globally and the pages are split up into five groups according to their “access age” as follows:
Group 1 | Pages that have just been assigned the frame | Active groups: System working set Pages in these groups can be accessed without hardware interruption |
Group 2 | Pages that had a reference, had not run out of CPU time, or deserved a second chance | |
Group 3 | Pages dedicated to the review of the reference indicator | |
Group 4 | Pages that have been identified as candidates for displacement from the system working set during the periodic working set review | |
Group 5 | Read Write Queue: Pages that still need to be saved to the paging area Read Only Queue: Pages that have a copy on the paging area Empty Queue: Free Frames | Inactive group: |
The pages in each group - more precisely the hardware frames on which the pages are located - are chained with one another.
Principle of execution
As a rule, as many pages as possible are kept active. As a result the “free pool” is relatively small. However, it must have a certain minimum size in order to satisfy page requests that follow in rapid succession. When the minimum size is reached, free pool regulation is therefore carried out with the aim of always having enough free frames in the Empty Queue.
The system working set algorithm uses the LRU (Least Recently Used) method to select the pages that remain accessible in main memory and the pages that are removed from the system working set to be pushed into the free pool:
- Modified pages are appended to the Read Write Queue because the page content still has to be saved in the paging area. By writing back pages from the Read Write Queue and then reassigning them to the Read Only Queue, the paging routine ensures that the Read Only Queue is normally never empty.
Unmodified pages are appended to the Read Only Queue, since a copy of the page already exists in the paging area.
When a main memory page is released, the associated frame is placed in the Empty Queue.
If a main memory page is requested, the system takes a frame from group 5, fills it with the current page content from the paging area or - for newly requested pages - with zeros and then puts it in group 1. Then the page is accessible and the reference indicator is set.
Except in the case of a reclaim, in which the owner re-accesses an already deactivated page in the free pool, the system always serves page requests from the Empty Queue, which contains the unused frames. If this makes the Empty Queue too small, it is filled with pages from the Read Only Queue. This contains pages that can be overwritten because their content is already saved on the paging area. With the transition to the Empty Queue, the pages "lose" their owner and then no reclaim is possible.
The Empty Queue and the Read Only Queue form the pool from which the system can immediately satisfy memory requests. If this supply becomes too small, the system writes pages from the Read Write Queue, which contains pages with new / changed content, to the paging area. At the end of the write process, the pages in the memory can be overwritten and are placed in the Read Only Queue. To determine whether a page has been referenced, the hardware (reproduced on x86 servers by X2000) sets the associated reference indicator when the page is accessed.
The following applies to the system working set procedure:
- Referenced pages always remain in the system working set.
- Task local pages remain in the system working set even if not referenced, if the task has not consumed a certain CPU time since the last access.
- Global pages remain in the system working set again if they are not referenced, i.e. they get a second chance and are only displaced in the subsequent check if there is no reference by then.
- Fixed pages always remain in the system working set.
The system working set procedure is carried out both on-demand in the event of bottlenecks in the free pool and periodically at certain intervals or when a logical machine enters the 'IDLE' state.
The simple SYS-WS algorithm results in a reduction in paging management outlay, albeit at the expense of reduced accuracy in determining the working set requirements of the individual tasks. The reduction in outlay is especially noticeable in the case of large main memories.
If a task is deactivated, it retains its working set even if it is in the inactive state. If the task is reactivated, no “page reclaims” are necessary to restore the working set.
While the SYS-WS procedure knows the UPG value (used pages) of every task, it has no means of determining which phase the task is in (even inactive tasks have a UPG value ≠ 0.) .
Calculation of the PPC value (planned page count) is therefore approximate: the UPG value is compared with an assumed mean working set value, dependent on the category type.
Since as many pages as possible are kept active, the total UPG value is practically always in the magnitude of the available paging main memory and has only limited relevance. The working set requirements are expressed exclusively by the PPC value. This value represents only a rough estimate. With todays large memory configurations advantages result from the fact that no outlay is necessary for estimating exact memory requirements, as they are superfluous.