|
|
|
Modern Operating Systems by Herbert Bos and Andrew S. Tanenb...
Modern_Operating_Systems_by_Herbert_Bos_and_Andrew_S._Tanenbaum_4th_Ed.pdf
Showing 251-252 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 251
220
MEMORY MANAGEMENT
CHAP. 3
2204
Current virtual time
1213 0
2084 1
2032 1
1620 0
2020 1
2003 1
1980
1
2014 1
Time of
last use
R bit
(a)
(b)
(c)
(d)
New page
1213 0
2084 1
2032 1
1620 0
2020 1
2003 1
1980
1
2014 0
1213 0
2084 1
2032 1
1620 0
2020 1
2003 1
1980
1
2014 0
2204 1
2084 1
2032 1
1620 0
2020 1
2003 1
1980
1
2014 0
Figure 3-20.
Operation of the WSClock algorithm.
(a) and (b) give an example
of what happens when
R
= 1.
(c) and (d) give an example of
R
= 0.
In principle, all pages might be scheduled for disk I/O on one cycle around the
clock. To reduce disk traffic, a limit might be set, allowing a maximum of
n
pages
to be written back. Once this limit has been reached, no new writes would be
scheduled.
What happens if the hand comes all the way around and back to its starting
point? There are two cases we have to consider:
Page 252
SEC. 3.4
PA GE
REPLACEMENT ALGORITHMS
221
1.
At least one write has been scheduled.
2.
No writes have been scheduled.
In the first case, the hand just keeps moving, looking for a clean page. Since one or
more writes have been scheduled, eventually some write will complete and its page
will be marked as clean. The first clean page encountered is evicted. This page is
not necessarily the first write scheduled because the disk driver may reorder writes
in order to optimize disk performance.
In the second case, all pages are in the working set, otherwise at least one write
would have been scheduled. Lacking additional information, the simplest thing to
do is claim any clean page and use it. The location of a clean page could be kept
track of during the sweep.
If no clean pages exist, then the current page is chosen
as the victim and written back to disk.
3.4.10 Summary of Page Replacement Algorithms
We have now looked at a variety of page replacement algorithms.
Now we
will briefly summarize them.
The list of algorithms discussed is given in Fig. 3-21.
Algorithm
Comment
Optimal
Not implementable, but useful as a benchmark
NRU (Not Recently Used)
Very crude approximation of LRU
FIFO (First-In, First-Out)
Might throw out important pages
Second chance
Big improvement over FIFO
Clock
Realistic
LRU (Least Recently Used)
Excellent, but difficult to implement exactly
NFU (Not Frequently Used)
Fairly crude approximation to LRU
Aging
Efficient algorithm that approximates LRU well
Working set
Somewhat expensive to implement
WSClock
Good efficient algorithm
Figure 3-21.
Page replacement algorithms discussed in the text.
The optimal algorithm evicts the page that will be referenced furthest in the fu-
ture. Unfortunately, there is no way to determine which page this is, so in practice
this algorithm cannot be used.
It is useful as a benchmark against which other al-
gorithms can be measured, however.
The NRU algorithm divides pages into four classes depending on the state of
the
R
and
M
bits. A random page from the lowest-numbered class is chosen.
This
algorithm is easy to implement, but it is very crude. Better ones exist.
FIFO keeps track of the order in which pages were loaded into memory by
keeping them in a linked list. Removing the oldest page then becomes trivial, but
that page might still be in use, so FIFO is a bad choice.
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
