|
|
|
Modern Operating Systems by Herbert Bos and Andrew S. Tanenb...
Modern_Operating_Systems_by_Herbert_Bos_and_Andrew_S._Tanenbaum_4th_Ed.pdf
Showing 248-249 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 248
SEC. 3.4
PA GE
REPLACEMENT ALGORITHMS
217
w(k,t)
k
Figure 3-18.
The working set is the set of pages used by the
k
most recent mem-
ory references. The function
w
(
k
,
t
) is the size of the working set at time
t
.
put it differently, there exists a wide range of
k
values for which the working set is
unchanged. Because the working set varies slowly with time, it is possible to make
a reasonable guess as to which pages will be needed when the program is restarted
on the basis of its working set when it was last stopped. Prepaging consists of load-
ing these pages before resuming the process.
To implement the working set model, it is necessary for the operating system
to keep track of which pages are in the working set. Having this information also
immediately leads to a possible page replacement algorithm: when a page fault oc-
curs, find a page not in the working set and evict it.
To implement such an algo-
rithm, we need a precise way of determining which pages are in the working set.
By definition, the working set is the set of pages used in the
k
most recent memory
references (some authors use the
k
most recent page references, but the choice is
arbitrary). To implement any working set algorithm, some value of
k
must be cho-
sen in advance. Then, after every memory reference, the set of pages used by the
most recent
k
memory references is uniquely determined.
Of course, having an operational definition of the working set does not mean
that there is an efficient way to compute it during program execution. One could
imagine a shift register of length
k
, with every memory reference shifting the regis-
ter left one position and inserting the most recently referenced page number on the
right. The set of all
k
page numbers in the shift register would be the working set.
In theory, at a page fault, the contents of the shift register could be read out and
sorted. Duplicate pages could then be removed. The result would be the working
set. However, maintaining the shift register and processing it at a page fault would
both be prohibitively expensive, so this technique is never used.
Instead, various approximations are used. One commonly used approximation
is to drop the idea of counting back
k
memory references and use execution time
instead. For example, instead of defining the working set as those pages used dur-
ing the previous 10 million memory references, we can define it as the set of pages
Page 249
218
MEMORY MANAGEMENT
CHAP. 3
used during the past 100 msec of execution time.
In practice, such a definition is
just as good and much easier to work with.
Note that for each process, only its
own execution time counts. Thus if a process starts running at time
T
and has had
40 msec of CPU time at real time
T
+ 100 msec, for working set purposes its time
is 40 msec. The amount of CPU time a process has actually used since it started is
often called its
current virtual time
.
With this approximation, the working set of
a process is the set of pages it has referenced during the past
τ
seconds of virtual
time.
Now let us look at a page replacement algorithm based on the working set. The
basic idea is to find a page that is not in the working set and evict it.
In Fig. 3-19
we see a portion of a page table for some machine. Because only pages located in
memory are considered as candidates for eviction, pages that are absent from
memory are ignored by this algorithm. Each entry contains (at least) two key items
of information: the (approximate) time the page was last used and the
R
(Refer-
enced) bit. An empty white rectangle symbolizes the other fields not needed for
this algorithm, such as the page frame number, the protection bits, and the
M
(Modified) bit.
Information about
one page
2084
2204
Current virtual time
2003
1980
1213
2014
2020
2032
1620
Page table
1
1
1
0
1
1
1
0
Time of last use
Page referenced
during this tick
Page not referenced
during this tick
R (Referenced) bit
Scan all pages examining R bit:
if (R == 1)
set time of last use to current virtual time
if (R == 0 and age >
τ
)
remove this page
if (R == 0 and age
≤
τ
)
remember the smallest time
Figure 3-19.
The working set algorithm.
The algorithm works as follows. The hardware is assumed to set the
R
and
M
bits, as discussed earlier. Similarly, a periodic clock interrupt is assumed to cause
software to run that clears the
Referenced
bit on every clock tick.
On every page
fault, the page table is scanned to look for a suitable page to evict.
As each entry is processed, the
R
bit is examined. If it is 1, the current virtual
time is written into the
Time of last use
field in the page table, indicating that 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
