Page 436 - DCAP103_Principle of operating system

Unit 14: Case Study of Linux Operating System

swapped in, the process is deemed ‘’in memory’’ and can be scheduled to run. The pages of the Notes
text, data, and stack segments are brought in dynamically, one at a time, as they are referenced. If
the user structure and page table are not in memory, the process cannot be run until the swapper
brings them in. Paging is implemented partly by the kernel and partly by a new process called
the page daemon. The page daemon is process 2 (process 0 is the idle process traditionally called
the swapper and process 1 is in it, as shown in Figure 14.12).

Like all daemons, the page daemon is started up periodically so it can look around to see if there is
any work for it to do. If it discovers that the number of pages on the list of free memory pages is too
low, it initiates action to free up more pages. Linux is a demand-paged system with no prepaging and
no working set concept (although there is a system call in which a user can give a hint that a certain
page may be needed soon, in the hopes it will be there when needed). Text segments and mapped
files are paged to their respective files on disk. Everything else is paged to either the paging partition
(if present) or one of the fixed-length paging files, called the swap area. Paging files can be
added and removed dynamically and each one has a priority. Paging to a separate partition,
accessed as a raw device, is more efficient than paging to a file for several reasons. First, the
mapping between file blocks and disk blocks is not needed (saves disk I/O reading indirect
blocks). Second, the physical writes can be of any size, not just the file block size. Third, a page
is always written contiguously to disk; with a paging file, it may or may not be.
Pages are not allocated on the paging device or partition until they are needed. Each device and
file starts with a bitmap telling which pages are free. When a page without backing store has to
be tossed out of memory, the highest priority paging partition or file that still has space is chosen
and a page allocated on it. Normally, the paging partition, if present, has higher priority than
any paging file. The page table is updated to reflect that the page is no longer present in memory
(e.g., the page-not-present bit is set) and the disk location is written into the page table entry.
14.4.8 Page Replacement Algorithm

Page replacement works as follows. Linux tries to keep some pages free so they can be claimed
as needed. Of course, this pool must be continually replenished, so the PFRA (Page Frame
Reclaiming Algorithm) algorithm is how this happens.
First of all, Linux distinguishes between four different types of pages: unreclaimable, swappable,
syncable, and discardable. Unreclaimable pages, which include reserved or locked pages,
kernel mode stacks, etc., may not be paged out. Swappable pages must be written back to the
swap area or the paging disk partition before the page can be reclaimed. Syncable pages must
be written back to disk if they have been marked as dirty. Finally, discardable pages can be
reclaimed immediately.

At boot time, init starts up a page daemon, kswapd, one per each memory node, and configures
them to run periodically. Each time kswapd awakens, it checks to see if there are enough free
pages available, by comparing the low and high watermarks with the current memory usage for
each memory zone. If there is enough memory, it goes back to sleep, although it can be awakened
early if more pages are suddenly needed. If the available memory for any of the zones falls
below a threshold, kswapd initiates the page frame reclaiming algorithm. During each run, only
a certain target number of pages is reclaimed, typically 32. This number is limited to control
the I/O pressure (the number of disk writes, created during the PFRA operations). Both, the
number of reclaimed pages and the total number of scanned pages are configurable parameters.
Each time PFRA executes, it first tries to reclaim easy pages, then proceeds with the harder
ones. Discardable and unreferenced pages can be reclaimed immediately by moving them onto
the zone’s freelist. Next, it looks for pages with backing store which have not been referenced
recently, using a clock-like algorithm. Following are shared pages that none of the users seems

LOVELY PROFESSIONAL UNIVERSITY 429