NUR, 2차 기회 , 클럭 페이지 교체

7.4 페이지 교체 기법

7.4.4 NUR(Not Used Recently) 페이지 교체

- 참조 여부와 수정 여부에 따른 우선순위에 따라 적합한 페이지를 교체

- 구현 : 페이지 마다 참조 비트 r 과 수정 비트 m 이용

* 페이지 프레임에 적재 :  r = 0, m = 0

* 페이지를 참조 :  r = 1 

* 페이지를 수정 : m = 1

* 교체 우선순위  :

1. r=0, m=0   //  2. r=0, m=1

3. r=1, m=0   //  4. r=1, m=1

 

 

특징

- 적은 오버헤드로 적절한 성능을 낼 수 있음

- LRU와 유사하면서도 실제로 자주 쓰임

- 동일 그룸 내에서의 선택은 무작위

- 모든 참조 비트 r을 주기적으로 0으로 변경

 

 

7.4.5 2차 기회 (second chance) 페이지 교체 

- FIFO 페이지 교체기법과 참조 여부에 따른 우선순위를 고려하여 적합한 페이지를 교체

- 구현 : FIFO 큐와 참조 비트 이용

 

* 페이지 프레임에 적재 : 참조 비트는 0

* 페이지 참조 : 참조 비트는 1

 

 

 

교체 대상 선택 방법

1) 큐의 선두를 꺼내 참조 비트 조사

2) 참조 비트가 0이면 교체 대상으로 선택

3) 참조 비트가 1이면 0으로 바꿔 큐의 뒤에 넣음

 

 

 

7.4.6 클럭 (clock) 페이지 교체

- 2차 기회 페이지 교체를 원형 큐를 이용하여 구현한 것

- 교체가 필요한 경우 큐에서의 삭제 및 삽입 대신 포인터 이동으로 간단히 구현

1) 포인터가 가르키는 참조비트가 1이면 

2) 1을 0으로 바꾸고 다음으로 이동

3) 0이면 삭제 후 새로운 페이지 삽입

 

 

 

7.4.7 프로세스별 페이지 집합 관리

프로세스별 페이지 집합

- 프로세스마다 페이지 프레임에 적재된 페이지들의 집합

 

프로세스별 페이지 집합의 크기가 적은 경우

- 메모리에 적재할 수 있는 프로세스의 수 많아짐 -> 시스템 처리량 증대

- 각 프로세스별 페이지 부재 많아짐  -> 성능 저하

 

페이지 집합 관리 알고리즘

- 워킹 세트 알고리즘

- PFF 알고리즘

 

(1) 워킹세트 ( workong set) 

- 하나의 프로세스가 자주 참조하는 페이지의 집합

- 워킹세트 W(t,w) : 시간 t - w 로 부터 시간 t 까지의 프로세스 시간 간격동안 참조된 페이지의 집합

 

* 프로세스 시간

  : 그 프로세스가 CPU를 점유하고 있는 시간

* t : 현재 시간

* w : 워킹세트 윈도 크기

 

 

워킹세트 알고리즘

- 데닝(Denning)이 제안

- 페이지 부재 비율을 감소시키기 위한 방법

- 원칙 : 실행 중인 프로그램의 워킹세트를 메모리에 유지

( 국부성)

- 프로세스가 실행됨에 따라 워킹세트의 크기는 변함

 

- 운영체제는 충분한 여분의 프레임이 존재하면 새로운 프로세스를 실행시킴

- 반대로 프레임이 부족해지면 가장 우선순위가 낮은 프로세스를 일시적으로 중지시킴

- 워킹세트가 메모리에 유지되지 못하는 경우

** 쓰래싱 (thrashing)

페이지 부재가 비정상적으로 많이 발생하여 프로세스 처리보다 페이지 교체에 너무 많은 시간을 소비하여 시스템 처리량 급감하는 현상

 

문제점 

- 과거를 통해 미래를 예측하는 것이 정확하지 않음

- 워킹세트를 정확히 알아내고 이를 계속적으로 업데이트하는 것이 현실적으로 어려움

- 워킹 세트 윈도의 크기 w의 최적 값을 아기 어려우며 이 역시 변화할 수 있음

 

 

(2) PFF (Page Fault Frequency) 알고리즘

- 프로세스의 상주 페이지 세트를 변경하며 관리

- 페이지 부재가 발생할 때 빈도를 계산하여 상한과 하한을 벗어나는 경우에만 변경

- 페이지 부재 빈도 

  : 두 페이지 부재가 일어난 사이의 시간의 역수

- 운영체제는 프레임의 여분 상황에 따라 새로운 프로세수 추가 및 중지 결정

 

**상주 페이지 세트

프로세스가 페이지 부재떄문에 멈추게 되는 빈도에 기초한 페이지 세트