LRU (Least Recently Used)
LRU (Least Recently Used)는 캐시 메모리 관리 방법 중 하나로, 가장 오래 참조되지 않은 페이지가 교체되는 알고리즘입니다.
사용된지 오래된 페이지는 앞으로도 사용될 확률이 낮다는 가설에 의해 만들어진 알고리즘입니다.
페이지 교체 알고리즘
페이징 기업으로 메모리를 관리하는 운영체제에서, 페이지 부재가 발생해 새로운 페이지를 할당하기 위해 현재 할당된 페이지 중 어떤 것과 교체할 지 결정하는 방법
쉽게 말하자면,
- 캐시에 값이 존재한다면, 캐시에서 해당 값을 꺼내 사용 후 다시 캐시에 넣습니다.
- 캐시에 값이 존재하지 않아 저장해야 하는데 캐시가 가득 찼다면, 이때 첫번째 값과 교체됩니다.
실행 과정
캐시 사이즈: 4
입력 값: 123245
- 초록색: 새로 입력된 값
- 파란색 테두리: 캐시 위치 업데이트
- 빨간색 테두리: 페이지 교체 발생
시간 4: 캐시에 존재하는 2가 사용되어 마지막 자리로 이동
시간 5: 캐시가 가득 채워짐
시간 6: 오랫동안 사용되지 않은 1이 제거되고 5 삽입
코딩 문제
프로그래머스 - [1차] 캐시 에서 LRU 알고리즘을 이용하고 있으며,
해당 문제의 풀이는 eunsilson - [프로그래머스] [1차] 캐시 (Java)에서 볼 수 있습니다.
