12-1. Paging - Faster Translations (TLBs, 주소 변환 캐시)¶

a.k.a 주소-변환 캐시(address translation cache)

• TLB
  • 칩의 Memory-Management Unit(메모리 관리 장치, MMU)의 일부
  • TLB는 가상 주소에서 물리 주소 변환을 위해 필요한 page table 일부를 저장하는 하드웨어 캐시
  • TLB를 이용하면 이전에 참조한 페이지에 대한 물리 주소가 저장되어 있어, 메모리 상의 page table을 참조할 필요가 없어 성능이 향상된다.

기본 절차¶

가정¶

• 선형 페이지 테이블을 페이지 테이블로 사용

  “배열로 구성된 페이지 테이블”

• TLB 중에서는 하드웨어로 관리하는 TLB로 구성.

  “하드웨어가 페이지 테이블 접근에 대한 대부분의 책임을 관리하는 구조”

절차¶

1. 가상 주소에서 가상 페이지 번호를 추출한다
2. VPN이 TLB에 있는지 확인한다.
   1. 존재한다.
      1. TLB에서 페이지 프레임 번호를 추출한다.
      2. 접근 권한이 있는지 확인한다
      3. 가상 주소의 오프셋과 결합하여 물리 주소를 구성한다.
   2. 존재하지 않는다.
      1. 페이지 테이블에 접근한다.
      2. 프로세스의 가상 주소가 유효한지 검사한다.
      3. 접근 권한이 있는지 확인한다.
      4. 해당 변환 정보를 TLB로 읽어들인다.
      5. 하드웨어 명령어를 재실행한다. (1~2번까지 다시 실행한다는 의미)
3. 메모리에 접근한다.

이때 TLB 미스가 발생하는 경우를 최대한 피해야 함!

TLB 기본 알고리즘¶

// Paging 기법에서 TLB를 사용한 메모리 접근 과정  

// 1. VPN 추출 : 가상 주소에서 VPN 추출  
// 가상 주소에서 VPN_MASK를 AND 연산하고 right shift 함  
VPN = (VirtualAddress & VPN_MASK) >> SHIFT  

// 2. TLB Lookup : 추출한 VPN으로 TLB를 검색함  
// 해당 VPN이 있으면 TLB Hit, 없으면 TLB Miss  
(Success , TlbEntry) = TLB_Lookup(VPN)  

// TLB Hit(Success)  
if (Success == TRUE) {  
  // 3. TLB에 해당 VPN이 있는 경우, 해당 PTE의 보호 비트를 체크  
  // 메모리 접근이 가능한지 검사하고  
  if (CanAccess(TlbEntry.ProtectBit) == True) {  
    // 가능하면, offset를 가상 주소에서 추출하고 물리 주소 계산해 메모리 접근  
    offset = VirtualAddreess & OFFSET_MASK;  
    PhysAddr = (TlbEntry.PFN << SHIFT) | Offset;  
    AccessMemomry(PhysAddr);  
  } else RaiseException(PROTECTION_ERROR); // 메모리 접근 불가시 예외  
} else {  
  // TLB Miss  
  // 4. TLB에 해당 VPN이 없는 경우, 해당 VPN에 대한 PTE를 찾기 위해  
  // PTBR과 VPN을 이용해 PTEAddr를 계산해 메모리 접근해서 해당 PTE를 얻음  
  PTEAddr = PTBR + VPN * sizeof(PTE);  
  PTE = AccessMemory(PTEAddr);  

  // 얻은 PTE가 유효하면 TLB에 해당 VPN, PFN을 삽입한 후 다시 명령어 실행  
  // 유효하지 않으면 SEGFAULT 예외 발생  
  if (PTE.Valid == False) RaiseException SEGFAULT;  
  else {  
    TLB_Insert(VPN, PTE.PFN, PTE.ProtectBits);  
    RetryInsturction();  
  }  
}  

성능 개선의 원리¶

지역성¶

• Temporal Locality(시간적 위치)

  • 최근에 접근한 명령어나 데이터는 다시 접근될 가능성이 높음

  • 한 번 배열 전체를 다 읽은 후에도 얼마 안 있어 배열의 데이터를 사용한다면 시간 지역성으로 인한 성능 향상에 해당한다. 한 번 참조된 메모리 영역이 짧은 시간 내에 다시 참조되는 현상.

  • Spatial Locality(공간적 위치)

    • 해당 주소 근처의 메모리에 접근할 가능성이 높음
    • 프로세스가 참조하는 메모리 주소들이 근접한 위치에 있을 가능성이 높은 특성을 말한다.
    • 이 특성 때문에 TLB에 저장되는 page table entry는 자주 사용되는 페이지들로 담게 되고, 이로 인해 TLB에서의 빈도가 높아져 hit rate가 증가한다.
    • 따라서 TLB hit rate가 높을수록 메모리 접근 시간이 단축되어 프로세스 성능이 향상된다.
    • 배열 항목이 페이지 내 서로 인접하여 있으므로 페이지 내 첫 번째 항목에 접근할 때만 미스가 발생하고, 이후에는 같은 페이지 내에 다른 항목들이 있으므로 문제가 없다. 이런 식으로 인접한 데이터를 접근할 때는 공간 지역성으로 성능이 향상된다.

📔 성능 개선에 캐시를 사용할 때, “작은 캐시를 어떻게 잘 사용하는가”에 대해 고민하는 것임을 명심하자.

TLB 미스의 처리¶

하드웨어로 관리되는 TLB(Hardware-Managed TLB)¶

• CISC(Complex Instruction Set Computer) 아키텍처인 Intel x86과 같은 경우, TLB miss를 전적으로 하드웨어에서 처리
  1. 하드웨어는 page table이 메모리 어디에 있는지 정확히 알아야 함
  2. page table로 올바른 page table 항목을 찾아 필요한 변환 정보를 추출
  3. 하드웨어는 그 후 TLB를 업데이트하고 명령을 재시도 한다.

x86 CPU는 멀티 레벨 페이지 테이블(Multi-Level page table) 사용.

소프트웨어로 관리되는 TLB(Software-managed TLB)¶

• MIPS, SPARC와 같은 RISC(Reduced Instruction Set Computer) 아키텍처는 소프트웨어 관리형 TLB를 사용한다.
  1. CPU가 TLB miss를 만나면 하드웨어가 예외를 발생시키고 실행 모드를 커널 모드로 변경한 뒤 운영체제의 trap handler로 제어가 전달되어 실행된다.
  2. 운영체제의 trap handler는 TLB miss를 처리하기 위해 페이지 테이블을 검색하여 변환 정보를 찾는다.
  3. TLB 접근이 가능한 특권 명령어로 TLB를 업데이트 한다
  4. 하드웨어는 유저 모드로 해당 명령을 재실행한다.

시스템 콜과의 차이점¶

• 시스템 콜은 트랩 핸들러 이후 다음 명령어를 실행
• TLB 미스는 트랩 핸들러 이후 기존 명령어를 재실행

종류에 따라 현재 명령어의 PC 값 혹은 다음 명령어의 PC 값을 저장할 필요 있음.

TLB 핸들러 실행 시 미스가 무한 반복되지 않으려면¶

• TLB 미스 핸들러를 접근하는 과정 자체에서 TLB 미스가 발생하는 상황.
  1. 가상 주소가 아닌 물리 주소로 고정하여 물리 메모리에 위치시키는 방법 → 주소 변환이 불필요
  2. TLB 일부를 TLB 미스에 사용하는 트랩 핸들러 코드 주소로 고정. = 연결(wired) 변환

장점¶

1. 유연성 — 하드웨어 변경 없이 페이지 테이블 구조의 변경이 자유롭다
2. 단순함 — 미스 발생 시 하드웨어는 할 일이 많지 않다.

TLB Control Flow 알고리즘(OS Handled)

// 가상 주소에서 VPN 추출, 가상 주소가 페이지 번호와 오프셋으로 분할  
1:   VPN = (VirtualAddress & VPN_MASK) >> SHIFT  

// TLB_Lookup 함수 호출해 TLB에 페이지 번호가 캐시되어 있는지 확인함  
// TLB hit이나 miss 둘 중 하나의 결과가 반환  
2:   (Success, TlbEntry) = TLB_Lookup(VPN)  

// TLB Hit인 경우, TlbEntry에 캐시된 페이지 번호와 해당 물리 페이지(PFN)  
// 에 대한 정보가 포함. 이걸로 해당 물리 주소에 대한 메모리 액세스  
3:   if (Success == True) // TLB Hit  

// 보호 비트로 해당 메모리 접근할 수 있는지 체크  
4:   if (CanAccess(TlbEntry.ProtectBits) == True)  

// 오프셋 마스킹 수행  
// (가상 주소에서 추출한 오프셋을 물리 주소의 오프셋과 일치하도록 변환)  
5:       Offset = VirtualAddress & OFFSET_MASK  
// 물리 주소 계산 후, AccessMemory 함수를 이용해 해당 물리 주소 접근  
// 결과를 레지스터에 저장함  
6:       PhysAddr = (TlbEntry.PFN << SHIFT) | Offset  
7:       Register = AccessMemory(PhysAddr)  

// 접근 불가면 예외 발생  
8:   else  
9:       RaiseException(PROTECTION_FAULT)  

// TLB Miss인 경우, 해당 예외 발생. os의 예외 처리하는 부분으로 전달됨  
10:  else // TLB Miss  
11:      RaiseException(TLB_MISS)  

TLB 구성¶

• 실제 TLB Entry

  • MIPS R4000(64bit)
    

• TLB entry

  • TLB는 완전 연관(fully associative) ¹ 방식으로 설계
  • 일반적인 TLB에는 32, 64, 128개 중 한가지 방식의 entry가 있음
  • 하드웨어는 전체 TLB를 병렬로 검색해 원하는 변환을 찾아낸다.
  • Bit
    1. valid bit — 유효한 변환 정보를 갖고 있는지
    2. protection bit — 읽기, 쓰기, 실행 권한 등
    3. dirty bit
    4. address-space identifier(주소 공간 식별자)
       1. 프로세스 식별자와 유사하지만 더 작은 비트를 가짐. 프로세스별로 TLB 변환 정보를 구분하는데 사용.
       2. 코드 페이지를 공유하여 사용되는 물리 페이지 수를 줄이고, 메모리 부하를 낮추기 위해 두 항목이 동일한 물리 페이지를 가리킬 수도 있다.

• TLB Issues : Context Switching

  • 프로세스의 컨텍스트 스위칭이 발생할 경우, TLB에 저장된 가상 주소와 물리 주소의 매핑 정보가 새로운 프로세스의 주소 공간과 맞지 않을 수 있다.
  • 이런 문제로 TLB를 비우고 새로운 매핑 정보를 채워넣어야 한다는 비효율성이 발생
  • 이걸 해결하기 위해 TLB에 Address Space Identifier(ASID) 필드를 추가하는 방법이 생김
    • ASID는 각각 프로세스에 고유한 식별자를 할당해, TLB에서 각 프로세스의 가상 주소와 물리 주소 매핑 정보를 분리해 저장할 수 있도록 한다.
    • 컨텍스트 스위칭이 발생해도 ASID를 참조해 해당 프로세스의 가상 주소와 물리 주소 매핑 정보를 쉽게 찾을 수 있다. TLB 적중률도 향상시키고, TLB에서 새로운 매핑 정보를 쉽게 업데이트 할 수 있음

공유 페이지¶

• 두 개의 프로세스(P1, P2)가 하나의 물리 페이지(Physical Page 101)를 공유함
• 이 때, P1은 이 물리 페이지를 자신의 가상 주소 공간에서 10번째 페이지에 매핑하고, P2는 50번째 페이지에 매핑함
• 이런 방식은 물리 메모리 사용량을 줄이는 데 유용함. 같은 내용의 페이지가 여러 프로세스에서 동시에 필요한 경우, 이 페이지를 각각 프로세스가 메모리에 복사하는 건 비효율적임. 따라서, 이 페이지들을 물리 메모리에는 1번만 저장하고, 필요한 프로세스들이 이 페이지를 공유해 사용하는 방식으로 처리한다.

교체 정책¶

TLB에 새 항목을 탑재할 때, 부족한 공간을 확보하기 위해 캐시 교체(cache replacement)를 어떻게 수행하여 미스율은 낮추고 성능을 개선할 수 있을까?

• TLB 대체 정책
  1. LRU(Least Recently Used)
     • 가장 오랫동안 사용하지 않은 항목을 우선적으로 대체함
     • 여기서는 locality를 활용한 방식으로 LRU를 적용
     • 일반적으로 특정 영역의 메모리가 더 자주 참조될 가능성이 높음. 지역성을 활용하기 위해, LRU에선 가장 오랫동안 참조되지 않은 페이지를 우선적으로 대체한다.
  2. 랜덤 교체
     - 구현이 간단, 예상치 못한 예외 상황을 피하고자
     Caches: LRU v. random

TLB의 한계¶

• 짧은 시간 동안 접근하는 페이지의 수가 TLB에 들어갈 수 있는 수보다 많다면 많은 수의 TLB 미스가 발생하여 느리게 동작할 수 있다. = TLB 범위(TLB Coverage)를 벗어난다고 표현

  → 더 큰 페이지 크기를 지원하도록 하여 개선 가능: DBMS에서 주로 사용, 임의적 접근

CPU 파이프라인에서 TLB 접근은 병목이 될 수 있다.

• 물리적으로 인덱스된 캐시(Physically Indexed Cache)

  주소 변환이 캐시 접근 전에 실행되어야 하는데, 주소 변환에 사용되는 비용으로 인해 구조 상 병목 발생

• 가상적으로 인덱스된 캐시(Virtually Indexed Cache)
  • 위 문제를 일부 해결하지만 가상으로 인덱스된 캐시 공통현상
    1. Synonym
    하나 이상의 가상 주소가 하나의 물리주소와 매핑되는 문제
    2. homonym
    캐시값으로 인해 남은 것이므로 문맥 교환 시 invalidation / clean 으로 해결

다음에 배울 것: 은 더 큰 페이지 크기를 지원하도록 하는 것이다. 더 큰 페이지들을 사용할 경우 TLB의 유효 범위가 늘어날 수가 있다.

더 큰 페이지들을 위한 지원은 데이터베이스 관리 시스템(database management system, DBMS)과 같은 프로그램들에 의해서 주로 사용되며, 이러한 프로그램의 자료 구조들은 클 뿐만 아니라 임의적으로 접근된다.