Transcript class slides

Virtual Memory: Page
Replacement
Operating Systems
Fall 2002
OS Fall’02
Realizing Virtual Memory
 Hardware support
Memory Management Unit (MMU): address
translation, bits, interrupts
 Operating system support
Page replacement policy
Resident set management
Load control
 degree of multiprogramming
OS Fall’02
Page Replacement Policy
 Resident set maintenance
Fixed or variable allocation
Per-process or global replacement
 Page replacement problem
A fixed number of frames, M, is used to map
the process virtual memory pages
Which page should be replaced when a page
fault occurs and all M frames are occupied?
OS Fall’02
Requirements and Metrics
 Workload: a sequence of virtual memory
references (page numbers)
 Page fault rate =
#page faults/#memory references
 Minimize the page fault rate for
workloads obeying the principle of locality
Keep hardware/software overhead as small
as possible
OS Fall’02
Algorithms




Optimal (OPT)
Least Recently Used (LRU)
First-In-First-Out (FIFO)
Clock
OS Fall’02
Optimal Policy (OPT)
 Replace the page which will be
referenced again in the most remote
future
 Impossible to implement
Why?
 Serves as a baseline for other algorithms
OS Fall’02
Least Recently Used (LRU)
 Replace the page that has not been
referenced for the longest time
 The best approximation of OPT for the
locality constrained workloads
 Possible to implement
 Infeasible as the overhead is high
Why?
OS Fall’02
First-In-First-Out (FIFO)
 Page frames are organized in a circular
buffer with a roving pointer
 Pages are replaced in round-robin style
When page fault occur, replace the page to
which the pointer points to
 Simple to implement, low overhead
 High page fault rate, prone to anomalous
behavior
OS Fall’02
Clock (second chance)
 Similar to FIFO but takes page usage into
account
Circular buffer + page use bit
When a page is referenced: set use_bit=1
When a page fault occur: For each page:
if use_bit==1: give page a second chance:
use_bit=0; continue scan;
if use_bit==0: replace the page
OS Fall’02
Example: Page 727 is needed
0
n
Page 19
use = 1
Page 9
use = 1
1
Page 1
use = 0
.
.
next frame
pointer
.
8
Page 45
use = 1
Page 191
use = 1
Page 222
use = 0
Page 556
use = 0
Page 33
use = 1
Page 67
use = 1
7
Page 13
use = 0
6
5
OS Fall’02
4
2
3
After replacement
0
n
Page 19
use = 1
Page 9
use = 1
1
Page 1
use = 0
.
.
Page 45
use = 0
.
2
next frame
pointer
8
Page 191
use = 0
Page 222
use = 0
Page 727
use = 0
Page 33
use = 1
Page 67
use = 1
7
Page 13
use = 0
6
5
OS Fall’02
4
3
Example of all algorithms
OS Fall’02
LRU and non-local workloads
 Workload: 1 2 3 4 5 1 2 3 4 5…
Typical for array based applications
 What is the page fault rate for M=1,…,5?
 A possible alternative is to use a Most
Recently Use (MRU) replacement policy
OS Fall’02
Belady’s Anomaly
 It is reasonable to expect that regardless
of a workload, the number of page faults
should not increase if we add more
frames: not true for the FIFO policy:
1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5
1 1
4
5
2 2
1
3
3 3
2
4
OS Fall’02
1 1
5
4
2 2
1
5
3 3
2
4 4
3
Algorithm comparison
OS Fall’02
Clock algorithm with 2 bits
 Use “modified” bit to evict unmodified
(clean) pages in preference over modified
(dirty) pages
 Four classes:
u=0;
u=0;
u=1;
u=1;
m=0:
m=1:
m=0:
m=1:
not recently used, clean
not recently used, dirty
recently used, clean
recently used, dirty
OS Fall’02
Clock algorithm with 2 bits
 First scan: look for (0,0) frame, do not
change the use bit
If (0,0) frame is found, replace it
 Second scan: look for (0,1) frame, set
use bit to 0 in each frame bypassed
If (0,1) frame is found, replace it
 If all failed, repeat the above procedure
this time we will certainly find something
OS Fall’02
Page buffering
 Evicted pages are kept on two lists:
free and modified page lists
 Pages are read into the frames on the
free page list
 Pages are written to disk in large chunks
from the modified page list
 If an evicted page is referenced, and it is
still on one of the lists, it is made valid at
a very low cost
OS Fall’02
Resident set management
 With multiprogramming, a fixed number
of memory frames are shared among
multiple processes
 How should the frames be partitioned
among the active processes?
 Resident set is the set of process pages
currently allocated to the memory frames
OS Fall’02
The working set model [Denning’68]
 Working set is the set of pages in the
most recent  page references
 Working set is an approximation of the
program locality
OS Fall’02
The working set strategy
 Monitor the working set for each
currently active process
 Adjust the number of pages assigned to
each process according to its working set
size
 Monitoring working set is impractical
 The optimal value of  is unknown and
would vary
OS Fall’02
Approximating the WS
 Global page replacement
All memory frames are candidates for page
eviction
 a faulting process may evict a page of other
process
Processes with larger WS are expanding
whereas those with smaller WS are shrinking
 Problem: may unjustly reduce the WS of
some processes
Combine with page buffering
OS Fall’02
Approximating the WS
 Local page replacement
Only the memory frames of a faulting
process are candidates for replacement
 Dynamically adjust the process allocation
Page-Fault Frequency (PFF) algorithm
OS Fall’02
Page-Fault Frequency (PFF)
 Approximate the page-fault frequency:
Count all memory references for each active
process
When a page fault occurs, compare the
current counter value with the previous page
fault counter value for the faulting process
If < F, expand the WS; Otherwise, shrink the
WS by discarding pages with use_bit==0
OS Fall’02
Multiprogramming level
 Too many processes in memory
Thrashing, inability to run new processes
 The solution is swapping:
save all the resident set of a process to the
disk (swapping out)
load the pages of another process instead
(swapping in)
 Long-term and medium term scheduling
decides which processes to swap in/out
OS Fall’02
Long (medium) term scheduling
 Decision of which processes to swap
out/in is based on
The CPU usage
Creating a balanced job mix with respect to
I/O vs. CPU bound processes
 Two new process states:
Ready swapped
Blocked swapped
OS Fall’02
UNIX process states
running
user
schedule
sys. call
interrupt
ready
user
return
zombie
interrupt
running
kernel
preempt
wait for event
schedule
ready
kernel
created
Swap in
terminated
event done
Swap out
ready
swapped
event done
OS Fall’02
blocked
Swap out
blocked
swapped
Segmentation with paging
 Segmentation
simplifies protection and sharing, enforce
modularity, but prone to external
fragmentation
 Paging
transparent, eliminates ext. fragmentation,
allows for sophisticated memory management
 Segmentation and paging can be
combined
OS Fall’02
Address translation
Seg #
Page #
Frame #
Offset
Offset
Seg Table Ptr
Segment
Table
Page Table
Offset
P#
S#
+
Program
+
Segmentation
Paging
OS Fall’02
Main Memory
Page
Frame
Page size considerations
 Small page size
better approximates locality
large page tables
inefficient disk transfer
 Large page size
internal fragmentation
 Most modern architectures support a
number of different page sizes
 a configurable system parameter
OS Fall’02
Next: File system, disks, etc
OS Fall’02