컴퓨터 시스템 : CSAPP 9장 정리 - 9.6 주소의 번역

9.6 주소 변환 (Address Translation)

주소 변환은 가상 메모리 시스템에서 가상 주소 공간(VAS)의 각 주소를 물리 주소 공간(PAS)의 주소로 변환하는 과정을 뜻한다. 이 절의 목표는 하드웨어(MMU)의 동작 방식을 이해하고, 직접 주소 변환 과정을 계산해 볼 수 있을 정도로 개념을 익히는 것이다.

주소 변환의 수학적 정의

주소 변환은 다음과 같은 함수로 정의된다:

MAP: VAS → PAS ∪ ∅

• MAP(A) = A′ : 가상 주소 A에 해당하는 데이터가 메모리에 있을 경우, 물리 주소 A′에 위치함.
• MAP(A) = ∅ : 해당 데이터가 현재 물리 메모리에 존재하지 않음 (즉, 페이지 폴트 발생 가능).

변환 구성 요소

• 가상 주소(VA)는 두 부분으로 나뉜다:
  • VPN: 가상 페이지 번호 (상위 비트)
  • VPO: 가상 페이지 오프셋 (하위 비트)
• MMU는 VPN을 이용해 페이지 테이블에서 PTE를 찾고, PPN과 VPO를 조합하여 물리 주소를 생성한다.
• VPO와 PPO는 동일한 비트 수를 갖는다. 이는 가상 페이지와 물리 페이지의 크기가 같기 때문이다​.

---

9.6.1 캐시와 가상 메모리 통합 (Integrating Caches and VM)

가상 메모리와 SRAM 캐시를 함께 사용하는 시스템에서는 캐시에 접근할 때 가상 주소를 쓸지, 물리 주소를 쓸지 결정해야 한다.

대부분의 시스템은 물리 주소 캐시(Physically Addressed Cache)를 사용한다.

이유는 다음과 같다:

1. 프로세스 간 공유 용이
   여러 프로세스가 동시에 같은 물리 캐시에 접근할 수 있게 하며, 같은 물리 페이지를 공유할 수 있다.
2. 보호 문제 해결 간편
   주소 변환 과정에서 접근 권한이 이미 검사되므로, 캐시에서 별도로 접근 권한을 확인할 필요가 없다.

캐시 접근 순서

• 가상 주소가 생성되면, MMU가 주소 변환을 수행한 뒤, 변환된 물리 주소로 캐시에 접근한다.
• 페이지 테이블 엔트리(PTE) 또한 일반 데이터처럼 캐시에 저장될 수 있다​.

---

9.6.2 TLB를 이용한 주소 변환 속도 향상

가상 주소가 생성될 때마다 MMU는 해당 주소를 물리 주소로 변환하기 위해 PTE(Page Table Entry)를 참조해야 한다. 최악의 경우 이 작업은 메모리 접근을 추가로 요구하게 되어 수십~수백 사이클의 비용이 든다. L1 캐시에 PTE가 있다면 그 비용은 몇 사이클 수준으로 줄어든다.

하지만 많은 시스템에서는 이마저도 피하고자, TLB(Translation Lookaside Buffer)라는 MMU 내부의 PTE 전용 캐시를 사용한다​.

TLB의 구조와 동작

• TLB는 소형, 가상 주소 기반 캐시로, 각 라인은 하나의 PTE를 담고 있다.
• 일반적으로 높은 연관도(associativity)를 갖는다.
• TLB 접근 시, VPN의 하위 비트는 TLB 인덱스(TLBI)로 사용되고, 나머지는 TLB 태그(TLBT)로 사용된다.
• 예: TLB에 T = 2^t개의 셋이 있다면, TLBI는 VPN의 하위 t비트, TLBT는 상위 비트다.

TLB 히트 및 미스 처리 과정

• TLB 히트 (일반적인 경우):
  1. CPU가 가상 주소를 생성함.
  2. MMU가 TLB에서 PTE를 조회하여 성공적으로 찾음.
  3. MMU가 PTE를 이용해 물리 주소 생성 후 캐시에 전달함.
  4. 데이터가 반환됨.
• TLB 미스:
  1. MMU는 TLB에 원하는 PTE가 없음을 인식.
  2. MMU는 메인 메모리나 캐시에서 페이지 테이블을 통해 해당 PTE를 가져옴.
  3. 이 PTE는 TLB에 저장되고, 기존 엔트리를 교체할 수도 있음.

이 구조는 주소 변환 속도를 비약적으로 향상시키며, 특히 연속적인 메모리 접근이 잦은 프로그램에 큰 효과를 준다​.

---

9.6.3 다단계 페이지 테이블 (Multi-Level Page Tables)

지금까지는 단일 페이지 테이블(single-level page table)만 사용하는 것으로 설명했다. 하지만 만약 32비트 가상 주소 공간을 갖고, 페이지 크기가 4KB, 그리고 각 페이지 테이블 엔트리(PTE)가 4바이트일 경우, 전체 가상 주소 공간을 커버하는 데 4MB의 페이지 테이블이 필요하다. 이는 작은 프로그램이 가상 주소 공간의 일부만을 사용하는 경우에도 불필요하게 큰 공간을 차지하게 된다. 64비트 주소 공간에서는 이 문제가 훨씬 더 심각해진다.

해결책: 다단계 페이지 테이블

• 일반적인 해결 방식은 페이지 테이블 계층 구조(hierarchy)를 사용하는 것이다.
• 예를 들어, 32비트 주소 공간에서 페이지 크기 4KB, PTE 크기 4바이트인 경우:
  • 레벨 1 페이지 테이블(L1): 각 엔트리는 4MB 범위(1024개의 연속 페이지)를 커버.
  • 총 1024개의 엔트리로 전체 4GB 가상 공간을 커버할 수 있음.
  • 각 L1 PTE는 해당 chunk에 할당된 페이지가 없으면 null이고, 있으면 **레벨 2 페이지 테이블(L2)**을 가리킨다.

최적화 효과

• 대부분의 주소 공간은 사용되지 않기 때문에, 해당 L1 PTE가 null이면 L2 페이지 테이블 자체를 만들 필요 없음.
• L1 테이블만 항상 메모리에 두고, 나머지 L2 테이블은 필요할 때 만들고 필요 없으면 디스크로 스왑 가능.
• 레벨 1과 2 테이블의 크기는 각각 4KB로 페이지 크기와 일치하여 구현이 간단함.

일반화

• 가상 주소는 VPN1, VPN2, ..., VPNk, VPO로 나뉘며,
  • 각 VPNi는 해당 레벨의 페이지 테이블에서 인덱스 역할.
  • 최종 레벨의 PTE는 실제 물리 페이지 번호(PPN) 또는 디스크 블록 주소를 포함.
  • 물리 페이지 오프셋(PPO)은 가상 페이지 오프셋(VPO)와 동일.

이 구조는 TLB와 함께 작동하여 다단계 접근의 성능 비용을 줄인다. 실제로는 단일 페이지 테이블보다 느리지 않다​.

---

9.6.4 모든 요소를 통합한 주소 변환 예시 (End-to-End Address Translation)

이 절에서는 지금까지 배운 내용을 종합하여, 가상의 작은 시스템을 예로 들어 주소 변환의 전체 과정을 단계별로 설명한다.

시스템 구성 가정

• 가상 주소: 14비트 (n = 14)
• 물리 주소: 12비트 (m = 12)
• 페이지 크기: 64바이트 (P = 2⁶)
• TLB: 총 16 엔트리, 4-way 세트 연관
• L1 데이터 캐시: 4바이트 라인, 16 세트, 직접 매핑(direct-mapped)
• 메모리는 바이트 주소 지정(byte-addressable) 방식
• 모든 접근은 1바이트 단위

주소 형식 분해

• 가상 주소는 상위 8비트는 VPN, 하위 6비트는 VPO로 나뉜다.
• 물리 주소는 상위 6비트는 PPN, 하위 6비트는 PPO로 나뉜다.
• 페이지 크기가 64바이트이므로, VPO와 PPO는 6비트로 동일하다.

주소 변환 예시 흐름

1. CPU가 가상 주소를 생성한다. 예: 0x03d4
2. MMU가 VPN(0x0F)을 추출하고, TLB에서 해당 PTE를 찾는다.
3. TLB가 세트 0x3에서 태그 0x3을 찾고, PPN(0x0D)를 반환한다.
4. MMU는 PPN과 VPO(0x14)를 결합해 물리 주소 0x354를 생성한다.
5. 이 물리 주소는 캐시에 전달된다:
   • Set Index = 0x5
   • Tag = 0x0D
   • Offset = 0x0
6. 캐시는 태그를 비교하고, 히트가 발생하여 데이터 0x36을 반환한다.
7. 데이터는 MMU를 거쳐 CPU로 전달된다.

이 과정을 통해 TLB 히트, 페이지 유효, 캐시 히트가 일어났을 때의 전체 주소 변환과 데이터 접근 과정을 정확히 추적할 수 있다​.