[Algorithm] LRU(Least Recently Used) 알고리즘

 

INTRO

---

페이지 교체 알고리즘에는 다양한 알고리즘이 있다.

FIFO, LFU, Count-Base ...

이 중 LRU 알고리즘에 대해 소개한다.

 

---

 

1. LRU 알고리즘이란?

◆ 가장 오랜 시간 사용되지 않은 페이지를 교체하는 운영체제의 페이지 교체 정책 알고리즘이다.

◆ 주로 캐시에서 메모리를 다루기 위해 사용된다.

◆ 캐시는 크게 보면 웹 서비스부터, 작게는 CPU가 RAM이나 Disk에 접근할 때.. 등 광범위하게 사용됨.

◆ 이러한 캐시들은 자원이 한정되어있으며, 한정된 자원 내에서 빠르게 데이터 접근이 가능해야 한다.

◆ 따라서 어떤 데이터를 남기고, 어떤 데이터를 지울지에 대한 알고리즘이 필요.

◆ 여기서 오래 참조되지 않은 데이터는 내보내는 '시간(temporal) 지역성'의 성질을 가지는 알고리즘이다.

 

◆ LRU는 아래와 같은 장/단점을 가진다.

 

장점

- 빠른 액세스

가장 최근에 사용한 아이템부터 가장 적게 사용한 아이템까지 정렬된다.

따라서 두 아이템에 접근할 경우, O(n)의 시간 복잡도를 가진다.

 

- 빠른 Update

하나의 아이템에 엑세스 할때마다 업데이트 되며, O(n)의 시간 복잡도를 가진다.

 

단점

- 많은 공간 차지

n개의 아이템을 저장하는 LRU는 n의 크기를 가지는 1개의 Linked-list와(혹은 Queue) 이를 추적하기 위한 n의 크기를 가지는 1개의 hash-map이 필요하다.

이는 O(n)의 복잡도를 가지지만, 2개의 데이터구조를 사용해야 한다는 단점이 있다.

 

---

 

 

 

 

 

2. 예시

◆ 아래와 같은 3개의 공간을 가진 Queue가 있다.

 

◆ 1 -> 2 -> 3을 차례로 삽입(put)했을 경우

 

 

◆ 2를 참조(get)한 경우

 

◆ 4를 put 한 경우

 

---

 

 

 

3. 예제 소스(C++ STL)

◆ 예제 소스는 아래 링크에서 참조하였다.

◆ 주석 부분을 참고하면 좋을 듯 하다.

 

 

https://www.geeksforgeeks.org/lru-cache-implementation/

LRU Cache Implementation - GeeksforGeeks

 

 

---

 

 

마무리

 캐싱이 필요한 다양한 곳에서 사용되는 알고리즘이므로 한번 쯤 알아두는것이 좋을 것 같다.

추가적으로 다른 캐시 알고리즘들에 대해서도 다룰 예정

 

 

 

 

 

 

 

 

 

 

-퍼가실 때는 출처를 꼭 같이 적어서 올려주세요!