페이지 교체 알고리즘 - 주기억장치를 효율적으로 사용하자

 

👍 교체전략이란?

 

주기억장치 교체전략 = 페이지 교체 알고리즘

 

현대 운영체제는 제한된 용량을 가진 주기억장치를 효율적으로 사용하기 위해 다양한 전략을 사용한다.

그중 교체전략은 가상기억장치 다중프로그래밍에서 프로그램별 할당된 메모리가 꽉 찼을 때, 어떤 페이지를 바꿔껴야 더 효율적인지를 다루는 전략이며, 이를 위한 알고리즘을 "페이지 교체 알고리즘"이라고 한다.

 

CPU가 지금 당장 연산해야 할 코드가 마침 주기억장치 내 페이지 프레임에 들어있는 것을 가리켜, 해당 페이지가 적중했다고 하여 "Page Hit"라고 한다.

반대로 페이지 프레임에 없다면 해당 페이지가 실패 또는 없다고 하여 "Page Fault"라고 한다.

 

따라서 교체전략, 즉 페이지 교체 알고리즘의 목표는 다음 하나로 정해진다.

페이지 적중률을 높여라!

*페이지 적중률 = Page Hit 횟수 ÷ 전체 페이지 참조 횟수

페이지 적중률(Hit Ratio)이 높은 교체전략을 효율적이라고 하며, 프로그램의 실행 속도 향상을 가져온다.

반대로 페이지 적중률이 낮다면 그만큼 Page Fault가 많아져, 프로그램의 본격적인 실행은 못하고, 필요한 Page를 가상기억장치에서 로딩하는 데에만 집중하는 "스레싱"이 발생한다.

 

---

👍 그렇다면 교체전략에는 어떤 알고리즘들이 있을까?

 

👊 최적화(OPT, Optimality)

앞으로 가장 오랫동안 사용하지 않"을" 페이지를 예측하여 교체하기 - 미리 알고 한다는 자체가 현실성이 없음

 

👊 FIFO(First In - First Out)

각 페이지가 주기억장치에 적재될 때마다 시간을 기록하고, 가장 오래 있던 페이지를 교체한다.

페이지 부재(Page Fault)가 가장 많이 발생한다.

프로세스(각 프로그램)에 할당된 페이지 프레임 수가 증가하면 Page Fault 수가 감소하는 것이 당연하지만, 현실적으로는 오히려 더 증가하는 모순현상이 일어남.

 

👊 LRU(Least Recently Used)

빈도수와 상관없이 최근에 가장 오랫동안 사용하지 않은 페이지를 교체한다.

과거에 자주 사용했어도 최근에 사용하지 않았다면 교체 대상이 된다.

각 페이지마다 계수기(시간 기억 영역)를 둔다.

 

👊 LFU(Least Frequency Used)

사용빈도가 가장 적은 페이지를 교체한다.

사용한 횟수를 기억할 참조변수를 각 페이지마다 갖게 하여 사용할 때마다 1씩 증가시킨다.

 

👊 NUR(Not Used Recently)

최근에 호출하지도 사용하지도 않은 페이지를 제거한다.

페이지를 가상기억장치로부터 호출한 것을 "참조비트(Referenced Bit)"로, 적재 후 실제 사용까지 한 것을 "변형비트(Modified Bit)"로 구분하고,

오래전에 호출/사용한 것을 0, 최근에 호출/사용한 것을 1로 각각 기록하며 지속 갱신한다.

이때 참조비트와 변형비트가 모두 0인 것을 교체 대상으로 한다(오래 전에 적재하여 아직 사용하지 않았기 때문).

 

👊 Second Chance(이차 기회)

FIFO와 LRU의 혼합방식으로, 가장 오래된 페이지 중 최근에 사용되지 않은 것을 교체 대상에서 제외한다.

가장 오래된 페이지일수록 곧 사용할 가능성이 높아질 것 같음을 반영하기 때문이다.

 

👊 PFF(Page Fault Frequency)

작업집합(Working Set)에 존재하는 페이지들을 관찰하여 [최근에 자주 사용되지 않은 페이지]와 [작업집합에 속하지 않은 페이지] 중에서 최근에 자주 사용하는 페이지와 교체한다.

즉, 자주 사용되는 페이지는 메모리에 고정배치하여 교체 대상에서 제외한다.

 

👊 Stack을 이용한 LRU

가장 최근의 페이지가 스택의 꼭대기(Top)에 위치한다.

스택이 모두 채워지면 바닥(Bottom)에 있는 페이지를 제거한다.

스택 중간에 있는 페이지가 참조될 경우에는 해당 페이지의 위치를 스택의 꼭대기(Top)로 변경한다.

페이지가 참조될 때마다 PUSH, POP이 빈번하게 일어나기 때문에 오버헤드가 많이 발생한다.