Modern Operating Systems by Herbert Bos ...
Modern_Operating_Systems_by_Herbert_Bos_and_Andrew_S._Tanenbaum_4th_Ed.pdf-M ODERN O PERATING S YSTEMS
Showing 797 out of 1137
Modern Operating Systems by Herbert Bos and Andrew...
Modern_Operating_Systems_by_Herbert_Bos_and_Andrew_S._Tanenbaum_4th_Ed.pdf-M ODERN O PERATING S YSTEMS
Modern Operating Systems by Herbert...
Modern_Operating_Systems_by_Herbert_Bos_and_Andrew_S._Tanenbaum_4th_Ed.pdf-M ODERN O PERATING S YSTEMS
Page 797
CHAP. 10
Each time PFRA executes, it first tries to reclaim easy pages, then proceeds
with the harder ones.
Many people also grab the low-hanging fruit first. Dis-
cardable 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 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 ef-
ficient 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
of the system, that is, the ratio of pages
with backing store vs. 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 cer-
tain 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 dif-
ferent urgencies. 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 the
manner described in Fig. 10-18. To maintain some heuristics and 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 Fig. 10-18. During the first scan of a 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 is more likely to be evicted.
Pages on the inactive list, which have not been referenced since the last time
they were inspected, are the best candidates for eviction. They are pages with both
set to zero in Fig. 10-18. However, if necessary,
pages may be reclaimed even if they are in some of the other states. The
arrows in Fig. 10-18 illustrate this fact.
The reason PRFA maintains pages in the inactive list although they might have
been referenced is to prevent situations such as the following. Consider a process
which makes periodic accesses to different pages, with a 1-hour period. A page ac-
cessed 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 candi-
date for reclamation.
One aspect of the memory-management system that we have not yet mention-
ed is a second daemon,
, actually a set of background daemon threads. The
threads either (1) wake up periodically, typically every 500 msec, to write

Ace your assessments! Get Better Grades
Browse thousands of Study Materials & Solutions from your Favorite Schools
Concordia University
Great resource for chem class. Had all the past labs and assignments
Leland P.
Santa Clara University
Introducing Study Plan
Using AI Tools to Help you understand and remember your course concepts better and faster than any other resource.
Find the best videos to learn every concept in that course from Youtube and Tiktok without searching.
Save All Relavent Videos & Materials and access anytime and anywhere
Prepare Smart and Guarantee better grades

Students also viewed documents