[TIL] 페이지 교체 알고리즘

 운영체제는 물리 메모리의 크기의 한계를 극복하기 위해, 가상 메모리 기법을 사용한다. 이는 프로그램의 일부만 주기억 장치에 적재하여 사용하는 방식으로, 프로세스 전체가 메모리에 올라오지 않더라도 실행이 가능하도록 하는 기법이다.

 

 가상 메모리 기법을 구현하는 방식 중 하나인 요구 페이징 기법 (Demand Paging) 으로 메모리를 관리하는 운영체제에서, 필요한 페이지가 주기억장치에 적재되지 않았을 시(page fault), 어떤 페이지 프레임을 선택하여 교체할 것인지 결정하는 방법을 페이지 교체 알고리즘이라고 한다.

 

페이지 교체 알고리즘은 다음과 같이 크게 6가지가 있다.

 

OPT(Optimal)

앞으로 가장 오랫동안 사용되지 않을 페이지 교체

• 발레디의 최적 알고리즘으로 MIN, OPT 등으로 불린다.
• 가장 이상적인 알고리즘 이다.
• 프로세스가 앞으로 사용할 페이지를 미리 알아야하기 때문에, 실제로 구현하기 거의 불가능한 알고리즘이다.
• 비교 연구 목적을 위해 사용된다.

 

FIFO(First in First out)

가장 먼저 들어온 페이지를 교체

• 메모리에 가장 먼저 올라온 페이지를 먼저 내보낸다.
• 들어온 시간을 저장하거나 올라온 순서를 큐를 이용해 저장할 수 있다.
• 구현이 간단하지만, 성능이 좋다고 장담할 수 없다.
  • 페이지 2(9번째)의 경우, 직전 페이지 부재(page 4)로 인해 페이지 4와 페이지 2가 교체되고 난 후, 또 다시 페이지 2를 사용하기 위해 교체했던 페이지 2를 다시 불러들였다.이렇듯 활발하게 사용 중인 페이지를 계속해서 교체한다면 페이지 부재율이 높아지고 실행속도가 떨어질 위험이 있다.

 

LRU(Least Recently Used)

가장 오랫동안 사용하지 않은 페이지 교체

 

 최적 알고리즘은 실제 구현이 불가능하므로, 최적 알고리즘의 방식과 비슷한 효과를 낼 수 있는 방법을 사용한 것이 LRU 알고리즘이다. 최적 알고리즘은 페이지가 사용될 시간을 미리 알고 있다. 현실 적으로 페이지가 사용될 시간을 미리 아는 것이 불가능하다면, 과거의 데이터를 바탕으로 페이지가 사용될 시간을 예측하여 교체하는 것은 가능하다.

 

이때, 예측 방법으로 가장 오랜 기간 사용되지 않은(least recently used) 페이지를 교체하는 방식을 사용한다.

• 시간 지역성(temporal locality) (최근에 참조된 페이지가 가까운 미래에 다시 참조될 가능성이 높은 성질) 을 고려한 알고리즘이다.
• 사용된 시간을 알수있는 부분을 저장하여 가장 오랫동안 참조되지 않는 데이터를 제거하기 때문에 페이지마다 카운터가 필요하다.
  • 카운터: 각 페이지 별로 존재하는 논리적인 시계로, 해당 페이지가 사용될 때마다 0으로 초기화한 후 시간을 증가한다.
• 큐로 구현가능이 가능하다. 사용한 데이터를 큐에서 제거하여 맨 위로다시 올리고, 프레임이 모자랄 경우 맨 아래에 있는 데이터를 삭제한다.
• 프로세스가 주기억장치에 접근할 때마다 참조된 페이지 시간을 기록해야하므로 막대한 오버헤드가 발생할 수 있다.
• 최적 알고리즘과 비슷한 효과를 낼 수 있어 성능이 좋은 편이다.
• 많은 운영체제가 채택하는 알고리즘이다.

 

LFU(Least Frequently Used)

참조 횟수가 가장 낮은 페이지를 교체

 

 만약, 교체 대상인 페이지가 여러 개 일 경우, LRU 알고리즘을 따라 가장 오래 사용되지 않은 페이지로 교체한다.

• LFU 알고리즘은 초기에 한 페이지를 집중적으로 참조하다가 이후 다시 참조하지 않는 경우 문제가 될 수 있다. 앞으로 사용하지 않아도 초기에 사용된 참조횟수가 높아 메모리에 계속 남아있기 때문이다.
• 가장 최근에 불러온 페이지가 교체될 수 있으며, 이에 따른 오버헤드가 발생할 수 있다.
• LRU는 직접 참조된 시점만을 반영하지만, LFU는 참조 횟수를 통해 장기적 시간 규모에서의 참조 성향을 고려할 수 있다.

 

MFU(Most Frequently used)

참조 횟수가 가장 많은 페이지를 교체

 

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

• 참조 횟수가 적은 페이지가 최근에 사용된 것이기 때문에 앞으로 사용될 가능성이 높다는 판단이다.

 

NUR(Not Used recently)

클럭 알고리즘

 

 클럭 알고리즘은 LRU처럼 가장 최근에 참조되지 않은 페이지를 대상으로 선정한다는 점에서 LRU와 근사하지만 교체되는 페이지의 참조 시점이 가장 오래되었다는 것을 보장하지는 않는다. 클럭 알고리즘은 그림처럼 참조 비트(reference bit)를 순차적으로 조사하며 동작한다.

 

1. 프레임 내의 페이지가 참조될 때 하드웨어에 의해 1로 자동 세팅된다.
2. 클럭 알고리즘은 한 바퀴 돌며 참조되지 않은 페이지의 참조 비트 값을 0으로 바꾼 후 지나간다.
3. 참조 비트가 0 인 페이지를 방문하면 해당 페이지를 교체한다.

 클럭 알고리즘은 시계 바늘이 한 바퀴 도는 동안 걸리는 시간만큼 페이지를 메모리에 유지시켜 페이지 부재율을 줄이도록 설계 되었다.

 

References

https://medium.com/pocs/%ED%8E%98%EC%9D%B4%EC%A7%80-%EA%B5%90%EC%B2%B4-page-replacement-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-650d58ae266b

https://zangzangs.tistory.com/143

https://steady-coding.tistory.com/526