2

I wrote a simulation program of page replacement, where Clock algorithm (use 1 bit use bit) performs exactly same as FIFO, which makes me very confused.

Here I have a simple case to replicate my difficulty:

Say I have page 1 3 5 7 in memory, and initially memory is like:
1 use=1 <- handle
3 use=1
5 use=1
7 use=1

When 2 needs to be inserted, clock handle travels through all the pages and 
at last substitute 1:
1 use=0 <- handle
3 use=0
5 use=0
7 use=0
To:
2 use=1
3 use=0 <- handle
5 use=0
7 use=0

Then I need to insert 4:
2 use=1
4 use=1
5 use=0 <- handle
7 use=0

Then after 6 and 8:
2 use=1 <- handle
4 use=1
6 use=1
8 use=1

Suppose FIFO evicts the front page (first), and insert to the end. In this example, Clock is exactly same as FIFO, which always evicts the oldest (front) page.

I don't know what I have done wrong, can someone point it out?

Lingyuan

Lingyuan He
  • 156
  • 2
  • 3
  • 8

1 Answers1

0

You didn't do anything wrong. The clock/second-chance algorithm will behave the same as FIFO as long as a page already in memory is requested again. A that point, the reference bit is set to 1, and the next time that page is up to be replace, instead of replacing it, the reference bit is set to zero, and the next candidate victim page is examined in the same fashion. So, you could say that the page with the flipped bit was given a... second chance.

user3591541
  • 49
  • 8