Page Replacement Policy

말 그대로 페이지 교체 정책입니다. 운영체제가 메모리 부족 상황에서 어떤 페이지를 제거할지 결정하는 전략입니다.

필요성

운영체제는 가상 메모리 덕분에 물리 메모리보다 큰 주소 공간을 다룰 수 있습니다. 하지만 모든 페이지를 동시에 물리 메모리에 유지할 수 없기 때문에, 새로운 페이지를 메모리에 불러와야 할 때는 기존 페이지 중 일부를 제거해야합니다.
→ 여기서 어떤 페이지를 제거할지 결정하는 기준이 Page Replacement Policy 입니다.

정책 종류와 개념

4개의 정책 종류가 있습니다.

FIFO: 가장 오래된 페이지를 제거합니다.

LRU: 가장 오랫동안 사용되지 않은 페이지를 제거합니다.

Clock: FIFO를 순환 큐로 개선합니다. 사용 비트를 확인합니다.

Random: 무작위로 제거합니다.

→ 장단점을 포함해서 도표로 알아봅시다.

정책	설명	장단점
FIFO (First-In, First-Out)	가장 오래된 페이지를 제거	간단하지만 성능은 낮을 수 있음
LRU (Least Recently Used)	가장 오랫동안 사용되지 않은 페이지 제거	현실적인 모델이지만 구현 비용 ↑
Clock (Second Chance)	FIFO를 순환 큐로 개선, 사용 비트를 확인	LRU 근사치, 구현 쉬움
Random	무작위로 제거	실험적 용도, 간단하지만 예측 불가

Pintos에서…

Pintos 프로젝트에서는 자신만의 page replacement policy를 직접 구현해야 합니다.

해당 vm_evict_frame 코드에서 구현하면 됩니다.

static struct frame *
vm_evict_frame (void) {
/* 교체할 victim frame을 선택하고 반환 */
}

Pintos에서 권장하는 방식은 Clock Algorithm 입니다.

• struct frame이나 struct page에 accessed 비트 확인합니다.
• 한 번 스캔하면서 accessed == true면, false로 리셋합니다. (Second Chance)
• accessed == false면, victim으로 선택합니다.

정책 구현 시 고려할 사항들

고려 항목	설명
accessed 비트	하드웨어가 자동으로 세팅함 (TLB miss 시 유지)
thread 간 공유 여부	공유 페이지는 조심해서 관리해야 함
frame list 동기화	evict-frame은 여러 스레드에서 동시에 호출될 수 있음 → 락 필요
swap 연동	victim을 제거하기 전, 내용 저장 필요 (swap_out)

요약

항목	설명
Page Replacement이란?	메모리 부족 시 어떤 페이지를 제거할지를 결정하는 정책
주요 정책	FIFO, LRU, Clock, Random 등
OSTEP 관점	LRU 이상적이지만, Clock이 현실적인 대안
Pintos 구현	evict_frame()에서 Clock 방식으로 victim 선택 → swap 또는 삭제 수행
핵심 함수	pml4_is_accessed(), pml4_set_accessed(), swap_out() 등