31. 페이지 교체 알고리즘

1. 페이지 교체 알고리즘 개요

프로세스가 요구한 페이지가 메모리에 없을 때 페이지 부재가 발생한다. 이 때 메모리 관리자는 스왑 영역에 있는 페이지를 가져와야 하는데, 메모리가 꽉 차있을 경우 기존 페이지를 스왑 영역으로 내보내야 한다. 이 때, 스왑 영역으로 내보낼 페이지를 결정하는 알고리즘을 페이지 교체 알고리즘이라고 한다.

 

좋은 페이지 교체 알고리즘은 앞으로 사용할 가능성이 적은 페이지를 스왑 영역으로 보내 페이지 부재를 줄이고 시스템의 성능을 향상시킨다.

 

 

좋은 페이지 교체 알고리즘

알고리즘의 성능을 평가하기 위해선 여러 가지를 고려해야 한다. 페이지 부재 횟수, 평균 대기 시간, 전체 작업 시간, 페이지 성공 횟수 등을 기준으로 평가할 수 있겠다.

 

 

 

2. 페이지 교체 알고리즘 종류

무작위 페이지 교체 알고리즘

무작위로 대상 페이지 선정하여 내보낸다.

 

 

FIFO

메모리에 올라온 지 가장 오래된 페이지를 내보낸다.

 

 

LRU

사용한 지 가장 오래된 페이지를 내보낸다.

 

 

LFU

사용 빈도가 가장 적은 페이지를 내보낸다.

 

 

NUR

최근에 사용한 적이 없는 페이지를 내보낸다. 페이지에 접근하면 1이 되는 참조 비트와 페이지가 변경되면 1이 되는 변경 비트를 이용해 구현한다.

 

두 비트는 쌍을 이루는데, (0, 0) 이런 식이다. 우선순위는 다음과 같다.

 

(0, 0) => (0, 1) => (1, 0) => (1, 1)

 

낮은 우선순위부터 차례로 해당하는 페이지가 있는지 검사한다. 있으면 그 페이지를 내보내며 여러 개일 경우 무작위로 선정한다. 모든 페이지가 (1, 1)일 경우에는 모든 페이지를 (0, 0)으로 초기화한다.

 

 

FIFO 변형

페이지 적중에 성공하면 큐의 맨 뒤로 보내는 2차 기회 페이지 교체 알고리즘과 원형 큐를 이용해 페이지를 순환하며 페이지 적중 시 참조 비트를 바꿔 기회를 한 번 더 부여하는 시계 알고리즘이 있다.