CS 공부 & 면접 맛보기 0x0A [운영체제] : LRU 캐싱 (Least Recently Used Cache)

LRU 캐싱 (Least Recently Used Cache)

질문

LRU 캐싱이란 무엇인가요?

답변

LRU (Least Recently Used) 캐싱은 가장 오랫동안 사용하지 않은 데이터를 제거하는 페이지 교체 알고리즘입니다. 사용 빈도가 낮은 데이터를 제거함으로써 효율적으로 메모리를 관리할 수 있습니다.

---

LRU 캐싱의 원리

• 기본 아이디어: 페이지에서 가장 오랫동안 사용되지 않은 데이터를 제거.
• 사용 사례: 메모리 제한이 있는 환경에서 효율적인 데이터 관리.
• 특징: 최근 사용된 데이터는 페이지 상단에 유지되고, 오래된 데이터는 페이지 하단에 유지됨.

---

LRU 캐싱의 구현 방법

첫 번째 방법: 타임스탬프 활용

• 원리: 데이터가 언제 사용되었는지 타임스탬프를 저장하여 가장 오래된 데이터를 제거.
• 구현: 각 데이터에 타임스탬프를 추가하고, 주기적으로 오래된 데이터를 제거.

C++ 코드 예제:

#include <iostream>
#include <unordered_map>
#include <vector>
#include <algorithm>
using namespace std;

class LRUCache {
    int capacity;
    unordered_map<int, pair<int, int>> cache; // key -> {value, timestamp}
    int time = 0;

public:
    LRUCache(int cap) : capacity(cap) {}

    void put(int key, int value) {
        time++;
        if (cache.size() == capacity) {
            auto it = min_element(cache.begin(), cache.end(), [](const auto &a, const auto &b) {
                return a.second.second < b.second.second;
            });
            cache.erase(it->first);
        }
        cache[key] = {value, time};
    }

    int get(int key) {
        if (cache.find(key) == cache.end()) return -1;
        cache[key].second = ++time;
        return cache[key].first;
    }
};

int main() {
    LRUCache cache(2);
    cache.put(1, 10);
    cache.put(2, 20);
    cout << "Key 1: " << cache.get(1) << endl;
    cache.put(3, 30); // Key 2 제거
    cout << "Key 2: " << cache.get(2) << endl;
    return 0;
}

---

두 번째 방법: 큐를 활용한 구현

• 원리: 페이지 데이터를 큐(Queue) 방식으로 관리.
• 구현:
  • 데이터 접근 시 해당 데이터를 큐의 맨 앞으로 이동.
  • 새 데이터가 들어오면 맨 아래에 추가하고, 캐시가 가득 차면 가장 오래된 데이터 제거.

C++ 코드 예제:

#include <iostream>
#include <list>
#include <unordered_map>
using namespace std;

class LRUCache {
    int capacity;
    list<int> cache;
    unordered_map<int, list<int>::iterator> hash;

public:
    LRUCache(int cap) : capacity(cap) {}

    void put(int key) {
        if (hash.find(key) != hash.end()) {
            cache.erase(hash[key]);
        } else if (cache.size() == capacity) {
            int last = cache.back();
            cache.pop_back();
            hash.erase(last);
        }
        cache.push_front(key);
        hash[key] = cache.begin();
    }

    void display() {
        for (auto it : cache) {
            cout << it << " ";
        }
        cout << endl;
    }
};

int main() {
    LRUCache cache(3);
    cache.put(1);
    cache.put(2);
    cache.put(3);
    cache.display();
    cache.put(4);
    cache.display();
    return 0;
}

---

세 번째 방법: Set과 List를 이용한 구현

• 원리: 데이터가 존재하는지 Set으로 확인하고, 새로운 데이터 추가 시 기존 데이터를 제거 후 삽입.
• 구현:
  • Set을 사용하여 중복 검사.
  • List로 데이터의 순서를 유지.

C++ 코드 예제:

#include <iostream>
#include <list>
#include <unordered_set>
using namespace std;

class LRUCache {
    int capacity;
    list<int> cache;
    unordered_set<int> cacheSet;

public:
    LRUCache(int cap) : capacity(cap) {}

    void put(int key) {
        if (cacheSet.find(key) != cacheSet.end()) {
            cache.remove(key);
        } else if (cache.size() == capacity) {
            int last = cache.back();
            cache.pop_back();
            cacheSet.erase(last);
        }
        cache.push_front(key);
        cacheSet.insert(key);
    }

    void display() {
        for (auto it : cache) {
            cout << it << " ";
        }
        cout << endl;
    }
};

int main() {
    LRUCache cache(3);
    cache.put(1);
    cache.put(2);
    cache.put(3);
    cache.display();
    cache.put(4);
    cache.display();
    return 0;
}

---

LRU 캐싱 구현 방식 비교

구현 방법 | 특징 | 시간 복잡도 | 공간 복잡도

타임스탬프 사용	정확하지만 메모리 사용 많음	O(n)	O(n)
큐 사용	직관적이고 구현 쉬움	O(n)	O(n)
Set + List 사용	메모리 절약 및 빠름	O(1)	O(n)

---

결론

• LRU 캐싱은 가장 오랫동안 사용하지 않은 데이터를 제거하는 효율적인 캐싱 알고리즘입니다.
• 타임스탬프, 큐, Set+List 방식 등 여러 방식으로 구현할 수 있습니다.
• 상황에 따라 메모리 사용량과 성능을 고려하여 적절한 방식을 선택하는 것이 중요합니다.