2차 기회 알고리즘

2차 기회 알고리즘(Second-Chance algorithm)은 FIFO (페이지 교체 알고리즘)를 개선한 방식으로, 교체 대상 페이지에 기회를 한 번 더 부여하여 최근에 참조된 페이지가 바로 제거되지 않도록 하는 알고리즘이다. 클럭 알고리즘의 이론적 기초가 되며, LRU (페이지 교체 알고리즘)의 근사 형태로 분류된다.

1 개념

기본적으로 FIFO 방식으로 페이지를 제거하되, 페이지마다 참조 비트(reference bit)를 추가로 관리한다. 페이지가 참조되면 참조 비트는 1로 설정된다. 교체 대상 선정 시, 참조 비트가 1인 경우는 제거 대상에서 제외하고 0으로 초기화한 뒤 다시 큐의 뒤로 넣는다. 이를 통해 최근에 참조된 페이지는 제거되지 않고 한 번 더 기회를 얻는다.

2 동작 방식

1. 페이지 요청이 들어오면, 참조된 페이지의 참조 비트를 1로 설정한다.
2. 페이지 폴트가 발생하고 프레임이 가득 찼을 경우:
   1. 큐의 맨 앞 페이지를 확인한다.
   2. 참조 비트가 0이면 → 해당 페이지를 교체한다.
   3. 참조 비트가 1이면 → 참조 비트를 0으로 초기화하고 큐 뒤로 이동시킨다.
3. 교체 대상이 결정될 때까지 위 단계를 반복한다.

3 예시

초기 상태: 프레임 큐 = [A¹, B⁰, C¹] → B는 참조 비트가 0이므로 제거됨 → A와 C는 참조 비트를 0으로 초기화한 후 큐 뒤로 이동

4 장점

• FIFO의 단점을 완화하고 지역성을 어느 정도 반영
• 구현이 간단하고 실제 시스템 적용 가능
• 클럭 알고리즘으로 확장 가능

5 단점

• 참조 비트를 추적해야 하므로 완전한 FIFO보다 오버헤드가 있음
• 정확한 LRU (페이지 교체 알고리즘)는 아님
• 페이지가 많은 경우, 반복 탐색으로 지연이 발생할 수 있음

6 클럭 알고리즘과의 관계

• 클럭 알고리즘은 2차 기회 알고리즘을 원형 큐로 구현한 구조
• 2차 기회 알고리즘은 이론, 클럭 알고리즘은 실제 운영체제에서의 구현 형태

7 같이 보기

• FIFO (페이지 교체 알고리즘)
• 클럭 알고리즘
• LRU (페이지 교체 알고리즘)
• 참조 비트
• 페이지 교체 알고리즘

8 참고 문헌

• Silberschatz, A., Galvin, P. B., & Gagne, G. (2020). Operating System Concepts. Wiley
• Tanenbaum, A. S., & Bos, H. (2014). Modern Operating Systems. Pearson