[정보처리기사] 페이지 교체 알고리즘, LRU 알고리즘 문제 풀이

다음은 운영체제 페이지 순서를 참고하여 할당된 프레임의 수가 3개일 때  LRU 알고리즘의 페이지 부재 횟수를 작성하시오.

 

• 프레임 3개 (페이지를 담을 수 있는 공간)
• 페이지 참조 순서: 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1

 

LRU란?

가장 오랫동안 사용하지 않은 페이지를 교체하는 방법

---

풀이 방법

프레임을 [오래된 것 ← → 최근 것] 순서로 관리합니다.

단계별 상세 풀이

단계참조현재 프레임 상태동작페이지 부재

1	7	[7, -, -]	빈 프레임에 7 삽입	✅ (1)
2	0	[7, 0, -]	빈 프레임에 0 삽입	✅ (2)
3	1	[7, 0, 1]	빈 프레임에 1 삽입	✅ (3)
4	2	[0, 1, 2]	가장 오래된 7을 제거하고 2 삽입	✅ (4)
5	0	[1, 2, 0]	0이 있음, 최근 위치로 이동	❌
6	3	[2, 0, 3]	가장 오래된 1을 제거하고 3 삽입	✅ (5)
7	0	[2, 3, 0]	0이 있음, 최근 위치로 이동	❌
8	4	[3, 0, 4]	가장 오래된 2를 제거하고 4 삽입	✅ (6)
9	2	[0, 4, 2]	가장 오래된 3을 제거하고 2 삽입	✅ (7)
10	3	[4, 2, 3]	가장 오래된 0을 제거하고 3 삽입	✅ (8)
11	0	[2, 3, 0]	가장 오래된 4를 제거하고 0 삽입	✅ (9)
12	3	[2, 0, 3]	3이 있음, 최근 위치로 이동	❌
13	2	[0, 3, 2]	2가 있음, 최근 위치로 이동	❌
14	1	[3, 2, 1]	가장 오래된 0을 제거하고 1 삽입	✅ (10)
15	2	[3, 1, 2]	2가 있음, 최근 위치로 이동	❌
16	0	[1, 2, 0]	가장 오래된 3을 제거하고 0 삽입	✅ (11)
17	1	[2, 0, 1]	1이 있음, 최근 위치로 이동	❌
18	7	[0, 1, 7]	가장 오래된 2를 제거하고 7 삽입	✅ (12)
19	0	[1, 7, 0]	0이 있음, 최근 위치로 이동	❌
20	1	[7, 0, 1]	1이 있음, 최근 위치로 이동	❌

페이지 부재 발생 시점

1. 초기 삽입: 7, 0, 1 (3회)
2. 교체 발생: 2, 3, 4, 2, 3, 0, 1, 0, 7 (9회)

---

최종 답

총 페이지 부재 횟수: 12회

---

핵심 포인트

1. 프레임을 [오래된 것 → 최근 것] 순서로 관리
2. 페이지가 이미 있으면 → 맨 뒤(최근)로 이동
3. 새 페이지가 들어오면 → 맨 앞(가장 오래된) 페이지 제거
4. 페이지 부재 = 새로운 페이지가 메모리에 들어올 때만 발생