페이징은 상당한 성능 저하를 가져올 수 있다. 페이지 테이블의 저장을 위해 큰 메모리 공간이 요구된다. 주소 변환을 위해 페이지 테이블의 정보를 읽어야하고, 페이지 테이블 접근을 위한 메모리 읽기 작업의 비용은 비용이 크다. 모든 load/store 명령마다 페이지 테이블에 접근하려 한다면, 당연히 속도가 엄청 느려질 것이다.
핵심 질문: 주소 변환 속도를 어떻게 향상시킬까?
주소 변환을 어떻게 빨리 할까? 페이징에서의 추가 메모리 참조를 어떻게 피할까? 어떤 하드웨어가 추가로 필요할까? OS는 어떤 식으로 이에 개입할까?
OS는 이를 위해 하드웨어의 도움을 받는다. 빠른 주소 변환을 위해 TLB(Translation-lockaside buffer)가 도입되었다. TLB는 MMU의 일부로, 자주 참조되는 가상주소-물리주소 변환 정보를 저장하는 하드웨어 캐시이다.
가상 메모리 참조 시, 하드웨어는 먼저 TLB에 원하는 정보가 있는지를 확인한다. 있을 경우 페이지 테이블에 접근하지 않아도 되기 때문에 페이징의 성능이 크게 향상된다.
1. TLB의 기본 알고리즘
하드웨어 부분의 알고리즘은 다음과 같다.
가상 주소에서 VPN을 추출하고, TLB에 존재하는지 확인한다. 존재한다면(TLB hit) PFN을 추출하여 물리 주소로 변환하고, 메모리에 접근할 수 있다.
만약 변환 정보가 없다면(TLB miss) 페이지 테이블에 접근해야한다. 가상 메모리 참조의 유효성을 검사를 거쳐 유효할 경우 변환 정보를 TLB로 읽어들이게 된다. 해당 작업은 시간이 오래 걸리지만, 이후 같은 가상 주소로 다시 접근한다면, TLB에 정보가 있어 메모리 참조가 빠르게 처리된다.
모든 캐시 설계 철학처럼, “주소 변환 정보가 대부분의 경우 캐시에 있다”라는 가정을 전제로 만들어졌다. TLB 미스가 많아질수록 페이지 테이블 참조를 위한 메모리 접근 횟수가 많아지고, 프로그램이 느려지게 될 것이다.
2. 예제: 배열 접근
배열 a를 순차적으로 탐색한다면, a[0], a[3], a[7]을 접근할 때만 TLB 미스가 발생하고 이외에는 TLB히트이다. 만약 더 큰 페이지의 크기를 가진다면 TLB 히트의 비율이 더 높아질 것이다.
일반적인 경우 페이지는 4KB이기 때문에, 위 예제에서는 a[0]에서 한번만 미스가 발생할 것이다.
TLB 역시 일종의 캐시이기 때문에, 시간 지역성과 공간 지역을 가진다. 실제로 많은 프로그램들은 공간/시간 지역성을 띄고있기 때문에 TLB가 더욱 효과적일 것이다.
3. TLB 미스는 누가 처리할까
CISC 시절에는 하드웨어가 TLB 미스를 처리했다. 하드웨어는 페이지 테이블 base register 정보를 가지고 있고, 미스 발생시 하드웨어에서 테이블 엔트리 정보를 TLB로 반입한 후 미스가 발생했던 명령어를 재실행한다.
현재는 대부분의 컴퓨터가 RISC이다. RISC에서는 소프트웨어가 TLB를 관리한다. TLB 미스가 발생하면 예외 시그널을 발생시켜 커널모드로 진입하고, 트랩 핸들러의 실행을 통해 TLB를 갱신하게 된다.
소프트웨어 관리 TLB의 중요한 사항 2가지를 짚어보자.
- 시스템 콜의 트랩 핸들러와는 조금 차이가 있다. 시스템 콜은 호출 후에 다음 코드가 실행되지만, TLB의 트랩 핸들러가 종료되면 기존 코드를 다시 실행한다.
- TLB 미스 핸들러의 실행에 대해 TLB 미스가 발생할 수 있다. 그래서 OS는 TLB 미스 핸들러를 물리 메모리에 영구적으로 위치시키기도 한다. 이를 통해 핸들러에 대해서는 항상 TLB 히트가 발생한다.
TLB를 소프트웨어로 관리함을 통해, 하드웨어 변경 없이 테이블 구조를 유연하게 변경할 수 있고, 하드웨어가 처리할 일이 없어 더 단순하다.
4. TLB의 구성: 무엇이 있나?
VPN | PFN | 다른 비트들변환 정보 저장 위치에 제약이 없도록, 모든 항목마다 VPN과 PFN을 가지고 있다. 그래서 하드웨어 측면에서 보면, TLB는 완전 연관 캐시이다.
다른 비트들에는 뭐가 있을까? vaild bit는 유효한 변환 정보를 가지는지 나타낸다. protection bit는 접근 권한(read/write/exec)을 표시한다. 그 이외에도 주소 공간 식별자, dirty bit 등이 존재한다.
5. TLB의 문제: 문맥 교환
TLB의 VPN-PFN 변환 정보는 그것을 탑재시킨 프로세스에서만 유효하다. 만약 프로세스 간 context switch 가 발생한다면 어떡할까?
한 가지 방법은 문맥 교환 시에 TLB를 비우는 것이다. 이를 통해 잘못된 변환 정보의 사용은 막을 수 있겠지만, 새로운 프로세스가 실행될 때마다 TLB 미스가 발생할 것이고, 문맥 교체가 잦을 경우 성능에 부담이 갈 것이다.
이런 부담을 줄이기 위해 몇몇 시스템은 문맥 교환이 발생하더라도 TLB의 내용을 보존할 수 있는 하드웨어 기능을 추가했다. 주소 공간 식별자(Address space Identifier, ASID) 필드를 통해 프로세스 별로 TLB 변환 정보를 구분할 수 있다 (PID와 유사하다).
6. 이슈: 교체 정책
모든 캐시가 그러하듯, TLB에서도 캐시 교체 정책이 매우 중요하다.
가장 흔한 방법은 최저 사용 빈도(least-recently used, LCU) 방식이다. 오래 사용되지 않은 항목일수록 사용될 가능성이 적어 교체 대상으로 적합하다고 가정한다.
랜덤 정책도 있다. 구현이 간단하고 예외 상황의 발생을 피할 수 있다.
7. 실제 TLB
MIPS R4000는 32비트 주소 공간에서 4KB 페이지를 지원한다.
- 가상 페이지 번호(VPN): 19비트로 할당되며, 주소 공간의 절반은 사용자 주소 공간으로 할당된다.
- 물리 프레임 번호(PFN): 24비트로 할당되며, 최대 64GB의 메모리(2^24 개의 4KB 페이지들) 지원이 가능하다.
TLB 항목에는 또한 몇 가지 중요한 비트들이 포함되어 있다:
- 전역 비트(G): 이 비트는 프로세스 간에 공유되는 페이지들을 위해 사용된다. 전역 비트가 설정되면 ASID(Address Space Identifier)는 무시된다.
- ASID 필드: 8비트로, 운영체제는 이 필드를 통해 주소 공간을 구분한다.
- 일관성 비트(C): 이 비트는 페이지가 하드웨어에 어떻게 캐시되어 있는지 판별하는 데 사용된다.
- 더티 비트(D): 페이지가 갱신되면 세팅된다.
- 유효 비트(V): 항목에 유효한 변환 정보가 존재하는지 나타낸다.
- 페이지 마스크 필드: 여러 개의 페이지 크기를 지원할 때 사용된다. 그림에는 나타나있지 않다.
