[운영체제-김덕수 교수님] 가상 메모리 관리(5/6) - 가변 할당에서 교체 전략

프로세스에게 할당되는 페이지 프레임의 개수가 실시간으로 변하는 상황에서,
페이지 프레임 교체전략을 알아보자.
그런데 한가지 고민이 되는 것이 있다. 앞으로 들어올 Page frame 은 예측할 수 없다.
예측 할 수 없는 실체를 어떻게 교체한단 말인가?
페이지 프레임 이외에 새로운 단위가 필요할 것 같다.
시간이라는 요소를 좀더 적극적으로 사용한 Working Set algorithm, PFF algorithm, VMIN algorithm 을 배워보자

목차.
1. 개요
2. Working Set(WS) algorithm
    1. WS에서 메모리 관리
    2. Window size 와 Working Set size
    3. Working Set Transition
    4. 성능 평가
    5. 특징 및 장단점
3. Page Fault Frequency(PFF) algorithm
    1. Page Fault rate 의 기준
    2. PFF algorithm
    3. 성능 평가
4. VMIN algorithm
    1. algorithm
    2. 성능 평가
    3. 최적의 𝛥(델타) 
5. 결론

1. 개요

• Variable allocation
  • 프로세스에게 주는 메모리 공간의 크기가 프로세스 실행 중 실시간으로 변화 가능한 할당 전략
• 종류
  • WS(Working Set) algorithm
  • PFF(Page Fault Frequency) algorithm
  • VMIN(Variable MIN) algorithm

2. Working Set(WS) algorithm

• 1968년 Denning 제안
• Working Set
  • Process가 특정 시점에 자주 참조하는 page 들의 집합
  • 최근 일정시간(t) 동안 참조된 page들의 집합
• window: 우리가 바라봐야하는 영역
• 예상 페이지의 개수
  • 최소 : 1
  • 최대 : 𝛥 + 1
• 시간에 따라 변함
• W(t, 𝛥)
  • The working set of a process at time t
  • Time interval [t-𝛥, t] 동안 참조된 pages 들의 집합
  • 𝛥(델타): window size, system parameter

2.1. Working set memory management

• Locality에 기반을 둠
• Working set 을 메모리에 항상 유지
  • Page fault rate(thrashing) 감소
  • 시스템 성능 향상
• window size(𝛥) 는 고정
  • Memory allocation 은 가변
    • MA 가 고정 and 𝛥 가 가변 => LRU
  • 𝛥 값이 성능을 결정 짓는 중요한 요소

2.2. Window size vs. Working Set size

• locality 때문에 확 급증하다가, 점차 감소세를 띔
  • 그 이유는 아무리 윈도우 사이즈를 키워도, 프로세스가 참조하는 페이지 프래임은 한 곳에 모여있을 가능성이 높아서
    일정 수준을 지나면 증가세가 둔화를 띔

‏‏‎ ‎

2.3. Working set transition

• WS 이 전환할 때 일시적으로 페이지 프레임의 수가 늘어나는 현상

• 설명하기가 너무 까다롭네요. 영상을 직접 보시길..ㅠㅠ

‏‏‎ ‎

2.4. 성능 평가

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

page fault 뿐 아니라 평균 page frame 도 성능 평가시 고려해야함

‏‏‎ ‎

2.5. 특징 및 장단점

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

‏‏‎ ‎

단점

• working set management overhead
• Residence set(상주 집합)을 page fault 가 없더라도, 지속적으로 관리해야함

‏‏‎

window size 가 클수록 lifeTime 도 길고 page fault rate 도 적어지지만 비용이 많이 든다.

그리고 교차점이라고 꼭 선택해야하는 것은 아니다.

‏‏‎ ‎

3. Page Fault Frequency (PFF) 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

3.1. Criteria for page fault rate

• IFT > 𝜏 : Low page fault rate
• IFT < 𝜏 : High page fault rate
• 𝜏(타우) : threshold value
  • System parameter
• IFT
  • Inter Fault Time: page fault 가 일어난 간격의 시간

3.2. PFF Algorithm

1. Page fault 발생시, IFT 계산
2. IFT > 𝜏 (Low page fault rate)
   1. residence set <- [𝜏c-1, 𝜏c] 동안 참조 된 page 들 만 유지
   2. 나머지 page들은 메모리에서 내림
      1. 메모리 할당(# of page frame) 유지 or 감소
3. IFT <= 𝜏 (higg page fault rate)
   1. 기존 pages 들 유지
   2. + 현재 참조된 page 를 추가 적재
      1. 메모리 할당(# of page frames) 증가

3.3. 성능 평가

• Page fault 수 외 다른 지표도 함께 봐야 함
• Example
  • Time Interval [1,10]
    • # of page fault = 5
    • 평균 할당 page frame 수 = 3.7
  • 평가
    • 평균 3.7 개의 page frame 을 할당 받은 상태에서 5번의 page fault 발생
• 특징
  • 메모리 상태 변호가 page fault 발생 시에만 변함
    • Low overhead

4. Variable MIN(VMIN) algorithm

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

4.1. Algorithm

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

• 잘 모르겠습니다. 문송합니다.

‏‏‎ ‎

4.2. 성능 평가

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

‏‏‎ ‎

4.3. 최적의 성능을 위한 𝛥(델타) 값은?

• 𝛥 = R / U
  • U: 한번의 참조 시간 동안 page 를 메모리에 유지하는 비용
  • R: page fault 발생 시 처리 비용
• R > 𝛥 * U (𝛥 가 작으면)
  • 처리 비용 > page 유지 비용
• R < 𝛥 * U( 𝛥가 크면)
  • page fault 처리비용 < 유지 비용

‏‏‎ ‎

5. 결론

TO. 미래의 나

과거의 너는 잘 이해를 못했는데,
나중에 추가적인 자료를 보면 잘 이해하기를 바란다.