Page 373 - DCAP103_Principle of operating system

Principles of Operating Systems

Notes If a page fault occurs and the working set is smaller than the minimum, the page is added. On
the other hand, if a page fault occurs and the working set is larger than the maximum, a page
is evicted from the working set (but not from memory) to make room for the new page. This
algorithm means that Windows 2000 uses a local algorithm, to prevent one process from hurting
others by hogging memory. However, the system does try to tune itself to some extent. For
example, if it observes that one process is paging like crazy (and the others are not), the system
may increase the size of its maximum working set, so that over time, the algorithm is a mix of
local and global. There is an absolute limit on the working set size, however: even if there is only
one process running, it may not take the last 512 pages, to leave some slack for new processes.
So far, so good, but the story is not over yet. Once a second, a dedicated kernel daemon thread,
the balance set manager, checks to see if there are enough free pages. If there are not enough, it
starts the working set manager thread to examine the working sets and recover more pages. The
working set manager first determines the order to examine the processes in. Large processes that
have been idle for a long time are considered before small active processes and the foreground
process is considered last.

The working set manager then starts inspecting processes in the chosen order. If a process’
working set is currently less than its minimum or it has incurred more than a certain number
of page faults since the last inspection, it is passed over. Otherwise, one or more pages are
removed. The target number of pages to remove is a complicated function of the total RAM
size, how tight memory is, how the current working set size compares to the process’ minimum
and maximum, and other parameters. All the pages are examined in turn.
On a uniprocessor, if a page’s reference bit is clear, a counter associated with the page is
incremented. If the reference bit is set, the counter is set to zero. After the scan, the pages with the
highest counters are removed from the working set. The thread continues examining processes
until it has recovered enough pages, then it stops. If a complete pass through all processes still
has not recovered enough pages, it makes another pass, trimming more aggressively, even
reducing working sets below their minimum if necessary.

On a multiprocessor, looking at the reference bit does not work because although the current
CPU may not have touched the page recently, some other one may have. Examining another
CPU’s reference bits is too expensive to do. Consequently, the reference bit is not examined and
the oldest pages are removed.
It should be noted that for page replacement purposes, the operating system itself is regarded
as a process. It owns pages and also has a working set. This working set can be trimmed.
However, parts of the code and the nonpaged pool are locked in memory and cannot be paged
out under any circumstances.
12.3.6 Physical Memory Management

Above we mentioned that there were actually four free lists. Now it is time to see what all of
them are for. Every page in memory is either in one or more working sets or on exactly one of
these four lists, which are illustrated in Figure 12.13. The standby (clean) and modified (dirty)
lists hold pages that have recently been evicted from a working set, are still in memory, and
are still associated with the process that was using them. The difference between them is that
clean pages have a valid copy on disk and can thus be abandoned at will, whereas dirty pages
do not have an up-to-date copy on disk. The free list consists of clean pages that are no longer
associated with any process. The pages on the zeroed page list are not associated with any
process and are also filled with zeros. A fifth list holds any physically defective RAM pages
that may exist to make sure that they are not used for anything.

366 LOVELY PROFESSIONAL UNIVERSITY