본 글의 내용은 Operating Systems: Three Easy Pieces의 Paging: Faster Translations (TLBs) 챕터를 정리한 것입니다.

☑️ 개요

• 페이징은 주소 공간을 고정된 크기로 쪼개기 때문에, 많은 맵핑 정보가 필요하다.

• 이런 맵핑 정보를 저장하는 것이 페이지 테이블이며, 페이지 테이블은 메모리에 저장된다.

• 그래서 메모리 조회를 매번 하다보면 속도가 엄청나게 느려지는 게 페이징의 문제라고 할 수 있다.

• 그리고 주소 변환 속도를 높이기 위해서는 하드웨어의 도움이 필요한 경우가 많은데, 여기서 Translation Lookaside Buffer, 즉 TLB가 추가된다. 이것은 하드웨어 캐시에 불과해서 주소 변환 캐시라고 부르는 게 더 적절하기도 하다.

• TLB가 존재한다면 메모리를 참조하기 이전에 TLB에 주소 번역이 존재하는지 부터 확인하고, 작업을 진행한다.

☑️ TLB의 기본 알고리즘

• 가상 주소에서 VPN을 추출하고, 이 VPN에 대한 주소 번역을 TLB가 가지고 있는지 확인한다.

• 존재한다면 TLB가 주소 번역을 보유하는 것이며, TLB 히트가 발생했다고 할 수 있다.

• 찾지 못하면 TLB 미스라고 말할 수 있으며, 이때는 페이지 테이블에 접근하여 주소 번역을 찾고, TLB를 업데이트한다. 업데이트 된 후에 다시 하드웨어 명령을 시도하는데, 다시 시도했을 때는 TLB가 업데이트 되었기 때문에 TLB 히트가 발생한다.

• TLB를 사용하는 이유는 주소 번역이 캐시에서 발견될 것이라는 전제가 있기 때문이다. TLB 미스가 발생하면 추가 메모리 참조가 발생해 비용이 커지기 때문에, 가능한 TLB 미스를 피하는 것이 목표가 된다.

☑️ 예시: 배열 접근

• 위 그림은 페이지 16개와, 그 안에 배치된 배열이다. 배열의 첫번째 항목인 a[0] 은 VPN=06, Offset=04 에서 시작되며, 해당 페이지에는 4바이트 정수 3개만 삽입되었다. 배열의 나머지 원소들은 페이지에 이어서 삽입되었다.

• 위 코드의 주소 변환 과정을 생각해보자. a[0] 의 가상 주소를 통해 VPN을 추출하여, TLB에 주소 변환이 있는지 확인한다. 만약 배열에 처음 접근하는 상황이라면 TLB 미스가 발생할 것이다.

• 이어서 a[1] 에 접근하면 a[0] 과 같은 페이지에 존재하므로 TLB 히트가 발생한다. a[2] 도 마찬가지이다.

• 이제 a[3] 에 접근하면 다른 페이지에 있으므로 TLB 미스가 발생하고, TLB 업데이트 이후에 a[4] … a[6] 까지의 접근은 모두 TLB 히트가 발생한다.

• TLB는 이렇듯 spatial locality(공간 지역성)으로 성능을 향상시킨다. 페이지의 요소에 처음 액세스하는 경우에만 TLB 미스가 발생한다.

• 여기서 페이지의 크기가 더 컸다면 (16바이트 대신 32바이트 였다면) 훨씬 더 적은 TLB 미스를 겪게 된다. 일반적으로 페이지 크기는 4KB 정도로 설정한다.

• 만약 캐시 크기가 적당히 클 때, 위에서 예시로 든 반복문을 다시 한번 접근하면 모두 다 TLB 히트가 발생할 것이다. 이런 경우를 temporal locality(시간 지역성)이라고 하며, 시간 내에 메모리를 재참조할 때 TLB 적중률은 높아진다.

💡지역성

캐시의 기본 개념은 데이터를 참조할 때 지역성을 활용하는 것이다. 지역성에는 시간 지역성과 공간 지역성 두 가지 유형이 있다. 시간 지역성의 경우, 최근에 접근한 명령어 혹은 데이터가 곧 다시 접근될 가능성이 높다는 개념이다. (예시로 반복문이 있다) 공간 지역성은 주소 x에 접근하면 곧 x 근처의 메모리에 접근할 가능성이 높다는 것이다. (예시로 배열이 있다)
캐시는 명령어, 데이터, 주소 변환을 위해 작고 빠른 온칩 메모리에 복사본을 보관하여 지역성을 활용한다. 느린 메모리 대신 먼저 캐시에 복사본이 있는지 확인하고, 있다면 빠르게 접근하여 메모리 접근에 시간을 낭비할 필요가 없다.

☑️ TLB 미스는 누가 처리하는가?

• TLB 미스는 하드웨어 혹은 소프트웨어가 처리할 수 있다.

• CISC 아키텍처 같은 경우는 OS를 신뢰하지 않고 하드웨어가 TLB 미스를 전적으로 처리하게 하였다.

• 이를 위해 하드웨어가 페이지 테이블의 위치를 알아야 했다. (페이지 테이블 베이스 레지스터를 통해) x86 아키텍처 같은 경우는 다단계 페이지 테이블을 이용한다.

• RISC 아키텍처 같은 경우는 소프트웨어 관리형 TLB를 사용한다.

• TLB 미스가 발생하면 예외를 발생시켜 Kernel mode로 전환하여 trap handler로 이동한다. trap handler가 TLB 미스를 처리하고 다시 돌아와 명령어를 재시작한다.

💡 TLB 유효 비트 ≠ 페이지 테이블의 유효 비트

페이지 테이블에서 PTE가 유효하지 않으면 아직 물리 페이지가 할당되지 않았고, 프로그램에서 접근하면 안 된다는 의미이다. 반면 TLB 유효 비트는 단순히 TLB 항목에 변환이 유효한지에 대한 여부를 나타낸다. 예시로 시스템이 부팅되면, TLB 항목의 초기 상태는 유효하지 않음이다. 아직 주소 변환이 캐싱된 적이 없기 때문에 당연하다. 프로그램이 실행되며 가상 주소 공간에 접근하기 시작하면 TLB에 유효한 항목이 서서히 생겨난다. TLB 유효 비트는 컨텍스트 스위칭에서 유용하게 사용되는데, 모든 TLB 유효 비트를 유효하지 않음으로 설정하면 이전 프로세스의 주소 변환을 실수로 사용하지 않을 수 있다.

☑️ TLB에는 무엇이 들어있는가?

• 일반적인 TLB는 32, 64, 128개의 항목이 존재가능하며, fully-associative하다. (캐시 어느 곳에나 맵핑될 수 있는 구조) 그래서 하드웨어가 TLB를 병렬로 검색하며 원하는 번역을 찾을 수 있다.

• 각 항목은 대략적으로 아래와 같은 형태이다.

• TLB 항목에는 VPN, PFN 뿐만 아니라 여러 비트가 존재하는데, 유효한 주소 번역이 있는지 여부를 나타내는 유효 비트, 접근 가능한 방법을 결정하는 보호 비트, 더티 비트 등 여러 필드가 존재한다.

☑️ TLB 이슈: 컨텍스트 스위칭

• TLB에는 현재 실행 중인 프로세스에만 유효한 주소 변환이 포함되어 있어, 다른 프로세스에게는 무의미하다.

• 그래서 현재 프로세스가 이전 프로세스의 주소 변환을 사용하지 않도록 조심해야 한다.

• 이것을 해결하기 위한 방법은 컨텍스트 스위칭이 발생했을 때 TLB를 비우는 것이다. OS가 페이지 테이블 베이스 레지스터를 변경할 때 TLB 플러시를 실행한다.

• 그러나 이 접근은 프로세스가 바뀔 때마다 TLB 미스가 발생한다는 문제가 있다. 그래서 TLB에 주소 공간 식별자(ASID) 필드를 제공하여, 프로세스끼리 TLB를 공유하며 자신만의 주소 번역에 접근할 수 있다. 물론 이 작업을 위해 일부 레지스터를 현재 프로세스의 ASID로 설정한다.

• 여담으로 TLB의 두 항목이 동일한 PFN을 가지는 경우도 있다. 이 경우는 보통 코드 영역을 공유하는 것으로, 물리 페이지를 공유함으로써 공간을 효율적으로 사용한다.

☑️ TLB 이슈: 교체 정책

• 또 하나 고려해야 할 것은 캐시 교체이다. 새 항목이 기록될 때 기존의 어떤 항목을 교체해야 할까?

• 일반적인 접근 방식은 최근에 가장 적게 사용된 항목(LRU)를 퇴출하는 것이다.

• 또 다른 방식은 무작위로 퇴출하는 랜덤 정책이 있다. 이것은 특정 케이스에서 LRU보다 훨씬 효과적인데, 예시로 TLB의 크기가 n인데, n+1개의 페이지를 반복 접근하면 LRU는 불합리하게 동작하게 된다. 이런 것을 랜덤 정책이 해결할 수 있다.

☑️ TLB 항목(Entry)

• MIPS 아키텍처의 TLB는 다음과 같다.
  

• MIPS TLB에는 전역적으로 공유되는 페이지를 구분하는 글로벌 비트 또한 존재한다. 글로벌 비트가 설정되면 ASID를 무시하고 사용된다.

• MIPS는 소프트웨어로 TLB를 관리하기 때문에, 관리를 위한 4가지 Instruction이 존재한다. 주소 변환이 존재하는지 확인하는 TLBP , 항목을 레지스터로 로드하는 TLBR , 항목을 재배치하는 TLBWI , 항목을 교체하는 TLBWR 이다. 물론 이 명령어를 사용하려면 권한이 있어야 한다.

✅ 요약

• 메모리의 페이지 테이블 대신 TLB, 주소 변환 캐시를 통해 접근되는 것으로 주소 변환을 빠르게 처리한다.

• 이것은 흡사 메모리 가상화가 되지 않은 것과 비슷한 성능을 내며, 필수적으로 사용할 수 밖에 없다.

• 그러나 단기간에 접근하는 페이지 수가 TLB의 한계를 초과하면 속도가 상당히 느려질 수 있다. 이것을 TLB 커버리지 초과라고 한다.

• 이것을 해결하기 위해 더 큰 페이지 크기를 지원하고자 하는데, 보통 DBMS와 같은 프로그램에서 종종 활용한다.

• TLB에 주소 변환이 캐싱되어 있을 때 접근하면 TLB 히트, 없을 때 접근하면 TLB 미스가 발생한다. TLB 미스를 줄이는 것이 최우선 목표이다.

• TLB가 꽉차면 LRU, 랜덤 등의 정책으로 항목을 교체한다.