Could someone help me to figure an example of MRU and CLOCK?

Question

As title.

There is a buffer pool with 3 pages that receives requests for the following page numbers:

2,4,4,2,5,2,1,1,3,1

The replacement policies are MRU and CLOCK. I am confused about how they work. Could someone show me? Thanks a lot~

update:

There is my solution following the MRU policy:

2

2 4

2 4

2 4

2 4 5

2 4 5

1 4 5

3 4 5

1 4 5

Is that right?

And following the LRU policies:

          hit/miss?

2 m

2 4 m

2 4 h

2 4 h

2 4 5 m

2 4 5 h

2 1 5 m

2 1 5 h

2 1 3 m

2 1 3 h

Is that right?

Answer 1

There is my solution following the MRU policy... Is that right?

As per the definition of MRU mentioned by you, your MRU page replacement policy appears correct.

The replacement policies are MRU and CLOCK. I am confused about how they work. In this case(for 2,4,4,2,5,2,1,1,3,1 page numbers) :

In Clock page replacement policy, the OS circulates through pages, clearing reference bits and finding a page with reference bit set to 0.

Page number                  Reference bit

 2                               1
2,4                             1,1
2,4                             1,1
2,4                             1,1
2,4,5                          1,1,1
2,4,5                          1,1,1
1,4,5                          1,0,0
1,4,5                          1,0,0
1,3,5                          1,1,0
1,3,5                          1,1,0

And following the LRU policies: hit/miss? Is that right?

YES, for the LRU page replacement, the page ordering as well as the number of hits and misses both are correct.

Answer 2

For MRU eviction policy, let's keep the MRU page at the front. With the given request list, following will be the state of buffers:

2 -> 2
4 -> 2 4
4 -> 2 4
2 -> 4 2
5 -> 4 2 5
2 -> 4 5 2
1 -> 4 5 1
1 -> 4 5 1
3 -> 4 5 3
1 -> 4 5 1

---

For the CLOCK eviction policy, the page list would be ( * represents the buffer location to be filled in when a page fault occurs):

2 -> 2 *
4 -> 2 4 *
4 -> 2 4 *
2 -> 2 4 *
5 -> 2* 4 5
2 -> 2* 4 5
1 -> 1 4* 5
1 -> 1 4* 5
3 -> 1 3 5*
1 -> 1 3 5*

---

Following LRU policy, let's keep LRU page at the back. State of buffers will be:

2 -> 2
4 -> 2 4
4 -> 2 4
2 -> 4 2
5 -> 4 2 5
2 -> 4 5 2
1 -> 5 2 1
1 -> 5 2 1
3 -> 2 1 3
1 -> 2 3 1