OSTEP 19 Translation Lookaside Buffer

앞서 본 것처럼 페이징은 상당한 성능 저하를 가져올 수 있다. 주소 변환 속도를 어떻게 향상할까?

하드웨어의 도움을 받아야 한다. 주소 변환을 빠르게 하기 위해서 우리는 변환 색인 버퍼 (Translation Lookaside Buffer, TLB) 라는 것을 도입한다. 칩의 메모리 관리 유닛 MMU의 일부이다. 자주 참조되는 가상 주소 -> 실제 주소 변환 정보를 저장하는 하드웨어 캐시이다. 주소 변환 캐시가 좀 더 정확한 명칭이라고 할 수 있다.

가상 메모리 참조 시, 하드웨어는 먼저 TLB에 원하는 변환 정보가 있는지 확인하고, 만약 있다면 페이지 테이블을 통하지 않고 캐시를 통해 빠르게 주소를 변환한다.

1. TLB의 기본 알고리즘

먼저 가상 주소에서 가상 페이지 번호를 추출하고, 해당 VPN의 TLB 존재 여부를 검사한다. 만약 존재하면 TLB 히트이다. 여기서 PFN을 추출할 수 있다. 해당 페이지에 대한 접근 권한 검사가 성공하면, 그 정보를 원래 가상 주소의 오프셋과 합쳐서 원하는 물리 주소를 구성하고, 메모리에 접근할 수 있다.

TLB에 변환 정보가 존재하지 않는다면 (TLB 미스) 할 일이 많아진다. 페이지 테이블에 접근하고, 참조가 유효하고 접근 가능하다면 이를 TLB로 불러들인다. TLB가 갱신되면 하드웨어는 명령어를 재실행한다. 이번에는 TLB에 존재하므로 메모리 참조가 빠르게 처리된다.

메모리 접근은 다른 CPU 연산에 비해 매우 시간이 오래 걸리는 작업이다. TLB 미스가 많이 발생할수록 메모리 접근 횟수가 많아진다. TLB 미스가 발생하는 경우를 최대한 피해야 한다.

2. 예제: 배열 접근

이렇게 배열이 구성되어 있을 때, a[0], a[3], a[7]에 접근할 때 빼고 모두 TLB 히트이다. 이 예제에서는 1 page가 16 byte의 크기를 가지는데 만약 페이지 크기가 더 커진다면, TLB 히트 확률이 더 올라갈 것이다.

일반적인 경우 페이지는 4KB이다. 예제처럼 정수 배열을 연속적으로 접근하는 경우 한 번의 미스만 발생할 것이다.

시간 지역성(Temporal Locality): 이는 프로그램이 한 번 접근한 메모리 위치를 가까운 미래에 다시 접근할 가능성이 높다는 개념입니다. 예를 들어, 루프에서 반복적으로 사용되는 변수나 배열은 이러한 지역성의 예입니다. 시간 지역성을 활용하면, 한 번 접근한 데이터를 캐시에 저장하고, 미래의 접근에서는 빠르게 캐시에서 데이터를 가져올 수 있습니다.

공간 지역성(Spatial Locality): 이는 프로그램이 한 번 접근한 메모리 위치 주변을 가까운 미래에 접근할 가능성이 높다는 개념입니다. 예를 들어, 순차적으로 실행되는 명령어나 연속적인 메모리 위치에 저장된 배열의 원소들은 이러한 지역성의 예입니다. 공간 지역성을 활용하면, 데이터를 캐시에 블록 단위로 가져오고, 인접한 메모리 위치에 대한 접근에서는 캐시에서 빠르게 데이터를 가져올 수 있습니다.

3. TLB 미스는 누가 처리할까

하드웨어에서 처리하는 방법(CISC)과 소프트웨어에서 처리하는 방법(RICS) 두 가지가 있다.

하드웨어에서 처리하는 경우, 하드웨어가 페이지 테이블에 대한 명확한 정보를 가지고 있어야 한다. 이를 위해서 페이지 테이블 레지스터를 두고, 이 레지스터로 TLB를 갱신했다.

TLB에서 주소 찾는 것이 실패한 경우, 하드웨어는 예외 시그널을 발생시킨다. 시그널을 받은 운영체제는 잠시 실행을 중단하고 커널 모드로 변경한 후 TLB 미스를 처리하는 트랩 핸들러를 실행시킨다. 이 핸들러는 페이지 테이블을 검색하여 변환 정보를 찾고, TLB를 갱신한 후 리턴한다.

TLB를 소프트웨어로 관리하면 하드웨어 변경 없이 테이블 구조를 유연하게 변경할 수 있고, 하드웨어가 처리할 일이 없어서 더 단순하다.

4. TLB의 구성: 무엇이 있나?

TLB | PFN | 다른 비트

변환 정보 저장 위치에 제약이 없도록, 각 항목마다 VPN, PFN이 존재한다. TLB는 완전 연관 캐시이다. 다른 비트들은 무엇을 할까? TLB는 일반적으로 valid bit를 가지고 있다. 이 비트는 특정 항목이 유효한 변환 정보를 가지고 있는지 여부를 나타낸다. protection bit는 읽기, 쓰기, 실행 등 권한을 관리한다. 그 외에도 주소 공간 식별자, 더티 비트 등 여러 비트가 존재한다.

5. TLB의 문제: 문맥 교환

TLB에 탑재된 가상 주소와 실제 주소 간의 변환 정보는 그것을 탑재시킨 프로세스에서만 유효하다. 다른 프로세스로 context switch가 일어나면 어떻게 해야 할까?

첫 번째 방법은 문맥 교환을 수행할 때 다음 프로세스가 실행되기 전 TLB를 비우는 것이다. 문맥 교환이 일어날 때마다 TLB를 비우면 잘못 작동하는 것을 막을 수 있겠지만 TLB 미스가 많이 발생할 것이다.

이 부담을 개선하기 위해 몇몇 시스템에서는 문맥 교환이 발생하더라도 TLB의 내용을 보존할 수 있는 하드웨어 기능을 추가하였다. TLB 내에 주소 공간 식별자 (Address Space Identifier) 필드를 추가하는 것이다.

이를 통해 프로세스 별로 TLB 변환 정보를 구분할 수 있다.

6. 이슈: 교체 정책

모든 캐시가 그러하듯, TLB에서도 캐시 교체 정책이 매우 중요하다. TLB에 새로운 항목을 탑재할 때 어떤 항목을 교체 대상으로 선정해야 할까?

이 내용은 디스크, 메모리 간의 페이지 스왑 부분에서 상세히 다루고, 지금은 몇 개의 일반적인 정책들만 요약하도록 하자.

최저 사용 빈도(least-recently-used, LRU) 가 가장 흔한 방법이다. 사용되지 않은 오래된 항목일수록 앞으로도 사용될 가능성이 적으며, 교체 대상으로 적합할 것이다.

랜덤하게 고르는 방법도 일반적이다. 이는 구현이 간단하고 예외 상황의 발생을 피할 수 있다.

LRU같은 합리적인 정책은 $n$개의 변환 정보를 저장할 수 있는 TLB가 $n+1$개의 페이지들에 대해 반복문을 수행하는 프로그램에서 최악의 TLB 미스를 생성할수도 있다. 랜덤하게 교체하는 경우 이런 일이 (거의) 없을 것이다.

7. 실제 TLB

MIPS R4000는 32비트 주소 공간에서 4KB 페이지를 지원한다.

• 가상 페이지 번호(VPN): 19비트로 할당되며, 주소 공간의 절반은 사용자 주소 공간으로 할당된다.
• 물리 프레임 번호(PFN): 24비트로 할당되며, 최대 64GB의 메모리(2^24 개의 4KB 페이지들) 지원이 가능하다.

TLB 항목에는 또한 몇 가지 중요한 비트들이 포함되어 있습니다:

• 전역 비트(G): 이 비트는 프로세스 간에 공유되는 페이지들을 위해 사용된다. 전역 비트가 설정되면 ASID(Address Space Identifier)는 무시됩니다.
• ASID 필드: 8비트로, 운영체제는 이 필드를 통해 주소 공간을 구분한다.
• 일관성 비트(C): 이 비트는 페이지가 하드웨어에 어떻게 캐시되어 있는지 판별하는 데 사용된다.
• 더티 비트(D): 페이지가 갱신되면 세팅된다.
• 유효 비트(V): 항목에 유효한 변환 정보가 존재하는지 나타낸다.
• 페이지 마스크 필드: 여러 개의 페이지 크기를 지원할 때 사용된다. 그림에는 나타나있지 않다.