2차 기회 알고리즘 편집하기

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