08. Virtual Memory

Demand Paging

Demand Paging

• 실제로 필요할 때 page를 physical memory에 올리는 방법
  • I/O 감소, Memory 사용량 감소, 빠른 응답 시간, 더 많은 process 수용
• Valid / Invalid bit 사용
  • Invalid = 페이지가 물리적 메모리에 없는 경우, 처음에는 모든 page entry가 Invalid로 초기화

 

Page Fault

Page Fault

• Invalid page를 접근하면 MMU가 interrupt 발생시킴
• Kernel mode로 들어가서 page fault handler가 invoke 됨

Page Fault 처리 순서

1. if invalid reference: abort process
2. Get an empty page frame (없는 경우 replace = 기존에 존재하는 page를 backing store로 쫓아냄)
3. 해당 페이지를 disk(backing store)에서 memory로 읽어온다.
   3-1. disk I/O가 끝나기까지 이 프로세스는 CPU를 preempt 당함 (block)
   3-2. Disk read가 끝나면 page table entry에 기록, valid/invalid bit = 'valid'
   3-3. ready queue에 process를 다시 삽입 -> dispatch later
4. 추후 이 프로세스가 CPU를 잡고 다시 running
5. 아까 중단되었던 Instruction 재개

 

 

Performance of Demand Paging

Page Fault Rate 0 <= p <= 1.0

• if p == 0 : no page fault (ex. memory가 매우 커서 page가 모두 올라와 있을 때)
• if p == 1, every reference is a fault (처음 시작할때)

Effective Access Time

• (1-p) * memory access + p (OS & HW page fault overhead) + [swap page out if needed] + swap page in + OS & HW restart overhead

---

Page Replacement Algorithm

Free Frame이 없는 경우 -> Page Replacement

• 어떤 frame을 빼앗아올지 결정해야 함 -> Replacement Alogorithm 사용
• page-fault rate을 최소화하는 것이 목표

Optimal Algorithm

Belady's optimal algorithm, MIN, OPT

• 가장 먼 미래에 참조되는 Page 를 replace
• 미래의 참조를 어떻게 아는가? -> offline algorithm (online 컴퓨터에서 적용 못함)
• 다른 알고리즘의 성능에 대한 upper bound 제공

 

FIFO (First In First Out)

FIFO: 먼저 들어온 것을 먼저 내쫓음

• 메모리가 증가할 수록 page fault가 증가함

 

LRU (Least Recently Used) & LFU (Least Frequently Used)

LRU: 가장 오래 전에 참조된 것을 지움

 

LFU: 참조 횟수가 가장 적은 객체를 지움

• 최저 참조 횟수를 가진 page가 여러 개 있는 경우
  • 임의로 선정
  • 성능 향상을 위해 LRU와 결합해서 가장 오래 전에 참조된 page를 지우게 구현 가능
• LRU처럼 직전 참조 시점만 보는 것이 아니라 장기적인 시간 규모를 보기 때문에 page의 인기도를 좀 더 정확히 반영가능
• 참조 시점의 최근성 반영하지 못하고 LRU보다 구현이 복잡하다는 단점

LRU와 LFU 알고리즘의 구현

• LRU: Linked List로 구현: O(1) complexity
• LFU: tree구조로 구현 (heap): O(log n) complexity
  • Linked list로 구현하면 O(n) complexity

 

Clock Algorithm

Caching

• paging system 처럼 한정된 빠른 저장 공간을 가지고 계속적으로 요청되는 새로운 객체를 저장 공간에 읽어들였다가 후속 요청 시 직접 서비스하는 방식
• 저장 공간 = cache
• paging system, cache memory, buffer caching, Web caching ...

캐쉬 운영의 시간 제약

• Replacement Algorithm에서 삭제할 객체를 결정하는 일에 지나치게 많은 시간이 걸리는 경우 실제 시스템에서 사용할 수 없음
• Buffer caching이나 Web caching의 경우 O(1) ~ O(log n)정도까지 허용
• Paging system의 경우: 페이지 요청이 매우 비번하여 O(1)인 LRU 알고리즘도 부담 👉 Clock Alogorithm

Clock Algorithm (= Second chance algorithm, NUR(Not Used Recently), NRU(Not Recently Used))

• LRU의 근사 알고리즘
• 동작 방식
  • Reference bit을 사용해서 교체 대상 페이지 선정 (circular list)
  • reference bit가 0인 것을 찾을 때까지 포인터를 하나씩 앞으로 이동
  • 포인터가 이동하는 중에 reference bit 1은 모두 0으로 바꿈 (first chance)
  • Reference bit가 0인 것을 찾으면 그 페이지를 교체
  • 한 바퀴 되돌아와서도 (=second chance) 0이면 그때에는 replace 당함
  • 자주 사용되는 페이지라면 second chance가 올 때 reference bit = 1일 것이다.
• 개선 방법
  • reference bit와 modified bit(dirty bit)을 함께 사용
  • refernce bit = 1 : 최근에 참조된 페이지
  • modified bit = 1 : 최근에 변경된 페이지 (I/O를 동반하는 페이지) -> 추후 메모리에서 쫓아내기 전에 디스크에 먼저 써주어야 함

 

Page Frame의 Allocatioin

Allocation problem: 각 process에 얼마만큼의 page frame을 할당할 것인가?

• 명령어 수행을 위해 최소한 할당되어야 하는 frame 수가 있음
• Loop를 구성하는 page 들은 한 번에 allocate되는 것이 유리함: 아니면 매 loop마다 page fault 발생할 것이므로

Allocation Scheme

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

 

Global vs Local Replacement

Global Replacement

• Replace 시 다른 process에 할당된 frame을 빼앗아올 수 있음 (메모리 전체를 대상으로 함)
• Process 별 할당량을 조절하는 또 다른 방법
• Working set, PFF 알고리즘 사용

Local Replacement

• 자신에게 할당된 frame 내에서만 replacement

---

Thrashing

Thrashing

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

 

Working-Set Algorithm

Locality of reference (참조의 지역성)

• 프로세스는 특정 시간 동안 일정 장소만을 집중적으로 참조한다.
• Locality set = 집중적으로 참조되는 해당 page들의 집합

Working-Set Model

• Working Set: Locality에 기반하여 프로세스가 일정 시간동안 원활하게 수행되기 위해 한꺼번해 메모리에 올라와 있어야 하는 page들의 집합
• Working Set Model에서는 프로세스의 working set 전체가 메모리에 올라와 있어야 수행되고 그렇지 않을 경우 모든 frame을 반납한 후 swap out (suspend)
• Thrashing을 방지하고 MPD(Multiprogramming degree)를 결정

Working-Set Algorithm

• 프로세스들의 working set size 합이 page frame 수보다 큰 경우
  • 일부 프로세스를 swap out시켜 남은 process의 working set을 우선적으로 충족 (MPD를 줄임)
• Working set을 다 할당하고도 page frame이 남는 경우
  • Swap out 되었던 프로세스에게 working set 할당 (MPD를 키움)
• Working set을 제대로 탐지하기 위해서는 window size를 잘 결정해야 함
  • window size 너무 작으면 locality set을 모두 수용하지 못할 우려, 너무 크면 여러 규모의 Locality set 수용

 

PFF (Page-Fault Frequency) Schema

PFF

• page-fault rate의 상한값과 하한값을 두고 상한값을 넘으면 frame을 더 할당하고 하한값 이하이면 할당 frame 수를 줄인다.
• 빈 frame이 없으면 일부 프로세스를 swap out

 

Page Size의 결정

Page size를 감소시키면

• 페이지 수, 페이지 테이블 크기 증가
• Internal fragmentation 감소
• Disk transfer 효율성 감소
• 필요한 정보만 메모리에 올라와 메모리 이용이 효율적 <-> Locality의 활용 측면에서는 좋지 않음

👉 요즘 트렌드: Larger page size