Transcript Chapter 8 Notes (More)

Virtual memory
What is program size>memory
available?
• Load only the parts of the memory that is
needed
• Do bookkeeping
• When accessing, make sure that that part of
the program is in memory; if not in
memory, replace some part by the needed
part
• This is called overlay
Demand paging
• Maintain two tables
– Page map table
• same as before (add a column: valid)
– File map table
• For each page i, this table tells where in disk the
page is available
Address translation
• When converting page number into frame
number, check if that valid bit is 1 (means
the page is in memory)
• If valid bit is 0, it means the page is not in
memory (page fault). Now, bring the page
from disk into main memory
Policies
• Allocation
• Fetch
• Replacement
Allocation policies
• Static allocation
– The number of frames allocated to a program
does not change when it executes
• Dynamic allocation
– The number frames allocated to the program
changes with time
Fetch policy
• Prefetch
– Fetch a page from disk before it is needed
• Demand fetch:
– Fetch a page from disk only when it is needed.
Replacement policy
• When no free frame is available and we
have a page fault, one of that process’s
pages will have to be replaced.
• Which page will be replaced?
Three replacement policies
• FIFO
• LRU
• Belady’s optimal
Basis for comparison
• Execution time page trace (ETPT) =
sequence of pages referenced when a
program executes
• Reference string w = replace consecutive
identical pages numbers by one occurrence
• ETPT = 1223343334456
• Corresponding reference string = 12343456
Belady’s optimal rule
• Replace the page that will not be needed for
the longest time in the future
1 2 3
1 1 2
2 2
3
x x x
4
1
2
4
x
1
1
2
4
25
11
22
45
x
1
1
2
5
2
1
2
5
3
1
3
5
x
4
4
3
5
x
5
4
3
5
FIFO
• Exhibits anomaly (when the number of
frames allocated increases, the page fault
rate increases)
• Replace the page in the First in First Out
manner. (use a queue data structure)
Least Recently Used (LRU)
• Replace the page that has not been
referenced for the longest time in the past
• LRU does not exhibit anomaly
• Variations of this are used in practice
Implementation of LRU
• Exact implementation is very expensive
• Use approximation algorithms
Approximation algorithms
• 1. Clock algorithm
–
–
–
–
–
–
Maintain two bits (r,w) per page in mamory
r bit is set to 1 every time is referenced
w bit is set to 1 every time the page is written
periodically, set all r bits to 0
Replace the page if the two bits are (0,0)
Else look for page with (0,1) or (1,0)
Approximation 2
• Maintain a long bit string (1 bit per page of
the program)
• Set bit i when page i is referenced
• Periodically, save the bit string in a circular
buffer and clear all the bits
• At time of page fault, choose the page to be
replaced based on its bit values in the
strings
Thrashing
• When we allocate too few frames to a
process, the page fault rate is very high (low
CPU utilization)
• When too many frames are allocated, fewer
programs will be accommodated
Demand paging in Unix
• Conditions
– Memory architecture allows paging
– Kernel implements a paging policy
– Restartable execution is possible
• execute part of an instruction, page fault and restar
Page [map] Table
• Contents:
– Physical address of page
– Protection bits (r/w/x)
– 5 bit fields to support demand paging
•
•
•
•
•
valid (1=contents valid)
reference (1= recently referenced)
modify (dirty bit)
copy on write
age
Free Frames
• The kernel maintains a supply of free
frames in two lists (to be allocated to
programs when there is a page fault)
– a free list (FIFO list)
– a hash list (for finding if a process’s page, after
page fault on that page, is in free list
• Allocate free frames from the free list
Page Stealer Process
• Swaps out pages (frames) that are no longer
part of the process’s working set
• Created during system initialization and
invoked whenever the number of free
frames is low
Stealer process
• Clear the reference bit of each page
• Remember how many passes were made
since the last time the page was accessed
• When a threshold value is reached, make
the page ``ready to swap out.’’ and add to
free list
Stealer Process
• Page stealer is waken up by the kernel when
available free frames is lower than a
threshold
• Page stealer swaps out pages until the
number of frames in the free list is larger
than a threshold
• The threshold is implementation dependent.