Virtual Memory
Topics to be covered
• Background
• Demand Paging
• Process Creation
• Page Replacement
• Allocation of Frames
• Thrashing
• Demand Segmentation
• Operating System Examples
Background
• Virtual memory
– Only part of the program needs to be
in memory for execution.
– Logical address space can therefore
be much larger than physical address
space.
Virtual Memory That is Larger Than
Physical Memory
Demand Paging
• Bring a page into memory only when
it is needed
• Page is needed reference to it
– invalid reference abort
– not-in-memory bring to memory
Valid-Invalid Bit
• With each page table entry a valid–invalid bit is
associated
(1 in-memory, 0 not-in-memory)
• Initially valid–invalid but is set to 0 on all entries
• Example of a page table snapshot:
Frame # valid-invalid bit
1
0
0
0
1
1
Page table
Page Fault
Steps in Handling a Page Fault
Pure demand paging
• Start execution of a process with
zero pages in main memory
What happens if there is no free
frame?
• Page replacement –
– algorithm
– performance – want an algorithm
which will result in min. no. of
page faults
Page Replacement
Graph of Page Faults Versus The
Number of Frames
Modify bit
• Page replacement requires
significant I/O transfer.
• Write the page to disk ( or
swap out a page) only when
modify bit is 1
Global vs. Local Allocation
Global replacement Local replacement
A page of any process can be Page of only that process is
replaced replaced
The no. of frames allocated to a The no. of frames allocated to a
process change over time process are fixed
Page replacement algorithms
• FIFO
• Optimal
• LRU
• LRU approximation
• Additional reference bits
• Second chance
• Enhanced second chance
• Counting algorithms
• LFU
• MFU
First-In-First-Out (FIFO)
Algorithm
Reference string:
1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5
First-In-First-Out (FIFO) Algorithm
1 1 4 5
2 2 1 3 9 page faults
3 3 2 4
First-In-First-Out (FIFO) Algorithm
1 1 4 5
2 2 1 3 9 page faults
3 3 2 4
1 1 5 4
2 2 1 5 10 page faults
3 3 2
4 4 3
• FIFO Replacement – Belady’s Anomaly
– more frames more page faults
FIFO Page Replacement
FIFO Page Replacement
15 page faults
FIFO Illustrating Belady’s
Anomaly
Optimal Algorithm
• Replace page that will not be used for longest period of
time.
1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5
Difficult to implement as we do not know future references.
• Hence, it is used for comparative study.
1 4
2 6 page faults
3
4 5
Optimal Page Replacement
Optimal Page Replacement
LRU Algorithm
• Reference string:
1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5
Least Recently Used (LRU)
1 5
2
3 5 4
4 3
LRU Page Replacement
LRU Page Replacement
LRU Algorithm implementation
• Time stamp
• Stack implementation – keep a stack
of page numbers in a double link
form
Use Of A Stack to Record The Most Recent
Page References
LRU Approximation Algorithms
• It uses reference bit.
• Whenever a page is referenced, the
reference bit is set to 1
• Reference bits are associated with each
entry in page table.
• Initially all bits are set to 0 by OS.
LRU Approximation Algorithms
• Additional reference bits algorithm
• Second-chance algorithm
• Enhanced second-chance algorithm
Additional reference bits algorithm
• A table of 8 bit byte is maintained for each
page.
• At regular intervals, the OS shifts the
reference bit for each page into high order
bit of its 8-bit byte, shifting other bits right
by 1 bit, discarding low order bit.
• The page with lowest no. is LRU page & is
selected for replacement
Second-Chance Algorithm
• It uses FIFO algorithm.
• When a page is selected its reference bit is
checked. If it is 1, it is set to 0 and moves to
next page.
• If it is 0, it is replaced.
• It is implemented using circular queue.
Second-Chance Algorithm(cont.)
Enhanced second chance algorithm
• It considers reference bit as well as modify
bit.
• With these two bits we have following four
classes.
rb mb
0 0 Best page to replace
0 1 Not good; page has to be written
out before replacement
1 0 Probably will be used again
1 1 Recently used & modified
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
Allocation of Frames
• Each process needs minimum
number of pages
• Equal allocation
• Proportional allocation
• Equal allocation –
• For example, if there are 100 frames and 5
processes, give each process 20 frames.
• Proportional allocation – Allocate according to
the size of process
si size of process pi
S si
m total number of frames
si
ai allocation for pi m
S
m 64
s1 10
s2 127
10
a1 64 5
137
127
a2 64 59
137
Thrashing
• A high paging activity is caIled
thrashing.
• A process is said to be
thrashing if it is spending more
time in paging than executing.
Thrashing (Cont.)
Solution
• To avoid thrashing, we should assign a
process as many frames as it needs.
• But, how to know the no. of frames a
process needs.
• For this we have two methods
– Working set model
– Page fault frequency
Working-Set Model
• It depends on locality model.
• Locality is set of pages that are in active use.
• During execution, a process moves from one
locality to another.
• It sees how many frames a process is actually
using.
working-set window a fixed number of
page references
Working-set model(contd..)
Working-Set Model(contd..)
• if too small, it will not encompass entire locality
• if too large, it will encompass several localities
• Let WSSi be no. of frames a process needs
D = WSSi total demand frames
• if D > m Thrashing
• Policy if D > m, then suspend one of the
processes
Page-Fault Frequency
– If rate too low, process have too many
frames
– If rate too high, process needs more frames