페이지 교체 기법, FIFO, LRU, LFU

7.4 페이지 교체 기법

- 모든 페이지 프레임이 사용되고 있을 때 새로 적재되어야 할 페이지를 위하여 어느 페이지를 교체할 것인가를 결정

- 교체 대상 선택 -> 보조기억장치에 보관 -> 새로운 페이지를 적재

최적화의 원칙

- 앞으로 가장 오랫동안 사용되지 않을 페이지를 교체 대상으로 선택

- 이론적으로는 최적이나 미래를 예측할 수 없어 실현 불가능

 

선택을 위한 기본 정책

- 대체로 좋은 결론을 내리면서 시간 및 공간의 오버헤드가 적은 방법

 

교체 제외 페이지 

- 페이징을 위한 슈퍼바이저 코드 영역, 보조기억장치 드라이버 영역, 입출력장치를 위한 데이터 버퍼 영역 등

 

페이지 교체 알고리즘

- FIFO 페이지 교체 기법

- LRU 페이지 교체 기법

- LFU 페이지 교체 기법

- NUR 페이지 교체 기법

- 2차 기회 페이지 교체기법

- 클럭 페이지 교체 기법

- 워킹세트 알고리즘, PFF 알고리즘

 

 

7.4.1 FIFO (First-In First-Out) 페이지 교체

- 메모리 내에 가장 오래있었던 페이지를 교체

- 구현 : FIFO 큐 이용 

 

 

단점

 

- 오래 전에 적재되어 반복적으로 사용되는 페이지가 교체될 수 있음

 

- Belady의 이상현상 발생

 : 프로세스에 더 많은 수의 페이지 프레임을 할당할 경우

오히려 페이지 부재가 더 많이 발생할 수 있는 현상

 

7.4.2. LRU 페이지 교체

LRU(Least Recently Used)페이지 교체기법

- 가장 오랫동안 사용되지 않은 페이지를 교체

- 구현 : 참조시간 이용 또는 리스트 이용

(그림 위)

  * 페이지가 참조될 때마다 그때의 시간을 기록

  * 참조시간이 가장 오래된 페이지를 교체

 

 

(그림 아래)

** 페이지가 참조되면 리스트의 선두로 옮김

** 리스트의 끝에 있는 페이지를 교체

 

 

특징

- Bealady의 이상현상 발생하지 않음

- 많은 경우 최적화 원칙에 근사한 선택을 함

- 국부성(locality)에 기반

  : 어느 한 순간에 특정 부분을 집중적으로 참조

** 시간 국부성 : 현재 참조된 기억장소는 가까운 미래에도 계속 참조될 가능성이 높음

** 공간 국부성 : 하나의 기억장소가 참조되면 근처의 기억장소가 계속 참조될 가능성이 높음

 

단점

- 경험적 판단이 맞지 않는 상황도 존재

- 막대한 오버헤드

 

 

 

7.4.3 LFU(Least Frequently Used) 페이지 교체기법

- 참조된 횟수가 가장 적은 페이지를 교체

- 구현 : 참조 횟수 이용

 

* 페이지가 참조될 떄마다 증가된 횟수 기록

* 참조 횟수가 가장 적은 페이지 교체

 

단점 

- 가장 최근에 메모리로 옮겨진 페이지가 교체될 가능성 높음

- 초기에 매우 많이 사용된 후 더 이상 사용되지 않는 페이지는 교체 가능성 낮음

- 막대한 오버헤드