Information Technology Reference
In-Depth Information
the lru page replacement in linux
For example, a process will be killed in Linux to
release its memory space when the process keeps
being denied its requested pages.A process will be
swapped out for the same purpose in the 4.4 BSD
operating system. If the free page pool cannot be
filled in a timely manner, the system will start to
swap out or remove processes.
Unfortunately, the existence of false LRU
pages makes kernel function __get_free_pages()
in Linux (and the pageout daemon in 4.4 BSD)
easily and quickly find “qualified” pages, includ-
ing many false LRU pages, to fill the free page
pool. As the result, the system can be involved
in a “pre-thrashing” state for a significantly long
period of time before the kernel is awakened to
swap out or remove processes. The CPU utiliza-
tion in the pre-thrashing state can be extremely
low due to the large number of page faults. The
system developers of the 4.4 BSD operating sys-
tem points out that the system performance can
be much better when the memory scheduling is
done by page replacement operations than when
the process swapping is used [McKusick et al.
1996]. The swap token mechanism is a page-
replacement-oriented memory scheduling scheme
to address the thrashing issue before the system
has to swap out or remove processes.
An approximate LRU algorithm is adopted in
the Linux kernels as its global page replacement
policy. When a page fault occurs, kernel func-
tion do_page_fault() will be called to handle it.
If the page fault is caused by a legal access to a
page missed in memory but stored in the swap
file on disk, the kernel will try to get a free page
in memory and load the requested page from the
swap file by kernel function do_swap_page() .
If there are no free memory pages available, the
kernel will make a room for the page by selecting
a victim page from the memory for replacement.
If the replaced page is dirty, it has to be written
back first to the swap file, which also contributes
to the number of major page faults (NPF).
To select victim pages, kernel function __
get_free_pages() is invoked by the swap daemon
kswapd , which is waken up when the free physical
memory space is below a threshold or when a page
faulted program cannot find a page from the free
page pool. The function will look into the process
space of each eligible process in the system to see
if it is a candidate from which memory pages can
be found for swapping. It always starts from the
process with the largest resident pages. The kernel
will then check through all of the virtual memory
pages in the page table of the selected process.
Generally, once the kernel finds that the reference
bit of a page table entry is turned off (indicating
that the page has not been accessed since it was
reset last time by the function), the kernel will
select the page for replacement. If the bit is on,
the kernel will turn it off, and keep checking the
next page in the table. If no pages can be replaced
from this process, the next candidate process will
be tried. This implementation effectively emulates
the behavior of the LRU replacement algorithm
with a small overhead. However it also generates
false LRU pages during concurrent execution of
programs as we have discussed.
Most operating systems have protection
mechanisms to resolve serious thrashing problems.
the implementation of the
Swap token in linux
The basic idea of the swap token mechanism is to
keep false LRU pages from spreading over all the
concurrently running processes, and to make the
working set of at least one process be identified and
established. A token is a newly introduced global
and mutually exclusive variable in the kernel,
which has two states, indicating either the token
is available or the token has been taken by a page
faulted process. The token is initialized when the
system is booted. In the implementation, a process
requests the token right before it invokes func-
tion do_swap_page() , which is called right after
a page fault occurs and before the page is loaded
Search WWH ::




Custom Search