CS - 페이지 교체 알고리즘

메모리 내에 저장된 페이지 중에서 어떤 페이지를 교체할지 결정하는 알고리즘

페이지 교체 알고리즘은 물리적인 메모리 공간이 한정되어 있을 때, 페이지 부재가 발생하는 상황에서 새로운 페이지를 적재하기 위해 기존 페이지 중 어떤 페이지를 제거할지 결정하는 역할

여러 알고리즘이 있으며, 각 알고리즘은 다양한 방식으로 페이지를 교체하며 알고리즘에 따라 페이지 부재율이나 페이지 교체 오버헤드 등의 성능이 달라짐

1.오프라인 알고리즘

먼 미래에 참조되는 페이지와 현재 할당되는 페이지를 바꾸는 알고리즘

입력 데이터가 모두 주어진 상태에서 실행되는 알고리즘. 입력 데이터를 모두 가지고 있기 때문에, 실행 중에 새로운 입력이 들어오지 않음

오프라인 알고리즘은 입력 데이터를 한꺼번에 처리할 수 있으므로 실행 시간과 공간 사용량을 예측할 수 있다. 따라서 입력 데이터의 크기에 따라 적절한 실행시간과 공간을 예약하여 처리할 수 있다.

하지만, 미래에 사용되는 프로세스를 알 수 없다. 즉, 메모리 할당에서는 사용할 수 없는 알고리즘이지만 다른 알고리즘과의 성능 비교에 대한 기준을 제공

-> 오프라인 알고리즘의 대표적인 예시는 정렬 알고리즘. 정렬 알고리즘은 입력 데이터를 모두 가지고 있기 때문에 오프라인 알고리즘. 입력 데이터가 모두 주어졌으므로 한 번에 정렬할 수 있다.

2.시간기반 알고리즘

2-1) FIFO

가장 먼저 온 페이지를 교체 영역에 놓는 방법

캐시 메모리에 새로운 데이터가 들어오면 가장 오래전에 들어온 데이터를 제거하고 새로운 데이터를 추가

이 방식은 구현이 간단하지만, 오래된 데이터가 최근에 사용된 데이터와 비슷한 경우엔 성능 저하 가능성 존재

2-2) LRU

참조가 가장 오래된 페이지를 교체하는 방법

LRU 방식은 가장 최근에 사용된 데이터를 먼저 사용할 가능성이 높기 때문에 캐시히트율을 높일 수 있음

LRU 알고리즘 구현 방식은 데이터를 저장하는데 추가적인 비용이 들어가게 됨 -> 오래된 것을 파악하기 위해 각 페이지마다 계수기, 스택을 두어야한다는 문제점 발생

2-3) NUR(Not Used Recently)

일명 clock 알고리즘 최근 사용여부를 0,1로 표시하여 교체하는 방법

1은 최근에 참조, 0은 참조되지 않음을 의미

시계방향으로 돌면서 0을 찾고 0을 찾는 순간 해당 프로세스를 교체. 해당 부분을 1로 바꾸는 알고리즘

LRU - 데이터를 사용할 때마다 사용 시간을 갱신 / NUR - 사용하지 않는 데이터를 주기적으로 스캔하여 사용 여부를 판단

3.빈도기반 알고리즘

3-1) LFU(Least Frequently User)

가장 참조 횟수가 적은 페이지를 교체( = 많이 사용하지 않은 것을 교체)

LFU 방식은 사용 빈도가 낮은 데이터를 제거하여 캐시 히트율을 높일 수 있음

그러나 LFU 알고리즘은 일부 데이터가 빈번하게 사용되는 경우에는 성능 저하가 발생 가

구너드