2차 기회 알고리즘(Second-Chance algorithm)은 FIFO (페이지 교체 알고리즘)를 개선한 방식으로, 교체 대상 페이지에 기회를 한 번 더 부여하여 최근에 참조된 페이지가 바로 제거되지 않도록 하는 알고리즘이다. 클럭 알고리즘의 이론적 기초가 되며, LRU (페이지 교체 알고리즘)의 근사 형태로 분류된다.
개념
기본적으로 FIFO 방식으로 페이지를 제거하되, 페이지마다 참조 비트(reference bit)를 추가로 관리한다. 페이지가 참조되면 참조 비트는 1로 설정된다. 교체 대상 선정 시, 참조 비트가 1인 경우는 제거 대상에서 제외하고 0으로 초기화한 뒤 다시 큐의 뒤로 넣는다. 이를 통해 최근에 참조된 페이지는 제거되지 않고 한 번 더 기회를 얻는다.
동작 방식
- 페이지 요청이 들어오면, 참조된 페이지의 참조 비트를 1로 설정한다.
- 페이지 폴트가 발생하고 프레임이 가득 찼을 경우:
- 큐의 맨 앞 페이지를 확인한다.
- 참조 비트가 0이면 → 해당 페이지를 교체한다.
- 참조 비트가 1이면 → 참조 비트를 0으로 초기화하고 큐 뒤로 이동시킨다.
- 교체 대상이 결정될 때까지 위 단계를 반복한다.
예시
초기 상태: 프레임 큐 = [A1, B0, C1] → B는 참조 비트가 0이므로 제거됨 → A와 C는 참조 비트를 0으로 초기화한 후 큐 뒤로 이동
장점
- FIFO의 단점을 완화하고 지역성을 어느 정도 반영
- 구현이 간단하고 실제 시스템 적용 가능
- 클럭 알고리즘으로 확장 가능
단점
- 참조 비트를 추적해야 하므로 완전한 FIFO보다 오버헤드가 있음
- 정확한 LRU (페이지 교체 알고리즘)는 아님
- 페이지가 많은 경우, 반복 탐색으로 지연이 발생할 수 있음
클럭 알고리즘과의 관계
- 클럭 알고리즘은 2차 기회 알고리즘을 원형 큐로 구현한 구조
- 2차 기회 알고리즘은 이론, 클럭 알고리즘은 실제 운영체제에서의 구현 형태
같이 보기
참고 문헌
- Silberschatz, A., Galvin, P. B., & Gagne, G. (2020). Operating System Concepts. Wiley
- Tanenbaum, A. S., & Bos, H. (2014). Modern Operating Systems. Pearson