[운영체제] 캐시 교체 정책

[운영체제] 캐시 교체 정책 & LRU

캐시 교체 정책에 대해 알아보기 전, 캐시에 대한 이해가 필요하신 분들은 아래 게시물을 참고하시면 좋을 것 같습니다.

2022.08.19 - [운영체제] 캐시 (Cache)

 

캐시의 용량은 매우 작기 때문에 캐싱되는 모든 데이터를 다 담아둘수가 없습니다.

 

그래서 새로운 데이터를 캐싱하기 위해서는 불필요한 데이터를 지워줘야 하는데, 불필요한 데이터를 나누는 기준을 캐시 교체 정책이라고 합니다.

캐시 교체 정책

캐시 교체 정책에는 크게 3가지가 있습니다.

 

FIFO (First In First Out)

• Queue 와 같이 가장 먼저 들어간 데이터를 교체
• 구현은 간단하지만 교체가 잦을수도 있음

 

LFU (Least Frequently Used)

• 사용 횟수가 가장 적은 데이터를 교체
• 교체 대상이 여럿이면 LRU 를 따름
• 최근에 적재된 데이터가 교체될 가능성이 있음
• 초반에 집중적으로 쓰이고 이후 쓰이지 않는 데이터가 존재할 수 있음

 

LRU (Least Recently Used)

• 가장 오랫동안 사용되지 않은 데이터 교체
• 가장 구현이 간단하고 보편적인 방식

 

이 중 가장 보편적으로 사용되는 방식인 LRU 에 대해 조금 더 알아보겠습니다.

LRU 동작방식

캐시는 빠른 속도를 제공해야하기 때문에 최대한 낮은 시간복잡도를 가지는 자료구조를 이용해 구현해야합니다.

 

LRU 캐시는 삽입과 삭제 모두 O(1) 의 시간복잡도를 가지는 이중연결리스트를 가지고 구현할 수 있습니다.

 

이중연결리스트

• 새로 캐싱되거나 Hit 하는 데이터는 tail 로
• 가장 오래 사용되지 않은 데이터는 head 로
  • 새로 캐싱되거나 Hit 되는 데이터가 tail 로 계속해서 이동하기 때문에 자연스럽게 가장 오래 사용되지 않은 데이터는 head 가 됨
• 캐시 용량이 부족하면 head 의 캐시를 지우고 tail 에 새로운 캐시를 붙여서 저장
• 새로 캐싱되거나 head 의 데이터가 삭제되는 경우 시간복잡도 O(1)

 

이와 같은 이중연결리스트의 특성을 이용해서 LRU 캐시를 구현할 수 있습니다.

 

하지만 이중연결리스트에서 Hit 되는 데이터를 탐색해야 하는 경우 O(n) 의 시간복잡도를 가지게 된다는 치명적인 단점이 있습니다.

 

그래서 이중연결리스트에 딕셔너리 (해시맵) 를 추가로 사용하여 문제점을 보완할 수 있습니다.

 

 

딕셔너리 (해시맵)

• Key-Value 를 쌍으로 가지는 자료구조로 탐색 시 O(1) 의 시간복잡도를 가짐
• Key 는 절대 중복저장되지 않음
• 딕셔너리에서 Key 들이 이중연결리스트의 각 노드들, 즉 캐시데이터를 가리키게 한다면 탐색 시 O(1) 의 시간복잡도로 개선 가능

참고 링크

https://www.interviewcake.com/concept/java/lru-cache

LRU Cache Data Structure | Interview Cake

https://gengmi.tistory.com/entry/Cache-%EC%BA%90%EC%8B%9C-%EB%8F%99%EC%9E%91%EA%B3%BC-%EC%BA%90%EC%8B%9C-%EA%B5%90%EC%B2%B4-%EC%A0%95%EC%B1%85

[Cache] 캐시 동작과 캐시 교체 정책