요구페이징

• 프로세스를 메모리에 적재할 때 처음부터 모든 페이지를 적재하지 않고 필요한 페이지만을 메모리에 적재하는 기법

페이지 교체 알고리즘

• 요구 페이징 기법으로 페이지들을 적재하다 보면 언젠가 메모리가 가득 차게 됨

• 이때는 당장 실행에 필요한 페이지를 적재하기 위해 메모리에 적재된 페이지를 보조기억장치로 내보내야 함

• 이를 결정하는 방법이 페이지 교체 알고리즘 → 쫓아낼 페이지를 결정하는 기법

• 일반적으로 페이지 폴트를 가장 적게 일으키는 알고리즘을 좋은 알고리즘으로 평가

• 페이지 교체 알고리즘을 제대로 이해하려면 페이지 폴트 횟수를 알 수 있어야 함

• 페이지 폴트 횟수는 페이지 참조열(page reference string)을 통해 알 수 있음

• 페이지 참조열 == CPU가 참조하는 페이지들 중 연속된 페이지를 생략한 페이지열

• 페이지 교체 알고리즘의 종류는 매우 다양함

• 따라서 아래 두 가지 ‘왜?, ‘무엇?’을 이해하는게 중요

  • 1. 왜 사용하는지?
  • 2. 무엇이 좋은 페이지 교체 알고리즘인지?

1) FIFO 페이지 교체 알고리즘 (First-In-First-Out Page Replacement Algorithm)

• 이름 그대로 메모리에 가장 먼저 올라온 페이지부터 내쫓는 방식
• “오래 머물렀다면 나가라!”

<예제>

Q. 프로세스가 사용할 수 있는 프레임이 3개 있다고 가정하고 페이지 참조열이 아래와 같다