LRU 메모리 페이지 교체

좋습니다!
이번엔 LRU (Least Recently Used) 알고리즘을 그림과 함께 예시로 쉽게 설명드릴게요.

---

✅ LRU (Least Recently Used)란?

• 가장 오랫동안 사용되지 않은 페이지를 교체하는 알고리즘입니다.
• 즉, 최근에 사용한 적이 없는 페이지를 메모리에서 쫓아냅니다.
• 보통 Stack, LinkedHashMap 또는 시간 기록 등을 활용해 구현합니다.

---

🧠 예시 상황

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

---

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

[ 7 ]           → MISS (7 넣음)
[ 7 0 ]         → MISS (0 넣음)
[ 7 0 1 ]       → MISS (1 넣음)
[ 0 1 2 ]       → MISS (7 out, 가장 오래 사용 X)
[ 0 1 2 ]       → HIT  (0 사용 → 순서 변경)
[ 1 2 3 ]       → MISS (0 out, 가장 오래 사용 X)
[ 1 3 0 ]       → MISS (2 out)
[ 3 0 4 ]       → MISS (1 out)

---

🖼️ 그림으로 표현 (프레임이 3개일 때):

페이지 요청:       7   0   1   2   0   3   0   4
메모리 상태:
                ┌───┐
           7 →  │ 7 │
                └───┘
                ┌───┐
           0 →  │ 0 │
                └───┘
                ┌───┐
           1 →  │ 1 │
                └───┘
                ┌───┐
           2 →  │ 2 │  (7 out, 가장 오래된 사용)
                └───┘
           0 →  HIT  (0 최근 사용됨 → 순서 재조정)
           3 →  │ 3 │  (0은 최근 사용, 1 out)
           0 →  HIT  (0 최근 사용됨 → 순서 재조정)
           4 →  │ 4 │  (1 out)

---

✅ 페이지 교체 여부 정리

요청	상태	교체 발생	메모리 상태
7	MISS	O	[7]
0	MISS	O	[7, 0]
1	MISS	O	[7, 0, 1]
2	MISS	✅	[0, 1, 2] (7 out)
0	HIT		[0, 1, 2]
3	MISS	✅	[1, 2, 3] (0 out)
0	MISS	✅	[2, 3, 0] (1 out)
4	MISS	✅	[3, 0, 4] (2 out)

→ 총 6번의 페이지 폴트 발생
(이번 예시에서는 FIFO와 동일한 횟수지만, 일반적으로는 LRU가 더 성능이 좋습니다)

---

✅ LRU vs FIFO 핵심 차이

항목	FIFO	LRU
기준	가장 먼저 들어온 순	가장 오랫동안 안 쓴 순
구현 난이도	아주 쉬움 (Queue)	조금 복잡함 (Stack, 시간 기록 필요)
정확도	낮음 (불필요한 페이지 제거 가능성 낮음)	높음 (사용 빈도 기반 교체)
성능	중간~낮음	일반적으로 FIFO보다 좋음

---

필요하시면 코드로 LRU 구현 예시나
FIFO vs LRU vs Optimal 비교까지 정리해드릴 수 있어요.
원하시나요? 😊