문제
참조 문자열이 A, B, C, D, A, E, F, A, B, C 일 때, 페이지 프레임 4개를 가진 시스템에서 OPT(Optimal) 알고리즘을 적용했을 때 발생하는 페이지 부재(Page Fault) 횟수를 쓰시오.
정답
6
6
해설
OPT 알고리즘은 앞으로 가장 늦게 다시 사용되거나, 앞으로 전혀 사용되지 않을 페이지를 교체한다. 트레이싱:
- A✗ → [A]
- B✗ → [A, B]
- C✗ → [A, B, C]
- D✗ → [A, B, C, D]
- A○ → [A, B, C, D]
- E✗: 이후 참조는 F, A, B, C 이므로 다시 쓰이지 않는 D를 교체 → [A, B, C, E]
- F✗: 이후 참조는 A, B, C 이므로 다시 쓰이지 않는 E를 교체 → [A, B, C, F]
- A○, B○, C○ 따라서 페이지 부재는 총 6번 발생한다.