[컴퓨터 구조] 27. Virtual Memory (2) - TLB

TLB

가상 메모리를 사용할 때 참고하는 page table 이 메모리에 있기 때문에, page를 읽으려고 할 때마다 접근하는 시간이 오래 걸린다. (메모리에 대한 접근을 매우 느리게 만든다.)

메모리의 특정 부분에서 데이터를 읽기 위해서 2번의 메모리 접근이 필요한 것이다.

 

첫번째는 VA를 PA로 변환하기 위해 page table에 접근하면서 1번 메모리에 접근하고,

두번째는 이렇게 얻어온 PA를 가지고 데이터/명령어를 읽어오기 위해 메모리에 한번 더 접근한다.

 

그래서 이 문제를 해결하기 위해 하드웨어 지원을 추가하는 방법을 고민했다.

page table에 대한 접근은 그래도 spatial locality가 꽤 좋다.

명령어의 크기가 4byte인 것에 비해 4KB라는 페이지 크기는 매우 넉넉해서 한번 페이지를 캐싱했을 때, 가까운 미래에 동일한 페이지로 다시 접근할 확률이 높기 때문이다.

 

그래서 이 페이지 엔트리 자체를 캐싱하는 것을 떠올렸다.

페이지 정보를 얻기 위해 page table이 존재하는 메모리까지 매번 가는게 아니라, 메모리 이전에서 확인하는 것이다.

이 캐시를 TLB (Translation Lookaside Buffer) 라고 부른다.

이 캐시는 CPU 내의 저장공간을 이용하며, 최근 이용했던 physical page number (PTE)를 보관한다.

 

 

TLB는 프로세서 내부의 MMU (Memory Management Unit) 안에 존재한다.

CPU 가 현재 실행하려고 하는 명령어, 또는 데이터의 가상 주소를 MMU에 보내고, 만약 TLB에 이미 페이지 넘버를 잘 캐싱해두고 있었다면, page table을 거치지 않고 바로 phsical address를 얻을 수 있다.

 

그러면 곧바로 메모리에 접근해서 원하는 데이터를 얻어올 수 있게 된다.

이때 TLB는 Page Table 이 갖고있는 entry 일부를 캐싱해서 갖고 있다.

 

 

TLB & Cache

TLB와 캐시를 대해 함께 생각보자.

TLB는 page table에 대한 캐시라고 볼 수 있고, 지금까지 정리했던 '캐시'는 명령어와 데이터에 대한 캐시였다.

'캐시'는 보통 virtual address가 아니라 physicall address를 캐싱하기 때문에 TLB와 캐시를 조합하는 경우에는 아래와 같이 사용한다.

 

 

먼저 CPU가 요구하는 가상 주소를 TLB를 거쳐 physical address로 변환한 뒤, 이 주소에 대해 캐시를 찾아서 캐싱된 값이 있다면 바로 가져오고, 캐싱된 값이 없다면 캐시가 메모리에서 블록 단위로 데이터를 가져와 캐싱한 뒤, 다시 CPU에게 값을 돌려주게 된다.

 

(그런데 여기에서 의문점이 생겼다. 왜 굳이 매번 physical address로 바꿔야 하는걸까? virtual address로 캐싱해두고, cache miss가 발생했을 때만 virtual address를 physical address로 바꾼 다음 접근하면 더 효율적이지 않을까?)

 

 

TLB는 페이지 테이블의 엔트리를, '캐시'는 명령어 또는 데이터를 블록단위로 캐싱한다.

 

Example

32bit 길이의 가상주소 (4GB의 가상 공간), 30bit 길이의 물리 주소 (1GB의 메모리) 를 갖는 컴퓨터가 있다고 생각해보자.

그리고 먼저 TLB가 direct-mapped 구조로 되어있다고 해보자.

TLB의 entry는 8개, 각 페이지의 크기는 4KB 라고 해보자.

 

그러면 위와 같은 구조로 되어있을 것이다.

먼저 CPU가 사용하는 가상 주소는 아래와 같이 하위 12bit 를 page offset으로 빼고 남은 20bit를 virtual page number 로 사용한다.

 

이때 virtual page number의 하위 3bit 를 TLB 엔트리를 구분하는데 사용하고, 남은 17bit 를 Tag 로서 사용한다.

 

physical page number의 경우, 30bit에서 하위 12bit 페이지 오프셋을 뺀 나머지 18bit로 나타내므로

만약 valid bit가 1이고 tag가 일치하여 TLB hit가 발생하는 경우 위와 같이 물리주소를 구할 수 있다.

 

---

 

이번에는 같은 컴퓨터에서 TLB가 4-way set associative를 사용하는 경우를 살펴보자.

또한 이때 TLB 엔트리의 개수는 128개라고 해보자.

 

우선 TLB가 위와 같이 구성되어 있을 것이다.

LRU가 필요한 이유는 사용한지 가장 오래된 엔트리를 식별하여 방출하기 위해 존재한다.

 

4way 이기 때문에 128개 entry를 4개씩 set으로 묶으면 총 32개의 set이 나온다.

따라서 index는 0~31까지의 범위를 가질 수 있다.

 

 

 

이때 CPU가 사용하는 가상주소는 4KB 페이지 offset 12bit를 제외하고 남은 20bit 에서, TLB 인덱스를 구분할 5bit를 제외한 나머지 15bit를 Tag로 사용한다.

 

TLB Hit를 판별할 때는 셋 인덱스에 접근하여 4개의 way로 모두 가서 일치하는 tag와 valid 비트의 설정을 확인한다.

 

 

만약 TLB Hit 로 판별이 되면, 해당하는 physical page number 를 mux로 가져온 뒤, page offset을 합쳐서 물리주소로 변환하고 '캐시'로 보낸다.

 

---

TLB Hit & Miss

TLB는 페이지 테이블에 대한 일종의 캐시이므로 Hit 가 일어날 수도 있고, Miss가 일어날 수도 있다.

 

TLB Hit 가 발생하는 경우, CPU가 원하는 페이지 정보가 이미 TLB에 들어있기 때문에 Virtual Address 와 Physical Address 간의 변환이 즉각적으로 일어날 수 있다는 뜻이다.

 

TLB Miss가 발생하는 경우, 페이지 테이블로가서 페이지 데이터를 얻어와야 한다.

이때 발생할 수 있는 상황에 따라 TLB Miss는 2가지로 분류할 수 있다.

 

1. 단순한 TLB Miss

만약 요청한 페이지가 메인메모리에 로드되어 있다면, (페이지 테이블에 페이지 데이터가 들어있는 경우)

PTE 를 가져와서 TLB에 저장하면 되므로, 캐시 미스를 담당하듯 하드웨어 설계만으로도 해결할 수 있고, 소프트웨어적으로 처리할 수도 있다.

이때도 메모리에는 1번만 접근하므로 그렇게 큰 페널티는 아니다.

이때는 10~100 사이클 내의 페널티로 해결 가능하며, 이 페널티 시간은 페이지 테이블에서 PTE 일부를 TLB에 로딩하는 시간이다.

 

참고로 페이지테이블은 캐시가 아니다.

페이지  테이블은 해당 프로그램이 원하는 translation 정보를 '모두' 갖고 있는 매핑 정보이다.

메모리에 대한 것도, swap space에 대한 것도 모두 갖고 있다.

 

메모리에 저장된 '실제 페이지 데이터' 는 secondary storage에 대한 캐시로서 볼 수 있을지 몰라도, 페이지 테이블은 그냥 VA에서 PA로 바꿔주는 매핑 테이블일 뿐이므로 '캐시' 로 볼 수 없다.

 

2. Page Fault

TLB Miss가 발생해서 페이지 테이블에 가봤더니, 페이지 테이블에서도 이 페이지는 메모리에 없으니 Swap Space로 가야한다고 말하는 경우이다.

이때는 조금 복잡해서 운영체제가 처리한다. 따라서 제어권을 프로세스로부터 운영체제로 넘겨받는다.

 

우선 VA를 갖고 페이지 엔트리로 가면, 거기에는 Swap Space 시작 주소를 매핑하고 있다.

그러면 운영체제 입장에서는 어떤 디스크 안에 있는 어떤 페이지를 메인 메모리로 옮겨야 하는지까지 파악한 상태이다.

 

이때 만약 메인메모리가 유효한 페이지들로 가득 차있다면, 어떤 페이지 일부를 방출해야 한다.

어떻게든 방출하는 페이지를 결정했다면, 방출하는 페이지가 write-back 방식을 채택해서 dirty bit 가 1로 설정되어 있는 겨우 하드디스크에 동기화하기 위해 쓰는 작업을 먼저 해야 한다.

그리고 하드디스크에 쓰기가 완료되면 해당 페이지를 방출하고 새로운 swap sapce의 페이지로 채운다.

이 과정까지 하고나면 운영체제가 다시 제어권을 페이지 fault 가 일어났던 그 instruction(프로세스)에게 넘겨준다.

 

이렇게 Swap Space에 가서 페이지를 메모리로 올린 뒤, 메모리에서 페이지 테이블을 업데이트하고, 페이지 테이블 정보를 TLB로 업데이트하는 과정은 시간이 꽤 많이 걸린다. 하드디스크나 플래스는 DRAM 기반의 메모리보다 엄청나게 느리기 때문이다.

그래서 이 경우에는 기능상 문제는 없지만 성능상 페널티가 꽤 크다.

 

이 두가지 상황 중에서는 TLB Miss가 훨씬 더 자주 발생한다.

메인 메모리의 크기가 크니 우선 어지간하면 TLB Miss 가 발생해서 메모리에 갔을 때, 메모리는 GB 단위로 엄청 큰데, 페이지 하나의 크기는 4KB로 상대적으로 매우 작아서 엄청 많은 페이지를 저장할 수 있다.

따라서 확률적으로 CPU가 요청한 페이지는 메모리에 이미 담겨있을 확률이 높고, page fault는 흔하지 않다고 생각할 수 있다. 그래서 프로그램을 빠르게 동작시킬 수 있는 것이다.

 

실제로 컴퓨터를 살 때는 DRAM 메모리가 큰 걸 사는 것이 성능 향상을 크게 체감할 수 있는 방법이다.

 

Example

 

컴퓨터가 위 그림과 같은 구조로 되어있다고 생각해보자.

프로세서 내에는 Write-back 정책을 사용하는 캐시가 들어있다.

 

CPU가 어떤 프로그램의 lw 와 같은 명령어를 실행할 때는 VA 로 요청을 하고, TLB를 거치면 이 주소가 PA로 변환이 되어 캐시를 확인하고 캐시 미스인 경우 메모리까지 확인하는 과정을 거칠 수 있다.

하드디스크 관점에서 하드디스크는 어떤 프로그램의 모든 명령어와 데이터를 갖고있다.

만약 이 프로그램을 실행하면, 이 데이터들을 전체 또는 일부를 메모리로 올린다.

이때 메모리에 올릴 때는 페이지 단위로 올린다.

하드디스크에 저장되어 있는 프로그램 중에, 내가 실행하려고 하는 것만 메인 메모리에 페이지 단위로 넣었는데, CPU 입장에서는 메인 메모리의 데이터 일부를 캐시에 넣을 수 있으므로 메인 메모리의 명령어와 데이터 일부가 또 캐시로 올라간다. 이때는 캐시 블록 단위로 올라간다.

 

 

이 상황에서 CPU 가 어떤 데이터를 쓰는 행위른 한다면, write-back 정책을 사용하고 있을 때 cache에만 데이터를 쓰고 나중에 해당 블록이 교체될 때 실제 메모리의 데이터도 바뀐다.

그런데 이때 하드디스크는 새로운 데이터를 써야하는지 모른다.

그래서 하드디스크에도 페이지 단위로 업데이트할 수 있도록 더티비트 같은 세팅이 필요하다.

 

즉, 메인 메모리는 수많은 페이지로 이루어져있는데, 이 중에 어떤 페이지가 더티하고 더티하지 않은지 관리되어야 하고, 많약 더티한 페이지를 방출한다면 어떤 페이지를 방출 할 지 결정할 수 있어야 한다.

(replacement policy)

---

TLB 테이블 구조 개선

위 내용을 통해 TLB는 어떤 페이지가 업데이트 되었는지를 확인할 필요가 있다.

따라서 page table과 TLB 둘 모두에 더티비트를 추가한다.

TLB에 있는 entry가 방출될 때는, TLB의 해당 엔트리가 가리키는 page table 도 같이 업데이트된다.

 

page table이 갖고 있는 dirty bit는 메인 메모리 상에서 해당 페이지가 방출될 때, 하드디스크를 같이 업데이트할 것인지 결정하는 용도로 사용된다.

 

dirty bit 말고도, 방출될 수 있는 여러개의 엔트리가 있을 때, 어떤 엔트리를 방출할 지 결정하는 용도로 use bit (또는 reference bit) 가 필요하다.

(TLB에서는 n-way associative 방식일 때만 사용될 것 같다.)

보통은 간단하게 설계하기 위해 1bit 정보만 갖고 있으며, 이 페이지에 접근한적이 있으면 1, 없으면 0으로 세팅된다.

 

 

이제 TLB와 페이지 테이블을 같이 살펴보면 위와 같은 구조가 된다.

어떤 Virtual page number 가 추출되면, page table 에서는 이 번호로 직접 접근해서 physical page number 또는 disk address를 알아내고, TLB에서는 TLB의 인덱스 수만큼 하위 비트를 체크해서 적절한 인덱스에 접근한 뒤, 남은 비트를 tag와 비교해서 hit, miss 여부를 결정할 것이다.

 

따라서 page table 에는 tag 정보가 없고, TLB에는 tag 정보가 있다.

page 테이블은 모든 virtual page number에 대한 physical page 매핑 정보를 갖고 있고,

TLB는 페이지 테이블에 대한 일종의 캐시이기 때문에 일부 정보만 담겨 있어서 tag 정보가 추가로 필요하다.

 

page table의 valid 비트는 1이면 physical memory 를 가리키고, 0이면 disk (swap space) 를 가리키고 있는 것으로 해석할 수 있다.

반면 TLB의 경우, valid 비트가 말 그대로 유효한 엔트리인지 아닌지를 판별하는 역할로 쓰인다.

 

page table의 dirty bit 가 1이라는 뜻은 해당 페이지가 CPU에 의해 한번이라도 쓰여진적이 있다는 것을 의미한다.

TLB도 마찬가지 의미를 가진다.

(근데 이게 TLB에서 의미가 있는 bit 일까? TLB에서 캐싱이 되어있다는 것은 Page Table에서 읽은 적이 있다는 것이고, 그 뜻은 Disk 에서 메모리로 불러온적이 있다는 뜻이니까 TLB의 physical page address 는 항상 메모리 주소를 가리킬 것이고, 그러면 page fault 가 발생할 일이 없으니까 메모리의 내용을 디스크에 쓸 일이 없으니 dirty bit가 필요 없는 것이 아닌가??)

 

page table의 ref 비트는 replacement policy를 도와주기 위해, 최근 접근한 적이 있는지 여부를 알려주는 비트이다.

그렇다면 나중에 시간이 점점 지나면 지날 수록 ref 비트가 1이 되는 엔트리가 늘어날 것이다.

ref 비트는 0 → 1 만 되고, 그 반대는 되지 않기 때문이다.

결국 모든 비트가 1을 갖게되면 이때는 replacement policy를 구분할 수 없게 된다.

따라서 어떤 구간에서는 운영체제는 주기적으로 모든 ref bit를 0으로 초기화해준다.

이때 이후에도 또 접근했다면 그때 다시 1로 세팅하는 과정을 반복한다.

 

TLB와 캐시 사이 상호작용

하드웨어적으로는 TLB도 캐시이고, '캐시'도 캐시이다.

TLB도 캐시이기 때문에 direct mapped 구조로 설계할 수도, fully-associative 구조로 설계할 수도, 그 중간으로 설계할 수도 있다.

 

위 그림과 같은 구조에서는 virtual page number 하나를 모든 엔트리와 한번에 비교하고 있으므로 fully-associative 방식으로 설계된 TLB라는 것을 알 수 있다.

(인덱스가 없는 것도 그 힌트이다.)

만약 세번째 entry 가 TLB hit 였다면, 캐시된 physical page number 와 page offset을 합쳐서 물리 주소를 계산해낼 것이다.

 

이 예제는 가상 주소와 물리 주소 모두 32bit, 즉 4GB인 상황을 나타낸 예시이다.

 

 

이렇게 계산한 물리주소로 실제 데이터를 갖고오기 위해서, 이제 캐시에 접근해야 한다.

캐시에 접근할 때는 byte offset 을 제거하고, word offset 을 제거한 나머지로 block address를 계산하고,

block address 에서 캐시 블록의 개수 (셋의 개수) 를 나타내는 범위만큼하위 bit를 보고 엔트리를 찾은 뒤, 나머지 상위bit 를 tag로 보고 비교해서 cache hit 여부를 찾을 것이다.

 

만약 캐시 hit 가 발생하면, 해당 캐시가 담고있는 block 에서 적절한 word를 word offset을 통해 가져올 것이다.

 

이렇게 물리주소로부터 태그 정보를 받아들이고, 물리주소로부터 index 정보를 받아들이는 캐시를 PIPT (Physically-Indexed and Physically-Tagged cache) 라고 부른다.

이게 가장 기본적인 캐시의 구조이다.

 

하지만 이 기본 구조에도 여전히 한계는 존재한다.

캐시히트가 일어났을 때, TLB 접근한번, 캐시 접근한번 이렇게 2번의 접근을 필요로 하기 때문이다.

(비록 메모리를 2번 접근하는 것 까지는 아니지만)

 

따라서 이것보다 조금 더 빠르게 구동시키려는 욕심으로 등장한 구조로 VIPT 캐시도 있다.

Virtually-Indexed and Physically-Tagged 캐시라는 뜻이다.

그러면 인덱싱을 조금 더 빠르게 할 수 있다는 장점이 생긴다.

TLB를 거치지 않고 인덱싱을 할 수 있기 때문이다.

하지만 이런 그주도 또 험난한 과정이 있다.

PIPT는 단순하고, VIPT는 이 구조에서 갖고 있는 별도의 문제들이 있어서 복잡해진다.

 

이 그림에서는 tag 옆에 데이터가 별도로 떨어져있는데, 만약 하나의 캐시가 여러개 word를 block로 가지는 경우, 캐시 인덱스와 block offset을 합쳐서 특정 word 데이터를 가져오는 것을 나눠서 그린 것이다.

(그동안은 mux로 특정 워드를 가져오는 것으로 표현했는데, 이 그림은 그걸 다르게 표현한 것이다.)