Translation Lookaside Buffer

TLB

 

 

Part of the chip's memory-management unit(MMU).

 

A hardware cache of popular virtual-to-physical address translation.

 

 

 

TLB Basic Algorithms

 

 

VPN = (VirtualAddress & VPN_MASK) >> SHIFT
(Success, TlbEntry) = TLB_Lookup(VPN)
if(Success == TRUE){ // TLB Hit
    if(CanAccess(TlbEntry.ProtectBit) == true){
        offset = VirtualAddress & OFFSET_MASK
        PhysAddr = (TlbEntry.PFN << SHIFT) | Offset
        AccessMemory(PhysAddr)
    } else RaiseException(PROTECTION_ERROR)
}
else{ // TLB Miss
    PTEAddr = PTBR + (VPN * sizeof(PTE))
    PTE = Accessmemory(PTEAddr)
    if(PTE.Valid == false)
        RaiseException(SEGFAULT)
    else{
        TLB_Insert(VPN, PTE.PFN, PTE.ProtectBits)
        RetryInstruction()
    }
}

 

 

virtual address 를 physical address (popular한) 변환을 할 때 이러한 과정이 100번 일어난다고 가정한다.

 

실행할 때 time 사이에 실제로 자주 접근되고 있는 page Entry가 존재하는데 그런 entry 를 실제로

cache 할 때 해당 page entry를 가져올 필요가 없다.

 

즉, access 빈도를 줄일 수 있으며 이를 TLB 라고 한다.

 

 

Accessing An Array

 

 

int sum = 0;
for(i = 0; i < 10; i++)
    sum += a[i];

 

 

총 40 byte 할당이 필요한 상황이다.

 

4 byte씩 들어갈 때 a[0] 는 VPN 6 에서 offset 4 를 읽는다.

 

처음에는 VPN 6 에 대한 entry가 없는 상태이므로 TLB Miss가 발생할 것이다.

 

PTEAddr = PTBR + (VPN * sizeof(PTE))
PTE = Accessmemory(PTEAddr)
if(PTE.Valid == false)
    RaiseException(SEGFAULT)
else{
    TLB_Insert(VPN, PTE.PFN, PTE.ProtectBits)
    RetryInstruction()
}

 

TLB Miss가 발생할 때 실행되는 코드이다.

 

Page Table Entry 에 대한 size만큼 VPN 을 곱해줘서 PTBR (Page Table BaseLine Register)을 더해주면 Page Table Entry에 대한 Address 를 얻을 수 있다. 

 

그 후에 TLB 에 VPN, PTE.PFN, PTE.ProtectBits 을 넣어주고 다시 명령어를 실행하도록 한다.

 

그래서 a[1], a[2] 에 대한 동일한 VPN 6에 대하여 TLB_Lookup(VPN) 을 호출하여 얻은 Success,

TlbEntry 에 대하여 위에서 해당 VPN 에 대한 TLB Insert를 해줬으므로 TLB Hit 이 일어난다.

 

즉, a[0], a[3], a[7] 는 TLB Miss, 그 외에는 TLB Hit 이 일어난다.

 

TLB Miss = 3, TLB Hit = 7 이므로 TLB hit rate 는 70% 가 된다.

 

 

Locality

 

 

Temporal Locality=> An instruction or data item that has been recently accessed will likely be reaccessedsoon in the future.

 

 

Spatial Locality=> If a program access memory at address x, it will likely soon access memory near x.

 

 

 

Who Handles the TLB Miss?

 

 

Hardware handles the TLB miss entirely on CISC.

 

- The hardware has to know exactly where the page tables are located in memory.

- The hardware would "walk" the page table, find the correct page-table entry 

  and extract the desired translation, update and retry instruction.

- Hardware-managed TLB.

 

RISC has what is known as a software-managed TLB.

 

- On a TLB miss, the hardware raises exception (trap handler).

  => Trap handler is code within the OS that is written with the express purpose

       of handling TLB miss.

 

CISC는 instruction 가 복잡하고 RISC는 instruction 이 짧아서 복잡한 연산을 하지 않는다.

 

 

TLB entry

 

 

 

TLB is managed by Full Associative method.

 

- A typical TLB has 32, 64, or 128 entries.

- Hardware searches the entire TLB in parallel to find the desired translation.

- other bits : valid bits, protection bits, address-space identifier, dirty bit.

 

여기서 Full Associative 이란?

 

TLB 4개, PT 에 VPN 8개가 있다고 가정할 때, TLB가 PT 에 VPN 이 뭐가 되든 들어갈 수 있다.

 

추가로 Direct Mapped 는 PT 의 VPN이 0~7, TLB는 0~3 이라고 할 때, 

page table 의 VPN을 4로 modulor operation 을 한다고 할 때의 나머지에 대해서

 

VPN 0 => TLB 0, VPN 1 => TLB 1, VPN 2 => TLB 2, VPN 3 => TLB 3

VPN 4 => TLB 0, VPN 5 => TLB 1, VPN 6 => TLB 2, VPN 7 => TLB 3

 

와 같이 매기는 방법이다.

 

 

Context Switching

 

 

 

위와 같이 VPN 10을 접근하면서 PFN이 100이면 해당하는 entry를 읽어서 TLB Table에 insert한다.

 

Context Switch 가 일어나서 동일하게 VPN 10을 접근하면서 PFN 170으로 TLB Table에 insert 한다.

 

그렇다면 발생하는 문제점은? => VPN 이 동일한데 또 다시 VPN 10을 접근하려고 할 때이다.

 

즉, TLB 를 같이 공유해서 생기는 문제점으로서 이를 해결하기 위해 ASID 를 추가한다.

 

ASID는 process ID 와 동일한 개념으로 이해하면 편리할 듯 하다.

 

 

즉 위와 같이 ASID를 process A에 대한 ASID, process B에 대한 ASID로 매김으로써 동일한 VPN

을 접근하려고 할 때 어떤 process가 호출했는지까지를 확인함으로써 해결이 가능하다.

 

 

 

다른 케이스가 존재하는데 VPN은 다르나 PFN가 동일하게 된 경우이다.

 

아래의 사진을 보도록 하자.

 

 

예를 들어서 a.out 를 fork() 를 띄워서 process A, B 를 띄웠다고 가정해보자.

 

Process A, B 에 대한 Code, Heap, Stack 에 대해서 Code 부분을 page table 에서 mapping 하면실제로 virtual address는 다르지만 physical frame number이 같을 수 있다.

 

이러한 경우 Code Sharing 을 함으로써 실제 TLB Entry를 보면 PFN이 같을 수 있다. (ASID는 다르고)

 

즉, Page Table 수를 줄일 수 있어서 메모리 공간을 효율적으로 관리가 가능하다.

 

 

TLB Replacement policy

 

 

LRU(Least Recently Used)

 

- Evict an entry that has not recently been used.

- Take advantage of locality in the memory-reference stream.

 

 

 

Cache가 꽉찰 때 누구를 밀어낼 것인가는 굉장히 중요한 issue 이다.

 

그래서 적용되는 방법으로 LRU 이다.

 

가장 최근에 사용이 되지 않은 값을 밀어내고 해당 자리에 값을 채우는 방법이다.

 

위 사진처럼 값을 차례대로 읽어가면서 꽉찰 경우에 최근에 사용되지 않은 값을 밀어낸다.