Exploring the LRU Algorithm: A Journey into Cache Management

🧠Intuition

The LRU stands for “least recently used”. The everyday scenario of “least recently used” is when you hit Alt + Tab in Windows and the application being used shown up. The least recently used app will be in the far right.

In this exploration, we will delve into the mechanics of the LRU algorithm, using a concrete example to illustrate its operation and effectiveness.

⛳Objective

before:
after:

Our example starts with an initial state like so. After dealing with the sequence of requests to read B->C->B->A->D->A->E->C->E, the memory slot will be filled with E C A.

📖Terminology

Although using the Alt + Tab is the most common scenario I can think of, the application of LRU applies to context of database. Before delving into the concrete example, let me first introduce few terms.

page: you can simply think of page as a block of data. e.g. A,B,C,D,E refer to 5 different block of data.
page fault: when you try to access the data of a page, the page doesn’t show up in the memory yet. In this case, it will occur and trigger the migration of this page from disk to memory.
page hit: opposite to page fault, when you try to access the page, it’s already loaded into the memory.
unreference: the page remains

🗣Step by step

0️⃣

current state☑️: we haven’t read any page into the memory.
what’s next🎯: we are about to read the page B.

1️⃣

current state☑️: We have read B into the memory.
- red: Since B was not in the memory yet, this is a page fault.
- 1: This is the 1st time reading. Put it as the history of querying page B.
- gray bar: [B] is loaded.
what’s next🎯: we are about to read the page C.\

2️⃣

current state☑️: We have read C into the memory.
- red: Since C was not in the memory yet, this is a page fault.
- 2: This is the 2nd time reading. Put it as the history of querying page C.
- gray bar: [B, C] are loaded.
what’s next🎯: we are about to read the page B.\

3️⃣

current state☑️: We have read B into the memory.
- green: Since B is already in the memory, this is a page hit.
- 3: This is the 3rd time reading. Put it as the history of querying page B.
- gray bar: [B, C] are loaded.
what’s next🎯: we are about to read the page A.\

4️⃣

current state☑️: We have read A into the memory.
- red: Since A was not in the memory, this is a page fault.
- 4: This is the 4th time reading. Put it as the history of querying page A.
- gray bar: [A, B, C] are loaded.
what’s next🎯: we are about to read the page D.\

5️⃣

current state☑️: We have read D into the memory.
- Slots are full and we evicted C. Why?
  - C held the smallest value of history. See the preceding diagram that
    - A:4
    - B:3
    - C:2👈
    - (the smaller value is, the page is less used)
- red: Since D was not in the memory, this is a page fault.
- 5: This is the 5th time reading. Put it as the history of querying page D.
- gray bar: [A, B, D] are loaded.
what’s next🎯: we are about to read the page A.\

6️⃣

current state☑️: We have read A into the memory.
- green: Since A is already in the memory, this is a page hit.
- 6: This is the 6th time reading. Put it as the history of querying page A.
- gray bar: [A, B, D] are loaded.
what’s next🎯: we are about to read the page E.\

7️⃣

current state☑️: We have read E into the memory.
- Slots are full and we evicted B. Why?
  - B held the smallest value of history. See the preceding diagram that
    - A:6
    - B:3👈
    - D:5
    - (the smaller value is, the page is less used)
- red: Since E was not in the memory, this is a page fault.
- 7: This is the 7th time reading. Put it as the history of querying page E.
- gray bar: [A, D, E] are loaded.
what’s next🎯: we are about to read the page C.\

8️⃣

current state☑️: We have read C into the memory.
- Slots are full and we evicted D. Why?
  - D held the smallest value of history. See the preceding diagram that
    - A:6
    - D:5👈
    - E:7
    - (the smaller value is, the page is less used)
- red: Since C was not in the memory, this is a page fault.
- 8: This is the 8th time reading. Put it as the history of querying page C.
- gray bar: [A, C, E] are loaded.
what’s next🎯: we are about to read the page E.\

9️⃣

current state☑️: We have read E into the memory.
- green: Since E is already in the memory, this is a page hit.
- 9: This is the 9th time reading. Put it as the history of querying page E.
- gray bar: [A, C, E] are loaded.
what’s next🎯: $\emptyset$ nope, we have finished all the queries.