Translation Lookaside Buffers - TLB란?

TLB란?

Address Translation 과정에서 VPN을 PFN으로 변환하려면 Page Table에 접근하여야 한다.

이 과정을 더 빠르게 하기 위해 자주 쓰이는 Translation들을 Memory Management Unit(MMU)에 저장하여 사용하는데

이렇게 저장한 Cache를 TLB라 한다.

 

 

TLB 기본 알고리즘

1. Translation 요청이 들어오면 주소값에서 VPN을 추출한다.

2. 해당하는 Translation이 TLB에 있는 지 확인한다.

3-1. TLB에 있다면 VPN을 PFN으로 변환하여 반환한다. (TLB Hit)

3-2. TLB에 없다면 Page Table에 접근하여 PFN으로 변환하여 반환한다. (TLB Miss)

      그 후 해당 Translation을 TLB에 업데이트한다.

 

 

TLB가 왜 효율적인가?

이와 같이 10개의 int를 저장하는 배열이 있다고 할 때

위와 같은 코드를 실행한다고 하면 총 10번의 Translation이 발생한다.

하지만 이 때 a[0] a[3] a[7] 에서는 TLB Miss가 발생하여 Page Table에서 변환해야 하지만

나머지 7번의 접근, 즉 전체 Translation 중 70%에서는 TLB Hit가 발생하여 시간 절약이 가능하다.

이는 배열이 연속된 주소공간에 있기 때문에 가능한데 이를 Spatial Locality라 한다.

 

※ Spatial Locality : 프로그램이 메모리 x에 접근했다면, 다음번에는 x 근처의 메모리에 접근할 가능성이 높다.

※ Temporal Locality : 프로그램이 접근했던 메모리는 가까운 시간 내에 다시 접근할 가능성이 높다.

 

 

TLB의 구성

TLB의 Entry는 PTE와 비슷하지만 VPN이 index 역할을 할 수 없기 때문에 VPN이 같이 저장되어야 한다.

그리고 뒤쪽에는 PTE처럼 valid, protection bit와 같은 flag들이 저장된다.

 

※ TLB는 용량이 작기 때문에 여러 프로세스가 나누어 사용해야 하므로 Context Switch가 발생하면 기존에 남아있는 TLB Entry들 때문에 다른 프로세스가 엉뚱한 메모리로 접근하는 것을 막을 방법이 필요하다.

-> 이를 막기 위해서 Context Switch 시마다 TLB를 비우면 되지만 이는 매우 비효율적인 방법이다.

따라서 위와 같이 Address Space Identifier(ASID) 값을 추가하여 어떤 프로세스가 사용하는 Entry인지를 저장한다.

 

 

TLB 관리 정책

앞에서 계속 말했듯이 TLB는 용량이 부족한데 이 때문에 모든 Translation을 저장할 수 없다.

따라서 우리는 TLB가 꽉 차있을 때 새로운 Translation이 업데이트될 때 어떤 Entry를 삭제할 지 정해야 한다.

이 때 사용된지 가장 오래된(Least Recently Used) Entry를 삭제하는 것이 가장 합리적이다.

따라서 위의 Reference Row와 같이 요청될 때 가장 사용된 지 오래된 Entry를 삭제하면 총 11번에 TLB Miss가 발생한다.