컴퓨터 시스템 : CSAPP 9장 정리 - 9.3 캐싱 도구로서의 VM

9.3 가상 메모리를 캐시로 사용하는 방법 (VM as a Tool for Caching)

가상 메모리는 개념적으로 디스크에 저장된 N개의 연속적인 바이트 셀 배열로 구성되어 있다. 각각의 바이트는 고유한 가상 주소를 가지며, 이 주소는 배열의 인덱스 역할을 한다. 디스크에 있는 이 데이터는 메인 메모리에 캐시 된다. 이 구조는 메모리 계층의 다른 캐시들과 유사하게 작동한다.

가상 메모리 시스템은 디스크와 메모리 간의 전송 단위로 고정 크기 블록을 사용한다. 이를 가상 페이지(Virtual Page, VP)라고 부르며, 보통 P = 2^p 바이트 크기를 갖는다. 물리 메모리 역시 같은 크기의 물리 페이지(Physical Page, PP)로 나뉜다.

어떤 시점에서, 가상 페이지는 다음 세 가지 집합 중 하나에 속한다:

• Unallocated: 아직 할당되지 않은 페이지. 디스크 공간도 점유하지 않는다.
• Cached: 메모리에 캐시되어 있는 할당된 페이지.
• Uncached: 할당되었지만 현재 메모리에는 없는 페이지​.

---

9.3.1 DRAM 캐시 구성 (DRAM Cache Organization)

DRAM 캐시는 CPU와 주기억장치 사이에 있는 SRAM 캐시(L1, L2, L3)와 구분된다. 이 구성을 명확히 하기 위해, 책에서는 앞단의 SRAM 캐시와 VM 기반 DRAM 캐시를 구분해서 설명한다.

DRAM 캐시의 특징

1. 느린 접근 시간
   DRAM은 SRAM보다 적어도 10배 느리며, 디스크는 DRAM보다 100,000배 더 느리다. 따라서 DRAM 캐시에서의 miss는 매우 큰 비용이 든다.
2. 큰 페이지 크기
   miss 비용이 크기 때문에, 한 번 불러올 때 많은 데이터를 다루도록 페이지 크기를 키운다. 일반적으로 4KB에서 2MB 사이이다.
3. 완전 연관 매핑(Fully Associative)
   어떤 가상 페이지든지 어떤 물리 페이지에나 올 수 있도록 한다. 이는 miss 시 어떤 페이지든 교체 가능하게 만든다.
4. 정교한 교체 알고리즘
   잘못된 페이지를 교체하면 매우 비싼 비용이 발생하므로, 운영체제는 LRU보다 훨씬 더 정교한 알고리즘을 사용한다 (세부 내용은 책에서 다루지 않는다).
5. 쓰기 전략: Write-back 사용
   디스크 접근이 느리기 때문에, DRAM 캐시는 항상 write-back 전략을 사용한다. 즉, 페이지가 교체될 때에만 디스크에 쓰기를 수행한다​.

---

9.3.2 페이지 테이블 (Page Tables)

가상 메모리 시스템은 캐시처럼 동작한다. 따라서 시스템은 다음과 같은 정보를 알아야 한다:

1. 특정 가상 페이지가 DRAM에 캐시되어 있는지 여부.
2. 만약 캐시되어 있다면, 어떤 물리 페이지에 저장되어 있는지.
3. 캐시되어 있지 않다면, 디스크의 어디에 저장되어 있는지, 그리고
4. 어떤 물리 페이지를 교체할 것인지를 결정해야 한다.

이러한 기능은 다음의 세 가지 요소가 함께 작동함으로써 구현된다:

• 운영체제 소프트웨어
• MMU (Memory Management Unit)라는 하드웨어
• 페이지 테이블(page table)이라는 데이터 구조

페이지 테이블 구조

페이지 테이블은 **페이지 테이블 엔트리(Page Table Entry, PTE)**로 구성된 배열이다. 각 가상 페이지는 고정된 위치의 PTE를 가진다.

각 PTE는 두 개의 필드로 구성된다:

• Valid 비트: 이 가상 페이지가 현재 DRAM에 캐시되어 있는지를 나타낸다.
  • Valid = 1이면, 주소 필드는 해당 물리 페이지의 시작 주소를 포함한다.
  • Valid = 0이면, 주소 필드는 그 페이지가 아직 할당되지 않았음(null)을 의미하거나, 디스크 상의 위치를 가리킨다.

예시

예를 들어, 가상 페이지가 8개이고 물리 페이지가 4개인 시스템에서는 다음과 같이 구성될 수 있다:

• VP 1, VP 2, VP 4, VP 7 → DRAM에 캐시 됨 (valid = 1)
• VP 0, VP 5 → 아직 할당되지 않음 (null)
• VP 3, VP 6 → 할당은 되었지만 DRAM에는 없음 (valid = 0, 주소는 디스크 위치)

이러한 구조 덕분에 완전 연관 캐시와 같이 어떤 가상 페이지든 어떤 물리 페이지에든 매핑 가능하다. 운영체제는 필요에 따라 어떤 물리 페이지든 교체 대상으로 선택할 수 있다​.

---

9.3.3 Page Hits (페이지 히트)

페이지 히트는 CPU가 참조한 가상 페이지(VP)가 이미 DRAM에 캐시되어 있을 때 발생한다. 이 상황은 캐시 히트와 유사하며, 매우 빠르게 데이터를 가져올 수 있다는 점에서 중요하다.

페이지 히트 처리 과정

가상 페이지 VP2에 있는 워드를 읽는 상황을 예로 들자.

1. CPU는 가상 주소를 생성하여 MMU로 전달한다.
2. MMU는 해당 가상 주소의 VPN을 사용하여 PTE 2를 찾는다.
3. PTE 2의 valid 비트가 1이므로, 해당 가상 페이지가 DRAM에 존재함을 나타낸다.
4. PTE에 있는 물리 주소(PP1의 시작 주소)를 사용하여, 물리 주소를 계산한다.
5. 이 물리 주소를 통해 DRAM에서 데이터를 읽어온다.

이러한 처리 과정은 하드웨어 수준에서 자동으로 수행되며, 운영체제의 개입 없이 빠르게 완료된다​.

---

9.3.4 Page Faults (페이지 폴트)

가상 메모리에서 DRAM 캐시 미스는 페이지 폴트(page fault)라고 부른다. 이는 CPU가 참조한 가상 페이지가 DRAM에 존재하지 않을 때 발생한다.

페이지 폴트 처리 과정

예를 들어 CPU가 VP3에 있는 워드를 참조했는데, DRAM에 해당 페이지가 없다면 다음의 과정이 일어난다:

1. MMU는 PTE 3을 읽고, valid 비트가 0임을 확인한다.
2. MMU는 페이지 폴트 예외를 발생시킨다.
3. CPU는 커널에 있는 페이지 폴트 핸들러를 호출한다.
4. 커널은 희생 페이지(victim page)를 선택한다. 여기선 예를 들어 VP4가 PP3에 저장되어 있고, 그 페이지가 선택된다고 하자.
5. 만약 VP4가 수정되었다면, **디스크에 다시 저장(write-back)**한다.
6. 커널은 페이지 테이블을 수정하여 VP4가 더 이상 DRAM에 없음을 반영한다.
7. 디스크에서 VP3를 PP3로 복사하고, PTE 3을 갱신한다.
8. 마지막으로 예외가 발생했던 명령어를 재실행하며, 이번엔 페이지가 메모리에 있기 때문에 정상적으로 실행된다​.

---

9.3.5 Allocating Pages (페이지 할당)

이 절에서는 가상 메모리 페이지가 새롭게 할당되는 경우를 다룬다. 대표적인 예는 C 프로그램에서 malloc을 호출했을 때 발생한다.

페이지 할당 절차

1. 사용자가 malloc 호출을 통해 메모리 요청을 한다.
2. 커널은 디스크 상에 새로운 공간을 할당하고, 새로운 가상 페이지(VP)를 생성한다.
3. 페이지 테이블에서 해당 가상 페이지에 해당하는 PTE를 찾아, 그 위치에 디스크 상의 새로 할당된 페이지 위치를 기록한다.
4. 이 시점에서 해당 페이지는 아직 DRAM에 로드되지 않았으며, valid 비트는 여전히 0으로 유지된다.
5. 이후 해당 페이지에 접근이 시도되면, 이는 페이지 폴트를 발생시키고, 실제로 디스크에서 DRAM으로 데이터를 로드하는 작업이 이어진다​.

예시 (Figure 9.8 기준)

• VP 5가 새롭게 할당된 상황을 가정한다.
• 커널은 디스크에 VP 5를 위한 공간을 생성하고, PTE 5를 해당 디스크 위치로 설정한다.
• 아직 페이지는 메모리로 로드되지 않았으므로, valid 비트는 0이다.

그림 9.8 : 새로운 가상페이지의 할당

---

9.3.6 Locality to the Rescue Again (국소성이 또다시 구원자가 되다)

가상 메모리에 대해 처음 배우는 많은 사람들이 가장 먼저 떠올리는 생각은 "비효율적일 것 같다"는 것이다. 디스크 접근에 의한 큰 miss penalty 때문에 프로그램 성능이 망가질 거라 생각한다. 하지만 실제로는 대부분의 경우 가상 메모리는 잘 작동한다. 그 이유는 바로 우리가 잘 아는 국소성(locality) 덕분이다.

작업 집합 (Working Set)

• 프로그램 전체 실행 동안 참조되는 페이지 수는 물리 메모리보다 많을 수 있다.
• 하지만 국소성의 원리에 따르면, 대부분의 시점에서 프로그램은 비교적 작은 집합의 페이지들만을 집중적으로 참조한다. 이 집합을 작업 집합(working set) 또는 상주 집합(resident set)이라고 부른다.
• 프로그램이 실행되면서 처음에는 이 작업 집합을 메모리로 가져오는 데 시간이 걸릴 수 있다. 하지만 일단 작업 집합이 메모리에 올라오면, 이후의 접근은 대부분 히트로 처리되어 디스크 접근 없이 진행된다.

스레싱(Thrashing)

• 모든 프로그램이 좋은 시간적 국소성(temporal locality)을 가지는 것은 아니다.
• 만약 작업 집합의 크기가 물리 메모리보다 크다면, 프로그램은 지속적으로 페이지를 스왑 인/아웃하게 되며, 이 현상을 스레싱(thrashing)이라 부른다.
• 스레싱이 발생하면 성능이 급격히 저하된다.
• 프로그램이 지나치게 느려진다면, 현명한 프로그래머는 스레싱 여부를 의심해봐야 한다​.