Operating System: 12. TLB

변환-색인 버퍼(Translation-Lookaside Buffer)

• 주소 변환을 빠르게 하기 위해서 TLB의 도움을 받는다.
• TLB는 자주 사용 되는 가상 주소-실주소 변환 정보를 저장하는 하드웨어 캐시다.
• TLB는 메모리 관리부(memory-management unit, MMU)의 일부다.
• TLB를 도입함으로써 페이징이 사용 가능한 기법이 된다.

TLB의 기본 알고리즘

• 동작 과정
  • 1. 먼저 가상 주소에서 가상 페이지 번호(VPN)을 추출한다.
  • 2. 해당 VPN의 TLB 존재 여부를 검사한다.
    • 만약 존재하면 TLB 히트, 아니라면 TLB 미스
  • 3. TLB 히트한 경우 TLB 항목에서 페이지 프레임 번호(PFN)을 추출한다.
  • 3. TLB 미스한 경우 하드웨어가 변환 정보를 찾기 위해 페이지 테이블에 접근한다.
  • 4. 프로세스가 생성한 가상 메모리 참조가 유효하고 접근 가능하다면, 해당 변환 정보를 TLB로 읽어들인다. (메모리 접근은 굉장히 느리다)
  • 5. TLB가 갱신되면 하드웨어는 명령어를 재실행한. (TLB에 변환 정보가 존재하므로 TLB 히트)
• 이를 코드로 나타내면 아래와 같다.

  VPN = (VirtualAddress & VPN_MASK) >> SHIFT
  (SUCCESS, TlbEntry)
  if (SUCCESS = True)                                  // TLB 히트
    if (CanAccess(TlbEntry.ProtectionBits) == True)
        Offset = VirtualAddress & OFFSET_MASK
        PhysAddr = (TlbEntry.PFN << SHIFT) | Offset
        AccessMemory(PhysAddr)
    else
        RaiseExecption(PROTECTION_FAULT)
  else                                                 // TLB 미스
    PTEAddr = PTBR + (VPN * sizeof(PTE))
    PTE = AccessMemory(PTEAddr)
    if (PTE.Valid == False)
        RaiseExecption(SEGMENTATION_FAULT)
    else if (CanAccess(PTE.ProtectionBits) == False)
        RaiseExecption(PROTECTION_FAULT)
    else
        TLB_Insert(VPN, PTE.PFN, PTE.ProtectionBits)
        RetryInstruction()
  

배열 접근

• 가상 주소 공간이 8비트이고, 페이지 크기가 16바이트라면 가상 주소는 4비트 VPN(16개의 가상 페이지)과 4비트 오프셋으로 구성된다.
• 16개의 페이지로 구성된 가상 주소 공간을 도식적으로 아래와 같이 표현한다.

• 간단한 코드를 통해 TLB 동작 과정을 살펴보자.

  int sum = 0;
  for (i = 0; i < 10; i++)
    sum += a[i];
  

• 배열 원소를 읽는 TLB 동작을 정리해 보면 1. 미스 2. 히트 3. 히트 4. 미스 5. 히트 6. 히트 7. 히트 8. 미스 9. 히트 10. 히트가 된다. (TLB 히트 비율은 70%)
• 배열이 처음으로 접근되었지만, TLB는 공간 지역성(spatial locality)로 성능을 개선할 수 있다.
• 페이지 크기는 TLB의 효용성에 매우 중요한 역할을 한다.
• 예제 프로그램이 루프가 종료한 후에도 배열을 사용한다면 성능이 더욱 개선될 것이다. 이 경우 시간 지역성(temporal locality) TLB히트율이 높아진다.

TLB 미스는 누가 처리할까?

1. CISC(complex instruction set computers)

• TLB 미스를 하드웨어가 처리하도록 한다.
• 하드웨어가 페이지 테이블에 대한 명확한 정보를 가지고 있어야 한다.
• 동작 과정
  • 1. 페이지 테이블에서 원하는 페이지 테이블 엔트리를 찾는다.
  • 2. 필요한 변환 정보를 추출하여 TLB를 갱신한다
  • 3. TLB 미스가 난 경우 명령어를 재실행한다.

2. RISC(reduced instruction set computing)

• 소프트웨어 관리 TLB(software-mangaed TLB)를 사용한다.
• 동작 과정
  • 1. TLB에서 주소 찾는 것이 실패하면 하드웨어는 예외(exception)을 시그널을 발생시킨다.
  • 2. 예외를 받은 운영체제는 명령어 실행을 잠정 중지하고, 실행 모드를 커널 모드로 변경하여, 커널 코드 실행을 준비한다.
  • 3. 실행 모드를 커널 모드로 변경하는 작업의 핵심은 커널 주소 공간을 접근할 수 있도록 특권 레벨(privilege level)로 상향 조정하는 것이다.
  • 4. 커널 모드로 변경되면 트랩 핸들러(trap handler)를 실행한다.
  • 5. 이때, 트랩 핸들러는 TLB 미스를 처리하는 운영체제 코드이다.
  • 6. 이 트랩 핸들러는 페이지 테이블을 검색하여 변환 정보를 찾고, TLB 접근이 가능한 특권 명령어를 사용하여 TLB를 갱신한 후에 리턴한다.
  • 7. 이후 하드웨어가 명령어를 재실행 한다. TLB 히트가 난다.
  • 8. 트랩이 발생하면 운영체제는 트랩 핸들러가 종료되었을 때 다시 실행을 계속할 명령어 주소(program counter)를 저장한다.

    VPN = (VirtualAddress & VPN_MASK) >> SHIFT
    (Success. TlbEntry) = TLB_Lookup(VPN)
    if (Success == True)
      if (CanAccess(TlbEntry.ProtectionBits) == True)
      Offset = VirtualAddress & OFFSET_MASK
      PhyAddr = (TlbEntry.PFN << SHIFT) | Offset
      else
      RaiseExecption(PROTECTION_FAULT)
    else
      RaiseExecption(TLB_MISS)
    

주의 사항

• TLB 미스 핸들러를 실행할 때, TLB가 미스가 무한 반복되지 않도록 주의를 한다. 이는 TLB 미스 핸들러를 접근하는 과정에서 발생하는 상황이다.
  1. TLB 미스 핸들러를 물리 메모리에 존재시킨다.
  2. TLB의 일부를 핸들러 코드 주소를 저장하는 데 영구히 할당한다(연결(wired) 변환)

장점

• 운영체제는 하드웨어 변경없이 페이지 테이블 구조를 자유로이 변경할 수 있다.
• TLB 제어 흐름에서 보는 것과 같이 하드웨어는 별로 할 일이 없고, 예외가 발생하면 운영체제의 TLB 미스 핸들러가 처리한다는 점에서 단순하다는 장점이 있다.

TLB의 구성

• 일반적인 TLB는 32, 64, 또는 128개의 엔트리를 가지며, `완전 연관(fully associative)방식으로 설계된다.
• 완전 연관 방식에서 변환 정보는 TLB내 어디든 위치할 수 있으며, 원하는 변환 정보를 찾는 검색은 TLB전체에서 병렬적으로 수행된다.

  VPN    |    PFN    | 다른 비트들
  

• 변환 정보 저장 위치에 제약이 없도록, 각 항목마다 가상 페이지 번호(VPN)과 물리 페이지 번호(PFN)가 있다.
• 하드웨어 측면에서 TLB는 완전 연관 캐시이다. 변환 주소를 찾을 때 하드웨어는 TLB의 각 항목을 동시에 검색한다.
• valid bit: 특정 항목이 유효한 변환 정보를 갖고 있는지 여부, (cf. 페이지 테이블에서 어떤 페이지 테이블 항목(PTE)가 무효로 표시되어 있다면, 아예 할당되어 있지 않다는 점에서 구분된다)

TLB와 문맥 교환 문제

• 두 개의 프로세스가 있을 때, P1의 10번째 가상 페이지가 물리 프레임 100에 매핑되어 있다고 하자. P2의 10번째 가상 페이지는 물리 프레임 170에 있을 때 문맥교환이 일어나면 10번째 가상 페이지 변환 정보가 2개 존재한다.
• 한 방법은 문맥 교환을 수행할 때 기존 TLB 내용을 비우는 것이다.
  • 잘못된 사용을 방지할 수 있지만, 매번 TLB미스가 발생하게 되어 성능에 문제가 된다.
• TLB 내 주소 공간 식별자(address space identifier, ASID)필드를 추가한다.
  • 이는 프로세스 식별자와 비슷하지만 더 적은 비트를 갖고 있다.

실제 TLB (MIPS R4000)

• 32비트 주소 공간에 4KB 페이지를 지원한다.

• VPN은 20비트 오프셋은 12비트를 가질거라 생각하지만, 19비트가 VPN에 할당되어 있다. (주소 공간의 반은 커널이 사용한다)
• 전역(global) 비트(G)
  • 이 비트는 프로세스들 간에 공유되는 페이지들을 위해 사용된다.
  • 전역 비트가 설정되어 있으면 ASID는 무시된다.
• 일관성(coherence) 비트(C)
  • 페이지가 하드웨어에 어떻게 캐시되어 있는지 판별된다.
• 더티 비트(dirty)
  • 페이지가 갱신되면 셋팅된다.
• 유효 비트(valid)
  • 항목에 유효한 변환 정보가 존재하는지 나타낸다.
• 운영체제를 위하여 예약이 되어 있는 비트가 있다. 이는 TLB 미스가 나서는 안되는 (ex: TLB 미스 핸들러) 코드와 데이터를 위해 사용한다.