2024. 5. 31. 21:49ㆍCS/Operating System
TLBs
페이지 테이블을 거쳐서 메모리에 액세스 하면 시간이 많이 걸린다. original page table은 doubled the cost of memory lookups 하다. Two-level에서는 triple the cost 하다!
시간적인 오버헤드를 줄이기 위해서 도입된 게 TLB이다. TLB의 목적은 메모리 액세스 한 번의 수준으로 물리 주소를 얻는 것이고, 해결책은 캐싱밖에 없다.
페이지 테이블의 일부 내용을 캐싱하고 있는 하드웨어가 Translation Lookaside Buffer TLB이다. MMU안에 TLB가 들어있다.
TLB는 어떻게 구성되어 있을까?
- 캐시 안에는 페이지 테이블과 상당히 유사한 데이터를 가지고 있다.
- 그림에는 없지만 ref가 있을 것이다.
- 캐시를 태그로 사용하기 위해 virtual page도 가지고 있다.
- TLB는 하드웨어이고, 일반적으로 Fully associative cache이다.
- 캐시를 쓸 때 보통 태그를 쓴다. 내가 원하는 데이터가 캐싱된 데이터가 맞는지 확인하기 위해 태그를 쓰고, 여기서는 page number가 된다.
- 캐시에 들어있는 값들은 페이지 테이블 엔트리들이 될 것이다.
- PTE와 offset을 잘 조합하면 MMU가 피지컬 어드레스를 계산할 수 있다.
TLB는 캐시이기 때문에 로컬리티를 역시 사용한다.
- TLB는 로컬리티가 굉장히 좋을 것이다. 페이지 테이블은 한 번 액세스 하면 자주 액세스하기 때문이다. hit율이 굉장히 높다.
캐시 복습
CPU는 메모리의 일부를 가지고 있는 L1 캐시 등을 가지고 있다. CPU가 데이터 x에 액세스 해야 한다면 L1을 뒤져 뒤져볼 것이다. 그때 사용하는 게 아래의 그림이다. 앞의 20bit가 태그로 사용되었는데, 이 회로를 잘 이해해자!`
Direct Mapped Cache
액세서하려는 데이터의 address가 캐시의 어느 위치에 캐싱될지를 결정하는 캐시가 Direct Mapped Cache이다.
뒤의 3bit만큼 잘라낸 001이 캐시의 001에 들어갈 수 있다. 그림에서 회색인 메모리들은 회색 캐시에만 들어갈 수 있다.
회색인 데이터가 내가 찾는 게 맞는지 확인하기 위해 앞의 두 비트를 태그로 사용해서 비교한다.
이 방식의 장점은 쉽다는 것이다. 단점은 캐시 미스의 비율이 보통 높다. 다른 공간이 비었음에도 회색 얘들은 회색 캐시만 두고 싸운다.
Set associative
다른 공간이 비었음에도 회색 얘들은 회색 캐시만 두고 싸우는 현상 극복하고자 Set associative가 등장했다.
캐시를 여러 개씩 묶어서 여러 개의 칸들에 들어갈 수 있게끔 빈 곳에 들어가게 하는 것이다. 대신 태그를 동시에 비교해야 하므로 하드웨어가 더 비싸진다.
Fully associative 방식은 전체를 한 집합으로 보고, 빈 곳이라면 캐싱하는 방식이다. 태그를 한 번에 모든 캐시를 비교해야 하므로 더 비싸긴 한데 캐시 확률이 훨씬 높다.
그렇다 보니 TLB는 히트율이 매우 높다. 비싸더라도 감수하고 Fully associative로 한 것이다.
TLB 말고 일반적인 캐시는 Fully associative로 갈수록 비싸지만 미스 확률이 낮아진다. 1 way는 얼마 4 way는 얼마 이런 게 있지만 TLB는 가격을 감수하고 그냥 좋은 걸 쓰는 게 전체 성능을 높여준다.
Translation Using a TLB
- TLB에서 태그를 검색할 때 Fully associatve로 구현된 덕분에 태그의 검색이 한 클락 안에 하드웨어적으로 매우 빠르게 TLB에서 태그를 검색할 수 있다.
- TLB 태그 중에 찾는 데이터가 없다면 페이지 테이블을 뒤져본다.
- TLB에서 미스가 났다면 페이지 테이블에서 찾고, 찾은 엔트리 전체를 TLB에 캐싱해 두고 다시 시작해서 TLB로 접근한다. 이렇게 하는 이유는 locality 때문이다.
TLB를 사용해서 주소를 번역하는 과정을 정리해 보자.
- 32bit의 logical address를 잘라서 page number로 만들고 TLB에서 병렬적으로 태그를 찾는다.
- TLB에서 miss가 났다면 페이지 테이블에서 p를 가지고 찾아서 f를 TLB에 올린다.
- restart using tlb, TLB에서 바로 찾을 테고, 그걸 사용하게 된다. 그림과는 조금 다른 것이다.
- 중요한 건 TLB에서 99% 이상 hit가 난다는 것이다. 거의 페이지 테이블을 사용하지 않고도 TLB만 이용해도 address를 translation 할 수 있게 되는 것이다. 그럼 원래 두 번 메모리 액세스 하던것을 거의 한 번에 가까운 시간에 엑세스 할 수 있다.
TLB에서 miss가 났을 때 누가 TLB에 찾은 frame을 올려 줄까?
- 하드웨어 (MMU) : 인텔
- 하드웨어가 할 수 있다면 훨씬 빠를 것이다.
- 이를 위해서는 하드웨어가 페이지 테이블이 메모리의 어디에 있는지 알아야 하고, 페이지 테이블의 엔트리를 긁어올 수 있어야 한다.
- 사실 페이지 테이블의 위치를 저장하는 레지스터가 있어서 해당 레지스터에 접근하면 바로 페이지 테이블에 접근해서 긁어올 수 있다.
- 그런데 이렇게 되려면 페이지 테이블이 하드웨어에 정의된 format을 따라야 한다.
- 소프트웨어 (OS)
- page fault가 일어나면 page fault handler를 호출하듯이 TLB miss가 나면 TLB miss handler를 돌리는 방식이다.
- 운영체제가 페이지 테이블을 찾고 TLB에 올려야 한다.
- 이를 위해서는 운영체제가 사용할 수 있는 특수한 instruction을 통해 가능하다. 이건 당연히 빠르면 좋다. TLB를 다루는 데 있어서 CPU가 제공하는 특별한 ISA가 있어야 한다.
- 장점은 운영체제에게 좀 더 flexible 하게 format을 유동적으로 변경할 수 있다.
실제로는 성능상의 문제로 하드웨어를 사용하고, 페이지 테이블은 정의된 format대로 동작한다.
Managing TLBs
TLB를 잘 관리하기는 쉽지 않다. consistent를 지켜줘야 하기 때문이다. TLB의 값과 TLB가 캐싱하는 테이블의 값에 대해 일관성이 잘 유지되어야 한다는 뜻이다.
- 만약 페이지 테이블에서 어떤 값이 바뀌면 TLB 엔트리 자체를 invalidation 시켜야 한다. TLB의 해당 엔트리 자체가 쓸모없다고 표시해 두는 것이다.
- 따라서 운영체제는 페이지 테이블의 내용이 바뀌게 되면 TLB에서 찾아서 valid bit를 0으로 만든다.
- 그럼 해당 엔트리에 대해 miss가 나서 페이지 테이블에 접근하게 된다.
또 중요한 것은, 페이지 테이블은 프로세스마다 가지고 있다.
- 그렇다면, TLB도 프로세스마다 가지고 있어야 할 것 같은데 사실 TLB는 하드웨어라 딱 하나만 존재한다. 콘텍스트 스위치가 일어나면 페이지 테이블 자체가 바뀌면서 아예 다른 내용을 TLB가 캐싱하고 있는 상태가 된다.
- 즉, 컨텍스트 스위치가 일어나면 TLB는 새로운 프로세스를 위한 테이블로 새로 채워 넣어야 한다. TLB를 싹 다 지울 필요는 없고 invalid bit를 0으로 설정해 두면 된다. 그리고 새로운 프로세스가 어떤 데이터에 접근하면 miss가 나게 되고 그럼 TLB 엔트리가 하나씩 바뀌면서 해결된다.
- 인텔 아키텍처에서는 TLB flush가 자동으로 일어난다. 콘텍스트 스위치가 일어나면 CR3라는 레지스터의 값이 변한다. CR3는 어떤 프로세스가 쓰는 페이지 테이블의 첫 값을 저장하고 있다.
- 만약 이렇게 하지 않으면 TLB 엔트리에 PID를 모두 가지고 있어야 한다. 이럼 inverted처럼 프로세스가 내려가면 다 검색해야 한다는 문제가 또 생기기에 flush 시키는 게 낫다.
- 사실 TLB를 flush 시키고 나면 TLB가 텅텅 비었다는 거고 어느 정도까지는 계속 miss가 나고 어느 순간부터 hit가 나면서 해결될 것이다. 그런데 이 오버헤드가 꽤 크다. 콘텍스트 스위치의 큰 오버헤드 중 하나도 이 TLB flush이다.
TLB flush 때문에 TLB가 miss가 나면 누군가는 TLB에서 내려가야 한다.
- 피지컬 한 메모리가 꽉 차면 디스크로 내리는 방식이 page demanding이다. 똑같은 게 TLB에서도 일어난다.
- TLB replacement ploicy가 하드웨어적으로 잘 구현되어 있다.
TLB에 캐싱하고 있는 엔트리가 페이지 테이블에서 디스크로 내려가게 되면, 해당 엔트리는 페이지 테이블에서 invalid 상태가 된다. 그럼 페이지 테이블의 해당 엔트리에 변화가 있는 것이고 TLB의 해당 엔트리 또한 invalid 된다.
Memory Reference
TLB를 사용해서 메모리에 접근하는 상황은 어떻게 나뉠까?
The common case (TLB hits)
- MMU에서 TLB로 read, write가 일어난다.
- TLB는 address의 page number를 가지고 lookup 한다.
- 그걸 protection bit를 보고 read/write 등 보호를 확인한다.
- 문제가 없다면 피지컬 한 프레임을 특정할 수 있다.
- MMU는 프레임 넘버와 offset으로 피지컬한 어드레스를 만들어낸다.
- MMU는 피지컬한 어드레스에 접근해서 CPU에 넘겨준다.
TLB miss
TLB miss가 나는 경우에는 두 가지 선택지가 있다. 누가 TLB에 PTE를 채워 넣을까에 관한 선택이다.
- 하드웨어 MMU
- MMU는 OS의 관여는 전혀 없이 필요한 엔트리를 TLB에 채워 넣으면 끝이다.
- Trap to the OS
- 트랩이 발생하게 되고, OS는 핸들러를 호출한다.
- OS는 페이지 테이블을 볼 수 있고 찾아서 TLB에 PTE를 로드시키고 다시 시작시킨다.
TLB miss를 핸들링하고 난다면 TLB 안에는 valid PTE가 분명 있을 거고 retry 하면 TLB hit case처럼 동작한다.
TLB miss : recursive fault
가장 문제가 되는 케이스이다.
- TLB가 miss가 났는데, 페이지 테이블 자체가 디스크에 내려가있는 경우인데, 사용하지 않는 테이블 자체를 디스크에 내릴 수 있기 때문에 이런 케이스가 가능하다.
- 그럼 page fault handler를 실행하고 페이지 테이블을 메모리에 올리게 된다. 그리고 다시 retry 한다.
- 또 TLB miss가 발생하고 가져온 페이지 테이블에 접근했는데 또 실제 페이지가 디스크에 내려가있어서 page fault가 또 일어나는 케이스가 생길 수 있다.
Page fault는 사실 두 종류이다.
- Protection 때문에 execution 할 수 없는데 execute 연산이 들어오는 경우도 page fault이다.
- 당연히 operation이 허용되지 않을 거고 protection fault라고 하긴 하지만 일반적인 용어로 page fault라고도 한다.
- page fault가 invalid 한 경우 페이지가 디스크에 있을 수 있고 페이지 테이블 자체가 디스크에 있을 수 있다.
어떤 케이스던 page fault가 발생하면 트랩이 생기게 되고 운영체제 코드가 실행된다.
- Read/Write/Execute : OS는 보통 프로세스에게 fault를 돌려보내거나 copy on write, mapped files 등의 기법을 사용한다.
- Invalid(메모리 자체가 할당이 되지 않음) : 프로세스에게 알려주면 끝이다.
- Invalid(피지컬 한 메모리에 없고 디스크에 내려가 있음) : page fault handling, frame을 할당하고 disk에서 읽어와서 페이지 테이블을 업데이트시키고 다시 시작한다.
TLB hit 총 정리
- TLB hit
- 대부분 이 케이스이다.
- 엔트리를 찾아낼 수 있고 엔트리 자체도 피지컬 한 프레임에 할당되어 있는 경우
- 메모리 액세스가 한 번 일어난다.
- 그림으로 따지면 p로 f를 찾았는데 f가 메모리에 할당된 경우이다.
- 드물게 TLB에는 있는데 그게 할당되지 않아서 page fault가 일어난 상황도 존재한다.
- 이게 왜 엄청나게 드무냐면 보통의 상황에서는 TLB hit인데 page fault 일 수 없다.
- PTE가 디스크로 내려간다면 TLB도 업데이트하기 때문인데, 이 케이스는 테이블 자체가 내려가면 가능하긴 하다.
- 이 경우에도 메모리 액세스는 한 번 일어난다.
- TLB miss - page table is in memory
- 메모리에 존재하는 페이지 테이블에서 찾아서 TLB를 업데이트하고 다시 시작한다.
- frame이 메모리에 있으면 두 번의 메모리 액세스가 일어나지만, frame이 없다면 page fault가 발생해 세 번의 메모리 엑세스와 한 번의 디스크 엑세스가 일어난다.
- TLB miss - page table is page out
- page table을 위한 page fault handler를 실행한다. -> 메모리 한 번, 디스크 한 번 엑세스
- 페이지 테이블을 올리고 TLB을 업데이트 한 뒤 restart 한다. -> 메모리 한 번 엑세스
- 여기서도 또 프레임에 대해 page fault가 일어날 수 있고 안 일어날 수 있다. → reculsive page fault
- 프레임에 대한 pf가 일어나지 않았다면 메모리 액세스가 총 세 번, 디스크 엑세스가 한 번 일어나고, pf가 일어났다면 메모리 엑세스 네 번, 디스크 엑세스가 두 번 일어난다.