LRU(Least Recently Used) 알고리즘

페이지 교체 알고리즘

cpu가 계산을 할 때 필요한 데이터가 페이지에 있다면 cache hit라고 부르며, 없을 경우 보조기억장치로부터 데이터를 페이지로 옮겨온 후 계산을 하는데 이는 cache miss라고 부른다. 두 경우 시간이 차이 나기 때문에 보다 빠른 연산을 위해서 페이지의 여러 정보 중 어느 정보를 오래 저장해 놓는지가 매우 중요하다. 이렇게 한정된 자원 내에서 최고의 효율을 얻기 위한 알고리즘을 페이지 교체 알고리즘이라고 한다.

페이지 교체 알고리즘의 종류는 다음과 같다.

  • FIFO(First-In-First-Out)
  • OPT(OPTimal Page Replacement)
  • LRU(Least Recently Used)
  • Count-Based
  • LFU(Least Frequently Used)
  • MFU(Most Frequently Used)

LRU 이론

LRU 알고리즘은 가장 최근에 사용되지 않은 페이지를 제거하는 알고리즘이다. 이 알고리즘의 기본 가설은 가장 오랫동안 사용하지 않은 데이터는 앞으로도 사용할 확률이 적다는 것이다. 알고리즘의 구현하는 첫 번째 방법은 페이지에 저장된 데이터가 언제 사용되었는지를 알 수 있게하는 부분을 구현해 가장 오랫동안 참조되지 않은 페이지를 제거하는 방법이다. 두 번째 방법은 페이지에 데이터를 Queue 형식으로 저장하는 방법이다. 페이지 내에 필요한 데이터가 존재하면 페이지 내에서 제거하고 맨 위로 올리고, 존재하지 않는다면 바로 입력하여 맨 아래 데이터를 제거하는 과정을 구현한다.

Reference