[OS] 메모리 가상화(Memory Virtualization): 6. Paging: TLB

 

*이 글은 Operating Systems: Three Easy Pieces(운영체제 아주 쉬운 세 가지 이야기)를 바탕으로 작성되었습니다. 첨부한 모든 그림은 해당 도서에서 가져온 자료입니다. 내용 중 잘못된 부분이 있다면 알려주세요 :)

 

지난 글에서 paging 기법으로, linear page table을 사용할 때 메모리 접근 비용이 성능 저하를 가져왔다.

 

Address translation 속도를 어떻게 줄일 수 있을까?

 

메모리 접근 비용이 부담이라면....

하드웨어의 도움을 받아보자

 

---

 

🧐 TLB (Translation-Lookaside buffer)

• 자주 참조되는 가상 주소-물리 주소 변환 정보를 저장하는 하드웨어 캐시
• address translation cache
• MMU에 속해있다.

• 가상 메모리 참조 시, 하드웨어는 먼저 TLB에 정보 있는지 확인
• 있다면 page table 통하지 않고 변환, 없다면 page table을 통해 변환

출처: https://en.wikipedia.org/wiki/Translation_lookaside_buffer

• VPN | PFN | other bits 로 구성
• other bits로는 valid bit, protection bit, address-space identifier bit, dirty bit 등

 

TLB의 기본 알고리즘

 

VPN = (VirtualAddress & VPN_MASK) >> SHIFT		//Virtual Address에서 VPN 추출
(Success, TlbEntry) = TLB_Lookup(VPN)			//해당 VPN의 TLB 존재 여부 검사
if (Success == True)							//TLB Hit
	if (CanAccess(TlbEntry.ProtectBits) == True)//해당 page 접근 권한 검사	
    	Offset = VirtualAddress & OFFSET_MASK	//Offset 추출
        PhysAddr = (TlbEntry.PFN << SHIFT) | Offset	//PFN, Offset으로 Physical address
        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)		//TLB에 정보넣음
		RetryInstruction()

 

 

예제로 한 번 살펴봅시다.

아래 코드를 실행할 때를 생각해보자

 

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

 

 

아래 그림은 페이지로 구성된 Virtual Address Spac를 표현한 것이다.

 

 

 

• a[0]의 VPN=06, TLB에서 VPN 06번을 찾는다 
  ⇨ 없다! TLB miss
  ⇨ Page table을 통해 PFN 얻고, 이를 TLB에 갱신
• a[1]의 VPN=06, TLB에서 VPN 06번을 찾는다
  ⇨ 있다! TLB hit
  ⇨ TLB를 통해 PFN 얻음

위 두 가지 배열 접근 예를 보면 a[0], a[3], a[7]의 경우에 page table에 접근하고, 나머지는 TLB를 통해 PFN을 얻는다는 것을 알 수 있다.

⇨ 3 miss, 7 hit

 

 

 

 

 

 

위 예시로 알겠지만, TLB는 Locality로 성능을 개선할 수 있다.

• Temporal Locality
  한 번 참조된 메모리 영역이 짧은 시간 내에 재 참조
  TLB의 히트율에 영향
  
  
• Spatial Locality
  서로 인접해있기 때문에, 페이지에서 첫 번째 항목을 접근할 때만 miss

---

 

🧐 TLB miss

 

그럼 TLB miss의 경우 어떻게 처리되는걸까?

하드웨어에서 처리하는 방법과 소프트웨어에서 처리하는 방법, 두 가지가 있다.

 

1. CISC(complex instruction set computers)

• hardware-managed TLB
• 하드웨어에서 처리
  1. Page table에서 원하는 PTE를 찾는다
  2. 필요한 변환 정보를 추출한다
  3. TLB를 갱신한다
  4. TLB miss가 발생한 명령어를 재실행한다

 

2. RISC(reduce instruction set computing)

• software-managed TLB
• 소프트웨어에서 처리
  1. TLB에서 주소 찾는 것이 실패하면, 하드웨어는 예외 발생한다
  2. 예외 시그널을 받은 OS는 명령어 실행 중지하고, kernel mode로 변경한다
  3. trap handler를 실행시켜, page table을 검색하여 변환정보 추출한다
  4. TLB를 갱신한다

---

 

🧐 TLB의 문제: Context Switching

 

TLB에 있는 변환 정보는 프로세스마다 다르다.

각자 자신의 프로세스의 변환 정보를 잘 가져와서 사용해야한다.

 

예제를 생각해보자.

프로세스 P1이 실행 중이라고 가정하자.

 

현재 P1의 VPN 10이 PFN 100에 매핑되어있다.

또다른 프로세스 P2는 VPN 10이 PFN 170에 매핑되어있다. 

 

 

이때 VPN 10의 정보가 두 개나 존재한다.

어떤 프로세스가 어떤 변환 정보를 사용해야하는지 알 수 없다.

 

이 문제를 해결할 방법이 또 몇 가지가 있다.

 

 

1. context switch 전 기존의 TLB 내용 비우기

• context switch 전 valid bit를 모두 0으로 설정

⇨ Cost is HIGH

 

 

2. ASID(Address Space IDentifier)

• ASID 필드를 추가

추가로 다른 process, 다른VPN이 페이지를 공유할 수 있다.

위 예시는 두 개의 다른 VPN이 동일한 PFN을 가리키고 있다.

두 프로세스가 하나의 페이지를 공유할 때 발생한다. 이 경우 메모리 부하를 줄일 수 있다.

 

---

🧐 TLB Replacement Policy

 

TLB에 새로운 항목을 탑재할 때, 존재하는 항목 중 교체해야한다.

이때 교체 정책(Replacement Policy)이 매우 중요하다.

 

LRU (Least Recently Used)

• 사용되지 않은지 오래된 항목일수록, 교체 대상에 적합
• 메모리 참조 패턴에서의 지역성을 최대한 활용하는 것이 목적

---

 

🧐 실제 TLB

 

실제 TLB를 살펴보자.

예시는 MIPS R4000이다.

 

• 32비트 주소 공간, 4KB 페이지
• VPN 19비트
• FPN 24비트
• Global bit (G)
• ASID
• Coherence bit (C)
• Dirty bit (D)
• Valid bit (V)

---

 

TLB는 주소 변환 캐시로 사용하여 대부분의 메모리 참조들은 page table을 읽지 않고 가능하다.