TLB(Translation-Lookaside Buffer)

/*

본 내용은 학교 수업내용을 바탕으로 하고 OSTEP(Operating Systems: Three Easy Pieces) 교재를 참고하여 정리한 내용입니다.

*/

 

 

페이징은 프로세스의 주소공간을 고정된 크기로 나누고 각 페이지의 실제 위치와 매핑해주는 것이며 이때 필요한 정보들을 메모리에 있는 페이지테이블이라는 자료구조에 저장하게 된다. 이 페이지테이블에 매핑정보들을 저장하기 위해서는 큰 메모리 공간이 요구되기 때문에 페이지테이블에 접근하는 것은 큰 오버헤드를 유발한다. 그렇기 때문에 운영체제의 속도를 개선하기 위해서는 TLB(Translation-Lookaside Buffer), 변환-색인 버퍼라는것의 도움이 필요하다,

 

cf) MMU(Memory Management Unit)은 CPU가 메모리에 접근하는 것을 관리하는 하드웨어 부품이며 가상메모리주소를 실제물리주소로 변환할 때 TLB(Translation-Lookaside Buffer)를 참조하게 된다. 

 

가상주소변환이 이루어지는 과정을 보도록 하자.

1   VPN = (VirtualAddress & VPN_MASK) >> SHIFT
2   (Success, TlbEntry) = TLB_Lookup(VPN)
3   if (Success == True) // TLB HIT!
4     if (CanAccess(TlbEntry.ProtectBits) == True)
5       Offset = VirtualAddress & OFFSET_MASK
6       PhysAddr = (TlbEntry.PFN << SHIFT) | Offset
7       AccessMemory(PhysAddr)
8     else
9       RaiseException(PROTECTION_FAULT)
10  else  // TLB MISS;
11    PTEAddr = PTBR + (VPN * sizeof(PTE))
12    PTE = AccessMemory(PTEAddr)
13    if (PTE.Valid == False)
14      RaiseException(SEGMENTATION_FAULT)
15    else if(CanAccess(PTE.ProtectBits == False))
16      RaiseException(PROTECTION_FAULT)
17    else
18      TLB_Insert(VPN, PTE.PFN, PTE.ProtectBits)
19      RetryInstruction() 

 

가상메모리주소에서 VPN을 추출한다 (라인 #1)

VPN의 TLB여부를 검사(라인 #2)

VPN이 TLB에 있다면 TLB HIT이다. (라인 #3)

해당 페이지에 대한 접근 권한 검사까지 성공하면 (라인 #4) 그 정보와 가상주소의 offset을 합쳐서 원하는 물리메모리주소를 얻을 수 있다.

 

만약 VPN이 TLB에 없다면 TLB MISS이다. (라인 #10)

TLB miss가 되면 하드웨어가 페이지테이블에 접근하여 변환정보를 가져오고(라인 #11 - #12)

가상메모리가 유효하고 접근권한검사까지 성공해야 (라인 #13 - #15) 해당 변환 정보를 TLB로 읽어온다.(라인 #18)

TLB가 갱신되면 명령어를 재실행하게 되며 이 때는 메모리참조가 빠르게 발생한다.

 

위의 예제를 통해 TLB미스가 날 경우 많은시간과 오버헤드가 발생하게 되는 것을 알 수 있다. 그러므로 TLB미스를 최소한으로 줄이는 것이 중요하다.

 

 

아래의 예를 하나 더 보도록 하자.

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

메모리공간 내의 배열

가상주소 100번지부터 10개의 4바이트 정수배열이 존재하며 가상주소 공간은 8비트이며 페이지 크기는 16바이트이다.

2의 8제곱(주소공간크기) / 2의4제곱(페이지크기) = 16개의 페이지.(가상주소는 4비트의 VPN과 4비트의 offset으로 구성되어 있다.)

 

배열의 첫 요소a[0]는 VPN=06, offset=04에서 시작한다. 06번 페이지에는 총 세 개의 4바이트 정수가(a[0], a[1]. a[2]) 들어갈 수 있고 그 다음 요소는 07번 페이지로 들어가게 된다. 07번 페이지에는 총 4개의 4바이트 정수가 들어갈 수 있다(a[3] ~ a[6]).

그리고 08번 페이지에는 총 3개의 4바이트 정수가 들어갈 수 있다(a[7] ~ a[9]). 

 

위의 그림을 통해 각 페이지의 첫번째 정수를 읽을 때만 TLB MISS가 발생하고 나머지 정수를 읽을 때는 TLB HIT이 발생하고 10개의 4바이트 정수 중에서 7개의 4바이트 정수가 HIT 됐으므로 70%의 히트율을 보인다.

 

히트율을 높이기 위해서는 페이지의 크기를 키우거나 배열의 타입을 short로 줄이면 된다.

페이지의 크기를 키운다면 한 페이지에 더 많은 4바이트 정수가 들어갈 수 있기 때문에 더 빈번하게 TLB HIT가 발생할 것이고 배열의 타입을 short로 줄인다면 2바이트 배열정수가 페이지에 들어가기 때문에 같은 페이지의 크기 대비 더 많은 요소가 들어갈 수 있게 된다.

 

배열의 요소들이 페이지내에 인접해 있기 때문에 공간지역성으로 인해 성능을 개선할 수가 있다. 그리고  위의 코드에서 for loop가 종료된 후에도 배열을 그대로 사용한다면 모든 주소변환정보가 TLB에 담겨 있기 때문에 시간지역성으로 인해 TLB히트율은 높아질 것이다.