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

(page 1)

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)

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

(page 2)

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)

(page 3)

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)

(page 4)

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)

(page 5)

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)

(page 6)

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)

(page 7)

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

(page 8)

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)
w 50 (page 0)w 15400 (page 30)r 2200 (page 4)

(page 9)

PLRU example 2

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

(page 10)

PLRU example 2

v

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

(page 11)

PLRU example 2

v

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

(page 12)

PLRU example 2

v v

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

(page 13)

PLRU example 2

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

(page 14)

PLRU example 2

• Same as normal LRU
• We were unlucky

(page 15)

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

(page 16)

PLRU example 3

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

(page 17)