---

All frames needed soon?

• What if we examine all check_frames frames and all are in lookahead list?
• Which one do we choose to remove?
• The one which is first needed at the latest time
  • An example should make it clear

All frames needed example

w 1492 (page 2)
w 50 (page 0)
w 15400 (page 30)
w 15300 (page 30)
w 180 (page 0)
r 2200 (page 4)
w 1292 (page 2)

• Consider this lookahead list
• Suppose all checked frames are in this lookahead list
  • Which frame do we remove?

All frames needed example

w 1492 (page 2)
w 50 (page 0)
w 15400 (page 30)
w 15300 (page 30)
w 180 (page 0)
r 2200 (page 4)
w 1292 (page 2)

All frames needed example

w 1492 (page 2) First (page 2)w 50 (page 0)
w 15400 (page 30)
w 15300 (page 30)
w 180 (page 0)
r 2200 (page 4)
w 1292 (page 2)

All frames needed example

w 1492 (page 2) First (page 2)w 50 (page 0) First (page 0)w 15400 (page 30)
w 15300 (page 30)
w 180 (page 0)
r 2200 (page 4)
w 1292 (page 2)

All frames needed example

w 1492 (page 2) First (page 2)w 50 (page 0) First (page 0)w 15400 (page 30) First (page 30)w 15300 (page 30)
w 180 (page 0)
r 2200 (page 4)
w 1292 (page 2)

All frames needed example

w 1492 (page 2) First (page 2)w 50 (page 0) First (page 0)w 15400 (page 30) First (page 30)w 15300 (page 30)
w 180 (page 0)
r 2200 (page 4) First (page 4)w 1292 (page 2)

All frames needed example

w 1492 (page 2) First (page 2)w 50 (page 0) First (page 0)w 15400 (page 30) First (page 30)w 15300 (page 30)
w 180 (page 0)
r 2200 (page 4) First (page 4)w 1292 (page 2)

• Construct a list in order of when pages are first used, ie: 2, 0, 30, 4
  • Use the last item, ie. remove frame containing page 4

PLRU example 2

• Same as before, except:
  • check_frames = 2

• num_frames = 6, page_size = 512
• lookahead = 3, check_frames = 2
• Current operation:
  w 1492 (page 2)
• Lookahead list:
  w 50 (page 0)w 15400 (page 30)r 2200 (page 4)

PLRU example 2

• Page 2 is not in cache
• Cache miss
• Must find a frame to remove

PLRU example 2

v

^

• Start at back of list
• Page 4 is in lookahead list
• Don't remove this frame

PLRU example 2

v

^

• Move to next frame
• Page 30 is in lookahead list
• Don't remove this frame

PLRU example 2

v v

^ ^

• Cannot move to next frame
  • Since check_frames is only 2
• Must choose one of the last 2 frames

PLRU example 2

• Examine lookahead list:
  w 50 (page 0)w 15400 (page 30)r 2200 (page 4)
• Page 30 is needed before page 4
• So remove page 4

PLRU example 2

• Same as normal LRU
• We were unlucky

PLRU example 3

• What if the page 30 and page 4 operations were swapped?
  w 50 (page 0)r 2200 (page 4)w 15400 (page 30)

v v

^ ^

• Still must choose one of last 2 frames

PLRU example 3

• This time page 4 is needed before page 30
• So remove page 30

(page 17)