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/
마무리
캐싱이 필요한 다양한 곳에서 사용되는 알고리즘이므로 한번 쯤 알아두는것이 좋을 것 같다.
추가적으로 다른 캐시 알고리즘들에 대해서도 다룰 예정
-퍼가실 때는 출처를 꼭 같이 적어서 올려주세요!
'Dev > [Algorithm]' 카테고리의 다른 글
[Algorithm] [C++] 백준 1436번 영화감독 숌 (0) | 2020.11.04 |
---|---|
[Algorithm] [C++] 백준 15649번 N과M(1) (0) | 2020.11.04 |
[Algorithm] [C++] 백준 10171번 고양이 (0) | 2020.10.22 |
[Algorithm] [C++] 백준 2798번 블랙잭 (0) | 2020.10.22 |
[Algorithm] [C++] 백준 10989번 수 정렬하기 3 (0) | 2020.07.14 |