Page 437 - DCAP103_Principle of operating system

Principles of Operating Systems

Notes to be using much. The challenge with shared pages is that, if a page entry is reclaimed, the
page tables of all address spaces originally sharing that page must be updated in a synchronous
manner. Linux maintains efficient tree like data structures to easily find all users of a shared page.
Ordinary user pages are searched next, and if chosen to be evicted, they must be scheduled for
write in the swap area. The swappiness of the system, that is, the ratio of pages with backing
store versus pages which need to be swapped out selected during PFRA, is a tunable parameter
of the algorithm.

Finally, if a page is invalid, absent from memory, shared, locked in memory, or being used for
DMA, it is skipped. PFRA uses a clock-like algorithm to select old pages for eviction within a
certain category. At the core of this algorithm is a loop which scans through each zone’s active
and inactive lists, trying to reclaim different kinds of pages, with different urgency. The urgency
value is passed as a parameter telling the procedure how much effort to expend to reclaim some
pages. Usually, this means how many pages to inspect before giving up.

During PFRA, pages are moved between the active and inactive list in a manner described in
Figure 14.18 maintain try to find pages which have not been referenced and are unlikely to be
needed in the near future, PFRA maintains two flags per page—active/inactive, and referenced
or not. These two flags encode four states, as shown in Figure 14.18 during first set of pages,
PFRA first clears their reference bits. If during the second run over the page it is determined that
it has been referenced, it is advanced to another state, from which it is less likely to be reclaimed.
Otherwise, the page is moved to a state from where it will more likely to be evicted. Pages on
the inactive list, which have not been referenced since the last time they were inspected, are best
candidates for eviction. These correspond to pages with both PG active and PG referenced equal
to zero in Figure 14.18 ever necessary, pages may be reclaimed even if they are in some of the
other states. The refill arrows in Figure 14.18 considered in the page frame replacement algorithm.

Figure 14.18: Refill Arrows in Page Frame Replacement Algorithm

Inactive Active

PG_active=0 refill PG_active=0
PG_referenced=1 PG_referenced=1
refill

used timeout timeout used
used

PG_active=0 refill PG_active=0
PG_referenced=1 PG_referenced=1

The reason PRFA maintains pages in the inactive list although they might have referenced is
to prevent following situations. Consider a process which makes periodic accesses to different
pages, with a 1-hour period. A page accessed since the last loop will have its reference flag set.
However, since it will not be needed again for the next hour, there is no reason not to consider
it as a candidate for reclamation.

One other aspect of the memory management system that we have not yet mentioned is a second
daemon, pdflush, actually a set of background daemon threads. The pdflush threads either

430 LOVELY PROFESSIONAL UNIVERSITY