[Operating System] Page Replacement

Paging Replacement Policy

• 메모리 모든 페이지프레임이 사용중인 상황에 SWAP에 위치한 페이지프레임을 참조하는 상황이 발생할 수 있다.

• 메모리 페이지프레임중 하나를 SWAP의 페이지프레임과 교체해야한다.(PAGE FAULT)

• PAGE FAULT가 자주발생하는것 - 쓰레싱.

• PAGE FRAME이 미래에 얼마나 참조될지 예측하는것.

• 과거의 경향을 근거로 예측한다.

OPTIMAL

• 미래에 참조될 PAGE순서를 모두 아는 상태에서 앞으로 참조까지 시간이 가장 긴 PAGE를 교체한다.

FIFO

• 먼저 들어온 페이지가 먼저 나가는 단순 큐.

• 쉽지만 구현이 어려움

LRU

• 가장 오랫동안 참조되지 않은 페이지를 교체

• 각 page frame마다 가장 최근에 참조된 시각을 기록해야 하는데, 성능이좋지않다.

LIFO

• 가장 최근에 들어온 페이지가 빠져나가는 스택 방식

• 하나의 프레임만이 지속적으로 교체되기 때문에 PAGE FAULT자주 발생

LFU

• 참조된 빈도가 낮은 PAGE를 교체하는 것이다.

• 참조횟수 새로운 변수를 만들어야한다. 동일한 참조횟수이면 FIFO 채택

Clock = NUR(NOT USED RECENTLY)

• 클락 정책은 현대 OS에서 채택하고 있는 페이지 REPLACEMENT 정책이다.

• 기존 페이지테이블에 이미 존재하던 R,W bit를 활용한다.

1. 참조되지 않았으며, 수정되지 않음 (R = 0, W = 0)

1. 참조되었으며, 수정되지 않음 (R = 1, W = 0)

1. 참조되었으며, 수정됨 (R = 1, W = 1)

• 우선순위 1을 먼저 찾고, 1이 없을 경우 우선순위 2를 찾고 그과정에서 지나치는 모든 페이지프레임의 R bit를 0으로 설정한다. 우선순위 2도 없으면 모든 page frame탐색하면서 r비트를 0으로 만들었을 것이다. 그 상태에서 다시 우선순위 1을 찾는 반복을 수행한다.

• 새로운 → 는 메모리를 가리키는 포인터.

• CLOCK 정책에서 다음에 삽입할 PAGE가 어디인지 알려준다.

• *은 참조여부이다. 있을경우 R BIT 1 없을 경우 R BIT 0