Virtual Memory #2
- 프로그램은 Virtual Address 상에서 구현되며, 실제 D-RAM에 Access할 때에는 Physical Address를 사용한다.
(Virtual Address는 Physical Address로 Translation하기 위한 Mapping 정보는 메인 메모리의 Page Table에 저장되어 있다.)
- 데이터나 명령어에 접근하기 위해서는 실질적으로 2회의 Transaction(Memory Access)을 필요로한다. (비효율성)
1. Virtual Address를 Physical Address로 변환할 때, Page Table을 참고하기 위한 메인 메모리 접근
2. 원하는 데이터, 명령어를 가져오고자 할 때, Physical Address를 통한 실질적인 메인 메모리 접근
- TLB는 위와 같은 비효율성으로 인한 성능 저하를 개선하고자 고안한 개념이다.
- 통상, 4KB 크기의 Page Table Entry들 중에서, 최근에 사용했던 소수의 Entry만 CPU 내부의 TLB에 따로 저장한다.
- 즉, TLB는 소수의 Page Table Entry를 위한 Cache라 볼 수 있다.
- 우수한 Locality를 갖고있는 상황에서는 Translation을 위해 메인 메모리까지 접근하지 않고, TLB를 이용하여 빠르게 주소를 변환할 수 있게 된다.
- TLB가 탑재된 프로세서에서 일어나는 메모리 접근 과정이다.
- TLB는 통상적으로, 프로세서 내의 MMU(Memory Management Unit)의 일부이다.
- 메인 메모리의 Page Table에는 Physical Address와 Virtual Address 사이의 Mapping 정보와
특정 프로그램의 전체 Virtual Space에 대한 Translation 정보를 Page Table Entry 형태로 저장되어 있다.
- TLB에서 Cache Hit가 일어난다면, Virtual Address를 바로 Physical Address로 변환하여 원하는 데이터/명령어를 메인 메모리로 부터 가져올 수 있게 된다.(이러한 이상적인 상황에서는 Page Table에 접근할 필요가 없다.)
- TLB는 Page Table의 일부를 저장하는 Cache라 생각할 수 있다.
(일반적으로, Cache는 데이터/명령어의 일부를 저장하는 기억소자를 의미한다.)
- TLB와 Cache 모두, Hit Rate을 높이기 위한 개념이다.
- 대부분의 프로세서들은 Cache 혹은 메인 메모리에 접근하기 위해 Physical Address를 사용하며, 이는 TLB가 Virtual Address를 변환하여 얻어낼 수 있다.
- Virtual Address의 Bit Width는 32bits, Physical Address의 Bit Width은 30bits라 가정하자.
- TLB는 Cache와 같이, 구조적으로 3가지로 분류된다.
(Directed Mapped, Set Associative, Fully Associative)
- 셋 중, Directed Mapped TLB에 관한 설명이다.
- 32bits Virtual Address는 Tag 17bits, 8개의 Entry를 구분짓기 위한 3bits의 Index, 4KB의 Virtual Page를 다루기 위한 12bits의 Page Offset 로 구성된다.
(즉, Tag와 Index 20bits는 Page Number를 구분하기 위해, Page Offset 12bits는 특정 Page 내부의 위치를 구분하기 위해 사용된다 볼 수 있다.)
- 즉, \(2^20\)개의 서로다른 Virtual Page를 가질 수 있다.
- Valid 값이 1이고, Tag Comparison 결과가 참이면 TLB Hit가 발생한 것이다.
- TLB Hit가 발생하면, 해당 Virtual Address와 대응되는 Physical Address 정보를 담고있는 18bits의 Physical Page Number를 반환한다.
(Physical Address이든, Virtual Address이든 Page Offset은 고정적으로 12bits를 필요로하기 때문에, 30bits로 구성된 Physical Address에서 Physical Page Number는 18bits로 구성되는 것이다.)
- 4-Way Associative TLB에 관한 설명이다.
- 이 TLB가 가질 수 있는 최대 Entry 갯는 128개라 가정한다. (즉, 각 Way에는 32개의 Entry로 구성된다.)
- 마찬가지로, 4KB의 Virtual Page를 다루기 위한 12bits의 Page Offset로 구성된다.
- 각 Way에서 32개의 Entry를 구분짓기 위해 5bits의 Index로 구성된다.
- Tag는 15bits로 구성된다.
(즉, Tag+Index의 20bits를 이용하여 Virtual Page Number를 표현한다.)
- 4개의 각각의 Way에 대한 4개의 Comparator를 필요로 한다.
- TLB Hit를 확인하기 위해 Valid Bit도 AND 조건에 포함된다.
(전반적으로, Set Associative Cache와 동일한 동작 방식을 취한다.)
- TLB에 관한 용어들에 대한 설명이다.
- TLB 또한 Cache이므로, Hit, Miss가 발생될 수 있다.
TLB Hit
- CPU가 접근하고자 하는 Page가 이미 TLB에 저장되어 있는 상황이다.
TLB Miss
- CPU가 접근하고자 하는 Page가 TLB에 없는 상황이다.
- TLB Miss는 다시 아래 두 가지로 분류된다.
1) Merely TLB Miss
- 단순한 TLB Miss인 경우를 의미한다.
- 원했던 Page가 TLB에는 없지만, 메인 메모리에는 있는 상황을 의미한다.
- 메인 메모리의 Page Table에 접근하여 원하는 Page 정보를 TLB로 로딩하여 해결한다.
- 통상적으로, 10 Cycle 이상의 Penalty를 발생시킨다.
2) Page Fault
- 원하는 Page가 TLB에는 물론, 메인 메모리도 아닌, Disk(Secondary Stroage)에 있는 상황을 의미한다.
- 프로세서는 Disk에 접근하여 원하는 Page를 메인 메모리에 로드한다.
(Disk와 같이, 데이터 검색을 물리적으로 행하는 장치들은 굉장히 많은 Cycle Penalty를 발생시킨다.
※ TLB의 크기는 메인 메모리보다 훨씬 작기 때문에 Page Fault보다는 TLB Miss가 빈번히 발생하게 된다.
- TLB Miss와 Page Fault에 대한 구체적인 설명이다.
1. TLB Miss
- 요청한 Page가 메인 메모리에 위치한 상황이다.
- 메인 메모리에 있는 해당 Page Table Entry를 TLB로 Load한 다음, 프로세서는 다시 TLB에 접근하여 TLB Hit를 발생시킨다.
(H/W적 구현, S/W적 구현* 모두 가능한 부분이며, 일반적으로 S/W적으로 구현한다.)
* S/W적 구현 방법
- TLB Miss가 발생하면, Exception을 발생시켜 OS의 Exception Handler가 메인 메모리에 있는 Page Table에 접근하여 요청했던 Page Table Entry를 TLB에 로드하게 한다.
2. Page Fault
- 요청한 Page가 Disk(Secondary Stroage)에 위치한 상황이다.
- OS가 처리를 전적으로 담당한다.
- Page Fault가 발생되면, 현재 진행중인 프로세스를 Interrupt(중단)하고 제어권을 프로세스에서 OS에게 넘긴다.
- OS는 Virtual Address에 해당되는 Page Table Entry에 접근하여 원하는 Page가 저장된 Disk의 주소를 알아낸다.
- Disk에 있는 Page를 메인 메모리에 로드하되, 메인 메모리가 기존의 다른 Page로 가득 차 있는 경우, Page Replace를 수행한다.
- 교체할 Page에 Dirty Bit가 설정되어 있으면(기존에 Write 동작을 수행한 적이 있다면) 교체할 Page를 일단 Disk에 Write한 다음, Disk에 있던 요청한 Page를 메인 메모리에 로드한다.
- 위 작업들을 마친 후, Page Table을 Update하고, 중단했던 프로세스를 다시 재개한다.
※ Page Fault가 발생하면, Disk까지 접근해야 하므로, Penalty가 큰 편에 속한다.
- TLB의 구체적인 구조에 대한 설명이다.
- 일반적인 Cache의 경우, Write-Back, Write-Through 방식 중 하나를 택한 구조를 갖는다.
- Write-Back Cache는 어떤 Cache Block을 Update해야 하는 상황이 발생하면, 해당 Cache 부분만 Update하고, 메인 메모리에는 반영하지 않고 있다가, Replacement가 발생하면 그제서야 메인 메모리에 데이터를 기록하는 방식의 Cache를 의미한다.
(메인 메모리에 반영하지 않은 데이터는 Dirty Bit를 1로 설정하여 구분짓는다.)
- Replacement가 발생하기 전까지는 Cache에 보관된 데이터와 메인 메모리에 있는 데이터가 서로 일치하지 않는다.
- Replacement가 발생하면 Cache의 데이터가 메인 메모리까지는 동기화되지만, Disk까지는 동기화가 이루어지지 않는다.
- 메인 메모리에 새로 쓰여진 데이터는 Page 단위로 Disk에 저장된다.
- Cache와 메인 메모리 사이에서 그러했듯, 메인 메모리에서 Disk에 Write-Back하는 방식으로 수행된다면, 메인 메모리가 Disk에 데이터를 저장할 또 다른 Replacement Policy가 필요하다.
- 메인 메모리에 새로운 데이터가 쓰여졌고, 이 데이터를 아직 Disk에는 저장하지 않은 상황을 표시하기 위해(메인 메모리와 Disk 사이를 오가는 Page 단위의 데이터를 조사하여, 특정 Page에 쓰기 작업 수행 유무를 TLB에서 Tracking해야 하므로) TLB에도 Dirty Bit를 필요로하게 된다.
- 만약, Dirty = 1로 설정된 Entry가 메인 메모리의 Page와 Swap하는 기준을 위해 Ref bit를 가질 수 있다.
- 특정 Page의 Ref bit는 접근된 적이 있으면 1로 설정된다.
- OS는 주기적으로 Ref bit를 0으로 초기화하여, 시간이 지나 많은 Entry의 Ref bit가 모두 1로 설정되는 것을 막는다.
(주기적으로 초기화됨에도 불구하고, Ref bit가 1로 설정되어 있는 Entry는 최근(초기화 주기 이내)에 자주 이용되고 있는 Entry를 의미한다.)
- Page Table은 특정한 프로세스/프로그램의 전체 Virtual Space 에 해당하는 만큼의 Translation 정보를 저장하고 있다.
- Virtual Page Number에 해당하는 Page Table Entry는 Physical Page Number, Disk Address 중 하나의 형태로 Page Table에 저장되어 있다.
- Page Table에는 한 프로그램 전체에서 특정 Virtual Addreess를 Physical Address로 Translation하기위한 모든 정보가 저장되어 있으므로 Tag Bit를 굳이 필요로하지 않는다.
- 즉, Virtual Page Number에 해당되는 Page Table Entry는 Page Table에 반드시 저장되어 있는 구조이다.
- TLB에 저장된 데이터들이 Replacement될 때마다, Dirty, Ref가 설정된다.
- TLB에 저장된 내용들은 Locality를 고려하여 자주 사용할 것 같은 Page Table의 일부 Entry들이기 때문에, Tag Bits도 필요로 한다.
- 실제 사용되고 있는 프로세서의 TLB와 Cache 구조이다.
- 위 그림에서 TLB에는 Entry마다 Comparator가 위치해있다. 즉, 특정 Entry는 아무 Entry에나 진입 가능한 Fully Associative Cache 구조의 TLB이다.
- 32bits의 Virtual Address중 Page Offset 12bits를 제외한 나머지 20bits 값은 Tag Comparison을 위해 온전히 사용되며, 이러한 구조에서 Indexing은 필요하지 않다.
- 근래 사용되는 대부분의 Cache에서는 Physical Address를 사용한다.
- TLB Hit가 발생한 경우, Physical Page Number 20bits에 원래 Virtual Address의 Page Offset과 Concatenation하여 Physical Address를 만들어 낸다.
- 즉, 위 그림의 프로세서는 Virtual Address, Physical Address 모두 32bits Bit Width을 가진 형태임을 알 수 있다.
- Cache에 원하는 데이터가 있는지 확인하기 위해 Physical Address를 사용할 수 있다.
- Physical Address의 Block Offset, Byte Offset을 제외한 부분(상위 Bits)을 Tag와 Index로 활용할 수 있다.
- Cache가 Physical Address를 이용하여 Indexing과 Taging을 수행함으로써 원하는 데이터를 가져올 수 있게 한다.
- 이러한 구조를 PIPT(Physically-Indexed and Physically-Tagged Cache) 구조라 한다.
- Cache는 본래 Physical Address를 사용하는 Unit이기 때문에 PIPT 구조는 가장 직관적인 구조라 할 수 있다.
- 성능적인 측면에서 PIPT 구조에서는 Virtual Address를 항상 Physical Address로 변환해야 하기 때문에 성능 측면에서 불리한 면이 있다.
- 즉, Cache Hit가 발생되어도 TLB에 접근해야 하는 단점이 존재한다.
- VIPT(Virtually Indexed and Physically-Tagged) Cache와 같이 PIPT 구조의 단점을 개선한 Cache 구조도 존재한다.
