9. Virtual Memory

Virtual Memory

Demand Paging

• 실제로 필요할 때 Page를 메모리에 올리는 것
  • I/O 양의 감소
  • Memory 사용량 감소
  • 빠른 응답 시간
  • 더 많은 사용자 수용
• Valid / Invalid bit의 사용
  • Invalid의 의미
    • 사용되지 않는 주소 영역인 경우
    • Page가 물리적 메모리에 없는 경우
  • 처음에는 모든 Page entry가 invalid로 초기화
  • address translation시에 invalid bit이 set 되어 있으면, Page fault

Page Fault

• invalid page를 접근하면 MMU가 Page Fault Trap을 발생시킴
• Kernel mode로 들어가 Page fault handler를 invoke
• 다음 순서로 Page Fault 처리
  • Invalid reference? -> abort process
  • Get an empty page frame (없으면 replace)
  • 해당 Page를 disk에서 memory로 읽어옴
    • disk I/O가 끝나기까지 이 프로세스는 block
    • Disk read가 끝나면 Page table entry 기록 후, valid bit set
    • Ready queue에 process 삽입
  • 이 프로세스가 CPU 잡고 다시 running
  • 아까 중단되었던 intruction 재개

free frame이 없는 경우

• Page replacement
  • 어떤 frame을 뺴앗아올지 결정해야 함
  • 곧바로 사용되지 않을 Page 쫓아내는 것이 좋음
  • 동일 Page가 여러 번 메모리에서 쫓겨났다가 다시 들어올 수 있음
• Replacement Algorithm
  • Page-fault rate을 최소화하는 것이 목표
  • 주어진 Page reference string에 대해 Page fault를 얼마나 내는지 조사하여 평가 가능

Optimal Algorithm

• 가장 먼 미래에 참조되는 Page를 replace
• 현실적으로 불가능하기 때문에 다른 알고리즘의 성능에 대한 Upper bound 제공

FIFO Algorithm

• FIFO Anomaly: frame 수를 올렸음에도, Page fault의 수가 늘어날 수 있음

LRU Algorithm

• 가장 오래 전에 참조된 Page를 replace

LFU Algorithm

• 최저 참조 횟수의 Page를 replace
• 최저 참조 횟수 page가 여러 개인 경우?
  • 여러 Page 중 임의로 선정하거나,
  • 성능 향상을 위해 가장 오래 전에 참조된 Page를 replace
• 장단점
  • LRU처럼 직접 참조 시점만 보는 것이 아리나 장기적 시간 규모를 보기 때문에 Page의 인기도를 더 정확히 반영할 수 있음
  • 참조 시점의 최근성을 반영하지 못함
  • LRU 보다 구현이 복잡함
• LRU vs. LFU

LRU와 LFU 알고리즘의 구현

다양한 캐싱 환경

• 캐싱 기법
  • 한정된 빠른 공간(캐시)에 요청된 데이터를 저장해두었다가 후속 요청 시 캐시로부터 직접 서비스하는 방식
  • Paging System 외에도 Cache memory, buffer caching, web caching 등 다양한 분야에서 사용
• 캐시 운영의 시간 제약
  • 교체 알고리즘에서 삭제할 항목을 결정하는 일에 지나치게 많은 시간이 걸리는 경우 실제 시스템에서 사용할 수 없음
  • Buffer caching이나 Web caching의 경우
    • O(1)에서 O(log N) 정도까지 허용
  • Paging System의 경우
    • Page fault의 경우에만 운영체제가 관여
      • Page가 이미 메모리에 존재하는 경우 참조 시간 등의 정보를 운영체제가 알 수 없음
      • LRU의 list 조작 조차 불가능

Clock Algorithm

• LRU의 근사 알고리즘
• a.k.a Second chance algorithm, NRU(Not Recently Used)
• Referece bit를 사용해서 교체 대상 페이지 선정
  • Reference bit가 0인 것을 찾을 때 까지 포인터를 하나씩 앞으로 이동
• 포인터가 이동하는 중에 Reference bit 1은 모두 0으로 set
• Reference bit이 0인 것을 찾으면 해당 Page 교체
• 한 바퀴 되돌아와서도(=Second chance) 0이면 그 때 replace
  • 자주 사용되는 Page라면 Second chance 올 때 1
• Clock Algorithm의 개선
  • reference bit와 modified bit를 함께 사용
  • reference bit = 1; 최근에 참조된 Page
  • modified bit = 1; 최근에 변경된 Page(I/O 동반하는 page)
  • 가능한 modified bit이 0인 Page를 쫓아내서 시간 단축할 수 있을 것

Page Frame의 Allocation

• Allocation problem: 각 프로세스에 얼마만큼의 Page frame을 할당할 것인가?
• Allocation의 필요성
  • 메모리 참조 명령어 수행 시 명령어, 데이터 등 여러 Page 동시 참조
    • 명령어 수행을 위해 최소 할당되어야 하는 frame 수가 존재
  • Loop를 구성하는 Page들은 한꺼번에 allocate되는 것이 유리함
    • 최소한의 allocation이 없으면 매 loop 마다 page fault
• Allocation Sheme
  • Equal allocation: 모든 프로세스에 똑같은 개수 할당
  • Proportinal allocation: 프로세스 크기에 비례하여 할당
  • Priority allocation: 프로세스의 priority에 따라 다르게 할당

Global vs. Local Replacement

• Global replacement
  • Replace 시 다른 프로세스에 할당된 frame을 뺏을 수 있음
  • 프로세스 별 할당량을 조절하는 또 다른 방법
  • FIFO, LRU, LFU 등의 알고리즘을 global replacement로 사용 시에 해당
  • Working set, PFF 알고리즘 사용
• Local replacement
  • 자신에게 할당된 frame 내에서만 replacement
  • FIFO, LRU, LFU 등의 알고리즘을 프로세스 별로 운영

Thrashing

• 프로세스의 원활한 수행에 필요한 최소한의 Page frame 수를 할당 받지 못한 경우 발생
• Page fault rate가 매우 높아짐
• CPU utilization이 낮아짐
• 운영체제는 Multiprogramming degree를 높여야 한다고 판단
• 또 다른 프로세스가 시스템에 추가됨
• 프로세스 당 할당된 frame의 수가 더욱 감소
• 프로세스는 page의 swap in / swap out으로 매우 바쁨
• CPU가 idle 해지는 현상 발생
• Low throughput

Working-set Model

• Locality of reference
  • 프로세스는 특정 시간 동안 일정 장소만을 집중적으로 참조
  • 집중적으로 참조되는 해당 Page들의 집합을 Locality set이라 함
• Working-set Model
  • Locality에 기반하여 프로세스가 일정 시간 동안 원활하게 수행되기 위해 한 번에 메모리에 올라와 있어야 하는 Page들의 집합을 Working Set이라 정의
  • Working Set 모델에서는 프로세스의 Working Set 전체가 메모리에 올라와있어야 수행되고 그렇지 않을 경우 모든 frame을 반납한 후 Swap out
  • Thrashing을 방지!
  • Multiprogramming degree를 결정

• Working set의 결정
  • Working set window를 통해 알아냄
  • window size가 delta인 경우,
    • Working set에 속한 Page는 메모리에 유지, 속하지 않은 것은 버림
    • 즉, 참조된 후 delta 시간 동안 해당 page를 메모리에 유지한 후 버림
  • 시간 별로 Working set의 크기는 유동적으로 변함
• Window size delta
  • Working set을 제대로 탐지하기 위해서는 Window size를 잘 결정해야 함
  • delta 값이 너무 작으면 locality set 모두 수용하지 못할 우려
  • delta 값이 너무 크면 여러 규모의 locality set 수용
• Working-set Algorithm
  • 프로세스들의 working set size의 합이 page frame 보다 큰 경우
    • 일부 프로세스를 swap out 시켜 남은 프로세스의 working set을 우선적으로 충족시킴
  • Working set을 다 할당하고도 Page frame이 남는 경우
    • Swap out 되었던 프로세스에게 Working set 할당

PFF(Page Fault Frequency) Model

• Page fault rate의 상한값과 하한값을 설정
  • Page fault rate이 상한값을 넘으면 frame을 더 할당
  • Page fault rate이 하한값 이하이면 할당 frame 수를 줄임
• 빈 frame이 없으면 일부 프로세스를 Swap out

Page Size의 결정

• Page size를 감소시키면
  • Page 수 증가
  • Page table 크기 증가
  • Internal fragmentation 감소
  • Disk Transfer의 효율성 감소
    • Seek/Rotation vs. Transfer
  • 필요한 정보만 메모리에 올라와 메모리 이용이 효율적
    • Locality의 활용 측면에서는 좋지 않음
• 트렌드는 Larger page size