TLB : Translation Lookaside Buffers

페이지을 사용하면 성능 오버헤드가 발생할 수 있다. 주소 공간을 작은 고정 크기 단위로 나누는 것은 많은 매핑 정보가 필요하다. 이를 저장하기 위한 공간이 많이 필요하고 참조하기 위한 시간도 필요하다. 우리는 페이징의 성능을 높이기 위해 하드웨어의 도움을 받는다.

MMU의 일부인 TLB(translation-lookaside buffer)는 주소 변환 캐시(address-translation cache)로 작동한다. TLB 원하는 변환이 있는지 확인하여 참조할 필요 없이 TLB를 통해 변환을 한다.

TLB Basic Algorithm

배열 페이지 테이블과 TLB를 사용한 가상 주소 변환을 살펴보자
TLB에 변환 정보가 있다면 테이블 엑세스없이 변환할 수 있고 아니라면 참조를 해야한다.
처음 참조하는 것은 TLB에 정보가 없지만 변환 후 TLB에 저장하므로 다음 참조는 없앨 수 있다.
처음 참조하는 것은 테이블 엑세스를 해야하므로 TLB에 변환 정보가 없는 상황을 줄이는 것이 중요하다.

//가상주소에서 VPN 얻기
 VPN = (VirtualAddress & VPN_MASK) >> SHIFT 
//TLB가 VPN변환을 보유하는지 확인
 (Success, TlbEntry) = TLB_Lookup(VPN) 
 
// TLB가 변환을 보유한다면,(TLB Hit)
if (Success == True) 
	//해당 TLB 항목에서 물리적 주소(PA)형성
	if (CanAccess(TlbEntry.ProtectBits) == True)
		Offset = VirtualAddress & OFFSET_MASK
		PhysAddr = (TlbEntry.PFN << SHIFT) | Offset
		Register = AccessMemory(PhysAddr)
	else
		RaiseException(PROTECTION_FAULT)
// TLB에서 변환을 찾지 못했다면,(TLB Miss)
else 
	//페이지 테이블 엑세스
	PTEAddr = PTBR + (VPN * sizeof(PTE))
	PTE = AccessMemory(PTEAddr)
    //PTE에 접근 권한 없다면 오류
	if (PTE.Valid == False)
		RaiseException(SEGMENTATION_FAULT)
    //PTE에 보안 비트 확인 후 오류
	else if (CanAccess(PTE.ProtectBits) == False)
		RaiseException(PROTECTION_FAULT)
    //정상 작동이 일 때, TLB에 변환 정보 저장
	else
		TLB_Insert(VPN, PTE.PFN, PTE.ProtectBits)
		RetryInstruction()

Example: Accessing An Array

예시를 통해 TLB의 작동을 명확하게 이해해보자
메모리에 가상 주소 100부터 시작하는 10개의 4바이트 정수 배열이 있다고 가정하자
가상 주소 공간이 8비트인데 16바이트 페이지가 있으므로 가상 주소는 4비트 VPN과 4비트 offset으로 나뉜다. 가상페이지는 16개, 각 페이지는 16바이트

첫 번째 항목인 a[0]은 VPN=06, offset=04 에서 시작한다. VPN=07 에는 a[3]~a[6] 이 있고, VPN=08 에는 a[7]~a[9]가 있다.

각 배열 요소에 엑세스 하는 코드가 있다.

int i, sum = 0;
for (i = 0; i < 10; i++) {
    sum += a[i];
}

a[0]에 엑세스할 때 CPU는 가상주소 100에 대한 load를 볼 것이다. 하드웨어는 VPN=06을 추출하고 TLB를 확인한다.(TLB miss)
다음, a[1]에 엑세스할 때는 TLB hit가 된다. a[0] 과 같은 페이지에 있기 때문에 TLB에 저장되어있었던 것이다. a[3]에서 다시 TLB miss가 나며 a[4]~a[6]은 TLB hit가 된다.
10번의 엑세스에서 3번의 miss 와 7번의 hit가 생긴다. TLB hit rate는 70%인 것이다. 페이지의 첫 번째 요소에서만 miss가 일어나므로 페이지가 커지면 100%에 가까워질 것이다.

TLB 또한 하나의 캐시(cache)로써 공간, 시간 지역성(spatial, temporal locality)으로 인해 TLB hit rate 를 높일 수 있다.

공간 지역성은 한 번 엑세스한 주변의 요소에 접근할 가능성이 크다는 개념이다. a[0]에 접근 한 후 a[1]과 a[2]에서 hit가 된 것이 같은 페이지에 있었기에 그 페이지에 있는 것들은 hit 가 된 것이다.

시간 지역성은 한 번 엑세스한 것에 다시 엑세스할 가능성이 크다는 개념이다. loop가 한 번 더 돈다면, miss가 되었던 요소들도 TLB에 저장되었기에 hit가 된다.

모든 요소를 TLB에 저장한다면 모두 hit가 되겠지만, TLB는 캐시이다.
캐시는 크기가 작기 때문에 빠른 것이다. 크기를 늘린다면 느려질 것이고, 존재하는 캐시를 잘 활용하는 것이 중요하다.

Who Handles The TLB Miss?

TLB miss는 하드웨어 또는 OS가 처리한다.

과거에는 하드웨어가 복잡한 명령어 세트를 사용했고, 전적으로 TLB miss를 처리했다. 이를 위해 하드웨어는 메모리에서 페이지 테이블의 위치를 정확히 알아야 했다. miss 발생시, 페이지 테이블을 탐색하고 변환하고 TLB를 업데이트했다. 예로는 Intel x86 아키텍처가 있다.

현대 아키텍처(RISC 등)는 소프트웨어(OS)로 관리되는 TLB를 가진다. TLB miss 발생시 하드웨어는 단순히 예외를 발생시킨다. 명령 스트림을 일시 중지시키고, 권한 수준을 커널 모드로 올리고 트랩 핸들러로 이동한다. 트랩 핸들러는 TLB miss를 처리하기 위한 OS내의 코드이다. 이 코드를 통해 TLB를 업데이트하고 트랩에서 반환한다.

TLB Contents: What’s In There?

하드웨어 TLB의 내용을 살펴보자 전형적인 TLB는 32,64 또는 128개의 엔트리(entries)를 가지며 전체 연관성(fully associative)이라고 한다. 이것은 변환 정보가 TLB의 어느 위치에나 있을 수 있으며 변환을 찾기 위해 TLB를 병렬로 검색한다는 것을 의미한다.TLB 엔트리는 다음과 같을 수 있다.

VPN과 PFN이 각 엔트리에 모두 포함되어 있다.
기타비트에는 valid bit, protection bit, address-space identifier, dirty bit 등이 있을 수 있다.

TLB Issue: Context Switches

TLB를 사용하면 context switching 에서 문제가 발생한다. TLB에는 현제 실행중인 프로세스에 대한 가상주소 변환 정보가 있다. 이 정보는 다른 프로세스에 대해서는 의미가 없다. 결과적으로 다른 프로세스로 전환할때 이전 프로세스의 변환 정보를 실수로 사용하지 않도록 주의해야 한다.
프로세스 P1과 P2가 TLB에 저장되어 있다면,

VPN 값이 같고 PFN 값이 다르다. 이럴때, 하드웨어는 어느 항목이 어느 프로세스에 속하는지 구별할 수 없다.
이 문제를 해결하기 위해 TLB를 컨텍스트 스위치할때 비울 수 있다. 잘못된 변환 정보를 만나는 일을 없지만, 새로운 프로세스에서 TLB 미스가 나며 비용이 발생한다. 컨텍스트 스위치가 자주 일어날 수록 이 비용도 높아질 것이다.

이런 오버헤드를 줄이기 위해 TLB를 공유할 수 있도록 하드웨어를 지원한다. TLB에 address space identifier (ASID) 를 지원해서 이를 해결 할 수 있다.

아래와 같이 PFN이 같을때는 코드를 공유하고 있다는 뜻이다. 이런 상황에서는 메모리 오버헤드를 줄이므로 유용하다.

Issue: Replacement Policy

새로운 항목을 TLB에 추가할 때 이전 항목을 교체해야한다. 이에대한 교체 정책을 어떻게 설정할지가 하나의 문제이다. 접근법중 하나는 최근에 사용되지 않은 항목을 교체하는 것이다. 이를 LRU(least-recently-used)라고 한다. 다른 접근법은 무작위로 교체하는 것이다. 무작위 정책은 때로 더 나은 성능을 보여준다.

A Real TLB Entry

실제 TLB를 살펴보자 이 예는 MIPS R4000 에서 가져왔다.
MIPS R4000는 4KB 페이지를 사용하는 32비트 주소 공간을 지원한다. 따라서 20비트의 VPN과 12비트의 offset이 있을것이다. 하지만 VPN은 19비트만 사용한다. 실제로 사용자 주소는 주소 공간의 절반만 사용하고 나머지는 커널에 예약되기 때문이다. VPN은 최대 24비트의 PFN으로 변환되며, 따라서 최대 64GB($2^{24}$개의 4KB 페이지)를 지원할 수 있다.

MIPS TLB에는 전역비트(global bit)(G) 를 볼 수 있다. 전역비트가 설정되면 ASID가 무시된다.하드웨어가 페이지를 캐시하는 방식을 결정하는 3개의 일관성(Coherence)(C) 비트를 볼 수 있으며 valid, dirty bit와 page mask field도 볼 수 있다. 64비트중 회색으로 표시된 사용되지 않는 부분도 있다.