운영체제 9-1 Virtual Memory

Demand Paging // 요청이 있으면 페이지에 올리겠다.

• 실제로 필요로할 때 page를 메모리에 올리는 것
  - I/O양의 감소
  - Memory 사용량 감소
  - 빠른 응답 시간
  - 더 많은 사용자 수용

• Valid / Invalid bit의 수용
  - Invalid의 의미
  #사용되지 않는 주소 영역인 경우
  #페이지가 물리적 메모리에 없는 경우
  - 처음에는 모든 page entry가 invalid로 초기화
  - address translation 시에 invalid bit이 set되어 있으면
  =>"page fault"

Memory에 없는 Page의 Page Table

Page Fault

• invalid page를 접근하면 MMU가 trap을 발생시킴 (Page fault trap)
• Kernel mode로 들어가서 page fault handler가 invoke됨
• 다음과 같은 순서로 page fault를 처리한다.

1. Invalid reference? (eg. bad address, protection violation) => abort process (잘 못된 요청이 아닌지)
2. Get an empty page frame (없으면 뻇어 온다.: replace)
3. 해당 페이지를 disk에서 memory로 읽어온다.(메모리보다 디스크가 훨씬 느리다.)
   #1. disk I/O가 끝나기까지 이 프로세스는 CPU를 preempt당함 (block)
   #2. Disk read가 끝나면 page tables entry 기록, valid/invalid bit = "valid"
   #3.ready queue에 process를 insert => dispatch later
4. 이 프로세스가 CPU를 잡고 다시 running
5. 아까 중단되었던 instruction을 재개

Steps in Handling a Page Fault

Performance of Demand Paging

page fault 가 0 이면 메모리에서 다 참조
page fault 가 1 이면 매번 메모리 참조 할 때마다 Page Fault가 발생한다는 의미이다.

Free frame이 없는 경우

• Page replacement
  - 어떤 frame을 빼앗아올지 결정해야 함
  - 곧 바로 사용되지 않을 page를 쫓아내는 것이 좋음
  - 동일한 페이지가 여러번 메모리에서 쫓겨났다가 다시 들어올 수 있ㄴ음

• Replacement Algorithm
  - page-fault rate을 최소화하는 것이 목표
  - 알고리즘의 평가
  #주어진 page reference string에 대해 page fault를 얼마나 내는지 조사
  - reference string의 예
  #1,2,3,4,1,2,5,1,2,3,4,5

Optimal Algorithm

페이지교체 알고리즘 1. FIFO(First In First Out) Algorithm

페이지교체 알고리즘 2. LRU (Least Recently Used) Algorithm

페이지교체 알고리즘 3. LFU (Least Frequently Used) Algorithm

• LFU 참조 횟수(reference count)가 가장 적은 페이지를 지움
  -최저 참조 횟수인 page가 여럿 있는 경우
  #LFU 알고리즘 자체에서는 여러 page 중 임의로 선정한다.
  #성능 향상을 위해 가장 오래전에 참조된 page를 지우게 구현할 수도 있다.
  -장단점
  #LRU처럼 직전 참조 시점만 보는 것이 아니라 장기적인 시간 규모를 보기 때문에 page의 인기도를 좀 더 정확히 반영할 수 있음
  #참조 시점의 최근성을 반영하지 못함
  #LRU보다 구현이 복잡함

LRU와 LFU 알고리즘 예제