[OS] Page Replacement: FIFO, LRU, Clock, 그리고 Thrashing

운영체제의 메모리 관리에서 가장 중요한 문제 중 하나는 '어떤 페이지를 내보낼 것인가?'이다. 메모리(RAM)는 한정되어 있고, 동시에 여러 프로세스가 실행되면 모든 페이지를 올려둘 수 없기 때문이다.

이때 운영체제는 페이지 교체 정책(Page Replacement Policy) 을 이용해 희생(victim) 페이지를 선택한다.

 

 

Page Replacement 개념

메인 메모리는 결국 가상 메모리의 캐시(Cache) 라고 볼 수 있다. 디스크(Backing Store)에서 필요한 페이지를 가져오고, 공간이 부족하면 덜 쓰이는 페이지를 내보낸다.

 

이 과정의 목표는 페이지 폴트(Page Fault)를 최소화하는 것이다. 즉, 평균 메모리 접근 시간(AMAT) 을 줄이는 것이다.

 

 

 

평균 메모리 접근 시간(AMAT)는 주로 다음과 같이 구한다. 

 

예시

• 메모리 접근: 100ns
• 디스크 접근: 10ms (1000만 ns)
• 만약 miss 확률이 0.1(10%)이면 → AMAT ≈ 1ms (100ns + 0.1 * 10ms)
• miss 확률을 0.001(0.1%)로 낮추면 → AMAT ≈ 10.1μs (100ns + 0.001 * 10ms)

Hit rate 90%와 99.9%의 차이만으로도 100배 빠른 성능 차이가 발생한다.

 

 

 

---

 

 

이상적인 정책: Belady’s optimal replacement policy

이론적으로 가장 좋은 정책은 앞으로 가장 오랫동안 사용되지 않을 페이지를 교체하는 것이다. 미래를 보고 가장 나중에 쓰이는 걸 찾는 것이다. 

 

하지만 미래를 예측할 수는 없기 때문에 현실적으로 불가능하다. 그래도 비교 대상의 척도로는 좋다. 

 

 

미래를 예측한 값이기 때문에 가장 이상적인 hit rate을 가진다.

 

 

---

 

 

FIFO (First-In, First-Out)

• 먼저 들어온 페이지를 먼저 내보내는 구조 (들어온 페이지는 queue의 마지막에 두고, queue의 가장 값의 페이지를 내보낸다)

FIFO의 치명적 문제: 페이지 0이 자주 쓰여도, 먼저 들어왔다는 이유만으로 내보내진다.

 

 

또한 구현이 간단하지만 Belady’s Anomaly(캐시 크기가 늘었는데 오히려 성능이 나빠짐) 현상이 발생할 수 있다.

FIFO에서는 캐시(페이지 프레임) 수가 늘어나도 페이지 폴트가 줄지 않을 수 있다. 이런 현상을 Belady’s Anomaly라고 하며, 더 많은 메모리가 오히려 성능을 떨어뜨리는 대표적인 예시이다.

 

 

 

 

Random

• 무작위로 페이지를 선택해 교체
• 구현은 간단하지만 예측 불가, 성능이 운에 좌우됨

랜덤 방식은 가장 최적일때도 있지만 최악일때도 있는 방법이다.

 

 

---

 

 

역사 기반 정책: LRU (Least Recently Used)

FIFO나 Random의 문제는 "최근에 쓴 페이지를 버릴 수도 있다"는 것이다.

 

따라서 OS는 최근 사용 이력(History) 을 바탕으로 판단하는 LRU를 사용한다.

• 가장 오래전에 접근된 페이지를 교체
• 시간 지역성(Temporal Locality) 과 공간 지역성(Spatial Locality) 을 기반으로 동작

LRU(Least Recently Used)는 '가장 오랫동안 사용되지 않은 페이지'를 교체하는 방식이고, LFU(Least Frequently Used)는 '가장 사용 빈도가 낮은 페이지'를 교체하는 방식이다. 일반적으로 운영체제는 구현 효율과 locality 특성 때문에 LRU를 더 자주 사용한다.

 

 

FIFO와 Random 방식과 비교했을 때 높은 hit rate을 보인다.

 

 

 

locality(지역성)이 없을때는 LRU, FIFO, RANDOM이 모두 비슷한 hit rate를 보인다. 

 

 

하지만 80% 접근이 20%의 'hot'페이지에 집중될때는 LRU의 성능이 가장 좋다. 왜냐하면 자주 접근되는 페이지는 최근 접근으로 간주되어 캐시에 저장되고 있기 때문이다.

 

 

순차적 반복 접근 (예: 0~49 반복)은 상황이 다르다. LRU/FIFO 최악(0% hit)이다. 계속 새로운 페이지가 들어와 이전의 페이지는 사라지고, 지역성도 없기 때문이다. 이 경우는 Random이 오히려 낫다.

 

 

모든 상황에서 LRU가 최적은 아니며, 워크로드 특성에 따라 다르게 작동한다.

 

 

---

 

 

LRU의 구현 문제 (Implementing Historical Algorithms)

LRU(Least Recently Used)는 분명 성능이 좋지만, 구현 비용이 매우 크다. 이유는 "최근 사용 이력"을 계속 추적해야 하기 때문이다.

 

LRU의 문제점

• 모든 메모리 접근마다 '최근 사용' 정보 갱신 필요
• 페이지가 접근될 때마다 리스트의 가장 최근 위치(MRU) 로 이동
• 결국 매 접근마다 자료구조를 갱신해야 하므로, 시간 복잡도가 크다

 

 

예를 들어 4GB 메모리에 약 100만 개의 페이지가 있다면, 매 접근 시 전체를 스캔하거나 타임스탬프를 갱신해야 한다. 이건 CPU가 아무리 빨라도 감당 불가능하다.

 

FIFO와의 차이

• FIFO는 삽입/삭제 시에만 갱신
• LRU는 모든 접근 시에 갱신

즉, LRU는 성능은 좋지만 오버헤드가 너무 크다. 이 때문에 현실적인 OS는 '근사치'로 접근한다.

 

 

---

 

 

Approximation LRU: Clock Algorithm

LRU를 완벽하게 구현하기는 어렵지만, 비슷한 효과를 내는 방법이 있다. 그게 바로 Clock 알고리즘이다.

 

기본 아이디어

• 하드웨어 지원 비트(reference bit) 사용
• 페이지가 접근될 때마다 하드웨어가 자동으로 use bit = 1 로 설정
• OS는 교체 시 시계바늘(clock hand) 처럼 원형 리스트를 돌며 다음 규칙을 적용한다

Use Bit	의미	동작
1	최근에 사용됨	use 비트를 0으로 초기화하고 다음 페이지로 이동
0	최근에 사용되지 않음	해당 페이지 교체(Evict)

즉, 한 번 회전할 때 use=1인 페이지들은 '이번엔 봐줄게'라는 의미이며, 두 번째 회전에서도 여전히 use=0이라면 '이제 내보내자'는 의미다.

 

장점

• 구현 간단 (원형 큐 + 비트 하나)
• 완벽한 LRU에 근접한 성능
• 하드웨어 지원 덕분에 CPU 오버헤드 적음

 

 

 

Clock algorithm은 LRU와 비슷한 성능을 낸다.

 

 

Dirty Page: Modified Clock

LRU나 Clock 알고리즘은 단순히 "얼마나 오래됐는가"만 보지만, 현실에서는 페이지가 수정되었는지(Dirty 여부) 도 중요하다.

 

Dirty Page란?

• 페이지가 메모리에서 수정되었지만, 디스크에는 반영되지 않은 상태
• 디스크로 내보내려면(write-back) I/O가 필요하므로 교체 비용이 크다

 

Clean Page	수정되지 않음	빠름 (바로 버림)
Dirty Page	수정됨	느림 (디스크 쓰기 필요)

 

 

하드웨어 도움: Modified Bit (Dirty Bit) 를 활용한 Modified Clock

Clock 알고리즘을 개선해 깨끗한 페이지를 우선 교체하는 방식이다.

1. use=0, clean → 바로 교체
2. use=0, dirty → 후보 없을 시 교체
3. 그 외 (use=1) → use=0으로 초기화 후 패스

 

결과적으로 I/O 비용을 최소화하면서 LRU에 근접한 효율을 달성한다.

 

 

 

---

 

 

 

그 밖의 가상 메모리 정책들

페이지 교체 외에도, 운영체제는 여러 정책을 함께 사용한다. 대표적으로 언제 페이지를 불러올지 / 어떻게 디스크에 쓸지를 결정하는 정책들이다.

 

1. Demand Paging (요구 페이징)

• 페이지를 실제로 접근하는 순간에 로드
• 즉, 처음에는 디스크에 있고, 접근 시점에만 메모리로 가져옴
• 장점: 메모리 낭비 최소화 / 단점: 첫 접근 시 page fault 발생

"필요할 때만 불러온다(On-Demand)" 

 

 

2.  Prefetching (사전 적재)

• OS가 다음에 쓸 페이지를 미리 예측해 불러옴
• 예: 페이지 3을 불렀다면, 바로 옆 페이지 4도 함께 불러오기
• 연속적인 접근(Sequential Access)에서 매우 효과적

 

예측이 틀리면 오히려 메모리 낭비가 된다. 그래서 정확한 패턴 예측이 가능한 경우에만 사용된다.

 

3. Clustering / Grouping (클러스터링, 그룹 쓰기)

• 페이지를 하나씩 디스크에 쓰는 대신, 여러 개의 Dirty 페이지를 묶어 한 번에 기록
• 디스크는 순차적 쓰기(sequential write) 가 훨씬 빠르기 때문에, 이렇게 하면 I/O 효율이 크게 향상된다.

 

 

Thrashing (스래싱)

이 모든 정책이 잘 작동하려면, 각 프로세스의 Working Set(활발히 사용되는 페이지 집합)이 물리 메모리 안에 들어가 있어야 한다.

 

하지만 메모리가 부족하면? OS는 페이지 교체에 너무 많은 시간을 쓰게 되고, CPU는 대기 상태에 빠진다.
이게 바로 Thrashing (스래싱) 현상이다.

 

스래싱의 결과

• 디스크 I/O 폭증
• CPU 사용률 급감
• 전체 시스템 느려짐 (거의 멈춘 것처럼 보임)

 

해결책

1. Admission Control
→ 동시에 실행되는 프로세스 수를 줄인다. (적은 수의 프로세스만 실행)

2.Out-of-Memory Killer
→ 메모리를 과도하게 사용하는 프로세스를 강제 종료한다.

 

 

 

 

 

출처: 경북대학교 한명균 교수님, “운영체제” 강의 자료