#15 변환참조버퍼 TLB _ 심화편

TLB, 실제로 얼마나 빨라지는 건데? — 숫자로 보는 TLB 심화

TLB가 정확히 왜 필요한지, VPN·PFN이 실제로 어떻게 캐싱되는지, 지역성 덕분에 TLB hit rate가 왜 높아지는지, Context Switching이 왜 문제고 ASID가 어떻게 해결하는지, 그리고 TLB가 꽉 찼을 때 뭘 빼내는지까지 숫자로 직접 확인해볼게.

---

Paging의 오버헤드, 다시 짚고 가기

Paging으로 메모리를 가상화하면 메모리 접근 하나당 두 번의 작업이 필요해. Page Table에 한 번 접근하고, 거기서 얻은 정보로 실제 메모리에 또 한 번 접근하는 거야. 이 두 번째 접근이 매번 따라붙으니까 느려질 수밖에 없어. 이걸 빠르게 만들려고 나온 게 TLB야.

---

TLB가 뭐야

TLB는 MMU의 일부분이자, 주소 변환을 위한 하드웨어 캐시야. 자주 쓰는 VPN(가상 페이지 번호)이랑 PFN(물리 프레임 번호) 쌍을 저장해두고 있어. CPU가 Paging으로 주소를 변환할 때, Page Table 대신 먼저 TLB를 확인해. 원하는 VPN이 TLB에 있으면 Page Table을 아예 안 거치고 바로 변환이 끝나. 없으면 어쩔 수 없이 Page Table까지 가야 해.

논리 주소는 보통 p | d 형태로 나눠서 봐 — p는 페이지 번호, d는 offset이야. 이 표기법으로 전체 흐름을 그려보자.

논리 주소가 p랑 d로 나뉘고, p를 TLB에서 찾아. TLB에 있으면(TLB hit) 바로 프레임 번호 f를 얻어서 f+d로 물리 주소를 만들어. TLB에 없으면(TLB miss) 메모리에 있는 Page Table까지 가서 p로 인덱싱해 f를 찾고, 이 결과를 TLB에도 새로 등록해둬. 그래야 다음번엔 TLB에서 바로 찾을 수 있으니까.

---

TLB 안에는 정확히 뭐가 들어있어

TLB는 Full Associative 방식으로 관리돼. 이 말은 TLB 안 어느 칸에든 새 항목이 들어갈 수 있고, 검색할 때도 하드웨어가 전체 TLB를 한 번에 병렬로 뒤진다는 뜻이야. 그래서 검색 자체가 굉장히 빨라. 보통 TLB는 32개, 64개, 128개 정도의 항목을 가져.

각 항목에는 VPN·PFN 말고도 이런 정보가 같이 들어있어.

• valid bit: hit/miss 여부
• protection bit: read/write/execute 권한
• ASID(address-space identifier): 어느 프로세스 것인지 구분하는 값
• dirty bit: 수정 여부

---

캐시라는 개념, 이렇게 이해하면 편해

나도 처음엔 캐시가 왜 필요한지 감이 잘 안 왔었는데, 도서관으로 생각하니까 확 이해됐어. 학교 중앙 도서관까지 가서 책 한 권 빌리려면 왕복하는 데만 한참 걸리잖아. 근데 학과 건물 지하에 자주 보는 전공 책들만 따로 모아둔 작은 서재가 있다면, 매번 중앙 도서관까지 안 가고 그 서재에서 바로 빌릴 수 있어.

TLB(그리고 캐시 전반)가 딱 이런 거야. CPU 입장에서 메모리는 이 '중앙 도서관'이야. 접근은 가능한데 왕복이 너무 오래 걸려. 그래서 자주 쓰는 정보만 CPU 가까이에 작게 모아두는 캐시를 두고, 필요할 때마다 거기서 먼저 찾아보는 거지. 실제로 프로세서 성능은 18개월마다 두 배씩 빨라졌는데, 메모리 접근 속도(대역폭·지연시간)는 그만큼 못 따라와서 이 격차를 메우려고 캐시 계층이 점점 중요해진 거야.

---

배열 접근으로 실제 hit rate 확인해보기

TLB가 성능을 얼마나 끌어올리는지 숫자로 직접 보자. page 크기가 16바이트고, 가상 주소 공간이 8비트라고 해보자. 8비트니까 2^8 = 256바이트야(2^8이 196이 아니라 256이라는 점, 계산기 두드려보면 바로 나와). 256바이트를 16바이트씩 나누면 페이지가 총 16개 나와.

이제 이런 코드를 실행한다고 해보자.

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

int가 4바이트니까 a[0]부터 a[9]까지 배열 전체 크기는 40바이트야. 이 배열이 가상 주소 100번지부터 시작한다고 하면, 페이지 테이블은 이렇게 채워져.

a[i]를 순서대로 접근하면서 TLB가 어떻게 움직이는지 정리하면 이래.

1. a[0] 요청 → VPN 6이 TLB에 없으니까 miss, 이때 VPN 6 전체가 TLB에 올라와
2. a[1], a[2] 요청 → 이미 VPN 6이 TLB에 있으니까 hit
3. a[3] 요청 → VPN 7은 아직 없으니까 miss, VPN 7이 새로 올라옴
4. a[4]~a[6] 요청 → hit
5. a[7] 요청 → VPN 8이 없으니까 miss
6. a[8], a[9] 요청 → hit

결국 miss는 a[0], a[3], a[7] 딱 3번이고, 나머지 7번은 전부 hit이야. TLB hit rate = 70%. TLB가 없었다면 10번의 접근마다 매번 Page Table을 거쳐야 했는데, TLB 덕분에 3번만 Page Table에 가면 됐어. 배열이 더 커지면 이 hit rate는 100%에 더 가까워져 — 처음 몇 개만 miss가 나고 나머진 전부 hit이니까.

이 hit rate가 높은 이유가 바로 공간 지역성(Spatial Locality) 때문이야.

---

지역성(Locality), 두 종류

시간 지역성(Temporal Locality): 최근에 접근한 데이터에 또 접근할 가능성이 높다는 뜻이야. 반복문에서 같은 변수를 계속 쓰는 상황이 대표적이야. 하드웨어는 이 특성을 이용하려고 작고 빠른 캐시에 최근 정보를 저장해둬. 캐시가 작으니까 빠르게 찾을 수 있는 거고, 캐시가 커지면 오히려 이 빠른 속도를 잃어버려.

공간 지역성(Spatial Locality): 어떤 요소에 접근했다면, 그 주변 요소에도 접근할 가능성이 높다는 뜻이야. 배열처럼 순차적으로 접근하는 데이터가 딱 이 케이스야. 방금 본 배열 예시가 정확히 이거였고.

---

실제 접근 시간(EAT)은 얼마나 걸릴까

이제 이 hit rate가 실제 시간에 어떤 영향을 주는지 계산해보자.

• TLB hit ratio(α) = 80%
• TLB 검색 시간 = 20ns
• 메모리 접근 시간 = 100ns

TLB hit인 경우엔 TLB 검색(20ns) + 메모리 접근(100ns) = 120ns가 걸려. TLB miss인 경우엔 TLB 검색(20ns) + Page Table 접근(100ns) + 실제 메모리 접근(100ns) = 220ns가 걸려.

EAT = 0.80 × (20 + 100) + 0.20 × (20 + 100 + 100)
    = 0.80 × 120 + 0.20 × 220
    = 96 + 44
    = 140ns

hit ratio 하나가 80%만 돼도 평균 접근 시간이 140ns로 떨어져. 만약 TLB가 아예 없었다면 매번 220ns가 걸렸을 거야. 단위는 항상 ns(나노초)로 맞춰서 계산해야 헷갈리지 않아.

 

 

 

면접 포인트 ( •̀ ω •́ )✧

TLB가 나오게 된 배경과 개념을 설명해 주세요.

Paging은 메모리에 접근할 때마다 Page Table 접근 한 번, 실제 메모리 접근 한 번, 이렇게 두 번의 메모리 참조가 필요해서 느립니다. TLB는 이 문제를 풀려고 나온, 자주 쓰는 VPN-PFN 매핑을 저장해두는 하드웨어 캐시입니다. MMU 안에 있고, Full Associative 방식으로 관리되어 하드웨어가 전체 TLB를 병렬로 검색합니다. TLB에 원하는 정보가 있으면(TLB Hit) Page Table을 거치지 않고 바로 주소 변환이 끝나고, 없으면(TLB Miss) Page Table까지 접근한 뒤 그 결과를 TLB에 등록합니다.

TLB가 메모리 성능을 어떻게 향상시키는지 TLB hit rate와 Spatial Locality 개념으로 설명해 주세요.

배열처럼 연속된 메모리를 접근하는 경우, 같은 page 안에 있는 여러 데이터는 한 번의 TLB miss로 그 page 전체가 캐싱되고 나면 이후 접근은 전부 TLB hit이 됩니다. 이게 바로 공간 지역성 덕분입니다. 실제로 16바이트 page에 10개짜리 int 배열을 접근하면 3번의 miss와 7번의 hit이 나와서 hit rate가 70%가 되고, 배열이 커질수록 이 비율은 100%에 가까워집니다. hit rate가 높을수록 매번 Page Table을 거치는 시간이 줄어들어서 평균 메모리 접근 시간(EAT)이 짧아집니다.

---

Context Switching이 터뜨리는 문제

TLB에 Process A의 VPN 10 정보가 저장돼 있다고 해보자. 여기서 Context Switching이 일어나서 Process B로 넘어갔는데, Process B도 마침 VPN 10을 쓴다고 해보자. 문제는 Process A의 VPN 10이랑 Process B의 VPN 10은 완전히 다른 물리 주소를 가리킨다는 거야. 근데 TLB 입장에서는 VPN 10이라는 값만 보이니까, 이 항목이 A 것인지 B 것인지 구분할 방법이 없어. 이 상태로 그냥 두면 Process B가 Process A의 메모리 영역에 잘못 접근하는 심각한 문제가 생겨.

ASID로 해결하기

하드웨어의 도움을 받아서 TLB에 ASID(Address Space Identifier)라는 필드를 하나 추가해. 프로세스마다 고유한 ASID를 부여하고, TLB 항목에 VPN·PFN이랑 같이 이 ASID도 저장해. 그러면 VPN이 똑같아도 ASID가 다르면 완전히 다른 항목으로 구분돼.

여기서 재밌는 케이스가 하나 더 있어. VPN이 다른데 PFN이 같은 경우도 있을 수 있어.

VPN PFN valid prot ASID

10	101	1	rwx	1
50	101	1	rwx	2

Process 1의 VPN 10이랑 Process 2의 VPN 50이 똑같이 PFN 101을 가리켜. 이건 두 프로세스가 같은 물리 page를 공유하고 있다는 뜻이야(Code 세그먼트 공유 같은 상황). 이렇게 공유하면 물리 메모리에 실제로 올라가는 페이지 수가 줄어드니까 메모리를 그만큼 아낄 수 있어. 이때도 ASID 덕분에 이 항목이 어느 프로세스 것인지는 여전히 구분이 돼.

 

 

 

면접 포인트 ( •̀ ω •́ )✧

TLB 사용 중 Context Switching이 발생하면 어떻게 해결하는지, 두 가지 방안으로 설명해 주세요.

첫 번째 방법은 Context Switching이 일어날 때마다 TLB를 통째로 비우는 겁니다. 안전하긴 한데, 새 프로세스가 실행될 때마다 초반에 TLB miss가 몰려서 오버헤드가 큽니다. 두 번째 방법은 TLB 항목에 ASID(Address Space Identifier)를 추가하는 겁니다. 프로세스마다 고유 ID를 부여해서 VPN이 같아도 ASID로 구분하면, TLB를 비우지 않고도 여러 프로세스의 항목을 동시에 안전하게 유지할 수 있습니다.

---

TLB가 꽉 찼을 땐 뭘 빼낼까

TLB 공간이 다 찼는데 새로운 매핑이 들어와야 한다면, 기존 항목 중 하나를 내보내야 해. 목표는 TLB miss rate를 최소화하는 거야(= TLB hit rate를 최대화하는 것과 같은 말).

대표적인 방법이 두 가지야.

• LRU(Least Recently Used): 가장 오래 안 쓴 항목을 내보내. 시간 지역성을 이용하는 방식이야.
• Random: 그냥 무작위로 하나를 골라서 내보내.

3칸짜리 TLB에 이런 순서로 참조가 들어온다고 해보자.

7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1

LRU로 하나씩 따라가 보면 이렇게 흘러가.

순서 참조 결과 TLB 상태(최근 순)

1	7	miss	7
2	0	miss	0, 7
3	1	miss	1, 0, 7
4	2	miss (7 내보냄)	2, 1, 0
5	0	hit	0, 2, 1
6	3	miss (1 내보냄)	3, 0, 2
7	0	hit	0, 3, 2
8	4	miss (2 내보냄)	4, 0, 3
9	2	miss (3 내보냄)	2, 4, 0
10	3	miss (0 내보냄)	3, 2, 4
11	0	miss (4 내보냄)	0, 3, 2
12	3	hit	3, 0, 2
13	2	hit	2, 3, 0
14	1	miss (0 내보냄)	1, 2, 3
15	2	hit	2, 1, 3
16	0	miss (3 내보냄)	0, 2, 1
17	1	hit	1, 0, 2

하나씩 세보면 총 17번 참조에 11번이 miss야. 그러니까 TLB miss ratio는 11/17 ≈ 64.7%가 돼. (이 수를 18번 참조로 놓고 11/18=61%로 계산하는 경우도 있는데, 실제로 참조 순서를 하나씩 세보면 17번이 맞아서 정확한 비율은 64.7%야.)

4번째 참조인 '2'가 들어올 때, TLB에 있던 7·1·0 중에서 가장 오래 안 쓴 '7'이 빠져나가고 그 자리에 '2'가 들어오는 게 LRU의 핵심이야.

 

 

 

면접 포인트 ( •̀ ω •́ )✧

TLB 공간이 꽉 찼을 때 어떤 프로세스를 빼고 새로운 걸 넣는지, TLB Replacement Policy를 설명해 주세요.

목표는 TLB miss rate를 최소화하는 겁니다. 대표적으로 LRU와 Random 두 가지 방식이 있는데, LRU는 시간 지역성을 이용해서 가장 오래 사용하지 않은 항목을 내보내고 그 자리에 새 항목을 넣습니다. Random은 말 그대로 무작위로 하나를 골라 내보냅니다. LRU가 지역성을 활용하기 때문에 대체로 더 나은 hit rate를 기대할 수 있지만, 참조 패턴에 따라 결과는 달라질 수 있습니다.

---

TLB의 효율은 결국 지역성(locality)에 기대고 있고, 그중에서도 공간 지역성이 대부분의 실제 코드(배열, 순차 접근)에서 hit rate를 확 끌어올려줘. 근데 이 효율은 Context Switching 앞에서 무너질 뻔했고, ASID라는 작은 필드 하나로 그 문제를 풀었어. "캐시는 지역성을 먹고 산다"는 말, TLB에도 그대로 적용되는 셈이야.