페이지 교체는 물리 메모리가 부족할 때 기존 페이지 중 회수할 대상을 정해 새 페이지가 사용할 프레임을 확보하는 과정입니다. 다시 사용할 가능성이 낮은 페이지를 골라 Page Fault와 I/O 비용을 줄이는 것이 목적입니다.
| 알고리즘 | 교체 기준 | 특징과 한계 |
|---|---|---|
| FIFO | 메모리에 가장 먼저 들어온 페이지 | 단순하지만 자주 쓰는 페이지도 교체하며 Belady의 모순 가능 |
| OPT | 앞으로 가장 늦게 다시 사용할 페이지 | 이론적으로 최적이지만 미래를 알아야 하므로 비교 기준으로 사용 |
| LRU | 가장 오랫동안 사용하지 않은 페이지 | 시간 지역성을 활용하지만 정확한 접근 순서 관리 비용 발생 |
| LFU | 사용 횟수가 가장 적은 페이지 | 사용 빈도를 반영하지만 과거에 많이 사용된 페이지가 오래 남을 수 있으며, 사용 횟수 관리 비용 발생 |
| Clock | 참조 비트를 순회하며 최근 사용되지 않은 페이지 선택 | 참조 비트가 1이면 0으로 바꾸고 기회를 더 주며, LRU를 저렴하게 근사 |
교체 대상의 데이터가 변경되었다면 보존을 위한 기록이 필요할 수 있습니다. 따라서 참조 이력뿐 아니라 Dirty 여부와 회수 비용도 성능에 영향을 줍니다.
리눅스에서는 MGLRU를 사용하여 페이지를 관리하고 있습니다.
Belady의 모순은 무엇인가요?
같은 참조 순서에서 프레임 수를 늘렸는데 오히려 Page Fault가 증가하는 현상이며 FIFO에서 나타날 수 있습니다. 정확한 LRU와 OPT는 큰 프레임 집합이 작은 집합의 내용을 포함하는 성질이 있어 이 현상이 발생하지 않습니다.
페이지를 교체하면 항상 디스크에 기록하나요?
아닙니다. 수정되지 않았고 파일 등에서 다시 읽을 수 있는 페이지는 버려도 됩니다. 변경된 파일 페이지나 보존해야 하는 익명 페이지는 필요에 따라 파일 또는 스왑에 기록해야 합니다.
Thrashing은 어떻게 완화하나요?
실행보다 페이지를 내보내고 다시 읽는 데 시간을 과도하게 쓰는 현상입니다. 동시 실행 작업 수를 줄이거나 메모리를 늘리고, Working Set이 메모리에 머물도록 조정하며, 접근 지역성을 개선할 수 있습니다.
출처 및 참고자료
[운영체제] 페이지 교체 알고리즘패스트캠퍼스 운영체제 강의와 쉽게 배우는 운영체제 교재에 대한 TIL입니다. 저번 포스팅은 메모리 관리 작업 중 메모리 가져오기(Fetch) 정책에 관한 것이었다면, 이번 포스팅은 메모리 재배치(Replacement) 정책에 관한 것이다. 페이지 교체 알고리즘의 종류 페이지 교체 알고리즘의 핵심은 메모리에서 앞으로 사용할 가능성이 적은 페이지를 대상 페이지로 선정하여 페이지 부재를 줄이고 시스템의 성능을 향상하는 것이다. 따라서, 이에 대한 구현 방식에 따라 아래와 같은 여러 종류의 페이지 교체 알고리즘이 만들어졌다. 앞으로 소개될 모든 페이지 교체 알고리즘은 아래 그림과 같은 메모리 접근 순서를 사용하고 물리 메모리는 3개의 프레임을 가졌다고 가정할 것이므로 참고하고 읽어주길 바란다. 페이지는 번호 대..
rob-coding.tistory.com