TLB(Translation Lookaside Buffer)란?
- 가상 메모리 주소를 물리 메모리 주소로 변환하는 정보를 빠르게 접근하기 위한 캐시이며,
MMU의 의 일부다. - 프로그램이 사용하는 가상 주소와 실제 데이터가 저장된 물리 주소 간 변환을 가속화함으로써
시스템 성능을 향상시킨다. 모든 메모리 접근 요청에 대해 페이지 테이블을조회하면 상당한성능 저하가 발생한다.- TLB는 가장
최근이나자주사용되는주소 변환 정보를 저장함으로써, 이러한 페이지 테이블 접근 없이 빠른 주소 변환을 가능하게 한다.
TLB의 기본 알고리즘
가상주소에서 가상 페이지 번호(virtual page number,VPN)을 추출한 후, 해당 VPN이 TLB에 존재하는 지 검사한다.
-
만약 존재하는 경우 TLB 히트라고 한다.
- TLB가 변환 값을 가지고 있다는 것을 뜻한다.
- TLB 항목에서 페이지 프레임 번호(page frame number, PFN)를 추출할 수 있다.
- 해당 접근 권한 검사가 성공하면, 그 정보를 원래 가상 주소의 오프셋과 합쳐서 원하는 물리주소 (PA)를 구성하고, 메모리에 접근할 수있다.
-
만약 존재하지 않는다면 TLB 미스라고 한다.
- 하드웨어가 변환 정보를 찾기 위해서 페이지 테이블에 접근한다.
- 프로세스가 생성한 가상 메모리 참조가 유효하고 접근 가능하다면, 해당 변환 정보를 TLB로 읽어들인다.
- 페이지 테이블 접근을 위한 메모리 참조 때문에 매우 시간이 많이 소요되는 작업이다.
- TLB가 갱신되면 하드웨어는 명령어를 재실행한다.
- 이번에는 TLB에 변환 정보가 존재하므로, 메모리 참조가 빠르게 처리된다.
-
TLB는 프로세싱 코어와 가까운 곳에 위치하고, 매우 빠른 하드웨어로 구성되어 있기 때문에 TLB에서의 주소 변환 작업은 많은 비용이 들지 않는다.
-
하지만
미스가 발생하는 경우페이지 테이블을 접근하여 변환 정보를 찾는 메모리 참조 과정이 추가 되기 때문에페이지 비용이 커진다. -
페이지 테이블이
복잡한 구조를 갖게 된다면, 메모리 참조 과정도 복잡해지기 때문에 미스가 자주 발생한다면 프로그램은상당히 느려지게 된다.(메모리 접근 연산은 CPU연산에 비해 매우 오랜 시간이 걸리기 때문에)
배열 접근에서의 TLB
-
메모리 시작 주소인 가상 주소 100에서 시작하는 10개의 4바이트 정수로 이루어진 배열을 가정한다. 이 배열은 16바이트 페이지를 가진 작은 8비트 가상 주소 공간에 배치되어 있으며, 가상 주소는 4비트 VPN(가상 페이지 번호)과 4비트 오프셋으로 나뉜다.
-
아래 표는 크기가 16바이트인 16개의 페이지로 구성된 가상 주소 공간을 도식적으로 표현 하고있다.
-
배열의 첫 항목(a[0])은 (VPN = 06 , Offset = 04)에서 시작하며 세 개의 4바이트 정수가 페이지에 들어갈 수 있다.(a[0],a[1],a[2])
| VPN | Offset 00 | Offset 04 | Offset 08 | Offset 12 |
|---|---|---|---|---|
| VPN=00 | ||||
| ... | ||||
| VPN=06 | a[0] | a[1] | a[2] | |
| VPN=07 | a[3] | a[4] | a[5] | a[6] |
| VPN=08 | a[7] | a[8] | a[9] | |
| ... | ||||
| VPN=15 |
배열의 원소의 합을 구하는 간단한 코드를 살펴보자.
int sum = 0;
for (i = 0; i < 10; i++) {
sum += a[i];
}- 메모리 접근을 단순화 하기 위해 변수 i, sum 그리고 명령어를 위한 메모리 접근은 무시한다.
- 반복문이 실행되고 배열의 첫번째 항목인 (a[0])에 접근한다.
- 가상주소 100번이고 이 주소를 가상 페이지 번호(VPN)와 오프셋으로 분리한다.
- 하드웨어는 TLB에서 해당 VPN을 키로 사용하여 물리 페이지 번호(PFN)를 검색한다.
- TLB가 처음에 완전히 초기화 되어있다고 가정할 때 TLB 미스가 발생한다.
- 미스가 발생하면 해당 VPN 06번에 대한 물리 페이지 번호를 운영 체제의 도움을 받아 메모리의 페이지 테이블에서 찾아 TLB를 갱신한다.
- 다음은 a[1]을 읽는다 VPN 06에 대한 정보가 TLB에 존재하므로 a[1],a[2]는 TLB 히트가 발생한다.
- a[3]를 읽을 경우 TLB 미스가 발생하고 이전 과정을 진행 후 a[4],a[5],a[6]는 TLB 히트가 발생한다. 이후 a[7],a[8],a[9]도 같은 과정을 반복한다.
배열 원소를 읽는 TLB동작을 정리해 보면 미스, 히트, 히트, 미스, 히트, 히트, 히트, 미스, 히트, 히트, 히트가 되며 TLB 히트 비율은 70%가 된다. 배열 예제 코드가 루프 종료 후에도 배열을 사용한다면 시간 지역성으로 인해 TLB 히트율이 더 높아진다.(a[3],a[4],a[5],a[6] 은 공간지역성과 연관이 있다.)
TLB 미스처리는 누가 할까?
1. CISC(complex-instruction set computers : 복잡한 명령어들로 구성된 컴퓨터)
- 하드웨어 엔지니어들은 sneaky한 운영체제 개발자들의 특성 때문에 그들을 완전히 신뢰할 수 없었고 TLB 미스를 하드웨어가 처리하도록 설계했다.
- 처리하기 위해서 하드웨어는 페이지 테이블에 대한 명확한 정보를 가지고 있어야 했고, page-table base register를 통해서 정확한 형식을 파악하고 있었다.
- TLB 미스 발생시 하드웨어의 처리
- 페이지 테이블에서 원하는 페이지 테이블 엔트리를 찾고
- 필요한 변환 정보를 추출한다.
- TLB를 갱신한 후
- TLB 미스가 발생한 명령어를 재실행한다.
Intel x86 CPU는 하드웨어로 관리 되는 TLB의 대표적인 예로 멀티 레벨 페이지 테이블(multi-level page table)을 사용하며 CR3 레지스터가 페이지 테이블 주소를 갖고 있다.
2. RISC(reduced instruction set computing)
- CISC보다 최근에 등장한 컴퓨터 구조로 MIPS R10K나 Sun의 SPARC v9가 대표적이다.
- RISC 기반의 컴퓨터는 소프트웨어 관리 TLB를 사용한다.
- TLB 미스 발생시 소프트웨어의 처리
- TLB 미스 발생시 하드웨어는 exception 시그널을 발생시킨다.
- exception 시그널을 받은 운영체제는 명령어 실행을 중지하고 실행모드에서 커널모드로 변경한다.
- 커널 코드 실행을 준비할 수 있는 커널모드로 변경이 되면 트랩 핸들러(trap handler TLB 미스 처리를 담당하는 운영체제 코드)를 실행한다.
- 트랩핸들러는 페이지 테이블을 검색하여 변환 정보를 찾아 TLB를 갱신한 후 리턴한다.
- 하드웨어는 리턴 신호를 받고 명령어를 재실행하며 갱신된 TLB에서 히트가 발생한 후 계속된다.
TLB 미스를 처리하는 트랩핸들러는 시스템 콜 호출 시 사용되는 트랩 핸들러와 차이가 있다?
- 시스템 콜은 트랩 핸들러에서 리턴 후 시스템 콜을 호출한 명령어의 다음 명령어를 실행한다.
- TLB는 TLB 미스 처리후, 트랩에서 리턴하면 트랩을 발생시킨 명령어를 다시 실행하며, 재실행 시에는 TLB에서 히트가 발생한다.
트랩 발생시 운영 체제는 트랩 핸들러가 종료되었을 때 다시 실행할 명령어 주소(Program Counter 값)을 저장한다.
- 트랩의 발생 원인에 따라 현재 명령어의 PC값 혹은 다음 명령어의 PC값을 저장한다.
TLB 미스 발생시 TLB미스가 무한 반복 되지 않게 주의하기
해결방안
1. TLB 미스 핸들러를 물리 메모리에 위치시키기
- TLB 미스 핸들러의 주소는 핸들러의 '물리' 주소로 표시 되어 해당 TLB 미스 핸들러는 unmap되어 있어 주소 변환이 필요 없다.
2. TLB의 일부 핸들러 코드 주소를 영구히 할당하여 저장한다.
- 이렇게 되면 TLB핸들러는 항상 TLB에서 히트된다. 이를 연결(wired)변환 이라고 한다.
TLB를 소프트웨어로 관리하는 방식의 장점은 유연성, 단순함이다.
미스가 발생했을 때 하드웨어는 별로 할 일이 없으며 하드웨어는 단지 예외를 일으키고 운영체제의 TLB미스 핸들러가 나머지 일을 한다.
TLB의 구성
- TLB는
완전 연관 캐시 방식을 주로 사용하며, 32, 64, 128개의 엔트리를 가진다. - 완전 연관 방식에서
변환 정보는TLB 내 어디는 위치할 수 있으며, 원하는 변환정보를 찾는 검색은 TLB 전체에서병렬적으로 수행된다.- 변환 주소를 찾을 때, 하드웨어는 TLB의 각 항목을 동시에 검색한다.
VPN | PFN | 다른 비트들 //TLB의 구성- 변환 정보 저장 위치에 제약이 없도록, 각 항목마다 가상 페이지 번호와 물리번호가 있다.
- 가상 페이지 번호를 키로 사용해 물리 페이지 번호를 찾는다. TLB에는 유효 비트와 보호 비트 같은 다양한 제어 비트들이 포함되어 있어, 변환의 유효성과 페이지 접근 권한을 관리한다.
- 이외에 주소 공간 식별자(address-space identifier), 더티 비트(dirty bit) 등이 있다.
TLB에서의 문맥교환
- TLB에 있는 가상 주소와 실제 주소 간의 변환 정보는 그것을 탑재시킨 프로세스에서만 유효하다. 다른 프로세승에게들에는 의미가 없다.
- TLB 사용시 프로세스간 문맥 교환시 새로운 프로세스에서는 이전에 실행하던 프로세스의 변환 정보를 사용하지 않도록 주의해야한다.
문맥 교환시 TLB 내용을 어떻게 관리하는가?
1. 문맥 교환시 다음 프로세스가 실행되기 전에 기존 TLB를 비우는 방법
- 소프트웨어 기반의 시스템의 경우
- 특별한 하드웨어 명령어를 사용하여 이 목적을 달성할 수 있다.
- 하드웨어로 관리되는 TLB의 경우
- 페이지 테이블 베이스 레지스터가 변경될 때 비우기를 시작할 수 있다.(운영체제는 문맥교환을 할 때 PTBR을 어쨌든 변경해야한다.)
둘 중 어는 경우든 비우는 작업은 모든 vaild bit를 0으로 설정하는 것이다.
- 문맥교환 할 때마다 TLB를 비우면 잘못된 변환 정보를 사용하는 상황을 방지할 수 있지만, 이 방식은 공짜가 아니며 새로운 프로세스가 실행될 때, 데이터와 코드 페이지에 대한 접근으로 TLB미스가 발생하게 된다. -> 문맥 교환이 빈번히 발생하면서 성능에 큰 부담 발생
2. TLB 내에 주소 공간 식별자(address space identifier, ASID) 필드 추가하기
- ASID는 프로세스 식별자(process identifier, PID)와 대략적으로 유사하다.
- 단, ASID는 좀 더 적은 비트를 갖는다. EX) ASID는 8비트 PID는 32비트
- 주소 공간 식별자를 사용할 경우, 프로세스 별로 TLB 변환 정보를 구분할 수 있으며, 하드웨어는 현재 어떤 프로세스가 실행 중인지 파악하고 있어야 한다.
- 이를 위해, 문맥 전환 시, 운영체제는 새로운 ASID 값을 정해진 레지스터에 탑재한다.
- 서로 다른 VPN을 갖는 두 개의 다른 프로세스들의 두 항목이 동일한 물리 페이지를 가르키고 있는 경우 코드 페이지를 공유하면 프로세스가 사용하는 물리 페이지의 수를 줄일 수 있다.
TLB 캐시 교체정책
미스율을 줄이거나 히트 비율을 증가시키키 위해 어떤 항목을 교체해야하는가?
- LRU(least-recently-used, LRU 최저 사용 빈도)
- 메모리 참조 패턴에서 지역성을 최대한 활용하는게 목적
- 사용된지 오래된 항목일수록, 앞으로 사용될 가능성이 작으며, 교체 대상으로 적합하다.
- Random
- 교체 대상을 무작위로 정한다.
- 때때로 잘못된 결정을 내릴수도 있다.
- 구현이 간단하고 예상치 못한 예외 상황의 발생을 피할 수 있다.
요약
- 메모리 칩상의 작은 전용 TLB를 주소 변환 캐시로 사용하여 대부분의 메모리 참조는 메인 메모리 상의 page table을 읽지 않고도 처리가 가능하다.
- 프로그램이 짧은 시간동안 접근하는 페이지들의 수가 TLB에 다 들어갈 수 없다면, TLB미스가 발생하고 느리게 동작한다. 이러한 현상을 TLB 범위(TLB coverage)를 벗어난다고 한다.
- 더 큰 페이지들을 사용할 경우 TLB의 유효 범위가 늘어날 수 있다.
- 할당 받은 페이지의 일부분만 사용하여 내부 단편화가 발생하여 비교적으로 작은 4KB 크기를 사용한다.
- 물리적으로 인덱스된 캐시(physically-indexed cache)가 사용될 경우 주소변환이 캐시 접근 전에 이루어져야 하는데, 이런 경우는 상당히 느려질 수가 있다.
- 이러한 문제 때문에 가상 주소로 캐시를 접근하는 다양한 방법들이 고안되었다.
- 캐시히트가 발생한 경우에 비싼 변환을 하지 않도록 하였다.
- 가상적으로 인덱스된 캐시(virtually indexed cache)는 일부 성능 문제를 해결하지만, 새로운 하드웨어 설계 문제들을 수반한다.
출처
Operating Systems: Three Easy Pieces (운영체제 아주 쉬운 세가지 이야기)
각 페이지 테이블을 가지고 있기때문ㅇ ㅔ페이지 테이블의 크기가 크다?
페이지 크기를 늘리는 경우 페이지 테이블 크기가 커진다/?
