Replacement Strategies(교체 기법)

Fixed allocation

• 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 change algorithm

Variable allocation

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

지난번까지 Fixed allocation을 알아봤고, 이번 강의부턴 variable allocation을 공부합니다!

Variable Allocation

• 할당하는 메모리의 크기가 가변적인 방법이다.
  총 3가지 방법이 있다: WS(Working Set) algorithm, PFF(Page Fault Frequency) algorithm, VMIN(Variable MIN) algorithm

1. WS(Working Set) algorithm

• 1968년 Denning이 제안
• Working set
  - Process가 특정 시점에 자주 참조하는 page들의 집합
  - 최근 일정 시간(Δ)동안 참조된 page들의 집합
  - 시간에 따라 변함
  - W(t, Δ)
  - The working set of a process at time t
  - Time interval(t-Δ, t)동안 참조된 pages들의 집합
  - Δ: window size, system parameter
  
  
  
• Locality에 기반
• Working set을 메모리에 항상 유지
  • Page fault rate(thrashing) 감소
  • 시스템 성능 향상
• Window size(Δ)는 고정
  - Memory allocation은 가변
  - Δ값이 성능 결정 짓는 중요한 요소
  
• locality 때문에 윈도우가 커져도 working set사이즈 증가율이 감소하는 지점이 온다.(쓰는 것만 계속 쓰기 때문에.)
  
  
  
  
  
  

성능 평가

• Page fault수 외 다른 지표도 함께 봐야 함
• Example
  • Time interval [1,10]
    • # of page fault = 5
    • 평균 할당 page frame 수 = 3.2
  • 평가
    • 평균 3.2개의 page frame을 할당 받은 상태에서 5번의 page fault 발생

특성

• 적재되는 page가 없더라도 메모리를 반납하는 page가 있을 수 있음
• 새로 적재되는 page가 있더라도, 교체되는 page가 없을 수 있음

단점

• Working set management overhead(윈도우 지속적으로 관찰해야 함)
• Residence set(상주 집합)을 page Fault가 없더라도 지속적으로 관리해야 함.
  

Mean number of frames allocated vs page fault rate

• window size가 증가하면 page fault는 감소하지만, 메모리 lifetime도 증가하기 때문에 page 유지비용이 증가한다.
• 이런 것들을 고려해서 적절한 지점을 잘 찾아야 한다.
  

2. PFF(Page Fault Frequency) algorithm

• Residence set size를 page fault rate에 따라 결정
  • Low page fault rate(long inter-fault time)
    • Process에게 할당된 PF 수를 감소
  • High page fault rate(short inter-fault time)
    • Process에게 할당된 PF 수를 증가
• 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
• IFT: Inter Fault Time(페이지 폴트간의 시간 간격)

Algorithm

## 3. VMIN(Variable MIN) algorithm

Example

성능 평가

• 평균 3.7개의 page frame을 할당 받은 상태에서 5번의 page fault 발생

특징

• 메모리 상태 변화가 page fault 발생 시에만 변함
  • Low overhead

3. Variable MIN(VMIN) algorithm

• Optimal algorithm(최적의, 이상적인, 구현 불가능한)
  • 평균 메모리 할당량과 page fault 발생 횟수 모두 고려했을 때의 Optimal
• 실현 불가능한 기법(Unrealizable)
  • Page reference string을 미리 알고 있어야 함
• 기법
  • [t, t+ Δ]을 고려해서 교체할 page 선택

Algorithm

• Page r이 t 시간에 참조 되면, Page r이 (t, t+ Δ) 사이에 다시 참조되는지 확인
• 참조 된다면, page r을 유지
• 참조 안 된다면, apge r을 메모리에서 내림

Example

성능 평가

• 평균 1.6개의 page frame을 할당 받은 상태에서 5번의 page fault 발생

최적 성능을 위한 Δ값

--------------------------------------------------

Other Considerstaions

• Page size
• Program restructuring
• TLB reach

1. Page Size

• 일반적인 page size
  • 

Small page size

• Page Table이 크다. (오버헤드 큼)
• 내부 단편화 감소
• I/O 시간 증가
• Locality 향상
• Page fault 증가

Large page size

• page table이 작다. (오버헤드 작음)
• 내부 단편화 증가
• I/O시간 감소
• Locality 저하
• Page fault 감소

페이지 크기는 클수록 좋은걸까? 아니면 작을수록 좋은걸까?

• No best Answer
• 하지만 요즘은 페이지 크기가 점점 커지는 추세다. 이유는?
  • HW의 발전 경향과 연관이 있다.
  • CPU 성능도 증가하고 메모리 사이즈도 등가하는 추세.
  • 메모리 속도 보다 CPU 속도의 증가가 압도적이기 때문에, I/O를 최소화하는게 좋다.(I/O많으면 CPU가 메모리 기다리느라 병목현상 생김)

2.Program restructuring

• 가상 메모리 시스템의 특성에 맞도록 프로그램을 재구성
• 사용자가 가상 메모리 관리 기법(예, paging system)에 대해 이해하고 있다면, 프로그램의 구조를 변경하여 성능을 높일 수 있음
• 예를 들어 이중 for loop을 비효율 적으로 도는 아래 코드를 수정하며 성능을 개선할 수 있다.
  
  

3.TLB reach

• Direct Address Mapping 할 때 느린 속도의 한계를 개선하기 위해 두는 HW.

TLB Reach란?

- TLB를 통해 접근할 수 있는 메모리의 양
- the number of entries \* the page size

TLB의 Hit ratio를 높이려면?

• TLB 크기 증가
  • Expensive
• Page 크기 증가 or 다양한 page size 지우너
  • OS의 지원이 필요