[WEEK11] Pintos _ Project3 FIFO / LRU / Clock 알고리즘? Eviction 정책들 파헤치기

FIFO / LRU / CLOCK Algorithm이 뭘까?

• 물리메모리 크기의 제한을 극복하기 위해 나온 다양한 정책들이 있고 그 정책은 아래와 같다.
  
  • FIFO (First in - First out) : 구현이 간단하나 성능이 좋지 않다.
  • 랜덤 (Random) : 운에 따라 성능이 달라진다.
  • 최적조건 (Optimal) : 가장 나중에 접근될 페이지를 교체하는 것이다. 대부분의 경우 가장 성능이 좋다. (콘센트 문제와 유사)
  • LRU (Least Recently Used) : 지역성의 원칙(최근성)에 따르는 것으로 가장 오래 전에 사용하였던 페이지를 교체한다.
  • LFU (Least Frequently Used) : 지역성의 원칙 (빈도수)에 따르는 것으로 가장 적은 빈도로 사용된 페이지를 교체한다.
    
• 메인메모리가 가상메모리에 페이지를 가져놓기 위한 캐시로 여겨진다면 평균 메모리 접근시간(Average Memory Access Time, AMAT)를 계산할 수 있는데 해당 계산식은 아래와 같다.

• 현대 시스템에서는 디스크 접근 비용이 매우 크기 때문에 아주 작은 미스가 발생하더라도 큰 비용이 발생한다.
  따라서 디스크 접근비용을 줄이는 것이 관건이다.

 

• 여러가지 TC를 돌려본 결과 FIFO는 좋지 못한 성능을 보였고 최적조건이나 LRU가 가장 좋은 결과를 보였다.
  (예외적인 상황으로 Sequential Workload에서는 Rand가 좋은 성능을 보였고, FIFO는 최악의 성능을 보여주었다.)

 

• 하지만 LRU의 경우 4KB의 페이지를 4GB의 물리메모리에 올릴 때 백만개의 페이지를 조사해야하고, 이 중 가장 오래 전에 사용된 페이지를 찾는 것은 고비용의 연산이 필요한 상황이다.

 

• 여기서 나온 것이 시계알고리즘 (clock algorithm)으로 최근 사용 유무에 따라 Use Bit (1 : 최근 사용 / 0 : 사용 x) 등을 통해서 0인 페이지를 찾기 위해 순서대로 탐색한다. 이런 알고리즘을 통해서 기존 LRU의 단점을 극복할 수 있었다.
  

 

• Dirty Bit를 사용하는 것은 시계알고리즘을 좀 더 추가 개선하는 것으로 Dirty Bit가 1이라면 무엇인가 써져있다는 상태이다.
  Dirty Bit가 1일 경우 디스크에 다시 갔다와야하기 때문에 연산 비용이 많이 들어서 성능적인 측면을 고려하여서는 위의 Use Bit와 Dirty Bit를 동시에 사용함으로써 조금이라도 비용을 덜 들일 수 있다.
  

 

• 근데 제일 좋은 방법은 그냥 물리 메모리를 늘리는 것임 🤣

 

참고자료

- OSTEP (p.257 ~ 272)