15 가상 메모리4

4) 페이지 교체 알고리즘

  * 예시)
   : 페이지 참조열 = 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1
   : 프레임의 수 = 3

4-1) First-In-First-Out (FIFO) Algorithm
  * 메인 메모리에 제일 먼저 올라온 페이지를 Victim(희생양)으로 결정
  * 초기화 코드는 재사용되지 않을 것이라는 전제

  * Page Fault (페이지 부재) : 15회 발생
  * 이상 현상: Belady's Anomaly
      할당되는 프레임의 수가 증가해도 페이지 부재율이 증가하는 현상.

4-2) Optimal Algorithm
  * 앞으로 제일 사용이 늦게될 페이지를 Victim(희생양)으로 결정
  * 앞으로 한참동안 사용이 되지 않는 페이지는 제일 불필요할 것이다.

  * Page Fault (페이지 부재) : 9회 발생
  * 문제점: 미래에 어떤 페이지가 사용될 지 알 수 없다.


4-3) Least Recently Used (LRU) Algorithm
  * 가장 최근에 사용되지 않았던 페이지를 Victim(희생양)으로 결정
  * 통계적으로 최근에 사용되지 않았던 페이지는 앞으로도 사용되지 않을 가능성이 높다.

  * Page Fault (페이지 부재) : 12회 발생

5) 페이지 교체 알고리즘의 비교

6) Global vs Local Replacement
  * Global Replacement
    : 페이지 교체의 대상이 메인 메모리에 있는 모든 페이지를 대상으로 한다.
    : 다른 프로세스의 영향을 받게 되게 된다. 프로세스의 실행이 늦어지거나 빨라질 수 있다.
    : 개별 프로세스의 동작 보다는 시스템 전반의 효율에 중점을 두기 때문에 대형 시스템에서 이용된다.

  * Local Replacement
    : 페이지 교체의 대상이 동일 프로세스의 페이지만 대상으로 한다.
    : 각 프로세스에 할당된 프레임의 수는 변하지 않으며, 프로세스의 상대적인 중요도에 따라 메모리 할당을 조정, 성능개선을 할 수 있다.