Transcript CSCI 315 Lecture 3

Page Replacement Algorithms
(Virtual Memory)
03/26/2008
CSCI 315 Operating Systems Design
1
Servicing a Page Fault
operating
system
running
process
3
2
page table
1
i
6
physical
memory
free frame
5
4
disk
03/26/2008
CSCI 315 Operating Systems Design
2
No free frame: now what?
• Page replacement: Are all those pages in
memory being referenced? Choose one to swap
back out to disk and make room to load a new
page.
– Algorithm: How you choose a victim.
– Performance: Want an algorithm which will result in
minimum number of page faults.
• Side effect: The same page may be brought in
and out of memory several times.
03/26/2008
CSCI 315 Operating Systems Design
3
Page Replacement
• Prevent over-allocation of memory by modifying pagefault service routine to include page replacement.
• Use modify (dirty) bit to reduce overhead of page
transfers – only modified pages are written to disk.
• Page replacement completes separation between logical
memory and physical memory – large virtual memory
can be provided on a smaller physical memory.
03/26/2008
CSCI 315 Operating Systems Design
4
Basic Page Replacement
1. Find the location of the desired page on disk.
2. Find a free frame:
- If there is a free frame, use it.
- If there is no free frame, use a page replacement
algorithm to select a victim frame.
3. Read the desired page into the (newly) free frame.
Update the page and frame tables.
4. Restart the process.
03/26/2008
CSCI 315 Operating Systems Design
5
Page Replacement Algorithms
• Goal: Produce a low page-fault rate.
• Evaluate algorithm by running it on a particular
string of memory references (reference string)
and computing the number of page faults on that
string.
• The reference string is produced by tracing a
real program or by some stochastic model. We
look at every address produced and strip off the
page offset, leaving only the page number. For
instance:
1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5
03/26/2008
CSCI 315 Operating Systems Design
6
Graph of Page Faults Versus The
Number of Frames
03/26/2008
CSCI 315 Operating Systems Design
7
FIFO Page Replacement
•
•
•
•
03/26/2008
Reference string: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5.
3 frames (3 pages can be in memory at a time per process)
1
1
4
5
2
2
1
3
3
3
2
4
1
1
5
4
2
2
1
5
3
3
2
4
4
3
4 frames
9 page faults
10 page faults
FIFO Replacement  Belady’s Anomaly: more frames less
page faults.
CSCI 315 Operating Systems Design
8
FIFO Page Replacement
03/26/2008
CSCI 315 Operating Systems Design
9
FIFO (Belady’s Anomaly)
03/26/2008
CSCI 315 Operating Systems Design
10
Optimal Algorithm
• Replace the page that will not be used for longest period
of time. (How can you know what the future references
will be?)
• 4 frames example: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5
1
4
2
6 page faults
3
4
5
• Used for measuring how well your algorithm performs.
03/26/2008
CSCI 315 Operating Systems Design
11
Optimal Page Replacement
03/26/2008
CSCI 315 Operating Systems Design
12
LRU Algorithm
• Reference string: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5
1
5
2
3
5
4
3
4
• Counter implementation:
– Every page entry has a counter; every time page is referenced through
this entry, copy the clock into the counter.
– When a page needs to be changed, look at the counters to determine
which are to change.
03/26/2008
CSCI 315 Operating Systems Design
13
LRU Page Replacement
03/26/2008
CSCI 315 Operating Systems Design
14
LRU Algorithm (Cont.)
• Stack implementation – keep a stack of
page numbers in a double link form:
– Page referenced:
• move it to the top
• requires 6 pointers to be changed
– No search for replacement.
03/26/2008
CSCI 315 Operating Systems Design
15
Use Of A Stack to Record The Most Recent
Page References
03/26/2008
CSCI 315 Operating Systems Design
16
LRU Approximation Algorithms
• Reference bit
– With each page associate a bit, initially = 0
– When page is referenced bit set to 1.
– Replace the one which is 0 (if one exists). We do not know the
order, however.
• Second chance
– Need reference bit.
– Clock replacement.
– If page to be replaced (in clock order) has reference bit = 1.
then:
• set reference bit 0.
• leave page in memory.
• replace next page (in clock order), subject to same rules.
03/26/2008
CSCI 315 Operating Systems Design
17
Second-Chance (clock)
Page-Replacement Algorithm
03/26/2008
CSCI 315 Operating Systems Design
18
Counting Algorithms
• Keep a counter of the number of references that
have been made to each page.
• LFU Algorithm: replaces page with smallest
count.
• MFU Algorithm: based on the argument that
the page with the smallest count was probably
just brought in and has yet to be used.
03/26/2008
CSCI 315 Operating Systems Design
19
Allocation of Frames
• Each process needs a minimum number of
pages.
• There are two major allocation schemes:
– fixed allocation
– priority allocation
03/26/2008
CSCI 315 Operating Systems Design
20
Fixed Allocation
• Equal allocation – e.g., if 100 frames and 5 processes, give
each 20 pages.
• Proportional allocation – Allocate according to the size of
process.
si  size of process pi
S   si
m  total number of frames
s
ai  allocation for pi  i  m
S
03/26/2008
m  64
si  10
s2  127
10
 64  5
137
127
a2 
 64  59
137
a1 
CSCI 315 Operating Systems Design
21
Priority Allocation
• Use a proportional allocation scheme
using priorities rather than size.
• If process Pi generates a page fault,
– select for replacement one of its frames.
– select for replacement a frame from a process
with lower priority number.
03/26/2008
CSCI 315 Operating Systems Design
22
Global vs. Local Allocation
• Global replacement – process selects a
replacement frame from the set of all
frames; one process can take a frame from
another.
• Local replacement – each process selects
from only its own set of allocated frames.
03/26/2008
CSCI 315 Operating Systems Design
23
Thrashing
• If a process does not have “enough” pages, the
page-fault rate is very high. This leads to:
– Low CPU utilization.
– Operating system thinks that it needs to increase the
degree of multiprogramming.
– Another process added to the system.
• Thrashing  a process is busy swapping pages
in and out.
03/26/2008
CSCI 315 Operating Systems Design
24
Thrashing
• Why does paging work?
Locality model
– Process migrates from one locality to another.
– Localities may overlap.
• Why does thrashing occur?
 size of locality > total memory size
03/26/2008
CSCI 315 Operating Systems Design
25
Locality in Memory-Reference Pattern
03/26/2008
CSCI 315 Operating Systems Design
26
Working-Set Model
•   working-set window  a fixed number of page
references.
• WSSi (working set of Process Pi) =
total number of pages referenced in the most recent 
(varies in time)
– if  too small will not encompass entire locality.
– if  too large will encompass several localities.
– if  =   will encompass entire program.
• D =  WSSi  total demand frames
• if D > m  Thrashing
• Policy if D > m, then suspend one of the processes.
03/26/2008
CSCI 315 Operating Systems Design
27
Working-set model
03/26/2008
CSCI 315 Operating Systems Design
28
Keeping Track of the Working Set
• Approximate with interval timer + a reference bit
• Example:  = 10,000
– Timer interrupts after every 5000 time units.
– Keep in memory 2 bits for each page.
– Whenever a timer interrupts copy and sets the values of all
reference bits to 0.
– If one of the bits in memory = 1  page in working set.
• Why is this not completely accurate?
• Improvement = 10 bits and interrupt every 1000 time
units.
03/26/2008
CSCI 315 Operating Systems Design
29
Page-Fault Frequency Scheme
Establish “acceptable” page-fault rate.
– If actual rate too low, process loses frame.
– If actual rate too high, process gains frame.
03/26/2008
CSCI 315 Operating Systems Design
30