Page replacement

Page replacement

 

   - 메모리가 가득차면, 기존의 적재된 페이지를 선별하여 backing store에 page out 시키고, 그 빈공간으로 새로운 페이지를 적재한다.

 

   - page out 시키는 페이지의 정보 변경 여부를 확인하여 변경되지 않았으면 backing store에 저장하지 않아도 된다. 이를 위해 page table에 dirty bit를 추가하여 페이지 정보 변경 여부를 표시한다.

 

 Victim page

 

   - page replacement에 의해 page out 되는 페이지를 victim page 라고 한다. victim page를 선택하는 최우선의 조건은 데이터가 변경되지 않은, 즉 dirty bit가 0인 페이지를 선택하는 것이 backing store에 저장을 불필요로 하기 때문에 가장 유리하다. 그 이후는 replacement algorithm에 따라 선별한다.

 

Page reference string

 

   - 페이지 테이블의 엔트리는 페이지 크기 단위로 업데이트되고 참조되기 때문에, 연속된 페이지를 갖는 논리주소를 처리하면서 page fault / page replacement 가 일어나지는 않을 것이다. 따라서 이런 연속으로 중복된 인덱스 참조를 제거하여 어떤 순서로 페이지가 참조되는지 나타내는 string이다.

 

   - 예를 들어 논리주소가 124 123 434 535 537 323 342 233 424 483 943 968 943 순서이고, 페이지 크기를 쉽게 100이라고 할때, 참조되는 페이지 인덱스는 1 1 4 5 5 3 3 2 4 4 9 9 9 일 것이고, 연속된 중복 인덱스를 제거하면, page reference string은 1 4 5 3 2 4 9 가 된다.

 

 Page replacement algorithm

 

   - 앞서 말했 듯, 페이지 참조에서 주소별 데이터는 페이지 단위로 업데이트 되고 참조된다. (예, 페이지 사이즈가 100이라면 논리주소 142 153 132은 모두 한번에 참조되고, 업데이트 된다), 따라서 교체 알고리즘은 중복을 제거하여 페이지 인덱스 접근 순서를 보여주는 page reference string을 기준으로 하여 적용된다.

 

   - 페이지 교체 알고리즘은 FIFO / OPT / LRU 가 대표적이다.

 

1) FIFO (first in first out)

 

   - 가장 먼저 들어온 페이지가 victim이 된다. 예를 들어 프로그램의 초기화 코드는 처음 한번이 중요하지 다시 쓰일 확률이 다른 것보다 적을 것이다. 이런 상황에서 FIFO는 초기화 코드에 해당하는 페이지를 우선적으로 page out 할 것이다.

 

   ** Belady's anomaly : 이상적으로는 페이지 크기와 page fault 수는 반비례하나 FIFO 알고리즘 사용시, 페이지 프레임을 크게 할 때 오히려 page fault가 증가하는 모순적인 상황이 발생한다.

 

2) OPT (optimal)

 

   - 이후에 가장 덜 사용될 페이지를 victim으로 한다. 말 그대로 최적의 알고리즘이지만 비현실적이다.

 

3) LRU (Least Recently Used)

 

   - OPT는 이후의 페이지 사용 빈도를 기준으로 한다면, LRU는 과거의 페이지 사용 빈도를 기준으로 한다. 과거에 가장 덜 사용된 페이지를 victim 페이지로 한다.

 

Global replacement vs Local replacement

 

   - 교체 알고리즘 페이지 비교 범위를 모든 프로세스의 페이지로 하는 것을 global, 해당 프로세스의 페이지 만을 기준으로 하는 것을 Local replacement라고 한다.