[Chapter-8] Virtual Memory

-이대 반효경 교수님 강의 기반으로 작성되었습니다-

 

++ virtual memory는 os 가 전적으로 관리

 

Demand Paging

• 프로그램이 필요할 때만 페이지를 메모리에 로드 ==> 차지하는 물리적 메모리 양이 줄어듬 
  • 페이지? : 메모리 관리에서 사용하는 기본 단위
• valid / invalid bit (페이지의 헤더인듯)
  • valid : 해당 페이지가 메모리에 존재
  •  invalid : 페이지가 메모리에 존재 x, 맨 처음에는 모두 invalid

 

Page Fault

• invalid로 표시된 페이지에 접근하는 것
  • 접근 시 mmu(주소 변환 hw) trap 발생
  • 커널쪽에서 page fault handler 콜함 ==> 커널 함수에 있을듯?
    • mm(memory management) dir 내부에 관련 코드가 있다 합니다.
  • page falut로 인해 디스크 접근은 오래 걸리는 작업임

 

Page replacement

• 어떤 frame을 빼앗아 올지... (이미 다 차있다는 가정 하)
• page fault 최소화가 목표 ==> 알고리즘 평가에 중요한 요소

 

Algorithm

• optimal 알고리즘(=opt)
  • 미래 참조 페이지를 안다는 가정 = 불가능
  • 가장 먼 미래에 참조되는 페이지를 replace
• FIFO
  • first in first out : 별 알고리즘 없음
• LRU (Least Recently used)
  • 오래전 참조 지우기
  • 링크드 리스트로 구현, 참조한것을 뒤로
• LFU (Least Frequenty Used)
  • 덜 사용된거 지우기
  • heap으로 구현

 

 

캐싱

• 페이징에서 메모리 = 캐시
• 프로세스A가 메모리에 페이지를 올리면 
  • os는 lfu, lru 불가능 ==> 두 알고리즘은 못쓴다.

 

clock 알고리즘

• 

  빙글빙글

• = lru 근사 알고리즘
  • 네모 안은 reference bit
  • 페이지가 참조 된다면 1로 set (os가 아닌 hw가 함)
  •  돌면서 1은 모두 0으로
  •  0인것을 찾으면 그 페이지는 교체
  • bit를 두개사용 (refer, modified) ==> lfu, lru 모두 쓰는듯이)

 

Allocation

프로세스 마다 page frame 할당?

• Equal allocation : 모든 ps에 똑같이
• Proportional allocation : ps 크기에 따라
• Priority allocation : 우선순위에 따라

Global vs Local Replacement

• Global
  • 다른 프로세스에 할당된 frame 뺏어올 수 있다.
  • working set, pff ...
• Local
  • 할당된 frame 내에서만 replacement
  • fifo, lru, lfu 등의 알고리즘을 ps 별로 운영

 

Thrashing

= page falut 가 너무 빈번(메모리가 너무 적게 할당됨)

==> cpu utilization이 낮아짐

==> os는 cpu 이용률을 보고 프로세스를 더 추가

==> 악순환

so multiprogramming의 degree를 줄여야...(pff, working-set 알고리즘이 이 역할을 한다.)

 

Working-set Model

• locality of ref
  • ps는 특정시간, 일정 장소만 집중적으로 참조
  • 이 페이지를 locality set이라 부른다.
• Working set Model
  • Locality 기반 한번에 메모리에 올라와 있어야 하는 페이지 집합
  • 다 안올라와 있으면 모든 프레임을 반납, swap out
  • 위에 thrashing 방지
    • multiprogramming의 degree를 결정

 

Working-Set Algorithm

• working set window 를 보고 working set을 결정
• page frame 보다 ps들의 working set size 합이 더 크면
  • 일부 ps swap out
• working set을 다 할당 후에도 page frame이 남으면
  • swap out 당한 ps에게 다시 working set 할당
• window size (= 데이터 범위)
  • 작으면 locality set 모두 수용 x
  • 크면 여러 규모 locality set 수용

 

PFF scheme

• multiprogramming의 degree를 조절하면서 thrashing 방지하는 알고리즘
• 직접 page fault rate를 봄
• page fault rate가 높다면 그 프로그램에 page를 더 줌

 

Page size

• 사이즈를 줄이면
  • 페이지 수 증가
  • 페이지 테이블 크기 증가
  • internal fragmentation 감소
  • disk transfer 효율성 감소
  • 필요한 정보만 메모리에 올라옴
• 트렌드는 사이즈 늘리기