램, 메모리의 페이지 교체 알고리즘 중 FIFO 를 C++ 로 구현 해 보도록 하겠습니다.
FIFO인 만큼 가장 쉽게 구현 해 볼 수있는 페이지 교체 알고리즘 입니다.
queue<int> pageFrame;
unordered_set<int> pageChecker;
전 위와같이 큐와 unordered_set 을 사용 하여 구현 하였습니다.
큐는 페이지 프레임 안에 들어가있는 것을,
unordered_set 안에는 현재 큐 안에 있는 페이지들을 나타냅니다.
아래 코드에서는 페이지 프레임 내부는 나타내지 않는데 만약 페이지 내부를 보고 싶으시다면
unordered_set 대신 unordered_map 을 이용하여 몇번째 페이지인지 같이 넣어 주시면
간단하게 페이지 프레임 내부또한 알 수 있습니다.
ex) 3개의 프레임이 있을 시
5번 페이지 로드 -> queue 에 5 저장, map 에 (5,1) 저장
3번 페이지 로드 -> queue : 5 / 3 map (5,1) , (3,2)
2번 페이지 로드 -> queue : 5 / 3 / 2 map : (5,1) ,(3,2), (2,3)
1번 페이지 로드 -> 페이지 부재 발생 => queue 의 프론트인 5 제거 , map 의 5에는 1번 슬롯이라고 저장되어 있으니
1번 슬롯에 1번 페이지가 들어가야함. -> queue 3 / 2 / 1 map : (3,2) , (2,3), (1,1)
unordered 를 사용 한 이유는
탐색에서 매우 우수한 속도를 보여주며,
순서가 필요 없고 데이터 범위가 크지 않아서 사용 하였습니다.
unordered_map 사용 방법은 아래 글을 참고 => C++ 셋(set) 과 멥(map) 종류, 쉽게 알아보자. (링크)
코드
#include <iostream>
#include <queue>
#include <unordered_set>
using namespace std;
int main() {
int slotMax;
int newPage;
int pageFaultCount = 0;
queue<int> pageFrame;
unordered_set<int> pageChecker;
unordered_set<int>::iterator itr = pageChecker.end();
cout << " 페이지 프레임의 슬롯 개수를 입력 해 주세요 : ";
cin >> slotMax;
while (true) {
cin >> newPage;
itr = pageChecker.find(newPage);
if ( itr == pageChecker.end()) {
// 페이지 부재 발생
pageFaultCount++;
if (pageFrame.size() == slotMax) {
// 페이지 프레임 가득 차있음.
pageChecker.erase(pageFrame.front());
pageFrame.pop();
}
pageFrame.push(newPage);
pageChecker.insert(newPage);
}
cout << "Page Fault Count : " << pageFaultCount << endl;
}
return 0;
}