왜 이 편이 계산 문제의 핵심인가

14편에서 배웠듯, 물리 메모리에 빈 프레임이 없을 때 페이지 부재가 발생하면 운영체제는 누구를 내보낼지(희생 페이지, victim page) 골라야 한다. 이 결정 규칙이 페이지 교체 알고리즘(page replacement algorithm)이다. 독학사 시험에서 이 단원은 이론 설명보다 참조열(reference string)을 표로 그려 페이지 부재 수를 세는 계산 문제로 가장 자주 나온다. 이 편은 하나의 참조열을 네 알고리즘 모두에 적용해 비교하는 방식으로, 시험장에서 바로 쓸 수 있는 계산 절차를 손에 익힌다.

이 편 전체에서 사용할 참조열은 다음과 같고, 프레임(frame, 프로세스에게 배정된 물리 메모리 블록) 수는 3개로 고정한다.

참조열: 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1   (총 20회 참조)
프레임 수: 3

쉽게 말하면: 페이지 교체 알고리즘은 “냉장고(프레임)가 꽉 찼는데 새 재료(페이지)를 넣어야 할 때, 어떤 재료를 버릴지” 정하는 규칙이다.

FIFO — 가장 먼저 들어온 것을 내보낸다

원리

FIFO(First-In First-Out, 선입선출) 알고리즘은 이름 그대로 프레임에 가장 먼저 적재된 페이지를 희생 페이지로 고른다. 각 페이지가 언제, 얼마나 자주 쓰이는지는 전혀 고려하지 않고 오직 “적재된 순서”만 본다. 구현이 단순해 큐(queue) 하나로 관리할 수 있다는 장점이 있지만, 자주 쓰이는 페이지라도 먼저 들어왔다는 이유만으로 쫓겨날 수 있다는 약점이 있다.

단계별 계산표

결과 해석: 부재 표시가 붙은 칸을 세면 15회다(적중은 5, 6, 7, 8단계에 해당하는 5번, 12·13·16·17단계). $20 - 5 = 15$. FIFO는 20번의 참조 중 15번이나 디스크에서 페이지를 다시 가져와야 했다 — 뒤에서 확인할 LRU·OPT보다 훨씬 나쁜 성적이다. 4단계에서 7을 내보냈는데 18단계에서 7이 다시 필요해진 것처럼, FIFO는 “곧 다시 쓸 페이지”인지 전혀 신경 쓰지 않기 때문에 이런 비효율이 반복된다.

LRU — 가장 오래 안 쓴 것을 내보낸다

원리

LRU(Least Recently Used, 최근 최소 사용) 알고리즘은 가장 최근에 참조된 시점이 가장 오래된 페이지를 희생 페이지로 고른다. FIFO는 “언제 들어왔는지”만 보지만, LRU는 “언제 마지막으로 썼는지”를 본다. 14편에서 배운 시간 지역성(temporal locality, 최근 쓴 것을 곧 다시 쓰는 경향)에 기반한 알고리즘이라, 실제 프로그램 패턴에 훨씬 잘 들어맞는다.

단계별 계산표

프레임 구성은 왼쪽부터 가장 오래전에 쓴 페이지(희생 후보), 오른쪽이 가장 최근에 쓴 페이지가 되도록 정렬해 표시한다.

결과 해석: 부재는 12회다(적중은 5, 7, 12, 13, 15, 17, 19, 20단계로 8회, $20-8=12$). FIFO(15회)보다 3회 적다. 14단계를 보면 0을 내보냈는데, 이 0은 4단계 전인 11단계에서 마지막으로 쓰였을 뿐이라 “가장 오래 안 쓴” 페이지였다. 반면 3(10단계에서 씀), 2(13단계에서 씀)는 최근에 썼으므로 살아남았다. 이렇게 최근 사용 이력을 반영하니 FIFO보다 실제 재사용 패턴에 잘 맞는 결과가 나온다.

자주 틀리는 점: LRU는 “가장 오래전에 적재된” 것이 아니라 “가장 오래전에 참조된(마지막으로 쓰인)” 것을 내보낸다. 7단계에서 0이 적중했으면, 0은 그 순간 “방금 쓴 페이지”로 갱신되어 희생 순번 맨 뒤로 밀려난다. 적재 시점과 참조 시점을 혼동하면 FIFO와 답이 뒤섞인다.

OPT — 미래를 알고 있다면(이론적 최적)

원리

OPT(Optimal, 최적 교체) 알고리즘은 앞으로 가장 오랫동안 쓰이지 않을 페이지, 또는 앞으로 다시는 쓰이지 않을 페이지를 희생 페이지로 고른다. 미래의 참조를 미리 알아야 하므로 실제 운영체제에서는 구현할 수 없지만, “이론상 낼 수 있는 최소 부재 횟수”를 계산해 다른 알고리즘의 성능을 비교하는 기준선(baseline)으로 쓰인다.

단계별 계산표

각 부재 시점에서 남은 참조열을 미리 보고, 프레임 안의 페이지 중 다음 참조가 가장 먼 것(또는 다시 안 나오는 것)을 표시한다.

결과 해석: 부재는 9회뿐이다(적중이 5, 7, 9, 10, 12, 13, 15, 16, 17, 19, 20단계로 11회, $20-11=9$). 같은 참조열에서 FIFO는 15회, LRU는 12회, OPT는 9회다. OPT는 이론적 하한선이므로 어떤 알고리즘도 OPT보다 적은 부재를 낼 수 없다 — 이 값은 “이 알고리즘이 최적에 얼마나 가까운가”를 재는 잣대로 쓰인다.

LFU — 가장 적게 쓴 것을 내보낸다

LFU(Least Frequently Used, 최소 빈도 사용) 알고리즘은 프레임에 있는 동안 참조 횟수가 가장 적은 페이지를 희생 페이지로 고른다. “자주 쓰는 페이지는 앞으로도 자주 쓰일 것”이라는 가정에 기반한다.

자주 틀리는 점: 참조 횟수가 같은 페이지가 여러 개면(동점) 어느 것을 내보낼지 알고리즘 자체만으로는 정해지지 않는다. 시험 문제에서는 보통 “동점이면 가장 먼저 적재된(오래된) 페이지를 내보낸다”는 FIFO 동점 처리 규칙을 함께 제시하므로, 문제 지문의 동점 처리 조건을 반드시 확인해야 한다. 이 편의 계산에서도 이 규칙을 적용한다.

결과 해석: 부재는 13회다(적중은 5, 7, 11, 12, 13, 16, 19단계로 7회, $20-7=13$). 이번 참조열에서는 OPT(9) < LRU(12) < LFU(13) < FIFO(15) 순으로 성적이 좋았다. 다만 LFU의 순위는 참조열의 패턴과 동점 처리 규칙에 따라 달라질 수 있어, “LFU가 항상 LRU보다 나쁘다”고 일반화하면 안 된다. 예를 들어 0처럼 초반에 많이 쓰인 페이지가 나중엔 안 쓰이는데도 누적 빈도가 높다는 이유로 계속 살아남는 것은 LFU의 대표적인 약점이다 — 이를 “오래된 인기”에 낚이는 문제라 부르기도 한다.

네 알고리즘 비교 정리

벨레이디 이상 — 프레임을 늘렸는데 부재가 더 늘어난다

직관에 반하는 현상

쉽게 말하면: 벨레이디 이상은 “냉장고를 더 큰 걸로 바꿨는데 오히려 장 보는 횟수가 늘어난” 것처럼 상식과 어긋나는 현상이다.

보통은 프레임 수를 늘리면 더 많은 페이지를 동시에 담을 수 있으니 페이지 부재가 줄어들 것으로 기대한다. 그런데 FIFO 알고리즘에서는 프레임 수를 늘렸는데 오히려 페이지 부재 횟수가 늘어나는 경우가 실제로 존재한다. 이를 벨레이디 이상(Belady’s Anomaly)이라 한다. LRU와 OPT는 이런 이상 현상이 발생하지 않는다는 것이 증명되어 있다(스택 알고리즘의 성질). FIFO는 이 성질을 만족하지 않기 때문에 이상 현상이 일어날 수 있다.

실제 숫자로 확인하기

이 현상을 보여주는 고전적인 참조열은 다음과 같다.

참조열: 1 2 3 4 1 2 5 1 2 3 4 5   (총 12회 참조)

프레임 3개로 FIFO를 계산하면:

프레임 3개일 때 부재는 9회다(적중 3회, $12-3=9$).

프레임 4개로 같은 참조열을 FIFO로 계산하면:

프레임 4개일 때 부재는 10회다(적중 2회, $12-2=10$).

결과 해석: 프레임을 3개에서 4개로 늘렸는데도 페이지 부재는 9회에서 10회로 오히려 늘었다. 원인은 7단계 이후에 있다. 프레임 3개일 때는 4단계에서 1을, 5단계에서 2를 이미 내보낸 상태라 7단계에서 5가 들어올 때 4가 나가면서 마침 1과 2가 다시 프레임에 남아 8·9단계가 적중된다. 반면 프레임 4개일 때는 1, 2, 3, 4가 전부 프레임에 남아 있다가 7단계에서 1이 쫓겨나는 바람에, 정작 8·9단계에서 1과 2를 다시 불러와야 하는 엇갈림이 생긴다. “적재 순서”만 보는 FIFO는 프레임이 늘어도 이런 우연한 엇갈림을 막을 근거가 없다. 이것이 FIFO가 LRU·OPT보다 이론적으로 열등하다고 평가받는 이유 중 하나다.

핵심 정리

• 같은 참조열(7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1, 프레임 3개)에서 FIFO는 15회, LRU는 12회, LFU는 13회, OPT는 9회의 페이지 부재가 발생했다.
• FIFO는 적재 순서, LRU는 마지막 참조 시점, LFU는 누적 참조 횟수, OPT는 미래 참조를 기준으로 희생 페이지를 고른다.
• OPT는 이론적 최적(하한선)이라 실제 구현이 불가능하며, 다른 알고리즘의 성능을 재는 비교 기준으로 쓰인다.
• 벨레이디 이상은 FIFO에서 프레임 수를 늘렸는데도 페이지 부재가 늘어나는 현상이다(참조열 1 2 3 4 1 2 5 1 2 3 4 5에서 프레임 3개는 9회, 4개는 10회). LRU·OPT에서는 발생하지 않는다.
• LFU는 동점 처리 규칙이 문제마다 다를 수 있으므로 지문의 조건을 먼저 확인해야 한다.

마무리 복습

참고 자료

• KOCW 운영체제 강의자료 - 스케줄링/동기화/가상메모리 
• 운영체제 개론 KOCW 자료