Lookahead list example
w 2000
w 1492
r 456
w 24121
r 24120
r 34
r 4592
r 2000
w 2000
r 1492
r 24120
Contains 0 operations.
0 operations processed.
Initially empty.
(page 1)
Lookahead list example
* w 2000
w 1492
r 456
w 24121
r 24120
r 34
r 4592
r 2000
w 2000
r 1492
r 24120
Contains 1 operation.
0 operations processed.
(page 2)
Lookahead list example
w 2000
* w 1492
r 456
w 24121
r 24120
r 34
r 4592
r 2000
w 2000
r 1492
r 24120
Contains 2 operations.
0 operations processed.
(page 3)
Lookahead list example
w 2000
w 1492
* r 456
w 24121
r 24120
r 34
r 4592
r 2000
w 2000
r 1492
r 24120
Contains 3 operations.
0 operations processed.
(page 4)
Lookahead list example
w 2000
w 1492
r 456
* w 24121
r 24120
r 34
r 4592
r 2000
w 2000
r 1492
r 24120
Contains 4 operations.
0 operations processed.
(page 5)
Lookahead list example
+ w 2000
w 1492
r 456
w 24121
* r 24120
r 34
r 4592
r 2000
w 2000
r 1492
r 24120
Contains 4 operations.
1 operation processed.
(page 6)
Lookahead list example
w 2000
+ w 1492
r 456
w 24121
r 24120
* r 34
r 4592
r 2000
w 2000
r 1492
r 24120
Contains 4 operations.
2 operations processed.
(page 7)
Lookahead list example
w 2000
w 1492
+ r 456
w 24121
r 24120
r 34
* r 4592
r 2000
w 2000
r 1492
r 24120
Contains 4 operations.
3 operations processed.
(page 8)
Lookahead list example
w 2000
w 1492
r 456
+ w 24121
r 24120
r 34
r 4592
* r 2000
w 2000
r 1492
r 24120
Contains 4 operations.
4 operations processed.
(page 9)
Lookahead list example
w 2000
w 1492
r 456
w 24121
+ r 24120
r 34
r 4592
r 2000
* w 2000
r 1492
r 24120
Contains 4 operations.
5 operations processed.
(page 10)
Lookahead list example
w 2000
w 1492
r 456
w 24121
r 24120
+ r 34
r 4592
r 2000
w 2000
* r 1492
r 24120
Contains 4 operations.
6 operations processed.
(page 11)
Lookahead list example
w 2000
w 1492
r 456
w 24121
r 24120
r 34
+ r 4592
r 2000
w 2000
r 1492
* r 24120
Contains 4 operations.
7 operations processed.
(page 12)
Lookahead list example
w 2000
w 1492
r 456
w 24121
r 24120
r 34
+ r 4592
r 2000
w 2000
r 1492
* r 24120
Contains 4 operations.
7 operations processed.
No more input!
flush() is called, which indicates to process the
rest of the lookahead list.
(page 13)
Lookahead list example
w 2000
w 1492
r 456
w 24121
r 24120
r 34
r 4592
+ r 2000
w 2000
r 1492
r 24120
Contains 3 operations.
8 operations processed.
(page 14)
Lookahead list example
w 2000
w 1492
r 456
w 24121
r 24120
r 34
r 4592
r 2000
+ w 2000
r 1492
r 24120
Contains 2 operations.
9 operations processed.
(page 15)
Lookahead list example
w 2000
w 1492
r 456
w 24121
r 24120
r 34
r 4592
r 2000
w 2000
+ r 1492
r 24120
Contains 1 operation.
10 operations processed.
(page 16)
Lookahead list example
w 2000
w 1492
r 456
w 24121
r 24120
r 34
r 4592
r 2000
w 2000
r 1492
+ r 24120
Contains 0 operations.
All 11 operations
processed.
(page 17)
Finding frame to remove
- Starts from back of cache list
- Examines frames one at a time
- When it finds one which isn't needed by the operations in the lookahead list
- This is the frame which is removed
- Examines at most check_frames frames
(page 18)
PLRU example 1
- num_frames = 6, page_size = 512
- lookahead = 3, check_frames = 4
- Current operation:
- Lookahead list:
w 50 (page 0)w 15400 (page 30)r 2200 (page 4)
(page 19)
PLRU example 1
- Page 2 is not in cache
- Cache miss
- Must find a frame to remove
(page 20)
PLRU example 1
v
^
- Start at back of list
- Page 4 is in lookahead list
- Don't remove this frame
- Normal LRU algorithm would blindly remove this frame
(page 21)
PLRU example 1
v
^
- Move to next frame
- Page 30 is in lookahead list
- Don't remove this frame
(page 22)
PLRU example 1
v
^
- Move to next frame
- Page 42 is NOT in lookahead list
- Remove this frame
- Then add page 2 as usual
(page 23)
PLRU example 1
- Pages 30 and 4 are still in cache
- So will be cache hits when the upcoming operations are processed
(page 24)