페이지 교체 알고리즘
- 페이지 교체 기법은 새로이 적재될 페이지를 위한 주기억장치 공간을 확보하기 위하여, 현재 주기억장치를 차지하고 있는 페이지들 중에서 어떤 페이지를 선택하여 가상 공간으로 보낼 것인가를 결정하는 기법
FIFO(First-In First-Out) 알고리즘
- 페이지가 교체될 필요가 있을 때 가장 먼저 주기억장치에 들어와 있는 페이지와 교체시키는 방법
- FIFO 알고리즘
- 각 페이지가 주기억장치로 들어올 때마다 타임-스탬프(time-stamp)를 찍어 사용
- 장점
- 단점
- 중요하게 계속 사용되고 있는 주기억 공간의 페이지가 오랫동안 페이지 프레임을 차지하였다는 이유 하나만으로 교체
- FIFO 모순 (Belady의 이변)
- 일반적으로 어떤 프로세스에게 더 많은 기억 공간을 확보하여 줌으로써 그 프로세스의 실행이 개선되기를 기대
- 즉, 어떤 프로세스에 할당된 페이지 프레임 수의 증가하면 페이지 부재의 수가 감소할 것으로 알고 있음
- 그러나 FIFO 페이지 교체 방법 하에서, 어떤 페이지 호출에서는 프로세스에 할당된 페이지 프레임의 수가 증가될 때 현실적으로 페이지 부재가 더 증가하는 현상
최적 교체(Optimal Replacement) 알고리즘
- 앞으로 가장 오랫동안 사용되지 않을 페이지를 교체
- 최소의 페이지 부재율을 가지는 알고리즘
- 최적 교체 알고리즘
- 페이지 호출 순서에 대한 모든 상황을 사전에 미리 파악하고 있어야 하기 때문에 다루기 어렵고 비현실적(단점)
LRU(Least Recently Used) 알고리즘
- 현시점에서 가장 오래 전에 사용된 페이지를 제거하는 방법
- 한 프로세스에서 사용되는 각 페이지마다 타임-스탬프용 카운터 및 스택을 두어 현시점에서 가장 오래 전에 사용된 페이지를 제거
- 카운터에 의한 방법은, 어떤 페이지에 대한 참조가 있을 때마다 그 시간 레지스터의 내용은 페이지 테이블 내에 있는 사용 시간 필드에 복사
- 즉, 새로운 페이지가 호출되면 각 페이지 테이블 항목과 연관된 사용 시간 레지스터 값을 탐색하여 가장 작은 값을 가진 페이지와 교체
2차 기회(second chance) 알고리즘
- 페이지 테이블의 각 항목에 한 개의 참조 비트를 연관시킨 후, 처음에 운영체제에 의해 모든 참조 비트는 0로 됨
- 그 후 한 프로세스가 수행되면서 참조한 각 페이지와 관계된 비트는 값이 1로 바뀜
- 페이지 교체를 위하여 페이지의 참조 비트를 조사하여 그 값이 0이면 그 페이지를 교체하고, 참조 비트가 1이면 그 페이지에게 2차 기회를 주고 다음 페이지를 조사하기 위하여 FIFO 방식으로 진행
- 2차 기회 알고리즘
- 어떤 페이지가 2차 기회를 얻었다면 그것의 참조 비트는 0이 되고 그것의 현재 시간이 도착 시간으로 수정
- 그리하여 2차 기회가 주어진 페이지는 다른 페이지들이 교체되거나 2차 기회가 주어질 때까지 주기억장치에 남아있게 됨
- 또 빈번히 사용된 페이지가 있다면 그 페이지는 결코 교체되지 않을 것임
LFU(Least Frequently Used) 알고리즘
- 각 페이지의 사용이 얼마나 집중적으로 되었는가에 관심을 갖고, 가장 적게 사용되거나 집중적이 아닌 페이지가 대체됨
- 처음엔 많이 사용되다가 나중에 사용되지 않는 페이지가 계속 메모리에 남게 되는 모순이 있는데, MFU(Most Frequently Used)에 의해 해결
NUR(Not Used Recently) 알고리즘
- 최근에 사용되지 않은 페이지는 가까운 미래에 사용되지 않는 경향에 따라 그것들 을 참조되는 페이지와 교체
- 각 페이지에 대해 두 개의 하드웨어 비트를 첨가
- 참조된 비트=0 : 그 페이지가 참조되지 않았을 경우
참조된 비트=1 : 그 페이지가 참조되었을 경우
- 변형된 비트=0 : 그 페이지가 변형되지 않았을 경우
변형된 비트=1 : 그 페이지가 변형되었을 경우
- 페이지 교체 시 참조 비트가 0인 페이지를 찾음
-> 만일 모든 페이지의 참조 비트가 1일 때는 변형 비트가 0인 것을 찾음
- 다중 사용자 환경에서는 가까운 시간 안에 모든 참조 비트가 1이 됨
-> 주기적으로 모든 참조 비트를 0으로 세트 시켜 해결
