page 교체는 어떻게 동작하며, 무엇이 thrashing을 일으키는가?

Question

IT Interview Practice · Accepted Answer

물리 RAM이 가득 찼는데 프로세스가 더 많은 page를 필요로 하면, OS는 자리를 만들기 위해 상주 중인 page를 **축출(evict)**해야 한다 — dirty하다면 **swap**(디스크)에 기록한다. 어느 page를 축출할지가 **page 교체(page replacement)** 결정이며, 잘못하면 성능이 망가진다.

## 교체 정책

이론적 최적은 미래에 가장 나중에 쓰일 page를 축출하는 것(**Bélády의 OPT**)이다 — 미래를 볼 수 없으니 불가능하다. 그래서 우리는 **LRU(least recently used)**를 근사한다: 가장 오래 쓰이지 않은 page를 축출한다. 진짜 LRU는 모든 접근마다 타임스탬프가 필요해(너무 비쌈) 실제 kernel은 **clock(second-chance) 알고리즘**을 쓴다:

```text
Frames arranged in a ring; each has a REFERENCE bit the hardware sets on access.
A "hand" sweeps around the ring:
   ref bit = 1 → clear it, give the page a second chance, move on
   ref bit = 0 → evict THIS page (approximates "least recently used")

[1]→[1]→[0] ← evict here   (the sweep clears 1s until it finds a 0)
         ▲___________|
```

clock은 O(1) 비용으로 LRU 같은 결과를 준다. Linux는 **active/inactive LRU list**로 이를 더 정교화한다.

## working set과 thrashing

프로세스의 **working set**은 어떤 시간 창 안에서 그것이 활발히 쓰는 page의 집합이다. paging은 *결합된 working set들이 RAM에 들어맞는 한* 잘 동작한다. 들어맞지 않으면:

```text
working set > RAM → evict a page that's about to be needed → immediate page fault →
evict another needed page → ... → the CPU spends ~all its time paging to disk, ~0% on real work
                            = THRASHING
```

thrashing은 완만한 경사가 아니라 절벽이다: 한계를 조금만 넘어도 거의 모든 접근이 miss하기 때문에 throughput이 붕괴한다. 증상: CPU는 거의 유휴인데 디스크 I/O는 포화, 그리고 latency 폭발.

## 고치기 / 피하기

- **RAM 추가** 또는 **부하 감소**(동시 프로세스 줄이기)로 working set이 들어맞게 한다.
- scheduler는 프로세스 전체를 **suspend하고 swap-out**해 수요를 줄일 수 있다(medium-term scheduling).
- Linux의 **OOM killer**는 최후의 수단이다 — 영원히 thrash하느니 프로세스를 죽인다.
- **locality**를 개선해 working set 자체를 작게 만든다.

## 왜 중요한가

이는 메모리 이야기 전체를 하나로 묶으며, thrashing이 실제 production 실패 모드이기 때문에 senior가 즐겨 묻는 질문이다: N명의 사용자에서는 멀쩡하던 서비스가 working set이 RAM을 넘어서는 N+1에서 절벽으로 떨어진다. 그 특징(과도한 paging, 포화된 디스크, 멈춘 CPU)을 알아채고 지렛대(RAM, 부하 차단, locality — 그리고 swap이 메모리 부족을 latency 재앙으로 바꾼다는 사실)를 아는 것이, 몇 분 만에 진단하는 것과 이유 모를 멈춘 머신을 멍하니 바라보는 것의 차이다.

교체 정책

working set과 thrashing

고치기 / 피하기

왜 중요한가

관련 질문