페이지 교체 알고리즘
- 운영체제는 프로세스가 필요로 하는 데이터를 메모리(RAM)에서 관리
- 메모리 용량은 제한되어 있기 때문에, 모든 데이터를 한 번에 메모리에 올려놓을 수 없는 경우가 발생
- 이럴 때, 페이지라는 단위로 데이터를 관리하고, 필요할 때 페이지 교체(Page Replacement) 를 통해 메모리에 올리거나 내리게 됨
- 페이지 교체는 메모리가 꽉 찼을 때 새로운 페이지를 메모리에 로드하기 위해 기존의 페이지를 내리는 작업을 의미
- 어떤 페이지를 내릴지 결정하는 것이 페이지 교체 알고리즘의 역할
스왑 영역(Swap Space)
- 물리적인 메모리(RAM) 용량이 부족할 때 사용되는 디스크 공간
- 하드 드라이브나 SSD에 위치
- 운영체제가 주 메모리에서 사용되지 않는 데이터를 일시적으로 저장하기 위해 사용
- 역할
- 가상 메모리 확장
- 메모리 부족 시 지원
- 프로세스 일시 정지 - 동작 방식
- 페이지 아웃(Page Out) : 사용되지 않거나 덜 사용되는 메모리 페이지를 스왑 영역으로 옮김
- 페이지 인(Page In) : 필요할 때, 운영체제는 스왑 영역에 있는 페이지를 RAM으로 불러옴
- 페이지 폴트(Page Fault) : 프로세스가 필요한 데이터를 메모리에서 찾지 못했을 때 발생하며, 이때 운영체제는 스왑 영역에서 해당 데이터를 찾아 RAM으로 가져옴
대표적인 페이지 교체 알고리즘
-
FIFO (First In, First Out)
- 가장 먼저 메모리에 올라온 페이지를 가장 먼저 내리는 방식
- 큐(Queue) 구조로 관리
- 구현이 단순하고 직관적
- 벨라디의 모순(페이지 프레임을 늘려도 페이지 폴트(Page Fault)가 오히려 증가하는 현상) 발생
-
LRU (Least Recently Used)
- 최근에 사용된 페이지는 앞으로도 사용할 가능성이 높다는 가정에 기반하여, 가장 오랫동안 사용되지 않은 페이지를 교체하는 방식
- 일반적으로 효율적이며, 현실 세계의 메모리 접근 패턴과 잘 맞음
- 구현이 복잡하며, 페이지 접근 시간이나 순서를 기록하는 오버헤드 발생
-
LFU (Least Frequency Used)
- 사용 빈도가 높은 페이지는 앞으로도 사용할 가능성이 높다는 가정에 기반해, 사용 빈도가 가장 적은 페이지를 교체하는 방식
- 특정 페이지가 자주 사용될 경우, 메모리에서 오래 유지됨
- 오래된 페이지가 빈도 수가 높다는 이유로 계속 유지될 수 있어 비효율적
- 이를 방지하기 위해 사용 빈도를 시간에 따라 감소시키는 방식도 이용
-
Optimal (OPT)
- 앞으로 가장 오랫동안 사용되지 않을 페이지를 교체하는 방식
- 이론상 가장 효율적이지만 실제 구현은 불가능
-
Clock(Second Chance)
- FIFO 알고리즘을 개선한 방식으로, 각 페이지에 참조 비트를 두어 해당 페이지가 최근에 사용되었는지를 판단하고, 사용되지 않은 페이지만 교체 대상이 됨
- FIFO에 비해 복잡하지만, LRU와 비슷한 성능을 내면서도 구현이 비교적 간단
