10. swapping

Swapping & Page Replacement

Reading

• 이 단원은 크게 두 부분으로 나뉜다.
  • Swapping: Mechanisms
  • Swapping: Policies
• 즉 앞부분에서는 메모리가 부족할 때 페이지를 어떻게 내보내고 다시 가져오는지를 배우고, 뒷부분에서는 어떤 페이지를 내보낼지를 결정하는 replacement policy를 배운다.

Swapping

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

Memory Hierarchy

• 메모리 계층은 보통 다음처럼 생각한다.
  • Registers
  • Cache
  • Main memory
  • Disk storage
• 아래로 갈수록
  • 용량은 커지고
  • 속도는 느려지고
  • 비용 특성은 달라진다.
• 그리고 각 층은 바로 위 층의 backing store 역할을 한다.

How to Swap

• 예전에는 memory overlay처럼 프로그래머가 직접 코드와 데이터를 들락날락시키는 방식도 있었다.
• 하지만 현대 OS는 보통 OS가 이를 맡는다.
• swapping 방식은 크게 두 가지다.
  • process-level swapping
    • 프로세스 전체를 backing store로 내보냈다가 나중에 다시 가져온다.
  • page-level swapping
    • 개별 page를 내보내고 다시 가져온다.
• 현대 virtual memory에서는 보통 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를 들고 나르는 데 따로 예약한 공간
• swap space는 dedicated partition일 수도 있고, file system 안의 file일 수도 있다.
• swap space 크기는 동시에 사용할 수 있는 memory page의 총량과도 관련된다.

When to Swap

• 가장 단순한 방법은 memory가 완전히 찰 때까지 기다렸다가 그때 replacement를 시작하는 것이다.
• 하지만 슬라이드는 이 lazy approach가 비현실적이라고 말한다.
• 실제로는 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 쪽으로 돌릴 수 있다.
• 즉 eviction 대상 선정은 단순히 “오래된 page"만이 아니라 page의 성격도 함께 본다.

Page Replacement policy

• replacement policy의 목표는 page fault rate를 최소화하는 것이다.
• 이유는 disk access penalty가 memory access보다 너무 크기 때문이다.
• 슬라이드는 AMAT를 다음처럼 설명한다.

• 여기서 miss penalty인 disk access cost가 매우 크기 때문에, miss rate가 조금만 올라가도 전체 성능이 크게 나빠진다.

OPT (or MIN)

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

FIFO (1)

• FIFO는 memory에 가장 먼저 들어온 page를 먼저 내보내는 방식이다.
• 장점은 단순하다.
  • 구현이 쉽다.
  • 모든 page가 비슷하게 residency를 받는다는 의미에서 공평해 보인다.
• 하지만 실제로 오래 있었다고 해서 덜 중요하다는 보장은 없다.
• 어떤 page는 오래됐어도 계속 필요한 page일 수 있다.
• 그래서 FIFO는 Belady’s anomaly를 겪을 수 있다.
  • frame 수를 늘렸는데도 page fault가 더 많아질 수 있다.

FIFO (2)

• 예시 reference string을 통해 FIFO의 실제 fault 수를 보여준다.
• 이 슬라이드의 핵심 메시지는 두 가지다.
  • FIFO는 직관적이지만 성능이 그리 좋지 않을 수 있다.
  • frame 수가 늘어난다고 반드시 fault가 줄어드는 것이 아니다.
• 즉 FIFO는 간단하지만, locality를 잘 반영하지 못한다.

LRU (1)

• **LRU(Least Recently Used)**는 가장 오랫동안 최근에 사용되지 않은 page를 내보낸다.
• OPT가 미래를 본다면, LRU는 과거의 사용 기록으로 미래를 예측하려는 정책이다.
• locality가 잘 있는 workload에서는 OPT를 꽤 잘 근사한다.
• 또 LRU는 stack algorithm이라 Belady’s anomaly를 겪지 않는다.
• 하지만 구현이 어렵고, access history를 추적해야 하며, frequency까지 직접 고려하지는 않는다.

LRU (2)

• stack algorithm은 memory size를 늘려도 page fault 수가 늘어나지 않는 정책을 말한다.
• LRU는 여기에 속한다.
• 즉 frame 수가 m 일 때 memory 안에 있는 page 집합은, frame 수가 m+1 일 때의 집합에 포함된다.
• 그래서 FIFO처럼 Belady’s anomaly가 생기지 않는다.

RANDOM

• RANDOM은 이름 그대로 임의의 page를 골라 교체한다.
• 장점은 아주 단순하다는 것이다.
  • bookkeeping이 거의 필요 없다.
• 단점은 말 그대로 운에 좌우된다는 점이다.
• 다만 어떤 workload에서는 FIFO나 LRU보다 더 나은 결과를 보이기도 한다.
• 즉 단순하다고 해서 항상 최악인 것은 아니다.

Comparisons

• 이 슬라이드는 replacement policy의 성능이 workload에 따라 달라진다는 점을 보여준다.
• 예를 들어
  • 완전히 random한 접근
  • 일부 소수 page에 접근이 몰리는 workload
  • 일정한 길이의 loop를 도는 workload에서 policy의 결과가 다르게 나타난다.
• 즉 어떤 policy가 항상 절대적으로 최고라고 말하기는 어렵다.

Implementing LRU

• 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 비용이 크다.
• 즉 LRU의 핵심 문제는 정확히 구현하려면 비용이 비싸다는 점이다.

Clock

• Clock은 LRU를 근사하는 대표적인 알고리즘이다.
• 각 PTE의 R(reference) bit를 이용한다.
• 모든 page frame을 원형으로 두고, clock hand가 victim 후보를 가리킨다.
• page fault가 났을 때
  • R == 1이면 R bit를 0으로 끄고 다음 page로 넘어간다.
  • R == 0이면 그 page를 evict한다.
• 즉 최근에 한 번 더 기회를 준다는 의미에서 second chance 알고리즘이라고도 볼 수 있다.

Clock Extensions

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

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를 더 산다.

Summary

• 이 단원은 virtual memory의 mechanism, policy, optimization을 구분해서 생각하게 만든다.
• mechanism 쪽에는
  • physical/virtual addressing
  • paging
  • page tables
  • TLB 같은 것이 있다.
• policy 쪽에는
  • page replacement policy
  • page allocation policy가 있다.
• optimization 쪽에는
  • demand paging
  • copy-on-write
  • multi-level page tables
  • TLB
  • replacement policy tuning 같은 것이 있다.
• 결국 10단원의 핵심은 memory가 부족할 때 무엇을 언제 어디로 내보낼지, 그리고 그 판단을 어떤 policy로 할지다.