8장 2 페이지 교체

 

페이지 교체 란

페이지 부재가 발생 하였을 때 물리적 메모리에 빈 공간이 없을 때 하나의 페이지를 스왑아웃하여 빈 공간을 확보하는 작업 

 

페이지 교체 알고리즘 

(목표) 페이지의 부재율을 최소화 -> 미래에 참조될 가능성이 가장 적은 페이지를 선택하여 스왑아웃 하는 방안을 모색

(페이지 교체의 예)

책에서 스크린샷

 

(성능) 주어긴 페이지 참조열 (page reference string)에 대해 부재율을 계산하여 평가

          (페이지 참조열 예시) 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5
                               참조되는 페이지들의 번호를 시간 순서에 따라 나열
                               해당 번호의 페이지가 이미 메모리에 올라와 있으면 메모리에서 적중(hit)
                               메모리에 없는 경우 페이지 부재 발생

 

1) 최적 페이지 교체

 

빌레디의 최적 알고리즘 (Belady's opitmal algorithm) 또는 MIN, OPT 로 불림

: 페이지 중 가장 먼 미래에 참조될 페이지를 쫓아내서 페이지 부재율을 최소화하는 알고리즘

: 미래에 어떤 페이지가 어떠한 순서로 참조될지 미리 알고 있다는 전제하에 운영 -> 오프라인 알고리즘

+ 알고리즘 중에 가장 적은 페이지 부재율을 보장
+ 한 시스템에서 새로운 알고리즘 설계시의 성능평가의 기준
- 실제 시스템에서는 사용 불가 

 

(작동원리 예시)

 

페이지 부재가 7번째에 발생 -> 미래에 일어날 페이지 순서 참조 -> 4 를 스왑아웃 하고 5를 적재

 

2) 선입선출(First In First Out :FIFO) 알고리즘

 

페이지 교체 시 물리적 메모리에 가장 먼저 올라온 페이지를 우선적으로 내쫓는다.

- 비효율적인 상황이 발생 (페이지 부재 다수 발생)

메모리 공간이 늘어나도 성능은 오히려 너 나빠질수도 있다. -> FIFO의 이상 현상

 

3) LRU(Least Recently Used) 알고리즘

성능향상을 위해서는 향후 사용될 가능성이 낮은 페이지를 우선적으로 메모리에서 쫓아내는 것이 바람직

• 메모리 참조 성향 중 중요한 한가지 성질 => 시간지역성(temporal locality)
  • 최근에 참조된 페이지가 가까운 미래에 다시 참조될 가능성이 높은 성질

LRU 알고리즘은 시간지역성을 이용하여 마지막 참조 시점이 가장 오래된 페이지를 쫓아낸다.

 

4) LFU (Least Frequently Used) 알고리즘

메모리에있는 페이지 중 참조 횟수가 가장 적었던 페이지를 쫓아내는 알고리즘

• Incache-LFU : 메모리에 올라온 후 부터 참조 횟수를 카운트 
• Perfect-LFU : 메모리에 올라온 이력에 관계없이 해당 페이지가 과거에 참조 된 총 횟수 카운트
  + 페이지 참조 횟수를 정확히 반영
  - 모든 페이지의 참조 기록을 보관하여야 하므로 오버헤드 발생

5) 클럭 알고리즘(clock algorithm) / 2차 기회 알고리즘

NUR(Not Used Recently) 또는 NRU(NOT Recently Used) 알고리즘

하드웨어적인 지원을 통해 알고리즘의 운영에 시간적인 오버헤드를 줄인 방식

• 오랫동안 참조되지 않은 페이지 중 하나를 교체
• 하드웨어적인 지원으로 동작하여 LRU 보다 페이지의 관리가 빠르고 효율적
• 시곗바늘이 한 바퀴 도는 동안 다시 참조 되지 않은 페이지를 교체
• 페이지 부재율을 줄이도록 설계
• 작동원리
  • 프레임내의 페이지가 참조 되면 하드웨어가 자동으로 1로 셋팅
  • 시곗바늘이 참조비트가 1인 페이지를 지나면 0으로 셋팅
  • 시곗바늘이 참조비트가 0인 페이지를 지나면 교체 대상 페이지