Page replacement

Operating System - Page replacement

1. Page Replacement
Sashikanta Taorem
MTech – CSE
1
st
Semester
Presented by:

2. Overview
1.Why we need page replacement?
3.Basic page replacement technique.
5.Different type of page replacement
algorithm and their examples.

3. Why????
Limited physical memory --> limited number
of frame --> limited number of frame
allocated to a process.

4. Basic Page Replacement
1.Find the location of the desired page on the
disk.
3.Find a free frame
If there is a free frame use it.
No free frame – use page replacement algorithm to
select a victim frame.
Write the victim frame to disk, change the frame and
page tables accordingly.

5. Basic Page Replacement (Contd)
3. Read the desired page into the newly freed
frame, change the page and frame tables.
4. Restart the user process.

6. Page Replacement
Victim
Swap desire
page in
Reset page
table for new
page
Change to
invaid
Page table
Frame
Valid
invalid bit
2
4
3
0
F
I
V
Swap out
victim page
1
Physical memory

7. Overhead
If no free frames - 2 page transfers.
Solution : Modify bit or Dirty bit.

8. Replacement Policy
Which page to be replaced?
Page removed should be the page least
likely to be referenced in the near future.
Most policies predict the future behavior on
the basis of past behavior.

9. Page faults versus number of frames
Number of frames
Number of page
faults

10. Replacement Algorithm
1.FIFO page replacement
3.Optimal page replacement
5.LRU page replacement
7.LRU-Approximation page replacement
9.Counting-Based page replacement

11. FIFO Page Replacement
Easy to understand and program.
Performance is not always good.
Belady’s Anomaly

12. Drawbacks - FIFO
A page which is being accessed quite often
may also get replaced because it arrived
earlier than those present
Ignores locality of reference. A page which
was referenced last may also get replaced,
although there is high probability that the
same page may be needed again.

13. FIFO – An Example
70120304230321201701
7
0
77
0
1
2
0
1
2
3
1
2
3
0
4
3
0
4
2
0
4
2
3
0
2
3
0
1
3
0
1
2
7
1
2
7
0
2
7
0
1

14. Optimal Page Replacement
Lowest page fault rate of all algorithms
Free from Belady’s anomaly

15. Optimal Page Replacement (contd)
“Replace the page that will not be used for the
longest period of time.”
Requires future knowledge of the reference
string.
Used for comparison studies.

16. OPR – An Example
70120304230321201701
7
0
77
0
1
2
0
1
2
0
3
2
4
3
2
0
3
7
0
1
2
0
1

17. LRU Page Replacement
Free from Belady’s Anomaly.
Problem: How to order the frame defined by
the time of last use.
Solution:
Counters
Queue

18. LRU – An Example
70120304230321201701
7
0
77
0
1
2
0
1
2
0
3
4
3
4
2
3
2
0
3
7
0
1
0
4
2
0
2
3
1
2
0
1

19. LRU – Approximation Page
Replacement
Additional-Reference-Bits Algorithm
Second-Chance Algorithm
Enhanced Second-Chance Algorithm

20. Additional-Reference-Bits Algorithm
Uses reference bit, initially at 0 ,after reference h/w
updates it to 1.
We can use 8-bit byte as reference bits history.
At regular interval
–Shift the reference bit into the high-order bit of 8-bit byte,
shifting the other bits right by 1 bit and discarding the low-
order bit.

21. Additional-Reference-Bits Algorithm
Example:
00000000 – page has not been use for eight time
period.
11111111 – use at least once in each time period.
11000100 is use more recently than 01110111

22. Second-Chance Algorithm
Uses FIFO and a reference bit.
Implement using a circular queue.
Refer as CLOCK algorithm.

24. Enhanced Second-Chance Algorithm
Considers the Reference bit and the modify
bit as an ordered pair, (Reference bit,
Modify bit).
Four possible cases:
1.(0,0) – neither recently used nor modified.
2.(0,1)
3.(1,0)
4.(1,1)

25. Counting-Based Page Replacement
Uses COUNTERS to count the number of
references that have been made to each
page.
3.Least Frequently used
4.Most frequently Used

26. Page-Buffering algorithm
Uses POOL of frames
When a page fault occurs, a victim is chosen but the
page is read into a free frame from the pool before
the victim is written out.
When a page fault occurs, we first check whether the
desire page is in the free-frame pool. If it is not, we
must select a free frame and read into it.

27. Objective Questions!!!

28. Ans: C
1.Dirty bit is used to show the
a. page with corrupted data
b. the wrong page in the memory
c. page that is modified after being loaded
into cache memory
d. page that is less frequently accessed.

29. Ans: C
2. What replacement policy is used by Windows NT
a.LRU
b.NFU
c.FIFO
d.Clock Replacement
e.None of the above

30. CLOCK algorithm
3. Second-Chance page replacement algorithm
is also known as ………………

31. Reference String
4. The string of memory references is called
___________.

32. Belady’s Anomaly
5. FIFO page replacement suffers from
________________anomaly.

33. Page fault increases with increase in
number of frames.
6. What is Belady’s anomaly??

34. TRUE
7. Optimal Page Replacement algorithm has
the lowest page fault rate.
TRUE/FALSE

35. The reference bit and the modify bit
8. Enhanced Second-Chance algorithm uses
_____________and ___________ as an
ordered pair.