14. Virtualization) Translation Lookaside Buffers

이전 글에서 Virtual memory를 효율적으로 다룰 수 있는 방법 중 하나인 Paging에 대해서 알아보았고,

Paging은 process마다 page table을 요구하기 때문에 큰 메모리를 차지한다는 것을 알 수 있었다.

 

"page table을 저장하기 위해 physical memory의 큰 부분을 차지한다"

이 말은 paging은 virtual address를 translate 할때마다 큰 메모리 look up 이 필요하다는 말과 같다.

어떻게 Address Translation을 빠르게 할 수 있을까?

이를 해결하기 위해서는 하드웨어와 OS(소프트웨어)의 지원이 필요하다.

하드웨어는 MMU(memory-management unit)에 TLB(translation-lookaside buffer)을 제공한다.

즉, 하드웨어가 제공하는 address-translation을 위한 캐시이다.

 

virtual address를 translate할때, 하드웨어는 TLB를 먼저 확인하고 vpn에 해당하는 pfn이 존재한다면, page table을 look up할 필요가 없는것이다.

러프한 TLB 원리를 위의 코드와 함께 알아보자.

Virtual address를 translate하는 과정은 다음과 같다.

1. virtual address에서 VPN을 추출한다.

2. TLB가 VPN을 hold하고 있는지 확인한다.

 

TLB가 VPN을 hold하고 있다면 (TLB hit)

3. TLB entry에서 PFN을 추출하여 physical address를 구한다.

 

TLB에 VPN이 없다면 (TLB miss)

3. 하드웨어는 page table에 접근하여 entry를 look up한다.

4. page table entry에서 PFN을 추출하여 physical address를 계산한다.

5. TLB에 조회한 VPN과 VPN에 해당하는 PFN을 추가한다.

 

TLB에 VPN이 있다면 오버 헤드가 발생하지 않을 것이고, TLB miss가 발생하면 PFN을 찾기 위해 page table에 접근해야 하므로 추가 

메모리 참조가 발생한다. 캐시에 비해 메모리를 접근하는것은 느리기 때문에 TLB miss는 paging에 높은 cost를 발생시킬 것이다.

 

TLB의 작동을  더 잘 이해하기 위해 위와 같은 코드를 실행한다고 하자.

8bit virtual address space를 제공한다고 한다면, 4bit의 VPN와 4bit의 offset으로 표현할 수 있을 것이고,

2^4 = 16개의 VPN이 있을 것이다. 배열의 시작 virtual address는 100이라 하자.

이러한 가정을 뒀을 때 배열은 virtual memory에 다음과 같이 저장되어 있을 것이다.

 

 

배열에 처음 접근할때, a[0]부터 조회를 시작할때, CPU는 virtual address 100을 load하려 할것이다. 하드웨어는 Virtual address 100, 즉 01100100에서 VPN 6을 추출하고 TLB를 look up할 것이다. TLB에는 아직 아무것도 저장되어 있지 않기 때문에 TLB miss가 발생하고 page table을 look up 한 후 TLB에 VPN 정보를 저장할것이다.

 

a[1]과 a[2]는 a[0]에 접근할 때 VPN 6에 해당하는 PFN을 TLB에 저장해두었기 때문에 TLB hit이 발생한다. 따라서 page table에 접근하지 않는다!

 

이를 반복하여, a[3]에서는 TLB miss가 발생하고 a[4], a[5], a[6]에서는 TLB hit이 발생한다. a[7]을 접근할때는 다시 TLB miss, a[8], a[9]에서는 TLB hit이 발생한다.

 

 

정리하면 miss, hit, hit, miss, hit, hit, hit, miss, hit, hit으로 TLB hit rate가 70%이다.

이런 방식으로 TLB는 성능 향상을 제공한다.

 

TLB의 성능 향샹은 Locality의 특성 이용한 것이다. Locality가 무엇일까?

Spatial locality

Spatial locality는 프로세스가 memory address x에 접근했다면, 그 다음에는 x 근처에 있는 memory에 접근할 가능성이 높다고 보는것이다. 위의 배열 순회 예시를 보면 spatial locality를 확인할 수 있다.

Temporal locality

Temporal locality는 최근에 접근한 데이터를 다시 접근할 확률이 높다는 것이다. 우리가 배열을 반복해서 순회하게 된다면 temporal locality를 활용할 수 있을 것이다.

누가 TLB miss를 handle할까?

과거에는 하드웨어가 복잡한 instruction (CISC)를 통해 관리했다. 하지만 오늘날에는 OS가 이를 관장한다.

하드웨어는 TLB miss가 발생했을때, exception을 발생시키고, 이를 handle할 privileged instruction을 실행하기 위해 kernel mode로 전환한 뒤 trap handler를 호출한다.

실행 과정을 본다면 page table을 통해 translation을 한 후 privileged instruction을 통해 TLB를 업데이트 하고, return from trap을 통해 실행하고자 했던 process의 instruction을 재개할 것이다.

 

이전에 process에 대해 다뤘을때 return-from-trap에 대해 얘기한적이 있다. 

하지만 엄밀히 따지면 여기서의 return-from-trap과 전에 다뤘던 return-from-trap에는 차이가 있다.

이전의 return-from-trap은 user mode로 전환한 뒤 실행했던 instruction 다음부터 재개하면 되지만

TLB miss에서의 return-from-trap은 trap을 발생시킨 instruction부터 다시 실행하여야 한다.

그렇기 때문에 하드웨어는 OS에 trap이 발생하였을때 다르게 PC를 저장해야한다.

TLB 의 문제 : Context Switches

잘 생각해보면 TLB는 process들이 context switch를 할 때 문제가 발생할 수 있다.

실행되고 있던 process를 p1, context switch 되어 새로 실행되는 process를 p2라고 하자.

p1의 VPN 10은 PFN 100에 있지만 p2의 VPN 10은 PFN 170에 있을 수 있다.

 

그렇다면 context switch가 발생할 때 TLB를 어떻게 관리해야 할까?

 

가장 간단한 방법은 context switch가 발생할때 TLB를 flush 하는  방법이다.

그러므로 다음 process가 실행할 때면 TLB가 비어있게 될것이다!

하지만 문제점도 있다 process switch를 할때마다 process는 TLB miss를 계속해서 마주치게 될것이다.

 

이런 오버헤드를 줄이기 위한 다른 방법은 TLB 필드에 Address Space Identifier(ASID)를 저장하는 것이다.

ASID를 PID라고 생각할 수는 있지만 PID보다는 bit수가 더 적다!

ASID를 활용하면 TLB는 process마다 TLB 엔트리를 구분할 수 있다!

 

위의 TLB 엔트리는 실제 TLB를 축소한 것이다. 그럼 실제 TLB Entry는 어떤 구조로 있을까?

 

MIPS의 TLB 엔트리는 위의 사진과 같다. 간단하게 몇종류의 bit에 대해 알아보자

(G) global bit

processes 사이에 공유할 수 있는 global한 page인지 나타내는 bit이다.

그러므로 G bit가 1이라면 ASID가 무시된다.

 

추가적으로, TLB는 Fully associative라고고 말한다. Fully associative라는것은 TLB의 어느 위치에라도 제약없이 저장될 수 있다는 말이다. 그렇기 때문에 하드웨어는 TLB를 서치할 때 parallel하게 탐색한다.