[PintOS, Project 3] Virtual Memory Management - Replacement Strategies for Fixed Allocation

Locality;지역성

 프로세스가 프로그램/데이터의 특정 영역을 집중적으로 참조하는 현상

 

  - 원인 :

     ㆍLoop structure in program (for문, while문)

     ㆍArray, structure 등의 데이터 구조 (한 구조체에서 값을 불러왔을 때, 짧은 시일 내에 그 구조체에서 다른 값을 호출할 가능성이 높다)

 

  - 공간적 지역성 (Spatial locality)

     ㆍ참조한 영역과 인접한 영역을 참조하는 특성

 

  - 시간적 지역성 (Temporal locality)

     ㆍ한 번 참조한 영역을 곧 다시 참조하는 특성

 

 

Replacement Strategies

  - Fixed allocation : 한 프로세스에게 정해진 수의 page frame을 할당한다.

     ㆍMIN(OPT, B0) algorithm
     ㆍRandom algorithm
     ㆍFIFO(First In First Out) algorithm
     ㆍLRU(Least Recently Used) algorithm
     ㆍLFU(Least Frequently Used) algorithm
     ㆍNUR(Not Used Recently) algorithm
     ㆍClock algorithm

     ㆍSecond chance algorithm

 

  - Variable allocation : 

     ㆍWS(Working Set) algorithm
     ㆍPFF(Page Fault Frequency) algorithm
     ㆍVMIN(Variable MIN) algorithm

 

 

Min Algorithm (OPT algorithm)

  - 1966년 Belady에 의해 제시

  - Minimize page fault frequency : page fault를 기준으로 정립한 알고리즘 (Optimal solution이라고도 부른다)

  - 기법 :

     ㆍ앞으로 가장 오랫동안 참조되지 않을 page 교체

     ㆍTie-breaking rule : page 번호가 가장 큰/작은 페이지 교체

 

  -> 미래를 예측해야 되기 때문에 실현 불가능한 기법이다. 

  -> 교체 기법의 성능 평가 도구로 사용됨 

       -> 미리 교체될 page를 알고 있는 상태에서 Min Algorithm을 적용하면 최적의 방법이 된다. 여기에 평가하고 싶은 교체 기법을 적용시킨 뒤, Min Algorithm과 비교해봐서 얼마나 근접한지로 성능을 평가할 수 있다.

 

 

 

Random Algorithm

  - 무작위로 교체할 page 선택

  - Low overhead 

 

 

FIFO Algorithm

  - 가장 오래된 page를 교체

     -> Page가 적재된 시간을 기억하고 있어야 한다.

 

  - Locality에 대한 고려가 없다

     -> 자주 사용되는 page가 교체 될 가능성이 높음

 

그림 1. FIFO anomaly 의 예

 - FIFO anomaly (Belady's anomaly)

     -> FIFO 알고리즘의 경우, 더 많은 page frame을 할당 받음에도 불구하고 page fault 의 수가 증가하는 경우가 생김

 

 그림 1에서 page를 3개에서 4개로 늘렸음에도 불구하고 page fault가 늘어난 것을 확인할 수 있다.

 

 

LRU (Least Recently Used) Algorithm

가장 오랫동안 참조되지 않은 page를 교체

  - Page 참조 시 마다 시간을 기록해야 함

  - Locality에 기반을 둔 교체 기법

  - MIN Algorithm에 근접한 성능을 보여줌

  - 실제로 가장 많이 활용되는 기법 

 

단점

  - 참조 시 마다 시간을 기록해야 함 (Overhead)

    ㆍ간소화된 정보 수집으로 해소 가능

  - Loop 실행에 필요한 크기보다 작은 수의 page frame이 할당 된 경우, page fault 수가 급격히 증가함

    -> Allocation 기법에서 해결해야 함

 

 

 

LFU (Least Frequently Used) Algorithm

가장 참조 횟수가 적은 Page를 교체

  - Page 참조 시 마다, 참조 횟수를 누적시켜야 함

  - Locality 활용 : LRU 대비 적은 overhead

 

단점

  - 최근 적재된 참조될 가능서인 높은 page가 교체 될 가능성이 있음

  - 참조 횟수 누적 overhead

 

 

NUR(Not Used Recently) Algorithm

최근에 사용되지 않은 Page를 교체

  - LRU보다 적은 overhead로 비슷한 성능 달성 목적

 

Bit vector 사용

  - Reference bit vector (r), Update bit vector (m)

 

 

 

Clock Algorithm

주기적인 초기화 없이 Reference bit를 사용함

Page frame들을 순차적으로 가리키는 pointer를 사용하여 교체될 page 결정

 

그림 2. Clock Aglorithm 의 도식화

  - Pointer를 돌리면서 교체 Page 결정

     ㆍ현재 가리키고 있는 page의 reference bit(r) 확인

     ㆍr = 0 인 경우, 교체 page로 결정

     ㆍr = 1 인 경우, reference bit 초기화 후, pointer 이동

 

  - 먼저 적재된 page가 교체될 가능성이 높음 (FIFO와 유사)

  - Reference bit를 사용하여 교체 페이지 결정 (LRU 나 NUR와 유사 -> Locality를 활용함)

 

 

Second Chance Algorithm

Clock algorithm과 유사

Update bit (m)도 함께 고려함 

그림 3. Second Chance Algorithm

현재 가리키고 있는 page의 (r, m)확인

(0,0) : 교체 page로 결정

(0,1) : write-back (cleaning) list에 추가 후, (0,0)으로 갱신

(1,0) : (0,0)으로 갱신

(1,1) : (0,1)으로 갱신