[CSAPP] Virtual Memory

컴퓨터 구조 (Architecture)/CSAPP

[CSAPP] Virtual Memory

피그브라더 2020. 3. 27. 18:45

1. Introduction

1-1. 가상 메모리 (Virtual Memory)

몇몇 단순한 임베디드 마이크로컨트롤러와 같이 가상 메모리 기술을 사용하지 않는 시스템에서는 메모리 참조 방식이 아래 왼쪽 그림과 같다. 즉, CPU가 물리 주소를 메인 메모리에 바로 입력하여 메모리 참조를 진행하는 것이다. 반면 대부분의 현대 데스크탑, 서버, 노트북과 같이 가상 메모리 기술을 사용하는 시스템에서는 메모리 참조 방식이 아래 오른쪽 그림과 같다. 가상 메모리(Virtual Memory) 시스템에서는 각 프로그램이 가상의 주소를 사용하도록 하며, CPU가 메모리 참조를 시도할 때는 MMU(Memory Management Unit)라는 하드웨어 장치를 이용하여 해당 가상 주소(Virtual Address)를 실제 메인 메모리의 물리 주소(Physical Address)로 변환하여 메모리 참조를 진행한다.

[Figure] 가상 메모리 기술을 사용하지 않는 시스템(왼쪽), 가상 메모리 시스템(오른쪽)

1-2. 가상 메모리의 필요성

그렇다면 이와 같은 가상 메모리 기술은 왜 사용하는 것일까? 크게 세 가지 이유로 나눠서 생각해볼 수 있다. 각각에 대한 자세한 내용은 바로 이어지는 세 개의 큰 주제(Caching, Memory Management, Memory Protection)에서 설명하는 부분을 읽어보도록 하자.

먼저, 메인 메모리를 효율적으로 사용하기 위해서이다. 가상 메모리 시스템에서는 각 프로그램이 사용하는 가상 주소 공간(Virtual Address Space)을 우선 디스크에 저장해 두고, 그중에서 자주 사용되는 부분만 메인 메모리로 가져와서 사용한다. 즉 메인 메모리를 디스크의 캐시로 사용하는 것이다. 이렇게 하면 하나의 메인 메모리에 여러 프로그램의 데이터와 코드를 로드하는 것이 가능해진다.

다음으로, 메모리 관리를 단순화한다. 가상 메모리 시스템에서는 각 프로세스가 완전히 동일한 포맷의 가상 주소 공간을 가진다. 이것이 가능한 이유는 실제로 메모리 참조를 수행할 때는 가상 주소를 물리 주소로 변환하는 작업이 진행되기 때문이다. 따라서 각각의 프로세스에게 혼자서 메인 메모리를 사용한다는 듯한 착각을 제공한다. 이는 링커 및 로더의 구현과 메모리 할당 방식 등을 단순화한다.

마지막으로, 메모리 보호 메커니즘을 단순화한다. 가상 메모리 시스템에서는 한 프로세스가 다른 프로세스의 주소 공간에 접근하는 것을 쉽게 막을 수 있다. 또한, 가상 주소를 물리 주소로 변환할 때 참조하는 맵핑 테이블의 각 엔트리에는 해당 가상 주소에 대한 접근 권한이 명시된다. 따라서 유저 프로세스가 커널 영역에 접근하는 것처럼 허용되지 않은 주소 공간에 접근하는 것도 쉽게 막을 수 있다.

2. VM for Caching

2-1. 가상 메모리와 DRAM 캐시

가상 메모리는 디스크에 저장되는 N개의 연속적인 바이트들로 이뤄진 배열을 의미하며, 해당 바이트 배열의 일부는 메인 메모리(DRAM 캐시)에 캐시 된다. 캐시 메모리가 메인 메모리의 캐시로 사용된다면, 메인 메모리는 디스크의 캐시로 사용되는 셈이다. 그리고 캐시 메모리와 DRAM의 관계에서 블록(Block)이라는 단위를 사용하듯이, 메인 메모리와 디스크의 관계에서는 페이지(Page)라는 단위를 사용한다. 디스크에 위치하는 가상 주소 공간(Virtual Address Space)의 각 페이지는 가상 페이지(Virtual Page), 메인 메모리에 위치하는 물리 주소 공간(Physical Address Space)의 각 페이지는 물리 페이지(Physical Page)라고 부른다.

다음은 디스크의 가상 페이지들이 물리 페이지들에 맵핑된 예시를 보여준다. Unallocated는 프로그램에 의해 사용되지 않는 가상 주소 공간에 해당하는 가상 페이지이고, Uncached는 프로그램에 의해 사용되지만 아직 물리 페이지에 맵핑되지 않은 가상 페이지이며, Cached는 프로그램에 의해 사용되고 물리 페이지에 맵핑까지 된 가상 페이지이다.

한편, DRAM 캐시(= 디스크의 캐시)는 캐시 메모리(= 메인 메모리의 캐시)에 비해 Miss Penalty가 매우 크다는 특징이 있다. DRAM과 SRAM의 속도 차이는 10배 정도인 반면, 디스크와 DRAM의 속도 차이는 거의 10,000배에 이르기 때문이다. 이로 인해 캐시 메모리와 DRAM 캐시는 다음과 같이 크게 두 가지 측면에서 차이점을 가진다.

2-1-1. Miss Penalty 처리 방식

캐시 메모리의 경우 DRAM과 SRAM의 속도 차이가 그렇게 크지는 않기 때문에 하드웨어 수준에서만 처리해도 문제가 되지 않는다. 그러나 DRAM 캐시의 경우 디스크와 DRAM의 속도 차이가 상당히 크기 때문에 하드웨어 수준에서만 처리하기에는 낭비되는 시간이 너무 많다. 따라서 소프트웨어적인 처리를 가미한다. 대표적인 사례는 하드웨어가 DRAM 캐시의 Miss Penalty를 처리하는 동안 문맥 전환을 통해 잠시 다른 프로세스에게 제어를 넘겨주는 것이다. 이렇게 하면 DRAM 캐시의 Miss Penalty를 처리하는 긴 시간을 기다리기만 하면서 낭비하지 않아도 된다.

2-1-2. 캐시 구조 (Cache Organization)

캐시 메모리에 비해 DRAM 캐시는 Miss Penalty가 상당히 크기 때문에 Miss Rate를 최소화하기 위한 구조가 필요하다. 먼저, 페이지 사이즈가 블록 사이즈에 비해 상당히 크다. 페이지 사이즈는 일반적으로 4-8KB 정도이며, 때로는 4MB 정도까지 이르는 경우도 있다. 다음으로, Fully Associative 구조를 갖는다. 즉 각각의 가상 페이지는 어떠한 물리 페이지에도 맵핑될 수 있다. 단 이렇게 하면 DRAM 캐시에서 특정 가상 페이지의 캐싱 여부를 확인할 때 모든 물리 페이지를 확인해야 할 것이다. 이를 해결하기 위한 방법이 바로 맵핑 테이블이다. 맵핑 테이블은 입력된 가상 주소를 바탕으로 해당 가상 페이지가 DRAM 캐시에 존재하는지를 단번에 알아낼 수 있도록 한다. 다만 맵핑 테이블의 크기는 가상 페이지의 개수에 비례하기 때문에 맵핑 테이블의 크기를 최소화하는 전략도 필요하다. 이에 대해선 뒤에서 알아보도록 하자. 또한, 매우 정교한 Replacement 알고리즘을 사용한다. Miss Rate를 최소화하기 위해 지금까지도 훌륭한 알고리즘이 많이 개발되어 왔다. 대표적인 알고리즘이 Second Chance 알고리즘이다. 마지막으로, Write-back 방식을 채택한다. Write-through 방식은 쓰기 작업을 수행할 때마다 디스크에 접근을 시도해야 해서 시간적으로 엄청난 낭비가 발생한다. 따라서 디스크의 접근을 최소화하기 위해 Write-back 방식을 채택한다.

※ Second Chance 알고리즘

LRU(Least Recently Used) 알고리즘을 근사적으로 구현한 알고리즘이다. FIFO 또는 순환 큐에 참조된 순서대로 PTE 정보가 저장되어 있고, 메모리 참조 시마다 해당 PTE의 참조 비트를 1로 설정한다. 그러다가 페이지 폴트가 발생하여 특정 페이지를 추방해야 하는 상황이 되면, 가장 옛날에 참조된 PTE부터 시작하여 다음과 같은 방법으로 추방할 페이지를 찾는다. 우선, 현재 보고 있는 PTE의 참조 비트를 확인한다. 만약 0이라면 그 페이지를 추방하면 된다. 반면 1이라면 그 값을 0으로 바꾸고(= 한 번 살아남을 기회를 주고) 다음 PTE를 확인한다. 그리고 추방할 페이지를 찾을 때까지 이 과정을 반복한다. 만약 모든 PTE의 참조 비트가 1이라면 한 바퀴를 돌아서 참조 비트를 0으로 바꿨던 최초의 PTE에 다시 도달하여 그 페이지를 추방하게 될 것이다. 이 알고리즘의 기본 아이디어는 이렇다. 참조 비트가 0으로 바뀐 뒤 한 번이라도 재 참조되면 참조 비트가 다시 1로 설정되므로 이후 추방할 페이지를 찾을 때 살아남게 된다는 것이다. 따라서 자주 참조되지 않는 페이지는 이후 추방할 페이지를 찾을 때에도 여전히 참조 비트가 0일 수 있고, 이러한 경우 살아남지 못하고 추방당하는 것이다.

2-2. 페이지 테이블 (Page Table)

페이지 테이블(Page Table)은 가상 페이지와 물리 페이지 사이의 맵핑 정보를 담은 테이블로, 메인 메모리의 커널 영역에 저장되는 자료 구조 중 하나이다. 각 프로세스는 자신만의 페이지 테이블을 가지기 때문에, 문맥 전환을 수행할 때 저장 및 복원하는 문맥 정보에도 해당 프로세스의 페이지 테이블 정보가 포함된다. 페이지 테이블의 각 엔트리는 페이지 테이블 엔트리(Page Table Entry, PTE)라고 부른다. 각 PTE는 해당 가상 페이지가 어떤 물리 페이지에 맵핑이 되어 있는지, 또는 맵핑이 되어 있지 않다면 디스크의 어느 위치에 존재하는지에 대한 정보를 담고 있다. 만약 프로그램이 사용하지 않아서 할당되지 않은 가상 페이지라면 null 값을 저장한다. 이를 그림으로 나타내면 다음과 같다.

2-3. 페이지 히트 (Page Hit)

접근하고자 하는 가상 주소에 해당하는 PTE의 Valid 비트가 1이면, 해당 가상 페이지가 물리 페이지에 맵핑되어 있음을 의미한다. 이를 페이지 히트(Page Hit) 또는 DRAM 캐시 히트라고 부른다. 이제 해당 PTE의 정보를 바탕으로 가상 주소를 물리 주소로 변환하여 메인 메모리에 접근하기만 하면 된다. 이를 그림으로 나타내면 다음과 같다.

2-4. 페이지 미스 (Page Miss) → 페이지 폴트 (Page Fault)

접근하려는 가상 주소에 해당하는 PTE의 Valid 비트가 0이고 그곳에 디스크의 특정 위치 정보가 저장되어 있다면, 해당 가상 페이지가 물리 페이지에 맵핑되어 있지 않음을 의미한다. 이를 페이지 미스(Page Miss) 또는 DRAM 캐시 미스라고 부른다. 이러한 경우 페이지 폴트(Page Fault) 예외가 발생하여 페이지 폴트 핸들러(Page Fault Handler)가 호출된다. 그러면 페이지 폴트 핸들러는 현재 메인 메모리에서 특정 물리 페이지를 선택하여 추방하고, 디스크에게 요청된 가상 페이지를 가져오도록 명령한 뒤 문맥 전환을 통해 잠시 다른 프로세스에게 제어를 넘겨준다. 이후 디스크가 가상 페이지를 메인 메모리에 로드하는 작업을 완료하면, 인터럽트를 발생시켜서 문맥 전환을 통해 다시 페이지 폴트 핸들러의 프로세스로 제어를 옮긴다. 그러면 페이지 폴트 핸들러는 추방된 물리 페이지와 새로 들어온 물리 페이지의 정보를 바탕으로 PTE를 갱신하고, 페이지 폴트를 일으켰던 명령어의 위치로 다시 리턴하여 해당 명령어를 재실행한다. 그러면 이번에는 페이지 히트가 발생하므로 위에서 설명한 방식대로 메모리 참조를 진행하면 된다. 이를 그림으로 나타내면 다음과 같다.

※ 추방하려는 물리 페이지의 Dirty 비트가 1이라면 해당 물리 페이지 내용을 먼저 디스크에 반영해줘야 한다. (Write-back)

※ 페이지 폴트 핸들러는 커널 영역에 항상 상주하고 있다. 이곳에서 페이지 폴트가 발생하면 곤란할 것이다.

2-5. 페이지 할당 (Allocating Pages)

유저 프로세스로 실행되는 프로그램이 추가적으로 힙 영역을 할당하려고 시도하면(EX. malloc 함수), 커널은 적절한 크기의 연속적인 가상 페이지들을 디스크에 할당하고 그것들에 해당하는 PTE들을 페이지 테이블에 새로 만들어 준다. 그렇게 생성된 각각의 PTE는 Valid 비트가 0이며, 해당 가상 페이지가 디스크의 어느 위치에 할당되어 있는지에 대한 정보를 담게 된다. 이를 그림으로 나타내면 다음과 같다.

2-6. 작업 집합 (Working Set)

이와 같은 가상 메모리 기술이 훌륭한 성능을 보이는 것은 프로그램의 지역성(Locality)을 잘 활용했기 때문이라고 할 수 있다. 실제로, 각 프로그램은 특정 한 시점에 몇 개의 활성화된 가상 페이지들에 접근하는 경향이 있다. 그러한 가상 페이지들의 집합을 작업 집합(Working Set)이라고 한다. 쉽게 말해서 작업 집합은 프로그램이 자주 사용하는 가상 주소 공간을 의미한다. 만약 프로그램이 시간적 지역성(Temporal Locality)을 잘 활용할 수 있도록 짜여 있다면, 작업 집합의 크기는 작을 것이다.

만약 작업 집합의 크기가 메인 메모리의 크기보다 작다면, 최초의 미스(Compulsory Miss) 이후에는 메모리 참조에 있어서 굉장히 좋은 성능을 보일 것이다. 반면, 작업 집합의 총크기가 메인 메모리의 크기보다 크다면, 특정 가상 페이지가 물리 페이지에 맵핑이 되었다가 해당 물리 페이지가 다시 추방당하는 과정이 계속 반복될 것이다. 이러한 현상을 트래싱(Thrashing)이라고 하며, 트래싱이 발생하면 대부분의 시간이 페이지 폴트를 처리하는 데 사용되므로 메모리 참조 성능이 심각하게 저하된다.

3. VM for Memory Management

3-1. 메모리 관리 (Memory Management)

가상 메모리 기술은 메모리 관리(Memory Management) 측면에서도 중요한 역할을 수행한다. 핵심적인 아이디어는 이렇다. 각 프로세스는 자신만의 가상 주소 공간을 가지기 때문에, 메인 메모리를 혼자서 사용하는 것처럼 생각해도 전혀 문제가 없다는 것이다. 다만 실제로는 그것이 불가능하기 때문에 맵핑 함수가 각 프로세스의 몇몇 가상 페이지들만 물리 페이지에 적절히 맵핑하고, 그 정보를 페이지 테이블에 기록하는 것이다. 그러면 각 프로세스는 자신의 페이지 테이블 정보를 바탕으로 특정 가상 페이지에 해당하는 물리 페이지를 요청하면서 메모리 참조를 진행할 수 있다.

이때, 각각의 가상 페이지는 어떠한 물리 페이지에도 맵핑될 수 있으며, 동일한 가상 페이지라 하더라도 맵핑 시점에 따라 다른 물리 페이지에 맵핑될 수 있다. 이는 DRAM 캐시의 Fully Associativity 특성에 기인한다. 따라서 맵핑 함수만 적절히 잘 선택된다면 메모리를 더 단순하게 할당하거나 관리하는 것도 가능해진다. 심지어는 서로 다른 가상 페이지들을 하나의 물리 페이지에 맵핑함으로써 프로세스들 간의 코드 및 데이터의 공유를 가능하게 할 수도 있다. 이를 그림으로 나타내면 다음과 같다.

3-2. 링킹 및 로딩의 단순화 (Simplifying Linking and Loading)

3-2-1. 링킹의 단순화

가상 메모리 시스템에서는 각 프로그램이 똑같은 포맷의 가상 주소 공간을 가진다. 예를 들어, 모든 프로세스의 가상 주소 공간은 코드 세그먼트, 유저 스택, 공유 라이브러리 영역이 동일한 주소에서 시작하게 되어 있다. 이러한 통일성으로 인해, 링커를 디자인하고 구현하는 것이 매우 단순화된다. 가령 링커가 완전한 하나의 실행 가능한 파일을 만들어내는 과정에서, 해당 프로그램의 코드와 데이터가 실제로 메인 메모리의 어느 위치에 맵핑이 될지 전혀 고려할 필요가 없어진다.

3-2-2. 로딩의 단순화

로더에 해당하는 execve 함수는 .text 섹션과 .data 섹션을 위한 가상 페이지들을 디스크에 할당하고, 그것들에 대한 PTE들을 새로 만들어서 Valid 비트를 0으로 설정하고 디스크 내 적절한 위치를 가리키도록 한다. 여기서 주의할 점은 로더는 가상 페이지들을 메인 메모리에 직접 올리지 않는다는 것이다. 대신, 나중에 CPU가 특정 명령어를 명령어 메모리에서 Fetch 하거나 데이터 메모리에 접근해야 하는 명령어를 수행할 때, 가상 메모리 시스템에 의해 요청된 가상 페이지들이 메인 메모리에 올라가고 해당 PTE가 적절히 수정된다.

4. VM for Memory Protection

가상 메모리 기술은 메모리 보호(Memory Protection) 메커니즘의 구현을 용이하게 해준다. 가상 메모리 시스템에서는 CPU가 특정 가상 주소를 발생시킬 때마다 그것에 해당하는 PTE를 반드시 읽을 수밖에 없다. 따라서 각 PTE에 해당 가상 페이지에 대한 접근 권한 정보를 추가해주면 프로세스별로 각 가상 페이지에 대한 접근을 통제하는 것이 매우 쉬워진다. 이를 그림으로 나타내면 다음과 같다.

만약 PC에 저장된 값이 실행 권한이 없는 가상 페이지의 가상 주소이거나, 특정 명령어가 읽기/쓰기 권한이 없는 가상 페이지에 대하여 읽기/쓰기 작업을 수행하려 하면 하드웨어 수준에서 예외가 발생하여 예외 핸들러로 제어가 넘어간다. 예를 들어, x86-64 리눅스 시스템에서 읽기 권한이 없는 가상 페이지를 읽으려고 시도하면 General protection fault 예외가 발생하여 "Segmentation faults" 메시지가 출력된다. 또한 할당되지 않은 가상 페이지(Valid 비트 = 0 & 디스크 위치 정보 없음)에 접근할 때도 마찬가지 결과가 나타난다.

5. Address Translation

5-1. 용어 정리

용어/기호		의미
N = 2^n		가상 주소 공간 내 주소의 개수
M = 2^m		물리 주소 공간 내 주소의 개수
P = 2^p		페이지 사이즈 (바이트 단위)
V = {0, 1, 2, . . . , N-1}		가상 주소 공간
P = {0, 1, 2, . . . , M-1}		물리 주소 공간
MAP : V → P ∪ {∅}		가상 주소 VA에 대하여, 1) VA가 PA에 맵핑되어 있는 경우 : MAP(VA) = PA 2) VA가 물리 주소 공간에 맵핑되지 않은 경우 : MAP(VA) = ∅
가상 주소 (Virtual Address)	VPO (Virtual Page Offset)	가상 페이지 내 오프셋
	VPN (Virtual Page Number)	가상 페이지 번호
	TLBI (TLB Index)	TLB 집합 번호
	TLBT (TLB Tag)	동일한 TLB 집합에 맵핑되는 PTE들을 구별해주는 태그
물리 주소 (Physical Address)	PPO (Physical Page Offset) = VPO	물리 페이지 내 오프셋
	PPN (Physical Page Number)	물리 페이지 번호
	CO (Byte Offset within Cache Line)	캐시 블록 내 오프셋
	CI (Cache Index)	캐시 집합 번호
	CT (Cache Tag)	동일한 캐시 집합에 맵핑되는 캐시 블록들을 구별해주는 태그

5-2. 주소 변환 (Address Translation)

페이지 테이블 엔트리(PTE) 정보를 바탕으로 가상 주소(Virtual Address)를 물리 주소(Physical Address)로 변환하는 과정은 다음과 같다. 먼저 변환하고자 하는 가상 주소에 해당하는 PTE를 찾아간다. 만약 PTE의 Valid 비트가 0인데 그곳에 디스크의 특정 위치 정보가 저장되어 있다면, 해당 가상 페이지가 물리 페이지에 맵핑되어 있지 않음을 의미하므로 페이지 폴트 예외가 발생한다. 반면 PTE의 Valid 비트가 1이면 해당 가상 페이지가 물리 페이지에 맵핑되어 있음을 의미하므로, 해당 PTE에서 맵핑된 물리 페이지의 번호(PPN)를 알아낸다. 그리고 여기에 가상 주소의 페이지 오프셋 정보(VPO)를 덧붙여 주면 물리 주소가 완성된다. 참고로 페이지 테이블 자체의 시작 주소는 CPU 내 페이지 테이블 베이스 레지스터(Page Table Base Register, PTBR)라는 곳에 저장이 되어 있다.

5-3. TLB (Translation Lookaside Buffer)

TLB(Translation Lookaside Buffer)는 메인 메모리에 존재하는 페이지 테이블의 캐시로서, MMU 내부에 존재하는 작은 하드웨어 버퍼 장치를 의미한다. 즉 TLB에는 참조되는 빈도가 높은 페이지 테이블 엔트리(PTE)들이 저장된다. 캐시 메모리가 메인 메모리의 캐시로 사용되는 것과 마찬가지 관계이다. 따라서 TLB 히트가 발생하면 페이지 테이블 참조를 위해 메인 메모리에 찾아갈 필요가 없어진다. 만약 TLB가 없다면 페이지 테이블을 참조하는 과정에만 최소한 1번의 메모리 참조를 진행해야 하며, 또 다른 메모리 참조로 인해 캐시 메모리 내에서 페이지 테이블 일부가 추방이라도 당하면 추후 캐시 메모리의 Miss Penalty로 인해 주소 변환 과정은 더욱 느려질 것이다.

TLB에 접근하여 PTE를 가져오는 과정은 위 그림과 같다. 앞에서 알아보았듯이 각 PTE의 주소는 가상 주소의 VPN을 통해 알아낸다. 따라서 TLB에 접근할 때도 가상 주소의 VPN을 입력한다. 그리고 VPN 중 TLB 집합의 번호를 의미하는 TBLI 부분을 통해 해당 PTE가 위치할 수 있는 집합에 찾아간다. 그곳에서 만약 TBLT와 동일한 태그를 갖는 유효한(Valid 비트 = 1) 라인이 발견되면 TLB 히트이므로, 해당 라인에서 PTE를 가져오면 된다. 반면 TLBT와 동일한 태그를 갖는 유효한 라인이 없다면 TLB 미스이므로, 어쩔 수 없이 메인 메모리로 찾아가서 PTE를 직접 가져와야 한다. 전체적으로 캐시 메모리와 동작 방식이 거의 유사함을 알 수 있다.

※ 문맥 전환 시 TLB에 존재하는 모든 라인의 Valid 비트는 0으로 세팅된다.

※ 페이지 폴트 핸들러는 추방된 물리 페이지와 새로 들어온 물리 페이지의 정보를 바탕으로 PTE와 TLB의 내용을 함께 갱신한다. 특히, 추방되는 물리 페이지에 해당하는 TLB 내 PTE는 Valid 비트를 0으로 설정한다. 이를 통해 TLB 히트가 발생하면 반드시 해당 가상 페이지가 물리 페이지에 맵핑되어 있음을 보장하게 된다.

5-4. 메모리 참조 전체 과정 ★★★

지금까지 논의한 내용을 종합해 보자. 우선, 프로그램에서 메모리를 접근하는 경우는 두 가지이다. 하나는 PC에 저장된 값을 바탕으로 명령어 메모리에서 명령어를 읽어오는 경우이고, 나머지 하나는 데이터 메모리를 접근하는 특정 명령어(EX. popq, pushq, movq)를 실행하는 경우이다. 그리고 이러한 메모리 접근은 전부 가상 주소에 근거하여 이뤄진다. 이제 CPU가 메모리 접근을 위해 특정 가상 주소(VPN)를 발생시켰다고 가정해 보자. 그러면 우선 PTE를 가져오기 위해 TLB를 방문하게 된다.

만약 TLB 히트라면, 그곳에 존재하는 PTE를 바탕으로 가상 주소를 물리 주소로 변환한다. 그러면 이제 해당 물리 주소를 바탕으로 메모리 계층(L1 캐시 → L2 캐시 → 메인 메모리)에 접근하면 된다(이 과정에서 발생하는 미스들은 전부 하드웨어 수준에서 처리). 참고로, TLB 히트이면 해당 가상 페이지가 물리 페이지에 반드시 맵핑되어 있음이 보장된다. (곧 알아보겠지만) TLB 미스가 발생하여 TLB에 PTE를 캐시 하는 시점에는 이미 해당 가상 페이지가 물리 페이지에 맵핑되어 있는 상태이며, 페이지 폴트 핸들러에 의해 특정 물리 페이지가 추방되는 경우에는 이에 해당하는 TLB 내 PTE의 Valid 비트도 0으로 세팅되기 때문이다.

반면 TLB 미스라면, 다시 두 가지 경우로 나뉜다. 먼저, 해당 가상 페이지가 물리 페이지에 맵핑되어 있는 경우이다. 이러한 경우 메모리 계층에 접근하여 해당 가상 페이지에 대한 PTE를 가져오고, 이를 TLB에 반영해준다(이 과정은 하드웨어 혹은 소프트웨서 수준에서 처리). 그리고 해당 PTE를 바탕으로 가상 주소를 물리 주소로 변환하여 메모리 계층에 접근하면 된다.

다음으로, 해당 가상 페이지가 물리 페이지에 맵핑되어 있지 않은 경우이다. 이러한 경우 메모리 계층에 접근하여 가져오는 PTE의 정보를 보고 페이지 폴트 예외를 발생시킨다. 그러면 페이지 폴트 핸들러는 앞서 설명했듯이 특정 페이지를 추방하고 새로운 페이지를 가져온 뒤 이에 맞게 PTE와 TLB의 정보를 갱신해준다. 이제 다시 페이지 폴트를 유발했던 명령어를 재실행하면 바로 앞에서 설명했던 'TLB 미스인데 해당 가상 페이지가 물리 페이지에 맵핑되어 있는 경우'가 된다.

위에서 설명한 세 가지의 경우를 각각 그림으로 나타내면 다음과 같다.

5-4-1. TLB 히트 (→ 페이지 히트)

5-4-2. TLB 미스, 페이지 히트

5-4-3. TLB 미스, 페이지 폴트

※ Miss Handling

1) 캐시 메모리 미스 : 하드웨어 수준의 처리

2) 페이지 폴트 : 소프트웨어 수준의 처리 (예외 메커니즘)

3) TLB 미스 : 하드웨어 또는 소프트웨어 수준의 처리 (하드웨어 수준의 처리는 성능이 좋고 빠르지만, 소프트웨어 수준의 처리는 여러 알고리즘의 개발 가능성이 열려 있으므로 Flexibility가 매우 높다는 특징이 있음)

5-5. 멀티 레벨 페이지 테이블 (Multi-Level Page Table)

캐시 메모리와 달리 DRAM 캐시는 Fully Associative 특성을 가지기 때문에 각각의 가상 페이지가 어떠한 물리 페이지에 맵핑이 되는지를 나타내는 커다란 페이지 테이블이 필요하다. 그러나 페이지 테이블의 크기는 가상 페이지의 개수에 비례하므로, 페이지 테이블을 커널 영역에 그대로 저장하기는 곤란하다. 가령 가상 주소가 48비트로 표현되고, 페이지의 사이즈는 4KB이며, 각 PTE의 사이즈는 8바이트인 시스템을 가정해 보자. 그러면 페이지 테이블의 사이즈는 2*(48-12+3)=2^39 바이트, 즉 512GB가 된다. 이는 주기억 장치가 아니라 보조 기억 장치에도 저장하기 부담스러운 크기이다.

이러한 문제를 해결하는 것이 바로 멀티 레벨 페이지 테이블(Multi-Level Page Table)이다. 지금까지 다뤘던 페이지 테이블이 1단계 페이지 테이블이라면, 이제 이것을 n단계로 늘리자는 것이다. 그러면 n단계 페이지 테이블의 각 엔트리는 (n+1)단계 페이지 테이블 하나를 가리키고, 마지막 단계 페이지 테이블의 각 엔트리는 해당 가상 페이지에 대한 PTE를 저장하게 된다. 이를 그림으로 나타내면 다음과 같다.

그리고 멀티 레벨 페이지 테이블을 바탕으로 가상 주소를 물리 주소로 변환하는 과정은 다음과 같다. 이와 같이 각 단계의 페이지 테이블을 순차적으로 검색하여 물리 주소를 알아내는 과정을 페이지 워크(Page Walk)라고 부른다.

6. Simple Memory System Example

이해를 돕기 위해 간단한 메모리 시스템을 가정해 보고, 이를 통해 주소 변환이 어떻게 되는지 구체적으로 알아보도록 하자.

6-1. 주소 체계

6-2. TLB

6-3. 페이지 테이블 (일부)

6-4. 캐시 메모리

6-5. 주소 변환 예시 ①

6-6. 주소 변환 예시 ②

7. Case Study : The Intel Core i7/Linux Memory System

이제 마지막으로 현대에 사용되는 실제 메모리 시스템을 살펴보면서 가상 메모리 기술의 논의를 마치도록 하자. CPU와 운영체제의 종류에 따라 여러 시스템이 존재하겠지만, 그중에서도 우리는 인텔 코어 i7 CPU 기반의 리눅스 시스템을 다뤄보도록 할 것이다. 현재 인텔 코어 i7 CPU는 48비트의 가상 주소 공간(256TB)과 52비트의 물리 주소 공간(4PB)을 가지며, 호환성을 지키기 위해 32비트의 가상/물리 주소 공간(4GB)도 지원한다. 그러면 이제 이를 바탕으로 전반적으로 메모리 시스템이 어떻게 구축이 되어 있는지 알아보도록 하자.

7-1. 메모리 시스템

다음 그림은 인텔 코어 i7의 메모리 시스템을 요약해준다. 프로세서 패키지(칩)에는 4개의 코어가 존재하고, 모든 코어가 공유하는 L3 캐시 하나가 존재하며, 메인 메모리의 인터페이스에 해당하는 DDR3 메모리 컨트롤러가 존재한다. 그리고 각각의 코어는 데이터 및 명령어의 참조를 위한 캐시 계층을 갖추고 있고, PTE 참조를 위한 TLB 계층도 갖추고 있다. 이때 캐시 계층과 TLB 계층은 메인 메모리의 캐시 역할을 수행하므로 DDR3 메모리 컨트롤러를 통해 메인 메모리와 연결이 되어 있다. 마지막으로 페이지 사이즈의 경우 4KB 혹은 4MB로 설정이 되는데, 리눅스의 경우에는 4KB로 설정된다.

7-2. 메모리 참조 전체 과정

다음 그림은 인텔 코어 i7 CPU의 전체적인 메모리 참조 과정을 요약해준다. 각 프로세스는 자신만의 4단계 페이지 테이블 계층을 가진다. 참고로, 코어 i7 CPU의 구현 상으로는 페이지 테이블 자체에 해당하는 페이지들도 추방되거나 새로 들어올 수 있는 구조이지만, 리눅스는 할당된 가상 페이지에 해당하는 페이지 테이블들이 메모리에 항상 상주할 수 있도록 한다. 그리고 CR3는 첫 번째 단계 페이지 테이블의 물리적인 시작 주소를 저장하는 컨트롤 레지스터로, 이 또한 각 프로세스의 문맥에 포함되는 상태 정보이다.

7-3. 페이지 테이블 엔트리 (PTE)

네 단계의 페이지 테이블에 저장되는 각 PTE의 포맷은 다음과 같다. Level 1-3 페이지 테이블의 각 엔트리는 다음 단계의 페이지 테이블을 가리키고, 마지막 단계에 해당하는 Level 페이지 테이블의 각 엔트리는 해당 가상 페이지가 맵핑된 물리 페이지를 가리킨다. PTE에 저장되는 각 필드에 대한 설명은 바로 이어서 등장하는 표에 나타나 있다.

필드		설명
P		Level 1-3 페이지 테이블 엔트리의 경우, P의 값이 1이면 가리키는 페이지 테이블이 존재함을 의미하고 초록색으로 표시된 주소 필드가 다음 단계 페이지 테이블의 시작 주소에 해당하는 물리 페이지의 번호(PPN)를 저장한다. 따라서 모든 페이지 테이블들은 시작 주소가 4KB의 배수가 되도록 정렬되어 있어야 한다. 반면에 P의 값이 0이면 가리키는 페이지 테이블이 존재하지 않음을 의미한다. 반면 Level 4 페이지 테이블 엔트리의 경우, P의 값이 1이면 페이지 히트를 의미하고 초록색으로 표시된 주소 필드가 맵핑된 물리 페이지의 번호(PPN)를 저장한다. 각 물리 페이지는 당연히 시작 주소가 4KB의 배수가 되도록 정렬되어 있을 것이다. 반면에 P의 값이 0이면 맵핑된 물리 페이지가 없거나 할당되지 않은 가상 페이지임을 의미한다.
접근 권한	R/W	읽기/쓰기 (Read/Write) vs 읽기 전용 (Read-only)
	U/S	유저 프로세스가 접근할 수 있는 가상 페이지인가?
	XD	실행할 수 없는 가상 페이지인가? (64비트 시스템에서부터 도입된 필드로, 잘못된 세그먼트에 악성 프로그램의 코드를 삽입하는 버퍼 오버플로우 공격을 예방하는 역할을 수행)
A		해당 가상 페이지가 참조될 때마다 MMU에 의해 1로 셋팅된다. (Replacement 알고리즘에 활용)
D		해당 가상 페이지에 쓰기 작업을 수행할 때마다 MMU에 의해 1로 셋팅된다. (Write-back)

7-4. 주소 변환 (Address Translation)

이제 위와 같은 네 단계의 페이지 테이블을 이용하여 가상 주소를 물리 주소로 변환하는 과정을 나타내 보면 다음 그림과 같다. 36비트 길이의 VPN을 네 개의 9비트로 나누면, 각각의 9비트는 해당 단계의 페이지 테이블 내에서의 오프셋을 의미하게 된다. 그리고 앞서 말했듯 CR3는 첫 번째 단계의 페이지 테이블의 물리적인 시작 주소를 저장한다. 참고로 동일한 가상 주소 공간에 대해 한 단계의 페이지 테이블만 사용한다면 해당 페이지 테이블의 총사이즈는 2^(36+3) = 512 GB가 된다. 이것이 곧 멀티 레벨 페이지 테이블을 사용하는 이유이다.

7-5. L1 캐시 참조 속도를 높이는 사소한 트릭

물리 주소에서 캐시 메모리 집합 번호를 나타내는 CI(Cache Index)가 VPO(=PPO)의 안쪽에 위치해 있다면, 병렬적 처리를 통해 L1 캐시 참조 속도를 조금이나마 향상시킬 수 있다. 가상 주소를 물리 주소로 변환하기 전에 미리 CI의 값을 알 수 있고, 이를 통해 미리 원하는 블록이 위치할 수 있는 캐시 집합에 찾아갈 수 있기 때문이다. 따라서 가상 주소를 물리 주소로 변환하여 CT 값을 알아내고 나면 곧바로 태그 값 비교를 진행할 수 있다. 참고로 이러한 트릭을 보고 "Virtually indexed, physically tagged"라고도 한다. 이를 그림으로 나타내면 다음과 같다.

저작자표시

'컴퓨터 구조 (Architecture) > CSAPP' 카테고리의 다른 글

[CSAPP] Exceptional Control Flow (10)	2020.03.24
[CSAPP] Linking (13)	2020.03.22
[CSAPP] Cache Memory (6)	2020.03.22
[CSAPP] Memory Hierarchy (6)	2020.03.17
[CSAPP] Pipelining - Performance (0)	2020.03.15

현재글[CSAPP] Virtual Memory

IT 엘도라도