[페이지 교체]LFU(Least Frequently Used) 방법 정리!

📘 LFU 페이지 교체 알고리즘

📖 페이지 교체란 무엇인가?

컴퓨터는 프로그램 실행 중 필요한 데이터를 메모리에 불러와서 작업합니다.
하지만 메모리의 크기는 한정돼 있어서, 새로운 데이터를 불러와야 할 때 이미 가득 찼다면 기존 데이터를 하나 제거해야 합니다.
이때 어떤 데이터를 제거할지를 결정하는 규칙을 페이지 교체 알고리즘이라고 부릅니다.
이 글에서는 자주 사용되지 않는 데이터를 제거하는 LFU (Least Frequently Used) 알고리즘에 대해 알아보겠습니다.

📖 LFU란 무엇인가?

LFU는 영어로 Least Frequently Used, 즉 가장 적게 사용된 데이터부터 제거한다는 뜻입니다.
메모리에 있는 데이터 각각이 지금까지 몇 번이나 사용되었는지를 기록하고, 그 수치가 가장 낮은 데이터를 제거합니다.
많이 쓰인 데이터는 남기고, 거의 쓰이지 않은 데이터부터 없애기 때문에 효율적입니다.

📖 LFU가 왜 필요한가?

메모리에 데이터를 무작위로 지우면 자주 쓰이는 데이터가 없어져 비효율적입니다.
FIFO처럼 단순히 오래됐다는 이유로 지우는 것도 비효율적일 수 있습니다.
LFU는 데이터를 얼마나 자주 쓰는지를 고려하기 때문에, 불필요한 교체를 줄이고 성능을 높이는 데 도움이 됩니다.

📖 LFU의 작동 원리

LFU의 기본 동작은 다음과 같습니다.

• ✅ 메모리에 있는 데이터마다 사용 횟수를 기록합니다.
• ✅ 메모리에 데이터가 들어오면 횟수를 1로 시작합니다.
• ✅ 메모리에서 데이터를 사용할 때마다 횟수를 1씩 더합니다.
• ✅ 메모리가 가득 찼다면, 가장 적게 사용된 데이터부터 제거합니다.
• ✅ 사용 횟수가 같은 데이터가 여러 개라면 보통 오래된 데이터를 먼저 제거합니다.

📖 예시로 배우기

이제 구체적인 예시를 통해 LFU가 어떻게 동작하는지 단계별로 살펴보겠습니다.

📄 전제 조건

• 메모리 크기: 3개(프레임 3개)
• 페이지 참조 순서:

4, 3, 2, 4, 3, 1, 4, 3, 5, 6

데이터를 불러올 때 메모리에 없으면 페이지 폴트, 메모리에 있으면 페이지 히트가 발생합니다.

📖 단계별 과정 — 매 단계마다 남은 데이터부터 보기

🔷 1단계

• 📜 남은 참조 순서: 4, 3, 2, 4, 3, 1, 4, 3, 5, 6
• 🔗 이번에 불러올 데이터: 4
• 행동: 메모리에 4가 없으니 추가하고 사용 횟수를 1로 기록합니다. (페이지 폴트)
• 📌 메모리 상태: [4] (4=1)

🔷 2단계

• 📜 남은 참조 순서: 3, 2, 4, 3, 1, 4, 3, 5, 6
• 🔗 이번에 불러올 데이터: 3
• 행동: 메모리에 3이 없으니 추가하고 사용 횟수를 1로 기록합니다. (페이지 폴트)
• 📌 메모리 상태: [4, 3] (4=1, 3=1)

🔷 3단계

• 📜 남은 참조 순서: 2, 4, 3, 1, 4, 3, 5, 6
• 🔗 이번에 불러올 데이터: 2
• 행동: 메모리에 2가 없으니 추가하고 사용 횟수를 1로 기록합니다. (페이지 폴트)
• 📌 메모리 상태: [4, 3, 2] (4=1, 3=1, 2=1)

🔷 4단계

• 📜 남은 참조 순서: 4, 3, 1, 4, 3, 5, 6
• 🔗 이번에 불러올 데이터: 4
• 행동: 4는 메모리에 있으니 사용 횟수를 2로 증가시킵니다. (페이지 히트)
• 📌 메모리 상태: [4, 3, 2] (4=2, 3=1, 2=1)

🔷 5단계

• 📜 남은 참조 순서: 3, 1, 4, 3, 5, 6
• 🔗 이번에 불러올 데이터: 3
• 행동: 3은 메모리에 있으니 사용 횟수를 2로 증가시킵니다. (페이지 히트)
• 📌 메모리 상태: [4, 3, 2] (4=2, 3=2, 2=1)

🔷 6단계

• 📜 남은 참조 순서: 1, 4, 3, 5, 6
• 🔗 이번에 불러올 데이터: 1
• 행동: 메모리가 가득 찼습니다. 가장 적게 사용된 2를 제거하고 1을 추가합니다. (페이지 폴트)
• 📌 메모리 상태: [4, 3, 1] (4=2, 3=2, 1=1)

🔷 7단계

• 📜 남은 참조 순서: 4, 3, 5, 6
• 🔗 이번에 불러올 데이터: 4
• 행동: 4는 메모리에 있으니 사용 횟수를 3으로 증가시킵니다. (페이지 히트)
• 📌 메모리 상태: [4, 3, 1] (4=3, 3=2, 1=1)

🔷 8단계

• 📜 남은 참조 순서: 3, 5, 6
• 🔗 이번에 불러올 데이터: 3
• 행동: 3은 메모리에 있으니 사용 횟수를 3으로 증가시킵니다. (페이지 히트)
• 📌 메모리 상태: [4, 3, 1] (4=3, 3=3, 1=1)

🔷 9단계

• 📜 남은 참조 순서: 5, 6
• 🔗 이번에 불러올 데이터: 5
• 행동: 메모리가 가득 찼습니다. 가장 적게 사용된 1을 제거하고 5를 추가합니다. (페이지 폴트)
• 📌 메모리 상태: [4, 3, 5] (4=3, 3=3, 5=1)

🔷 10단계

• 📜 남은 참조 순서: 6
• 🔗 이번에 불러올 데이터: 6
• 행동: 메모리가 가득 찼습니다. 가장 적게 사용된 5를 제거하고 6을 추가합니다. (페이지 폴트)
• 📌 메모리 상태: [4, 3, 6] (4=3, 3=3, 6=1)

📖 최종 결과

• 최종 메모리 상태: [4, 3, 6]
• 페이지 폴트 발생 횟수: 6회
• 페이지 히트 발생 횟수: 4회

📖 LFU의 장점과 단점

장점

• ✅ 자주 쓰이는 데이터는 오래 유지됩니다.
• ✅ 불필요한 교체가 줄어듭니다.

단점

• ❌ 오래전에 많이 쓰였지만 최근에는 쓰이지 않는 데이터가 남아있을 수 있습니다.
• ❌ 사용 횟수를 계산해야 하기 때문에 구현이 더 복잡합니다.

📖 마무리

• ✅ LFU는 “가장 적게 사용된 데이터부터 제거”하는 알고리즘입니다.
• ✅ 매 단계마다 남아 있는 참조 순서를 먼저 보고 현재 처리할 데이터를 이해하면 흐름을 쉽게 파악할 수 있습니다.
• ✅ 자주 쓰이는 데이터는 지키고, 거의 쓰이지 않는 데이터를 지우기 때문에 효율적입니다.

혹시 FIFO, LRU, OPT와의 비교 글이나 더 많은 예제가 필요하다면 요청해 주세요.
다음 글에서 더 심화된 내용을 다뤄 드리겠습니다.