운영체제. 가상 메모리 관리

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의 지원이 필요

좋은 웹페이지 즐겨찾기