[OS] TLB (Translation Lookaside Buffer)

1. TLB 의미와 구성

TLB는 Paging에서 문제가 됐던 잦은 메모리 접근을 보완하기 위한 방법이다.

자주 사용하는 Page Table Entry의 경우 MMU의 SRAM에 캐싱하는 것이다.

기존 Paging은 아래와 같은 방법으로 진행되었다.

위 사진에서 보다시피 페이지 테이블은 메인 메모리에 존재해서 CPU는 메인 메모리에 최소 두 번은 접근해야 원하는 데이터를 얻을 수 있다.

1) 페이지 테이블에 접근

2) 페이지 테이블을 기반으로 실제 메모리로 접근

따라서 이러한 메모리 낭비를 줄이고자 TLB를 사용한다.

TLB를 사용하면 Address translation 과정이 아래와 같이 바뀌게 된다.  PTEA(PTE Address)

 

- TLB 정의 및 역할

• 가상 메모리 주소를 물리적인 주소로 변환하는 속도를 높이기 위해 사용되는 캐시
• 최근 일어난 가상 메모리의 주소와 물리 주소의 변환 테이블 저장
• 일종의 주소 변환 캐시

 

---

 

2.  TLB의 장단점

 

- 장점

: CPU의 MMU 안에서 해결되므로 속도가 빠르다.

 

MMU란?
(Memory Management Unit, 메모리 관리 장치)

• CPU 코어 안에 탑재되어 가상주소를 물리주소로 변환하고 메모리를 보호하는 역할을 함
• MMU를 사용하면 CPU가 각 메모리에 접근하기 전에 메모리 주소 번역 작업을 수행함
• MMU는 RAM을 여러 페이지로 나눠 각 페이지를 하나의 독립된 항목으로 처리함

👉 모든 프로세스마다 같은 주소를 사용 가능

👉 CPU는 프로세스 관리가 쉬워짐. 서로 떨어진 데이터를 연속적으로 표현 가능

 

---

 

- 단점

: 요청한 정보가 TLB에 없다면 어쩔 수 없이 Page Table에서 가져와야 한다.

 

---

 

3. TLB entry

 

 

• 가상 페이지 번호 (VPN, Virtual Page Number)
  • 가상 주소의 상위 비트. 특정 페이지를 식별함
• 페이지 프레임 번호 (PFN, Page Frame Number)
  • 물리적 메모리에서 페이지가 위치하는 프레임을 식별함
• 유효 비트(Valid Bit)
  • 해당 엔트리가 유효한지 여부를 나타냄
• 참조 비트(Reference Bit)
  • 페이지가 최근에 참조되었는지 여부를 나타냄(다양한 페이지 교체 알고리즘에 사용됨)
• 수정 비트(Dirty Bit)
  • 페이지가 수정되었는지 여부를 나타냄. 수정된 페이지는 페이지 아웃 시 디스크에 기록되어야 함

 

---

4. TLB의 동작 원리

1) TLB 조회: CPU에서의 정보로 TLB 탐색

2) TLB에 있으면(=  TLB hit) Page Table을 거쳐갈 필요 없이 가상 주소를 실제 주소로 변환함

3) TLB에 없으면(= TLB miss) Memory에 있는 Page Table에서 가상 주소에 해당하는 정보를 가져와서 실제 주소로 변환함

 

---

 

5. TLB 사용 시 Context Switching이 발생한다면?

 

- 문제점

• TLB 엔트리의 유효성 👉 주소 변환 오류
  • TLB는 특정 프로세스의 가상 주소를 물리적 주소로 변환하는 매핑 정보를 캐시한다. 컨텍스트 스위칭이 발생하면 새로운 프로세스가 실행되기 때문에 기존의 TLB 엔트리는 새로운 프로세스의 주소 공간과 맞지 않게 된다.  이런 상황에서 잘못된  TLB 엔트리를 사용할 경우, 주소 변환 오류가 발생할 수 있다.
• 성능 저하
  • TLB 미스 증가: 컨텍스트 스위칭 후 TLB를 플러시하면, TLB에 저장된 매핑 정보가 모두 사라진다. 새로운 프로세스가 실행될 때, 자주 사용하는 주소 매핑 정보가 TLB에 없기 때문에, 초기 메모리 접근 시 TLB 미스가 증가하게 된다. 👉 페이지 테이블 접근이 증가해 메모리 접근 속도가 느려질 수 있다.
  • 캐시 효과 감소: TLB는 캐시의 일종으로, 자주 사용하는 매핑 정보를 빠르게 제공하여 메모리 접근 시간을 단축한다. 그러나 TLB 플러시로 인해 캐시된 정보가 사라지면 캐시의 효과가 감소하게 된다.
• 하드웨어 자원 낭비
  • 추가적인 하드웨어 복잡성: 프로세스 식별자를 사용하려면, 각 TLB 엔트리에 추가적인 필드를 포함해야 하며, 하드웨어 설계가 복잡해질 수 있다. 👉 TLB의 크기를 증가시키고, 하드웨어 자원의 효율성을 떨어뜨릴 수 있다.

 

---

 

- 해결 방법

해결 방법은 크게 두 가지가 있다.

TLB 플러시(TLB Flush)와 프로세스 식별자(Tagging)이다.

 

TLB 플러시(TLB Flush)

• 정의: 컨텍스트 스위칭이 발생할 때, 현재 TLB에 저장된 모든 엔트리를 무효화하는 방법
  👉 새로운 프로세스의 주소 매핑 정보가 정확히 반영될 수 있음
• 과정
  • 1) 컨텍스트 스위칭 발생: CPU가 실행 중인 프로세스를 변경해야 할 때, 운영 체제가 컨텍스트 스위칭을 수행함
  • 2) TLB 플러시: 현재 TLB에 저장된 모든 엔트리를 무효화함
  • 3) 새 프로세스 로드: 새로운 프로세스가 실행되기 시작하면서, 필요한 페이지가 접근될 때 TLB에 다시 매핑 정보를 로드함
• 장점
  • 구현이 단순함
  • TLB의 일관성을 보장 가능
• 단점
  • 모든 TLB 엔트리를 무효화함
    👉 초기 메모리 접근 시 TLB 미스가 증가하여 성능 저하가 발생할 수 있음

 

---

 

프로세스 식별자
(Tagging)

• 정의: 프로세스 식별자(tagging) 방법은 각 TLB 엔트리에 프로세스 ID(또는 주소 공간 ID)를 추가하는 방법
  👉 TLB 엔트리가 어느 프로세스에 속하는지 명확히 구분할 수 있음
• 과정
  • 1) TLB 엔트리 태깅: TLB 엔트리에 해당 매핑 정보가 속한 프로세스의 식별자를 포함함
  • 2) TLB 조회 시 검증: TLB 조회 시 현재 실행 중인 프로세스의 ID와 TLB 엔트리의 ID를 비교하여, 일치하는 경우에만 해당 엔트리를 사용함
  • 3) 컨텍스트 스위칭 발생: 새로운 프로세스가 실행될 때, TLB의 다른 프로세스 ID를 가진 엔트리는 자동으로 무효화됨
• 장점
  • TLB를 플러시할 필요가 없음
    👉 컨텍스트 스위칭 후 초기 메모리 접근 시 TLB 미스가 발생하지 않아 성능이 향상됨
• 단점
  • TLB 엔트리에 추가적인 식별자 필드가 필요함
    👉 하드웨어 구현이 더 복잡해질 수 있음

 

---

 

6. TLB Replacement policy

TLB가 꽉 찼을 때, 새로운 프로세스의 주소 변환 정보를 TLB에 추가하려면 기존의 엔트리 중 하나를 제거해야 한다.

이때 TLB 교체 정책(TLB Replacement policy)이 사용된다.

TLB 교체 정책이란 어떤 엔트리를 제거할지 결정하는 알고리즘이다.

주요 TLB 교체 정책에는 FIFO, LRU, Random, LFU가 있다.

대부분의 시스템에서 가장 많이 사용되는 TLB 교체 정책은 LRU이므로 LRU에 대해서 설명하고자 한다.

 

- LRU (Least Recently Used)

• 정의
  • 가장 오랫동안 사용되지 않은 엔트리를 제거하는 방식
  • 각 엔트리의 최근 사용 시점을 추적하여 결정함
• 과정
  • 1) 새로운 엔트리를 TLB에 추가할 때, TLB가 가득 차 있는지 확인함
  • 2) 가득 차 있다면, 가장 오랫동안 사용되지 않은 엔트리를 찾음
  • 3) 해당 엔트리를 제거하고, 새로운 엔트리를 TLB에 추가함
  • 4) 새로운 엔트리의 사용 시점을 갱신함
• 장점: 자주 사용되는 엔트리가 더 오래 유지될 수 있어 효율적임
   👉 이러한 이유로 LRU가 많이 사용됨
• 단점: 사용 시점을 추적하는 데 추가적인 하드웨어나 소프트웨어 복잡성이 필요함

 

---

 

참고

• https://velog.io/@becooq81/%EC%9A%B4%EC%98%81%EC%B2%B4%EC%A0%9C-TLB
• https://yeongjaekong.tistory.com/m/77
• https://devfancy.github.io/OS-19-TLB/
• https://github.com/devSquad-study/2023-CS-Study/blob/main/OS/os_tlb_advanced.md