LFU 메모리 페이지 교체

좋습니다!
이번엔 LFU (Least Frequently Used) 알고리즘을 그림과 함께 예시로 쉽게 설명드릴게요.
LRU보다 더 똑똑한 방식이라고도 볼 수 있어요.

---

✅ LFU (Least Frequently Used)란?

• 가장 적게 사용된 페이지를 교체하는 알고리즘입니다.
• 각 페이지마다 사용 횟수(빈도수)를 기록해두고,
• 사용 빈도가 가장 낮은 페이지를 교체합니다.

💡 LRU는 “언제”를 기준으로 하고,
💡 LFU는 “얼마나 자주”를 기준으로 합니다.

---

🧠 예시 상황

• 프레임 수: 3
• 페이지 요청 순서:
  👉 7, 0, 1, 2, 0, 3, 0, 4

---

📊 LFU 페이지 교체 시뮬레이션

각 요청마다 사용 횟수도 같이 적어볼게요.

요청	프레임 상태	사용 횟수	교체됨?	설명
7	[7]	7(1)	O	7 삽입
0	[7, 0]	7(1), 0(1)	O	0 삽입
1	[7, 0, 1]	7(1), 0(1), 1(1)	O	1 삽입
2	[0, 1, 2]	0(1), 1(1), 2(1)	✅	7 제거 (모두 1회지만 7이 먼저 들어옴)
0	[0, 1, 2]	0(2), 1(1), 2(1)		0 사용 → 횟수 증가
3	[0, 2, 3]	0(2), 2(1), 3(1)	✅	1 제거 (사용횟수 가장 낮은 것 중 먼저 들어온 1 제거)
0	[0, 2, 3]	0(3), 2(1), 3(1)		0 사용 → 횟수 증가
4	[0, 3, 4]	0(3), 3(1), 4(1)	✅	2 제거

---

🖼️ 그림으로 표현

페이지 요청:   7   0   1   2   0   3   0   4
메모리 상태:

7   → [7]              (7:1)
0   → [7, 0]           (7:1, 0:1)
1   → [7, 0, 1]        (7:1, 0:1, 1:1)
2   → [0, 1, 2]        (7 제거, 모두 1이지만 먼저 들어온 7 제거)
0   → [0, 1, 2]        (0 사용 → 0:2)
3   → [0, 2, 3]        (1 제거, 1:1 가장 낮음)
0   → [0, 2, 3]        (0 사용 → 0:3)
4   → [0, 3, 4]        (2 제거, 2:1)

---

✅ 정리

알고리즘	기준	장점	단점
FIFO	가장 오래된 순	구현 간단	성능 낮음 (Belady anomaly 발생)
LRU	가장 오랫동안 안 쓴 순	성능 보통~좋음	구현 약간 복잡
LFU	가장 적게 사용된 순	자주 쓰는 건 유지, 효율적	구현 복잡, 동률 처리 필요

---

🔍 LFU 단점도 알아두자!

• 동률인 경우 어떻게 제거할지 추가 정책 필요 (예: FIFO처럼 가장 오래된 거 제거)
• 특정 페이지가 한번이라도 자주 사용되면 계속 유지될 수 있어 갱신 어려움
  → 그래서 실제로는 LFU + LRU 혼합 방식도 자주 씁니다

---

필요하시면 세 가지 알고리즘을 애니메이션, 표, 코드까지 비교해드릴 수 있어요.
혹은 Java나 Python으로 구현해볼 수도 있고요!
어떤 방식으로 더 보고 싶으세요? 😊