운영체제 | Page Placement Policy

🥔 Page Replacement Policy란?

Page Replacement Policy는 가상 메모리 시스템에서 메모리가 부족할 때 어떤 페이지를 제거할지 결정하는 전략이다. 물리 메모리는 한정되어 있고, 새로운 페이지를 로드해야 하는데 빈 공간이 없다면, 기존에 있던 페이지 중 하나를 제거(evict)해야 한다.

운영체제는 이때 최적의 희생 페이지(victim page) 를 고르는 알고리즘을 사용하며, 이를 페이지 교체 정책(Page Replacement Policy) 라고 부른다.

🥔 페이지 교체가 발생하는 상황

1. 프로세스가 아직 메모리에 없는 페이지에 접근
2. 페이지 폴트(Page Fault) 발생
3. 물리 메모리(프레임)에 빈 공간이 없음
4. 운영체제가 기존 페이지 중 하나를 제거하고, 새로운 페이지를 로딩
5. 제거된 페이지가 변경된 경우, 디스크에 쓰는(write-back) 작업도 수행됨

🥔 대표적인 페이지 교체 알고리즘들

1. FIFO (First-In First-Out)

• 가장 먼저 들어온 페이지를 가장 먼저 제거
• 구현은 큐(Queue) 자료구조로 간단함
• ❌ 단점: 오래된 페이지가 아직도 자주 쓰일 수 있음

예시: [2, 3, 4]가 메모리에 있고 2가 가장 먼저 들어왔다면, 다음 교체 시 2가 제거됨

2. Optimal (OPT)

• 앞으로 가장 오랫동안 사용되지 않을 페이지를 제거
• 이론적으로 가장 적은 페이지 폴트를 발생시킴
• ❌ 단점: 미래를 알아야 하므로 현실에서는 구현 불가, 비교 기준으로만 사용

예시: 앞으로 한참 동안 안 쓸 페이지를 제거하는 완벽한 전략

3. LRU (Least Recently Used)

• 가장 오랫동안 사용되지 않은 페이지를 제거

• 과거의 사용 기록이 미래를 예측하는 데 도움이 된다는 가정

• 구현 방식:

  • 스택 또는 시간 스탬프로 추적
  • 최근 사용된 페이지는 가장 뒤로 보냄

자주 쓰이는 페이지는 메모리에 남기고, 한동안 사용되지 않은 페이지를 희생

4. Clock (Second Chance)

• LRU를 근사하기 위한 효율적인 방식
• 원형 큐를 사용하며, 각 페이지에 "참조 비트(reference bit)" 를 둔다
• 참조 비트가 1이면 두 번째 기회를 주고, 0이면 제거

시계 바늘처럼 포인터가 돌면서 교체할 후보를 찾음
성능과 정확성의 균형이 좋음

5. LFU (Least Frequently Used)

• 가장 적게 사용된 페이지를 제거
• 사용 횟수를 기반으로 판단
• ❌ 단점: 과거에 자주 쓰였던 페이지가 최근엔 쓰이지 않을 수도 있음

🥔 페이지 교체 정책 비교

정책	특징	장점	단점
FIFO	가장 먼저 들어온 페이지 제거	간단한 구현	Belady의 anomaly 발생 가능
OPT	미래 가장 늦게 사용될 페이지 제거	이론적으로 가장 적은 페이지 폴트	실제 시스템에는 구현 불가
LRU	최근에 사용 안 된 페이지 제거	성능 우수, 현실적인 근사 가능	구현 복잡도 높음
Clock	LRU 근사, 두 번째 기회 제공	성능과 구현의 균형	정밀한 LRU는 아님
LFU	사용 횟수 가장 적은 페이지 제거	자주 쓰는 데이터 유지 가능	오래된 데이터가 우선 유지될 수 있음

🥔 Belady’s Anomaly

FIFO 정책에서는 프레임 수를 늘렸는데도 페이지 폴트가 더 늘어나는 역설적인 현상이 발생할 수 있다.
이 현상을 Belady’s anomaly 라고 하며, LRU, OPT 등은 이 현상이 발생하지 않는다.

🥔 OS에서 실제 사용하는 정책은?

현대 운영체제에서는 정확한 LRU 구현이 어렵기 때문에 다음과 같은 하이브리드 방식이 사용된다:

• Linux: NRU(Not Recently Used), Aging, LRU Clock 등 LRU 변형 사용
• Windows: Working Set 기반의 Aging 알고리즘
• Pintos: Clock 알고리즘 기반의 Custom Page Replacement 구현 (Project 3에서 실습)

🥔 구현 시 고려사항

• 참조 비트 관리: 하드웨어(MMU)가 지원해주면 효율적, 없을 경우 소프트웨어로 추적
• 디스크 I/O 최소화: 페이지 교체 시 dirty bit 확인 후 write-back
• 멀티태스킹 환경: 프로세스마다 적절한 working set 관리가 필요

🥔 정리

• Page Replacement는 가상 메모리 시스템의 핵심 알고리즘이다.
• 정책에 따라 성능과 효율이 크게 달라진다.
• 현실에서는 LRU 근사 알고리즘(Clock 등)을 많이 사용한다.
• 테스트/과제에서 구현 시에는 교체 대상 페이지를 고르는 기준과 dirty/reference bit를 잘 다뤄야 한다.