[OS] 페이지 교체 알고리즘, 워킹셋, 스래싱 - 14

페이지 교체 알고리즘, 워킹셋, 스래싱 — RAM 관리가 무너지면 어떻게 되는가

이전 글에서 페이지 부재(Page Fault)가 발생하면 OS가 디스크에서 페이지를 가져온다고 했다. 그런데 RAM이 꽉 찼을 때 어떤 페이지를 내쫓을지, 그리고 그게 계속 잘못되면 시스템 전체가 어떻게 멈추는지까지 이어서 정리한다.

💡 이 글의 흐름: 어떤 페이지를 내쫓을까(교체 알고리즘) → 프로세스가 실제로 자주 쓰는 페이지 묶음이 있다(지역성 / 워킹셋) → 그게 RAM에 다 못 올라오면 시스템이 멈춘다(스래싱)

1. 페이지 교체 알고리즘 — 누구를 내쫓을까

RAM이 꽉 찬 상태에서 새 페이지를 가져와야 할 때, OS는 기존 페이지 중 하나를 디스크로 밀어내야 한다. 이때 "어떤 페이지를 골라서 내쫓을지" 결정하는 방법이 페이지 교체 알고리즘이다. 잘못 고르면 방금 내쫓은 페이지를 다시 불러오는 일이 반복되고, 그게 누적되면 시스템이 버벅인다.

OPT — 최적 교체

앞으로 가장 오래 사용되지 않을 페이지를 내쫓는다. 이론적으로 가장 성능이 좋다.

문제는 미래를 알아야 한다는 것. 실제 구현이 불가능해서 다른 알고리즘의 성능 비교 기준으로만 쓴다.

이론용 기준선

FIFO — 선입선출

가장 먼저 들어온 페이지를 내쫓는다. 구현이 단순하고 이해하기 쉽다.

단점: 오래됐다고 안 쓰는 게 아니다. RAM을 늘렸는데 오히려 페이지 부재가 더 늘어나는 벨레이디의 모순이 발생하기도 한다.

단순 구현

LRU — 최근 미사용

가장 오래 전에 마지막으로 사용된 페이지를 내쫓는다. 최근에 쓴 것은 곧 또 쓸 가능성이 높다는 원리다.

현실적으로 구현하려면 각 페이지마다 사용 시각을 기록해야 해서 하드웨어 지원이 필요하고 오버헤드가 있다.

현실 근접

LFU — 최소 빈도

사용 횟수가 가장 적은 페이지를 내쫓는다.

문제: 실행 초기에 집중적으로 쓴 페이지가 이후엔 안 쓰여도 높은 카운트를 유지해 남아있고, 방금 올라온 새 페이지가 먼저 쫓겨나는 역설이 생긴다.

카운터 기반

NUR — 최근 미참조

LRU의 근사판. 각 페이지에 참조 비트(최근에 썼나)와 변경 비트(내용을 바꿨나) 두 개만 두고, 이 조합으로 내쫓을 순위를 정한다.

LRU보다 오버헤드가 훨씬 적어 현실적인 타협안이다.

경량 LRU 근사

SCR — 2차 기회

FIFO를 보완한 방식. 내쫓으려고 골랐는데 참조 비트가 1이면 한 번의 기회를 더 준다(비트를 0으로 초기화하고 큐 맨 뒤로). 다음번에도 0이면 그때 내쫓는다.

자주 쓰는 페이지는 계속 기회를 받아 살아남는 구조다.

현실 사용

FIFO vs LRU — 같은 상황에서 어떻게 다른가

요청 순서가 4 → 3 → 2 → 1 → 4 → 3 → 5 → 4 → 3 → 2 → 1 → 5이고 RAM에 페이지 3개를 담을 수 있다고 하면, 두 알고리즘의 차이를 직접 볼 수 있다.

요청 순서

4

3

2

1

4

3

5

4

3

2

1

5

FIFO (프레임 3개) — 페이지 부재 9회

프레임 1

4

4

4

1

1

1

5

5

5

2

2

2

프레임 2

—

3

3

3

4

4

4

4

4

4

1

1

프레임 3

—

—

2

2

2

3

3

3

3

3

3

5

! = 페이지 부재 발생. FIFO는 "오래됐다 = 쓸모없다"고 가정하지만 틀릴 때가 많다.

LRU (프레임 3개) — 페이지 부재 8회 (FIFO보다 1회 적음)

프레임 1

4

4

4

1

4

4

5

4

4

2

1

5

프레임 2

—

3

3

3

3

3

3

3

3

3

3

3

프레임 3

—

—

2

2

2

2

2

2

2

2

2

2

LRU는 "최근에 쓴 것 = 곧 또 쓸 것"이라는 가정이 현실에 더 잘 맞는다.

알고리즘	기준	현실 사용	단점
OPT	미래에 가장 안 쓸 것	❌ 불가능	미래를 알 수 없음
FIFO	가장 먼저 들어온 것	⚠️ 단순한 환경	벨레이디의 모순
LRU	가장 오래 전에 쓴 것	✅ 근사 구현	하드웨어 오버헤드
LFU	사용 횟수 가장 적은 것	⚠️ 제한적	초기 집중 사용 왜곡
NUR	참조/변경 비트 조합	✅ 경량 LRU 대안	정밀도 낮음
SCR	FIFO + 2차 기회	✅ 실제 OS 사용	FIFO 기반 한계

2. 지역성(Locality) — 왜 LRU가 잘 통하는가

LRU가 현실에서 잘 동작하는 이유가 있다. 프로그램은 메모리를 무작위로 접근하지 않는다. 어떤 코드나 데이터에 접근하면, 그 주변을 계속 접근하는 경향이 있다. 이것을 메모리의 구역성(Locality)이라고 한다.

⏱ 시간 구역성 (Temporal Locality)

방금 접근한 것은 곧 다시 접근할 가능성이 높다.
한 번 쓴 변수나 함수는 반복해서 쓰이는 경우가 많다.

예: for 루프 안의 변수 i, 자주 호출되는 함수, 캐시에 올라간 게임 오브젝트 데이터

📍 공간 구역성 (Spatial Locality)

지금 접근한 주소의 근처도 곧 접근할 가능성이 높다.
코드는 순서대로 실행되고, 배열은 연속으로 읽힌다.

예: 배열 순회, 순차적 코드 실행, 구조체 필드 접근, 텍스처 샘플링

이 구역성 덕분에 가상기억장치가 성립한다. 프로그램 전체를 RAM에 올리지 않아도, 지금 쓰는 근처만 올려두면 대부분의 접근이 RAM 안에서 해결된다. 캐시 메모리도 같은 원리로 작동한다. 구역성이 높을수록 페이지 부재가 적고, 낮을수록(무작위 접근이 많을수록) 페이지 부재가 잦아진다.

3. 워킹셋(Working Set) — 지금 이 프로세스가 필요한 최소한

지역성을 좀 더 실용적으로 표현한 개념이 워킹셋이다. 한 프로세스가 일정 시간 동안 자주 접근하는 페이지들의 집합을 워킹셋이라고 한다. 게임으로 비유하면 지금 플레이 중인 맵과 캐릭터 데이터 — 당장 필요한 것들의 묶음이다.

워킹셋 개념 — 시간이 지나면서 필요한 페이지 집합이 바뀐다

시점 T1 — 워킹셋 {1, 2, 3}

1

2

1

3

2

3

RAM에 {1, 2, 3}만 있으면 OK

시점 T2 — 워킹셋이 {3, 4, 5}로 이동

1

2

3

4

5

4

이제 {3, 4, 5}가 필요

워킹셋보다 적은 프레임이 할당되면 → 계속 페이지 부재 → 스래싱 시작
워킹셋이 바뀌었는데 교체가 안 되면 → 죽은 페이지가 자리 차지 → 역시 문제

워킹셋의 핵심은 각 프로세스에 워킹셋만큼의 프레임은 반드시 보장해줘야 한다는 것이다. 그 아래로 내려가면 페이지 부재가 폭발적으로 늘어난다. 반대로 여유 있게 줄 수 없는 상황에서 프로세스가 너무 많이 동시에 실행되면 전체 시스템이 무너진다 — 이게 스래싱이다.

4. 스래싱(Thrashing) — 교체만 하다가 실제 일을 못 하는 상태

스래싱은 페이지 교체가 너무 자주 발생해서 실제 작업보다 페이지 불러오는 시간이 더 많아지는 현상이다. CPU는 쉬지 않고 돌아가는 것처럼 보이지만, 실제로는 페이지 부재 처리와 디스크 I/O만 반복하느라 아무것도 못 하는 상태다.

동시에 실행되는 프로그램 수 vs CPU 실제 활용도

CPU 실제 활용도

스래싱 포인트

동시에 실행 중인 프로그램 수 →

프로그램이 늘어날수록 CPU 활용도도 같이 올라가다가, 어느 시점을 넘으면 급격히 추락한다. 이 지점이 스래싱 포인트다. 프로그램이 많아질수록 각 프로세스에 돌아가는 RAM 프레임이 줄어들고, 워킹셋을 담기 부족해지면서 페이지 부재가 폭발한다.

✅ 정상 상태

각 프로세스가 워킹셋만큼의 프레임을 확보하고 있다.

페이지 부재가 가끔 발생하지만 빠르게 해결된다.

CPU는 실제 계산을 하느라 바쁘다.

❌ 스래싱 상태

모든 프로세스의 프레임이 워킹셋보다 부족하다.

A가 B 페이지를 내쫓으면, B가 C를 내쫓고, C가 A를 내쫓는 연쇄가 반복된다.

CPU 사용률 수치는 높지만 실제 일은 거의 0.

스래싱 대응 — OS가 할 수 있는 것

워킹셋 모니터링

→

프레임 부족 감지

→

일부 프로세스 일시 중단

→

남은 프로세스에 프레임 재분배

스래싱이 발생하면 OS는 프로세스 수를 줄이는 방향으로 대응한다. 일부 프로세스를 통째로 디스크에 내리고(스왑 아웃), 남은 프로세스들이 충분한 프레임을 확보할 수 있게 한다. 또한 프리페이징(Pre-paging)으로 워킹셋에 들어갈 것 같은 페이지를 미리 올려 초기 페이지 부재를 줄이기도 한다.

5. Unity 개발자 입장에서 보면

🎮 게임 개발에서 만나는 같은 문제들

스래싱과 워킹셋 개념은 OS 수준에서만 일어나는 게 아니다. Unity 개발에서도 같은 패턴이 반복된다.

• GC 스파이크 = 작은 스래싱: Managed Heap에서 GC가 너무 자주 돌면 실제 게임 로직 실행이 밀린다. 페이지 교체 연쇄처럼, GC가 메모리 정리하느라 프레임 처리를 못 하는 구조다. new를 매 프레임 남발하면 이 현상이 심해진다.
• 에셋 로딩의 워킹셋: 지금 플레이 중인 씬에서 필요한 텍스처, 메시, 사운드가 워킹셋이다. 이게 VRAM + RAM을 초과하면 계속 에셋을 로드/언로드하는 스래싱이 발생한다. Addressables로 씬 단위 워킹셋을 관리하는 게 정석이다.
• 구역성을 활용하는 NativeArray: NativeArray<T>는 연속 메모리라 공간 구역성이 높다. Burst + Job System과 조합하면 캐시 히트율이 높아지고 실질적인 처리량이 올라간다. 반면 흩어진 참조형 객체들은 공간 구역성이 낮아 캐시 미스가 잦다.

// ❌ 매 프레임 할당 — GC 스파이크 유발 (작은 스래싱)
void Update() {
    var list = new List<Enemy>(); // 매 프레임 GC 압박
}

// ✅ 구역성 활용 — 연속 메모리, 캐시 친화
using var positions = new NativeArray<float3>(count, Allocator.TempJob);
// 한 번에 쭉 처리 → 공간 구역성 높음 → 빠름

📎 용어 설명

1. 벨레이디의 모순(Belady's Anomaly) — FIFO에서 프레임 수를 늘렸는데 오히려 페이지 부재가 증가하는 역설적 현상. LRU에서는 발생하지 않는다.
2. 참조 비트(Reference Bit) — 각 페이지에 붙는 플래그. 최근에 접근되면 1, OS가 주기적으로 0으로 초기화. NUR/SCR이 이를 활용한다.
3. 프리페이징(Pre-paging) — 프로세스 시작 시 워킹셋에 들어갈 것 같은 페이지를 미리 RAM에 올려두는 기법. 초기 페이지 부재 폭탄을 완화한다.

페이지 교체 알고리즘 LRU 워킹셋 스래싱 지역성 운영체제 Unity