LRU(Least Recently Used) 캐시 교체 알고리즘이란?

LRU(Least Recently Used) 캐시 교체 알고리즘이란?

LRU(Least Recently Used)는 컴퓨터 시스템에서 메모리 관리와 캐시 교체를 효율적으로 처리하기 위한 캐시 교체 알고리즘입니다.

이 알고리즘은 캐시에서 데이터를 교체해야 할 때, 가장 오랫동안 사용되지 않은 데이터를 제거하는 방식으로 동작합니다.

 

LRU 알고리즘 동작 원리

• 캐시는 한정된 크기만 가지고 있어서, 새로운 데이터가 들어올 때 캐시에 공간이 부족하면 기존 데이터를 제거해야 합니다.
• LRU는 "가장 쵝느에 사용된" 데이터를 우선적으로 유지하고, 가장 오랫동안 사용되지 않은 데이터를 제거하는 방식입니다.
• 즉, 데이터를 캐시에 접근할 때마다 해당 데이터를 "가장 최근에 사용된" 상태로 갱신하고, 새로운 데이터가 들어올 때는 가장 오래된 데이터를 제거합니다.

 

예시

다음은 LRU 알고리즘이 어떻게 동작하는지 캐시 크기가 3인 경우로 예를 들어 설명하겠습니다.

입력 요청: ["A", "B", "C", "D", "B", "A", "E", "F", "B"]

1. "A" 요청:
   • 캐시: []
   • "A"가 캐시에 없으므로 캐시 미스 발생.
   • "A"를 캐시에 추가.
   • 캐시 상태: [A]
2. "B" 요청:
   • 캐시: [A]
   • "B"가 캐시에 없으므로 캐시 미스 발생.
   • "B"를 캐시에 추가.
   • 캐시 상태: [A, B]
3. "C" 요청:
   • 캐시: [A, B]
   • "C"가 캐시에 없으므로 캐시 미스 발생.
   • "C"를 캐시에 추가.
   • 캐시 상태: [A, B, C]
4. "D" 요청:
   • 캐시: [A, B, C]
   • "D"가 캐시에 없으므로 캐시 미스 발생.
   • 캐시가 가득 찼으므로 **LRU에 의해 가장 오래된 "A"**를 제거.
   • "D"를 캐시에 추가.
   • 캐시 상태: [B, C, D]
5. "B" 요청:
   • 캐시: [B, C, D]
   • "B"는 이미 캐시에 있으므로 캐시 히트 발생.
   • "B"는 최근에 사용되었으므로, 캐시 내에서 가장 최근으로 갱신.
   • 캐시 상태: [C, D, B]
6. "A" 요청:
   • 캐시: [C, D, B]
   • "A"가 캐시에 없으므로 캐시 미스 발생.
   • 캐시가 가득 찼으므로 **LRU에 의해 가장 오래된 "C"**를 제거.
   • "A"를 캐시에 추가.
   • 캐시 상태: [D, B, A]
7. "E" 요청:
   • 캐시: [D, B, A]
   • "E"가 캐시에 없으므로 캐시 미스 발생.
   • 캐시가 가득 찼으므로 **LRU에 의해 가장 오래된 "D"**를 제거.
   • "E"를 캐시에 추가.
   • 캐시 상태: [B, A, E]
8. "F" 요청:
   • 캐시: [B, A, E]
   • "F"가 캐시에 없으므로 캐시 미스 발생.
   • 캐시가 가득 찼으므로 **LRU에 의해 가장 오래된 "B"**를 제거.
   • "F"를 캐시에 추가.
   • 캐시 상태: [A, E, F]
9. "B" 요청:
   • 캐시: [A, E, F]
   • "B"가 캐시에 없으므로 캐시 미스 발생.
   • 캐시가 가득 찼으므로 **LRU에 의해 가장 오래된 "A"**를 제거.
   • "B"를 캐시에 추가.
   • 캐시 상태: [E, F, B]

 

Problem Solving 예제

https://jay-din.tistory.com/359

[프로그래머스 2018 KAKAO BLIND RECRUITMENT] [1차] 캐시(Lv.1) - 파이썬(Python)