[OSTEP] 19. 변환 색인 버퍼 (TLB: Translation Lookaside Buffers)

1. TLB의 기본 개념 (Basic Algorithm)#

TLB는 MMU(Memory Management Unit)의 일부로서, 가상 주소에서 물리 주소로의 변환 정보를 저장하는 하드웨어 캐시(Cache) 입니다.

주소 변환이 필요할 때 하드웨어는 페이지 테이블(메모리)을 보기 전에 먼저 TLB(캐시)를 확인합니다. 하드웨어의 동작 로직을 의사 코드(Pseudo-code)로 표현하면 다음과 같습니다.

1
// 0. 가상 주소에서 VPN 추출
2
VPN = (VirtualAddress & VPN_MASK) >> SHIFT
3

4
// 1. TLB 검색
5
(Success, TlbEntry) = TLB_Lookup(VPN)
6

7
if (Success == True) { // TLB Hit (빠름)
8
    if (CanAccess(TlbEntry.ProtectBits) == True) {
9
        Offset = VirtualAddress & OFFSET_MASK
10
        PhysAddr = (TlbEntry.PFN << SHIFT) | Offset
11
        AccessMemory(PhysAddr)
12
    } else {
13
        RaiseException(PROTECTION_FAULT)
14
    }
15
}
16
else { // TLB Miss (느림)
17
    // 2. 페이지 테이블 조회 (메모리 접근 발생)
18
    PTEAddr = PTBR + (VPN * sizeof(PTE))
19
    PTE = AccessMemory(PTEAddr)
20

21
    if (PTE.Valid == False) {
22
        RaiseException(SEGMENTATION_FAULT)
23
    } else if (CanAccess(PTE.ProtectBits) == False) {
24
        RaiseException(PROTECTION_FAULT)
25
    } else {
26
        // 3. TLB 업데이트 및 명령어 재실행
27
        TLB_Insert(VPN, PTE.PFN, PTE.ProtectBits)
28
        RetryInstruction()
29
    }
30
}

2. 지역성 (Locality): TLB가 작동하는 이유#

TLB는 크기가 매우 작습니다(보통 32~128 항목). 이렇게 작은 캐시가 어떻게 시스템 전체의 성능을 획기적으로 높일 수 있을까요? 그 비밀은 지역성(Locality) 에 있습니다.

다음은 16바이트 페이지 크기를 가진 시스템에서 정수 배열 a[0]부터 a[9]까지 순차적으로 접근하는 상황입니다.

Figure 19.2: 배열이 메모리에 배치된 모습. a[0]~a[2]는 같은 페이지(06)에, a[3]~a[6]은 다음 페이지(07)에 위치합니다.

3. TLB 미스 처리: 누가 담당하는가?#

TLB 미스가 발생했을 때 페이지 테이블을 뒤져서 새로운 정보를 가져오는 작업은 누가 할까요? 이는 아키텍처(CISC vs RISC)마다 다릅니다.

1
VPN = (VirtualAddress & VPN_MASK) >> SHIFT
2
(Success, TlbEntry) = TLB_Lookup(VPN)
3

4
if (Success == True) { // TLB Hit
5
    if (CanAccess(TlbEntry.ProtectBits) == True) {
6
        Offset = VirtualAddress & OFFSET_MASK
7
        PhysAddr = (TlbEntry.PFN << SHIFT) | Offset
8
        AccessMemory(PhysAddr)
9
    } else {
10
        RaiseException(PROTECTION_FAULT)
11
    }
12
}
13
else { // TLB Miss
14
    RaiseException(TLB_MISS) // 하드웨어는 예외만 발생시키고 끝!
15
}

4. TLB 항목의 구성 (TLB Contents)#

TLB는 단순한 VPN-PFN 매핑 외에도 몇 가지 중요한 비트들을 포함합니다.

• Valid Bit: 이 항목이 유효한 변환 정보를 담고 있는지 표시합니다. (페이지 테이블의 Valid 비트와는 다릅니다. 부팅 직후에는 모두 0입니다.)
• Protection Bits: 읽기/쓰기/실행 권한을 표시합니다.
• Dirty Bit: 해당 페이지가 수정되었는지 여부를 나타냅니다.
• ASID (Address Space ID): 문맥 교환 문제를 해결하기 위한 프로세스 식별자입니다.

5. 문맥 교환 문제 (Context Switch Issues)#

TLB는 프로세스별 가상 주소를 물리 주소로 변환합니다. 만약 프로세스 A에서 프로세스 B로 문맥 교환(Context Switch) 이 일어나면 어떻게 될까요?

프로세스 A의 VPN 10번과 프로세스 B의 VPN 10번은 서로 다른 물리 주소를 가리켜야 합니다. 하지만 TLB에 VPN 10번 정보가 남아있다면 하드웨어는 이를 구분할 수 없습니다.

6. 교체 정책 (Replacement Policy)#

TLB가 가득 찼을 때 새로운 항목을 넣으려면 기존 항목 중 하나를 버려야 합니다. 어떤 것을 버리는 게 좋을까요?

• LRU (Least Recently Used): 가장 오랫동안 사용하지 않은 항목을 교체합니다. 지역성의 원리에 따라 일반적으로 효율적입니다.
• Random: 무작위로 교체합니다. 구현이 매우 간단하고, LRU가 취약한 특정 패턴(TLB 크기보다 약간 큰 데이터를 반복 순회하는 경우)에서 오히려 더 좋은 성능을 보이기도 합니다.

7. 요약 (Summary)#

이번 장에서는 페이징의 성능 문제를 해결하는 핵심 장치인 TLB를 다뤘습니다.

• TLB는 하드웨어 캐시로서 주소 변환 속도를 획기적으로 높여줍니다.
• 공간/시간 지역성 덕분에 작은 크기로도 높은 히트율을 보장합니다.
• TLB 미스는 하드웨어 또는 OS(소프트웨어)가 처리합니다.
• 문맥 교환 시 발생하는 문제는 ASID를 통해 효율적으로 해결합니다.

다음 장에서는 페이지 테이블 자체가 너무 커지는 공간 문제를 해결하기 위한 멀티 레벨 페이지 테이블에 대해 알아보겠습니다.

8. 용어 정리#

• TLB(Translation Lookaside Buffer): 가상-물리 주소 변환 정보를 저장하는 하드웨어 캐시.
• TLB 히트(Hit): 원하는 변환 정보가 TLB에 있는 경우.
• TLB 미스(Miss): 변환 정보가 TLB에 없어 페이지 테이블을 조회해야 하는 경우.
• 공간 지역성(Spatial Locality): 참조된 주소와 인접한 주소가 곧 참조될 가능성이 높은 특성.
• 시간 지역성(Temporal Locality): 최근에 참조된 주소가 다시 참조될 가능성이 높은 특성.
• ASID(Address Space ID): TLB 내에서 프로세스를 구별하기 위해 사용하는 식별자.
• 플러시(Flush): TLB의 모든 항목을 무효화(비움)하는 작업.

Reference#

• Operating Systems: Three Easy Pieces - Chapter 19: Translation Lookaside Buffers