[운영체제] 페이지 교체 알고리즘 - FIFO, OPT, LRU, NRU, LFU, MFU

페이지 교체 알고리즘

필요한 페이지가 메모리에 없을 때 페이지 부재(page fault)가 발생하면 요청된 페이지를 디스크에서 메모리로 읽어와야 한다. 이때, 물리 메모리에 빈 프레임이 존재하지 않는다면 물리 매모리 내 페이지 중 하나를 선택해서 디스크의 스왑 영역을 보내야 한다.(Swapping) 이를 페이지 교체라고 한다. 메모리 내 페이지 부재율을 최소하하기 위한 목적으로 디스크의 스왑 영역으로 보낼 페이지를 결정하는 알고리즘을 페이지 교체 알고리즘이라고 한다.

 

FIFO(First In First Out)

• 가장 먼저 메모리에 올라온 페이지를 가장 먼저 내보내는 알고리즘
• 구현이 간단하지만 페이지의 향후 참조 가능성을 고려하지 않기 때문에 비효율적인 상황이 발생할 수 있음
• 들어온 시간을 저장하거나 올라온 순서를 큐를 이용해 저장
• Belady's Anomaly(FIFO Anomaly) 현상 발생 가능
  • 메모리 증가로 더 많은 프레임을 사용했는데도 페이지 부재 횟수가 오히려 증가하는 이상 현상
  • ex) 페이지 수를 3개에서 4개로 증가시겼음에도 페이지 부재가 더 발생하는 경우가 있음

 

OPT(Optimal)

• 앞으로 가장 오랫동안 사용하지 않을 페이지를 교체하는 알고리즘
• 모든 페이지 교체 알고리즘 중 page-fault 발생이 가장 적어 성능이 좋음
• 프로세스가 앞으로 사용할 페이지를 미리 예측하기 어려워 실제로 사용하는 것은 거의 불가능

 

LRU(Least Recently Used)

• 가장 오랫동안 사용하지 않은 페이지를 교체하는 알고리즘
• 시간 지역성(가까운 미래에 다시 참조된 가능성)을 고려해 가장 오래전에 참조가 이루어진 페이지를 내보냄
• 성능이 좋은 편으로 많은 운영체제가 채택
• 프로세스가 주기억장치에 접근할 때마다 참조된 페이지 시간을 기록해야해 오버헤드 발생 가능

 

NRU(Not Recently Used)

• LRU처럼 가장 최근에 참조되지 않은 페이지를 선택하지만 교체되는 페이지의 참조 시점이 가장 오래되었음을 보장하지 않음
• '클럭 알고리즘'이라고도 함
• 최근에 참조되었음을 의미하는 1과 참조되지 않음을 의미하는 0 참조 비트(Reference Bit)를 조사
  1. 프레임 내의 페이지가 참조될 때 하드웨어에 의해 1로 자동 세팅
  2. 클럭 알고리즘은 한 바퀴 돌았음에도 참조되지 않은 페이지의 참조 비트 값을 0으로 바꾼 후 지나감
  3. 참조 비트가 0인 페이지를 방문하면 해당 페이지를 교체

 

LFU(Least Frequently Used)

• 참조횟수가 가장 적은 페이지를 교체하는 알고리즘
• 교체 대상이 여러 개라면 가장 오랫동안 사용하지 않은 페이지를 교체
• 가장 최근에 불러온 페이지가 교체될 수 있으며, 이에 따른 오버헤드가 발생할 수 있음

 

MFU(Most Frequently Used)

• LFU와 반대로 참조 횟수가 가장 많은 페이지를 교체하는 알고리즘