페이지 교체 알고리즘에 대해 아는대로 설명하세요

가상 메모리 시스템은 메모리 관리 장치를 통해 가상 주소를 실제주소로 바꾸어 동작하게 한다.

이로 인해 프로그램의 전체 크기만큼 메모리가 필요하지 않고, 실제 동작하는 최소한의 메모리만으로 동작할 수 있다.

이때, 메모리 관리 장치는 메모리를 페이지 단위로 관리한다. 

메모리를 효율적으로 사용하기 위해서 사용하지 않는 페이지를 없애는 알고리즘을 페이지 교체 알고리즘이라 한다

---

1. FIFO 페이지 교체 : 메모리에 올라온지 가장 오래된 페이지를 없앤다.

가장 간단한 페이지 교체 알고리지만,

가장 오래된 페이지가 초기화 모듈이라면 성능이 저하될 수 있다.

2. 최적 페이지 교체(OPT) : 앞으로 가장 오래 동안 사용되지 않을 페이지를 교체한다.

가장 낮은 페이지 부재율을 가지고 있지만,

프로세스의 메모리 참조를 미리 알아야하기에 구현이 어렵다.

3. LRU 페이지 교체 : 가장 오래 사용되지 않은 페이지를 교체한다

최적 페이지 교체 알고리즘에 근사한 알고리즘이지만,

프로세스가 주기억장치에 접근할 때마다 참조된 페이지에 대한 시간을 기록하기 때문에 큰 오버헤드가 발생한다

(OPT는 미래시간을 적용하였고, LRU는 과거 시간에 대해 적용한 최적 교체 알고리즘이다)

4. NUR 페이지 교체 : 최근에 사용하지 않은 페이지를 교체한다

LRU와 비슷한 알고리즘이며, 최근의 사용여부를 확인 하기 위해 각페이지마다 두개의 비트 사용

LRU에서 나타나는 시간적 오버헤드를 줄일 수 있지만, 없애는 페이지의 참조 시점이 가장 오래되지 않은 경우가 있다

5. 참조 횟수 관련 알고리즘

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

초기에 한 페이지를 집중적으로 참조하다가 이후 다시 참조하지 않을 경우 문제가 될 수 있다

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

가장 적게 사용된 페이지가 최근에 올라오고 계속 사용될 것이라고 가정해서 만들어진 알고리즘이지만,

OPT 알고리즘을 제대로 금사하지 못해서 잘 쓰이지 않고 구현에 상당한 비용이 든다.