Suppose that we have main memory using the local Least Recently Used (LRU) repla
ID: 3826014 • Letter: S
Question
Suppose that we have main memory using the local Least Recently Used (LRU) replacement scheme and the One-Block-Lookahead (OBL) prefetching scheme. OBL prefetching is also known as prefetch-on-a miss because virtual page i+1 is prefetched when we have a page fault on virtual page i. We assume that 4 page frames are allocated to a process, and the process references its virtual pages in the following order: 7, 5, 8, 6, 9, 5, 7. Illustrate the change in the LRU stack for each reference, and clearly describe how the LRU and OBL prefetching work together for each reference (to make the change in the LRU stack).Explanation / Answer
Least recently used policy marks a block with timestamp on every access. and chooses block with the lowest tag for replacement.
OBL pre fetches block b+1 whenever there is a miss on block b.
Process is allocated four page frames. and virtual pages are referenced on order
7,5,8,6,9,5,7.Following is the LRU stack for each reference.
Page frame
Virtual Page
Timestamp
0
empty
0
1
empty
0
2
empty
0
3
empty
0
1. Reference 7
Page frame
Virtual Page
Timestamp
0
7
1
1
8
0
2
empty
0
3
empty
0
(Page 7 is brought into page frame 0.page 8 is also fetched as per OBL scheme and put into page frame 1. Timestamp for page 8 is reset. Timestamp for page 7 is updated.)
2. Reference 5
Page frame
Virtual Page
Timestamp
0
7
1
1
8
0
2
5
2
3
6
0
(Page 5 is brought into page frame 2.page 6 is also fetched as per OBL scheme and put into page frame 3. Timestamp for page 6 is reset. Timestamp for page 5 is updated.)
3. Reference 8
Page frame
Virtual Page
Timestamp
0
7
1
1
8
3
2
5
2
3
6
0
(As page 8 is already there, only its stamp is updated)
4. Reference 6
Page frame
Virtual Page
Timestamp
0
7
1
1
8
3
2
5
2
3
6
4
(As page 8 is already there, only its stamp is updated)
5. Reference 9
Page frame
Virtual Page
Timestamp
0
9
5
1
8
3
2
10
0
3
6
4
(7 and 5 are chosen for replacement. Virtual page 10 is also brought in. Timestamp for page 10 is reset. Timestamp for page 9 is updated.)
6. Reference 5
Page frame
Virtual Page
Timestamp
0
9
5
1
8
3
2
5
6
3
6
4
(Page 10 is chosen for replacement. Page 6 is already there.)
6. Reference 7
Page frame
Virtual Page
Timestamp
0
9
5
1
7
7
2
5
6
3
8
0
(Page 8 and 6 is chosen for replacement. Timestamp for page 8 is reset. And Timestamp for page 7 is updated.)
Please let me know in case of any doubts.
Thanks.
Page frame
Virtual Page
Timestamp
0
empty
0
1
empty
0
2
empty
0
3
empty
0
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.