LRU(Least Recently Used)

LRU

페이지 교체 알고리즘(페이지 교체 알고리즘 (tistory.com)) 개념 중 하나입니다.

페이지 내에서 가장 오랫동안 사용되지 않은 것을 교체하겠다는 의미를 갖고있는 알고리즘의 한 종류입니다.

이 알고리즘의 가설은 가장 오랫동안 사용되지 않은 것은 앞으로도 사용될 확률이 낮다는 것입니다.

 

LRU를 시각화한 도표

* 페이지 내에 데이터 존재여부는 현재 시간에 필요한 데이터와 이전 시간에 페이지 내에 존재하는 데이터를 비교한 것입니다.

 

시간 4에서 가장 오래 사용되지 않은, 가장 오래 적재되어 있던 0을 3으로 교체합니다. 시간 5에서도 같은 이유로 1을 4로 교체합니다.

시간 6에서는 교체가 아닌 갱신이 이루어집니다. 페이지 내에 3이 이미 존재하고 있고, 가장 최근에 사용된 데이터로 인식이 되게 끔 갱신을 해주어야 합니다. 이 때 갱신은 사용된 시간을 갱신해준다고 생각하면 될 것 같습니다.

시간 6에서 3을 갱신하고 나면 가장 오랫동안 사용되지 않은 것은 2입니다.(사실 갱신하지 않았어도 2이긴 하지만) 해서 시간 7에서 2를 1로 교체합니다.

 

LRU 구현하기 위한 2가지 방법

1. 페이지에 저장되어 있는 데이터가 언제 사용되었는지 시간 텀을 체크할 수 있는 부분을 구현하는 것입니다.
2. 큐(FIFO)를 이용하여, 페이지에 저장되어 있는 데이터일 경우 큐에서 끄집어 내어 큐의 맨 뒤로 보내고, 저장되어 있지 않은 데이터일 경우 바로 큐의 맨 뒤로 넣고 맨 앞의 데이터를 삭제시키는 형식으로 구현하는 것입니다.

 

관련 알고리즘 문제 : 코딩테스트 연습 - [1차] 캐시 | 프로그래머스 (programmers.co.kr)