페이지 교체 알고리즘(FIFO, LRU, LFU)

예제 설정 (공통)

• 참조열(reference string): 7, 0, 1, 2, 0, 3
• 프레임 수: 3

결과 요약

알고리즘	페이지 부재 수
FIFO	5
LRU	5
LFU	5

---

1) FIFO (선입선출)

가장 먼저 들어온 페이지를 먼저 내쫓음.

7	0	1	2	0	3
7	7	7	2	2	2
	0	0	0	0	3
		1	1	1	1
O(페이지 교체)	O(페이지 교체)	O(페이지 교체)	O(페이지 교체)		O(페이지 교체)

---

2) LRU (Least Recently Used)

가장 오래 안 쓰인 페이지를 교체(최근성 기반).

7	0	1	2	0	3
7	7	7	2	2	2
	0	0	0	0	0
		1	1	1	3
O(페이지 교체)	O(페이지 교체)	O(페이지 교체)	O(페이지 교체)		O(페이지 교체)

 

---

3) LFU (Least Frequently Used)

가장 사용 빈도가 낮은 페이지 교체. 동률이면 가장 오래 안 쓴 것(LRU)으로 타이브레이크.

7	0	1	2	0	3
7	7	7	2	2	2
	0	0	0	0	0
		1	1	1	3
O(페이지 교체)	O(페이지 교체)	O(페이지 교체)	O(페이지 교체)		O(페이지 교체)