페이지교체 알고리즘

페이지 교체 알고리즘은 운영체제에서 가상 메모리 관리를 위해 사용되는 기법이다.

메인 메모리(RAM)가 가득 찼을 때 새로운 페이지를 가져오기 위해 어떤 페이지를 교체해야 할지 결정하는 알고리즘이다.

 

1. FIFO(first in first out)

먼저 들어온 게 먼저 나가는 알고리즘이다.

가장 오래된 페이지를 교체하는데, 여기서 단순히 먼저 적재되었다는 이유로 교체된다는 비효율을 개선하기 위해 2차 기회 페이지 교체 알고리즘이라고 count를 세어 기회를 주었을 때 2차인 경우에 교체하는 알고리즘이 존재한다.

 

2. OPT알고리즘(Optional)

가장 오랫동안 사용되지 않을 페이지를 교체한다.

페이지의 미래 사용 빈도와 참조를 예측해야 돼서 실제 구현은 불가능한데 이론적으론 최적이다.

다른 알고리즘의 비교 대상으로 사용된다.

 

3. LRU(Least Recently Used)

가장 오랫동안 사용되지 않은 페이지를 교체한다.

최근 사용 이력을 바탕으로 구현되고 성능이 좋다.

 

4. LFU(Least Frequently Used)

사용 빈도가 가장 낮은 페이지를 교체한다.

접근 횟수를 계산해야 돼서 구현이 복잡하다.

 

가상 메모리 관리 기법 중 하나인 페이징을 사용해 메모리의 물리 주소 공간을 프레임 단위로 나누고, 프로세스의 논리 주소 공간을 페이지로 나누어 프레임을 할당하여 사용하면, 실제 사용 가능한 물리 메모리 양보다 큰 프로세스를 실행할 수 있다.