Question

A practical page replacement algorithm should have a low time overhead and be adaptive to various workloads.

Please explain how ARC achieves these two goals. In addition, among the related work mentioned in the paper <<A self-tuning, low overhead replacement cache>>, describe a counter-example for each of the goals (and explain why in detail).

Answer 1

Answer: In operating system, there are many page replacement algorithms out there like First-in-First out (FIFO), Least Recently used(LRU), Optimal page replacement and Random page replacement. All these algorithms are pratical algorithms as they are work on a simple principle in which whenever a page hits the computer memory and its not there in the memory page fault occurs and based on the algorithms applied the new replaces the page already inside the memory. Now which page got replaced depends on the algorithm.

All the replacement algorithms must be adaptive to different types of workloads nad should have low time overhead.

ARC helps in achieving these goals by reducing the time of work process for the replacement in the memory by increasing the throughput. Low overhead is achieved by ARC using least time bound of zero.