페이지 참조 배열과 프레임 개수가 주어졌을 때, 최적 페이지 교체 알고리즘(Optimal Page Replacement)을 사용해 메모리 블록에 페이지를 할당하는 과정에서 발생하는 히트(Hit)와 미스(Miss)의 횟수를 구하는 것이 이번 글의 목표입니다.
최적 페이지 교체 알고리즘이란?
페이지 교체 알고리즘(Page Replacement Algorithm)은 물리 메모리가 가득 찼을 때 어떤 페이지를 내보낼지 결정하는 알고리즘입니다.
그중 최적 페이지 교체 알고리즘은 가까운 미래에 다시 참조되지 않을 페이지를 교체 대상으로 선택합니다. 실제 시스템에서는 미래의 페이지 참조를 예측할 수 없어 구현이 불가능하지만, 이론적으로 미스(Miss) 횟수가 가장 적게 발생하는 가장 이상적인 알고리즘으로 평가됩니다. 따라서 다른 페이지 교체 알고리즘(LRU, FIFO 등)의 성능을 비교하는 기준점으로 자주 활용됩니다.
예시를 통해 동작 과정을 살펴보겠습니다.
위 그림처럼 1, 2, 3을 차례로 할당하면 메모리가 가득 찹니다. 이후 페이지 4를 삽입해야 하는 상황에서는, 현재 메모리에 있는 1, 2, 3 중 가장 오랫동안 다시 참조되지 않을 페이지를 찾습니다. 페이지 3이 근미래에 다시 등장하지 않는다면, 페이지 3을 내보내고 새 페이지 4를 넣는 방식입니다. 이 과정을 참조 배열의 끝까지 반복합니다.
예제 입출력
입력: page[] = { 1, 7, 8, 3, 0, 2, 0, 3, 5, 4, 0, 6, 1 }
fn = 3
출력: Hits = 3
Misses = 10
입력: page[] = { 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2 }
fn = 4
출력: Hits = 7
Misses = 6
문제 해결 접근 방식
- 페이지 참조 배열을 입력받습니다.
- 메모리에 있는 각 페이지가 근미래에 다시 참조되는지 확인하고, 참조되지 않는 페이지가 있다면 그 자리를 새 페이지로 교체합니다.
- 요청한 페이지가 이미 메모리에 있으면 히트(Hit)를 증가시키고, 없으면 미스(Miss)로 처리합니다.
- 배열의 마지막 요소까지 위 과정을 반복합니다.
- 최종적으로 히트와 미스의 개수를 출력합니다.
알고리즘
Start
Step 1-> 함수 int predict(int page[], vector<int>& fr, int pn, int index)
res = -1, farthest = index 로 선언 및 초기화
반복 For i = 0 ~ fr.size()-1
반복 For j = index ~ pn-1
If fr[i] == page[j]
If j > farthest → farthest = j, res = i
break
If j == pn → Return i // 미래에 한 번도 참조되지 않는 페이지
Return (res == -1) ? 0 : res
Step 2-> 함수 bool search(int key, vector<int>& fr)
반복 For i = 0 ~ fr.size()-1
If fr[i] == key → Return true
Return false
Step 3-> 함수 void opr(int page[], int pn, int fn)
vector<int> fr 선언, hit = 0 초기화
반복 For i = 0 ~ pn-1
If search(page[i], fr) → hit++ 후 continue (HIT)
If fr.size() < fn → fr.push_back(page[i])
Else → j = predict(page, fr, pn, i + 1), fr[j] = page[i] (MISS 후 교체)
히트 개수 출력, 미스 개수 출력
Step 4-> 함수 int main()
page[] = { 1, 7, 8, 3, 0, 2, 0, 3, 5, 4, 0, 6, 1 } 선언
pn = sizeof(page) / sizeof(page[0]), fn = 3 설정
opr(page, pn, fn) 호출
Stop
C++ 전체 코드
#include <bits/stdc++.h>
using namespace std;
// 앞으로 가장 늦게 사용될(또는 사용되지 않을) 페이지의 인덱스를 찾는 함수
int predict(int page[], vector<int>& fr, int pn, int index) {
int res = -1, farthest = index;
for (int i = 0; i < fr.size(); i++) {
int j;
for (j = index; j < pn; j++) {
if (fr[i] == page[j]) {
if (j > farthest) {
farthest = j;
res = i;
}
break;
}
}
// 미래에 한 번도 참조되지 않는 페이지라면 바로 반환
if (j == pn)
return i;
}
// 모든 프레임이 미래에 참조된다면, 가장 늦게 참조되는 페이지(res) 반환
return (res == -1) ? 0 : res;
}
// 프레임 안에 특정 페이지가 존재하는지 확인하는 함수
bool search(int key, vector<int>& fr) {
for (int i = 0; i < fr.size(); i++)
if (fr[i] == key)
return true;
return false;
}
// 최적 페이지 교체 알고리즘 실행 함수
void opr(int page[], int pn, int fn) {
vector<int> fr;
int hit = 0;
for (int i = 0; i < pn; i++) {
// 프레임에서 페이지를 찾은 경우 : HIT
if (search(page[i], fr)) {
hit++;
continue;
}
// 페이지를 못 찾은 경우 : MISS
// 빈 프레임이 남아 있다면 그대로 추가
if (fr.size() < fn)
fr.push_back(page[i]);
else {
// 교체할 페이지를 찾아 교체
int j = predict(page, fr, pn, i + 1);
fr[j] = page[i];
}
}
cout << "Hits = " << hit << endl;
cout << "Misses = " << pn - hit << endl;
}
// main 함수
int main() {
int page[] = { 1, 7, 8, 3, 0, 2, 0, 3, 5, 4, 0, 6, 1 };
int pn = sizeof(page) / sizeof(page[0]);
int fn = 3;
opr(page, pn, fn);
return 0;
}
실행 결과
Hits = 3 Misses = 10
핵심 정리
최적 페이지 교체 알고리즘은 predict() 함수를 통해 각 프레임의 페이지가 미래에 언제 다시 참조되는지 확인하고, 가장 늦게 참조되거나 아예 참조되지 않는 페이지를 교체하는 방식으로 동작합니다. 전체 참조 횟수에서 히트 횟수를 빼면 곧 미스 횟수가 되며, 이 알고리즘은 이론적으로 가능한 최소 미스를 보장하기 때문에 운영체제에서 페이지 교체 정책의 성능 상한선을 나타내는 중요한 기준이 됩니다.