페이지 교체 알고리즘인 FIFO, LRU, Clock은 각각 어떤 기준으로 교체 대상을 고르나요?

이렇게 답해 보세요 (핵심 답변)

물리 프레임이 부족할 때 FIFO는 가장 먼저 들어온 페이지를, LRU는 가장 오랫동안 참조되지 않은 페이지를 우선 교체합니다. 정확한 LRU는 매 메모리 접근마다 순서를 갱신하는 비용이 크기 때문에, 실제 운영체제는 참조 비트(Reference Bit)를 순환하며 확인하는 Clock 알고리즘 등으로 LRU를 근사해 구현합니다. 미래에 가장 늦게 쓰일 페이지를 빼는 최적(Optimal) 교체는 실시간 구현이 불가능한 비교 기준이며, 실제 커널은 수정된 페이지(Dirty Page)의 디스크 기록 비용과 워크로드도 함께 고려합니다.

함께 설명하면 좋은 이유 (꼬리질문 대비)

1. 정확한 LRU 순서를 매 메모리 접근마다 자료구조로 유지하려면 메타데이터 갱신 비용이 만만치 않게 듭니다.
2. 단순 FIFO 정책은 물리 프레임 수를 늘렸는데도 오히려 페이지 폴트가 더 많이 발생하는 Belady의 모순(Belady's Anomaly)이 생길 수 있습니다.

면접에서 자주 하는 실수

교과서의 단순 알고리즘 하나가 현대 운영체제 커널의 전체 페이지 교체·메모리 회수 정책 그대로라고 말하면 안 됩니다.