페이지 교체 (Page Replacement)

* 페이지 교체의 필요성

• 메모리 과할당(over-allocating) 발생 시 메모리 프레임이 부족하므로 페이지 교체가 필요하다.
• 페이지 교체는 요구 페이징의 기본
  • 페이지 교체를 이용해서 매우 작은 물리 메모리로도 프로그래머에게 광대한 가상 메모리를 제공

 

1. 페이지 교체 (Page Replacement)

(1) 페이지 교체 과정

• 보조저장장치에서 필요한 페이지의 위치를 알아낸다.
• 빈 페이지 프레임을 찾는다.
  • 비어 있는 프레임이 있다면 그것을 사용한다.
  • 비어 있는 프레임이 없다면 희생될(victim) 프레임을 선정하기 위하여 페이지 교체 알고리즘을 가동시킨다.
  • 희생될 페이지를 보조저장장치에 기록하고, 관련 테이블을 수정한다.
• 빼앗은 프레임에 새 페이지를 읽어오고 테이블을 수정한다.
• 페이지 폴트가 발생한 지점에서부터 프로세스를 계속한다.

페이지 교체 시 디스크를 두 번 접근해야 한다. 이와 같은 상황에서는 페이지 폴트 처리 시간이 2배 소요되며 그에 따라 실질 접근 시간도 증가한다.
이러한 오버헤드는 변경 비트(modify bit 또는 dirty bit)를 사용해서 감소시킨다.
변경 비트는 페이지 내의 어떤 바이트라도 쓰게 되면 페이지가 변경되었음을 나타내기 위해 설정된다.
변경 비트가 설정되어 있으면 보조저장장치에 기록된다.
변경 비트가 설정되어 있지 않다면 보조저장장치에 기록할 필요가 없다.

(2) 프레임 할당(frame-allocation)과 페이지 교체(page-replacement)

• 요구 페이징 시스템의 두 가지 중요한 문제
  • 프레임 할당(frame-allocation) 알고리즘
  • 페이지 교체(frame-replacement) 알고리즘

• 프레임 할당(frame-allocation)
  • 여러 프로세스가 존재하는 경우 각 프로세스에 얼마나 많은 프레임을 할당해야 할지 결정

• 페이지 교체(page-replacement)
  • 페이지 교체가 필요할 때마다 어떤 페이지를 교체해야 할지 결정
• Example
  • 참조열 (Reference String) : 1, 4, 1, 6, 1, 6, 1, 6, 1, 6, 1
  • 페이지 프레임 1개 : page fault 11번
  • 페이지 프레임 6개 : page fault 3번

 

2. 페이지 교체 알고리즘 (Page Replacement Algorithm)

• 페이지 폴트율 (page-fault rate)가 가장 낮은 것을 선정한다.
• 아래에 나오는 알고리즘의 Example의 가정
  • 참조열 (Reference String) : 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1
  • 페이지 프레임 3개

(1) First-In-First-Out (FIFO) Algorithm

메모리에 올라온 지 가장 오래된 페이지를 victim으로 선정한다.

• Example

• 총 15번의 page faults
• FIFO 알고리즘은 이해하기 쉽고 프로그램하기도 쉽다. 그러나, 성능이 좋지 않다.
• FIFO 알고리즘은 Belady의 모순이 발생한다.
• Belady의 모순 (Belady's anomaly)
  • 프로세스에게 할당된 프레임을 증가시켰는데 오히려 페이지 폴트율이 더 증가하는 현상 
  • Example
    • 참조열 : 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5
    • 페이지 프레임 3개 : pagefault 9개
    • 페이지 프레임 4개 : pagefault 10개

(2) Optimal Algorithm

앞으로 가장 오랫동안 사용되지 않을 페이지를 victim으로 선정한다.

• Example

• 총 9번의 page faults
• Optimal Algorithm은 가장 낮은 페이지 폴트율을 보장한다.
• 이 알고리즘은 실제 구현은 어렵다. 
  • 프로세스가 앞으로 메모리를 어떻게 참조할 것인지를 미리 알아야 하기 때문이다.

(3) Least Recently Used (LRU) Algorithm

가장 오랜 기간 동안 사용되지 않은 페이지를 victim으로 선정한다.

• LRU 알고리즘은 페이지마다 마지막 사용 시간을 유지한다. 
• 미래 대신 과거 시간에 대해 적용한 최적 교체 정책
• Example

• 총 12번의 page faults
• Belady의 모순 현상을 야기하지 않는다.

 

• LRU Algorithm의 구현
  • Counter(계수기) Implementation
    • 각 페이지 항목마다 사용 시간 필드를 넣는다.
    • 메모리가 접근될 때마다 시간은 증가한다.
    • 시간 값이 가장 작은 페이지가 교체된다.
    • 탐색하는 데 큰 overhead가 발생된다.
  • Stack(스택) Implementation
    • 페이지 번호의 스택을 유지한다.
    • 페이지가 참조될 때마다 페이지 번호는 스택 중간에서 제거되어 스택 top에 놓이게 된다.
      • 스택의 중간에 접근해야 할 필요가 있으므로 스택은 doubly linked list로 구현한다.
    • 교체가 일어날 경우 페이지 탐색이 필요 없이 스택의 밑바닥에서 pop이 일어난다.

(4) LRU 근사 (LRU Approximation) Algorithm 

• 두 가지 LRU 구현 방법 모두 TLB 레지스터 이상의 하드웨어 지원이 있어야 한다.
  • counter와 stack을 갱신하는 일을 메모리 참조 때마다 수행되어야 하기 때문
• LRU 페이지 교체 지원을 충분히 할 수 있는 하드웨어는 많지 않다. 
• 참조 비트 (reference bit)
  • 모든 참조 비트는 0으로 초기화
  • 프로세스가 실행되면서 참조되는 페이지의 비트는 하트웨어가 1로 세팅
  • 값이 0인 참조 비트를 가지는 페이지 중 하나를 victim으로 선정한다.

(i) 2차 기회 알고리즘 (Second-chance algorithm)

기본은 FIFO 교체 알고리즘이다. 그러나 페이지가 선택될 때마다 참조 비트를 확인해서 0이면 교체하고 1이면 다시 한번 기회를 주고 다음 FIFO 페이지로 넘어간다. 

• 순환 큐를 이용해서 구현한다.
  • 다음에 교체될 페이지를 가리킨다.
• 포인터는 0 값의 참조 비트를 가진 페이지를 발견할 때까지 큐를 탐색한다.
• 포인터가 돌아가면서 참조 비트 값들이 1인 것을 0으로 바꾼다.

(ii) 개선된 2차 기회 알고리즘 (Enhanced Second-chance algorithm)

2차 기회 알고리즘을 개선해서 참조 비트(reference bit)와 변경 비트(modify bit)를 사용한다.

• 네 가지 등급
  • (0, 0) : 사용되지도 변경되지도 않은 경우 - 교체하기 가장 좋은 페이지
  • (0, 1) : 사용되지는 않았지만 변경이 된 경우 - 페이지 교체 시 디스크에 내용을 기록해야하므로 좋지 않다.
  • (1, 0) : 사용은 되었으나 변경은 되었으나 변경은 되지 않은 경우 - 페이지는 곧 다시 사용될 가능성이 높다.
  • (1, 1) : 사용도 되었고 변경도 된 경우 - 곧 다시 사용될 것이며 교체시 디스크에 그 내용을 기록해야 한다.
• 페이지가 어떤 등급에 속하는지 확인해서 가장 낮은 등급을 가지면서 처음 만난 페이지를 교체한다.

(5) 계수 알고리즘 (Counting Algorithm)

참조할 때마다 계수를 하여 그 값으로 판단한다.

• LFU(Least Frequently Used) 알고리즘
  • 참조 횟수가 가장 작은 페이지를 교체하는 방법
• MFU(Most Frequently Used) 알고리즘
  • 참조횟수가 가장 많은 페이지를 교체하는 방법
• 잘 사용되지 않는다.
  • 구현에 드는 비용이 높고 성능이 최적 알고리즘에 근사하지 못한다.

(6) 페이지 버퍼링 알고리즘 (Page Buffering Algorithm)

페이지 교체 알고리즘과 병행하여 여러 가지 버퍼링을 사용

• 가용 프레임 여러 개를 풀(pool)로 유지하는 방법
• 변경된 페이지 리스트를 유지하는 방법
• 가용 프레임을 유지하지만, 원래 주인 프로세스가 누구였는지 기록하는 방법

(7) 응용(Application)과 페이지 교체

application의 특성에 맞게 page replacement algorithm 선택