운영체제. 가상 메모리 관리(교체 기법)

yo·2021년 6월 6일
0

가상 메모리 성능 향상을 위한 관리 기법들

  • Allocation strategies(할당 기법)
  • Fetch strategies
  • Placement strategies(배치 기법)
  • Replacement strategies(교체 기법)
  • Cleaning strategies(정리 기법)
  • Load control strategies(부하 조절 기법)

교체기법

1. Locality

  • 프로세스가 프로그램/데이터의 특정 영역을 집중적으로 참조하는 현상
  • 원인
    • Loop structure in program
    • Array, structure등의 데이터 구조
  • 공간적 지역성(Spatial locality)
    • 참조한 영역과 인접한 영역을 참조하는 특성
  • 시간적 지역성(Temporal locality)
    • 한 번 참조한 영역을 곧 다시 참조하는 특성
      스크린샷 2021-06-05 오후 8 47 28
      스크린샷 2021-06-05 오후 8 47 41

2. 교체 기법 방법들

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

1) MIN(OPT, B0) algorithm

  • 1966년 Belady에 의해 제시
  • Minimize page fault frequency(proved) -> 페이지 폴트를 최소하 시키는 방법으로 이미 증명이 됨.
    • Optimal solution( 다른 말로 최적의 방법이라고 불림)
  • 기법
    • 앞으로 가장 오랫동안 참조되지 않을 page 교체
      • Tie-breaking rule: 동점일 경우, page번호가 가장 큰/작은 페이지 교체
  • 실현 붕가능한 기법(Unrealizable)
    • Page reference string을 미리 알고 있어야 함
  • 교체 기법의 성능 평가 도구로 사용됨
    스크린샷 2021-06-05 오후 8 58 36
    스크린샷 2021-06-05 오후 9 00 34

2) Random Algorithm

  • 무작위로 교체할 page 선택
  • Low overhead
  • No policy

3) FIFO Algorithm

  • 가장 오래된 페이지 교체
  • Page가 적재된 시간 기억하고 있어야 함
  • 자주 사용되는 page가 교체될 가능성이 높음
    • Locality에 대한 고려가 없음
  • FIFO anomaly(Belady's anomaly)
    • FIFO알고리즘의 경우, 더 많은 page frame을 할당 받음에도 불구하고 page fault가 증가하는 경우가 있음
      스크린샷 2021-06-05 오후 9 18 58
      스크린샷 2021-06-05 오후 9 19 14

4) LRU(Least Recently Used) Algorithm

  • 가장 오랫동안 참조되지 않음 page를 교체
  • page참조시마다 시간을 기록해야 함
  • Locality에 기반을 둔 교체 기법
  • MIN 알고리즘에 근접한 성능
  • 실제로 가장 많이 사용되는 기법
  • 단점
    • 참조시 마다 시간을 기록해야 함(Overhead)
      • 간소화된 정보 수집으로 해소 가능(예시: 정확한 시간 대신 순서만 기록)
    • Loop 실행시 필요한 크기보다 작은 수의 page frame이 할당된 경우, page fault수가 급격히 증가함
      스크린샷 2021-06-05 오후 9 22 18
      스크린샷 2021-06-05 오후 9 22 39

5) LFU(Least Frequently Used) Algorithm

  • 가장 참조 횟수가 적은 Page 교체
    • Tie-breaking rule: LRU, 근데 동점 시 룰은 정하기 나름이다!
  • Page 참조시 마다, 참조 횟수를 누적시켜야 함
  • Locality 활용
    • LRU 대비 적은 overhead
  • 단점
    • 최근 적재된 참조될 가능성인 높은 page가 교체될 가능성이 있음
    • 참조 횟수 누적 overhead
      스크린샷 2021-06-05 오후 10 09 29
      스크린샷 2021-06-05 오후 10 10 59

6) NUR(Not Used Recently) Algorithm

스크린샷 2021-06-05 오후 10 15 09 스크린샷 2021-06-05 오후 10 16 02

7) Clock Algorithm

  • IBM VM/370 OS (무슨 말인지 모르곘다)
  • Reference bit 사용함
    • 주기적인 초기화 없음
    • 시계 바늘이 지나가며 초기화 시킴(뒤에 설명 나옴)
  • Page frame들을 순차적으로 가리키는 pointer(시계 바늘)를 사용하여 교체될 page 결정
    스크린샷 2021-06-05 오후 10 21 27
  • Pointer를 돌리면서 교체 page 결정
    • 현재 가리키고 있는 page의 reference bit(r) 확인
    • r = 0인 경우, 교체 page로 결정
    • r = 1인 경우, reference bit 초기화 후 pointer 이동
  • 먼저 적재된 page가 교체될 가능성이 높음
    • FIFO와 유사
  • Reference bit를 사용하여 교체 페이지 결정
    • LRU(or NUR)과 유사
      스크린샷 2021-06-05 오후 10 23 02

8) Second Change Algorithm

스크린샷 2021-06-05 오후 10 24 08
스크린샷 2021-06-05 오후 10 24 23
스크린샷 2021-06-05 오후 10 26 01
스크린샷 2021-06-05 오후 10 34 23

profile
Never stop asking why

0개의 댓글