|
|
|
Modern Operating Systems by Herbert Bos and Andrew S. Tanenb...
Modern_Operating_Systems_by_Herbert_Bos_and_Andrew_S._Tanenbaum_4th_Ed.pdf
Showing 243-244 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 243
212
MEMORY MANAGEMENT
CHAP. 3
3.4.4 The Second-Chance Page Replacement Algorithm
A simple modification to FIFO that avoids the problem of throwing out a heav-
ily used page is to inspect the
R
bit of the oldest page.
If it is 0, the page is both
old and unused, so it is replaced immediately.
If the
R
bit is 1, the bit is cleared,
the page is put onto the end of the list of pages, and its load time is updated as
though it had just arrived in memory. Then the search continues.
The operation of this algorithm, called
second chance
, is shown in Fig. 3-15.
In Fig. 3-15(a) we see pages
A
through
H
kept on a linked list and sorted by the
time they arrived in memory.
(a)
Page loaded first
Most recently
loaded page
0
A
3
B
7
C
8
D
12
E
14
F
15
G
18
H
(b)
A is treated like a
newly loaded page
3
B
7
C
8
D
12
E
14
F
15
G
18
H
20
A
Figure 3-15.
Operation of second chance.
(a) Pages sorted in FIFO order.
(b) Page list if a page fault occurs at time 20 and
A
has its
R
bit set. The numbers
above the pages are their load times.
Suppose that a page fault occurs at time 20.
The oldest page is
A
, which arriv-
ed at time 0, when the process started.
If
A
has the
R
bit cleared, it is evicted from
memory, either by being written to the disk (if it is dirty), or just abandoned (if it is
clean). On the other hand, if the
R
bit is set,
A
is put onto the end of the list and its
‘‘load time’’ is reset to the current time (20).
The
R
bit is also cleared. The search
for a suitable page continues with
B
.
What second chance is looking for is an old page that has not been referenced
in the most recent clock interval. If all the pages have been referenced, second
chance degenerates into pure FIFO.
Specifically, imagine that all the pages in
Fig. 3-15(a) have their
R
bits set. One by one, the operating system moves the
pages to the end of the list, clearing the
R
bit each time it appends a page to the end
of the list. Eventually, it comes back to page
A
, which now has its
R
bit cleared.
At
this point
A
is evicted. Thus the algorithm always terminates.
3.4.5 The Clock Page Replacement Algorithm
Although second chance is a reasonable algorithm, it is unnecessarily inef-
ficient because it is constantly moving pages around on its list.
A better approach
is to keep all the page frames on a circular list in the form of a clock, as shown in
Fig. 3-16.
The hand points to the oldest page.
Page 244
SEC. 3.4
PA GE
REPLACEMENT ALGORITHMS
213
When a page fault occurs,
the page the hand is
pointing to is inspected.
The action taken depends
on the R bit:
R = 0: Evict the page
R = 1: Clear R and advance hand
A
B
C
D
E
F
G
H
I
J
K
L
Figure 3-16.
The clock page replacement algorithm.
When a page fault occurs, the page being pointed to by the hand is inspected.
If its
R
bit is 0, the page is evicted, the new page is inserted into the clock in its
place, and the hand is advanced one position.
If
R
is 1, it is cleared and the hand is
advanced to the next page. This process is repeated until a page is found with
R
=
0. Not surprisingly, this algorithm is called
clock
.
3.4.6 The Least Recently Used (LRU) Page Replacement Algorithm
A good approximation to the optimal algorithm is based on the observation
that pages that have been heavily used in the last few instructions will probably be
heavily used again soon. Conversely, pages that have not been used for ages will
probably remain unused for a long time. This idea suggests a realizable algorithm:
when a page fault occurs, throw out the page that has been unused for the longest
time. This strategy is called
LRU
(
Least Recently Used
) paging.
Although LRU is theoretically realizable, it is not cheap by a long shot.
To
fully implement LRU, it is necessary to maintain a linked list of all pages in mem-
ory, with the most recently used page at the front and the least recently used page
at the rear. The difficulty is that the list must be updated on every memory refer-
ence. Finding a page in the list, deleting it, and then moving it to the front is a very
time consuming operation, even in hardware (assuming that such hardware could
be built).
However, there are other ways to implement LRU with special hardware. Let
us consider the simplest way first. This method requires equipping the hardware
with a 64-bit counter,
C
, that is automatically incremented after each instruction.
Furthermore, each page table entry must also have a field large enough to contain
the counter. After each memory reference, the current value of
C
is stored 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
