페이지 교체 알고리즘 알아보기 FIFO OPT LRU LFU NUR 예제

페이지 교체 알고리즘은 메모리에서 페이지 폴트가 발생할때 메모리가 전부 차있을경우 어떤 페이지를 제거하고 새로운 페이지를 집어넣을지 결정하는 알고리즘입니다.

FIFO (First-In-Fisrt-Out)

FIFO 알고리즘은 메모리에 가장 먼저 들어온 페이지를 먼저 교체하는 알고리즘입니다.

큐(QUEUE)의 자료구조를 사용하며 구현이 간단하고 이해하기 쉽습니다.
다만 자주 사용하는 페이지도 오래되었다는 이유로 교체되어 성능이 떨어질 수 있습니다.

• 프레임 수: 3
• 페이지 참조열: 7, 0, 1, 2, 0, 3, 0, 4, 2, 3

순서	참조 페이지	프레임 상태 (최신이 오른쪽)	페이지 폴트 발생 여부
1	7	7	✅
2	0	7, 0	✅
3	1	7, 0, 1	✅
4	2	0, 1, 2	✅ (7 교체)
5	0	0, 1, 2
6	3	1, 2, 3	✅ (0 교체)
7	0	2, 3, 0	✅ (1 교체)
8	4	3, 0, 4	✅ (2 교체)
9	2	0, 4, 2	✅ (3 교체)
10	3	4, 2, 3	✅ (0 교체)

• 총 페이지 폴트 횟수: 9
• 페이지 폴트율: 9 / 10 × 100 = 90%

---

OPT (Optimal)

OPT 알고리즘은 미래에 가장 오랫동안 사용되지 않을 페이지를 교체합니다

이론적으로는 optimal 알고리즘이 가장 적은 페이지 폴트를 발생하는 알고리즘이며 미래의 페이지 패턴을 알아야하므로 실제로 구현이 불가능하고 다른 알고리즘을 평가하는 기준으로 사용됩니다.

• 프레임 수: 3
• 페이지 참조열: 7, 0, 1, 2, 0, 3, 0, 4, 2, 3

순서	참조 페이지	프레임 상태 (왼쪽=오래된, 오른쪽=최신)	페이지 폴트 발생 여부
1	7	7	✅
2	0	7, 0	✅
3	1	7, 0, 1	✅
4	2	2, 0, 1	✅
5	0	2, 0, 1
6	3	2, 0, 3	✅
7	0	2, 0, 3
8	4	4, 0, 3	✅
9	2	4, 0, 2	✅
10	3	4, 3, 2	✅

• 총 페이지 폴트 횟수: 7
• 페이지 폴트율: 7 / 10 × 100 = 70%

---

LRU (Least Recently Used)

LRU 알고리즘은 가장 오랫동안 사용되지 않은 페이지를 교체합니다. 

최근에 사용한 페이지는 가까운 미래에도 사용할 가능성이 높다는 논리를 기반으로 하는 알고리즘이며 fifo보다 폴트율이 낮고 실제 사용패턴을 잘 반영합니다. 단 각페이지의 사용시간을 추적하기에 구현이 복잡합니다.

• 프레임 수: 3
• 페이지 참조열: 7, 0, 1, 2, 0, 3, 0, 4, 2, 3

순서	참조 페이지	프레임 상태 (왼쪽=오래된, 오른쪽=최근 사용)	페이지 폴트 발생 여부
1	7	7	✅
2	0	7, 0	✅
3	1	7, 0, 1	✅
4	2	0, 1, 2	✅
5	0	1, 2, 0
6	3	2, 0, 3	✅
7	0	2, 3, 0
8	4	3, 0, 4	✅
9	2	0, 4, 2	✅
10	3	4, 2, 3	✅

• 총 페이지 폴트 횟수: 8
• 페이지 폴트율: 8 / 10 × 100 = 80%

---

LFU (Least Frequently Used)

LFU 알고리즘은 가장 적게 사용된 페이지를 교체합니다.

각 페이지마다 참조 횟수를 저장하고 그 횟수를 참고해 교체를 하여 자주사용되는 페이지가 메모리에 유지되게 하지만 많이 사용했다 더이상 필요없는 페이지가 남아있을 수 있습니다.

• 프레임 수: 3
• 페이지 참조열: 7, 0, 1, 2, 0, 3, 0, 4, 2, 3

순서	참조 페이지	프레임 상태 (왼쪽=오래된, 오른쪽=최신)	사용 횟수(괄호)	페이지 폴트	교체된 페이지
1	7	7	(7:1)	✅	-
2	0	7, 0	(7:1, 0:1)	✅	-
3	1	7, 0, 1	(7:1, 0:1, 1:1)	✅	-
4	2	0, 1, 2	(0:1, 1:1, 2:1)	✅ (7 교체)	7
5	0	0, 1, 2	(0:2, 1:1, 2:1)		-
6	3	0, 2, 3	(0:2, 2:1, 3:1)	✅ (1 교체)	1
7	0	0, 2, 3	(0:3, 2:1, 3:1)		-
8	4	0, 3, 4	(0:3, 3:1, 4:1)	✅ (2 교체)	2
9	2	0, 3, 2	(0:3, 3:1, 2:1)	✅ (4 교체)	4
10	3	0, 3, 2	(0:3, 3:2, 2:1)		-

 

• 총 페이지 폴트 횟수: 7
• 페이지 폴트율: 7 / 10 × 100 = 70%

---

NUR (Not Used Recently)

NUR알고리즘은 LRU의 근사 알고리즘이며 최근에 사용하지 않은 페이지를 교체하는 방식입니다.
LRU와 LFU의 공간 낭비를 해결하기 위해 개발했습니다.

NUR은 각페이지를 참조비트와 변형비트의 두가지 비트를 사용해 4가지 클래스로 분류 합니다. 

참조비트(R) : 페이지 접근시 1로변환 시간(틱) 마다 0으로 초기화
변형비트(M) : 페이지가 변경 되면 1로 변환 시간마다 초기화되지 않음

4가지 클래스 구분

클래스	R	M	의미
0	0	0	최근에 사용되지 않고 수정도 안됨
1	0	1	최근에 사용되지 않았지만 수정됨
2	1	0	최근에 사용됨, 수정되지 않음
3	1	1	최근에 사용됨, 수정됨

 

• 프레임 수: 3
• 페이지 참조열: 7, 0, 1, 2, 0, 3, 0, 4, 2, 3

순서	참조 페이지	프레임 상태 (왼쪽=오래된, 오른쪽=최신)	(R, M) 상태	페이지 폴트	교체된 페이지
1	7	7	(1,0)	✅	-
2	0	7, 0	(7:(1,0), 0:(1,0))	✅	-
3	1	7, 0, 1	(7:(1,0), 0:(1,0), 1:(1,0))	✅	-
4	2	0, 1, 2	(0:(1,0), 1:(1,0), 2:(1,0))	✅ (7 교체)	7
5	0	0, 1, 2	(0:(1,0), 1:(0,0), 2:(0,0))		-
6	3	0, 2, 3	(0:(1,0), 2:(0,0), 3:(1,0))	✅ (1 교체)	1
7	0	0, 2, 3	(0:(1,0), 2:(0,0), 3:(1,0))		-
8	4	0, 3, 4	(0:(0,0), 3:(1,0), 4:(1,0))	✅ (2 교체)	2
9	2	0, 3, 2	(0:(1,0), 3:(0,0), 2:(1,0))	✅ (4 교체)	4
10	3	0, 3, 2	(0:(1,0), 3:(1,0), 2:(1,0))		-

 

 

• 총 페이지 폴트 횟수: 7
• 페이지 폴트율: 7 / 10 × 100 = 70%

---

이로써 페이지 교체 알고리즘의 예제를 통해서 기초개념과 같이 알아봤습니다.