필요한 페이지가 메모리에 없을 때 page-falut가 발생하고 Backing Store에서 해당 페이지를 찾아 빈 프레임에 로딩해야 하는데, 이때 빈 프레임이 없을 경우 희생 당할 프레임(victim frame)을 고르는 알고리즘이 페이지 교체 알고리즘이다. 페이지 교체 알고리즘은 page-fault 발생 비율을 줄이는 것을 목표로 한다.

FIFO

FIFO(First In, First Out)는 메모리 페이지 교체 알고리즘 중 하나로, 가장 먼저 메모리에 들어온 페이지를 가장 먼저 교체하는 방식을 사용합니다.

1. 구현이 간단하지만 성능은 좋지 않은 편이다.

2. Belady`s Anomaly 현상이 발생할 수 있다. :

프레임의 개수가 많아져도 page-fault가 줄어들지 않고 늘어나는 현상을 말한다.

LRU

• LRU(Least Recently Used)는 페이지 교체 알고리즘 중 하나로, 가장 오랫동안 사용되지 않은 페이지를 교체하는 방식을 사용합니다.

1. 최적 알고리즘과 비슷한 효과를 낼 수 있다.

최적 알고리즘은 주어진 문제를 해결하는 데 있어서 가장 효율적이고 최적의 솔루션을 찾아내는 알고리즘이다.
• 메모리 페이지의 참조 성향 중 시간 지역성을 고려한 알고리즘이다. 
(시간 지역성: 최근에 참조된 페이지가 가장 가까운 미래에 다시 참조될 가능성이 높음.)

1. 성능이 좋은 편이다.
2. 많은 운영체제가 채택하는 알고리즘이다.

• 페이지마다 카운터가 필요하며 큐로 구현이 가능하다. 사용한 데이터를 큐에서 제거하여 맨 위로 다시 올리고, 프레임이 모자랄 경우 맨 아래에 있는 데이터를 삭제한다. (카운터: 각 페이지 별로 존재하는 논리적인 시계로, 해당 페이지가 사용될 때마다 0으로 초기화한 후 시간을 증가한다.)
• 프로세스가 주기억장치에 접근할 때마다 참조된 페이지 시간을 기록해야하므로 막대한 오버헤드가 발생할 수 있다.