페이지 교체 알고리즘

페이지 부재 (Page Fault)

• CPU가 접근하려는 페이지가 메모리에 없는 상황이다.
• 페이지 부재 발생 시 페이지를 디스크에서 읽어봐야 하는데 이 과정에서 막대한 오버헤드가 발생한다.

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

 

페이지 교체 알고리즘은 page-fault 발생 비율을 줄이는 것을 목표로 한다. 

 

 

 

페이지 교체 (Page Replacement)

• 페이지 부재가 발생하면 요청된 페이지를 디스크에서 메모리로 읽어와야하는데, 물리적 메모리에 빈 프레임이 존재하지 않을 수 있다.
• 이러한 경우, 메모리에 올라와 있는 페이지 중 하나를 디스크로 쫓아내 메모리에 빈 공간을 확보하여 새로운 페이지를 메모리에 올려야 한다.
• 이러한 과정을 페이지 교체라고 부르며, page-out이 된 페이지를 희생양 페이지 (victim page)라고 한다.

 

 

페이지 교체 (Page Replacement) 종류

 

FIFO(First In First Out) 알고리즘

• FIFO 알고리즘은 이름 그대로 가장 먼저 메모리에 올라온 페이지를 가장 먼저 내보내는 알고리즘이다.
• 구현이 간단하지만 성능은 좋지 않은 편이다.
• 들어온 시간을 저장하거나 올라온 순서를 큐를 이용해 저장할 수 있다.
• Belady`s Anomaly 현상이 발생할 수 있다.

 

 

OPT(Optimal) 알고리즘

• OPT 알고리즘은 앞으로 가장 오랫동안 사용하지 않을 페이지를 교체하는 알고리즘이다.
• 모든 페이지 교체 알고리즘 중 page-fault 발생이 가장 적다.
• Belady`s Anomaly 현상이 발생하지 않는다.
• 프로세스가 앞으로 사용할 페이지를 미리 알아야한다.
• 실제로 구현하기 거의 불가능한 알고리즘이다.
• 실제로 사용하기 보다는 연구 목적을 위해 사용된다.

 

LRU(Least Recently Used) 알고리즘

• LRU 알고리즘은 가장 오랫동안 사용하지 않은 페이지를 교체하는 알고리즘이다.
• 최적 알고리즘과 비슷한 효과를 낼 수 있다.
• 성능이 좋은 편이다.
• 많은 운영체제가 채택하는 알고리즘이다.

 

 

LFU(Least Frequently Used) 알고리즘

• LFU 알고리즘은 참조횟수가 가장 적은 페이지를 교체하는 알고리즘이다.
• 교체 대상이 여러 개라면 가장 오랫동안 사용하지 않은 페이지를 교체한다.