Virtual Memory

Demand Paging

요청이 있을 시, 그 page를 memory에 올리는 것.

• I/O 양의 감소
• Memory 사용량 감소
• 빠른 응답 시간
• 더 많은 사용자 수용

Page Fault

Performance of Demand Paging

Page Fault Rate 0<=p<=1.0
p = 0, no page faults
p = 1, every reference is a fault

Free Frame이 없는 경우

Page replacement

어떤 frame을 뺏을지 결정해야하는데, 곧바로 사용되지 않을 page를 쫓아내는 것이 좋음. 동일한 페이지가 여러 번 메모리에서 쫓겨났다가 다시 들어올 수 있음.

Replacement Algorithm

page-fault rate을 최소화하는 것이 목표. 가급적 0에 가깝도록.
알고리즘은 주어진 page reference string에 대해 page fault를 얼마나 내는지를 조사하여 평가.

다양한 캐슁 환경

Clock Algorithm

Page Frame의 Allocation

Allocation Problem : 각 process에 얼마만큼의 page frame을 할당?

필요성

• 메모리 참조 명령어 수행시 명령어, 데이터 등 여러 페이지 동시 참조
  -> 명령어 수행을 위해 최소한 할당되어야 하는 frame의 수가 있음
• Loop을 구성하는 page들은 한꺼번에 allocate 되는 것이 유리
  -> 최소한의 allocation이 없으면 매 loop마다 page fault

Scheme

• Equal allocation: 모든 프로세스에 똑같은 갯수 할당
• Proportional allocation: 프로세스 크기에 비례하여 할당
• Priority allocation: 프로세스의 priority에 따라 다르게 할당

Global VS Local Replacement

• Global Replacement
• Local Replacement

Thrashing

• 프로세스의 원활한 수행에 필요한 최소한의 page frame 수를 할당 받지 못한 경우 발생
• Page fault rate이 매우 높아짐
• CPU utilization이 낮아짐
• OS는 MPD(Multiprogramming degree)를 높여야 한다고 판단
• 또 다른 프로세스가 시스템에 추가됨 (Higher MPD)
• 프로세스 당 할당된 frame의 수가 더욱 감소 => page fault는 더 자주 발생
• 프로세스는 page의 swap in/swap out으로 매우 바쁨
• 대부분의 시간에 CPU는 한가
• low throughput

이처럼 trashing은 막아야함. 이를 막기 위해서는 multiprogramming degree를 조절해야 함. 동시에 메모리에 올라가있는 process의 개수를 조절.
=> Working-set Model, PFF algorithm 사용

Working-Set Model

PPF Scheme

Page Size의 결정