페이지 교체 알고리즘(FIFO · LRU · OPT)Page Replacement Algorithm
페이지 부재가 났는데 빈 프레임이 없을 때, 메모리에 있는 페이지 가운데 내보낼 희생 페이지를 고르는 운영체제의 규칙이다. 들어온 순서(FIFO) · 최근 사용(LRU) · 앞으로의 사용(OPT) 같은 기준으로 고르며, 같은 프레임 수에서 부재가 적을수록 좋은 규칙이다.
1요약
- 페이지 교체 알고리즘은 요구 페이징의 부재 처리 안에서 희생 페이지를 고르는 규칙으로, 1966년 Belady 가 미래를 아는 최적 교체(오늘의 OPT)를 하한으로 세웠고(Belady 1966), 지금 리눅스는 접근 비트로 최근 사용을 어림하는 다세대 LRU(MGLRU) 위에서 페이지를 회수한다(커널 MGLRU 설계 문서).
- 규칙에 따라 같은 참조에도 디스크 읽기 횟수가 갈린다 — 설명용 가정 참조열 12개 · 프레임 3개에서 OPT 는 부재 6번, LRU 7번, FIFO 9번이고, FIFO 는 다른 참조열에서 프레임을 3개에서 4개로 늘리자 부재가 9번에서 10번으로 늘었다(Belady 외 1969 · 직접 실행).
- 교체 규칙이 문제인지는 부재 가운데 처음 보는 페이지가 아닌 것이 얼마인지로 가른다 — 내보냈다가 다시 읽는 부재가 많으면 규칙 · 할당을 보고, 처음 보는 페이지의 부재가 대부분이면 어떤 규칙도 줄일 수 없는 첫 접근이다.
2등장 배경
요구 페이징 기계는 없는 페이지를 쓸 때마다 드럼 · 디스크에서 읽어 오는데, 메모리가 차면 무엇을 내보낼지 정해야 했다. 곧 다시 쓸 페이지를 내보내면 그 페이지를 바로 다시 읽느라 입출력이 계산 시간을 잡아먹었다.
IBM 의 Belady 는 1966년 무작위 · FIFO · 사용 기록을 쓰는 교체를 견주고, 앞으로 가장 늦게 쓸 페이지를 내보내는 MIN 을 어떤 규칙도 넘을 수 없는 기준으로 제시했다(Belady 1966). 1969년 Belady · Nelson · Shedler 는 FIFO 에서 프레임을 늘리면 부재가 오히려 느는 참조열을 보였고(Belady 외 1969), 1970년 Mattson 등은 작은 메모리의 내용이 언제나 큰 메모리의 내용에 포함되는 스택 알고리즘(LRU · OPT)에는 이 일이 없음을 보였다(Mattson 외 1970).
정확한 LRU 는 메모리 접근마다 기록을 고쳐야 해서 운영체제는 하드웨어가 켜 주는 참조 비트로 어림한다. Multics 는 페이지마다 사용 비트를 두고 그 비트로 LRU 를 쉽게 구현한 변형을 썼고(Bensoussan 외 1972 8.5절), 리눅스는 익명 · 파일 페이지를 활성 · 비활성 목록으로 나눠 오다가(커널 unevictable LRU 문서) 접근 시점이 비슷한 페이지를 세대로 묶는 MGLRU 를 더했다(커널 MGLRU 설계 문서).
3쉽게 이해하기 — 공구 주머니 셋과 아래층 공구 차
수리 기사 박 씨의 허리 벨트에는 공구 주머니가 셋뿐이고, 나머지 공구는 아래층에 세운 공구 차에 있다. 작업 지시서대로 공구를 바꿔 쓰다가 주머니에 없는 공구가 필요하면 계단을 내려가 가져와야 하고, 주머니가 꽉 차 있으면 하나를 차에 돌려놓아야 한다. 가장 먼저 넣은 것을 돌려놓을지, 가장 오래 안 쓴 것을 돌려놓을지, 지시서를 넘겨 보고 가장 늦게 쓸 것을 돌려놓을지에 따라 계단을 오르내리는 횟수가 달라진다. 박 씨는 공구를 쓸 때마다 꼬리표를 걸고, 돌려놓을 때는 꼬리표 없는 주머니부터 고른다.
그림 1 · 주머니(프레임)에 없는 공구가 필요할 때만 계단(디스크 입출력)을 오가고, 무엇을 돌려놓을지 고르는 규칙이 교체 알고리즘이다.
그림 2 · 꼬리표가 걸린 주머니는 한 번 봐주고 지나가듯, 클럭의 바늘은 참조 비트가 1 인 프레임의 비트만 0 으로 바꾸고 넘어가 0 인 프레임을 내보낸다.
| 비유 속 역할 | 실제 이름 | 실제로 하는 일 |
|---|---|---|
| 박 기사 | 프로세스 | 참조열 순서대로 페이지를 쓴다 |
| 공구 주머니 셋 | 프레임 3개 | 프로세스가 메모리에 둘 수 있는 페이지 수 |
| 아래층 공구 차 | 디스크 · 스왑 영역 | 메모리에 없는 페이지가 있는 곳 |
| 주머니에 없음 | 페이지 부재 | 디스크 입출력이 일어나는 순간 |
| 차에 돌려놓는 공구 | 희생 페이지 | 교체 알고리즘이 고르고, 수정된 페이지면 먼저 디스크에 쓴다 |
| 작업 지시서 | 앞으로의 참조열 | OPT 만 안다고 가정하며 실제 운영체제는 모른다 |
| 쓸 때 거는 꼬리표 | 참조 비트(접근 비트) | 접근 때 하드웨어가 1 로 켜고 클럭의 바늘이 0 으로 끈다 |
| 마지막으로 쓴 시각 | LRU 의 사용 기록 | 정확히 두려면 접근마다 고쳐야 해서 비트로 어림한다 |
⚠ 비유가 맞지 않는 곳: 박 씨는 꼬리표를 손으로 걸지만 실제 참조 비트는 CPU 의 MMU 가 접근 때 스스로 켜고, 운영체제는 다음에 쓸 페이지를 모르므로 지시서를 넘겨 보는 OPT 는 실제로 돌릴 수 없고 비교 기준으로만 쓴다.
4구조 · 동작 — 참조열 12개를 다섯 규칙으로
교체는 부재 처리 중 빈 프레임이 없을 때만 일어나고, 규칙마다 희생 페이지를 고르는 데 쓰는 기록이 다르다(UIC 강의 노트).
| 알고리즘 | 내보내는 페이지 | 필요한 기록 | 값 · 근거 |
|---|---|---|---|
| FIFO | 가장 먼저 들어온 페이지 | 들어온 순서의 큐 | 구현이 가장 쉽고 벨레이디의 모순이 생긴다(Belady 외 1969) |
| OPT(MIN) | 앞으로 가장 오래 쓰지 않을 페이지 | 앞으로의 참조열 전체 | 부재 수의 하한 · 실제 구현 불가(Belady 1966) |
| LRU | 가장 오래전에 쓴 페이지 | 페이지마다 마지막 사용 시각 또는 스택 | 스택 알고리즘(Mattson 외 1970) · 두 구현 모두 하드웨어 지원 필요(UIC 강의 노트) |
| LFU | 참조 횟수가 가장 적은 페이지 | 페이지마다 횟수 | 예전에 많이 쓴 페이지가 남아 횟수를 주기적으로 오른쪽 시프트해 줄인다(UIC 강의 노트) |
| 클럭(2차 기회) | 바늘이 만난 참조 비트 0 인 페이지 | 프레임마다 참조 비트 1개 + 바늘 | 비트가 1 이면 0 으로 바꾸고 넘어간다(UIC 강의 노트) |
| 개선된 클럭 | (참조, 수정) = (0, 0) 부터 | 참조 비트 + 수정 비트 | 디스크에 쓰지 않고 버릴 수 있는 깨끗한 페이지를 먼저(UIC 강의 노트) |
프로세스 하나에 프레임 3개를 주고 페이지 2 · 3 · 5 · 2 · 1 · 3 · 2 · 1 · 3 · 5 · 1 · 4 를 차례로 참조하는 사례다. 참조열과 프레임 수는 설명용 가정 값이고, 부재 수는 직접 실행 값이다(Python 3.14 로 만든 시뮬레이터 · 동점이면 먼저 들어온 페이지 · LFU 는 내보낼 때 횟수를 지움).
- 참조 1 ~ 3(페이지 2 · 3 · 5)은 빈 프레임에 들어가는 부재 3번이고 참조 4(페이지 2)는 적중이다 — 다섯 규칙이 모두 같다.
- 참조 5(페이지 1)에서 첫 교체가 일어난다 — FIFO · 클럭은 가장 먼저 들어온 2 를, LRU · LFU 는 3 을, OPT 는 다음 사용이 가장 먼 5(참조 10)를 내보낸다.
- 참조 6(페이지 3)에서 LRU · LFU 는 방금 내보낸 3 을 다시 읽는 부재를 낸다 — OPT 는 3 을 남겨 두어 적중이다.
- 참조 7(페이지 2)에서 FIFO 는 가장 먼저 들어온 3 을 내보내지만, 클럭은 참조 6 에서 켜진 3 의 참조 비트를 0 으로 바꾸고 넘어가 비트가 0 인 5 를 내보낸다(그림 2) — 참조 9 에서 FIFO 는 3 을 다시 읽고 클럭은 적중이다.
- 참조 10(페이지 5)에서 OPT 와 LRU 는 둘 다 2 를 내보낸다 — LFU 는 횟수 3 인 2 를 지키느라 1 을 내보내고 참조 11 에서 1 을 다시 읽는다.
- 참조 12(페이지 4)는 처음 보는 페이지라 다섯 모두 부재다 — 처음 보는 페이지 다섯(2 · 3 · 5 · 1 · 4)의 부재 5번은 어떤 규칙도 피하지 못한다.
- 합계는 OPT 6 · LRU 7 · 클럭 8 · LFU 8 · FIFO 9 다 — 프레임을 4개 주면 페이지 다섯 가운데 넷이 늘 남아 다섯 모두 5번으로 같아진다.
그림 3 · 다섯 규칙 모두 처음 보는 페이지의 부재 5번은 같고, 차이는 곧 다시 쓸 페이지를 내보냈는가에서 난다 — OPT 6 · LRU 7 · 클럭 8 · LFU 8 · FIFO 9.
🔑 교체 알고리즘이 줄일 수 있는 것은 «내보냈다가 다시 들어오는» 부재뿐이다 — 처음 보는 페이지의 부재는 OPT 도 피하지 못한다.
벨레이디의 모순(Belady's anomaly)은 FIFO 에서 프레임을 늘렸는데 부재가 느는 현상이다. 참조열 0 · 1 · 2 · 3 · 0 · 1 · 4 · 0 · 1 · 2 · 3 · 4 에서 FIFO 는 프레임 3개면 9번, 4개면 10번 부재가 나고, 같은 참조열에서 LRU 는 10번에서 8번으로 준다(직접 실행). LRU · OPT 는 프레임 n 개일 때 메모리에 있는 페이지 집합이 언제나 n+1 개일 때의 집합에 포함되므로 프레임을 늘려 부재가 늘 수 없다(Mattson 외 1970). 클럭과, 내보낼 때 횟수를 지우는 LFU 는 스택 알고리즘이 아니어서 이 포함 성질이 보장되지 않고 모순이 생길 수 있다 — 같은 참조열의 직접 실행 결과(설명용 가정 값)는 클럭 9번 → 10번으로 늘고, LFU(횟수가 같으면 먼저 들어온 쪽을 내보냄)는 10번 → 8번으로 준다. 이 참조열에서 LFU 가 줄었다고 LFU 가 모순에서 자유롭다는 뜻은 아니다.
그림 4 · FIFO 는 프레임을 3개에서 4개로 늘리자 부재가 9번에서 10번으로 늘고, 같은 참조열에서 LRU 는 10번에서 8번으로 준다 — 4개 쪽이 3개 쪽의 내용을 품지 못하는 순간이 생기기 때문이다.
🔑 FIFO 는 «언제 들어왔나»로 순위를 매겨 큰 메모리가 작은 메모리의 내용을 품는다는 보장이 없고, LRU · OPT 는 «언제 쓰나»로 매겨 그 보장이 있다.
희생 페이지를 그 프로세스의 프레임 안에서만 고르면 지역 교체, 메모리 전체에서 고르면 전역 교체다. 전역 교체에서 프로세스들의 작업 집합 합이 프레임 수를 넘으면 어떤 규칙이든 남이 쓰는 페이지를 내보내게 되고, 작업 집합 모델은 «무엇을 내보낼까»가 아니라 «몇 프레임을 줄까»를 정해 이것을 막는다(Denning 1968 · UIC 강의 노트).
5비교 — 다섯 규칙의 비용과 성질
| 기준 | FIFO | OPT | LRU | LFU | 클럭 |
|---|---|---|---|---|---|
| 사례 부재(프레임 3개) | 9 | 6 | 7 | 8 | 8 |
| 벨레이디 참조열 3개 → 4개(직접 실행 결과 · 설명용 가정 값) | 9 → 10 | 7 → 6 | 10 → 8 | 10 → 8 | 9 → 10 |
| 접근마다 하는 일 | 없음 | 없음(미래를 앎) | 사용 시각 · 스택 갱신 | 횟수 증가 | 하드웨어가 참조 비트를 1 로 |
| 교체 때 하는 일 | 큐 맨 앞을 꺼냄 | 앞으로의 참조열 탐색 | 가장 오래된 시각 찾기 | 가장 적은 횟수 찾기 | 비트 0 을 만날 때까지 바늘 이동 |
| 실제 쓰임 | 비교 기준 · 단순 버퍼 | 부재 하한 비교 | 하드웨어 지원이 있을 때만 정확 | 드묾(UIC 강의 노트) | 운영체제 LRU 근사의 기본 꼴 |
분석운영체제는 메모리 접근마다 소프트웨어가 끼어들 수 없으므로 하드웨어 참조 비트만으로 되는 클럭 계열 · MGLRU 로 LRU 를 어림하고, OPT 는 기록해 둔 참조열로 새 규칙이 하한에서 얼마나 먼지 재는 데만 쓴다. 근거는 표의 「접근마다 하는 일」 행 — 정확한 LRU 는 두 구현 모두 하드웨어 지원이 필요하다(UIC 강의 노트).
6실무 진단 — 다시 읽는 부재 가르기
분석부재가 처음 보는 페이지인지, 내보냈다 다시 들어온 페이지인지부터 가르고, 다시 들어오는 쪽이면 회수가 후보를 얼마나 헛되이 훑는지와 프로세스가 직접 회수에 묶였는지를 본다. 근거는 cgroup v2 문서의 pgscan · pgsteal 정의와 sar(1) 의 pgscand/s 정의다.
| # | 증상 | 의심 원인 | 구분 | 확인 명령 | 판정 기준(근거) |
|---|---|---|---|---|---|
| 1 | 회수는 도는데 메모리가 잘 안 풀림 | 훑은 후보 대부분이 최근에 쓰임 | 교체 | grep -E '^pg(scan|steal) ' / | pgsteal(회수한 페이지)이 pgscan(훑은 페이지)보다 훨씬 작으면 참조된 페이지만 만나는 중(커널 cgroup v2 문서) |
| 2 | 할당에서 프로세스가 자주 멈춤 | kswapd 가 못 따라가 직접 회수 | 회수 | sar -B 1 | pgscand/s 가 0 이 아니면 프로세스가 멈춘 채 직접 스캔(sar(1) · 커널 mm 개념 문서) |
| 3 | 어느 교체 방식인지 모름 | MGLRU 켬 여부 | 설정 | cat / | 0x0001 비트 = MGLRU 주 스위치(커널 MGLRU 문서) |
순서는 스캔 대비 회수 → 직접 회수 → 설정이다. 그룹 하나가 아니라 모든 그룹에서 다시 읽는 부재가 함께 늘고 시스템 전체가 멈추면 규칙이 아니라 작업 집합 합의 문제이므로 스래싱 진단으로 넘긴다.
7시험 대비
www.q-net.or.kr시험에서는 같은 참조열에 FIFO · OPT · LRU 를 적용해 부재 수를 세는 동작 · 절차 설명형과, 규칙들을 견주며 벨레이디의 모순을 설명하게 하는 비교형이 나올 수 있다. 참조열 문제는 열마다 프레임 내용과 부재를 채우고 처음 보는 페이지의 부재를 따로 표시하면, 규칙이 줄일 수 있는 부재만 견줘 보여 다른 답안과 차이가 난다.
- 개요 — 정의 · 희생 페이지 · 부재 처리 안에서 교체가 일어나는 때 · 처음 보는 페이지 부재와 교체 부재의 구분
- 알고리즘 — 구조 표(FIFO · OPT · LRU · LFU · 클럭 · 개선된 클럭의 기준과 필요한 기록)
- 참조열 계산 — 그림 3 격자(참조열 12개 · 프레임 3개 · 부재 9 · 8 · 8 · 7 · 6 · 처음 보는 페이지 5)
- 벨레이디의 모순 — 그림 4(FIFO 9 → 10 · LRU 10 → 8) + 스택 알고리즘의 포함 성질
- 비교 · 실제 구현 — 비교표(접근마다 하는 일 · 참조 비트) + 작업 집합 · 스래싱과의 관계 · 리눅스 MGLRU
꼭 쓸 키워드
페이지 부재희생 페이지FIFOOPTLRULFU클럭참조 비트벨레이디의 모순스택 알고리즘
8오해와 사실
- 오해LRU 는 언제나 FIFO 보다 부재가 적다.사실참조열 0 · 1 · 2 · 3 · 0 · 1 · 4 · 0 · 1 · 2 · 3 · 4 에 프레임 3개면 FIFO 9번 · LRU 10번으로 LRU 가 더 많다(직접 실행) — LRU 가 보장하는 것은 프레임을 늘릴 때 부재가 늘지 않는다는 성질이다(Mattson 외 1970).
- 오해OPT 는 미래를 알아야 하니 쓸모가 없다.사실OPT 는 같은 참조열에서 어떤 규칙도 넘을 수 없는 부재 하한이라, 기록한 참조열로 새 규칙이 하한에서 얼마나 먼지 재는 기준이 된다(Belady 1966).
- 오해리눅스는 정확한 LRU 목록 순서대로 페이지를 내보낸다.사실리눅스는 페이지 테이블의 접근 비트를 훑어 세대를 매기고 가장 오래된 세대부터 회수하며, MGLRU 문서는 젊은 · 늙은 세대를 활성 · 비활성 목록에 대응시켜 설명한다(커널 MGLRU 설계 문서).
9핵심 정리
| 규칙 | 내보내는 기준 | 보는 정보 | 필요한 기록 | 사례 부재(프레임 3개) | 프레임을 늘릴 때 |
|---|---|---|---|---|---|
| FIFO | 먼저 들어온 것 | 과거 · 적재 순서 | 큐 | 9 | 부재가 늘 수 있음(벨레이디의 모순) |
| OPT | 가장 늦게 쓸 것 | 미래 · 참조열 | 참조열 전체 | 6 | 늘지 않음(하한) |
| LRU | 가장 오래 안 쓴 것 | 과거 · 마지막 사용 | 사용 시각 · 스택 | 7 | 늘지 않음(스택 알고리즘) |
| LFU | 가장 적게 쓴 것 | 과거 · 사용 횟수 | 횟수 | 8 | 늘 수 있음(스택 알고리즘 아님 · 직접 실행 결과 10 → 8 · 설명용 가정 값) |
| 클럭 | 바늘이 만난 R=0 | 최근 한 바퀴 | 참조 비트 + 바늘 | 8 | 늘 수 있음(스택 알고리즘 아님 · 직접 실행 결과 9 → 10 · 설명용 가정 값) |
| 개선된 클럭 | (R, M) = (0, 0) 먼저 | 최근 사용 + 수정 여부 | 참조 · 수정 비트 | — | 쓰기 비용을 줄임 |
| 작업 집합 | 교체가 아니라 할당 | 최근 창의 참조 | 참조 시각 | — | 프레임 수 자체를 정함 |
10참고 문헌
- 먼저 볼 문헌
- ★ Operating Systems: Virtual Memory (Course Notes · Operating System Concepts Ninth Edition Chapter 9 기반) — FIFO · OPT · LRU · 2차 기회 · LFU 를 같은 참조열로 견주는 교과서 설명을 볼 때
- ★ A Study of Replacement Algorithms for a Virtual-Storage Computer — 미래를 아는 최적 교체(MIN · 오늘의 OPT)를 하한으로 둔 원문을 볼 때
- ★ An Anomaly in Space-Time Characteristics of Certain Programs Running in a Paging Machine — FIFO 에서 프레임을 늘리면 부재가 느는 현상(벨레이디의 모순)의 원문을 볼 때
- ★ Multi-Gen LRU (Design doc) — 리눅스가 접근 비트로 세대를 매겨 가장 오래된 세대부터 회수하는 방식을 볼 때
- 본문 근거
- Evaluation Techniques for Storage Hierarchies — R. L. Mattson · J. Gecsei · D. R. Slutz · I. L. Traiger · IBM Systems Journal 9(2) 78-117 · 1970-06 ·
doi.org/10.1147/sj.92.0078· 확인 2026-11-18 - Multi-Gen LRU (Admin guide · enabled · min_ttl_ms) — The Linux Kernel documentation · 2026-11 ·
docs.kernel.org/admin-guide/mm/multigen_lru.html· 확인 2026-11-18 - Unevictable LRU Infrastructure — The Linux Kernel documentation · 2026-11 ·
docs.kernel.org/mm/unevictable-lru.html· 확인 2026-11-18 - Concepts overview (Memory Management · Reclaim) — The Linux Kernel documentation · 2026-11 ·
docs.kernel.org/admin-guide/mm/concepts.html· 확인 2026-11-18 - Control Group v2 (memory.stat) — The Linux Kernel documentation · 2026-11 ·
docs.kernel.org/admin-guide/cgroup-v2.html· 확인 2026-11-18 - sar(1) Linux manual page — man7.org · 2026-11 ·
man7.org/linux/man-pages/man1/sar.1.html· 확인 2026-11-18 - The Multics Virtual Memory: Concepts and Design (Communications of the ACM 15(5)) — A. Bensoussan · C. T. Clingen · R. C. Daley · multicians.org 게재본 · 1972-05 ·
multicians.org/multics-vm.html· 확인 2026-11-18 - The Working Set Model for Program Behavior — P. J. Denning · Communications of the ACM 11(5) 323-333 · 1968-05 ·
doi.org/10.1145/363095.363141· 확인 2026-11-18