operating system

operating system

  • Submitted By: chi4all42
  • Date Submitted: 08/20/2014 7:50 AM
  • Category: Science
  • Words: 2112
  • Page: 9

Page replacement algorithms
1

OS 2009-10

When a page fault occurs
2

 OS has to choose a page to evict from memory
 If the page has been modified, the OS has to schedule

a disk write of the page
 Th page j t read overwrites a page i memory (
The
just
d
it
in
(e.g.
4Kbytes)
 Clearly it’s better not to pick a page at random
Clearly, it s
 Same problem applies to memory caches

OS 2009-10

Benchmarking
3

 Tests are done by generating p g references (
yg
g page
(either

from real code or random)
 Sequences of page numbers (no real address, no
offset)
 Example:

7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1
OS 2009-10

Optimal page replacement
4

 At the moment of page fault:
 Label each page in memory is labeled with the number of
instructions that will be executed before that page is first
referenced
 Replace the page with the highest number: i.e. postpone as
much as possible the next page fault
 Nice optimal, but unrealizable
Nice, optimal
 The OS can’t look into the future to know how long it’ll take to
reference every page again

OS 2009-10

Example: optimal
5

Sequence

PF

6 page faults

OS 2009-10

Belady’s anomaly
6

Try this sequence

With 3 page frames
With 4 page frames
With FIFO, with the optimal algorithm, (later) with the LRU

OS 2009-10

“Not recently used” algorithm
7

 Use Referenced and Modified bits
 R&M are in hardware, potentially changed at each

reference to memory



R&M are zero when process is started

 On clock interrupt the R bit is cleared
 On page fault, to decide which page to evict:
 Classify:
Class 0 – R=0,M=0
 Class 1 – R=0,M=1
 Class 2 – R=1,M=0
 Class 3 – R=1,M=1




Replace a page at random from the lowest class

OS 2009-10

FIFO replacement
8

 FIFO, first in first out for pages
,
p g
 Clearly not particularly optimal
 It might end up removing a p g that is still
g
p
g page...

Similar Essays