Page Replacement Policy

Page Replacement Policy

[출처] : https://velog.io/@owlsuri/%ED%8E%98%EC%9D%B4%EC%A7%80-%EA%B5%90%EC%B2%B4-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

페이지 교체 정책 (혹은 알고리즘)은
메인 메모리(RAM)을 효율적으로 사용하기 위한
‘가상 메모리’의 기법 중,
어떤 메모리를 RAM에서 내릴지 결정하는 정책 혹은 알고리즘을 말한다

교체 대상을 선택하는 과정 중
시간 및 공간 에 대한 ‘오버헤드’를 생각해야 한다
(DRAM도 느린 편이지만, 하드웨어는 정말 끔찍하게 느리기에,
Page 교체는 가능하면 일어나지 않는 것이 좋다)
(MMU와 TLB 같이 가상 주소 -> 물리 주소 변환에 따른 노력이
Page Fault를 최대한 줄이기 위한 것)
(따라서 기왕 Page Fault가 발생한 경우,
다음 Page Fault의 가능성을 줄이기 위한 정책/알고리즘 인 것)

페이지 교체 알고리즘은 여러가지가 존재하나
분류를 한다면

• 참조 비트를 이용한 알고리즘
  
  • Clock 알고리즘 : 페이지를 원형 큐로 관리하고, 참조 비트를 확인하고 페이지 교체
    
  • Second Chance : Clock 의 변형으로, 추가적인 ‘변형’비트를 이용하여 페이지 교체
    
• 사용 빈도 기반 알고리즘
  
  • LFU (Least Frequently Used) : 가장 적게 참조된 페이지를 교체
    
• 시간 기반 알고리즘
  
  • LRU (Least Recently Used) : 오랫동안 사용되지 않은 페이지를 교체
    
  • FIFO (First in First out) : 가장 먼저 메모리에 들어온 페이지를 교체
    

이외에도 Optimal(최적화)라는 것이 존재하나
항상 최적의 페이지를 교체하는 것은 비현실적이다

FIFO(First In First Out)

가장 먼저 올라온 걸 가장 먼저 내보내는 알고리즘이다

• 장점
  
  • 구현이 쉽다
    (보통 ‘큐’를 이용하여 구현한다)
    
• 단점
  

  • 성능과 거리가 멀다
    (많이 참조되는 페이지를 교체해버릴 수 있음)
    

  • Belady’s Anomarly 현상
    

    페이지의 프레임 수가 늘어나 더 많은 페이지를 참조할 수 있으나
    Page Fault 수는 오히려 늘어난 경우를 말한다
    

LRU (Least Recently Used)

가장 오랫동안 참조되지 않은 페이지를 교체하는 알고리즘이다

• 동작 방식
  

  페이지가 참조될 때마다, 해당 페이지의 참조 시간을 업데이트
  페이지 교체가 필요할 때, 가장 오래전에 참조한 페이지를 교체
  

• 장점
  

  • Page Fault가 일어나지 않을 확률이 증가
    

    오랫동안 참조되지 않은 페이지를 교체하기에
    다음 페이지 참조 시, 데이터가 존재할 확률(Hit rate)이 올라감
    

• 단점
  
  • 구현이 복잡하다
    
  • 모든 페이지의 ‘참조 시간’을 추적하는 것이 ‘무거운 연산’이다
    

LFU (Least Frequently Used)

가장 적게 ‘참조’된 페이지를 교체하는 알고리즘

• 동작 방식
  

  페이지가 참조될 때마다, 해당 페이지의 ‘참조 횟수’를 증가
  페이지 교체가 필요할 때, 가장 낮은 참조 횟수를 가진 페이지를 교체
  

• 장점
  

  • 특정 상황에서 효율적
    

    일부 페이지가 지속적으로 자주 사용된다면 효율적이다
    

• 단점
  

  • 특정 상황에서 비효율적
    

    초기에 자주 참조된 페이지가 그 이후, 잘 사용되지 않으면
    다른 페이지만 자주 바꿔주어
    성능이 급감한다
    (Page Fault가 자주 일어나 성능이 저하되는
    ‘스레싱’ 현상이 발생할 수 있음)
    

LFU는 특정 상황에서만 사용이 고려된다

Clock 알고리즘

FIFO를 개선한 알고리즘으로
페이지 프레임에 ‘참조 비트’를 추가하여
해당 비트를 체크하여 페이지를 참조한다

• 구체적 동작 방식
  

  페이지를 처음 교체할 때, 페이지의 비트를 0으로 한다
  이후, 페이지가 참조될 때마다 페이지의 비트를 1로 설정
  페이지 교체가 필요할 때, 페이비의 비트가 0인 페이지를 찾는다
  원형 큐를 돌며, 모든 페이지의 비트가 1인 경우
  모든 페이지의 비트를 0으로 초기화하고
  다시 한번 0을 찾아 교체한다
  

• 장점
  
  • 간단한 구현 : 구현이 비교적 간단
    
  • 괜찮은 성능 : FIFO에 비하여 좋은 성능을 가지고 단점을 개선함
    
  • 적은 Overhead : 참조 비트만을 체크하기에, 비교적 적은 비용이 든다
    
• 단점
  

  • 최적해가 아닐 수 있음
    

    참조 비트만으로 최적해를 구하지 못할 가능성 존재
    

  • 특정 상황에서 비 효율적일 수 있음
    

    드문드문 사용되는 페이지가 메모리에 계속 남아있어
    메모리 사용 효율을 떨어뜨릴 수 있음
    

Second Chance 알고리즘

Clock 알고리즘의 변형 알고리즘으로
비슷하지만 약간의 변형이 존재함

• 구체적 동작 방식
  

  페이지가 참조될 때마다 참조 비트를 1로 한다
  페이지 교체가 필요할 때, 순환하며 참조 비트를 확인한다
  (이 때, 0이면 교체 대상으로 설정하고, 1이면 0으로 만들고 넘어간다)
  0을 찾을때까지 원형큐를 탐색한다
  

전반적으로 clock 알고리즘과 비슷하나
Second Chance의 경우, 최근 참조된 페이지를 조금 더 오래 유지하는 경향이 있다