Adaptive Replacement Cache (ARC) Algorithm

A project for Advanced Operating System(CS604) that implements ARC cache replacement policy.

Refer to paper Outperforming LRU with an adaptive replacement cache algorithm

Project done under supervision of Dr. Nitin Auluck

Implementation

Four primary lists:

1. MRU(T1) contains the top or most-recent pages in L1


2. MRUG(B1) contains the bottom or least-recent pages in L1


3. MFU(T2) contains the top or most-recent pages in L2


4. MFUG(B2) contains the bottom or least-recent pages in L2

Size of these lists is controlled by parameter p, which controls the ratio of sizes between most-recent and least-recent pages

Implemented in C++ using containers from Standard Template Library(STL)

Results

ARC outperforms LRU in terms of hit-ratio and execution time (calculated in sec.)

See Result Graphs