[PintOS, Project 3] Virtual Memory Management - Variable Allocation and Consideration

 

Working Set (WS) Algorithm

Working Set

  - Process가 특정 시점에 자주 참조하는 page들의 집합

  - 최근 일정시간 동안(Δ) 참조된 page들의 집합

  - 시간에 따라 변함

  - W(t, Δ)

     ㆍThe working set of a process at time t

     ㆍTime interval [t-Δ, t] 동안 참조된 pages들의 집합 (t-Δ, t]는 포함되지 않음)

     ㆍΔ : window size, system parameter

 

Working set memory management

  - Locality에 기반을 둠

  - Working set을 메모리에 항상 유지

    ㆍPage fault rate (thrashing) 감소

    ㆍ시스템 성능 향상

  - Window size (Δ) 고정

    ㆍMemory allocation은 가변

    ㆍΔ 값이 성능을 결정 짓는 중요한 요소

 

 

그림 1. Window size와 Working Set size의 관계

 그림 1에서 좌측(초반부)은 window size가 조금만 늘어나도 working set size가 급격히 늘어났으나, 우측(후반부)로 갈수록 window size가 늘어나도 working set size가 그다지 늘어나지 않는 것이 관측된다. 이는 locality때문에 일어나는 현상이다.

 

 

 

성능 평가

  - Page fault 수 외 다른 지표도 함께 봐야 한다.

    -> 평균 보유 page frame과 발생한 page fault 수를 비교한다.

 

 

특성

  - 적재되는 page가 없더라도, 메모리를 반납하는 page가 있을 수 있음

  - 새로 적재되는 page가 있을 지라도, 교체 되는 page가 없을 수 있음

 

 

단점

  - Working set management overhead

     -> 변화가 없더라도 지속적으로 window를 관찰해야 하므로 overhead가 높다.

  - Residence set (상주 집합)을 Page fault가 없더라도, 지속적으로 관리해야 함

 

 

 

그림 2. Page의 lifetime과 page fault rate의 관계

 lifetime을 높게 유지한다면, page의 유지 비용이 높아진다. 그러나 lifetime이 지나치게 짧으면 page fault rate가 급격하게 올라가기 때문에 이 사이에서 적절한 균형을 맞춰야한다.

 

 

 

Page Fault Frequency (PFF) Algorithm

Residence set size를 page fault rate에 따라 결정

  - Low page fault rate (long inter-fault time) : Memory Allocation 감소

    ㆍProcess에게 할당된 Page Frame 수를 감소

  - High page fault rate (short inter-fault time) : Memory Allocation 증가

    ㆍProcess에게 할당된 Page Frame 수를 증가

  -> 메모리 상태 변화가 page fault 발생 시에만 변함

 

 

Resident set 갱신 및 메모리 할당

  - Page fault가 발생 시에만 수행

  - Low overhead

 

 

Criteria for page fault rate

  - IFT > τ : Low page fault rate

  - IFT < τ : High page fault rate

  - τ : threshold value : System Parameter

 

 

Algorithm

  1) Page fault 발생 시, IFT 계산

      ㆍIFT = tc - tc-1

         (tc : 현 page fault 발생 시간, tc-1 : 이전 page fault 발생 시간)

  2) IFT > τ (Low page fault rate)

      ㆍREsidence set <- (tc-1, tc] 동안 참조 된 page들만 유지

      ㆍ나머지 page들은 메모리에서 내림 -> 메모리 할당 유지 or 감소

  3) IFT ≤ τ (High page fault rate)

      ㆍ기존 pages들 유지

      ㆍ현재 참조된 page를 추가 적재 -> 메모리 할당 증가

 

 

 

Variable MIN (VMIN) algorithm

Variable allcation 기반 교체 기법 중 optimal algorithm

  - 평균 메모리 할당량과 page fault 발생 횟수 모두 고려 했을 때의 Optimal

 

실현 불가능한 기법 (Unrealizable)

  - Page reference string을 미리 알고 있어야 함

 

 

최적 성능을 위한 Δ의 값은?

  - Δ = R / U

     ㆍU : 한번의 참조 시간 동안 page를 메모리에 유지하는 비용

     ㆍR : page fault 발생 시 처리 비용

 

  - R > Δ * U (Δ가 작으면)

     ㆍ처리 비용 > page 유지 비용

  - R < Δ * U (Δ가 크면)

     ㆍPage fault 처리 비용 < 유지 비용

 

 

 

 

Page Size

  - 시스템 특성에 따라 다름

  - 일반적인 page size는 128 byte ~ 4M byte

 

Small page size

  - Large page table : page size가 작으면 page의 수는 많아진다. -> High overhead

  - 내부 단편화 감소

  - IO 시간 증가

  - Locality 향상

  - Page fault 증가

 

Large page size

  - Small page table : Page size가 커지면 page의 수는 많아진다 -> Small overhead

  - 내부 단편화 증가

  - IO 시간 감소

  - Locality 저하

  - Page fault 감소

 

 

※ 시대가 발전할수록 Page의 크기가 점점 커지는 이유

  - Memory size 가 작으면 page 수가 많아져서 kernel의 부담이 점점 커진다. -> 상대적인 Page Fault 처리 비용 증가

  - CPU의 처리 용량 발전 속도에 비해서 Disk의 속도는 따라잡지 못하고 있다. -> IO 병목현상 발생

  

-> Page Fault 처리 비용을 감소시키고, IO 병목현상을 줄이기 위해서 page의 크기를 점점 크게 한다.

 

 

TLB Reach

TLB를 통해 접근할 수 있는 메모리의 양

  - entry의 수 * page size

 

TLB의 hit ratio를 높이려면?

  - TLB의 크기 증가 : Expensive

  - Page의 크기 증가 혹은 다양한 page size 지원

    -> 최근 OS의 발전 경향