paging: Faster Translations (TLBs)

paging이 느린 이유와 TLB

memory에 접근하기 위해 주소 변환을 하는데, 이 주소 변환 정보(page table)는 매우 커서 memory에 저장된다. 

다시말해 memory에 접근하려고 주소변환을 하는데 그 정보가 또 메모리에 있는 것이다.

이 때문에 memory에 매번 추가로 한번 더 access해야한다.

 

그래서 이것을 빠르게 하고자 TLB(translation lookaside buffer)를 사용한다.

TLB는 mmu안에 들어있고, 구조적으로는 캐시메모리이기 때문에 address translation cache라고도 부른다.

 

주소변환이란 앞서 설명했듯이 VPN를 PFN로 변환하는 과정이고, 여기서 캐시메모리를 사용하여 주소변환정보를 기억했다가 다시 사용하도록 하는 것이 TLB이다.

 

 

TLB control flow algorithm (mmu에서 수행됨.)

(2) vpn을 가지고 TLB에서 매칭되는 entry가 있는지 찾는다. 하나씩 인덱싱하지 않고, 캐시메모리이므로 한번에 비교할 수 있다.

vpn에 매칭되는 TLB entry를 찾았으면 TLB hit,  못 찾았으면 TLB miss가 된다.

 

(3) TLB hit일 경우:

TLB entry의 protection bit를 살펴보고 access가 가능한지 확인한다.

잘못된 접근일 경우 protection fault exception이 발생해서 trap으로 진입하고,

올바른 접근이면 page table entry의 PFN와 offset을 조립하여 physical address를 얻어낸다.

 

(10) TLB miss일 경우 (하드웨어적으로 처리하는 방법) : 

PTBR(page table base register)을 사용하고, VPN을 index로 사용하여 page table에서 PTE(page table entry)를 읽어온다.

 

그리고 앞서 살펴본 페이징 과정과 마찬가지로 valid bit, protection bit를 검증하는 단계를 거친다.

valid bit가 유효하지 않으면 segmentation fault exception, protect bit가 적절하지 않으면 protextion fault exception이 발생한다.

(mmu가 cpu에 interrupt를 건다, internal interrupt이다)

 

여기서 아무 문제가 없으면 VPN, PTE의 PFN, PTE의 protect bit를 TLB에 집어넣는다.

이때 TLB에 빈자리가 있으면 그곳에 넣으면 되고 자리가 없으면 교체가 필요한데, 보통 LRU(least recently used) 정책을 통해 최근에 가장 적게 사용된 것을 지우고 교체한다.

 

그리고 마지막으로 수행중이다가 TLB miss로 중단된 명령어를 다시 실행시켜준다.

(기계어 레벨에서는 명령어 수행이 중간에 중단되면 안한것과 똑같기 때문에 다시 실행시켜 줘야 한다.)

PTE와 TLB의 valid bit는 그 의미가 완전히 다르다!

PTE의 valid bit는 해당 페이지가 사용되고있는지 여부를 나타낸다.
따라서 유효하지 않을때(valid bit=0) 접근하려고 하면 segmentation fault가 발생한다.

TLB의 valid bit는 "VPN > PFN" 이 매핑 정보가 유효한지 여부를 나타낸다.
1이면 사용할 수 있는 유효한 매핑 정보이고, 0이면 무효한 정보이다.
(vpn으로 TLB에서 기껏 찾았는데 valid bit가 0이면 사용하지 못하게 되는 것이다.)

이러한 TLB가 주소변환 속도에 큰 개선을 가져올 수 있는 것은 크게 다음 두가지 특징때문이라고 볼 수 있다.

 

1. spatial locality (공간 지역성) = 공간적으로 몰려있어서 캐시메모리에 의한 속도 개선이 가능하다.

2. temporal locality (시간 지역성) = 가까운 시간내에 같은 페이지를 또 조회하면 TLB에 해당 페이지가 남아있을 확률이 높다.

 

TLB miss를 소프트웨어적으로 처리하는 방법 (software managed TLB)

앞서 살펴본 것처럼 TLB miss를 하드웨어적으로 처리할 수도 있지만, cpu에 따라 이것을 소프트웨어적으로 처리할 수도 있다.(mips)

TLB miss가 났을때 그냥 TLB_miss exception을 발생시키는 것이다. (trap 발생.)

따라서 이 경우에는 context switching이 일어날 때 TLB의 값을 바꿀 수 있는 특별한 기계어 set을 os가 가져야 한다. (but, kernel mode에서만 실행됨.)

 

이러한 소프트웨어적 TLB miss 처리방식에서는 특히 주의할 점이 있는데, 바로 TLB miss가 계속 생길 수 있다는 것이다.

TLB miss가 나서 trap handler를 찾아가서 처리하고 있는데, 그 과정중에 또 TLB miss가 발생하면 처리할 수 있는 방법이 없다.

그리고 이에 대해서는 두가지 해결책을 살펴볼 수 있다.

 

1. Trap Handler 자체가 virtual address가 아닌, 주소변환이 필요없는 물리적 메모리를 가지고 있어서 주소변환 필요없이 바로 접근될 수 있도록 한다. (unmapped)

2. TLB miss가 절대 안나도록, TLB중 일부는 Trap Handler의 정보를 담고있도록 한다. (wired)

 

TLB의 ASID

TLB는 하나 존재하고 여러 프로세스가 이를 공유하기 때문에 TLB에는 같은 VPN이 존재할 수도 있다.

따라서 이 경우 TLB의 VPN 정보가 어떤 프로세스의 것인지 헷갈리지 않게 하기 위해 context switching시에 TLB는 다 지운다.

(page table은 남겨두지만 TLB는 다 지운다. TLB를 지운다는 것은 해당 entry의 valid bit를 0으로 바꾸는 것이다.)

어떤 프로세스의 주소정보인지 헷갈리지 않게 하기 위한 또다른 방법이 있는데 바로 ASID(address space id)이다. ASID를 각 TLB entry마다 따로 부여해서 해당 entry가 어떤 프로세스가 저장한 정보인지를 구별할 수 있게 한다.

(pid로 구별하지 않는 이유는 pid정보가 너무 길기 때문이다.)

또한, 각기 다른 VPN이 물리적으로 같은 frame을 가리킬 수도 있다. 즉, 같은 내용을 공유할 수 있다.

 

 

실제 TLB entry(mips)

mips에서는 32bit중에 offset이 12bit이면, 상위 20비트 즉  2^20이 페이지 개수일것같지만 실제로는 2^19개이다.

이 이유는 전체 메모리의 절반은 커널이 사용하고, 유저가 사용하는 나머지 절반이 주소공간으로 잡히기 때문이다.