[Algorithm] LRU(Least Recently Used) Cache 알고리즘이란? (feat. 페이지 교체 알고리즘)

 

안녕하세요 Foma 입니다.

 

오늘은 효과적으로 메모리를 관리할 수 있는 페이지 교체 기법 중 하나인 LRU Cache 알고리즘에 대해서 다뤄 보려고 합니다.

 

바로 시작할게요~

---

Least Recently Used Cache Algorithm이란?

 

LRU 알고리즘은 FIFO, LFU, MFU 등과 같은 페이지 교체 기법 중 하나인데요.

 

(페이지 교체 기법에 대한 것은 여기 에서 확인해 주세요 ㅜ)

 

그 중에서도 가장 오랫동안 사용하지 않은 페이지를 교체하는 방법입니다.

---

LRU Design

 

LRU Cache 알고리즘은 오랫동안 사용하지 않은 페이지를 삭제해 주고 새롭게 사용된 페이지를 추가해 줘야 합니다.

 

삭제와 추가를 효율적으로 빠르게 하는 것이 핵심인데요.

 

즉, O(1) 시간 복잡도로 해당 기능을 수행해야 합니다.

 

새롭게 사용된 페이지를 가장 최근에 사용된 것으로 빠르게 추가하고 삭제하는 방법에 대해서 알아보겠습니다.

 

O(1)의 시간복잡도로 값을 추가하기 위해선 Linked List 자료구조가 필요합니다.

 

(Linked List에 대해 자세히 알고 싶다면 여기 에서 확인해 주세요!)

 

Linked List의 가장 앞 노드를 head, 가장 뒤 노드를 tail이라고 하겠습니다.

 

head는 가장 최근의 페이지를 저장하고 tail은 가장 오랫동안 사용되지 않은 페이지를 저장합니다.

 

만약 기존 Linked List에 새롭게 사용된 페이지가 이미 존재한다면 해당 노드를 맨 앞으로 이동시켜 줘야겠죠?

 

아래와 같이 Linked List가 있다고 가정하겠습니다.

 

만약 새롭게 사용된 노드가 4라면 기존에 있던 노드를 삭제해 줘야 할 것 입니다.

 

Linked List에서 노드를 삭제해 주는 방법은 해당 자리의 노드의 앞 뒤를 연결시켜 주면 되죠.

 

이 때 해당 노드의 자리가 어디인지 O(1) 시간 복잡도로 확인하기 위해서 Hash Table 자료구조가 필요합니다.

 

(Hash Table에 대해 자세히 알고 싶다면 여기 에서 확인해 주세요!)

 

노드가 가지고 있는 값을 key로, 해당 노드를 value로 가지고 있어야 하죠.

 

그 다음 새롭게 사용된 노드를 헤드로 이동해 주면 되죠.

 

헤드로 이동시켜 주는 방법은 이동시키기 전 헤드의 이전 값으로 해당 노드를 연결시켜 주면 됩니다.

 

만약 Linked List에 없는 값이 추가된다면 어떻게 해줘야 할까요?

 

기존의 노드를 삭제하고 이동하는 과정이 필요없으므로 위 과정에서 head를 추가하는 것만 해주면 됩니다.

 

이렇게 Linked List와 Hash Table 자료구조를 활용하여 가장 최근에 추가된 노드와 가장 오랫동안 쓰이지 않은 노드를 head와 tail에 저장할 수 있게 됩니다.

 

고로 만약 가장 오랫동안 사용되지 않은 노드를 삭제 한다면 tail 노드만 삭제해 주면 되는 것이므로 O(1)의 시간 복잡도만 발생하게 됩니다.

---

Source Code

 

(자세한 코드 설명은 여기 에서 확인해 주세요!)

 

class LRUCache {
    var head: Node?
    var tail: Node?
    var capacity = 0
    var cache = [Int: Node]()
    var count = 0
    
    init(_ capacity: Int) {
        self.capacity = capacity
    }
    
    func get(_ key: Int) -> Int {
        replace(key)
        return cache[key]?.val ?? -1
    }
    
    func put(_ key: Int, _ value: Int) {
        count += 1
        if head == nil {
            head = Node(key, value)
            tail = head
            cache[key] = head
            return
        }
        
        if cache[key] == nil {
            cache[key] = Node(key,value)
        } else {
            count -= 1
            cache[key]?.val = value
        }
        
        if count > capacity {
            delete(key)
        }
        
        replace(key)
    }
    
    func delete(_ key: Int) {
        cache[tail!.key] = nil
        if head === tail {
            head = cache[key]
            tail = head
        } else {
            tail = tail?.prev
            tail?.next = nil
        }
        
        count -= 1
    }
    
    func replace(_ key: Int) {
        if cache[key] == nil || head === cache[key] {
            return
        }

        cache[key]?.prev?.next = cache[key]?.next
        cache[key]?.next?.prev = cache[key]?.prev
        tail = cache[key] === tail ? cache[key]?.prev : tail
        
        cache[key]?.next = head
        head?.prev = cache[key]
        head = cache[key]
        head?.prev = nil
    }
}

---

Problem

 

• https://school.programmers.co.kr/learn/courses/30/lessons/17680
• https://leetcode.com/problems/lru-cache/

---

Reference

 

• https://ko.wikipedia.org/wiki/%ED%8E%98%EC%9D%B4%EC%A7%80_%EA%B5%90%EC%B2%B4_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98
• https://www.geeksforgeeks.org/page-replacement-algorithms-in-operating-systems/
• https://code-lab1.tistory.com/60