페이지 교체 알고리즘(LRU, LFU, MFU)::운영체제

 프로세스가 특정 페이지를 요구할 때 해당 페이지를 물리 메모리에 load합니다.

 

 메모리에 필요한 페이지가 있을 경우 바로 사용할 수 있지만, 페이지가 없을 경우(page-fault) 하드디스크에서 페이지를 찾아야 하기 때문에 많은 시간이 소비됩니다.

 

 페이지를 교체하는 가장 단순한 방법으로 FIFO(First In First Out) 알고리즘이 있습니다.

 메모리에 load된 페이지 중 가장 오래된 페이지를 교체합니다.

 페이지가 올라온 순서를 큐(Queue)에 저장해 순서대로 교체합니다.

 하지만, 활발하게 사용하고 있는 페이지를 계속해서 교체될 경우, 페이지 부재율이 높아 성능이 낮습니다.

 

 따라서 한정된 메모리에서 교체할 희생 프레임을 찾고, 적절한 페이지로 교체해 성능을 높일 수 있는 페이지 교체 알고리즘을 사용합니다.

 

 

1. LRU(Least Recently Used)

 

 가장 오래 사용하지 않은 페이지를 교체하는 알고리즘입니다.

 현재 가장 많은 운영체제가 채택한 알고리즘으로 가장 효율이 좋다고 평가받고 있습니다.

 

 

2. LFU(Least Frequently Used)

 

 참조 횟수가 가장 적은 페이지를 교체하는 알고리즘입니다.

 만약 교체 대상이 여러 페이지일 경우 가장 오래 사용하지 않은 페이지로 교체합니다.

 

 하지만 초기에 한 페이지를 집중적으로 참조하다가 나중에는 참조하지 않을 경우 문제가 될 수 있습니다.

 앞으로 사용하지 않는 페이지의 참조 횟수가 높아 메모리에 계속 남아있기 때문입니다.

 

 

3. MFU(Most Frequency Used)

 

 LFU 알고리즘과 반대로 참조 횟수가 가장 많은 페이지를 교체하는 알고리즘입니다.

 

 참조 횟수가 적은 페이지가 최근에 참조된 것으로 보고 앞으로 사용될 가능성이 높다고 판단한 알고리즘입니다.