[OSTEP-19] Translation Lookaside Buffers

페이징: 더 빠른 변환 (TLB)

• 페이징은 프로세스 주소 공간을 작은 고정된 크기로 나누고 각 페이지의 실제 위치를 메모리에 저장함
• 매핑 정보를 저장하는 자료구조를 페이지 테이블이라고 함
• 모든 load/store 명령어 실행이 추가적인 메모리 읽기를 수반하기 때문에 속도가 굉장히 느림

핵심 질문: 주소 변환 속도를 어떻게 향상할까

주소 변환을 어떻게 빨리할 수 있을까? 페이징에서 발생하는 추가 메모리 참조를 어떻게 피할 수 있을까? 어떤 하드웨어가 추가로 필요할까 운영체제가 어떤식으로 개입해야할까.

• 이를 위해 하드웨어의 도움을 받음. 주소변환을 빠르게 하기 위해 (Translation-lookaside buffer) 또는 TLB라고 부르는 것 TLB는 메모리 관리부 (MMU) 의 일부이며, 자주 참조되는 가상 주소 - 실주소 변환 정보를 저장하는 하드웨어 캐시 (주소-변환 캐시) 가 좀 더 적합한 명칭. 가상 메모리 참조 시, 하드웨어는 먼저 TLB 에 원하는 변환 정보가 있는지를 확인. 만약 있다면 페이지 테이블을 통하지 않고 변환 수행, 실질 적으로 TLB 는 페이징 성능을 엄청나게 향상시킴

---

TLB 의 기본 알고리즘

// 가상 주소의 번호를 가져오기 위함
VPN = (VirtualAddress & VPN_MASK) >> SHIFT
// TLB에 현재 VPN 과 관련된 정보가 존재하는지 조회
(Success, TlbEntry) = TLB_Lookup(VPN)

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

1. VPN 을 가져온다
2. 해당 VPN 의 TLB 존재 여부를 검사한다
   1. 존재할 경우
      1. page frame number, PFN을 추출한다
      2. 접근 권한 검사가 성공하면 메모리에 접근한다
   2. 존재하지 않을 경우
      1. 페이지 테이블에 접근
      2. 가상 메모리 참조가 유효할때
         1. 해당 변환 정보를 TLB로 읽어드림 (시간이 많이 소요됨)

모든 캐시의 설계 철학 처럼 TLB 역시 “주소 변환 정보가 대부분의 경우 캐시에 있다“ 라는 가정을 전제로 만들어짐

TLB는 프로세싱 코어와 가까운 곳에 위치하고 있고, 매우 빠른 하드웨어로 구성되기 때문에 주소 변환 작업은 그다지 부담스러운 작업이 아님.

미스가 발생하는 경우 페이징 비용이 커지기 때문에 TLB 미스가 발생하는 경우를 최대한 피해야 함

---

배열 접근

아래와 같이 가상 주소 100번지 부터 10개의 4바이트 크기의 정수배열의 값을 할당할때 캐시 hit rate 를 계산해보자

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

 

a[0] 을 접근할때 VPN = 6이므로 TLB 캐시 미스 → a[2] 까지 캐시 hit

각 VPN 에 첫 접근인 경우에만 메모리를 두번이상 참조해야하고 나머지는 바로 접근할 수 있음 (공간 지역성)

즉, 페이지의 크기는 TLB 의 효용성에 매우 중요한 역할을 함

위 프로그램이 루프 종료후에도 사용된다면 시간 지역성 으로 인해 TLB 의 히트율이 더 높아 질 것 임

---

TLB 미스는 누가 처리할까

하드웨어

• 과거 하드웨어는 복잡한 명령어로 구성되어 있어서 CISC (complex-instruction set computers) 라고 통칭함.
• 하드웨어 엔지니어들은 엉뚱한 방법쓰기를 좋아하는 운영체제 개발자들을 신뢰할 수 없었음
• 하드웨어는 TLB 미스를 처리하기 위해 Page Table 메모리 상 정확한 위치와 정확한 형식을 파악하고 있어야 함
  • 1) 페이지 엔트리 찾기
  • 2) 필요한 변환 정보 추출
  • 3) TLB 갱신 → TLB 미스 명령어 재 실행
• 인텔 x86 CPU 가 하드웨어로 관리되는 TLB 의 대표적인 예시 (multi-level page table)

소프트웨어 (운영체제)

• RISC (reduced instruction set computing) 은 CISC 보다 최근에 등장한 컴퓨터 구조.
• RISC 는 소프트웨어 관리 TLB 를 사용
  • 1) TLB 에서 주소 찾기 실패 → 하드웨어 예외 발생
  • 2) 명령어 실행 중지 → 실행 모드를 커널 모드로 변경
  • 3) trap handler 실행
    • TLB 미스의 처리를 담당하는 운영체제 코드
  • 4) 트랩 핸들러 갱신한 후에 리턴, 리턴되면 하드웨어가 명령어를 재 실행 함
• TLB 를 소프트웨어로 변경하는 방식의 장점
  • 유연성: 하드웨어 변경없이 페이지 테이블 구조를 자유로이 변경할 수 있음
  • 단순함: 캐시 미스가 발생했을때 하드웨어가 별로 할 일이 없음

두 가지 중요한 사항

1. TLB 미스를 처리하는 트랩 핸들러는 시스템 콜 호출 시 사용되는 트랩 핸들러와의 차이가 있음
   1. 시스템 콜 호출의 경우 트랩 핸들러에서 리턴후 다음 명령어 실행, TLB 미스 처리의 경우, 트랩에서 리턴하면 명령을 다시 실행
2. TLB 미스 핸들러를 실행할때, TLB 미스가 무한 반복되지않도록 주의해야함

---

TLB 의 구성

• 엔트리 개수: 32, 64, 128
• 완전 연관 방식 설계

VPNPFN다른비트

가상 페이지 번호

물리 페이지 번호

valid bit, protection bit, etc…

---

TLB 의 문제: 문맥 교환

TLB 에 존재하는 가상 주소와 실제 주소간의 변환 정보는 TLB 에 탑재시킨 프로세스 에서만 유효함. 새로운 프로세스에서는 이전에 실행하던 프로세스의 변환 정보를 사용하지 않도록 주의해야 함.

프로세스 P1 의 가상페이지 10은 물리 페이지 100, 프로세스 P2의 가상페이지 10은 물리 페이지 170일때 변환시 어떤 프로세스를 위한 항목인지 알 길이 없음

 

즉, TLB 가 정확하고 효율적으로 멀티 프로세스 간의 가상화를 지원하기 위해서는 추가적 기능이 필요함.

핵심 질문: 문맥 교환 시 TLB 내용을 어떻게 관리하는가

문맥 교환 시 실행될 프로세스에게는 이전 프로세스가 사용한 TLB 정보는 의미가 없음. 하드웨어 또는 운영체제는 이러한 문제를 어떻게 해결해야하는가

해결 방법 1. TLB 비우기

장점: 잘못된 변환 정보를 사용하는 상황 방지가능

단점: 새로운 프로세스가 실행될때 데이터와 코드 페이지에 대한 접근으로 인한 TLB 미스 발생

해결 방법 2. ASID 필드 추가

위에서 사용한 TLB 예제에 ASID 정보를 추가하면 TLB의 공간을 공유할 수 있음

 

---

교체 정책

모든 캐시가 그러하듯이 TLB 에서도 캐시 교체 정책이 매우 중요함, TLB에 새로운 항목을 탑재할 때, 현재 존재하는 항목 중 하나를 교체 대상으로 선정해야 함.

핵심 질문: TLB 교체 정책은 어떻게 설계해야 하는가

TLB에 새로운 항목을 추가할 때 어떤 항목을 교체해야 할까? 목표는 미스율을 줄이는 것

LRU (Least-Recently-Used)

메모리 참조 패턴에서 지역성(locality) 를 최대한 활용하는 것이 목적. 사용되지 않은지오래된 항목일수록, 앞으로도 사용될 가능성이 적음

n개의 변환 정보를 저장할 수 있는 TLB가 n+1 페이지들에 대해 반복문을 수행하는 프로그램에서 사용될 경우 최악의 TLB 미스를 생성함

Random

교체 대상을 무작위로 정함, 구현이 간단하고 예상치 못함 예외 상황을 피할 수 있음

요약

• 칩상의 작은 전용 TLB 를 주소 변환 캐시로 사용
  • 대부분의 메모리 참조들은 메인 메모리 상의 페이지 테이블을 읽지 않고도 처리가 가능하게 됨
  • 현대 시스템에서 페이징을 사용하기 위한 필수요소