[알고리즘] 캐시 교체 알고리즘 - LRU, LFU

이 내용을 다루기 앞서 이전에 포스팅했던 캐시에 대해 읽어보시는 것을 추천드립니다.

쿠키, 캐시, 세션 이란 ? 각 개념들과 차이점에 대해 쉽게 알아보자.

CS면접의 단골 질문인 쿠키, 캐시, 세션에 대해 각 특징과 차이점들에 대해 설명해놓았으므로 도움이 되실 겁니다.

 

캐시가 사용하는 리소스의 양은 무한대가 아니라 제한적이기 때문에, 캐시는 제한된 리소스 내에서 데이터를 빠르게 저장하고 접근할 수 있어야합니다.

그래서 "캐시 교체 알고리즘"으로 어떤 데이터를 버리고 어떤 데이터를 저장할지 결정합니다.

 

• 캐시 교체 알고리즘
  1. FIFO(First in First Out) - 가장 먼저 들어간 캐시를 교체
  2. LRU(Least Recently Used) -  가장 오랫동안 사용되지 않은 캐시를 교체
  3. LFU(Least Frequently Used) - 사용 횟수가 가장 적은 캐시를 교체

---

LRU (Least Recently Used Algorithm)

많은 운영체제가 사용하고 있는 알고리즘으로 가장 좋은 캐시 교체 알고리즘으로 평가되고 있습니다.LRU를 해석하면 가장 최근에 사용된 알고리즘이라는 뜻으로 "메모리에 남아 있는 캐시 중 가장 오래동안 사용되지 않은 캐시를 새로운 캐시로 교체"합니다.

그 이유는 가장 오랫동안 사용하지 않았던 데이터라면 앞으로도 사용할 확률이 적다고 판단하기 때문입니다.

 

LRU를 구현하기 위해서는 n의 크기를 가지는 DoublyLinkedList(or Queue)와 이를 추적하기 위한 n의 크기를 가지는 HashMap이 필요합니다.

 

Cache Hit 와 Cache Miss

Cache Hit : CPU 가 참조하고자 하는 메모리가 캐시에 존재하고 있을 경우

Cache Miss : CPU 가 참조하고자 하는 메모리가 캐시에 존재하지 않을 경우

 

 

---

LFU (Least Frequently Used) 

LFU를 번역하면 "가장 자주 사용되지 않음"이라는 뜻을 가집니다.

이 알고리즘은 해석 그대로 가장 적은 횟수를 참조하는 페이지를 교체합니다.

Queue로 구현가능하며, 각 캐시마다 참조횟수를 알아야하므로 각 캐시마다 카운터(counter)가 필요합니다.