[OS] Paging을 가속시킨 하드웨어 캐시: TLB

 

Paging table의 문제점

지난번에 포스팅했던 페이지를 보면 문제가 있었다. 가상 주소 → 물리 주소로 변환하는 과정은 생각보다 꽤 비싸다. 일반적으로는 페이지 테이블(Page Table) 을 한 번 거쳐야 하니까, CPU 입장에선 "메모리 한 번 읽으려는데 두 번이나 가야 하는 것"이다.

 

 

위 사진을 보면 메모리에서 PTE를 읽을때와, 메모리에서 PA 컨텐츠를 읽을 때 총 2번의 메모리 접근이 일어난다.

 

그래서 등장한 게 바로 , TLB (Translation Lookaside Buffer)이다. 이름만 보면 뭔가 거창하지만, 쉽게 말하면 주소 변환 캐시(address translation cache)다.

 

 

---

 

TLB: 주소 변환의 캐시

TLB는 CPU 안의 MMU(Memory Management Unit) 안에 있는 작은 하드웨어 캐시다. 역할은 단순하다.

"최근에 자주 썼던 가상주소 → 물리주소 변환 결과를 기억해두자."

 

 

즉, 페이지 테이블에 직접 가지 않고 "이전에 썼던 변환 결과가 있을지" TLB를 먼저 확인하는 거다.

• TLB hit → 바로 물리주소로 접근 (페이지 테이블 접근 생략 -> 빠름)
• TLB miss → 1. 페이지 테이블까지 가서 찾고, TLB를 업데이트 2. 재접근 시 바로 물리주소로 접근 가능

 

 

이런 식으로 "다음에 또 쓰일지도 모르는 주소 변환"을 캐싱하는 것이다.

 

 

 

왜 TLB가 빠를까?

TLB는 작고, CPU에 아주 가까운 곳에 있다. 그래서 접근 시간이 1 cycle 정도밖에 안 걸린다.
반면, TLB miss가 나서 실제 메모리를 다녀오면 100 cycle 가까이 걸린다.

게다가 프로그램은 locality (지역성) 을 갖는다.

• Temporal locality: 방금 쓴 데이터를 또 쓸 확률이 높다. (시간적)

• Spatial locality: 근처 주소의 데이터를 곧 접근할 가능성이 높다. 배열을 떠올리면 금방 이해 될거다. (공간적)

 

 

 

결국 CPU는 비슷한 주소를 반복적으로 쓰는 습성이 있어서,TLB 캐싱이 효과를 극대화시킨다.

 

 

 

예시: 배열 접근

예를 들어, 배열 a[10]을 순서대로 접근한다고 하자.

 

 

처음 a[0]에 접근할 때는 TLB miss가 난다. 하지만 그 이후의 a[1], a[2] 등은 같은 페이지 안에 있으니 TLB hit가 된다. (여기서 페이지 크기는 16B로 가정한다)

 

 

a[0], a[3], a[7]을 접근할때만 miss가 나고 나머지에 접근할때는 hit이 된다. 결국 전체 10번 접근 중 7번은 hit — 70% hit rate. 이게 바로 spatial locality의 힘이다.

 

 

---

 

 

근데 TLB miss는 누가 처리할까?

CPU 아키텍처마다 다르다.

• x86 (CISC) 계열은 하드웨어가 직접 처리한다.
  CPU가 페이지 테이블까지 가서 PTE(Page Table Entry)를 찾고, TLB에 업데이트까지 다 함.
• MIPS, RISC-V 같은 RISC 계열은 OS(소프트웨어)가 처리한다. TLB miss가 나면 exception이 발생해서 커널 모드로 들어가고, OS가 직접 페이지 테이블을 탐색하고 TLB를 갱신해준다. 이걸 software-managed TLB 라고 부른다. 하드웨어가 다 해주는 것보다 조금 느리지만, OS 입장에서 제어권이 더 많다.

두 방식의 큰 차이는 Miss가 발생했을 때 하드웨어에서 직접 처리하는지/ OS에게 알려주는지이다. 

 

 

Software-Managed TLB

앞에서 말했듯, RISC 계열 CPU는 OS가 직접 TLB miss를 처리한다. 근데 여기엔 생각보다 신경 써야 할 부분이 많다.

예를 들어 TLB miss가 나면 하드웨어가 단순히 예외발생처리를 하고 OS에게 책임을 넘긴다.
그럼 OS가 하는 일은 다음과 같다.

1. 현재 실행 중이던 명령을 잠시 멈춘다.
2. 커널 모드로 전환한다.
3. TLB miss handler 라는 특수한 커널 코드를 실행한다.
4. 페이지 테이블을 찾아서 해당 변환 정보를 TLB에 추가한다.
5. 그 명령을 다시 같은 위치에서 재시도한다.

여기서 중요한 게 바로 "같은 위치에서 재시도한다"는 거다.

 

따라서 Return-from-trap 행동이 다르게 된다.

• 보통 system call 같은 트랩은 다음 명령으로 넘어가지만,
• TLB miss는 "그때 못 했던 그 메모리 접근"을 다시 해야한다.

따라서 하드웨어는 trap 타입에 따라서 Program Counter (PC) 를 다르게 저장해야 한다.

 

 

 

또한 TLB miss 핸들러 코드 자체가 TLB miss를 일으킨다면?

 

TLB miss → 핸들러 → 또 miss → 또 핸들러 이건 그냥 지옥의 무한 루프이다.

그래서 이런 문제를 피하려고 OS는 두 가지 방법을 쓴다:

• 핸들러 코드는 물리 메모리 주소로 직접 접근하게 함 (주소 변환 X)
• 또는 TLB의 일부 엔트리를 “wired entry”로 예약해둬서, 핸들러 관련 주소는 항상 TLB hit이 나게끔 함

즉, TLB miss 처리 코드가 TLB miss를 내지 않게 하는 역설적인 예방책이 필요한하다.

 

 

---

 

TLB의 구성

TLB는 일종의 작은 데이터베이스처럼 생겼다. 각 줄(row)은 하나의 변환 정보를 나타내고, 이런 필드들을 갖고 있다.

VPN (Virtual Page Number)	가상 페이지 번호
PFN (Physical Frame Number)	물리 프레임 번호
Valid bit	유효한 변환인지 여부
Protection bits	read/write/execute 같은 접근 권한
ASID	어떤 프로세스의 주소 공간인지 식별
Dirty bit 등	페이지가 수정되었는지 표시

 

 

그리고 보통 TLB는 fully associative 구조라서 변환이 반드시 몇 번째 칸에 있어야 된다는 제약이 없다.
CPU가 병렬로 전부 검색해서 VPN이 맞는 엔트리를 찾는다. (물론 이게 빠른 대신, 하드웨어 설계가 좀 더 복잡하고 비싸다.)

 

캐시의 구조는 아래와 같다.

 

 

---

 

Cache vs. TLB 비교

TLB를 캐시라고 했으니까, 그럼 일반 캐시(L1/L2 cache)랑 뭐가 다른데? 라는 의문이 생긴다.

 

	Cache	TLB
저장 대상	데이터나 명령어	주소 변환(VPN → PFN)
비교 대상	메모리 주소	가상 페이지 번호 (VPN)
구조	Direct / Set / Fully associative 다양	거의 항상 Fully associative
일관성 문제	메모리와의 coherence 유지 필요	페이지 테이블과의 consistency 유지 필요 (OS의 역할)
갱신 방식	Write-back / Write-through	페이지 테이블 업데이트 시 TLB flush 필요

 

 

즉, 둘 다 메모리 접근을 빠르게 해주는 캐시지만, TLB는 주소 변환용, Cache는 데이터 저장용이다.

 

 

 

---

 

 

TLB 문제: Context Switch와 

 

이제 조금 현실적인 상황으로 가보자. CPU는 여러 프로세스를 빠르게 바꿔가며 실행하고, 그걸 Context Switch라고 한다.
그런데 TLB에는 '가상주소 → 물리주소' 변환 정보가 남아 있다는 게 문제다. 이 변환 정보는 현재 실행 중인 프로세스 기준으로 만들어진 거라, 다른 프로세스 입장에선 완전 엉뚱한 주소일 수 있다.

 

 

예를 들어, 그림과 같이 프로세스 A의 가상 주소 10이 물리 주소 100으로 매핑돼 있었는데, 이걸 B가 그대로 써버리면? B는 자기가 자기 메모리를 읽는 줄 알지만, 실제로는 A의 데이터를 엿보게 되는 거다.

이건 보안적으로도, 안정성 면에서도 좋지않다.

 

 

 

해결책은 다음 두 가지다.

1. TLB flush – 새 프로세스 실행 전에 TLB 비우기 (단, 성능 손해 큼)
2. ASID(Address Space ID) – 각 프로세스별로 TLB 엔트리에 고유 ID를 붙이기

 

Solution 1: Flush TLB (모두 지우기)

그래서 가장 단순한 해결책이 등장했다. Context Switch가 일어날 때마다 TLB를 비워버리자.

방법은 간단하다. TLB의 valid bit를 전부 0으로 만들어서 "지금 저장된 건 다 무효야"라고 표시하는 거다.

다음 프로세스가 실행될 땐, 필요한 주소 변환 정보를 새로 페이지 테이블에서 읽어오고, TLB를 다시 채워나간다. 이게 바로 TLB Flush 방식이다.

 

근데 Flush TLB의 문제는 이 방식이 진짜 느리다.

 

Context Switch는 생각보다 자주 일어난다. 그런데 그때마다 TLB를 비워버리면, 다음 프로세스가 실행될 때 계속 TLB miss가 나는 거다. 즉, CPU가 캐시를 매번 갈아엎는 꼴이라서 성능이 크게 떨어진다.

 

 

 

Solution 2: ASID (Address Space ID) - 구분하는 ID를 두자

그래서 등장한 게 ASID(Address Space Identifier) 라는 개념이다. 말 그대로 이 변환 정보가 어느 프로세스의 주소 공간에 속한 것인지 식별할 수 있게 해주는 ID다.

이제 TLB 엔트리 하나하나에 ASID 필드가 붙는다.

 

이러면 CPU는 같은 VPN(가상 페이지 번호)이라도 ASID가 다르면 다른 프로세스의 주소라고 인식할 수 있다.

즉, Context Switch가 일어나도 굳이 TLB를 싹 비우지 않아도 된다.

 

이 방식 덕분에 Context Switch 후에도 TLB hit를 유지할 수 있다.
성능적으로는 엄청난 차이다.

 

 

Another Case: 페이지 공유

ASID를 쓰면 생기는 또 다른 장점이 있다. 서로 다른 프로세스가 같은 물리 페이지를 공유할 수 있다는 점이다.

 

예를 들어 보자.

• 프로세스 A는 자기 가상 주소 공간의 10번째 페이지(VPN=10)에 물리 페이지 101을 매핑하고 있다.
• 프로세스 B는 자기 주소 공간의 50번째 페이지(VPN=50)에 같은 물리 페이지 101을 매핑했다.

즉, 같은 PFN을 서로 다른 가상 주소로 공유하는 셈이다.

 

이런 공유는 여러 상황에서 유용하다.

• 여러 프로세스가 공통 라이브러리 (예: libc) 를 공유할 때
• IPC(프로세스 간 통신) 를 위해 메모리를 공유할 때

결국 물리 메모리 사용량을 줄이고, 프로세스 간 협력을 더 효율적으로 만들 수 있다.

 

 

 

---

 

 

TLB Replacement Policy 

 

이제 진짜 현실적인 질문 하나 해보자. "그럼 TLB가 꽉 차면, 새로운 변환을 어디에 넣지?"

 

그렇다.TLB도 결국 캐시니까, 한정된 공간(보통 32~128 엔트리 정도) 안에서만 정보를 저장할 수 있다.

그래서 새로운 주소 변환을 넣을 때는 기존의 어떤 엔트리를 내보내야(evict) 한다.

 

이때 가장 많이 쓰이는 방법이 바로 LRU (Least Recently Used), 즉 "가장 오랫동안 안 쓰인 놈부터 내보내기" 전략이다.

 

 

이건 메모리나 캐시에서도 아주 흔히 등장하는 정책이다. 프로그램의 locality (지역성) 때문에 흔히 등장한다. 최근에 쓴 주소들은 다시 쓸 확률이 높고, 오래된 주소는 버려도 큰 타격이 없기 때문이다.

 

 

 

---

 

 

A Real TLB Entry 

지금까지는 개념적으로 "VPN이랑 PFN이 들어있다"고만 했는데, 실제로 CPU 내부의 TLB 엔트리는 훨씬 정교하다. 예를 들어 MIPS R4000 기준으로 보면, TLB 엔트리 하나가 64비트로 구성되어 있다

 

VPN (Virtual Page Number)	가상 페이지 번호. 어떤 가상 주소 영역인지 구분
PFN (Physical Frame Number)	물리 프레임 번호. 실제 물리 메모리 위치
G (Global bit)	모든 프로세스가 공유하는 페이지인지 표시
ASID (Address Space ID)	어떤 프로세스의 주소 공간에 속하는지 구분
C (Coherence bit)	하드웨어 캐시 일관성 정책 (어떻게 캐싱할지)
D (Dirty bit)	이 페이지가 쓰기(write)로 수정되었는지 표시
V (Valid bit)	이 엔트리가 유효한 주소 변환인지 여부

 

이 중에서 특히 중요한 건 ASID, D, V 세 개다.

• ASID: 프로세스 구분용. Context Switch 후에도 안전하게 재사용 가능.
• Dirty bit: 페이지가 수정되었는지 표시 → 나중에 디스크로 쓸 때 필요.
• Valid bit: 단순히 "이 변환 정보가 쓸모 있는가?" 판단.

 

결국 이 64비트 안에 운영체제, 하드웨어, 보안, 성능 관련 정보가 들어가 있는 것이다.

 

 

---

 

 

Summary

이제 전체 내용을 한 번 정리해보자.

• TLB (Translation Lookaside Buffer) 는 MMU(Memory Management Unit) 안의 하드웨어 캐시로, 가상주소 → 물리주소 변환 결과를 저장한다.
• 덕분에 CPU는 페이지 테이블을 매번 참조하지 않아도 빠르게 메모리에 접근할 수 있다.
• TLB miss 시에는 하드웨어(x86)나 소프트웨어(RISC)가 페이지 테이블을 조회하고, 변환 결과를 TLB에 추가한다.
• Software-managed TLB 는 OS가 직접 miss를 처리하므로 trap 복귀 주소 관리나 무한 루프 방지 같은 세부 로직이 필요하다.
• Context Switch 문제는 ASID(Address Space ID)로 해결할 수 있다. 덕분에 프로세스가 바뀌어도 TLB flush 없이 성능 유지 가능하다.
• TLB Replacement Policy 는 주로 LRU 기반이며, locality 덕분에 꽤 효율적이다.
• 실제 TLB 엔트리에는 VPN, PFN뿐 아니라 Valid bit, Dirty bit, ASID, Global bit 등 다양한 제어 비트가 들어 있다.

 

 

 

 

 

 

출처: 경북대학교 한명균 교수님, “운영체제” 강의 자료