페이징 방식의 가장 큰 단점은 페이지 테이블을 참조하는 과정에서 다시 메모리에 접근해야 한다는 것이다.
즉, 페이지 테이블에 접근->물리 주소로 번역->메모리에 접근과 같이 원하는 메모리에 접근하기 위해 메모리를 적어도 두 번 참조해야 하며 이는 큰 성능 저하를 유발한다.
이런 문제로 주소 변환을 빠르게 하기 위해서 주소 변환 정보를 캐시해두는 하드웨어 버퍼를 TLB translation-lookaside buffer라고 한다.
TLB는 자주 참조되는 가상 주소-물리 주소 정보를 저장하는 하드웨어 캐시이다.
가상 메모리 참조 시, 페이지 테이블보다 먼저 TLB를 참조한다.
- TLB에 VPN(virtual page number 가상 페이지 번호, 가상 주소에서 페이지 크기 비트만큼의 주소를 제외한 부분)을 검색하여 존재하면(TLB 히트) TLB에 저장된 PFN(page frame number 페이지 프레임 번호)를 읽어 물리 주소를 알 수 있다.
- TLB에서 VPN을 찾을 수 없다면(TLB 미스) 페이지 테이블에 접근하여 주소를 번역하고 TLB에 갱신한다.
2-1. TLB가 성능을 개선하는 이유
![[Pasted image 20240928171003.png]]
그림의 예시에서 배열은 3개의 페이지(06, 07, 08)을 걸쳐 저장되어 있다.
배열을 순서대로 순회한다면 TLB는 미스, 히트, 히트, 미스, 히트, 히트, 히트, 미스, 히트, 히트 순서로 동작할 것이다.
이 때 TLB히트는 공간 [[CSAPP#6-2. 지역성|지역성]]으로 인해 발생한다.
반면 페이지의 크기가 배열들을 모두 포함할 만큼 크고 배열들이 하나의 페이지 안에 배치되었다고 가정하자.
이 때에 TLB히트는 시간 지역성으로 인해 발생한다.
다른 캐시와 마찬가지로 TLB의 성능 개선은 프로그램의 지역성 정도에 의존한다.
2-2. TLB 미스를 처리하는 두 가지 방식
2-2-1. 하드웨어
CISC에서는 주로 하드웨어가 TLB 미스를 핸들링한다.
이를 위해서는 하드웨어가 페이지 테이블에 대한 명확한 정보를 가지고 있어야한다.
여기서 명확한 정보: (프로세스별) 페이지 테이블의 위치, 페이지 테이블의 형식
TLB 미스 발생 시
1. 페이지 테이블에서 원하는 페이지 테이블 엔트리를 찾고
2. 필요한 변환 정보를 추출하여
3. TLB를 갱신한다.
4. 그 후 TLB 미스가 발생한 명령어를 재실행한다.
이는 하드웨어가 수행한다.
2-2-2. 소프트웨어(운영체제)
RISC에서는 보통 운영체제가 TLB 미스를 핸들링하도록 설계되었다. (software-managed TLB)
1. 하드웨어가 예외(TLB 미스) 시그널을 발생시킨다.
2. 프로세스는 커널모드로 전환하여 예외 핸들러(exception handler, interrupt handler 또는 트랩 핸들러 trap handler)로 진입한다.
3. 예외 핸들러에서 TLB 미스를 확인하고 TLB 미스 핸들러를 호출한다.(따라서 운영체제는 TLB 미스 핸들러를 설계해놓아야 한다.)
4. TLB 미스핸들러에서 페이지 테이블을 검색하여 TLB를 갱신하는 명령어(커널 모드에서만 호출 가능한)를 호출하여 TLB를 갱신한다.
5. 작업이 완료되면 다시 유저 모드로 전환하여 TLB 미스가 발생한 명령어를 재실행한다.
2-3. TLB의 구성
TLB는 VPN, PFN, 그리고 다른 정보들을 저장하는 비트들로 구성되어있다.
가상주소의 앞부분인 VPN을 검색하여 물리 메모리상 위치인 PFN으로 변환한다.
그 외 정보 비트로는 valid bit(현재 프로세스에서 유효한지), protection bit, dirty bit, address-space identifier 등이 있다.
TLB의 동작 방식은 단층 구조든 다층 구조든 기본적으로 동일합니다. TLB는 가상 주소와 물리 주소의 매핑을 캐싱하는 역할을 하기 때문에, 다층 페이지 테이블 구조에서 각 단계의 페이지 테이블을 건너뛰는 데 도움을 줍니다. 계층이 있든 없든 TLB는 마지막으로 변환된 최종 물리 주소를 기억하고 있다가 빠르게 접근할 수 있게 해줍니다. 따라서 다층 구조에서도 TLB는 별도의 계층을 두고 동작하지 않습니다.
일반적인 x86-64 시스템에서 TLB의 엔트리 개수는 CPU 아키텍처와 모델에 따라 다릅니다. TLB는 크게 두 가지 종류가 있습니다:
1. Instruction TLB (ITLB): 명령어 페이징에 사용됩니다.
2. Data TLB (DTLB): 데이터 페이징에 사용됩니다.
각각의 캐시 크기와 엔트리 개수는 다를 수 있지만, 일반적으로 다음과 같은 특성을 가집니다:
- L1 TLB (레벨 1 TLB):
- ITLB와 DTLB로 나뉘며, 가장 빠르고 작은 캐시입니다.
- 일반적으로 64~128개의 엔트리를 갖고 있습니다.
- 4KB 페이지와 2MB/1GB의 큰 페이지들을 캐시할 수 있습니다.
- L2 TLB (레벨 2 TLB):
- ITLB와 DTLB가 통합된 경우가 많습니다.
- L1 TLB보다 크고 약간 느리지만, 512~2048개의 엔트리를 가집니다.
- L1 TLB에서 미스가 발생했을 때 L2 TLB를 참조합니다.
2-4. 문맥 교환 시
페이지 테이블은 일반적으로 프로세스마다 별개로 가지고 있기 때문에 문맥 교환 시에는 이전 프로세스에서 기록한 TLB의 정보가 유효하지 않다는 문제가 있다.
이 문제에 대처하는 방식 중 두 가지를 살펴보면:
1. 기존 TLB 내용을 비우는 방법
문맥 교환을 수행할 때 기존 TLB의 valid bit를 모두 0으로 만들어 문맥 교환 이후[^시점] 프로세스에서 사용하지 않도록 하는 방법이 있다.
다만 문맥 교환이 일어날 때마다 TLB가 초기화되는 것이므로 문맥 교환 이후에는 TLB 미스가 발생할 것이다. 따라서 문맥 교환이 잦은 경우 TLB를 통한 성능 개선을 기대하기 어렵다.
2. TLB에 주소 공간 식별자(address-space identifier, ASID)를 추가하는 방법
ASID는 PID와 유사한 정보로, 프로세스와 ASID 정보를 대조하여 자신의 TLB 정보만 사용할 수 있게 한다.
따라서 여러 프로세스가 TLB를 같이 사용할 수 있게 되어 매번 TLB를 비우지 않고 정보를 유지할 수 있다.
[^시점]: 소프트웨어 기반에서는 TLB를 비우는 하드웨어 명령어를 문맥 교환 시 사용함으로써 할 수 있다. 하드웨어 기반에서는 페이지 테이블 베이스 레지스터가 변경될 때 TLB를 비우도록 설계할 수 있다.
2-5. 캐시 교체
TLB도 다른 캐시나 물리 프레임처럼 수가 한정되어있기 때문에 공간을 초과하는 경우 교체가 필요하다.
교체 알고리즘에 대해서는 뒤의 [[#4. 페이지 교체 알고리즘|페이지 교체 알고리즘]]을 참고.
3. 페이지 테이블 축소
지금까지는 페이지 테이블이 모든 주소 공간에 대한 물리 주소로의 매핑을 가지고 있는 선형 페이지 테이블이라고 가정하였다.
예를 들어 32비트 시스템과 페이지 크기를 4KB(바이트)라고 가정하자.
그러면 32비트 주소공간에서 페이지의 개수는 개이다.
따라서 필요한 페이지 테이블 엔트리 역시 이므로 4바이트 페이지 테이블 엔트리 길이의 배열이 필요하다.
이 때 크기는 4MB로 프로세스가 100개만 되어도 400MB의 메모리 공간이 필요하다는 의미가 된다.
이를 해결하기 위해서는 페이지 테이블을 작게 만들어야 한다.
3-1. 방법1: 페이지 크기 증가
페이지의 크기를 4KB에서 더 크게 증가시키면 페이지의 개수와 필요한 페이지 테이블 엔트리의 개수가 줄어든다.
단순한 방법이지만 이는 페이지의 내부 단편화를 증가시킨다.
3-2. 방법2: 페이징과 세그멘테이션
세그멘테이션과 페이징을 혼합하여 사용하는 것도 한 가지 방법이 될 수 있다.
세그멘트별로 페이지 테이블을 분리하여 세그멘트의 크기 만큼의 엔트리만 사용하여 크기를 줄인다.
실제로 x86은 이런 하이브리드 방식을 지원하였다.
하지만 세그멘테이션의 단점(세그멘트 별 사용 방식에대한 가정이 필요, 세그멘트 내의 희소한 사용(특히 힙공간 에서)의 경우에는 여전히 페이지 테이블이 낭비됨)이 여전히 존재한다.
3-3. 방법3: 멀티 레벨 페이지 테이블
멀티 레벨 페이지 테이블에서는 선형 페이지 테이블을 트리 구조로 표현한다.
효율적이기 때문에 많은 현대 시스템에서 사용한다.
![[{D471808E-948E-4BF1-AB45-7B674890AF49}.png]]
![[Pasted image 20240927221326.png]]
x86에서는 페이지 디렉터리(PD)-페이지 테이블(PT) 2 단계로 구성된다.
64비트 확장 또는 x86-64에서는 페이지 맵 레벨4(PML4)-페이지 디렉터리 포인터(PDP)-페이지 디렉터리(PD)-페이지 테이블(PT) 4단계로 구성된다.
페이지 테이블을 제외한 각 단계의 엔트리에는 다음 단계의 포인터가 저장되어 있어 단계를 내려가면서 페이지 테이블 엔트리에 접근하게 된다.
장점
이런 멀티레벨 페이지의 장점은 할당된 페이지가 포함되지 않은 엔트리에는 valid bit를 0으로 표기함으로써 하위 단계의 자료구조를 생성하지 않고 공간을 절약할 수 있다는 점이다.
또한 선형 테이블 페이지의 경우 전체 테이블 페이지를 저장할 큰 크기의 연속된 공간을 필요로 했지만, 멀티 레벨 페이징에서는 단순히 free 페이지 풀에 있는 빈 페이지를 가져다 쓸 수 있다.(배열과 연결리스트의 관계를 떠올릴 수 있다.) 즉, 페이지 테이블을 저장할 공간 할당이 유연하다.
단점
멀티 레벨 페이징에서도 TLB는 동일하게 동작하므로 TLB 히트 시의 성능은 동일하다.
하지만 TLB 미스 시 페이지 테이블을 검색하기 위해서 다단계의 접근이 필요하므로 메모리 접근 시간이 증가한다.(pml4에서는 페이지 테이블을 검색하기 위해 메모리에 네 번 접근해야 한다.)
또 페이지 테이블 검색의 구현이 더 복잡해진다.
3-4. 방법4: 역 페이지 테이블
가상 주소로부터 물리 주소로 매핑하는 페이지 테이블은 프로세스마다 하나씩 필요했다.(가상 주소 공간이 프로세스의 수만큼 있으므로)
역 페이지 테이블은 각 물리 프레임으로부터 가상 주소 페이지를 매핑한다. 따라서 시스템은 하나의 자료 구조만으로 주소 번역을 할 수 있다.(물리 주소는 하나만 있으므로)
하지만 주소 검색 시 순차 탐색을 사용하면 성능이 너무 느려지므로 보통 해시 테이블을 이용하여 탐색한다.
3-5. 방법5: 페이지 테이블을 디스크로 스왑
페이지 테이블들을 커널 가상 메모리에 위치시키고, 페이지 테이블들을 디스크로 스왑하여 메모리 공간을 확보하는 방법도 가능하다.
