[CS / OS] 페이지 교체 알고리즘

1. 가상 메모리 (Virtual Memory)

메모리 관리 기법 중 하나로, 실제로 이용 가능한 자원을 추상화하여 사용자들에게 매우 큰 메모리인 것처럼 보이게 만드는 것. 즉, 프로그램에 실제 메모리 주소가 아닌 가상의 메모리 주소를 주는 방식.

• 요구 페이징 기법
  • 당장 실행에 필요한 페이지만 주기억장치에 적재하는 기법
  • Valid-Invalid Bit를 사용하여 관리
• Page Fault
  • 페이지 테이블을 통해 참조하려는 페이지가 valid(1) 즉, 메모리에 존재하면 페이지 테이블을 통해 논리주소에서 물리주소로 접근
  • invalid(0)이면 Page fault 발생

2. 페이지 기법 알고리즘

1. FIFO 
   • 가장 오래된 페이지를 내보내는 알고리즘
   • 구현은 간단하지만 성능이 좋지 않음
2. OPT
   • 앞으로 가장 오랫동안 사용하지 않을 페이지를 교체하는 알고리즘
   • 실제로 구현이 불가능
   • page fault가 가장 적게 발생한다
3. LRU
   • 가장 오랫동안 사용하지 않은 페이지를 교체하는 알고리즘
   • OPT 알고리즘과 비슷한 효과를 낼 수 있어 많은 운영체제가 채택한 알고리즘
   1.  
4. LFU
   • 참조횟수가 가장 적은 페이지를 교체하는 알고리즘
   • 교체 대상이 여러개면 가장 오랫동안 사용하지 않은 페이지 교체
5. MFU
   • 참조횟수가 가장 많은 페이지를 교체하는 알고리즘