9.6-Address_Translation

이 챕터에서는 주소변환의 기본을 다룬다.
여기서 VM을 도와주는 하드웨어의 역할을 예제를 직접 다룰 수 있을 정도로 다룬다.
하지만, 여기서는 일부 세부적인 부분, 특히 시간적인 부분은 무시되어있다.

articles/chapter9/imgs/address_translation_symbols.png
주요한 키워드를 요약해두었다.

Address Translation 은
와
의 Mapping 으로 이해할 수 있다.

이 때 실제 값은

이다.

articles/chapter9/imgs/address_trans.png
MMU(Memory Management Unit) 가 어떻게 Page Table 을 이용해서 이 맵핑을 수행하는지 보여준다.

CPU 안의 Control Register 인 가 현재의 Page Table 을 가르키고 있다.
bit 의 Virtual Address 는 2가지 부분으로 나뉜다.
bit 의 와 bit 의 으로 이루어져있다.

VPN 은 올마른 PTE 를 고를 때 사용된다.
예를 들어 VPN 0 은 PTE 0 을 가르키게 된다.

대응하는 Physical Addrss 는 2개의 부분을 합쳐서 구할 수 있다.
Page Table Entry 의 과 Virtual Address 의 로 이루어진다.

이 때, Physical, Virtual 모두 byte 를 사용하기 때문에,
Physical Page Offset(PPO) 가 동일하다.

Page Hit

articles/chapter9/imgs/page_hit_detail.png
Page Hit 일 때는 Hardware 가 처리해준다.

Processor 는 Virtual Address 를 생성해 MMU 로 보내준다.
MMU 는 PTE 주소를 만들고, Cache/Main Memory 에 요청한다.
Cache/Main Memory 는 PTE 를 MMU로 반환한다.
MMU 는 Physical Address 를 만들고, Cache/Main Memory 에 보낸다.
Cache/Main Memory 는 요청받은 data word 를 CPU로 보낸다.

Page Miss

articles/chapter9/imgs/page_miss_ex.png
Page Hit 은 하드웨어 만으로 관리되지만,
Miss 의 경우, OS의 Kernel 과 하드웨어의 협력에 의해 다뤄진다.

1~3 번까지는 동일하다. PTE 를 가져온다.
4. Valid bit 가 0 인 경우로, MMU 는 exception 을 유발시킨다. 이는 통제를 CPU에서 OS 내부의 Kernel 에 존재하는 Page Fault Exception Handler 에 넘긴다.

Fault Handler 는 Physical Memory 에 있는 Victim Page 을 인지하고,
만약 내용이 변했다면, Disk 에 반영한다.
Fault Handler 는 Disk 의 내용을 다시 가져오고,
Memory 의 PTE 업데이트한다.
Fault Handler 는 원래 Process 에게 통제를 넘겨준다. 이후에 실패했던 명령어를 다시 실행한다.
CPU 는 Virtual Address 를 MMU 에게 다시 보낸다.
Handler 에 의해 Caching 되었으므로,
Page Hit의 4번부터 진행하게 된다.

9.6.1 Integraing Caches and VM

articles/chapter9/imgs/VM_and_Cache.png

Virtual Memory 와 SRAM Cache 를 같이 쓰는 시스템에서,
Virtual 또는 Physical Address 가 SRAM Cache 에 접근할 수 있는지에 대한 논의가 있다.

자세한 trade-off 는 우리의 범위를 넘어서지만,
대부분의 시스템은 Physical Address 가 SRAM 에 접근한다.

이는 여러 Process 가 동시에 각자의 Block을 Caching 하고, 같은 Virtual Page 을 통해 Block 을 공유하는 상황을
직관적으로 만들어주기 때문이다.

그리고, Cache 는 Protection 관련 이슈는 다룰 수 없다.
접근 권한은 Address Translation Process 의 일부이기 때문이다.

그림은 Physical Address 와 Cache 가 어떻게 통합되어 있는지 보여준다.
핵심 아이디어는 Address Translation 이 Cache Lookup보다 먼저 일어난다는 것이다.

9.6.2 Speeding Up Address Translation with a TLB

CPU 가 Virtual Address 를 생성할 때마다, MMU 가 Virtual Address 를 Physical Address로 바꾸기 의해서는 PTE 를 가져와야 한다.
최악의 경우, Memory 에서 추가적인 Fetch 가 필요할 수 있다. 이는 천단위의 Cycle 이 필요하다.
PTE 가 L1 Cache 에 Caching 되어있으면 비용을 절감할 수 있다.
현대의 시스템은 MMU 안에 를
PTE 를 위한 Cache 로 그 비용을 더 줄이고자 한다.

TLB 는
작고, 각 Line 은 하나의 PTE에 해당하는 Block 을 가진 Cache 이다.
articles/chapter9/imgs/TLB_index.png
위와 같이 Virtual Page Number 에서 바로 Tag 와 Index 를 구한다.
Block 에는 하나의 PTE 가 있기 때문에 Offset 은 필요하지 않다.

TLB Hit

articles/chapter9/imgs/TLB_Hit.png

CPU 가 Virtual Address 를 만든다.
MMU 가 PTE 를 TLB 에 요청한다.
TLB 가 PTE 를 반환한다.
MMU 는 해당 PTE 를 이용해, Physical Address 로 바꿔, Cache/Main Memory 로 전달한다.
Cache/Main Memory 를 해당하는 데이터를 CPU에게 전달한다.

이 과정들은 MMU 내부에서, on-chip 으로 진행되기 때문에 빠르다.

TLB Miss

articles/chapter9/imgs/TLB_Miss.png

이 때는, MMU가 L1 Cache 에서 PTE 를 가져와야한다.
새로운 PTE 는 TLB 에 저장되는데, 기존의 PTE 가 사라질 수 있다.

9.6.3 Multi-Level Page Tables

하나의 Page Table 을 가지고 논의했지만, 다음과 같은 상황을 고려해보자.
32bit 주소체계에서, 4KB Page, 4byte PTE 라면, 우리는 늘 4MB의 Page Table 이 Memory 에 존재해야한다.
개의 주소는 4KB 의 Page 개가 필요하다.
이에 대해 Page Table Entry 가 4Byte 이므로, 총 Byte 가 필요하다.

이를 위해서 Page Table 에 대한 계층구조를 활용한다.
이를 이해하기 위해서, 구체적인 예시로 살펴본다.

32bit 의 주소체계에서, 주소공간은 4KB 의 Page 로 이루어져있다.
PTE 는 각각 4Byte 로 구성된다.
처음 2K 개의 Page 는 Code 와 Data, 다음 6K는 할당되어있지 않고,
다음 1023개의 Page 역시 할당되어있지 않으며, 마지막 Page 에 User Stack 이 할당되어있다고 가정한다.

articles/chapter9/imgs/two_level_page.png
2단계의 계층으로 위와 같이 구성한다.
level-1 의 Page Table 은 4MB 의 Virtual Address Space 를 담당한다.
4MB 는 1024개의 Page 를 갖게 된다. (1개의 Page 는 4KB의 주소를 담당한다.)
총 주소공간이 4GB 이기 때문에 level-1 은 1024개면 충분하다.

만약 담당한 Chunk 가 모두 비어있다면, 해당 level-1 의 PTE는 Null 이다.
만약 Chunk 내부에 1개라도 Page 가 할당되면, level-1 PTE 는 level-2 의 PTE 를 가르킨다.

level-2 의 PTE 는 Virtual Memory의 4KB 의 Page 를 맵핑해줘야하는 책임이 있다.
level-1, level-2 의 Page Table 이 4KB 인 점은 Page 와 같은 사이즈로 편리함을 위해서이다.

이러한 방식은 Memory 측면에서 2가지로 유리하다.
level-1 의 PTE 가 Null 이라면, 그에 대응하는 level-2 의 Page Table 은 존재하지 않아도 된다. 이것은 대부분의 Virtual Address Space 가 실제로 필요하지 않다는 점에서 유용하다.

level-1 의 Table 만이 Main Memory 에 항상 있으면 된다.
level-2 의 Table 은 필요에 의해 VM System 이 동적으로 할당 및 제거할 수 있다.
많이 사용되는 level-2 의 경우는 Main Memory 에 Caching 된다.

articles/chapter9/imgs/k_level_address_trans.png
위의 그림은 지금까지의 Address Translation 을 요약해준다.

Virtual Address 는 k개의 VPN(Virtual Page Number) 과 VPO(Virtual Page Offset) 으로 나뉜다.
각 k 이하의 PTE에서는 다음 단계의 Page Table 의 시작점을 가르킨다.
k-level Table 은 PPN 을 가져, MMU 는 이 PPN 과 PPO(VPO 와 같은) 을 조합해 Physical Address 를 구성한다.

k개의 PTE 에 접근하는게 비효율적으로 보일 수 있지만,
TLB 를 통한 Caching 이 이를 효율적으로 만들어준다.
실제로 Multi-level Table 는 Single-level Table 과 거의 유사한 속도를 낸다.