[OS] Page Placement Policy (페이지 배치 전략)

페이지 교체 정책

메모리의 모든 페이지 프레임이 사용되고 있는 상황에서 page fault가 일어나 새로운 페이지 프레임을 반입해야할 때, 교체 정책은 현재 적재되어있는 페이지 중 어떤 페이지를 교체시킬지를 결정한다. 모든 교체 정책의 목적은 교체되는 페이지가 가까운 미래에 참조될 가능성이 가장 적은 페이지가 되도록 하는 것이다.

 

※ 쓰레싱 (Thrashing)

쓰레싱이란 곧 사용될 페이지가 반출되는 일이 반복되는 현상으로 너무 잦은 page fault를 유발하여 I/O에 너무 많은 시간을 낭비하게 되는 경우가 발생한다. 따라서 합리적인 교체 정책을 채택하여 쓰레싱을 방지해야한다.

 

다양한 페이지 교체 정책

1. 최적 (Optimal)

• 미래에 참조될 때까지의 시간이 가장 긴 페이지를 교체
• 미래를 알아야하므로 구현 불가능한 정책
• 다른 교체 정책을 평가하는 기준으로서의 가치가 있음

 

2. LRU (Least Recently Used)

• 가장 오랫동안 참조되지 않은 페이지를 교체
• Optimal과 가장 유사한 성능을 보임
• 매 참조마다 최종 참조 시각을 기록해야하는데 이는 오버헤드가 너무 커 사실상 구현 불가능

 

3. LFU (Least Frequently Used)

• 가장 적게 사용된 페이지를 교체
• 매 참조마다 count를 증가시켜야하는데 이는 오버헤드가 너무 커 사실상 구현 불가능

 

4. FIFO (First In First Out)

• 메모리에 가장 오래 있었던 페이지를 교체
• 구현하기 쉽지만 상대적으로 좋지 않은 성능

 

5. LIFO (Last In First Out)

• 가장 최근에 들어온 페이지를 교체
• page fault가 자주 발생, 하지만 평균적인 성능은 FIFO와 비슷

 

6. 클록 (Clock)

클록은 현대 OS가 채택하고 있는 교체 정책이며 페이지 테이블에 존재하는 U비트와 M비트를 사용한다. one handed clock 방식의 교체 우선 순위는 다음과 같다.

1. 참조되지 않았으며 수정되지 않음 (u = 0, m = 0)
2. 참조되었으며 수정되지 않음 (u = 1, m = 0)
3. 참조되지 않았으며 수정됨 (u = 1, m = 0)
4. 참조되었으며 수정됨 (u = 1, m = 1)

우선순위 1번을 먼저 찾고 없을 경우 우선순위 2번을 찾아간다. 2번을 찾아가는 과정 중 지나치는 모든 페이지 프레임의 u비트를 0으로 설정한다. 만약 우선순위 2번도 없으면 모든 페이지 프레임을 탐색하면서 u비트를 0으로 만들었기 때문에 그 상태에서 다시 우선순위 1번을 찾는 반복을 수행한다.

---