[OS] TLB - Paging의 성능문제에 대한 해결책

해당 포스팅은 학교 수업 내용을 요약정리하는것에 초점을 두고 진행합니다. (3학년 2학기과정 OS수업)
참고문헌 : OSTEP(Operating System : Three Easy Pices)

 

---

1. Summary and Intro

 

페이징에 대한 내용을 먼저 본 뒤, 해당 포스팅을 보시면 더욱 도움이 됩니다!

 

https://baejun.tistory.com/15

[OS] 페이징(paging)이란?

https://baejun.tistory.com/16

[OS] 페이지 테이블 (page table)이란?

 

앞선 포스팅에서 페이징 기법에 대해 알아봤다.

메모리공간에 가변크기 대신 고정 크기의 공간을 할당하고, 주소가 연속적이여야 할 필요를 없앰으로써

외부단편화 문제를 해결해주었다.

 

하지만 페이징 기법도 당연히 문제점이 발생한다.

바로 주소변환이 느리다는 단점인데, 당연한 얘기이다.

외부단편화를 없애주는 메리트를 주던 페이지 테이블이 원인인데,

주소 변환을 위해선 2번의 페이지 접근이 수행되어야 한다. (①페이지 테이블 접근 ②명령어 및 데이터 접근)

이는 추후에 다룰 멀티 단계의 페이지 테이블의 경우(접근 과정이 더 많이 필요해짐) 더더욱 심각해지게 되는데

이러한 문제를 해결하기 위해 최적화 과정이 필요하고, 이를 위해 등장한게 "TLB 캐시이다"

---

2. What is TLB?

그래서 TLB가 뭐냐?

translation-lookaside buffer, 한국말로 번역하면 변환 색인 버퍼... 무슨 말인지 모르겠다

쉽게 말해 변환 정보를 참조하는 버퍼다. 근데 변환 정보를 ("논리주소 A는 물리주소 B로 가면됨) 담고있는건 비단 TLB뿐만이 아닌걸 우린 이미 알고있다.

그렇다, 페이지테이블에서도 변환 정보를 담고있고, 우린 페이지테이블을 통해서 변환 정보를 얻어온다 배웠다.

그렇다면 변환정보를 TLB에서 갖고오는 것과 page table에서 갖고오는게 무슨 차이가 있을까 ?

바로 속도 차이다 !

TLB는 MMU칩에 내장되어 있으며 자주 참조되는 변환 정보에 대한 "캐시 역할"을 수행한다.

즉, 메모리에 접근해야하는 page table보다 하드웨어에서 바로 가지고 오는 TLB가 속도 면에서 훨씬 우월하다는 것이다. (수업시간엔 1000배 차이다 ! 라고 했는데, 뭐 실제로 1000배 차이인지는 모릅니다.. 그 만큼 훨씬 빠르다는 거겠죵?)

TLB

TLB의 특성을 살펴보자

1. 하드웨어로 구현되어 있다.

2. 16~256개의 엔트리를 포함한다. -> 한정된 정보만 보유 가능하다! -> 자주쓰는 변환 정보를 선별해 담는다

3. 접근 방식 => ①Full associative = 아무데나 다 접근 가능한 것 / ②Set associative = 정해놓은 범위에서만 접근 가능한것

4. 교체방식 => LRU 방식 사용 => 공간이 꽉 차면 가장 오래된 데이터를 버리고 새로운 데이터를 맞이

5. 그리고 그림에 보이다시피 TLB는 온전한 PTE 그 자체를 가진다. 따라서 주소변환 정보 뿐 아니라 Valid와 같은 다양한 정보를 추가적으로 담고있다.

 

TLB가 포함된 주소변환 과정

매핑 변환 단계
1. 가상 주소 -> TLB 캐시 확인(hardware)
2. cache hit!(찾는 변환정보가 존재할 때) : TLB에서 물리 주소 변환 후 리턴
3. cache miss(찾는 변환정보가 존재하지 않을 때) : 기존 방식대로 메모리(page table) 접근 후 리턴

즉, TLB(하드웨어)에 먼저 접근한뒤에 없을 때에만 메모리(page table)에 접근하므로 속도 면에서 더 효율적.

---

3. TLB 접근 예제

자 그럼 이제 이 TLB가 들어간 주소 변환 과정을 예제로 살펴보자.

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

배열을 모두 더하는 코드이다.

배열이 담기는 가상주소

자 이제, 각 배열 index를 0~9번까지 물리주소와 매핑해보자. 어떤 과정을 거치게 될까?

우선 각 VPN의 첫번째 접근은 TLB에 변환 정보가 없을 것이다.(Cache miss)

그렇다면 이때는, 메모리에 접근해야하고, 메모리에서 해당 PTE에 접근 해 PTE정보를 TLB에 삽입한다.(이후 접근시에는 Cache hit! 가 일어나도록), 그런식으로 정리를 해보면

a[0] = cache miss , 해당 페이지에 대한 변환 정보 cache에 저장
a[1] = cache hit!
a[2] = cache hit!
a[3] = cache miss , 해당 페이지에 대한 변환 정보 cache에 저장
a[4] = cache hit!
a[5] = cache hit!
a[6] = cache hit!
a[7] = cache miss , 해당 페이지에 대한 변환 정보 cache에 저장
a[8] = cache hit!
a[9] = cache hit!

3번의 miss와 7번의 hit가 발생 해 TLB hit rate가 70%이다. 그에 상응하는 성능개선을 보상으로 받았을 것이다.

이때 cache에겐 공간 지역성과 시간 지역성을 보장받는것이 중요하다.

for loop를 돌며, 순차적으로 페이지에 접근하며, 한번 miss가 난 페이지의 변환 정보를 cache에 바로 insert하고 다시 재 참조 함으로써, 시간지역성과 공간지역성을 확보한 모오습!

시간 지역성

공간 지역성

시간 지역성(Temporal locality) : 한번 참조된 메모리 영역이 짧은 시간내에 재참조 되는 현상.
공간 지역성(Spatial locality) : 어떠한 요소에 접근했을때, 다음 접근은 그 요소 주변일 가능성이 높은 현상

---

4. TLB Cache Miss 처리 (RISC, CISC)

위에서 TLB Cache Miss 발생 시, 해당 페이지에 대한 변환 정보를 cache에 저장한다고 했는데, RISC방식과 CISC 방식으로 나뉜다.

 

1. CISC(하드웨어 기반) : 하드웨어가 페이지 테이블에 대한 정보를 가지고 있음.

이 경우에 처리 과정은 다음과 같다

(1) PTE 검색

(2) 필요한 변환 정보 추출

(3) TLB 갱신

(4) TLB miss 명령어 재 실행

 

2. RISC(소프트웨어 기반) : 소프트웨어 관리 TLB라고도 불린다.

이 경우엔 TLB 핸들러를 사용한다.

TLB 트랩 핸들러를 호출 한 후 현재 명령어를 재 실행 하는데, 주의해야 할 점은 시스템 콜의 트랩 핸들러와 차이가 있다는 것이다.

 

시스템 콜의 트랩 핸들러 : 트랩 핸들러 호출 후 "다음(next)" 명령어 실행
TLB의 트랩 핸들러 : 트랩 핸들러 호출 후 "현재(current)" 명령어 재실행

 

따라서 TLB에서의 트랩 핸들러는 현재 명령어를 재 실행하므로 무한 반복되지 않도록 주의해야 하는데, 무한 반복을 방지 하는 방법은 다음과 같다

(1) TLB 트랩 핸들러를 물리주소로 직접 할당한다 : 이렇게하면 주소 변환이 필요없음

(2) TLB 트랩 핸들러의 일부를 핸들러 코드 주소에 영구히 저장 : 이렇게하면 TLB 핸들러는 항상 TLB에서 cache hit

---

5. TLB의 문제점과 해결방안

TLB 또한 문제점을 갖고있는데, Context Switching(문맥 교환)이 일어날때 문제가 생긴다.

Process A 에서 TLB 테이블에 데이터를 삽입

이후 Process B로 Context Switching이 일어나 B process에서 TLB 테이블에 데이터를 삽입

위 경우에 Process A의 VPN 10번 주소의 변환 정보, Process B의 VPN 10번 주소의 변환 정보가 TLB Table에 담겨있다.

하지만 두 vpn 10번에 대한 구분이 불가능하므로, 이후 한 프로세스가 접근하려 할때, 어떤걸 참조할지 몰라버리게 된다.

이를 해결하기 위해 문맥 교환을 수행할 때 기존 TLB 내용을 Clear 하는 방식을 고안했지만, 문맥 교환시마다 claer를 수행 하는것은 비용적으로 부담이 된다.

그래서 생각 해 낸 것이, ASID, 즉 TLB 내에 주소 공간 식별자를 추가하는 방안이다!

PID와 유사한 개념으로 TLB의 프로세스 ID을 식별하여 프로세스 간 구분이 가능한 것이다.

 

고유 ASID 를 추가해 프로세스 간 식별이 가능해진 모오습

---

다음 장에선 페이징의 또 다른 문제점에 대해 다뤄보겠다 !!!