💾

10 : Translation-Lookaside Buffer

course

last review

2023/04/13 → 2023/04/14

mastery

rookie

progress

not started

date

2023/03/30

4 more properties

Previous chapter

09 : Paging

Paging

Main QUEST : Accelerating Address-Translation

Translation-Lookaside Buffer(TLB)

Example

Who handles the TLB miss?

Hardware Managing TLB

Software Managing TLB

TLB Contents

TLB valid bit ≠ Page Table valid bit

Context Switches

Replacement Policy

Least-Recently-Used : LRU

Random

Example

Paging

페이징은 고정 사이즈로 메모리를 나눠서 정보 매핑에 많은 양을 요구하는 형태로 성능 저하를 유도한다.

•

각 가상 페이지에 해당하는 물리 프레임 넘버와 페이지 테이블 엔트리를 작성항 페이지 테이블의 사이즈가 어마무시하기 때문이다.

•

가상 메모리를 물리 주소로 변환할때마다 이 페이지 테이블을 참조해야 하는데, 페이지 테이블에 접근하기 위한 메모리 읽기 작업은 엄청난 성능 저하를 유발한다.

Main QUEST : Accelerating Address-Translation

주소 변환을 빠르게 하는 방법은 무엇이 있을까? 페이징에서 발생하는 추가 메모리 참조를 피하는 방법은 어떤게 있을까? 어떤 하드웨어가 필요하며 OS가 개입를! 어떻게 해야할까?

OS의 실행속도를 개선하려면 도움이 필요하다.

대부분 하드웨어로부터 도움을 받는데 이번에도 하드웨어가 해결해줄 거다.

주소 변환을 빠르게 하기 위해 변환-색인 버퍼(translation-lookaside buffer, TLB)를 도입한다.

자주 참조되는 페이지테이블 엔트리를 저장하는 하드웨어 캐시이며 MMU(메모리 관리 유닛, memory-management unit)의 일부이다.

•

주소변환시 먼저 TLB에 해당 정보가 있는지 확인한다.

◦

있다면 페이지 테이블을 통하지 않고 변환을 빠르게 수행한다.

Translation-Lookaside Buffer(TLB)

VPN = (VirtualAddress & VPN_MASK) >> SHIFT
(Success, TlbEntry) = TLB_Lookup(VPN)
if (Success == True)                        // TLB hit
		if (CanAccess(TlbEntry.ProtectBits) == True)
				offset = VirtualAddress & OFFSET_MASK
				PhysAddr = (TlbEntry.PFN << SHIFT) | offset
				Register = AccessMemory(PhysAddr)
		else
				RaiseException(PROTECTION_FAULT)
else                                        // TLB miss
		PTEAddr = PTBR + (VPN * sizeof(PTE))
		PTE = AccessMemory(PTEAddr) //페이지테이블을 접근하기위한 높은 오버헤드
		if (PTE.Valid == False)
				RaiseException(SEGMENTATION_FAULT)
		else if (CanAccess(PTE.ProtectBits) == False)
				RaiseException(PROTECTION_FAULT)
		else
				TLB_Insert(VPN, PTE.PFN, PTE.ProtectBits)
				RetryInstruction()
C
복사

VPN = (VirtualAddress & VPN_MASK) >> SHIFT
C
복사

먼저 가상주소로부터 VPN을 추출한다. 익숙한 코드지?

(Success, TlbEntry) = TLB_Lookup(VPN)
if (Success == True)                        // TLB hit
		if (CanAccess(TlbEntry.ProtectBits) == True)
				offset = VirtualAddress & OFFSET_MASK
				PhysAddr = (TlbEntry.PFN << SHIFT) | offset
				Register = AccessMemory(PhysAddr)
		else
				RaiseException(PROTECTION_FAULT)
C
복사

그 다음 VPN을 TLB에 인덱싱하여 해당 PTE가 있는지 확인한다.

성공할 경우 (TLB에서 탐색하여 매핑되는 놈이 있을경우, 이를 TLB HiT!이라고 한다.) TLB가 변환 값을 갖고 있다는 걸 뜻한다.

해당 TLB에서 페이지 프레임 번호를 추출할 수 있다.

else                                        // TLB miss
		PTEAddr = PTBR + (VPN * sizeof(PTE))
		PTE = AccessMemory(PTEAddr) //페이지테이블을 접근하기위한 높은 오버헤드
		if (PTE.Valid == False)
				RaiseException(SEGMENTATION_FAULT)
		else if (CanAccess(PTE.ProtectBits) == False)
				RaiseException(PROTECTION_FAULT)
		else
				TLB_Insert(VPN, PTE.PFN, PTE.ProtectBits)
				RetryInstruction()
C
복사

반대로 TLB 미스가 일어날 경우 해야할 일이 산더미처럼 쌓이게 된다.

기본적으로 올바른 PTE를 찾기 위해 메모리에 있는 페이지 테이블로 접근해야한다.

메모리에서 올바른 PTE를 찾았다면, 이를 TLB에 넣어주는 작업을 한다.

모든 작업이 끝난 후, TLB를 다시 탐색하여 HiT시킨다!

Example

int a[10];

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

가상 주소 공간은 8비트이며, 페이지 크기는 16바이트이다. 가상 주소는 4비트 VPN과 4비트 오프셋으로 구성된다.

배열의 첫 항목인 a[0]은 VPN : 06 offset : 4이다.

for문을 돌면서 각 배열의 요소를 모두 한번씩 돌아보는 예제이다.

맨처음 a[0]을 탐색할 때 TLB를 보자. TLB가 완전히 초기화되어있다고 가정했을 때, TLB 미스가 발생한다.

따라서 페이지 테이블로 액세스하여, VPN06에 있는 PTE를 TLB에 올려놓는다.

a[1]의 VPN은 a[0]과 마찬가지로 06이므로, TLB 히트가 일어난다. a[2]도 마찬가지.

a[3]는 다시 TLB 미스가 난다. 다시 VPN = 07로 갱신해주면 a[6]까지는 TLB히트가 일어난다.

TLB의 로그를 살펴보자.

TLB log : miss HiT HiT miss HiT HiT HiT miss HiT HiT
C
복사

TLB 히트율이 70%다. 그닥 높은 수치는 아니지만, 0은 아니니까 다행이다.

예제에서 알 수 있는 사실은 페이지의 사이즈가 TLB의 히트율에 놀라운 관여를 한다는 점이다.

페이지 크기가 두배가 되면, TLB미스 회수는 압도적으로 줄 것이다.

또한, 루프 후에도 배열이 사용되는 일이 있다면 성능상에 좋은 영향을 줄 것이다.

Who handles the TLB miss?

Hardware Managing TLB

•

CICS(x86)

•

하드웨어가 페이지가 메모리 어디에 있는지 확인해야 한다.(via Page Table Base Register)

•

RISC(MIPS)

Software Managing TLB

RISC 아키텍처에서 많이 사용되는 소프트웨어 매니징 TLB는 하드웨어 매니징 TLB와 달리 소프트웨어로 TLB 미스를 처리합니다. 이 경우, TLB miss가 발생하면 예외를 발생시켜 처리할 수 있습니다.

MIPS 아키텍처에서는 다음과 같은 코드로 TLB 미스를 처리합니다.

TLB miss가 발생하면 예외를 일으키고, 이 예외를 처리하는 소프트웨어 코드에서 TLB miss 핸들러를 호출합니다. TLB miss 핸들러는 TLB miss를 처리하고, 페이지 테이블에서 물리적 주소를 얻어와 TLB에 삽입합니다.

•

운영체제는 CPU가 뭐가 됐던 간에 내가 원하는 페이지 테이블을 구현할 수 있다.

VPN = (VirtualAddress & VPN_MASK) >> SHIFT
(Success, TlbEntry) = TLB_Lookup(VPN)
if (Success == True) // TLB hit
		if (CanAccess(TlbEntry.ProtectBits) == True)
				offset = VirtualAddress & OFFSET_MASK
				PhysAddr = (TlbEntry.PFN << SHIFT) | offset
				Register = AccessMemory(PhysAddr)
		else
				RaiseException(PROTECTION_FAULT)
else // TLB miss
		RaiseException(TLB_MISS)
C
복사

RISC는 소프트웨어 관리 TLB를 사용한다.

TLB에서 주소찾기에서 실패하면 하드웨어는 예외 시그널을 발생시킨다.

예외 시그널을 받은 OS는 명령어를 잠정 중단하고, 유저모드에서 커널모드로 모드를 바꿔 커널 코드를 준비한다.

커널모드로 변경이 되면 트랩 핸들러(trap handler)를 실행한다.

TLB 미스의 처리를 담당하는 OS 코드이다.

페이지 테이블을 검색하여 정보를 찾고 TLB 접근이 가능한 레벨의 명령어를 사용하여 TLB를 갱신한 후에 리턴한다.

트랩 핸들러에서 리턴되면 하드웨어가 명령어를 재실행하는 방식이다.

TLB미스를 처리하는 트랩 핸들러와 시스템 콜 호출 시 사용되는 트랩핸들러의 결정적인 차이점은 반복의 유무다.

•

시스템 콜의 경우, 트랩에서 리턴한 후 다음 명령어를 호출한다.

•

그러나 TLB의 경우 해당 명령어를 재실행해야 한다.

즉, OS는 트랩의 원인에 따라서 현재 명령어의 PC값 혹은 다음 명령어의 PC값을 저장해야한다.

또한, TLB 미스 핸들러를 실행할 때, TLB 미스가 무한반복이 일어나지 않도록 주의하자.

•

TLB 미스를 해결하는 과정에서 TLB 미스가 또 일어나는 형태 등등…

TLB Contents

•

Fully associative : 특정 어드레스 주소가 위치할 수 있는 룰이 없으며 아무 곳에 들어갈 수 있다.

◦

많이 사용되는 놈들로 최대한 채울 수 있다.

◦

하드웨어적으로 어떤 값을 찾을 때 병렬로 한꺼번에 찾을 수 있다.

•

VPN | PFN | other bits

◦

유효비트 : 엔트리가 유효한 translation을 가지는지

◦

Protection bits : 페이지 테이블에 어떻게 페이지가 저장되는지?

◦

Address-space identifier, dirty bit, etc.

TLB valid bit ≠ Page Table valid bit

Context Switches

TLB를 사용하면 프로세스간 문맥 교환시, 새로운 문제가 등장한다.

프로세스 P1이 실행되고 있는 상황이다. TLB는 P1의 페이지 테이블의 내용을 갖고 있다.

P1의 VPN은 10일때, 또 다른 프로세스 P2로 컨텍스트 스위칭이 일어났다.

공교롭게도 P2의 VPN또한 10번이라 위와 같은 상황이 일어난다.

하나의 가상 페이지 넘버 VPN 10에 대해서 대응되는 물리 프레임 넘버가 100, 170 두개가 되는 것이다. 더군다나 어느 항목이 어떤 프로세스의 페이지인지 알 방법이 없다. 따라서 TLB가 정확하고 효율적으로 멀티 프로세스 간의 가상화를 지원하려면 추가 기능이 필요하다.

문맥 교환시 실행될 프로세스에게는 이전 프로세스가 사용한 TLB 정보는 의미가 없다. 하드웨어 또는 운영체제는 이런 문제를 어떻게 해결할까?

여러가지 해결방법이 있다.

한 방법은 컨텍스트 스위치를 진행할 때 기존 TLB 내용을 지우는 것이다.

하드웨어로 관리되는 TLB는 페이지 테이블 베이스 레지스터가 변경될 때 FLUSH를 시작할 수 있다.

이때 flush는 모든 valid bit를 0으로 설정하는 방식으로 변경할 수 있다.

새로운 프로세스가 실행될 때, 데이터와 코드 페이지에 대한 접근으로 반드시 TLB 미스가 일어나기 때문에, 컨텍스트 스위치가 자주 일어난다면 성능저하를 유발한다.

이를 해결하려면, 컨텍스트 스위치가 일어나더라도 TLB의 내용을 그대로 유지할 수 있으면서 다른 프로세스와 구분이 가능해야한다.

이를 위해 하드웨어에 TLB의 내용을 저장하는 기능인 주소 공간 식별자(Address Space IDentifier, ASID) 필드를 도입한다.

ASID는 PID와 유사하다. 다만 ASID는 좀 더 적은 비트를 가지고 있다.(ASID : 8bit, PID : 32bit)

위 예제는 하나의 VPN에서 두개의 PFN이 도출될 때에 대한 이야기다.

반대로 여러개의 VPN이 하나의 물리 메모리에 수렴하듯 매핑되면 어떨까?

P! F! N!

이런 경우는 두개의 프로세스가 하나의 페이지(코드 페이지 등등)

프로세스 1이 PFN 101을 프로세스 2와 공유하는 상황이다. 코드페이지를 공유하면 프로세스가 사용하는 물리 페이지의 수를 줄일 수 잇다.

Replacement Policy

앞서 말했듯이 TLB는 일종의 캐시다. 모든 캐시가 그러하듯, TLB에서도 캐시를 어떻게 교체하는지 정책을 짜는 것이 성능을 결정하는 매우 중요한 열쇠다.

TLB에 새 항목을 달기 위해서는 반드시 TLB의 기존 항목 중 하나를 버려야 한다. 질문은 다음과 같다.

TLB에 새로운 항목을 추가할 때 어떤 항목을 교체해야 성능이 개선될까?

Least-Recently-Used : LRU

LRU는 메모리 참조 패턴에서의 지역성을 최대한 활용한 방법이다.

사용된지 가장 오래된 항목이 앞으로 사용될 확률도 적다는 가정에 근거한다.

Random

교체 대상이 무작위다.

잘못된 결정을 내릴 가능성이 있지만, 구현이 간단하고 예상치 못한 예외를 피할 수 있다.

Example

•

32-bit 4KB page 어드레스 스페이스 

◦

12비트 오프셋

◦

20비트 VPN

•

PFN

◦

24비트 → 64GB 피지컬 메모리 인식

•

Global bit(G)

◦

프로세스 사이에 글로벌하게 공유되는 페이지 → 커널 영역

•

ASID bits

◦

어드레스 스페이스를 구분하기 위한 비트

◦

PID보다 비트수가 적음

▪

ASID 넘버보다 많은 수의 프로세스를 생성못하게 함

▪

ASID가 서포팅하지 않는거 처럼 행동

▪

ASID를 다이나믹하게 할당한다.

•

Coherence bits(C)

•

Dirty bits(D)

•

Valid bits(V)

•

Next chapter

11 : Multi-Level Page Table