페이지 교체

모든 메모리가 사용 중이어서 빈 프레임이 없는 경우 페이지 교체가 필요하다.

 

 

기본적인 페이지 교체

만약 빈 프레임이 없다면 현재 사용되고 있지 않은 프레임을 찾아 그것을 비워버린다.

그리고 페이지 테이블을 변화시킴으로써 프레임을 비어 있게 한다.

 

이 때 페이징 시스템은 두 가지 중요한 문제를 해결해야 한다.

그것은 프레임 할당 알고리즘과 페이지 교체 알고리즘이다.

즉 여러 프로세스가 존재하는 경우 얼마나 많은 프레임을 할당해야 할 지, 어떤 페이지를 교체해야 할 지를 결정해야 한다.

일반적으로 페이지 부재율이 가장 낮은 페이지 교체 알고리즘을 선정한다.

 

페이지 교체 알고리즘의 성능은 특정 메모리 참조 나열에 대해 알고리즘을 적용하여 페이지 부재 발생 횟수를 계산하여 평가한다.

이 때 메모리 주소의 나열을 참조열 이라고 한다.

 

 

FIFO 페이지 교체

가장 간단한 페이지 교체 알고리즘으로 메모리에 올라온 지가 가장 오래된 페이지를 비운다.

 

Belady의 모순 : 프레임을 더 주었는데 오히려 페이지 부재율은 더 증가하는 현상

 

 

최적 페이지 교체

앞으로 가장 오래 사용되지 않을 페이지를 찾아 교체한다.

앞으로 가장 오랫동안 사용되지 않을 페이지를 알 수 없으므로 구현이 불가능하다.

연구 목적이나 다른 알고리즘과의 비교 목적으로 사용된다.

 

 

LRU 페이지 교체

최근의 과거를 가까운 미래의 근사치로 추정해 가장 오랫동안 사용되지 않은 페이지를 교체한다.

LRU 페이지 교체 알고리즘은 하드웨어의 지원이 필요 하다.

 

계수기 : 각 페이지 항목은 계수기를 가지고 페이지 참조시 계수기를 증가시킨다.

페이지 교체 시 가장 작은 값의 계수기를 갖는 페이지를 교체한다.

 

스택 : 페이지 번호의 스택을 유지하고 페이지가 참조될 때마다 페이지 번호를 스택 꼭대기에 놓는다.

 

 

LRU 근사 페이지 교체

LRU 교체 알고리즘은 하드웨어 오버헤드가 크다. 이런 문제를 해결하기 위해 LRU 근사 페이지 교체 방식이 사용된다.

부가적 참조 비트 알고리즘 : 일정한 시간마다 참조 비트들을 기록함으로써 추가적인 선후관계 정보를 얻을 수 있다.

2차 기회 알고리즘 : 페이지가 선택될 때 참조 비트를 확인하고 참조 비트가 0 일 경우 페이지를 교체하고 1이면 다시 한 번 기회를 주는 방식이다.

 

개선된 2차 기회 알고리즘

참조 비트와 변경 비트 두개의 비트를 조합해서 등급을 설정한다.

페이지 교체 시 가장 낮은 등급을 가지면서 처음 만난 페이지를 교체한다.

 

 

계수-기반 페이지 교체

LFU 알고리즘 : 참조 횟수가 가장 적은 페이지를 교체한다.

MFU 알고리즘 : 참조 횟수가 가장 많은 페이지를 교체한다.