Paging: Faster Translations (TLBs)
- Paging의 문제점
paging을 사용하면 오버헤드가 발생한다.
address space를 고정 크기의 작은 unit(pages)들로 나누면 mapping information을 위한 많은 공간이 필요하다. 일반적으로 mapping information은 physical memory에 올라가므로 paging은 추가적인 메모리가 필요하다.
- TLB (Translation-Lookaside Buffer)
TLB는 MMU의 일부이며, VA → PA translation의 H/W cache다. TLB는 address-translation cache다.
translation을 원하는 주소가 TLB에 있으면 page table을 참조하지 않기 때문에 매우 빠르다.
TLB Basic Algorithm
H/W가 TLB를 관리하고, page table이 linear array라고 가정하자.
아래 코드는 TLB Control Flow Algorithm이다.
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
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()먼저 VA로부터 VPN을 추출하고 TLB에 해당 VPN이 있는지 확인한다.
VPN이 TLB에 있는 경우를 TLB Hit이라고 한다. 이 경우 TLB entry에서 PFN을 가져올 수 있다. 해당 TLB entry의 Protect Bits가 True 이면 offset, Physical address를 구할 수 있고 이후 Physical memory에 접근할 수 있다.
만약 VPN이 TLB에 없으면 TLB Miss가 발생한다. 이 경우 H/W가 page table에 접근하는 추가적인 memory reference가 발생한다. 해당 VPN의 PTE가 valid 하면 TLB를 업데이트 한다.(VPN, PFN, ProtectBits) 그리고 해당 instruction을 다시 수행한다.
TLB miss가 발생할 경우 메모리 참조가 caching에 비해 훨씬 오래 걸린다는 전제가 있다.
Example: Accessing An Array
간단한 예시를 들어보자. 4바이트 integer 10개의 array를 생각해 보자.
virtual address space는 8bit이고, page는 16-byte라고 가정하자.
그러면 4bits의 VPN(page 16개)와 4bits의 offset(16 bytes page이므로)로 나뉠 것이다.
위 그림처럼 16바이트 페이지가 16개 있고, 배열의 첫 번째 원소인 a[0]이 6번 페이지의 4바이트 offset에 위치한다. (a[0] = VPN(6) + offset(4))
아래의 C code를 실행한다고 가정하자.
int sum = 0;
for (i = 0; i < 10; i++) {
sum += a[i];
}먼저 VA 100에 해당하는 첫 번째 원소 a[0]에 접근하려 할 것이다. H/W는 VPN 6을 추출해서 TLB를 확인할 것이고, 당연히 TLB miss가 발생할 것이다.
이후 a[1]과 a[2]에 접근하면 같은 page에 있기 때문에 TLB Hit가 발생한다. a[3]에 접근할 때는 TLB miss가 발생하지만, 이후 a[4], a[5], a[6]에 접근하면 TLB Hit가 발생한다.
10번의 접근에 대한 TLB hit rate는 70%이다.
배열에 한번 접근했지만 spatial locality에 의해 TLB performance가 향상되길 기대할 수 있다.
만약 element들이 page에 tight 하게 위치했다면 TLB miss는 한 번만 발생했을 것이다. 일반적인 4KB 크기의 page에서는 TLB miss가 더 줄어들 것이다. 만약 이 배열에 다시 접근한다면 TLB hit rate가 100이다.
TLB에 cache를 저장할 공간만 충분하다면 temporal locality에 의해 TLB hit rate가 높아질 것이다.
지역성(Locality)
- Temporal locality
한 번 접근한 instruction이나 data item은 다시 accessed될 것이다.
- Spatial locality
프로그램이 address x에 접근하면, 곧 다시 x 주변 주소에 접근할 것이다.
[참고] http://blog.skby.net/지역성-locality/
Who Handles The TLB Miss?
TLB miss는 H/W와 S/W(OS)가 관리한다.
TLB Miss Handle : H/W
CISC(Complex Instrution Set Computer)라고 불리는 예전 컴퓨터에서는 hardware-managed TLB 방식을 사용한다.
이를 위해 H/W는 PTBR(page-table base register)를 이용해 page table의 위치를 찾을 수 있어야 한다.
(예: fixed multi-level page table를 사용하는 hardware-managed TLB)
TLB Miss Handle : S/W
RISC(Reduced-Instruction Set Computer)라고 불리는 modern architecture에서는 software-managed TLB 방식을 사용한다.
TLB miss가 발생하면 H/W는 exception을 일으킨다.
그러면 kernel mode로 권한을 상승시켜서 trap handler로 jump 한다.
privileged instruction으로 TLB를 update 하고 return from trap으로 돌아온다.
이때 instruction을 다시 실행해서 TLB hit를 발생시킨다.
OS handle TLB miss 1 : return form trap
먼저 return from trap에 대해 조금 더 자세히 다루어 보자.
기존의 return from trap은 trap into OS를 발생시킨 instruction의 바로 다음 instruction에서 execution을 재개하는 것이었다.
TLB miss-handling trap의 return from trap을 수행하는 동안, H/W가 trap을 발생시킨 해당 instruction의 execution을 재개해야 한다. 이때 TLB hit가 발생한다.
trap이 어떻게 발생했는지 알아야 하기 때문에 H/W는 적절하게 resume 하기 위해 다른 PC를 가지고 있어야 한다.
OS handle TLB miss 2 : avoid infinite chain
두 번째로 OS는 TLB miss가 infinite chain을 만들지 않도록 조심해야 한다.
먼저 TLB miss handler를 unmapped physical memory에 위치시키는 방법이 있다.(주소 변환이 필요 없으므로 TLB miss가 발생하지 않음)
또는 영구적으로 valid한 TLB의 특정 entry를 예약하고, 그 permanent translation slot이 handler code를 사용하도록 하는 방법이 있다. 이런 wired translation은 언제나 TLB hit를 발생시킨다.
Advantage of software-managed TLB
- Flexibility
OS는 H/W change 없이 page table 구현을 위한 어떤 data structure든 사용할 수 있다.
- Simplicity
기존 TLB Control Flow Algorithm code(의 line 11~19)과 달리 아래 코드처럼 exception(line 11)만 발생시키면 된다.
- TLB Control Flow Algorithm (OS Handled)
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)TLB Contents: What’s In There?
TLB는 보통 32, 64, 128개의 entry를 가지며 이 경우 fully associative라고 불린다. (fully associative 이면 캐시 내 아무 장소에 mapping 될 수 있다.)
찾는 주소가 TLB의 아무 곳에나 있다면 H/W는 TLB 전체를 parallel하게 찾을 것이다. (parrallel 하므로 1 clock에 바로 찾아준다.)
TLB entry는 다음처럼 생겼을 것이다: [VPN | PFN | other bits]
각 entry에 VPN과 PFN이 있고, H/W가 탐색할 때 이것들이 일치해야 멈춘다.
other bits에는 valid bit(translation에 대한 valid), protection bit(determine how a page can be accessed), ASID(address-space identifier), dirty bit(변경되었는지) 등이 있다.
protection bit의 예로 code page는 read and execute, heap page는 read and write로 마크 한다.
TLB valid bit & Page Table valid bit
page table에서 PTE가 invalid로 마킹되면, 그 페이지가 process에 의해 할당되지 않은 페이지이며 올바른 프로그램이 접근하면 안 된다는 것을 의미한다.
유효하지 않은 페이지에 액세스할 때 OS에 trap 하는 것이므로, OS는 프로세스를 중지한다.
반면 TLB valid bit는 TLB entry가 valid translation을 가지고 있는지를 나타낸다.
예를 들어 booting 할 때 어떤 address translation도 cache 되지 않았으므로, 각 TLB entry의 초기 상태는 invalid이다. virtual memeory가 활성화되고 프로그램이 실행되면 virtual address space에 access 하면서 TLB가 채워진다. 그리고 이때 valid entry가 TLB를 채운다.
모든 TLB entry를 invalid로 설정하면 실행하려는 프로세스가 이전 프로세스에서부터 우연히 VA→ PA translate를 하지 않도록 보장할 수 있다.
TLB valid bit는 context switching에도 유리하다.
TLB Issue: Context Switches
TLB는 현재 실행 중인 프로세스의 VA→PA translation이 valid한 지 아닌지에 대한 정보만 가지고 있다. 즉 다른 프로세스의 정보를 가지고 있지 않다.
따라서 H/W나 OS가 실행하려는 프로세스가 실수로 context switch 전 프로세스의 translation 정보를 사용하지 않도록 보장해야 한다.
예를 들어 프로세스 P1이 실행 중이라고 가정하면 TLB가 해당 caching translation이 valid하다고 마킹할 것이다.
P1의 10번째 virtual page가 physical frame 100에 매핑된다고 가정하자. 다음으로 P2를 실행하기 위해 context switching을 할 것이다. P2의 10번째 virtual page가 physical frame 170에 매핑된다고 가정하자.
그럼 TLB는 다음과 같을 것이다.
VPN 10이 다른 주소로 mapping 되지만, H/W는 구분할 수 없다.
따라서 구분할 방법이 필요하다.
Flush TLB
첫 번째 방법은 context switch마다 TLB를 flush하는 것이다.
그러면 다음 프로세스를 실행하기 전에 TLB를 비울 수 있다.
software-base system에서는 명시적이고 권한이 있는 H/W instruction으로 수행할 수 있다.
hardware-managed TLB에서는 page-table base register가 바뀌면 flush 하면 된다.(context switch 하면 OS가 PTBR을 바꾸므로)
두 경우 모두 valid bit를 0으로 바꾸고, TLB의 content를 clear 해야 한다.
하지만 OS가 스위치 할 때마다 TLB miss가 발생할 것이다.
ASID(Address Space IDentifier)
이런 오버헤드를 줄이기 위해 context switch 중에도 TLB를 공유할 수 있도록 H/W support가 필요하다.
어떤 H/W는 PID와 같은 역할을 하는 ASID를 TLB에 채운다. (크기는 ASID가 PID보다 작다.)
아래 그림처럼 프로세스마다 다른 ASID만 부여하면 된다.
H/W는 translation을 위해 지금 실행 중인 프로세스가 무엇인지 알아야 하고, OS는 context swich할 privileged register로 현재 프로세스의 ASID를 set 해야 한다.
이번에는 다른 VPN이 같은 PFN을 가리키는 상황을 고려해보자. 두 프로세스가 같은 페이지를 공유하는 경우 이런 상황이 발생할 수 있다.
위 그림처럼 code page를 공유한다면 physical page의 수를 줄일 수 있고, 결과적으로 memory overhead가 줄어든다.
Issue: Replacement Policy
TLB에 새로운 entry가 들어왔을 때 old entry를 replace 하는 cache replacement에 대해 고려해보자. miss rate를 줄이고, hit rate를 높이는 것이 목표다.
사용 한 지 가장 오래된 엔트리 LRU(least-recently-used)를 삭제하는 것이 가장 일반적이다. LRU는 locality in the memory-reference stream에 advantage를 가지고 있다.
다른 정책으로 random하게 삭제하는 방법이 있다.
random policy는 간단하고, corner-case를 피하기 위해 사용한다.
예를 들어 합리적인 LRU가 size n의 TLB를 n+1번 이상 loop을 돌면 매번(n 번 이후) TLB miss가 발생한다. 이 경우 random policy가 더 좋다.
A Real TLB Entry
위 그림은 software-managed TLB 중 하나인 MIPS의 실제 TLB entry이다. (MIPS R4000)
MIPS R4000 아키텍쳐는 32-bit address space와 4KB pages를 갖는다. 따라서 virtual address는 20-bit VPN과 12-bit offset으로 이루어져 있다고 생각할 수 있다.
하지만 그림에서 VPN은 19-bit뿐이다. user address는 커널용을 제외하면 address space의 절반만 사용할 수 있기 때문에 VPN이 19비트만 필요하다. VPN은 최대 24-bit의 PFN을 trnaslate 할 수 있고, 64GB의 physical memory를 지원할 수 있다.(KB pages)
또 특이한 점은 ASID을 무시하고 프로세스 간 globally-shared가 가능하지 나타내는 glaobal bit(G)가 존재한다.
address space를 구분하기 위해 8-bit ASID가 있다. 256()개 이상의 프로세스가 실행되면 Coherence bits(C)를 사용한다. 페이지가 사용되면 dirty bit로 나타낸다.
entry에 valid한 translation이 있는지 valid bit로 나타낸다. 보이지 않지만 multiple page size를 지원하기 위해 page mask도 있다.
MIPS TLB는 보통 32개나 64개의 entry를 갖는다. wired register로 몇 개의 slot을 OS가 예약했는지 H/W에 알려준다. 이 영역은 TLB miss handler 같은 중요한 code나 data를 저장한다.
Uploaded by Notion2Tistory v1.1.0