캐시(Cache) 알고리즘

LRU 알고리즘
LFU 알고리즘

구현
LeetCode 문제

---

LRU 알고리즘

- 주기억 장치에 적재되어 있는 페이지들에 대해, 참조된 시간을 기준으로 교체될 페이지를 선정하는 방법

- 한 프로세스에 할당된 페이지 프레임들 모두에 페이지가 적재되어 있는 상황에서 새로운 페이지가 적재되어야 할 때는 현재 주 기억 장치에 적재되어 있는 페이지 중 가장 오래동안 참조되지 않은 페이지를 교체 (즉, 사용한지 오래 된 것을 제거)

- 단점: 프로세스가 주 기억 장치에 접근할 때 마다 참조된 페이지에 대한 시간을 기록해야 한다. 

(참조된 페이지의 시간을 현재 시스템 시간으로 갱신한다)

 

아래 그림을 살펴본다.

LRU 알고리즘

 

- 페이지를 참조할 때마다 시간을 갱신한다(초록색 표시)

- 참조 값 5가 들어 올때 시간이 가장 오래된 것(빨간색 화살표)을 제거한다. 시간 순서상으로 가장 멀다.

  따라서 '2'를 비우고 '5'가 들어간다. 

- 이후 방식도 동일하게 동작한다.

 

※ 아래 출처의 그림과는 다릅니다. 본인은 페이지 참조시 마다 페이지 색깔을 초록색으로 바꿨습니다.

 

 

LFU 알고리즘

- 주기억 장치에 적재되어 있는 페이지들에 대해, 참조된 횟수를 기준으로 교체될 페이지를 선정하는 방법

- 한 프로세스에 할당된 페이지 프레임들 모두에 페이지가 적재되어 있는 상황에서 새로운 페이지가 적재되어야 할 때는 현재 주 기억 장치에 적재되어 있는 페이지 중 가장 참조 횟수가 적은 페이지를 교체 (즉, 덜 사용된 것을 제거)

- 참조 횟수가 동일할 경우 LRU 알고리즘을 적용해서 시간이 오래된 것을 교체

- 단점: 참조될 가능성이 많지만, 횟수에 의한 방법이므로 최근에 사용을 시작한 프로그램을 교체시킬 수도 있다. 

LRU와 비슷하게 참조된 페이지에 대한 횟수를 기록해야 한다.

 

LFU 알고리즘

 

- 오른쪽 하단에 참조 횟수를 기입하였다. 참조 될 때마다 숫자(빨간색)를 증가 시켰다.

-  시간=6 에서 '5'가 참조될 때 '1'을 제외한 '2', '6', '4'가 모두 한번 참조되었다. 참조 횟수가 동일하므로 교체된 시간이 긴 '2'를 제거하고 '5'를 채워 넣는다.

 

 

구현

- LinkedList로 구현한 Queue와 HaspMap을 이용한다.

- Queue는 주 메모리 역할을 하고, Hash는 접근 성능 개선을 위해 사용한다.

- 페이지가 주 메모리에 있으면, 노드(페이지)를 큐의 맨 앞으로 가져온다.

- 페이지가 주 메모리에 없으면, 큐에 새로운 노드(페이지)를 추가하고 노드에 대응하는 주소를 해쉬에서 업데이트 한다. 

- 큐가 가득차면, 큐의 맨 마지막 노드를 제거하고 들어오는 새로운 노드(페이지)를 큐의 앞에 위치시킨다.

 

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

class LRUCache {
	list<int> dq;
	unordered_map<int, list<int>::iterator> ma;
	int csize; //캐시 사이즈
public:
	LRUCache(int);
	void refer(int);
	void display();
};

// Declare the size
LRUCache::LRUCache(int n)
{
	csize = n;
}

void LRUCache::refer(int x) {
	// cache에 없다면
	if (ma.find(x) == ma.end())  //find 메소드 사용
	{
		// cache가 가득 찾다면
		if (dq.size() == csize) {
			// LRU 요소를 삭제한다
			int last = dq.back();
			dq.pop_back();
			ma.erase(last); //맨 마지막 요소의 주소도 삭제한다. 
		}
	}
	// cache에 있다면
	else
	{
		dq.erase(ma[x]); //(erage 메소드는 주소값을 받는다). 주소 값을 갱신하기 위해 원소 x의 주소를 삭제한다.
	}

	dq.push_front(x);   //원소를 큐에 앞에 넣는다.
	ma[x] = dq.begin(); //맵에는 원소 x의 주소를 저장(갱신)한다. 
}

void LRUCache::display()
{
	for (auto it = dq.begin(); it != dq.end(); it++) {
		cout << (*it) << " ";
	}
	cout << '\n';
}

int main() {
	LRUCache ca(4);

	ca.refer(1);
	ca.refer(2);
	ca.refer(3);
	ca.refer(1);

	ca.refer(4);
	ca.refer(5);
	ca.display();

	return 0;
}

 

 

LeetCode 문제

https://leetcode.com/problems/lru-cache/

LRU Cache - LeetCode

https://leetcode.com/problems/lfu-cache/

LFU Cache - LeetCode

 

 

---

코드 출처 : GeeksforGeeks

출처 : https://m.blog.naver.com/PostView.nhn?blogId=kyung778&logNo=60164009610&proxyReferer=https:%2F%2Fwww.google.com%2F