[컴퓨터구조#13] 가상 메모리 (Virtual Memory)

이번 글에서는 가상 메모리에 대해 정리해 보겠다.

목차

1. 가상 메모리 기초
2. 캐시와 가상 주소
3. 페이지 테이블
4. 가상 머신

---

1. 가상 메모리 기초

메모리의 추상화 레이어는 다음과 같다.

• 프로그램 관점: 가상 주소 공간 (0 ~ 2^n)
• 하드웨어 시스템 관점: 물리 주소 공간 (0 ~ MaxPhysMem)
• OS는 프로그램의 가상 메모리를 물리 메모리로 맵핑한다.

맵핑의 단위를 page, 가상 페이지와 물리 프레임 간의 맵핑을 page table, 맵핑이 존재하지 않아 OS의 개입이 필요한 경우를 page fault라 한다.

가상 메모리의 필요성

• 각 프로세스에 고립된 메모리 공간 제공
  • 서로 다른 프로세스에 isolation을 제공하여 보호되도록 한다.
  • 각 프로그램 인스턴스에 consistent한 메모리 모델 제공
  • fine-grained protection (page-granularity)
• 효율적인 메모리 관리
  • 실제로는 가상 메모리 공간을 위한 연속적인 물리 메모리가 존재하지 않음
  • lazy allocatoin (demand paging): 꼭 필요할 때만 물리 메모리를 할당
  • Swapping: 물리 메모리 내 전체 가상 메모리를 유지할 필요 없음
  • OS는 페이지 레벨의 fine-grained permission을 가질 수 있음 (rd/wt/ex)

한 프로그램의 주소 공간은 페이지(고정 크기) 혹은 세그먼트(가변 크기)로 나눠진다. 각 페이지의 시작 주소(메인메모리 혹은 이차 저장 장치)는 프로그램의 페이지 테이블 안에 포함되어 있다.  예를 들어 두 프로그램이 물리 메모리를 공유하는 경우 다음 왼쪽 그림과 같이 맵핑된다. 또한, 페이지 테이블을 통해서 가상 주소를 물리 주소로 오른쪽 그림과 같이 변환한다.

페이지 폴트

페이지 폴트는 exception의 한 종류로, 메모리가 가상 메모리 페이지에 접근하려고 하지만 대응하는 물리 메모리 프레임이 존재하지 않는 경우 발생한다. cold miss인 경우, 해당 메모리가 접근된 적이 없다는 것을 뜻하며, swapped page인 경우 해당 페이지를 디스크에서 fetch해와야 한다.

페이지 폴트 비율을 최소화하려면, fully associative placement를 활용하거나 효과적인 replacement 알고리즘을 사용해야 한다. 보통 LRU replacement가 많이 사용된다. 페이지가 접근되면 해당 페이지의 페이지 테이블 엔트리 안의 reference bit (use bit)을 1로 설정하고, 이는 OS에 의해 주기적으로 0으로 초기화된다. reference bit가 0인 페이지는 최근에 사용된 적이 없는 페이지임을 나타낸다.

페이지 테이블

페이지 테이블은 placement 정보를 저장한다. 가상 페이지 number에 의해 인덱싱되는 페이지 테이블 엔트리의 array이다. CPU 안의 페이지 테이블 레지스터는 물리 메모리 안의 페이지 테이블을 가리킨다. 페이지가 메모리 안에 존재한다면 PTE는 물리 페이지 number를 저장하며, reference, dirty 등 다른 status bit 정보도 함께 저장한다. 만약 페이지가 메모리 안에 없다면 PTE는 디스크의 swap space 위치를 참조할 수 있다.

 

2. 캐시와 가상 주소

위에서 살펴본 바와 같이, 가상 주소를 물리 주소로 변환하려면 추가적인 메모리 접근이 필요하다. 이는 메모리(캐시) 접근을 매우 expensive하게 만든다. 

이를 해결하기 위해, 하드웨어에서는 Translation Lookaside Buffer (TLB)를 사용한다. TLB는 페이지 테이블 lookup을 회피하기 위해 최근에 사용된 주소 맵핑을 트래킹하는 작은 캐시이다.

TLB

주소 변환은 PTE 접근 이후 실제 메모리 접근으로 이어져 추가적인 메모리 참조를 필요로 한다. 따라서 CPU 안에 PTE의 캐시 격인 TLB를 두어 빠른 접근을 가능하게 한다. 

TLB miss

만약 TLB에서 미스가 발생한다면, 이는 상황에 따라 (페이지 테이블에 존재하지만 TLB에는 없는) 단순한 미스일 수도 있고, 혹은 실제로 메인 메모리에 페이지가 존재하지 않는 페이지 폴트일 수도 있다. TLB 미스는 페이지 폴트보다 훨씬 더 자주 일어난다. TLB 미스를 다루는 방법은 다음과 같다.

• 하드웨어 (x86) : OS는 TLB 미스에 대해 신경 쓰지 않고, 하드웨어 컨트롤러가 페이지 테이블을 순회하며 TLB를 채운다. 더 빠르긴 하지만 TLB 관리에 유연하지 못하다.
• 소프트웨어 (Sun SPARC) : TLB 미스는 exception을 발생시킨다. OS exception handler가 페이지 테이블을 순회하고 명령어 시퀀스를 실행하며 TLB를 채운다. 더 느리지만 TLB가 소프트웨어(OS)에 의해 더 효율적으로 관리된다.

TLB parameter

두 머신에서의 TLB 파라미터 예시는 다음과 같다.

	Intel Nehalem	AMD Barcelona
주소 크기	48비트(가상), 44비트(물리)	48비트(가상), 48비트(물리)
페이지 크기	4KB, 2MB, 1GB	4KB, 2MB, 1GB
TLB 조직	코어당 L1 ITLB(128 entry), L1 DTLB(64 entry): 4-way set assoc, LRU unified L2 TLB(512 entry): 4-way, LRU TLB 미스는 하드웨어에서 처리	코어당 L1 1TLB(48 entry), L1 DTLB(48 entry): fully assoc, LRU 코어당 L2 ITLB(512 entry), L2 DTLB(512 entry): 4-way, LRU TLB 미스는 하드웨어에서 처리

TLB와 캐시

캐시가 태그 물리 주소를 사용한다면 캐시 lookup 전 translation이 필요.

혹은, 가상 주소 태그를 대신 사용할 수 있음. (더 복잡하긴 함)

 

 

 

 

 

 

• VA->PA 전환을 L1 캐시 접근 전에 수행는 경우
  • 프로세서 메모리 접근 -(VA)-> TLB -(PA)-> L1$
  • L1은 항상 물리 주소만 보게 된다. 즉, 이는 physically-index, physically-tagged 캐시
  • L1 접근 느림.
• 반면, VA->PA 전환을 L1 접근 이후에 수행하는 경우
  • 프로세서 메모리 접근 -(VA)-> L1$ -(PA)-> TLB 
  • L1은 항상 가상 주소만 보게 되어 virtually-index, virtually-tagged 캐시
  • L1 접근 빠름.
  • 단점(synonym problem)
    • 여러 가상 주소가 같은 물리주소에 맵핑되어 캐시 내 동일한 물리 주소에 여러 블록이 존재
    • 중복되는 블록에 대한 consistency 유지가 어려움
    • 하드웨어적 솔루션: 미스 발생 시 가능한 모든 위치를 확인하여 synonym 제거
    • 두 가상 주소가 synonym인지 아는 방법? 물리 주소를 알아야 함
  • 또한, context switch를 위해 캐시를 flush해야 함.
  • 멀티프로세서에서는 더 복잡해질 수 있음. 캐시 coherence snoop 문제 -> 캐시 coherence는 물리 주소 기반으로 이루어짐.

병렬적으로 TLB와 캐시 접근

페이지 오프셋은 물리주소와 가상주소에서 동일하므로, 공통되는 비트를 인덱스로 활용할 수 있다. 

예를 들어, 4KB page size, 32B cache block size인 시스템에서 페이지 오프셋은 12bit이다(4KB). 이 경우 공통 12비트 중 하위 5비트를 캐시 블록 오프셋으로, 앞 7비트를 인덱스로 활용할 수 있다.

즉 인덱스에 7비트를 활용하면 최대 128개의 set이 나올 수 있고, associativity별로 캐시 크기가 다음과 같이 달라진다.

• direct-mapped: 128*32B = 4KB
• 2-way: 128*2*32B = 8KB
• 4-way: 128*4*32B = 16KB
• 8-way: 128*8*32B = 32KB

페이지 크기에 의해 set 개수가 결정된다. 캐시 크기를 늘리기 위해서는 associativity를 늘려야 한다. (이는 캐시를 더 느리게 만든다.)

메모리 보호

프로세스는 물리 메모리에 직접 접근할 수 없고 페이지 테이블을 통한 변환을 통해서만 접근이 가능하다. 서로 다른 task는 가상 주소 공간의 일부분을 공유할 수 있다. 하지만 잘못된 접근에 대한 보호가 필요하며, 이는 OS의 도움을 필요로 한다. OS 보호를 위한 하드웨어 지원에는 privileged superviser mode(커널 모드), privileged instructions, 페이지 테이블 및 기타 state 정보는 superviser mode로만 접근 가능, 시스템 콜 exception 등이 있다.

 

3. 페이지 테이블

가상 주소 공간의 모든 가상 페이지들이 물리 메모리에 맵핑되는 것은 아니다. 따라서 페이지 테이블의 메모리 사용량을 줄이기 위해 다층 페이지 테이블이 사용될 수 있다. 이는 자연히 페이지 테이블 엔트리의 접근 시간을 증가시키게 된다. 또한, 추가적인 메모리 접근을 일으키게 된다. TLB 미스 발생 시 기존에는 페이지 테이블만 확인하면 됐다면, 다층 페이지 테이블 사용 시에는 TLB 미스가 발생하면 페이지 디렉토리와 페이지 테이블을 모두 확인해야 하기 때문이다.

예시로 x86-32 페이지 테이블 lookup을 생각해 보자.

• 32비트의 가상주소 중 첫 10 비트는 페이지 디렉토리를 인덱싱한다. 페이지 디렉토리 엔트리는 페이지 테이블을 가리킨다.
• 중간 10비트는 페이지 테이블을 인덱싱한다. 페이지 테이블 엔트리는 물리 메모리 페이지를 가리킨다.
• 마지막 10비트는 물리 페이지 내 오프셋이다.

특징

• 필요한 만큼의 페이지 테이블만 할당하므로 sparse한 주소 공간에서 잘 작동한다. 
• top 페이지 테이블만 물리 메모리에 고정된다.
• 각 페이지 테이블은 보통 1개의 페이지만 채워 디스크에서 움직이기 쉽게 한다.
• 각 가상 메모리 참조에 여러 번의 물리 메모리 참조가 필요하다.

64비트 x86의 경우, 64비트의 가상주소를 지원한다. 이 경우 3가지의 모드를 지원한다: (1) legacy 32-bit (32-bit VA, 32-bit PA), (2) legacy PAE (32-bit VA, 최대 52-bit PA), (3) long PAE (64-bit VA, 53-bit VA)

이 중 log mode는 48비트의 가상주소를 52비트의 물리주소에 맵핑하기 위해 4개의 레벨을 필요로 한다. 1~3번째 인덱스는 다음 레벨의 테이블을 가리키는 포인터를 포함하고, 4번째 인덱스는 PPN 정보를 가리킨다. 마지막 4KB는 페이지 오프셋이다.

1st index [47:39]

2nd index [38:30]

3rd index [29:21]

4th index [20:12]

offset [11:0]

인텔의 i7 코어의 메모리 시스템 및 end-to-end 주소 변환 과정은 다음과 같다.

i7 코어의 레벨1~3의 페이지 테이블 엔트리는 다음과 같은 정보를 포함한다.

XD

PT physical base address

G

PS

A

CD

WT

U/S

R/W

P=1

• P: child 페이지 테이블이 물리 메모리에 존재하는지(1), 아니면 0.
• R/W: 모든 도달 가능한 페이지에 대해 read only인지 read-write인지
• U/S: 모든 도달 가능한 페이지에 대해 user mode인지 superviser mode인지
• WT: child 페이지 테이블 캐시 정책이 write-through인지 write-back인지
• A: reference bit (읽기/쓰기 시 MMU(메모리 관리 장치)에 의해 set되고 소프트웨어(OS)에 의해 clear됨)
• PS: 페이지 크기 4KB or 4MB (레벨 1 PTE에서만)
• PT physical base address
• XD: 해당 PTE에서 도달 가능한 모든 페이지로부터 명령어 fetch 가능/불가능하게 할지

레벨 4 페이지 테이블 엔트리는 다음과 같은 정보를 포함한다.

XD

Page physical base address

G

D

A

CD

WT

U/S

R/W

P=1

• 위와 거의 유사하지만 dirty bit만 추가됨
• D: dirty bit (쓰기 시 MMU에 의해 set, 소프트웨어가 clear)

 

Inverted 페이지 테이블

다층 페이지 테이블의 대안으로, vpn을 해싱하여 ppn을 얻는다.

O(1)의 lookup시간이 걸린다

스토리지는 주소 공간의 크기가 아닌 물리 페이지의 개수에 비례한다.

TLB 미스 비율에는 (페이지 크기의 문제이므로) 영향을 주지 않지만, TLB 미스 penalty는 줄여준다.

 

HW/SW 경계

물리<->가상 주소 변환 시 어떤 부분이 하드웨어에서 수행될까?

• 최근 변환을 캐싱하는 TLB: TLB 접근 시간은 캐시 hit time의 일부이다. 파이프라인에 TLB 접근을 위한 추가 스테이지를 할당할 수 있다.
• 페이지 테이블 저장, fault 탐지 및 업데이트
  • 페이지 폴트는 인터럽트를 발생시키고 이는 OS에 의해 처리된다.
  • 하드웨어는 페이지 테이블 내 dirty&reference 비트를 적절히 처리해야 한다.

 

TLB 미스와 성능

4KB page, 64개의 entry를 가진 TLB는 4KB*64=256KB의 메모리를 커버할 수 있다. TLB의 coverage는 캐시의 coverage보다 훨씬 작다. TLB의 entry가 증가할수록 coverage는 증가하고 TLB 미스는 감소한다. 하지만 동시에 TLB hit time도 증가한다.

x86-64에서는 각 TLB 미스마다 4번의 메모리 접근이 필요하다. 최악의 경우 최종 변환을 위해 1000사이클 이상이 소요될 수 있다. 하지만 페이지 테이블은 L2/L3 캐시에도 캐싱될 수 있다.

TLB 미스의 부정적 효과를 줄이기 위해서는 ..

• TLB 미스 rate을 줄이기: superpaging
• TLB 미스 penalty를 줄이기: 페이지 테이블 캐싱을 허용, 중간 노드를 특별한 TLB에 캐싱 (page walk cache)

 

Huge Page

• 장점: TLB 미스를 줄일 수 있다. 예를 들어, 2MB의 큰 페이지는 4KB 페이지에 비해 TLB entry의 범위를 512배 늘릴 수 있다. 
• 요구사항: 연속적인 물리 메모리 chunk를 필요로 한다. (가상주소의 오프셋 = 물리주소의 오프셋)
• 내부 파편화(huge page 내 사용되지 않는 부분 존재) 및 외부 파편화(물리 메모리에 연속적인 aligned chunk 필요)를 신경 써야 한다.
• 메모리 관리를 신경 써야 하며, 기본 페이지를 huge 페이지로 움직여야 하므로 OS 지원이 필요하다.
• 페이지 테이블 조직에도 변화가 필요하다. 트리 기반의 페이지 테이블(다층 페이지 테이블)이 필요하다.
• TLB 지원: 주소 변환 시 페이지 크기가 알려져 있지 않기 때문에 가능한 여러 페이지 크기들을 가진 TLB를 lookup해야 한다.

[ISCA'13] Efficient Virtual Memory for Big Memory Servers에서는 segment 기반 변환이 제안되었다. (base, limit, offset 세 변수를 사용해서 연속적인 변환을 나타냄)

 

4. 가상 머신

시스템 가상화: 클라우드 컴퓨팅이나 서버 통합에서 널리 사용되며, hyperviser가 자원 관리를 담당한다. 각 가상 머신에서 독립적인 os가 돌아간다.

• hypervisor: 가상머신을 관리하는 SW layer. 가상 자원(레지스터와 메모리)을 실제 하드웨어 자원으로 맵핑한다. 실제 머신 명령어를 사용해서 가상 머신 명령어가 지정한 액션을 수행한다. 즉, 독립적인 개별 VM illusion을 제공한다.
• 각 VM에서 guest OS가 돌아간다. guest OS에 아무런 변화가 없다면 full virtualization, 머신 통제를 위해 약간의 변화가 있다면 para-virtualization이라 한다.
• Guest OS에 의한 privileged 명령어 관리: 안전하지 않은 연산은 hypervisor에게 trap한다. 안전한 연산은 guest OS 내부에서 조용히 처리한다.
• 메모리 관리: guest OS는 머신 메모리를 직접 바꿀 수 없다.

각 가상머신은 guest (virtual) 물리 메모리 공간을 본다. guest OS는 각 프로세스에 대한 guest physical page를 관리하고, hypervisor는 VM들을 위한 머신 페이지를 관리한다. 즉 guest OS의 가상 주소에서 물리 주소로(각 guest OS에 의해 생성되는 guest 페이지 테이블에 의해), 그리고 hypervisor에서 물리 주소에서 머신 주소로(VM별로 하나씩 존재하는 extended(=nested) 페이지 테이블) 2번의 translation이 필요하다.

하드웨어 기반 page walk

x86은 코어당 하나의 page walker를 가진다(하나의 페이지 테이블 포인터 - CR3). page walker는 현재 프로세스의 페이지 테이블을 순회할 수 있다.

하지만, 가상화에서는 2-level translation을 필요로 한다.

• guest page table: GVA -> GPA (guest 가상주소 -> guest 물리주소)
• nested page table: GPA -> MA (guest 물리주소 -> 머신주소)

이러한 상황에서 가상화된 시스템을 위한 메모리 가상화는 어떻게 지원할까? 이때 주의해야 할 것은 TLB는 GVA에서 MA로의 변환을 캐싱한다는 점이다. (두 단계 한번에) 따라서 TLB 미스에 대해서 주소 변환 문제가 생기게 된다.

기존: 하드웨어의 페이지 테이블 포인터인 CR3는 guest 페이지 테이블 디렉토리를 가리킨다.

=> Shadow Paging: guest 와 nested 페이지 테이블을 압축한 shadow 페이지 테이블(GVA->MA)을 활용하는 것이다. Shadow 페이지 테이블은 guest 페이지 테이블이나 nested 페이지 테이블 둘 중 하나라도 업데이트될 때마다 항상 업데이트되어야 한다. Hypervisor는 페이지 테이블 업데이트를 trap하고, 변화를 하드웨어 페이지 테이블과 그 뒤로 validate 및 propagate할 책임을 진다. 또한, 이때 CR3는 Shadow 페이지 테이블을 가리킨다. 

하드웨어 기반 2D page walk

만약 하드웨어가 2개의 ensted page table을 walk할 수 있다면 어떻게 될까?

• gCR3: 프로세스에 대한 guest 페이지 테이블 포인터. 프로세스 context switch 시 guest OS에 의해 바뀜
• hCR3: VM에 대한 nested 페이지 테이블 포인터. hypervisor에 의해 바뀐다.

만약 가상화된 시스템에서 x86-64에서 이 2D page walk를 적용한다면, 최악의 경우 (4번의 translation fully 다 한다면) 24번의 메모리 접근이 필요하다.