Virtual memory and page replacement algorithm

Presented to
Sir Tahir
Presented By
Ch Muhammad Awais
2695/FBAS/BSCS4/F13(A)
M Mansoor Ul Haq
Nouman Dilshad
Faheem Akhtar
Muddasir Shabbir

Now the Question is
What Is Virtual Memory ??

Virtual memory
“separation of user logical memory from physical 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
 Allows address spaces to be shared by several processes
 Allows for more efficient process creation

Virtual Memory which is larger than Physical
Memory

Advantages Of Virtual Memory:
Multitasking
Allocating Memory Is Easy and Cheap
More Efficient Swapping
Process may even be larger than all of the physical memory.
This concept is very helpful in implementing multiprogramming environment.

Disadvantage's Of Virtual Memory:
Longer Memory Access Time As HDD Is Slower.
Memory Requirement.
Applications run slower if the system is using virtual memory.
It takes more time to switch between applications.
Less hard drive space for your use.

 Prevent over-allocation of memory by modifying page-fault service routine to
include page replacement
 Use modify 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
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. Bring the desired page into the (newly) free frame; update the page and frame tables
4. Restart the process
Basic Page Replacement

Why and When We Use Page Replacement Algorithm ?
 Want lowest 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
In all our examples, the reference string is
1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5

Treats page frames allocated to a process as a
circular buffer:
When the buffer is full, the oldest page is
replaced. Hence first-in, first-out:
A frequently used page is often the oldest, so it will be
repeatedly paged out by FIFO.
Simple to implement:
requires only a pointer that circles through the page
frames of the process.

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)
 4 frames
First In First Out Algorithms
1
2
3
4
1
2
5
3
4
1
2
3
9 page faults
1
2
3
1
2
3
5
1
2
4
5 10 page faults
44 3

• Replace page that will not be used for longest period of time
• 4 frames example
1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5
 How do you know this?
 Used for measuring how well your algorithm performs
Optimal Algorithm
1
2
3
4
6 page faults
4 5

• Reference string: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5
• 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
5
2
4
3
1
2
3
4
1
2
5
4
1
2
5
3
1
2
4
3
Least Recent Used (LRU) Algorithm

Use of a stack to Record The Most Recent Page Reference

LRU Approximation Algorithms
• Reference bit
o With each page associate a bit, initially = 0
o When page is referenced bit set to 1
o Replace the one which is 0 (if one exists)
• Second chance
o Need reference bit
o Clock replacement
o 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

Advantages :-
 LRU policy is often used as a page replacement algorithm
 It is quite good algorithm.
 It is easy to choose that has already page faulted and not in use for
long period.
Disadvantages:-
 Problem is how to implement LRU replacement Require substantial
hardware assistance
 Problem is determine the frame order by the time of last use.

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

Virtual memory and page replacement algorithm

Recommended

More Related Content

What's hot (20)

Viewers also liked (8)

Similar to Virtual memory and page replacement algorithm (20)

Recently uploaded (20)

Virtual memory and page replacement algorithm