Virtual memory can be implemented via:
Demand paging
Demand segmentation
Demand Paging
Basic concept
Access to a page that is not in the memory causes Page Fault
Trap: reference to that page will trap to operating system if page
does not exist:
Page fault
1. Operating system looks at page table to decide:
Invalid reference abort
Just not in memory
2. Find free frame
3. Swap page into frame via scheduled disk operation
4. Reset tables to indicate page now in memory
Set validation bit = v
5. Restart the instruction that caused the page fault
Steps in handling a page fault
Aspects of demand paging
Consider Extreme case – start process with no pages in memory
OS sets instruction pointer to first instruction of process, non-memory-
resident -> page fault
And for every other process pages on first access
Pure demand paging: never bring the page into MM until it is
required
Actually, a given instruction could access multiple pages -> multiple page
faults
Hardware support needed for demand paging
Page table with valid / invalid bit
Secondary memory (swap device with swap space)
Performance of demand paging
Stages in Demand Paging (worse case):
A page fault causes the following sequence to occur:
1. Trap to the operating system
2. Save the user registers and process state
3. Determine that the interrupt was a page fault
4. Check that the page reference was legal and determine the location of
the page on the disk
5. Issue a read from the disk to a free frame:
1. Wait in a queue for this device until the read request is serviced
2. Wait for the device seek and/or latency time
3. Begin the transfer of the page to a free frame
6. While waiting, allocate the CPU to some other user
7. Receive an interrupt from the disk I/O subsystem (I/O completed)
8. Save the registers and process state for the other user
9. Determine that the interrupt was from the disk
10. Correct the page table and other tables to show page is now in memory
11. Wait for the CPU to be allocated to this process again
12. Restore the user registers, process state, and new page table, and then
resume the interrupted instruction
Demand paging can significantly affect the performance of a computer system.
In most computer systems, the memory-access time, denoted by ma, ranges from 10 to 200
nanoseconds.
Page Fault Rate 0 p 1
if p = 0 no page faults
if p = 1, every reference is a fault
Effective Access Time (EAT):
EAT = (1 – p) x memory access+ p X page fault
Effective Access Time (EAT):
EAT =
(1 – p) x memory access+ p (page fault overhead + swap page out + swap page in )
Demand paging example
Memory access time = 200 nanoseconds
Average page-fault service time = 8 milliseconds
milli sec = 1/1,000 sec
EAT = (1 – p) x 200 + p (8 milliseconds)
= (1 – p) x 200 + p x 8,000,000
= 200 + p x 7,999,800 Nano sec =
If one access out of 1,000 causes a page fault, then 1/1,000,000,000 sec
EAT = 8.2 microseconds. Micro sec = 1/1,000,000
This is a slowdown by a factor of 40!! sec
If want performance degradation < 10 percent
220 > 200 + 7,999,800 x p
20 > 7,999,800 x p
p < .0000025
< one page fault in every 400,000 memory accesses
Copy-on-Write
Copy-on-Write (COW) allows both parent and child processes to initially
share the same pages in memory
fork() system call creates child process that is duplicate of its parent
Copy of parent’s address space is created for child
Duplicating pages belonging to parent
Many child processes invoke exec() immediately after creation
Copying of parent’s space maybe unnecessary
COW allows parent and child processes initially to share same pages
Shared pages marked as copy-on-write pages
Only pages that can be modified marked as copy on write
Pages that cannot be modified- pages containing executable code- be
shared by parent and child
If either process writes to a shared page:
A copy of shared pages is created
Unmodified pages shared by parent and child processes
Allows more efficient process creation as only modified pages are copied
In general, free pages are allocated from a pool of zero-fill-on-demand
pages
Zero-fill-on-demand pages have been zeroed-out before being allocated by
erasing the previous contents
Pool should always have free frames for fast demand page execution
Don’t want to have to free a frame as well as other processing on
page fault
vfork() is a variation on fork() system call
With vfork(), the parent process is suspended, and the child process uses
the address space of the parent.
vfork() does not use copy-on-write, if the child process changes any
pages of the parent's address space, the altered pages will be visible to
the parent once it resumes.
Therefore, vfork() must be used with caution to ensure that the child
process does not modify the address space of the parent. Vfork() is
intended to be used when the child process calls exec() immediately
after creation.
Because no copying of pages takes place, vfork() is an extremely efficient
method of process creation and is sometimes used to implement UNIX
command-line shell interfaces.
Before Process 1 Modifies Page C
After Process 1 Modifies Page C
Page Replacement Algorithms
Need For Page Replacement
Basic Page Replacement
1. Find the location of the desired page on disk
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
- Write the victim frame to the disk; change the page and frame
tables accordingly
2. Bring the desired page into the free frame; update the page and frame
tables
3. Restart the user process.
Continue the process by restarting the instruction that caused the trap
Note: Potentially 2 page transfers for page fault – increasing EAT
Page Replacement
Page and Frame Replacement Algorithms
Frame-allocation algorithm determines
How many frames to give each process
Which frames to replace
Page-replacement algorithm
Want lowest page-fault rate on both first access and re-access
Evaluate algorithm by running it on a particular string of memory
references (reference string) and computing the number of page
faults on that string
String is just page numbers, not full addresses
Repeated access to the same page does not cause a page fault
Results depend on number of frames available
In all the examples, the reference string of referenced page
numbers is
7,0,1,2,0,3,0,4,2,3,0,3,0,3,2,1,2,0,1,7,0,1
Graph of Page Faults Versus The Number of Frames
FIFO page replacement Algorithm
• It is the simplest PRA
• OS keeps track of all pages in the memory in a queue, oldest
page is in the front of the queue.
• When the page needs to be replaced, page in the front of the
queue is selected for removal
Reference string : set of pages
Page slots: the number of pages MM can accommodate(no. of
frames).
First-In-First-Out (FIFO) Algorithm
Reference string: 7,0,1,2,0,3,0,4,2,3,0,3,0,3,2,1,2,0,1,7,0,1
3 frames (3 pages can be in memory at a time per process)
15 page faults
Can vary by reference string: consider 1,2,3,4,1,2,5,1,2,3,4,5
Consider frame size i)2 ii)3 iii)4 iv)5
For some page-replacement algorithms, the page-fault rate
may increase as the number of allocated frames increases.
Adding more frames can cause more page faults, Called as
Belady’s Anomaly
How to track ages of pages?
Just use a FIFO queue
FIFO Illustrating Belady’s Anomaly
Optimal Algorithm
One result of the discovery of Belady's anomaly was the search for
an optimal page-replacement algorithm.
An optimal page-replacement algorithm has the lowest page-fault
rate of all algorithms and will never suffer from Belady’s anomaly.
Replace page that will not be used for longest period of time
Reference string:
7,0,1,2,0,3,0,4,2,3,0,3,0,3,2,1,2,0,1,7,0,1
Least Recently Used (LRU) Algorithm
Use past knowledge rather than future
Replace page that has not been used in the most amount of time
Associate time of last use with each page
Reference string:
7,0,1,2,0,3,0,4,2,3,0,3,0,3,2,1,2,0,1,7,0,1
12 faults – better than FIFO but worse than OPT
Generally good algorithm and frequently used and also does not suffer from
Belady’s Anomaly
LRU Algorithm (Cont.)
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 find
smallest value
Search through table needed
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
But each update more expensive
No search for replacement
LRU and OPT are cases of stack algorithms that don’t have
Belady’s Anomaly
Use Of A Stack to Record Most Recent Page References
LRU Approximation Algorithms
LRU needs special hardware
Reference bit
With each page associate a bit, initially = 0
When page is referenced, bit set to 1
Replace any with reference bit = 0 (if one exists)
Doesn’t have any order
Additional Reference bit algorithm: Uses 8 bit reference for each page
The operating system shifts the reference bit for each page into the high-order bit
of its 8-bit byte, shifting the other bits right by 1 bit and discarding the low-order
bit. These 8-bit shift registers contain the history of page use for the last eight time
periods. If the shift register contains 00000000, for example, then the page has not
been used for eight time periods; a page that is used at least once in each period
has a shift register value of 11111111. A page with a history register value of
11000100 has been used more recently than one with a value of 01110111
Second-chance algorithm
Generally, FIFO, plus hardware-provides reference bit
Clock replacement
If page to be replaced has
Reference bit = 0 -> replace it
reference bit = 1 then:
set reference bit 0, leave page in memory
replace next page, subject to same rules
Second-Chance (clock) Page-Replacement Algorithm
Enhanced Second-Chance Algorithm
Improve algorithm by using reference bit and modify bit
Take ordered pair (reference, modify)
1. (0, 0) neither recently used not modified – if found
replace. Best page to replace
2. (0, 1) not recently used but modified –
Not quite as good, must write out before
replacement
3. (1, 0) recently used but clean – probably will be used
again soon
4. (1, 1) recently used and modified – probably will be used
again soon and need to write out before replacement
When page replacement called for, use the clock scheme
but use the four classes to replace page in lowest non-
empty class
Might need to search circular queue several times
1. (0, 0) - if found replace.
2. (0, 1) - if found replace else set reference bit to 0 for all the
frames
3. If step 2 failed make use bit=0 and repeat step 1 and 2
Thrashing
If a process does not have “enough” pages, the page-fault rate is very
high
Page fault to get page
Replace existing frame
But quickly need replaced frame back
This leads to:
Low CPU utilization
Operating system thinking that it needs to increase the degree of
multiprogramming
a process is busy swapping pages in and out
High paging activity is called Thrashing. A process is thrashing if it is
spending more time paging than executing.
Thrashing (Cont.)
Working-Set Model
working-set window a fixed number of page references
Example: 10,000 instructions
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
Approximation of locality
if D > m Thrashing
Policy if D > m, then suspend or swap out one of the processes
Page-Fault Frequency
More direct approach than WSS
Establish “acceptable” page-fault frequency (PFF)
rate and use local replacement policy
If actual rate too low, process loses frame
If actual rate too high, process gains frame
Working Sets and Page Fault Rates
Direct relationship between working set of a process
and its page-fault rate
Working set changes over time
Peaks and valleys over time
Page-Buffering Algorithms
Always Keep a pool of free frames,
Then frame available when needed, not found at fault time
Read page into free frame and select victim to evict and add
to free pool
When convenient, evict victim
Possibly, keep list of modified pages
When backing store otherwise idle, write pages there and set
to non-dirty
Possibly, keep free frame contents intact and note what is
in them
If referenced again before reused, no need to load contents
again from disk
Generally useful to reduce penalty if wrong victim frame
selected
Applications and Page Replacement
All of these algorithms have OS guessing about future
page access
Some applications have better knowledge – i.e.
databases
Memory intensive applications can cause double
buffering
OS keeps copy of page in memory as I/O buffer
Application keeps page in memory for its own work
Operating system can given direct access to the disk,
getting out of the way of the applications
Raw disk mode
Bypasses buffering, locking, etc
Allocation of Frames
Each process needs minimum number of frames
Example: IBM 370 – 6 pages to handle SS MOVE
instruction:
instruction is 6 bytes, might span 2 pages
2 pages to handle from
2 pages to handle to
Maximum of course is total frames in the system
Two major allocation schemes
fixed allocation
priority allocation
Many variations
Counting Algorithms
Keep a counter of the number of references that have been
made to each page
Lease Frequently Used (LFU) Algorithm: replaces page with
smallest count
Most Frequently Used (MFU) Algorithm:
The Least Frequently Used (LFU) Algorithm page-replacement
algorithm
Requires that the page with the smallest count be replaced.
The reason for this selection is that an actively used page should
have a large reference count.
A problem arises, when a page is used heavily during the initial
phase of a process but then is never used again.
Since it was used heavily, it has a large count and remains in
memory even though it is no longer needed.
One solution is to shift the counts right by 1 bit at regular
intervals, forming an exponentially decaying average usage
count.
Most Frequently Used (MFU) Algorithm
MFU is based on the argument that the page with the smallest
count was probably just brought in and has yet to be used.
Neither MFU nor LFU replacement is common.
The implementation of these algorithms is expensive, and they
do not approximate OPT replacement well.
Allocation of Frames
Consider a single-user system, with 128 K8 of memory composed of
pages 1K B in size. This system has 128 frames.
The operating system may take 35 KB, leaving 93 frames for the user
process.
Under pure demand paging, all 93 frames would initially be put on
the free-frame list. When a user process started execution, it would
generate a sequence of page faults.
The first 93 page faults would all get free frames from the free-frame
list. When the free-frame list was exhausted, a page-replacement
algorithm would be used to select one of the 93 in-memory pages to
be replaced with the 94th, and so on.
When the process terminated, the 93 frames would once again be
placed on the free-frame list.
There are many variations on this simple strategy. It requires that the
operating system allocate all its buffer and table space from the free-
frame list.
When this space is not in use by the operating system, it can be used to
support user paging.
Then these three free frames reserved on the free-frame list at all times.
Thus, when a page fault occurs, there is a free frame available to page
into.
While the page swap is taking place, a replacement can be selected,
which is then written to the disk as the user process continues to
execute.
Other variants are also possible, but the basic strategy is clear: The user
process is allocated any free frame.
Minimum Number of Frames
Cannot allocate more than the total number of available frames
Must also allocate at least a minimum number of frames.
One reason for allocating at least a minimum number of frames
involves performance. Obviously, as the number of frames
allocated to each process decreases, the page-fault rate increases,
slowing process execution.
In addition, when a page fault occurs before an executing
instruction is complete, the instruction must be restarted.
Consequently, enough frames must exist to hold all the different
pages that any single instruction can reference
Frame Allocation algorithms
Fixed Allocation:
Equal allocation – For example, if there are 100 frames (after
allocating frames for the OS) and 5 processes, give each process 20
frames
Keep some as free frame buffer pool
Proportional allocation – Allocate according to the size of process
Dynamic as degree of multiprogramming, process sizes change
si size of process pi
S si
m total number of frames
si
ai allocation for pi m
S
Priority Allocation
With either equal or proportional allocation, a high-
priority process is treated the same as a low-priority
process
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
Global vs. Local Allocation
With multiple processes competing for frames, the page-replacement
algorithms can be classified into two broad categories: global
replacement and local replacement.
Global replacement – process selects a replacement frame from the set
of all frames; one process can take a frame from another
The process execution time can vary.
But greater throughput.
Local replacement – each process selects from only its own set of
allocated frames
More consistent per-process performance
But possibly underutilized memory
