램,메모리 페이지 교체 알고리즘 구현 (최적화) - LRU C++

19 May 2019

Reading time ~3 minutes

램, 메모리의 페이지 교체 알고리즘 중LRU 를 C++ 로 구현 해 보도록 하겠습니다.

unordered_map 사용법을 숙지 하고 더블 링크드 리스트를 직접 만들어야 합니다~

unordered_map 사용 방법은 아래 글을 참고 => C++ 셋(set) 과 멥(map) 종류, 쉽게 알아보자. (링크)

우선은 List와 Node 는 페이지 프레임을 의미하며, unordered_map 은 무슨 페이지의 노드의 위치를 저장 합니다.

예

slot : 3 page : 3, 4, 5, 4, 1 (편의상 처음 3개는 바로 입력하고 시작 하겠습니다)

List - head -3 - 4 - 5 - tail

u_map - (3,3(1)), (4,4(2)), (5,*5(3))

page : 4 1) u_map 으로 이미 올라와 있는 페이지인지 확인. 2) 4 의 노드 주소를 u_map 으로 확인 3) 4의 노드를 List에서 제거 (u_map도 함께)

List - head - 3 - 5 - tail / u_map : ((3,3(1)), (5,5(2)) 5) 제일 뒤에 4노드를 삽입 (u_map도 함께 )

결과 List - head - 3 - 5 -4 - tail u_map - (3,3(1)), (4,4(3)), (5,*5(2))

page : 1 1) u_map 으로 올라와 있지 않은 페이지로 확인 2) head->next 노드를 제거및 해당하는 u_map 제거 3) tail 앞에 페이지 1 삽입 _ u_map 생성

List - head - 5 -4 - 1 - tail u_map - (1,1(3)), (4,4(3)), (5,*5(2))

코드

#include <iostream>
#include <queue>
#include <unordered_map>

using namespace std;

int slotMax = 3;

class Node {
public:
	int page;
	Node *pre;
	Node *next;
	Node(int a) {
		page = a;
	}
};

class List {
public :
	Node *head;
	Node *tail;
	Node *temp;
	int nSize = 0;
	unordered_map<int, Node *> pageChecker;
	int pageFault = 0;

	List() {  // 초기화
		head = NULL;
		tail = NULL;
		head = new Node(-1);
		tail = new Node(-1);
		head->next = tail;
		tail->pre = head;
	}
	void add(int a) { // 페이지 요구 명령
		auto itr = pageChecker.find(a);
		if (itr == pageChecker.end()) // 만약 없는 페이지 일 시 페이지 부재 +1
			pageFault++;
		if (nSize == slotMax) { // 모든 페이지가 다 차있을 시 
			if (itr == pageChecker.end()) { 
				// 페이지 프레임에 a가 없을시 제일 오래된 페이지 프레임 제거
				Node *del = head->next;
				head->next = del->next;
				del->next->pre = head;
				pageChecker.erase(del->page);
			}
			else
				pushBack(a); // 있다면 제일 뒤로 보내기 (최근에 사용 되었으니)
		}
		else
			nSize++;
		itr = pageChecker.find(a);
		if (itr == pageChecker.end()) { // 제일 후방에 페이지 추가
			temp = new Node(a);
			Node *ptemp = tail->pre;
			ptemp->next = temp;
			temp->pre = ptemp;
			temp->next = tail;
			tail->pre = temp;
			pageChecker.insert(make_pair(a, temp));
		}
	}
	void pushBack(int a) { // 중간의 페이지 삭제 ( 뒤로 보내기 위해서 )
		auto itr = pageChecker.find(a);
		Node *ptemp = itr->second;
		Node *bTemp = ptemp->pre;
		Node *nTemp = ptemp->next;
		bTemp->next = nTemp;
		nTemp->pre = bTemp;
		pageChecker.erase(itr);
	}
	void pt() {
		Node *temp = head->next;
		while (temp != tail) {
			cout << temp->page << " ";
			temp = temp->next;
		}
		cout << " // Page Fault : " << pageFault << endl;
	}
};

int main() {
	
	int newPage;
	int pageFaultCount = 0;
	
	List pageFrame;

	cout << " 페이지 프레임의 슬롯 개수를 입력 해 주세요  : ";
	cin >> slotMax;
	while (true) {
		cout << "page : ";
		cin >> newPage;
		pageFrame.add(newPage);
		pageFrame.pt();
	}
	return 0;
}

C++페이지교체알고리즘 LRU list unordered_map