10. Virtual Memory Swapping

Swapping

• swapping의 목적은 physical memory가 부족해도 프로세스를 계속 지원하는 것이다.
• 핵심 관점은 physical memory를 disk에 대한 cache처럼 본다는 것이다.
• 프로세스는 어느 순간에도 address space 전체를 다 쓰지 않고 일부만 집중적으로 쓰는 경우가 많으므로, 지금 당장 필요한 일부 페이지만 memory에 두고 나머지는 disk에 둘 수 있다.

Memory Hierarchy

How to Swap

• Memory overlays (old systems)
• process-level swapping
  • 프로세스 전체를 backing store로 내보냈다가 나중에 다시 가져온다.
• page-level swapping
  • 개별 page를 내보내고 다시 가져온다.

Memory Overlays

• Memory overlay는 옛날 시스템에서 쓰던 방식이다.
• programmer가 필요한 code나 data 조각을 직접 memory에 올리고 내린다.
• OS의 특별한 지원이 거의 필요 없지만, programmer 부담이 크다.
• 현대 OS의 page-level swapping과 대비되는 역사적 방식으로 이해하면 된다.

Page-level Swapping

• 하드웨어가 PTE를 봤는데 해당 page가 physical memory에 없을 수 있다.
• page fault
  • page가 disk로 swap-out된 상태라면, OS는 그 page를 다시 memory로 가져와야 한다.
  • 그런데 새 page를 들여오려면 frame이 필요하므로, OS는 기존 page 중 하나를 내보내야 한다.
  • 이 희생 페이지를 고르는 과정이 바로 page replacement다.

Where to Swap

• page를 내보낼 곳은 크게 두 종류로 볼 수 있다.
  • File system
    • 실행 파일이나 일반 파일이 있는 저장 공간
  • Swap space
    • page를 들고 나르는 데 따로 예약한 공간

When to Swap

• Lazy approach
  • memory가 완전히 찰 때까지 기다렸다가 그때 replacement를 시작하는 것
  • 비현실적
• 실제로는 OS가 free page를 어느 정도 유지하려고 함
• 임계값: LW(low watermark), HW(high watermark) 같은 기준을 둠. free page 수가 LW보다 내려가면 swap daemon이 page eviction을 시작하고, free page 수가 HW보다 올라가면 daemon은 비활성화됨.

Swapping in Linux

• Linux에서는 kswapd 같은 background thread가 free page 수를 보며 동작한다.
• free page가 너무 줄면 kswapd가 깨어나서 page를 내보내고, 충분히 여유가 생기면 다시 sleep 상태로 돌아간다.
• 다만 소비 속도가 너무 빠르면 background reclaim만으로는 부족해서, allocating process가 직접 reclaim 작업을 하기도 한다.

What to Swap

• page replacement policy는 모든 page를 똑같이 다루지 않는다.
• 어떤 종류의 page는 not swapped이고, 어떤 page는 swap되거나 drop될 수 있다.
• 예를 들어
  • kernel code, kernel data, page table, kernel stack 같은 것은 보통 안 내보냄
  • user heap/stack page는 swap 대상이 될 수 있음
  • file-backed page나 page cache page는 disk에 원본이 있으면 drop하거나 file system 쪽으로 돌릴 수 있음.

Page Replacement policy

• replacement policy의 목표: page fault rate 최소화
  • disk access penalty > memory access (10000배?정도)

• 
• miss penalty인 disk access cost가 매우 크기 때문에, miss rate가 조금만 올라가도 전체 성능이 크게 저하됨.

OPT (or MIN)

• OPT는 앞으로 가장 오랫동안 다시 쓰이지 않을 page를 내보내는 정책이다.
  • 이론적으로는 어떤 reference stream에 대해서도 가장 낮은 fault rate를 준다.
  • 하지만 미래를 알아야 하므로 실제 구현은 불가능함.
  • 따라서 OPT는 비교 기준으로 쓰는 이상적인 정책이다.

FIFO

• FIFO: First-In First-Out
  • Belady’s anomaly: frame 수를 늘렸는데도 page fault가 더 많아질 수 있음
  • locality 잘 반영x

LRU

• LRU: Least Recently Used
  • 가장 오랫동안 최근에 사용되지 않은 page를 내보냄
• locality가 잘 있는 workload에서는 OPT를 꽤 잘 근사함.
• stack algorithm이라 Belady’s anomaly를 겪지 않음.
  • memory size를 늘려도 page fault 수가 늘어나지 않는 정책(e.g. OPT, LRU, etc.)
• 하지만 구현이 어렵고, access history를 추적해야 하며, frequency까지 직접 고려하지는 않음.
• 즉 frame 수가 m 일 때 memory 안에 있는 page 집합은, frame 수가 m+1 일 때의 집합에 포함됨 > FIFO처럼 Belady’s anomaly가 생기지 않음.

RANDOM

• 랜덤 페이지를 골라서 evict
• no bookkeeping needed
• 단순하지만 workload에 따라 FIFO나 LRU보다 나을 수도 있다.
• 

Comparisons

Page Replacement Policy Comparison Workloads

• page replacement policy는 workload에 따라 성능이 달라진다.
• 강의안에서는 다음 workload를 비교한다.
  • 100% random access
  • 80% of references to 20% of pages
  • looping 50 pages in sequence
• locality가 강하면 LRU가 좋지만, 반복 패턴이나 random access에서는 다른 정책이 더 나을 수 있다.
• 특히 RANDOM은 bookkeeping이 없고, 특정 workload에서는 FIFO나 LRU보다 좋은 결과가 나올 수 있다.

Implementing LRU

• Software approach
  • OS가 page frame들을 reference time 순으로 정렬된 리스트로 관리한다.
  • page가 참조될 때마다 앞으로 옮기고, victim이 필요하면 뒤에서 고른다.
  • memory reference 때 느리지만 replacement 때는 빠르다.
• Hardware approach
  • 각 page frame에 timestamp를 둔다.
  • page가 참조될 때 현재 clock 값을 저장한다.
  • victim이 필요할 때 가장 오래된 값을 찾는다.
  • memory reference 때는 빠르지만 replacement 때 scan 비용이 크다.

Clock

• Clock은 LRU를 근사하는 대표적인 알고리즘이다.
• 각 PTE의 R(reference) bit를 이용한다.
• 모든 page frame을 원형으로 두고, clock hand가 victim 후보를 가리킨다.
• page fault가 났을 때
  • R == 1이면 R bit를 0으로 끄고 다음 page로 넘어간다.
  • R == 0이면 그 page를 evict한다.

Clock Extensions

• Clock은 여러 방식으로 확장할 수 있다.
• Clustering
  • replacement algorithm을 여러 번 돌리는 비용을 줄이기 위해 한 번에 여러 page를 처리한다.
• M(modify) bit 활용
  • dirty page는 replacement cost가 더 크므로, 가능하면 R과 M이 모두 0인 page를 선호한다.
• software counter 추가
  • page frame마다 counter를 두어 최근성 차이를 더 잘 표현한다.

Prefetching

• Prefetching은 OS가 “곧 필요할 것 같은 page"를 미리 가져오는 최적화다.
• 예를 들어 page 1에서 fault가 났다면, 순차 접근이 예상될 때 page 2도 같이 가져오는 식이다.
• 잘 맞으면 fault를 줄일 수 있다.
• 하지만 예측이 틀리면 불필요한 I/O와 memory 사용을 늘릴 수 있다.

Clustering, Grouping

• pending write들을 모아서 한 번에 큰 write로 disk에 내보내는 최적화다.
• 작은 write 여러 번보다 큰 write 한 번이 더 효율적일 수 있다.
• 따라서 eviction이나 write-back 과정에서는 page들을 모아서 처리하는 것이 성능에 도움이 된다.

Thrashing

• Thrashing: memory가 oversubscribed된 상태. 즉, 현재 돌아가는 프로세스들의 working set 전체를 physical memory가 담지 못하는 상태.
  • working set은 프로세스가 현재 활발히 쓰는 page들의 집합이다.
• 이 상황이 되면 OS는 대부분의 시간을 page를 disk와 memory 사이에서 왔다 갔다 시키는 데 쓰게 된다.
• 결국 CPU 일을 거의 못 하고 paging만 반복하게 된다.
• 단순한 해결책은 다음과 같다.
  • 프로세스를 줄인다.
  • memory를 더 산다.