|
|
|
Modern Operating Systems by Herbert Bos and Andrew S. Tanenb...
Modern_Operating_Systems_by_Herbert_Bos_and_Andrew_S._Tanenbaum_4th_Ed.pdf
Showing 245 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 245
214
MEMORY MANAGEMENT
CHAP. 3
page table entry for the page just referenced. When a page fault occurs, the operat-
ing system examines all the counters in the page table to find the lowest one. That
page is the least recently used.
3.4.7 Simulating LRU in Software
Although the previous LRU algorithm is (in principle) realizable, few, if any,
machines have the required hardware. Instead, a solution that can be implemented
in software is needed.
One possibility is called the
NFU
(
Not Frequently Used
)
algorithm. It requires a software counter associated with each page, initially zero.
At each clock interrupt, the operating system scans all the pages in memory. For
each page, the
R
bit, which is 0 or 1, is added to the counter.
The counters roughly
keep track of how often each page has been referenced. When a page fault occurs,
the page with the lowest counter is chosen for replacement.
The main problem with NFU is that it is like an elephant: it never forgets any-
thing. For example, in a multipass compiler, pages that were heavily used during
pass 1 may still have a high count well into later passes.
In fact, if pass 1 happens
to have the longest execution time of all the passes, the pages containing the code
for subsequent passes may always have lower counts than the pass-1 pages. Conse-
quently, the operating system will remove useful pages instead of pages no longer
in use.
Fortunately, a small modification to NFU makes it able to simulate LRU quite
well. The modification has two parts. First, the counters are each shifted right 1 bit
before the
R
bit is added in. Second, the
R
bit is added to the leftmost rather than
the rightmost bit.
Figure 3-17 illustrates how the modified algorithm, known as
aging
, works.
Suppose that after the first clock tick the
R
bits for pages 0 to 5 have the values 1,
0, 1, 0, 1, and 1, respectively (page 0 is 1, page 1 is 0, page 2 is 1, etc.).
In other
words, between tick 0 and tick 1, pages 0, 2, 4, and 5 were referenced, setting their
R
bits to 1, while the other ones remained 0.
After the six corresponding counters
have been shifted and the
R
bit inserted at the left, they have the values shown in
Fig. 3-17(a).
The four remaining columns show the six counters after the next four
clock ticks.
When a page fault occurs, the page whose counter is the lowest is removed. It
is clear that a page that has not been referenced for, say, four clock ticks will have
four leading zeros in its counter and thus will have a lower value than a counter
that has not been referenced for three clock ticks.
This algorithm differs from LRU in two important ways. Consider pages 3 and
5 in Fig. 3-17(e).
Neither has been referenced for two clock ticks; both were refer-
enced in the tick prior to that. According to LRU, if a page must be replaced, we
should choose one of these two. The trouble is, we do not know which of them was
referenced last in the interval between tick 1 and tick 2.
By recording only 1 bit
per time interval, we have now lost the ability to distinguish references early in the
Ace your assessments! Get Better Grades
Browse thousands of Study Materials & Solutions from your Favorite Schools
Concordia University
Concordia_University
School:
Operating_Systems
Course:
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
Know more
Students also viewed documents
lab 18.docx
lab_18.docx
Course
Course
3
Module5QuizSTA2023.d...
Module5QuizSTA2023.docx.docx
Course
Course
10
Week 7 Test Math302....
Week_7_Test_Math302.docx.docx
Course
Course
30
Chapter 1 Assigment ...
Chapter_1_Assigment_Questions.docx.docx
Course
Course
5
Week 4 tests.docx.do...
Week_4_tests.docx.docx
Course
Course
23
Week 6 tests.docx.do...
Week_6_tests.docx.docx
Course
Course
106
