페이지 교체 알고리즘 FIFO·LRU·OPT 비교와 벨레이디 이상, 프레임이 늘어도 부재가 늘어나는 이유 (정보처리기사)

가상 메모리에서 필요한 페이지가 메모리에 없으면 페이지 부재(page fault)가 일어나고, 빈 프레임이 없으면 어떤 페이지를 내보낼지 정해야 한다. 이 선택 규칙이 페이지 교체 알고리즘이다. 정보처리기사 필기에서는 FIFO·LRU·OPT의 개념을, 실기에서는 참조열을 주고 부재 횟수를 세게 하는 계산 문제로 자주 나온다.

페이지 교체 알고리즘은 메모리가 가득 찼을 때 희생 페이지를 고르는 규칙이다

프레임이 모두 차 있는 상태에서 새 페이지가 필요하면 하나를 내보낸다. 어떤 기준으로 고르느냐에 따라 부재 횟수가 달라진다. 핵심 용어는 페이지 부재, 프레임, 참조열, 희생 페이지, 지역성이다. 좋은 알고리즘은 곧 다시 쓸 페이지를 남기는 쪽이다.

FIFO·LRU·OPT는 무엇을 기준으로 내보낼지가 다르다

알고리즘	교체 기준	장점	한계
FIFO	가장 먼저 들어온 페이지	구현이 단순하고 큐 하나면 된다	자주 쓰는 페이지도 내보낼 수 있고 벨레이디 이상이 생긴다
LRU	가장 오래 전에 사용된 페이지	시간 지역성을 반영해 성능이 좋은 편	참조 시각 기록 비용이 크다
OPT(최적)	앞으로 가장 오래 쓰이지 않을 페이지	부재 횟수가 가장 적다	미래를 알아야 해서 구현 불가, 성능 비교 기준으로 쓴다
LFU	사용 횟수가 가장 적은 페이지	빈도를 반영	오래된 인기 페이지가 남는 문제
클럭(Second Chance)	참조 비트가 0인 페이지를 시계 방향으로 탐색	LRU 근사를 싸게 구현	참조 비트 주기적 초기화 필요

예시: 참조열 12개를 프레임 3개로 처리하면 FIFO는 부재 9번이다

참조열을 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5라 하고 프레임이 3개일 때 FIFO를 따라가 보자. 표의 프레임 열은 왼쪽이 가장 오래된 페이지이다.

순번	참조 페이지	프레임(오래된 것부터)	결과
1	1	1	부재
2	2	1-2	부재
3	3	1-2-3	부재
4	4	2-3-4	부재
5	1	3-4-1	부재
6	2	4-1-2	부재
7	5	1-2-5	부재
8	1	1-2-5	적중
9	2	1-2-5	적중
10	3	2-5-3	부재
11	4	5-3-4	부재
12	5	5-3-4	적중

부재는 9번이다. 같은 참조열을 LRU로 처리하면 10번, OPT로 처리하면 7번이다. LRU가 항상 FIFO보다 낫지는 않다는 점도 여기서 볼 수 있는데, 이 참조열은 곧바로 반복되는 패턴이 없어 LRU에 불리하다. 모든 값은 파이썬으로 검산했다.

프레임을 늘렸는데 부재가 늘어나는 현상을 벨레이디 이상이라 한다

같은 참조열에서 프레임을 4개로 늘리면 FIFO의 부재는 10번으로 오히려 증가한다. LRU는 8번, OPT는 6번으로 줄어든다. FIFO처럼 “프레임이 많을 때의 메모리 상태가 적을 때의 상태를 포함한다”는 성질(스택 성질)이 없는 알고리즘에서 이상이 생길 수 있고, LRU와 OPT는 이 성질이 있어 생기지 않는다.

답안에는 알고리즘 비교와 계산 과정을 표로 함께 보인다

서술형은 페이지 교체의 필요성 → 알고리즘별 기준과 장단점 → 벨레이디 이상 → 실제 시스템의 LRU 근사(클럭, 에이징) 순으로 쓴다. 계산 문제는 프레임 상태를 단계마다 적어 실수를 막는다. 실무와 연결하면, 메모리가 부족해 교체가 너무 자주 일어나면 CPU 이용률이 급락하는 스래싱이 생기는데, 이는 스래싱과 워킹셋·PFF 글에서 다뤘다.

실전 팁으로, 계산 문제에서는 참조열을 한 칸씩 내려가며 프레임 상태를 옆에 써 두고 마지막에 부재 횟수를 센다. 적중한 칸은 LRU에서만 순서가 바뀐다는 점, OPT에서는 이후 참조열을 끝까지 보고 가장 늦게 쓰이거나 다시 쓰이지 않는 페이지를 고른다는 점을 확인하면 대부분의 실수를 막을 수 있다. 부재율은 부재 횟수를 전체 참조 횟수로 나눈 값이며, 이 예시에서 프레임 3개 FIFO는 9/12 = 75%이다.

시험 직전 한 줄 요약

FIFO는 들어온 순서, LRU는 최근 사용, OPT는 미래 참조를 기준으로 교체하며, FIFO에서만 프레임이 늘어도 부재가 늘어나는 벨레이디 이상이 생긴다.

이 글은 학습용 정리이며 실제 시험 문항과 다를 수 있다. 출제 기준은 큐넷·KISA·한국데이터산업진흥원 등 공식 공지를 확인하라. 그림은 설명용 예시 데이터로 그린 개념도이며 실측 데이터가 아니다.