Name and describe four page replacement algorithms. Critically compare them with each
other.
Answer:
OPTIMAL: Impossible to achieve, but perfect. Works on the Nostradamus-like basis that we can predict which page won’t be used for the longest time, and elect that that one should be replaced.
LEAST RECENTLY USED: Most commonly used, not quite optimal but better than the rest. We mark
every page with a timestamp and the one which has been least recently accessed gets the flick. However we need to account for the extra overhead of adding/reading the time stamp, and who knows, the next page we want to access might just be the one we’ve sent back to the aether. It’s quite a performer though.
CLOCK: Each page is marked with a ‘usage’ bit, and each is given a ‘second chance’ upon page
replacement time. The one that becomes unmarked first disappears. Not quite as accurate as LRU, but has less of an overhead (one extra bit, as opposed to many for the timestamp).
FIFO: The simple and dodgiest option, we make the foolish assumption that the oldest page in the queue
is the one that gets tossed. This is not quite always the case.
LEAST RECENTLY USED: Most commonly used, not quite optimal but better than the rest. We mark
every page with a timestamp and the one which has been least recently accessed gets the flick. However we need to account for the extra overhead of adding/reading the time stamp, and who knows, the next page we want to access might just be the one we’ve sent back to the aether. It’s quite a performer though.
CLOCK: Each page is marked with a ‘usage’ bit, and each is given a ‘second chance’ upon page
replacement time. The one that becomes unmarked first disappears. Not quite as accurate as LRU, but has less of an overhead (one extra bit, as opposed to many for the timestamp).
FIFO: The simple and dodgiest option, we make the foolish assumption that the oldest page in the queue
is the one that gets tossed. This is not quite always the case.
Share To Friends Via:
Define the word operating system. 
