Page Replacement

• Memory 과다 할당 상태 ( Over Allocation of Memory )
  • Multi Programming System에서 메모리 내에 위치한 유저 프로세스의 수가 증가
  • 각 프로그램이 사용하는 페이지(Page)의 수가 많아지면, 물리 메모리(Frame)의 수가 부족
• 해결 방법
  • Page Fault 처리에 Page replacement를 추가
• 정의
  • 메모리에 더 이상 페이지를 추가로 적재할 공간이 없을 경우, 기존에 적재된 페이지 중 하나를 제거(교체)하고, 필요한 페이지를 가져오는 방법
  • 물리 메모리(Frame)에 적재된 페이지를 디스크로 내보내고, 디스크에 저장된 새로운 페이지를 가져와 메모리에 할당

Page Fault with Page Replacement

1. 디스크에서 요구된 Page의 위치를 찾는다.
2. 물리 Memory에서 Free Frame을 찾는다.
3. Free Frame이 있다면 사용한다.
4. 없다면, Page Replacement Alogrithm을 사용 → 교체할 Frame (Victim Frame)을 선택
5. 교체할 Frame을 Disk에 저장하고, Page Table을 변경
6. 요구된 Page를 Free Frame으로 읽어드리고 해당 Page Table을 적절하게 변경한다.
7. User Process를 재시작한다.

Page Replacement 고려 사항

• 각각의 User Process에게 어떻게 Frame을 분배해 줄 것인가
  • Frame Allocation Alogrithm
    • 각 프로세스가 필요한 만큼만 적절히 할당
• Page 교체가 필요할 때, 교체할 Page를 선택하는 방법
  • Page Replacement Algorithm
• Page 교체에 의한 I/O 작업 수행을 최대한 줄이려는 목적

Page Replacement Algorithms

• 목표

  • 가장 낮은 Page Fault 발생 빈도를 가지는 알고리즘

    = 가장 낮은 I/O 작업 횟수를 요구하는 알고리즘

• 가정

  • 세 개의 Frame이 할당
    • Page Fault 발생 빈도 는 Frame의 개수와 반비례
  • Page를 참조하는 순서 : 20번
  • 적재되는 순서
    • 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1
  • 한 번 참조된 페이지는 교체가 일어나기 전까지 물리 메모리에 유지
  • 다시 참조할 때 물리 Memory에 Page가 존재하는 경우에는 Page Fault가 발생하지 않음