LIRS, LRU and Ideal cache Implementation

Caches

1. clone this repository

git clone https://github.com/Barkir/VladimirovTasks

2. create build directory

mkdir build

3. run cmake from build dir

cd build
cmake ..

4. compile from build dir

cmake --build .

5. you will get two targets - lirs and lru (hopefully).

Testing UPD

Now for testing you can use run_tests.py

you can choose LRU, LIRS, IDEAL testing.

you'll need those libraries.

pip3 install questionary
pip3 install pathlib

---

How to test LRU?

Write your tests in tests directory in this fmt

1 : TEST_NAME (no spaces!!!)
2 : cache_size
3 : number of page calls
4 : call seqeunce
5 : number of hits you wait for

Then make run_tests.sh executable

chmod +x run_tests.sh

and run it

./run_tests.sh

---

LIRS tests implementation

Testing infrastructure of LIRS cache will differ from LRU. There is a class called LIRS Stats whhere we collect these data:

• size_t hits
• size_t misses

The LIRS cache will have two get functions - one is for regular use and one is for testing.

T& get(int key) {
    return getFunc(key, true);
}

T& getWithStats(int key) {
    return getFunc(key, false)
}

How to test LIRS?

To write a test - use this format:

{lir_size} {hir_size} {number of calls} {call sequence}

Then run program like this:

./lirs < test.txt

Then it prints you this info:

1. Total hits
2. Total misses
3. Hit Rate

That's all 4 today.

References

MySQL LIRS implementation source code

LIRS wiki

LIRS article

my attempts to figure out what's going on :|