정답
첫 번째 페이지 교체 프레임 번호: 1, 65번 페이지 적재 직후 해당 프레임의 페이지 교체 횟수: 2, 최종 프레임 상태: (0,0,23), (1,1,89), (2,0,17), (3,0,25), (4,0,51)
출제 의도
2차 기회 페이지 교체 알고리즘에서 참조 비트(ref_bit) 갱신 규칙과 프레임 포인터 이동 규칙을 적용하여, 참조열에 따른 페이지 폴트 발생 시 교체 프레임 선택 과정과 최종 프레임 구성을 정확히 추적하는지를 평가한다.
풀이 과정
초기 프레임 상태는 (프레임 번호: [참조 비트, 페이지])로 0:[1,23], 1:[0,43], 2:[0,17], 3:[1,33], 4:[1,51]이고 프레임 포인터는 3번 프레임을 가리킨다.
페이지가 메모리에 있으면 해당 프레임의 참조 비트를 1로 만든다. 페이지가 없으면(페이지 폴트) 포인터가 가리키는 프레임부터 2차 기회 알고리즘을 수행하여, 참조 비트가 0인 프레임을 만날 때 그 참조 비트를 1로 바꾸고 그 프레임을 교체 대상으로 선택한다. 교체가 일어나면 프레임 포인터는 방금 교체된 프레임을 가리킨다.
첫 참조 73은 페이지 폴트이므로 포인터(프레임 3)에서 시작한다. 프레임 3,4,0은 참조 비트가 1이어서 각각 0으로 바꾸며 넘어가고, 프레임 1이 참조 비트 0이므로 여기서 참조 비트를 1로 바꾸고 교체 대상으로 선택된다. 따라서 첫 교체는 1번 프레임에서 일어난다.
이후 65가 처음 적재될 때도 페이지 폴트가 발생하며, 알고리즘을 적용하면 다시 1번 프레임이 교체 대상으로 선택되어 65가 적재된다. 1번 프레임은 기존(43→73) 1회 교체가 이미 있었고, (73→65)로 1회가 추가되어 총 2회 교체가 된다.
남은 참조들을 같은 방식으로 추적하면 마지막 참조 89에서 다시 페이지 폴트가 발생하고, 순환하며 참조 비트를 0으로 내린 뒤 1번 프레임이 선택되어 89가 적재된다. 최종적으로 프레임들의 상태는 다음과 같다.
$$ [0,0,23],\ [1,1,89],\ [2,0,17],\ [3,0,25],\ [4,0,51] $$
<풀이가 부정확할 수 있으니 반드시 교차검증 확인 바랍니다.>