페이지 교체 전략

• Demand Paging(요구 페이징)
  • 프로그램 실행 시 전체 데이터를 메모리에 올리는 것이 아닌 필요한 것만 메모리에 올려 사용한다. 이때 필요한 페이지를 요구 페이징이라고 한다.
  • 가상 메모리 시스템에서 많이 사용된다.
  • 가상메모리에 데이터 올리고, 실제 필요로하는 요구 페이지를 메인메모리에 올려 사용
• page fault
  
  • CPU가 적재된 페이지 말고 다른 페이지가 필요할 때 page fault(페이지 부재)가 발생한다
  • 이때 보조기억장치에서 해당 페이지를 가져오게 된다.
  • 하지만 메모리가 꽉찼다면 페이지 교체가 이루어줘야한다.
  • 이때 교체가 이루어지는 메모리 페이지를 victim page라고 한다
• Page Reference String
  • 연속된 페이지를 갖는 논리주소를 처리할때는 page fault가 발생하지 않을 것이다.
  • 연속으로 참조하는 인덱스를 제거하여 어떤 순서대로 페이지가 참조되는지 나타내는 String
  • 예를 들어 논리주소가 100,101,103,402,322리고 페이지 크기가 100이라면 페이지 인덱스는 1,1,1,4,3 일 것이다.
  • 이때 100~103은 같은 페이지이기 때문에 page fault가 발생하지 않아 제거하면 1,1,4,3이 될것이다.
• 페이지 교체 전략
  • FIFO 알고리즘
    • 가장 먼저 들어온 페이지를 먼저 교체
    • 장점
      • 이해하기 쉽고, 구현이 쉽다
    • 단점
      • 오래된 페이지라고 항상 불필요한 것은 아니다(초기 변수 등)
      • 처음부터 많이 사용되는 페이지를 교체해 page fault라 자주 발생할 수 있다
      • Belady의 모순 존재
        • 페이지 프레임 수를 증가시켰더니 오히려 페이지 부재가 더 발생하는 모순
  • OPT 알고리즘(Optimal Page Replacement)
    • 앞으로 가장 잘 사용이 되지 않을 페이지를 교체
    • 장점
      • 가장 낮은 페이지 부재 비율을 보인다
    • 단점
      • 잘 사용이 되지 않을 페이지라는 것을 보장할 수 없고 구현이 어렵다
  • LRU 알고리즘(Least Recently Used)
    • 가장 오랫동안 참조하지 않은 페이지 교체
    • 사용할수 있는 알고리즘 중 가장 최적 알고리즘
    • 지역성 기반
  • LFU 알고리즘(Least Frequently Used)
    • 가장 적게한 참조한 페이지 교체
    • 초기에만 많이 사용한 페이지의 경우 교체되지 않을 수도 있음
      • 처음 초기화때 사용한 데이터들 등
• 교체 방식
  • Global
    • 프로세스를 구분하지않고 전체 페이지를 대상으로 victim page를 선정
  • Local
    • 자기 프로세스의 페이지에서만 victim page 선정