페이지 교체 알고리즘이란?
페이지 부재가 발생했을때 새로운 페이지를 할당해야 하는데 현재 할당된 페이지 중 어떤것을 교체할지 결정하는 방법이다.
가상 메모리 페이징은 필요한 페이지만 메모리에 적재하고 사용하지 않는 부분은 그대로 둔다.
하지만 필요한 페이지만 올려도 메모리는 결국 가득 차게 되고, 올라와있던 페이지가 사용이 끝난 후에도 자리를 차지하고 있을 수 있다.
따라서 메모리가 가득 차면, 추가로 페이지를 가져오기 위해서 안쓰는 페이지는 out하고(디스크의 스왑 영역으로 보냄), 해당 공간에 현재 필요한 페이지를 in 시켜야 한다.
여기서 어떤 페이지를 out 시킬지 정해야 하는데 이 알고리즘의 목표는 페이지 부재율을 최소화 하는 것이기 때문에 가까운 미래에 참조될 가능성이 가장 적은 페이지를 선택해서 내보내는 것이 성능을 향상 시킬 수 있다.
페이지 교체 알고리즘의 종류
OPT(Optimal)
앞으로 가장 오랫동안 사용되지 않을 페이지 교체
- 가장 이상적이다.
- 프로세스가 앞으로 사용할 페이지를 미리 알아야 하므로 실제 시스템에서 사용할 수는 없는 알고리즘이다.
- 다른 교체 알고리즘과의 비교 척도로써의 역할을 한다.
FIFO(First in First out)
가장 먼저 들어온 페이지를 교체
- 들어온 시간을 저장하거나 올라온 순서를 큐에 저장하고, 페이지 부재 시 메모리에 가장 먼저 올라온 페이지를 먼저 교체하는 방식이다.
- 보통 프레임의 수가 많아질수록 페이지 결함의 횟수는 감소할 것이라 생각할 수 있지만, 물리적 공간이 늘어났음에도 성능이 더 나빠지는 경우도 있다. 이를 FIFO의 이상현상, Belady’s Anomaly(FIFO anomaly)라고 한다.
LRU(Least Recently Used)
가장 오랫동안 사용되지 않은 페이지를 교체
- FIFO의 이상 현상이 발생하지 않는다.
- 메모리 페이지의 참조 성향 중 시간 지역성을 고려한 알고리즘이다.
단점
프로세스가 주기억장치에 접근할 때마다 참조된 페이지 시간을 기록해야 하므로 막대한 오버헤드가 발생할 수 있다.
LFU(Least Frequently Used)
참조 횟수가 가장 적은 페이지 교체
- 만약 최저 참조 횟수를 가진 페이지가 여러 개면 임의로 하나를 선정해 out 시키는데, 성능 향상을 위해 그들 중 상대적으로 더 오래전에 참조된 페이지를 out 시키도록 구현하는 것이 효율적이다.
- LRU는 직접 참조된 시점만을 반영하지만, LFU는 참조 횟수를 반영하므로 장기적 시간 규모에서의 참조 성향을 고려할 수 있다.
단점
- 가장 최근에 불러온 페이지가 교체될 수 있으며, 이에 따른 오버헤드가 발생할 수 있다. (가장 최근에 참조된 페이지는 지금부터 많이 사용되기 시작할 수 있지만 LFU는 이를 교체하기 때문에)
- 초기엔 많이 사용되다가 이후 사용되지 않은 페이지는 교체 가능성이 낮다.
MFU(Most Frequently used)
참조 횟수가 가장 많은 페이지 교체
- 가장 많이 사용된 페이지가 앞으로는 사용되지 않을 것이라는 가정에 의한 알고리즘이다.
NUR(Not Used Recently = NRU)
최근에 사용하지 않은 페이지 교체
- LRU 근사 알고리즘으로, LRU가 가장 오래전에 참조된 페이지를 교체하는것과 다르게 NUR은 가장 오랫동안 사용하지 않은 페이지를 교체한다.
- 각 페이지마다 참조 비트와 변형 비트가 사용된다.
- 참조 비트 : 참조 x 일 때 0, 참조 o 일 때 1
- 변형 비트 : 내용 변경 x 일 때 0, 변경 o 일 때 1
- 고정된 시간 간격이 있어 주기적으로 모든 페이지의 참조 비트를 초기화한다.
SCR(Second Chance Replacement)
가장 오랫동안 주기억장치에 있던 페이지 중 자주 사용되는 페이지의 교체를 방지하기 위한 알고리즘
- FIFO의 단점을 보완한 기법이다.
- 큐의 상단에서 꺼낸 대상의 참조 비트를 검사하여 0이면 교체 대상으로 선택하고, 1이면 0으로 바꿔 큐의 뒤에 삽입한다.
참고 사이트
