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

페이지 교체 알고리즘

페이지 교체 알고리즘은 가상 메모리에서 페이지 부재(page fault)가 발생했을 때 어떤 페이지를 메모리에서 제거하고 새로운 페이지를 적재할지를 결정하는 알고리즘이다. 페이지 교체 알고리즘의 목표는 페이지 부재가 최소화되고 시스템의 성능이 최적화되도록 하는 것이다.

페이지 교체 알고리즘

• page-out : 메모리에 있는 페이지를 내리는 것
• page-in : 새로운 페이지를 올리는 것
• victim page(희생양 페이지) : 교체되는 페이지

최적(Optimal) 알고리즘

• 앞으로 가장 오랫동안 사용되지 않을 페이지를 교체한다.
• 페이지 부재율을 최소화할 수 있지만, 앞으로 어떤 페이지가 사용될 지 미리 예측할 수 없기 때문에 실제로 구현하기 어렵다.
  
  

FIFO(First-In, First-Out) 알고리즘

• 먼저 들어온 페이지를 먼저 교체한다.
• 페이지의 사용 빈도나 중요도를 고려하지 않는다.
• 최근에 사용된 페이지라도 오래된 페이지일 경우 교체하므로, 캐시 지역성을 고려하지 않는다.
  
  

LRU(Least Recently Used) 알고리즘

• 가장 최근에 사용되지 않은 페이지를 교체한다.
• 페이지의 사용 기록을 유지하여 가장 오랫동안 사용되지 않은 페이지를 찾아 교체한다.
• 페이지 부재율을 상당히 줄일 수 있는 알고리즘이지만, 페이지 사용 기록을 유지하기 위해 추가적인 시스템 자원이 필요하다.
  
  

LFU(Least Frequently Used) 알고리즘

• 페이지 사용 횟수를 계산하여 페이지의 사용 빈도가 가장 낮은 페이지를 교체한다.
• 특정 페이지가 처음에 많이 사용되었다가 나중에 사용되지 않는 경우에는 성능 저하가 발생할 수 있다.
  
  

NRU(Not Recently Used) 알고리즘

• 페이지를 최근에 사용되지 않은 것과 사용된 것으로 나누어 최근에 사용된 페이지 중에서 임의로 교체할 페이지를 선택한다.
• 단순한 구현이 가능하며 LRU에 비해 성능 차이는 있지만, 적은 비용으로 구현할 수 있다.
  
  

MFU(Most Frequently Used) 알고리즘

• 가장 적게 사용된 페이지는 가장 최근에 사용된 페이지였을 가능성이 높으므로 가장 많이 사용된 페이지를 교체한다.
• 초기에 사용 빈도가 높았던 페이지가 나중에는 더 이상 사용되지 는 경우에도 여전히 캐시에 남아 있을 수 있다. 
  
  

페이지 교체 방식

Global 교체

• 메모리 상의 모든 프로세스 페이지에 대해 교체를 수행하는 방식
• 다중 프로그래밍 환경에서 여러 프로세스의 페이지가 동시에 메모리에 올라올 수 있으므로, 전체 페이지에 대해 교체를 수행하는 것이 효율적이다.
  
  

Local 교체

• 자기 프로세스 페이지에서만 교체를 수행하는 방식
• 자기 프로세스 페이지에서만 교체를 수행하면, 교체를 해야 할 때 각각의 프로세스마다 교체를 진행해야 하므로 비효율적이다.