TLB 퍼포먼스, Hash PageTable, Inverted PageTable, Segmented PageTable, Multi-Level PageTable - 운영체제

TLB Performance

• TLB Miss Rate = TLB misses / TLB Lookups
• 2048번 lookup
• miss는 2번 (int = 4 byte, page = 4kb 기준)
  • 각 페이지에서 최초 1번 시 miss 발생
• miss rate = 2/2048 = 0.1 %
• hit rate = 99.9%
• smaller page -> worse performance
• larger page -> better performance
• OS 입장에서는 페이지 크기를 키우는 게 도움이 됨
• 그러나 페이지 크기가 커지면 캐시 미스 등의 부작용
• TLB Reach: TLB에서 접근할 수 있는 페이지 크기
  • num of TLB Entries * page size

Workload에 따른 TLB Performance

• sequential array access = 항상 hit
• highly random = worse...
  • 다양한 페이지에 접근할 수 있기 때문
• 짧은 시간 내에 반복적으로 접근하면 또 나름 괜찮음
  • 시간 지역성
  • 나름.. 인 이유는 시간이 너무 오래 걸리면 eviction 일어나서 다시 miss일 경우 있기 때문

Workload Locality

• spatial locality: 다음 메모리 접근이 근처의 주소값이다
  • 같은 페이지에 반복적으로 접근할 경우 성능 좋음
  • 같은 TLB entry를 다시 사용할 수 있기 때문
• temporal locality: 다음 메모리 접근이 이전에 반복했던 형태이다
  • 같은 주소를 짧은 시간 안에 다시 접근할 경우 성능 좋음
  • 같은 TLB entry를 다시 사용할 수 있기 때문
• TLB 특징은 Spatial Locality가 갖춰졌을 때 최적의 성능

TLB Replacement Policy

• LRU: Least-Recently Used TLB
• Random: 아무거나
• LRU는 fully associative에서 Random과 비슷한 성능

LRU Troubles

• 극단적인 경우, 엔트리는 4개인데 5개 페이지를 반복 접근한다면
• 100% miss rate

Context Switches

1. Flush TLB on each switch
   • 비용이 크다, 최근 사용한 모든 TLB 엔트리 잃음
2. Track which entries are for which process
   • address space identifier
     • process ID와 비슷하다 (보통 ASID(Address Space IDentifier)보다 더 많은 비트 사용)
     • 같은 ASID를 갖는 프로세스는 TLB 공유가 가능
       • TLB flush 오버헤드를 줄이는 게 가능하다
   • 각 TLB 엔트리를 8bit ASID로 Tag
     • 2^8 = 256 ASID
     • 그루핑을 위해 PID를 사용하진 않는다

TLB Example with ASID

• load 0x1444 ASID: 12
  • TLB 탐색 조건
  • valid: 1
  • virt: 1
  • ASID: 12
  • => phys= 2
  • => load 0x2444
• load 0x1444 ASID: 11
  • TLB 탐색 조건
  • valid: 1
  • virt: 1
  • ASID: 11
  • => phys= 5
  • => load 0x5444
• 메모리에 있는 페이지테이블 접근 없이 바로 Phys Addr 얻는 게 가능하다

TLB Performance

• Context Switch는 비싸다
• ASID 방식을 사용하더라도 다른 프로세스가 TLB를 오염시킬 수 있음
  • process B의 엔트리가 process A의 엔트리를 덮어쓸 수 있음
• multiple TLB 사용
  • 1 TLB for data, 1 TLB for inst
  • 1 TLB for regular pages, 1 TLB for "super pages"

HW와 OS의 역할

• 누가 TLB Miss를 관리할까?
• HW: CPU가 페이지테이블이 어디 있는지 알고 있어야 함
  • CR3 reg on x86
  • HW, OS가 pagetable 구조체 알고 있음
  • HW가 pagetable 순차 탐색하며 TLB 채운다
• OS: CPU trap into OS
  • OS가 페이지테이블 해석한다
  • TLB 수정은 privileged mode에서
• protection bits 필요: rwx

페이지테이블 크기 계산

1. PTE = 2B, 32 possible VPN
   • 32 * 2B = 64B
2. PTE = 2B, vaddr = 24 bits, pages = 16B
   • page offset = 4 bits, VPN = 20 bits = 2^20개 = 1M개
   • 1M * 2B = 2MB
3. PTE = 4B, vaddr = 32 bits, pages = 4KB
   • page offset = 12 bits, VPN = 20 bits = 1M 개
   • 4MB
4. PTE = 4B, vaddr = 64 bits, pages = 4KB
   • page offset = 12 bits, VPN = 52 bits = 4Peta 개
   • 16PB

• 너무나도 크다

페이지 테이블이 큰 이유

• 사용하지 않더라도 엔트리는 생성되어야 함
• linear 하게 생성하면 공간이 낭비된다
• 이를 해결할 방법
  1. Hash Page Table
  2. Inverted Page Table
  3. Segmented Page Table
  4. Multi-level Page Table

Hash Page Table

• VPN은 해시화 되어 PFN 계산
  • 같은 해시를 가지면 chain을 이룬다
  • chain에서 값을 하나씩 비교해가며 찾음
  • chain을 따라 메모리 접근을 계속해야 함
• Hash Function을 거쳐야 함
  • CPU 사용

Inverted Page Table

• Inverted 페이지 테이블은 메모리 상에 하나 존재
  • 기존 페이지 테이블은 각 프로세스마다 하나씩 존재
• 페이지 테이블 엔트리가 VPN, PFN과 PID를 값으로 가짐
• PID, VPN 조합이 맞는 PFN을 반환
  1. linear search => too much time to search
  2. hashing => cpu use

Segmentation Page Table

• 사용하지 않는 엔트리를 저장하지 않기 위해 segmentation 사용

• 전체 주소 공간을 세그먼트로 나눔 (code, heap, stack)

  • 세그먼트 간 길이는 다를 수 있음

• Logical Address는 세 부분으로 나뉨

  

• 구현

  • 각 세그먼트가 페이지 테이블을 가진다
  • 각 세그먼트가 페이지 테이블의 base와 bounds를 track

  

• 0x002070 read:

  1. 0x002070의 seg: 0
     • segment 0의 base, bounds 찾기 in MMU
     • base: 0x002000, bounds: 0xff
  2. 0x002070의 page number: 2
     • page table의 0x002000의 2번째 entry 찾기 in Memory
     • page frame number: 0x004000
  3. page offset과 concat
     • 0x004070, Read Only

• 0x202016 read:

  1. 0x202016 seg: 2
     • base: 0x001000, bounds: 0x0f
  2. 0x202016 page number: 2
     • pfn: 0x003
  3. page offset concat
     • 0x003016, read/write

• 0x104c84 read

  • invalid

• 0x010424 write:

  • seg 0, read only => invalid

• 0x210014 write:

  • seg 2, base 0x001000, bounds: 0x0f
  • vpn 10, bounds가 0f인데 10에 접근 => invalid

• 0x203568 read:

  • seg 2
  • vpn 3: 0x02a
  • concat: 0x02a568