페이징 교체 알고리즘 이란?
페이지 교체 알고리즘(Paging Replacement Algorithm)은 페이징 기법으로 메모리를 관리하는 운영체제에서 페이지 부재(Page Fault)가 발생하여 새로운 페이지를 할당하기 위해 현재 할당된 페이지 중 어느 것과 교체할지를 결정하는 방법이다.
페이지 부재(Page Fault)는 실행중인 프로그램이 가상 메모리에 맵핑되었지만 실제 물리적 메모리에 로드되지 않은 메모리 페이지에 접근할 때 오류가 발생합니다. 물리적 메모리는 가상 메모리보다 작기 때문에 이러한 오류가 발생할 가능성이 높습니다. 이때 기존 페이지를 희생(Victim Page)하여 새로운 페이지를 교체하는 것이 페이징 교체 알고리즘입니다.
📘 Info
프레임: 물리 메모리를 일정 크기로 나눈 블록
페이지 : 가상 메모리를 일정한 크기로 나눈 블록
FIFO(First In First Out) 알고리즘
- 가장 먼저 메모리에 올라온 페이지를 가장 먼저 내보내는 알고리즘
- 구현은 간단하지만 성능에는 이점이 없음
- 들어온 시간을 저장 순서대로 저장하거나 큐를 이용해 저장
- 초기화 코드에 적절 할 수 있다
- Belady’s anomaly 현상이 발생할 수 있다
Belady’s anomaly란 페이지 프레임이 증가되어도 페이지 부재(Page Fault)가 줄어들지 않고 늘어나는 현상. FIFO알고리즘에서 3개의 슬롯에서 3, 2, 1, 0, 3, 2, 4, 3, 2, 1, 0, 4가 수행될 때 9번의 페이지 부재가 나타나지만 슬롯을 4개로 늘린다면 페이지 부재가 10개로 오히려 늘어난다.
OPT(Optimal) 알고리즘
- 가장 오랫동안 사용하지 않을 페이지를 교체
- 페이지 부재(Page Fault)가 알고리즘 중 가장 적으나 구현이 어렵다.
- 프로세스가 앞으로 사용할 페이지를 알아야함
LRU(Least Recently Uesd) 알고리즘
- 가장 오랫동안 사용하지 않은 페이지를 교체
- 최적 알고리즘과 비슷한 효과
- 많은 운영체제가 선택하는 성능이 좋은 알고리즘
- 기록을 TimeStamping에 오버헤드가 존재한다
MRU(Most Recently Used) 알고리즘
- 가장 참조 횟수가 많은 페이지를 교체하는 알고리즘
- Belady’s anomaly 현상이 일어날 수 있다
참고
노력하는 개발자입니다.