운영체제의 가상 메모리 시스템은 전체 프로그램을 한 번에 메모리에 올리지 않고 실제로 필요한 일부 페이지만 메모리에 적재한다. 그러나 물리 메모리 크기는 한정되어 있기 때문에 새로운 페이지를 불러오기 위해 기존 페이지 중 일부를 제거해야 하는 상황이 발생한다. 이러한 상황에서 어떤 페이지를 제거할지를 결정하는 기준이 바로 페이지 교체 알고리즘(Page Replacement Algorithm)이다. 이 알고리즘의 목표는 앞으로도 사용될 가능성이 낮은 페이지를 선택해 교체함으로써 페이지 폴트를 최소화하고 결과적으로 시스템 전체 성능을 향상시키는 것이다.
페이지 교체 알고리즘의 종류
앞으로 소개될 모든 페이지 교체 알고리즘은 아래 그림과 같은 메모리 접근 순서를 사용하고 물리 메모리는 3개의 프레임을 가졌다고 가정할 것이므로 참고하고 읽어주길 바란다. 페이지는 번호 대신 알파벳을 사용한다.
무작위 페이지 교체 알고리즘(Random)
무작위(Random) 페이지 교체 알고리즘은 말 그대로 교체가 필요한 시점에 메모리에 올라와 있는 페이지들 중 하나를 아무 기준 없이 무작위로 선택하여 제거하는 방식이다. 이 알고리즘은 구현이 가장 간단하며 복잡한 참조 기록이나 추가적인 연산 없이 단순하게 페이지 교체가 가능하다.
하지만 성능 면에서는 매우 비효율적이다. 자주 사용되는 페이지나 방금 접근한 페이지조차도 랜덤하게 제거될 수 있기 때문에 페이지 폴트가 빈번하게 발생할 수 있으며 전체적인 시스템 성능을 떨어뜨릴 수 있다. 따라서 실제 운영체제에서 사용되지는 않으며 보통 알고리즘 테스트나 시뮬레이션에서 비교군으로 사용되는 수준에 머무른다.
FIFO 페이지 교체 알고리즘(First In First Out)
FIFO(First In First Out)는 가장 먼저 메모리에 들어온 페이지를 가장 먼저 교체 대상으로 선택하는 방식이다. 큐(Queue) 자료구조를 이용해 쉽게 구현할 수 있으며 새로운 페이지는 항상 큐의 맨 뒤에 삽입되고 교체 시에는 맨 앞에 있는 페이지가 제거된다.
구현이 단순하고 직관적이라는 장점이 있지만 가장 큰 문제는 최근 접근 여부를 고려하지 않는다는 점이다. 자주 사용하는 페이지라도 단지 오래전에 들어왔다는 이유만으로 제거될 수 있어 비효율적이다. 이러한 특성 때문에 Belady's Anomaly가 발생할 수도 있는데 이는 메모리 프레임 수를 늘렸음에도 오히려 페이지 폴트가 증가하는 역설적인 상황을 말한다. 따라서 FIFO는 단순하지만 실질적인 성능에서는 한계를 갖는 알고리즘이다.
최적 페이지 교체 알고리즘(Optimal)
Optimal(OPT) 페이지 교체 알고리즘은 이론적으로 가장 성능이 뛰어난 알고리즘이다. 그 이유는 현재 시점 이후에 참조될 페이지들 중 가장 나중에 다시 사용될 페이지를 교체 대상으로 선정하기 때문이다. 즉, 미래의 접근 순서를 알고 있다고 가정할 수 있을 때 가장 이상적인 방식으로 페이지를 교체할 수 있다.
예를 들어, A, B, C가 메모리에 있고 앞으로 A와 B는 곧 접근될 예정이며 C는 한참 뒤에나 사용된다면 이 알고리즘은 C를 제거하게 된다. 이러한 원리 덕분에 페이지 폴트를 최소화할 수 있다.
하지만 현실에서는 프로그램의 미래 참조 정보를 알 수 없기 때문에 실제 구현은 불가능하다. 따라서 OPT는 이론적인 기준점(benchmark)으로 사용되며, 다른 알고리즘의 성능을 비교할 때 참고 기준으로 활용된다.
LRU 페이지 교체 알고리즘(Least Recently Used)
LRU(Least Recently Used) 알고리즘은 가장 오랫동안 사용되지 않은 페이지를 제거하는 방식이다. 시간의 흐름에 따라 최근에 사용된 페이지는 앞으로도 계속 사용될 가능성이 높고 오랫동안 사용되지 않은 페이지는 앞으로도 사용되지 않을 가능성이 높다는 지역성 원리를 바탕으로 한다.
1. 시간 기반 접근 방식 (Timestamp 방식)
이 방식은 각 페이지가 마지막으로 접근된 시간을 기록하고 페이지 교체가 필요할 때 가장 오래된 시간값을 가진 페이지를 교체 대상으로 선택하는 방식이다. 운영체제는 글로벌 타이머나 카운터를 유지하며 페이지 접근 시 해당 시점을 타임스탬프로 저장한다. 아래는 간단한 예시이다.
Map<Page, Integer> pageTimeMap;
int globalTime = 0;
void accessPage(Page page) {
pageTimeMap.put(page, globalTime++);
}- 장점: 이론적으로 정확한 LRU를 구현할 수 있다.
-단점: 매 접근마다 현재 시간 기록이 필요하고 교체 시 전체 페이지를 순회해야 하므로 오버헤드가 크다.
실제 운영체제에서는 성능 부담이 커서 거의 사용되지 않는다.
2. 스택 기반 접근 방식 (Linked List or Stack 방식)
LRU를 구현하는 또 다른 방법은 가장 최근에 사용한 페이지를 리스트의 앞에 유지하고 가장 오래된 페이지는 뒤에 위치시키는 방식이다. 페이지가 접근될 때마다 해당 페이지를 리스트의 맨 앞으로 이동시킨다.
// Java 의사 코드 예시
LinkedList<Page> stack;
void accessPage(Page page) {
stack.remove(page); // 중간에 있어도 제거
stack.addFirst(page); // 맨 앞에 삽입
}- 장점: 직관적이고 LRU 논리를 잘 반영함.
- 단점: 중간에 있는 페이지 제거/삽입 시 O(n) 시간이 걸림.
이를 보완하기 위해 Java에서는 LinkedHashMap을 사용해 LRU 캐시를 효율적으로 구현한다.
3. 참조 비트 시프트 방식 (Approximate LRU)
운영체제는 위처럼 정확한 시간 정보를 유지하기 어렵기 때문에 하드웨어 지원이 있는 참조 비트(Referenced Bit)를 활용해 근사적인 방식으로 LRU를 구현하기도 한다. 이 방식에서는 페이지마다 8비트 또는 16비트 정도의 레지스터를 유지한다. 그리고 일정 주기마다 다음과 같은 방식으로 레지스터를 업데이트한다.
- 모든 페이지의 레지스터를 오른쪽으로 1비트 시프트한다.
- 왼쪽 끝에 현재 참조 비트를 삽입한다. (1이면 최근 참조, 0이면 미참조)
예를 들어 어떤 페이지의 레지스터가 01000000이고 이번 주기에 참조되었다면 → 10100000이 된다.
페이지 교체 시에는 가장 작은 값을 가진 페이지를 교체 대상자로 삼는다.
- 장점: 하드웨어 지원 시 매우 효율적이며, 시간/공간 오버헤드가 낮다.
- 단점: 완전한 LRU는 아니며 근사값 기반이므로 정확도가 떨어질 수 있음.
이 방식은 대표적인 근사 LRU로 실제 운영체제에서도 널리 사용된다.
LFU 페이지 교체 알고리즘(Least Frequently Used)
LFU(Least Frequently Used) 알고리즘은 페이지의 누적 참조 횟수를 기준으로 가장 적게 사용된 페이지를 제거하는 방식이다. 각 페이지는 접근될 때마다 카운터를 증가시키며 교체가 필요할 때는 카운터 값이 가장 작은 페이지를 스왑 아웃하게 된다.
이 방식은 자주 사용하는 페이지를 메모리에 오래 유지할 수 있다는 장점이 있다. 하지만 단점도 명확한데 예를 들어 한참 전에는 자주 사용되었지만 최근에는 전혀 사용되지 않는 페이지가 여전히 높은 참조 횟수 때문에 교체 대상이 되지 않을 수 있다. 이런 경우 성능 저하가 발생할 수 있기 때문에 최근성과 빈도를 모두 고려한 하이브리드 방식이 필요하다.
LFU 역시 LRU와 마찬가지로 참조 횟수를 기록해야 하므로 추가적인 메모리 공간이 필요하다. 그럼에도 불구하고 빈도 기반의 판단이라는 점에서 특정 워크로드에서는 LRU보다 더 좋은 성능을 보이기도 한다.
NUR 페이지 교체 알고리즘(Not Used Recently)
NUR(Not Used Recently) 알고리즘은 LRU나 LFU의 성능을 유지하면서도 추가적인 메모리 공간 낭비 없이 구현할 수 있도록 고안된 방식이다. 이 알고리즘은 페이지 테이블 항목(PTE)에 존재하는 접근 비트(Referenced Bit)와 변경 비트(Modified Bit)를 활용한다.
페이지가 읽히거나 실행되면 접근 비트가 1로 설정되며, 페이지가 쓰기 연산에 의해 수정되면 변경 비트가 1이 된다. 이 두 비트는 페이지가 얼마나 자주 사용되고 있는지를 판단하는 중요한 기준이 된다. NUR는 이 비트들의 조합을 바탕으로 교체 우선순위를 매기며 (0, 0) 상태인 페이지, 즉 최근에 접근도 수정도 되지 않은 페이지를 가장 먼저 제거 대상 페이지로 판단한다. 만약 모든 페이지가 (1, 1) 상태라면 운영체제는 모든 비트를 초기화한 뒤 다시 교체를 시도하게 된다.
이 알고리즘은 메모리 공간을 아끼고도 비교적 우수한 성능을 보여주지만, 비트를 정확하게 유지하기 위해 하드웨어 지원이나 소프트웨어 오버헤드가 필요한 점은 고려해야 한다. 실제로 널리 사용되지는 않지만 이론적으로는 LRU나 LFU에 근접한 성능을 낼 수 있다.
FIFO 변형 알고리즘
2차 기회 페이지 교체 알고리즘(Second Chance)
2차 기회(Second Chance) 알고리즘은 FIFO의 단점을 보완한 방식이다. FIFO는 참조 여부를 고려하지 않아 자주 쓰는 페이지도 단순히 오래되었다는 이유만으로 제거될 수 있지만 Second Chance는 참조 비트를 활용해 기회를 한 번 더 부여하는 방식이다.
페이지가 교체 대상이 되기 전에 해당 페이지의 참조 비트를 확인하고 만약 1이라면 이를 0으로 바꾸고 교체를 보류한 채 큐의 뒤쪽으로 보내준다. 참조 비트가 0이면 그대로 해당 페이지를 제거한다. 이러한 방식 덕분에 최근에 사용된 페이지는 자연스럽게 제거 우선순위에서 밀려나고 자주 사용되지 않은 페이지가 먼저 제거되는 효과를 낸다.
이 알고리즘은 FIFO에 비해 성능이 개선되지만 큐를 유지하면서 중간 값을 뒤로 옮기는 연산이 자주 발생하므로 큐의 재정렬 비용이 커지는 단점이 있다. 그래도 LRU보다는 구현이 단순하고 실용적인 선택지로 자주 사용된다.
시계 알고리즘
시계(Clock) 알고리즘은 Second Chance를 원형 큐 형태로 구현한 방식이다. 각 페이지에는 참조 비트가 존재하며 시계 바늘처럼 포인터가 페이지들을 순회하면서 교체 대상을 찾는다.
포인터가 가리키는 페이지의 참조 비트가 1이면 해당 비트를 0으로 바꾸고 다음 페이지로 이동한다. 반면 참조 비트가 0인 페이지를 발견하면 해당 페이지를 제거하고 그 위치에 새로운 페이지를 적재한다. 이 방식은 LRU의 성능을 근사하면서도 구현 비용은 매우 낮기 때문에 실제 운영체제에서도 널리 사용된다.
Linux, Windows, macOS와 같은 대표적인 OS는 LRU의 정확한 구현 대신 이 Clock 알고리즘을 기반으로 한 변형 알고리즘을 사용하여 최근 사용된 페이지를 보존하고 오랫동안 사용되지 않은 페이지를 효율적으로 제거한다. 결과적으로 시계 알고리즘은 이론적 효율성과 구현 현실성 사이의 균형을 잘 맞춘 알고리즘으로 평가받는다.
📝 배운점
가상 메모리 시스템에서 페이지 교체 알고리즘이 왜 중요한지에 대한 근본적인 이해를 얻게 되었다. 운영체제는 제한된 물리 메모리 내에서 여러 프로그램을 동시에 실행시키기 위해 일부 페이지만 메모리에 올리는데 이 과정에서 어떤 페이지를 제거하고 어떤 페이지를 유지할지를 결정하는 전략이 전체 시스템 성능에 큰 영향을 미친다.
가장 먼저 느낀 점은 단순한 방식일수록 구현은 쉬우나 성능이 나쁘고 성능이 좋은 방식일수록 미래 예측이나 접근 이력 관리 등 복잡한 로직이 필요하다는 것이다. 예를 들어 OPT는 이상적인 알고리즘이지만 실현 불가능하고 LRU는 현실적인 대안이지만 접근 순서를 관리하는 데 리소스가 든다. 반대로 FIFO는 단순하지만 벨라디의 역설처럼 오히려 프레임을 늘려도 성능이 나빠지는 경우가 발생할 수 있다는 점도 인상 깊었다. 또한 실제 운영체제에서는 하드웨어 구현의 효율성과 알고리즘의 정확성 사이의 균형이 중요하다는 점도 배웠다. 예를 들어 시계(Clock) 알고리즘은 Second Chance의 기능을 유지하면서도 포인터를 사용해 빠르게 탐색할 수 있어 하드웨어에서 자주 사용된다. 이는 단순히 이론적인 성능보다 현실적인 환경에서의 타협과 설계 판단이 운영체제 개발에서 얼마나 중요한지를 느끼게 해줬다.
마지막으로 알고리즘 간의 비교를 통해 메모리 관리 전략이 단순한 기술 구현을 넘어서 시스템 전체의 효율성과 안정성을 좌우하는 핵심 요소임을 깨달았다. 앞으로 시스템 설계나 성능 최적화를 고민할 때 메모리 접근 패턴과 교체 전략에 대한 고려가 필수적이라는 점을 염두에 두게 되었다.
참고
