LRU(Least Recently Used) 알고리즘 이란

문제 풀다가 LRU알고리즘에 대한 문제가 나와서 정리해보려고 한다. LRU는 페이지 교체 알고리즘 중 하나이므로 페이지 교체 알고리즘 먼저 알아보자!

페이지 교체 알고리즘

• 페이징 기법으로 메모리를 관리하는 운영체제에서, 페이지 부재가 발생하여 새로운 페이지를 할당하기 위해 현재 할당된 페이지 중 어는 것과 교체할지 결정하는 방법.

  FIFO : 페이지가 주기억장치에 적재된 시간을 기준으로 교체될 페이지를 선정하는 기법
  - 단점 : 중요한 페이지가 오래 있었다는 이유만으로 교체되는 불합리. 가장 오래 있었던 페이지는 앞으로 계속 사용될 가능성이 있다.

  LFU : 가장 적은 회수를 참조하는 페이지를 교체
  - 단점 : 참조될 가능성이 많음에도 불구하고 횟수에 의한 방법이므로 최근에 사용된 프로그램을 교체싴킬 가능성이 있고, 해당 횟수를 증가시키므로 오버헤드 발생

  LRU : 가장 오랫동안 참조되지 않은 페이지를 교체
  - 단점 : 프로세스가 주기억장치에 접근할 때마다 참조된 페이지에 대한 시간을 기록해야 함. 큰 오버헤드가 발생

---

🧐LRU(Least Recently Used) 알고리즘 이란?

• 캐시가 사용하는 리소스의 양은 제한되어 있고, 캐시는 제한된 리소스 내에서 데이터를 빠르게 저장하고 접근할 수 있어야 한다.
• 가장 오랫동안 참조되지 않은 페이지를 교체하는 방법

✨장점
- 빠른 액세스 : 가장 최근에 사용한 아이템부터 가장 적에 사용한 아이템까지 정렬된다.
따라서 두 아이템에 접근할 경우, O(n)의 시간 복잡도를 가진다.
- 빠른 update : 하나의 아이템에 액세스 할때마다 업데이트 되며, O(n)의 시간 복잡도를 가진다.

⚡️단점
- 많은 공간 차지
=> n개의 아이템을 저장하는 LRU는 N의 크기를 가지는 1개의 Linked-list(queue)와 이를 추적하기 위한 n의 크기를 가지는 1개의 hash-map이 필요하다.
이는 O(n)의 복잡도를 가지지만, 2개의 데이터 구조를 사용해야 한다는 단점이 있다.

---

그림으로 살펴보기

Input : 123145 인 상황에서
4초를 보면 원래 있었던 1이 한번 더 입력되므로 1을 참조한다. 참조 후 오랫동안 참조하지 않은 순으로 바꾸면 2->3->1이 된다.
6초에는 cache size가 가득차 5가 들어갈 수 없으므로, 가장 오랫동안 참조되지 않은 2를 제거한 후 저장한다.
Output : 5413

코드

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

class LRU {
	// 데이터를 저장할 list
	list<int> LRUList;

	// 참조를 저장할 map
	unordered_map<int, list<int>::iterator> LRUMap;

	// 최대 용량
	int LRUMaxSize; 

public:
	LRU(int);
	void refer(int);
	void display();
};

// 클래스가 생성될 때 크기를 선언함.
LRU::LRU(int n)
{
	LRUMaxSize = n;
}

// 요소 x를 참조하는 함수 refer
void LRU::refer(int x)
{
	// 캐시 내에 없을 경우
	if (LRUMap.find(x) == LRUMap.end()) {
		// 캐시가 꽉 찼을 경우
		if (LRUList.size() == LRUMaxSize) {
			int last = LRUList.back();

			// 리스트에서 가장 오래 사용되지 않은 요소 pop
			LRUList.pop_back();

			// 참조도 함께 삭제
			LRUMap.erase(last);
		}
	}

	// 캐시 내에 있을 경우 해당 요소 삭제
	else
		LRUList.erase(LRUMap[x]);

	// 새로운 요소 x를 맨 앞에 push, 참조도 updqte
	LRUList.push_front(x);
	LRUMap[x] = LRUList.begin();
}

// 요소 x를 참조하는 함수 refer
void LRU::display()
{
	for (auto it = LRUList.begin(); it != LRUList.end(); it++) {
		cout << (*it) << " ";
	}

	cout << endl;
}

int main()
{
	LRU ca(4);

	ca.refer(1);
	ca.refer(2);
	ca.refer(3);
	ca.refer(1);
	ca.refer(4);
	ca.refer(5);
	ca.display();

	return 0;
}

Reference
https://rangsub.tistory.com/124?category=891713
https://j2wooooo.tistory.com/121