페이지 교체 알고리즘

페이지 교체 알고리즘 정리

알고리즘	교체 대상	기반 원리
FIFO	가장 먼저 메모리에 들어온 페이지	선입선출
LRU	가장 오랫동안 사용되지 않은 페이지	시간 지역성
LFU	참조 횟수가 가장 적은 페이지	참조 빈도

페이지(Page)란?

페이지는 가상 메모리를 사용하는 시스템에서 메모리를 관리하는 고정된 크기의 블록이다.

가상 메모리는 페이지 단위로 나뉘고, 이 페이지들이 물리 메모리(RAM)의 프레임에 연결(매핑)되어야 실행될 수 있다.

페이지 부재(Page Fault)

프로세스가 특정 페이지를 사용하려고 할 때, 해당 페이지가 RAM에 없는 경우를 Page Fault라고 한다.

Page Fault 과정

1. CPU는 운영체제(OS)에 제어권을 넘긴다.
2. 운영체제는 보조기억장치(HDD, SSD)에서 필요한 페이지를 찾는다.
3. RAM에 비어있는 프레임이 있다면 해당 페이지를 가져온다.
4. 만약 비어있는 프레임이 없다면, 기존에 페이지 중 하나를 보조기억장치로 보내고(swap-out), 그 공간에 새로운 페이지를 가져온다.(swap-in)

이떄 어떤 페이지를 내보낼지를 결정하는 규칙을 페이지 교체 알고리즘이라고 한다.

주요 페이지 교체 알고리즘

FIFO (First-In, First-Out)

RAM에 가장 먼저 들어온 페이지를 가장 먼저 내보내는 알고리즘

• 장점 : 구현이 간단하다.
• 단점 : 자주 사용되는 페이지임에도 먼저 들어온다면 교체될 수 있어서 비효율적일 수 있다.(Belady의 모순 : 프레임 수를 늘렸는데도 페이지 부재가 더 많이 발생하는 현상)

LRU (Least Recently Used)

가장 오랫동안 사용되지 않은 페이지를 교체하는 알고리즘

• 장점 : FIFO에 비해 페이지 부재율이 낮고, 일반적으로 좋은 성능
• 단점 : 각 페이지의 최근 사용 시간을 기록해야 하므로, 부담이 크고 구현이 복잡

LFU (Least Frequently Used)

참조 횟수가 가장 적은 페이지를 교체하는 알고리즘

• 장점 : LRU가 잡아내지 못하는 장기적인 참조 패턴 고려 가능
• 단점 : 참조 횟수를 계산하기 위한 오버헤드가 크고, 초기에만 많이 사용된 경우 계속 메모리에 남아있을 수 있다.