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

• 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)
  • 한 번 참조한 영역을 곧 다시 참조하는 특성
    
    

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을 미리 알고 있어야 함
• 교체 기법의 성능 평가 도구로 사용됨
  
  

2) Random Algorithm

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

3) FIFO Algorithm

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

4) LRU(Least Recently Used) Algorithm

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

5) LFU(Least Frequently Used) Algorithm

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

6) NUR(Not Used Recently) Algorithm

7) Clock Algorithm

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

8) Second Change Algorithm