운영체제 - Virtual Memory

Demand Paging

• 실제로 필요할 때 page를 메모리에 올리는 것
  • I/O 양의 감소
  • Memory 사용량 감소
  • 빠른 응답 시간
  • 더 많은 사용자 수용
• Valid / Invalid bit
  • Invalid
    • 사용되지 않는 주소 영역인 경우
    • page가 물리적 메모리에 없는 경우
  • address translation 시에 invalid bit이 set되어 있으면 "page fault"
    => CPU가 운영체제로 넘어감

Page Fault

• Invalid page를 접근하면 MMU가 trap을 발생시킴
• Kernel mode로 들어가서 page fault handler가 실행됨
• 처리 과정
  1. Invalid reference? (eg. bad address, protection violation) => abort
  2. 빈 page frame을 가져온다 (없으면 뺏어옴, replace)
  3. 해당 page를 disk에서 memory로 읽어온다
     (1) disk I/O가 끝나기까지 이 프로세스는 CPU를 preempt 당함(block)
     (2) Disk read가 끝나면 page tables entry 기록, valid/invalid bit = "valid"
     (3) ready queue에 process를 insert
  4. 이 프로세스가 CPU를 잡고 다시 run

Page Replacement

• 어떤 frame을 빼앗아올지 결정해야 함
• page fault rate을 최소화하는 것이 목표

  Replacement Algorithm

  • Optimal Algorithm
    • 미래의 reference를 알고있다고 가정
    • 가장 먼 미래에 참조되는 page를 replace
    • 다른 알고리즘의 성능에 대한 upper bound 제공

  FIFO Algorithm

  • 먼저 들어온 것을 먼저 내쫓음
  • FIFO Anomaly(Belady's Anomaly) : more frames => more page faults

  LRU(Least Recently Used) Algorithm

  • 가장 오래전에 참조된 것을 지움
  • O(1) complexity (linked-list를 이용해 구현)

  LFU(Least Frequently Used) Algorithm

  • 참조 횟수가 가장 적은 페이지를 지움
  • 최저 참조 횟수인 page가 여러개 있는 경우
    • 여러 page 중 임의로 선정
    • 성능 향상을 위해 가장 오래 전에 참조된 page를 지우게 구현할 수도 있음
  • O(log n) complexity (heap을 이용해 구현)

Caching

• 한정된 빠른 공간에 요청된 데이터를 저장해 두었다가 후속 요청시 캐시로부터 직접 서비스하는 방식
• paging system 외에도 cache memory, buffer caching, web caching 등 다양한 분야에서 사용
• paging system에서는 실제로 LRU, LFU같은 알고리즘을 적용할 수 없음
  • page fault가 일어난 경우에만 CPU가 OS로 넘어가기 때문에 모든 정보를 받아올 수 없음

Clock Algorithm

• LRU의 근사 알고리즘
• reference bit을 이용
• 하드웨어가 page가 참조될 때 reference bit을 1로 설정
• OS는 reference bit이 0인 것을 쫓아내고, 이동하는 중에 1은 0으로 바꿈

Global/Local Replacement

• Global replacement
  : Replace시 다른 process에 할당된 frame을 뺏어 올 수 있다
• Local replacement
  : 자신에게 할당된 frame 내에서만 replacement