10-3. VM. Management_Replacement Strategies_fixed allocation

가상 메모리의 성능향상을 위한 관리 기법중 SW components 에서  Replacement strategies(교체 기법)에 대해 다루어 본다.

 

Fixed allocation을 위한 교체기법

• MIN(OPT, B0) algorithm

• Random algorithm

• FIFO(First In First Out) algorithm

• LRU(Least Recently Used) algorithm

• LFU(Least Frequently Used) algorithm

• NUR(Not Used Recently) algorithm

• Clock algorithm

• Second chance algorithm

 

Variable allocation 을 위한 교체기법

• VMIN(Variable MIN) algorithm

• WS(Working Set) algorithm

• PFF(Page Fault Frequency) algorithm

 

Min Algorithm(OPT algorithm)

페이지 폴트를 최소화 시키는 알고리즘

min algorithm은 앞으로 가장 오랫동안 참조되지 않을 page를 교체하는 방법이다.

하지만 문제는 앞으로 어떤 page를 참조할지 미리 알고있다는 가정하에 적용하는 방법으로 실현 불가능한 기법인다.

 

배우는 이유는 Min algorithm은 말그대로 최적의 알고리즘이기 때문에 다른 교체 기법의 성능을 평가를 위한 기준 도구로 사용된다. 

Random Algorithm

무작위로 교체할 pgage선택

오버헤드가 없고 , 정책도 없지만 성능평가의 기준으로 사용할 수 있다.

 

FIFO Algorithm

page가 적재 된 시간을 기억하여 가장 오래된 page를 교체하는 방법이다.

자주 사용되는 page가 교체 될 가능성이 높다. 이는 Locality에 대한 고려가 없음을 말한다.

FIFO anomaly : 페이지 폴트 줄이기 위해 메모리 늘렸지만 locality를 고려하지 않아 오히려 더 늘어나는 경우가 있다.

 

LRU(Least Recently Used) Algorithm

가장 오랫동안 참조되지 않은 page를 교체하는 방법이다.

 

locality에 기반을 둔 교체 기법으로 최적 알고리즘인opt algorithm에 근접한 성능을 보인다.

실제로도 가장 많이 활용되는 기법!

 

단점

> 참조 시 마다 시간을 기록해야 하기때문에 overhead가 있다. 이를 해결하기 위한 방법으로는 정확한 시간대신 순서만 기록하는 등 간소화된 정보 수집으로 해소 가능하다.

 

>loop실행에 필요한 크기보다 작은 수의 페이지 프레임이 할당된 경우 page fault가 급격히 늘어난다. 이 문제는 allocation 기법에서 해결해야한다.(페이지 프레임을 적절하게 할당해줌)

 

 

LFU(Least Frequently Used) Algorithm

가장 참조 횟수가 적은 page를 교체하는 방법으로 참조횟수가 동일하다면 LRU rule을 적용시켜 해결한다.

LRU와 마찬가지로 Locality를 활용한 방법이며 시간을 기록하는 LRU대비 적은 overhead를 가진다.

단점

>최근 적재된 참조 가능성이 높은 page가 교체될 가능성이 있다.

>LRU보다는 적으나 여전히 적재  횟수를 기록해야 한다는 overhead가 존재한다.

 

NUR(Not Used Recently)Algorithm

최근에 사용되지 않은 페이지를 교체하는 방법으로 

LRU보다 적은 overhead로 비슷한 성능 달성을 목적으로 한다.

 

 

Clock Algorithm

Reference bit를사용하여 이들을 순차적으로 가리키는 pointer를 사용해 교체될 page를 결정한다.

주기적 초기화는 없다.

 

Pointer를 돌리면서 교체 pasge를 결정

현재 가리키고 있는 page의 reference bit확인 하여 r=0이녕우 교체 page로 결정하고

r=1인경우 reference bit를 초기화 하고 pointer를 이동한다.

 

먼저 적재된 page가 교체 가능성이 높다는 측면에서FIFO와 유사하고 

Reference bit를 사용해 교체 페이지를 결정한다는 측면에서 LRU or NUR과 유사한다

Clock Algorithm 예제

 

Second Chance Algorithm

clock algorithm과 유사 하며 Update bit 도 함께 고려한 알고리즘이다.

방법은 아래와 같다.

레퍼런스 비트(r)이 1인경우  0으로 바꿔주고 이동하고 r=0이고 m=1인경우 write-back을 하고 이동시킨다.

(0,0)인경우 교체 page로 결정한다.