FIFO 한계를 보완하는 Second Chance와 Clock 페이지 교체
참조 비트를 이용해 FIFO 페이지 교체의 한계를 줄이는 Second Chance와 Clock 알고리즘의 동작, 변형, 운영 특성을 정리한다.
2026-08-15 · 최초 발행 2025-12-28
FIFO가 최근 사용 정보를 놓치는 지점
FIFO는 먼저 들어온 페이지를 먼저 내보내므로 구현은 단순하다. 그러나 오래 메모리에 있었다는 사실만으로 교체 대상을 정한다. 최근까지 자주 접근된 페이지도 교체될 수 있고, Belady's Anomaly처럼 프레임을 늘려도 페이지 폴트가 늘어날 수 있다.
참조 순서가 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5일 때 FIFO를 적용하면, 프레임이 3개이면 페이지 부재는 9회이고 마지막 상태는 [3, 4, 5]다. 프레임을 4개로 늘리면 페이지 부재는 10회가 되며 마지막 상태는 [1, 2, 3, 4]다. 이처럼 프레임 수 증가가 페이지 부재 증가로 이어지는 현상을 FIFO Anomaly, 또는 Belady's Anomaly라고 부른다.
LRU와 OPT처럼 프레임을 늘릴 때 페이지 부재율 감소를 보장하는 방식은 스택 알고리즘이다. 이들은 프레임 n개에 들어 있는 페이지가 프레임 n+1개의 페이지 집합에 포함되는 포함 속성(Inclusion Property)을 만족한다. 반면 FIFO와 Random 같은 비스택 알고리즘은 이 성질을 보장하지 않으므로 Anomaly가 발생할 수 있다.
Second Chance는 FIFO의 순서를 버리지 않는다. 대신 교체 후보를 확인할 때 참조 비트를 함께 본다. 최근에 사용된 흔적이 있으면 즉시 내보내지 않고 한 번 더 순환할 기회를 준다.
참조 비트는 페이지 접근 시 하드웨어가 1로 설정하며, 운영체제는 이를 주기적으로 0으로 초기화한다. 이 비트는 정확한 접근 순서를 기록하지는 않지만 최근 사용 여부를 판단하는 데 쓸 수 있다.
페이지 폴트에서 후보를 다시 살피는 방식
페이지 폴트가 나면 FIFO 큐의 선두 페이지부터 검사한다.
참조 비트가 1인 페이지는 최근 사용된 것으로 보고 비트를 0으로 바꾼 뒤 큐의 끝으로 보낸다. 이어서 다음 후보를 검사한다. 반대로 참조 비트가 0이면 최근 사용 흔적이 없으므로 해당 페이지를 교체하고 새 페이지를 큐에 넣는다.
1. 참조 비트를 0으로 변경
2. 페이지를 큐의 끝으로 이동
3. 다음 페이지 검사 (Step 2로 복귀)
1. 해당 페이지를 교체
2. 새 페이지를 메모리에 로드
3. 새 페이지를 큐에 추가 (참조 비트 = 1)
참조 문자열로 보는 Second Chance
프레임 수는 3이고 참조 문자열은 A, B, C, A, D, A, B, E, A라고 하자. FIFO 큐의 방향은 다음과 같다.
[head] → [tail]
| 단계 | 참조 | 큐 상태 (참조비트) | 동작 | 폴트 |
|---|---|---|---|---|
| 1 | A | A(1) | 로드 | F |
| 2 | B | A(1) B(1) | 로드 | F |
| 3 | C | A(1) B(1) C(1) | 로드 | F |
| 4 | A | A(1) B(1) C(1) | Hit, 비트 유지 | - |
| 5 | D | D(1) B(0) C(0) | A(1)→A(0)→꼬리, B(0) 교체 | F |
| 6 | A | D(1) A(1) C(0) | Hit, 비트 유지 | - |
| 7 | B | D(0) A(0) B(1) | C(0) 교체 | F |
| 8 | E | E(1) A(0) B(0) | D(0) 교체 | F |
| 9 | A | E(1) A(1) B(0) | Hit, 비트 유지 | - |
이 경우 총 페이지 폴트는 6회다. 같은 참조 문자열에서 순수 FIFO는 7회의 페이지 폴트를 낸다.
| 알고리즘 | 페이지 폴트 |
|---|---|
| FIFO | 7 |
| 2차 기회 | 6 |
참조 비트를 유지하는 방법
참조 비트 설정은 MMU(Memory Management Unit)가 페이지 접근 시 처리하므로 소프트웨어가 매 접근마다 개입할 필요가 없다. 운영체제 쪽에서는 모든 참조 비트를 주기적으로 0으로 초기화해 최근성 정보를 갱신한다.
# 의사 코드
def periodic_reset(interval):
while True:
sleep(interval)
for page in all_pages:
page.reference_bit = 0초기화 주기는 교체 판단에 영향을 준다. 너무 짧으면 모든 페이지가 새것처럼 보이고, 너무 길면 오래된 참조 정보가 누적된다. 원본의 예시처럼 일정 시간 단위를 수백 ms로 둘 수 있다.
참조 비트를 여러 비트로 늘리면 시간 구간별 접근 흔적을 남길 수 있다.
8-bit 예시: 10010011
- 각 비트는 특정 시간 구간의 참조 여부
- 왼쪽에서 오른쪽으로 시간 경과
- 주기마다 오른쪽으로 시프트
N-bit 참조 정보는 LRU 근사를 더 정교하게 만들지만, 메모리 오버헤드와 관리 복잡도가 커지고 하드웨어 지원도 필요하다.
원형 구조로 재삽입을 없앤 Clock
Second Chance는 참조 비트가 1인 페이지를 큐 끝으로 옮긴다. Clock 알고리즘은 이 논리는 유지하되, 페이지를 실제로 재삽입하지 않는다. 프레임을 원형으로 연결하고 Clock Hand만 이동시킨다.
Clock Hand가 가리키는 페이지의 참조 비트가 0이면 그 자리에 새 페이지를 넣고 포인터를 다음 위치로 옮긴다. 비트가 1이면 이를 0으로 바꾸고 포인터를 전진시켜 다음 프레임을 확인한다.
def clock_replacement():
while True:
page = frames[clock_hand]
if page.reference_bit == 0:
# 교체
replace_page(page)
clock_hand = (clock_hand + 1) % num_frames
return
else:
# 2차 기회 부여
page.reference_bit = 0
clock_hand = (clock_hand + 1) % num_frames교체 여부와 관계없이 포인터는 다음 위치로 이동하며, 모듈로 연산으로 원형 구조를 순환한다.
프레임 4개, Clock Hand 위치 0, 참조 문자열 A, B, C, D, A, E, F의 진행은 다음과 같다.
| 참조 | Frame 0 | Frame 1 | Frame 2 | Frame 3 | Hand | 동작 |
|---|---|---|---|---|---|---|
| A | A(1) | - | - | - | 1 | 로드 |
| B | A(1) | B(1) | - | - | 2 | 로드 |
| C | A(1) | B(1) | C(1) | - | 3 | 로드 |
| D | A(1) | B(1) | C(1) | D(1) | 0 | 로드 |
| A | A(1) | B(1) | C(1) | D(1) | 0 | Hit |
| E | A(0)→E(1) | B(1) | C(1) | D(1) | 1 | A(1)→A(0), 교체 |
| F | E(1) | B(0)→F(1) | C(1) | D(1) | 2 | B(1)→B(0), 교체 |
첫 후보의 참조 비트가 0이면 교체 탐색은 O(1)이다. 모든 페이지의 참조 비트가 1이면 한 바퀴를 돌아야 하므로 O(n)이 된다. 추가 메모리는 프레임 수만큼의 참조 비트인 O(n)이고, Clock Hand 자체는 O(1)이다.
FIFO, Second Chance, Clock의 선택 기준
| 특성 | FIFO | 2차 기회 | Clock |
|---|---|---|---|
| 페이지 폴트 | 높음 | 중간 | 중간 |
| 구현 복잡도 | 낮음 | 중간 | 중간 |
| 실행 오버헤드 | 낮음 | 중간 | 낮음 |
| 메모리 오버헤드 | 낮음 | 중간 | 중간 |
| Belady's Anomaly | 발생 | 완화 | 완화 |
| LRU 근사 | 매우 낮음 | 중간 | 중간 |
| 하드웨어 지원 | 불필요 | 필요(참조 비트) | 필요(참조 비트) |
| 적용 사례 | 거의 없음 | 일부 시스템 | Linux 등 |
최근 사용 여부를 반영해야 하지만 정확한 LRU를 유지하는 비용이 부담스러울 때 Second Chance와 Clock이 절충안이 된다. 특히 Clock은 포인터만 이동하므로 선형 큐에서 발생하는 재삽입 비용을 피할 수 있다.
시스템과 버퍼 관리에서의 변형
Linux 커널은 Clock 알고리즘의 변형을 사용하며, Active/Inactive 리스트를 분리하고 다중 비트 참조 정보를 활용해 LRU를 근사한다.
// 간소화된 의사 코드
struct page {
unsigned int flags; // 참조 비트 포함
struct list_head lru; // LRU 리스트 연결
};
void mark_page_accessed(struct page *page) {
if (!PageActive(page) && PageReferenced(page)) {
activate_page(page);
} else if (!PageReferenced(page)) {
SetPageReferenced(page);
}
}데이터베이스 버퍼 관리에서도 Clock 기반 알고리즘이 널리 쓰인다. 이때 더티 비트와 참조 비트를 함께 고려해 쓰기 비용을 포함한 교체 우선순위를 정한다.
- 참조 비트 0 & 더티 비트 0 (최우선 교체)
- 참조 비트 0 & 더티 비트 1
- 참조 비트 1 & 더티 비트 0
- 참조 비트 1 & 더티 비트 1 (최후 교체)
메모리 회수 정책에서는 참조 비트 갱신 주기를 점검해야 한다. 참조 비트를 너무 빠르게 갱신하면 모든 비트가 1이 되고, 너무 느리게 갱신하면 동작이 FIFO와 같아진다. 전체 순회를 피하려면 최대 스캔 횟수를 제한할 수 있으며, 3비트 이상으로 확장해 판단을 더 세분화할 수도 있다. NUMA 환경에서는 로컬과 원격 메모리 접근 비용의 차이도 반영해야 한다.
메모리 압박이 큰 상황에서는 참조 비트를 무시하고 즉시 교체하는 빠른 회수 모드를 쓸 수 있다. 커널 페이지와 사용자 페이지를 분리해 우선순위를 조정하고, 메모리 부족 이전에 배경 회수를 수행하는 방식도 가능하다. 교체 전에 메모리 압축을 시도하는 선택지도 있다.
웹 브라우저 캐시는 수정된 Clock 알고리즘을 사용하면서 페이지 크기와 접근 빈도를 추가로 고려할 수 있다.
수정 비트까지 고려하는 교체 정책
Enhanced Second Chance는 수정 비트(Dirty Bit)를 더해 교체 후보를 세분화한다. 최근 사용되지 않았고 수정도 되지 않은 페이지는 쓰기 없이 내보낼 수 있으므로 우선 교체 대상이 된다.
(0, 0)은 최근 미사용이며 수정되지 않은 상태, (0, 1)은 최근 미사용이지만 수정된 상태다. (1, 0)은 최근 사용됐지만 수정되지 않았고, (1, 1)은 최근 사용됐으며 수정된 페이지다. 이 구분은 쓰기 비용을 고려하고 I/O를 최소화하는 교체 결정에 사용된다.
ARC(Adaptive Replacement Cache)는 Clock 개념을 활용해 빈도와 최근성의 균형을 맞추는 자가 조정 알고리즘이다. IBM 특허로 인해 일부 시스템에서는 사용이 제한된다. NRU(Not Recently Used)는 참조 비트와 수정 비트만 사용하고 참조 비트를 주기적으로 초기화하는, 더 단순한 형태의 정책이다.
근사 알고리즘이 감수하는 비용
Second Chance와 Clock은 최근 사용 정보를 반영해 FIFO의 단점을 줄이고, 단순한 참조 비트만으로 LRU보다 낮은 비용을 유지한다. 실제 시스템에 적용할 수 있고 확장도 가능하다.
대신 정확한 접근 순서를 알 수 없으므로 LRU보다 성능이 낮을 수 있으며, 특정 워크로드에서는 비효율적일 수 있다. 참조 비트 하드웨어 지원과 추가 메모리도 필요하다. 모든 페이지의 참조 비트가 1인 상황에서는 교체 후보를 찾기 위해 한 바퀴를 순회하며 O(n) 시간이 든다.