[운영체제] Virtual Memory

Demand Paging

• 요청이 있으면 page를 메모리에 올리는 것
• I/O 감소
• Memory 사용량 감소
• 빠른 응답 시간
• 더 많은 사용자 수용
• Valid bit의 사용
  • Invalid : 사용되지 않은 주소 영역이거나, 페이지가 물리적 메모리에 없는 경우
  • 처음에는 모든 page entry 가 invalid 로 초기화
  • address translation 시에 invalid bit이 되어 있으면 → Page Fault

Page Fault

• invalid page 접근 시 MMU 가 trap을 발생시킴
• 순서
  1. 비정상적 메모리 요청 감지 → 만약 그러면 abort
  2. 빈 페이지 프레임을 가져옴 → 없으면 뺏어옴
  3. 해당 페이지를 disk에서 메모리로 읽어옴
  4. 페이지 테이블에 해당 페이지 저장

Free Frame이 없는 경우

• page replacement
  • 어떤 frame 을 뻇어올 지 결정하는 부분
• 알고리즘
  • 페이지 폴트 비율을 최소화하는 것이 목표
  • page reference string에 대해 page fault 가 얼마나 나는지를 조사

옵티멀 알고리즘

• 가장 먼 미래에 참조되는 page를 replace
• 이를 미리 알고있다고 가정 → 실제 사용할 수는 없지만, 다른 알고리즘의 성능에 대한 upper bound 제공

FIFO (First In First Out)

• 먼저 들어온 것을 먼저 내쫓음
• Belady’s Anomaly (FIFO Anomaly)
  • 더 많은 프레임을 주면 페이지 폴트가 줄어야 함 → 근데 더 늘음 (더 나빠짐)

LRU (Least Recently Used)

• 가장 오래 전에 참조된 것을 지움
• 최근에 참조되는게 또 참조될 가능성이 높음

LFU (Least Frequently Used)

• 참조 횟수가 가장 적은 페이지를 지움
  • 최저가 여러개면
    • LFU 자체에서는 임의로 선정
    • 성능 향상을 위해 가장 오래 전에 참조된걸 지우게 만들 수도 있음
• 장단점
  • 장기적인 시간 규모를 보므로 page 인기도를 더 볼수 있음 그러나 새로 오는 인기있는 거를 버릴 수도 있음
  • 구현이 복잡함

LRU와 LFU 알고리즘 구현

• LRU : 링크드 리스트 - O(1) - 맨 앞에 있는 애를 버리면 됨
• LFU : 순차 검색이면 O(n) → heap 자료구조를 활용하여 O(log n)으로 만듦

다양한 캐시 환경

• 한정된 빠르 ㄴ공간에 데이터를 저장해두었다가 후속 요청 시 캐시로부터 직접 서비스하는 방식
• 교체 알고리즘에서 지나치게 긴 시간이 걸리면 안됨
• paging system의 경우
  • LRU, LFU 가 가능한가?
    • 운영체제가 그러한 정보를 알수있나? → 알수 없음
    • 접근 시간, 참조 횟수등을 page fault 발생시에 알수 없음
    • 결국 사용할 수 없음
  • 그러면 어떻게 하나?
    • Clock Algorithm

Clock Algorithm

• LRU의 근사 알고리즘
• NRU, NUR 이라고도 부름
• Second chance
• 참조가 되면 reference bit가 1이됨 → 하드웨어가 그렇게 함
• 1이면 0으로 바꾸고 다음 → 처음 만난 0을 교체함
• 개선
  • reference, modifed 비트를 함께 사용
  • modified bit (dirty bit) - 수정 여부 확인 비트 → 쫓아낼 때 1이면 disk에 write하고 내쫓음

Page Frame의 allocation

• 각 프로세스에 얼마만큼의 page frame을 할당할 것인가?
• Loop를 구성하는 page들은 한꺼번에 할당되는것이 유리함
  • 최소한의 할당이 없으면 매 루프마다 page fault
• Equal allocation : 모든 프로세스 똑같이 할당
• Proportional allocation : 프로세스 크기 비례해서 할당
• Priority allocation : Priority에 따라 다르게 할당

Global vs Local Replacement

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

Thrashing

• 프로세스의 원활한 수행에 필요한 최소한의 page frame 수를 할당 받지 못한 경우 발생
• 페이지 폴트 빈번
• CPU 이용률 낮아짐
• 메모리에 너무 많은 프로그램이 올라가서 발생
• OS는 CPU 이용률이 낮아지므로 프로그램을 더 올려야 한다고 판단

Working set model

• 참조 지역성
  • 프로세스는 특정 시간 동안 일정 장소만을 집중적으로 참조
  • 집중 참조 Page들의 집합을 locality set 이라 함
• 프로세스의 working set 모두가 올라와야 수행되고 그렇지 않은 경우 모든 frame을 반납한 후 swap out
• Thrashing을 방지함
• Multiprogramming degree를 결정

working set algorithm

• 윈도우 사이즈를 고정하여 그 안에 있는 page들을 working set으로 간주
• 그 안에 있는 page들을 모두 올라오게 하거나, 불가능하면 모두 swap out
• 이들을 유지시킴
• 참조된 후 고정 시간동안 해당 page를 메모리에 유지한 후 버림
• Window size를 잘 결정해야함

PFF (Page Fault Frequency) scheme

• page fault rate의 상한값, 하한값을 둔다
• 상한값을 넘으면 frame 더 할당
• 하한값 이하이면 할당 frame 수 줄임

page size의 결정

• 감소시키면
  • 페이지 수 증가
  • 페이지 테이블 크기 즈악
  • Internal fragmentation 감소
  • Disk transfer의 효율성 감소
  • 필요한 정보만 올라오므로 메모리 이용이 효율적이지만 locality 측면에서는 좋지 않음
• 요즘은 페이지 사이즈를 늘리는 추세