[정보처리기사] 페이지 교체 알고리즘, FIFO(선입선출) 문제 풀이

📌 문제

다음의 페이지 참조 열(Page reference string)에 대해 페이지 교체 기법으로 선입선출 알고리즘을 사용할 경우 페이지 부재(Page Fault) 횟수는? (단, 할당된 페이지 프레임 수는 3이고, 처음에는 모든 프레임이 비어 있다.)

 

<페이지 참조 열>
7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0

 

① 13

② 14

③ 15

④ 20

---

🤔 FIFO(First In First Out)란?

"가장 먼저 들어온 페이지를 가장 먼저 교체"

• 선입선출 방식
• 페이지가 메모리에 들어온 순서만 고려
• 구현이 가장 간단한 페이지 교체 알고리즘

---

📝 단계별 상세 풀이

핵심: 큐(Queue) 구조로 관리 [가장 오래된 → → → 가장 최근]

단계참조프레임 상태설명페이지 부재

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	[0, 1, 2]	0이 이미 있음	❌
6	3	[1, 2, 3]	가장 오래된 0을 제거, 3 삽입	✅ (5)
7	0	[2, 3, 0]	가장 오래된 1을 제거, 0 삽입	✅ (6)
8	4	[3, 0, 4]	가장 오래된 2를 제거, 4 삽입	✅ (7)
9	2	[0, 4, 2]	가장 오래된 3을 제거, 2 삽입	✅ (8)
10	3	[4, 2, 3]	가장 오래된 0을 제거, 3 삽입	✅ (9)
11	0	[2, 3, 0]	가장 오래된 4를 제거, 0 삽입	✅ (10)
12	3	[2, 3, 0]	3이 이미 있음	❌
13	2	[2, 3, 0]	2가 이미 있음	❌
14	1	[3, 0, 1]	가장 오래된 2를 제거, 1 삽입	✅ (11)
15	2	[0, 1, 2]	가장 오래된 3을 제거, 2 삽입	✅ (12)
16	0	[0, 1, 2]	0이 이미 있음	❌
17	1	[0, 1, 2]	1이 이미 있음	❌
18	7	[1, 2, 7]	가장 오래된 0을 제거, 7 삽입	✅ (13)
19	0	[2, 7, 0]	가장 오래된 1을 제거, 0 삽입	✅ (14)

📊 결과 분석

페이지 부재 발생 횟수

• 초기 삽입: 7, 0, 1 → 3회
• 교체 발생: 2, 3, 0, 4, 2, 3, 0, 1, 2, 7, 0 → 11회
• 총 페이지 부재: 14회

페이지 적중률

• 총 참조: 19회
• 페이지 부재: 14회
• 페이지 적중: 5회
• 적중률: 5/19 = 약 26.3%

---

🎯 정답: ② 14

설명: FIFO 알고리즘을 적용한 결과, 총 14번의 페이지 부재가 발생합니다.

---

💡 핵심 포인트

1. FIFO는 들어온 순서대로 나가는 단순한 구조
2. 페이지 사용 빈도를 고려하지 않음
3. 구현은 쉽지만 성능이 항상 좋지는 않음
4. Belady's Anomaly가 발생할 수 있는 알고리즘