페이지 교체 알고리즘 (Page Replacement Algorithm)

운영체제에서 꼭 다루는 Page Replacement Algorithm 입니다. (PRA라고 줄여 부르겠습니다)

 

저희는 컴퓨터의 저장공간에 프로그램을 설치해두고, 이를 더블클릭하여 실행합니다.

그렇게 실행된 프로그램은 프로세스가 되어 메모리 위해 올라가면서 실행되는 원리입니다.

 

이때 프로세스는 한 묶음으로 반드시 통채로 올라가는 것이 아니라, 분리된 채로 쪼개져서 메모리 위에 올라갑니다.

그리고 그 분리되는 단위를 페이지라고 이해하면 됩니다.

 

하지만 메모리의 용량은 제한적이기 때문에, 무한개의 프로세스를 만들 수는 없습니다.

따라서 프로세스의 특정 페이지는 회수(즉 메모리에서 해제)되어야만 메모리의 빈 공간이 생기고 그 곳에 새로운 페이지를 올릴 수 있게 됩니다. 이렇게 페이지를 회수하고 올리는 교체 과정을 스와핑(Swaping) 이라고 부릅니다.

 

스와핑은 비용이 큰 작업입니다. 따라서 최소화하는게 좋습니다.

이를 위해 페이지 교체 알고리즘들이 나오게 되었습니다. 

 

 

최적의 페이지 교체 알고리즘 - Optimal Page Replacement

그렇다면 스와핑 횟수를 최소화하는 가장 최적-최고의 페이지 교체 알고리즘(아이디어)은 뭘까요?

바로 "가장 오랫동안 참조되지 않을 페이지를 회수해버린다" 라는 아이디어입니다.

 

현실 세계에서는 절대 사용할 수 없습니다. 미래를 알아야만 적용가능한 알고리즘이기 때문입니다.

다만, 코딩테스트에서는 사용이 가능합니다. 보통 입력값으로 미래도 같이 주어지기 때문입니다.

 

백준 1700번 문제가 대표적입니다. 해당 문제에 대한 해설 코드는 아래와 같습니다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int INF = 987654321;
const int MAX_SIZE = 101; //1~100
int n,k;
int candidate[MAX_SIZE]; 
vector<int> holes; 
bool isSelected[MAX_SIZE]; 

void pageReplacement(int index){
    if(holes.size() != n) throw runtime_error("오직 구멍이 다 찼을 때만 사용할 수 있습니다.");

    int lastRef = 0; int targetNumber = -1;
    for(int selectedNum : holes){
        int curRef = INF;
        for(int j = index+1; j < k; j++){ 
            if(selectedNum == candidate[j]){
                curRef = j;
                break; 
            }
        }
        if(lastRef < curRef){
            lastRef = curRef;
            targetNumber = selectedNum;
        }
    }

    holes.erase(find(holes.begin(), holes.end(), targetNumber)); 
    isSelected[targetNumber] = false; 
}

void scheduling(int index, int & ret){
    int itemNumber = candidate[index];
    if(!isSelected[itemNumber]){ 
        if(holes.size() == n){
            pageReplacement(index);
            ret++;
        }
        holes.push_back(itemNumber);
        isSelected[itemNumber] = true;
    }
}


int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> n >> k;

    int ret = 0;
    for(int i = 0; i < k; i++) cin >> candidate[i];
    for(int i = 0; i < k; i++) scheduling(i, ret);
    cout << ret << "\n";

    return 0;
}

 

 

현실 세계에서 사용할 수 있는 최고의 알고리즘은? - LRU

바로 Optimal Page Replacement 를 근사화한 LRU(Least Recently Used) 입니다.

즉 "가장 오랫동안 참조되지 않은 페이지를 교체" 하는 알고리즘입니다. 

 

Optimal Page Replacement 는 미래를 바라보는 알고리즘이라면,

Least Recently Used 는 과거를 들여다보고 미래를 추측하는 알고리즘입니다.

 

하지만 실제 운영체제 페이지 교체 알고리즘으로 사용되지는 않습니다.

구현 비용이 크기 때문입니다. (모든 페이지 접근마다 타임스탬프 갱신 or 스택 조작 필요)

 

 

운영체제에서 자주 사용하는 PRA는? - Clock 알고리즘, Working Set 등

따라서 실제로는 LRU를 근사화한 알고리즘을 사용합니다. 

대표적으로 Clock 알고리즘과 Working Set이 존재합니다. 

자세한 내용은 생략하고, 대략적인 설명만 진행하면 다음과 같습니다.

 

Clock 알고리즘 (Second Chance Algorithm)

• LRU의 근사 알고리즘.
• 페이지마다 “참조 비트(reference bit)”를 두고, 한 바퀴를 돌면서 참조되지 않은 페이지를 찾아 교체.
• 참조된 페이지는 비트를 0으로 초기화하고 “한 번의 기회(Second Chance)”를 줌.
• 기회를 박탈당하면 교체 (이미 1인 상태에서 다시 방문하게 되었으면, 해당 페이지는 교체됨)

 

Working Set Model

• 각 프로세스마다 “작업 집합(working set)” 크기를 유지.
• 일정 주기마다 trim(메모리 줄이기) 하며 오래 안 쓰인 페이지를 스왑 아웃.
• PRA의 일종이라기보다는, locality를 계산하기 위한 하나의 방법
  • 지역성이 높을수록 자주 사용되는 페이지일거라는 믿음에서 비롯됨. (공간,시간 존재)
  • 또다른 방법으로 Page fault frequency 방법이 존재