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

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

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

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

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

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

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

부재는 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·한국데이터산업진흥원 등 공식 공지를 확인하라. 그림은 설명용 예시 데이터로 그린 개념도이며 실측 데이터가 아니다.