19. 페이징을 위한 더 빠른 변환, TLB의 등장 :
가상 메모리를 지원하고자 등장한 핵심 메커니즘인 페이징은 엄청난 퍼포먼스 오버헤드를 불러일으키게 된다,,, 라는 것을 지난 시간에 같이 알아보았다. 주소 공간을 작고, 획일적인 고정 사이즈의 조각들(이 조각들을 페이지라고 부른다.)로 잘라냈기 때문에, 페이징이라는 기법은 엄청난 매핑 정보를 요구하게 되었다.
매핑 정보가 일반적으로 물리 메모리에 상주하게 되기 때문에, 이대로라면 페이징은 프로그램이 생성한 각각의 가상 주소들의 실제 위치로 찾아가기 위해 추가적으로 메모리를 조회해야 하는 운명이다,,, 명령어를 fetch 하기도 전에, 그리고 외부로 load/store를 처리하기 위해, 우리는 정보 번역을 하려면 메모리로 가야만 하고 이러한 행위는 연산을 엄청나게 느리게 만든다.
요점 : 자, 그렇다면 어떻게 주소 변환을 빠르게 할 수 있을까? 어떻게 우리는 주소 변환을 빠르게 하고, 페이징이 요구하는 추가 메모리 참조를 피할 수 있을까? 어떤 하드웨어 서포트가 필요할까? 이때 OS는 어떤 역할을 할 수 있을까?
우리가 뭔가를 빨리빨리 하고 싶을 때는, 으레 OS가 도움을 주곤 했다. 그리고 또한 항상 그럴 땐 OS의 오랜 단짝 친구, 하드웨어도 등장하는 법이다.
주소 변환을 빠르게 하기 위해, 우리는 이제 소위 TLB(Translation-lookaside buffer)라고 불리는 녀석을 도입할 것이다. TLB는 칩에서 MMU라 불리는 메모리 관리 유닛의 일부고, 가상 주소를 물리 주소로 번역해주는 하드웨어 캐시다. 그러니까, 더 좋은 이름은 주소-변환 캐시 정도가 어떨까.
각각의 가상 메모리 참조를 수행할 때, 하드웨어는 TLB를 먼저 보고 원하는 변환 정보가 있는지 체크해본다. 만약 운 좋게 우리가 바라는 정보가 있다면, (모든 변환 정보를 다 들고 있는) 페이지 테이블까지 다녀오지 않고, (아주 빠르게) 그대로 변환을 수행한다. 이것이 엄청난 퍼포먼스 이득을 가져오기 때문에, TLB가 진정하게 가상 메모리를 가능하게 만들었다고 볼 수 있다.
TLB의 기본 구조 :
아래 그림은 어떻게 하드웨어가 가상 주소 번역을 핸들링하는지에 대한 개략적인 스케치다. 이때 페이지 테이블의 엔트리들은 linear 한 순서로 저장되어 있고, 하드웨어가 관리하는 TLB가 함께 있다고 가정했다.
1 VPN = (VirtualAddress & VPN_MASK) >> SHIFT
2 (Success, TlbEntry) = TLB_Lookup(VPN)
3 if (Success == True) // TLB Hit
4 if (CanAccess(TlbEntry.ProtectBits) == True)
5 Offset = VirtualAddress & OFFSET_MASK
6 PhysAddr = (TlbEntry.PFN << SHIFT) | Offset
7 Register = AccessMemory(PhysAddr)
8 else
9 RaiseException(PROTECTION_FAULT)
10 else // TLB Miss
11 PTEAddr = PTBR + (VPN * sizeof(PTE))
12 PTE = AccessMemory(PTEAddr)
13 if (PTE.Valid == False)
14 RaiseException(SEGMENTATION_FAULT)
15 else if (CanAccess(PTE.ProtectBits) == False)
16 RaiseException(PROTECTION_FAULT)
17 else
18 TLB_Insert(VPN, PTE.PFN, PTE.ProtectBits)
19 RetryInstruction()
먼저, 가상 주소로부터 가상 페이지 번호를 추출한다.(1) 그리고 이 가상 페이지 번호에 대한 번역 정보를 TLB가 들고 있는지 체크한다.(2) 만약 맞다면, 성공! TLB 히트다.(3) TLB가 우리가 원하는 정보를 잘 들고 있다는 소리다. 그럼 일단 바로 출발하지 말고, 해당 주소의 프로텍션 여부를 체크해봐야 한다.(4) 오케이라면, 적절한 TLB 엔트리에서 주소 번역을 수행해서 페이지 프레임 번호를 따와서 가상 주소의 오프셋과 합쳐서 물리 주소를 완성하고, 우리가 가고 싶은 메모리 위치로 가면 된다.(5-7) 만약 보호되고 있는 페이지라면, 프로텍션 폴트를 호출해서 프로세스를 종료시킨다.(8-9)
프로세서가 만약 TLB 안에서 원하는 변환을 못 찾았다면(10), TLB 미스다. 이 경우엔 몇 가지 일을 더 해야 한다. 이번 예제에서, 하드웨어는 주소 번역을 위해 페이지 테이블로 접근한다.(11-12) 이후는 이전 챕터에서 공부했던 것과 유사하다. Valid를 체크하고(13-14), 프로텍션을 체크하고(15-16), 둘 다 오케이라면 TLB를 업데이트하고 다시 시도한다.(18-19)
TLB 미스가 나면 추가 사이클을 들여서 메모리를 추가로 참조하고, TLB를 업데이트하고 나서, 재시도하는 비용이 발생한다. 그래도 이렇게 잘 적어두고 재시도를 하면 다음부터는 수행이 빨라질 것이다.
물론 모든 캐시에 다 통용되는 이야기지만, 캐시가 쓸모 있으려면 지극히 당연하게도 우리가 원하는 번역 정보가 캐시 안에 있는 걸 전제로 하는 것이다.(즉, 히트일 때) 만약 그렇다면, 약간의 오버헤드를 가지겠지만, TLB가 메인 메모리보다는 코어와 가까이 있기 때문에, 디자인 상 더 빨라질 것이다.
반대로 미스가 나면, 비싼 값을 치러야 한다. 번역을 하기 위해 페이지 테이블에 가야 하고, 추가로 메모리를 참조해야 한다.(명령어 종류에 따라 더 귀찮은 페이지 테이블 조회가 수반될 수도 있다.) 이렇게 미스가 자주 나면, 프로그램 수행은 눈에 띄게 느려질 것이다. 대부분의 CPU 명령어에 해당하는 메모리 접근은 비용이 많이 들고, TLB 미스는 더 많은 메모리 접근을 요구한다. 그러니까, 가능한 TLB 미스가 안 나도록 하는 게 매우 중요하다고 할 수 있겠다.
배열 접근 예제 :
TLB 동작을 명확히 보기 위해, 간단한 가상 주소 트레이스를 시험해보자. 또한 TLB의 도움으로 퍼포먼스가 얼마나 향상할 수 있는지 알아보자. 여기선 우리가 4-바이트짜리 정수 배열이 메모리에 있다고 가정한다. 가상 주소는 100번지에서 시작한다. 또한 16-바이트 사이즈의 페이지들과 자그마한 8-비트 가상 주소 공간을 가지고 있다고 하자. 그러므로 가상 주소는 4-비트 VPN(가상 페이지 16개까지 매핑 가능하겠죠?)과 나머지 4-비트 오프셋(왜냐하면 페이지 크기가 2^4 byte니까)으로 쪼개진다.
이제 여러분들은 아래 그림처럼 16개의 16-바이트 크기의 페이지들로 이루어진 시스템을 상상할 수 있을 것이다.
여러분들이 보시는 바와 같이, 배열의 첫 엔트리(a [0])는 VPN = 6, 오프셋 = 4에서 시작하고 있다. 그래서 이 페이지에서는 4개의 integer까지 들어갈 것이다. 배열 엔트리는 이런 식으로 칸에 맞춰 순서대로 쭉쭉 저장되어 a [9]까지 저장되어 있다고 하자. 이제 뭔가 C언어 비슷한 배열 element 접근에 관한 간단한 루프 예제를 생각해보자.
int sum = 0;
for (i = 0; i < 10; i++) {
sum += a [i];
}
단순하게 보기 위해, 변수 i나 sum 관련된 메모리 접근은 못 본 척 무시하고 오직 배열 a []에 대해서만 집중할 것이다. 맨 처음 a [0]에 접근할 때 CPU는 가상 주소 100번지를 보려고 할 것이다. 하드웨어는 이에 해당하는 VPN = 6을 레지스터에서 추출하고, valid 한 지 TLB를 볼 것이다. 근데 여기서 소위 콜드 스타트 미스라고 불리는 compulsary TLB miss가 났다고 해보자.(메모리 접근의 첫 시도는 캐시가 비어있어서 무조건 미스가 날 수밖에 없는 상황) 그럼 위에서 설명한 바와 같이 직접 메인 메모리까지 다녀와서 물리 주소를 찾아온 뒤에 TLB를 업데이트할 것이다.
다음 접근은 배열의 두 번째 element인 a [1]인데, 좋은 소식이 있다. 이번에는 TLB 히트다! 사실은 a [1]은 a [0]과 같은 가상 페이지 번호로 묶여있기 때문에, 방금 a [0]를 업데이트할 때 함께 불려 온 것이다. 그래서 a [1]의 위치는 캐시에서 빠르게 찾을 수 있는 것이다. a [2]도 마찬가지 이유로 히트가 나올 것이다.
불행히도, a [3]를 가져올 땐 TLB에 없어서 미스가 난다. 그러나 뒤의 세 개를 가져올 땐 히트가 날 것이다. 규칙성을 눈치챘는가? 여기 a [0]부터 a [10]까지 10번의 접근의 TLB 히트, 미스 여부를 H 혹은 M으로 표기해서 순서대로 쓰면 다음과 같다. M, H, H, M, H, H, H, M, H, H. 그러니까 hit rario를 70%라고 말할 수 있겠다. 근데 우리는 이 정도로 만족할 수 없다.(우리는 거의 100%에 도달하는 hit ratio를 원한다.)
비록 페이지가 바뀔 때마다 메모리까지 다녀와야 하지만, 그렇지 않은 경우는 배열의 원소들이 페이지 내에서 가까이에 모여 있기 때문에, spatial locality의 원리로 성능 향상을 기대할 수 있는 것이다.
페이지 사이즈가 이 예제에서 어떤 역할을 하는지 생각해보자. 만약 단순히 현재 구조에서 페이지 사이즈만 2배가 된다 치면, (즉, 페이지 사이즈가 32 바이트) 미스가 덜 날 것이라는 건 충분히 예측할 수 있을 것이다. 일반적으로 페이지 사이즈는 4KB이고, 방금 본 예제처럼 dense 한 배열 기반의 접근은 페이지가 바뀔 때마다 딱 한 번씩의 미스만 내면서 훌륭한 TLB 퍼포먼스를 보여줄 것이다.
만약에 이 프로그램을 다 돌리고 나서 또다시 배열 a에 접근하는 경우를 생각해보자, 이번엔 TLB에 10개의 배열이 위치한 페이지 번역 정보가 다 들어있기 때문에, 훨씬 더 좋은 결과를 보여줄 것이다. 다시 접근하기 전에 해당 페이지를 교체하지 않았다면, 100% 히트가 날 것이다. 이런 이득을 전문 용어로 temporal localty의 원리라고 부른다. 방금 참조한 정보를 조만간 또 재 참조한다는 뜻이다. 다른 여느 캐시처럼, TLB도 이런 프로그램 특징에 따른 spatial과 temporal locality의 영향을 강하게 받는 법이다. 만약에 실행되는 프로그램이 이런 지역성의 원리를 가지고 있다면, (사실 많은 프로그램이 그러하다.) TLB hit rate는 높게 나올 것이다!
지나가는 글 : 할 수 있을 때 캐싱하라.
캐싱은 컴퓨터 시스템에서 굉장히 중요하고 본질적인 성능 향상 기술입니다. "Common-case fast"라는 유명한 말과도 부합하죠.(자주, 반복적으로 발생하는 연산, 상황을 단순화하여 성능을 올린다는 컴퓨터 분야의 기초적이고 중요한 원리입니다.) 하드웨어 캐시라는 개념에 깔린 중심 아이디어는 명령어와 데이터 참조에서 지역성의 원리를 이용하자는 것입니다. 지역성은 시간 지역성과 공간 지역성이 있습니다. 시간 지역성의 원리란, 최근에 접근되어왔던 명령어나 데이터가 근미래에 또 재접근되기 쉽다는 뜻입니다. 반복문의 변수나 반복문 내의 명령어를 생각해보세요. 시간이 지남에 따라 반복적으로 접근되는 것을 알 수 있습니다. 공간 지역성은 만약 어떤 프로그램에서 메모리 주소 x에 있는 값이 접근되었다면, 곧 x 근처에 있는 값이 또 접근될 수 있다는 원리입니다. 배열 내에서 한 원소에 접근하고 그 직후에 바로 다음 원소에 접근하는 스트리밍의 예를 생각해보세요. 물론, 이런 특성들은 프로그램마다 조금씩 다를 수 있습니다. 그러니까 엄격한 법이라기보단 Rules of thumb이라는 것이죠.
명령어, 데이터, 주소 변환(우리가 지금 공부하는 TLB) 등 다양한 목적의 하드웨어 캐시가 있죠. 이런 캐시들은 작고, 빠른 온칩 메모리 안에 값을 복사해두고 지역성의 이점을 이용하고 있습니다. 요청을 수행하기 위해 느린 메인 메모리로 가는 대신, 프로세서는 먼저 자기와 가까이 있는 근처 캐시 안에 자기가 찾는 복사본이 있는지 확인하게 됩니다. 만약에 자기가 필요한 값이 존재한다면, 프로세서는 그 값에 빨리 접근할 수 있겠죠(즉, 더 작은 클럭 사이클을 들여서요.). 그리고 느린 메인 메모리까지 다녀오는 아까운 시간을 아낄 수 있을 겁니다.
당신은 이런 질문을 할 수도 있겠죠. 아니, 그렇게 캐시가 유용하고 좋으면서, 왜 우리는 훨씬 큰 캐시를 만들어서 데이터를 다 때려 박아 담아두지 않는 거지? 불행하게도, 더 본질적인 물리학의 법칙들을 고민해야 합니다. 만약에 빠른 캐시를 원한다면, 용량을 작게 설계해야 하죠. 전자기파의 속도나 여타 물리학적 제한들이 관련되어 있습니다. 그렇기 때문에 거대한 캐시는 느려질 것이고, 원래 목적에 부합하지 않을 겁니다. 그래서 우리는 작고, 빠른 캐시를 추구하게 됩니다. 이제 우리가 생각해야 할 것은 이러한 캐시들을 잘 활용하는 방법일 것입니다.
누가 TLB Miss를 핸들링 해주나? :
우리가 반드시 답해야 할 질문이 하나 있는 것이다. TLB가 Miss 나면 누가 핸들링해주지? 두 단짝 친구가 답이 될 것이다. 바로 하드웨어와 OS다. 오래전에는 하드웨어가 CISC (Complex-Instruction Set Computers)라는 복잡한 명령어 셋을 가지고 있었다. 그리고 그 당시 하드웨어를 짜는 사람들은 OS 짜는 사람들을 얍삽하다고 생각했고, 그다지 신뢰하지는 않았던 것 같다.
그래서 하드웨어가 TLB 미스가 났을 때 전체적으로 핸들링할 수 있어야 했다. 이를 위해선 하드웨어가 메모리 안에 페이지 테이블이 어디에 있는지 아주 정확하게 알고 있어야 했다.(지난 시간에 배운 page table base register를 통해서,) 마찬가지로 포맷도 정확하게 알아야 했다. 미스가 난 "바로 그 페이지 테이블 엔트리"에 하드웨어가 찾아갈 수 있어야 했고, 바람직한 번역 정보를 뽑아서 TLB를 업데이트한 뒤에, 명령어 처리를 재시도했다.
여기서 말한 "오래전"에 해당하는 아키텍처가 바로 인텔 x86 아키텍처이고, 고정된 멀티 레벨 페이지 테이블을 사용하는 하드웨어 관리 기반의 TLB를 가지고 있었다.(다음 챕터에서 자세히 살펴볼 것이다.) 당대의 CR3 레지스터는 페이지 테이블을 가리키는 용도로 사용되었다.
좀 더 이후에 출시된 아키텍처(MIPS R10k나 Sun 사의 SPARC v9 등 RISC 기반 컴퓨터)로 넘어오면, 소위 소프트웨어 관리 기반의 TLB라고 알려진 것을 들고 있게 된다. 이 구조에서 TLB 미스가 발생하면, 하드웨어는 예외 처리를 발생시킨다. 그러면 하드웨어는 현재 수행 중인 명령어 스트림을 멈추고 trap handler로 점프하고, 커널 모드가 제어권을 넘겨받게 된다.
당신이 예측했다시피, 이 trap hadler는 TLB 미스를 핸들링하는 목적으로 적힌 OS 내부 코드다. 이것이 실행되면, 코드는 페이지 테이블 내의 번역 정보를 뒤지고, 특별한 "권한" 명령어를 사용해서 TLB를 업데이트하고, trap 발생 지점으로 돌아온다. 이 시점에서 하드웨어는 명령어를 재시도하게 된다.(이번에는 TLB 히트가 나올 것이다.)
여기서 몇 가지 짚어봐야 할 것이 있다. 여기서의 return-from-trap 명령어는 일반적인 시스템 콜 할 때와는 조금 다른 점이 있다. 즉, 여기서의 return-from-trap은 OS의 트랩 발생 이후에 명령어 처리를 바로 그 시점에서 다시 수행할 수 있어야 한다. 마치 프로시저 콜로부터 반환된 상태가 프로시저 콜 직후의 명령어로 돌아오는 것처럼 말이다. 전자의 경우는, TLB 미스 핸들링 트랩으로부터 돌아왔을 때, 하드웨어가 반드시 그 트랩이 난 지점의 명령어를 재개해야만 한다. 이 재시도는 명령어를 다시 수행시킬 것이고, 이번에는 TLB 히트가 날 것이다. 그러므로, 어떻게 트랩이나 예외처리가 났느냐에 따라서, 하드웨어는 반드시 OS에서 트랩이 발생한 또 다른 프로그램 카운터를 저장해 두고 있어야 하며, 그 처리가 끝나고 돌아왔을 때 적절히 재개할 수 있어야 한다.
둘째, TLB 미스 핸들링 코드가 돌고 있을 때, OS는 TLB 미스들이 일으킨 무한 반복의 체인에 빠지지 않도록 추가적으로 주의를 기울여야 한다. 여기에는 많은 해결법이 존재한다. 예를 들어, TLB miss handler를 물리 메모리 안에 들고 있거나(매핑하지 않고 주소 변환과 상관이 없는 장소에), 영구적으로 valid 한 변환을 가진 몇몇 TLB 엔트리를 남겨둔다던지, 핸들러 코드 안에 영구적인 변환 슬롯을 남겨둬서 이것에 연계된 변환은 항상 히트가 난다던지 하는 다양한 기법들이 있다.
OS가 관리하는 접근법의 주된 장점은 그 flexibility에 있다. OS는 하드웨어의 변경 없이 구현하고 싶은 페이지 테이블의 어떤 구조든지 사용할 수 있다. 또 다른 장점은 위에서 TLB control flow에서도 확인할 수 있듯, simplicity다. 하드웨어가 미스가 났을 때 많은 일을 할 필요 없다. 예외 처리를 발생시킨 뒤 OS가 처리해줄 때까지 기다리고 있으면 되는 것이다.
지나가는 글 : RISC vs. CISC
1980년대에 컴퓨터 아키텍처 학계에 큰 싸움이 일어났습니다. 한쪽은 CISC(Complex Instruction Set Computing) 파였고, 반대쪽은 RISC(Reduced Instruction Set Computing) 파였죠. RISC 측은 버클리의 데이비드 패터슨과 스탠퍼드의 존 해네시가 있었습니다.(나중에 존 코크도 초기 RISC에 기여를 인정받아 튜링 상을 수상했죠.) CISC 명령어 셋은 명령어 개수가 많은 경향이 있었고, 각각의 명령어는 상대적으로 강력했습니다. 예를 들어, 스트링 카피의 경우에는 두 포인터와 길이를 사용해서 출발지에서 목적지로 바이트를 복사할 수 있었습니다. CISC가 가진 기저 아이디어는 명령어가 high-level에 기초를 두고 있다는 것이고, 그래서 어셈블리 어가 사용하기 쉬웠고, 그렇기에 코드 또한 간결하다는 장점이 있었습니다.
RISC 명령어 셋은 정확히 상반됩니다. RISC의 주요 목적은 명령어 셋이 컴파일러의 타깃이고, 모든 컴파일러가 원하는 것은 고성능 코드를 작성하는 데 사용될 수 있는 적고 단순한 요소라고 생각했습니다. 그래서 RISC 신봉자들은 하드웨어로부터 가능한 많은 부분을 제거하고(특히, 마이크로코드), 남은 것을 쉽고, 획일적이고, 빠르게 만들자고 주장했습니다.
초창기엔 눈에 띄게 빠른 RISC 칩이 큰 영향을 끼쳤습니다. 이에 관한 많은 논문이 나왔고, 몇몇 회사들이 생겼죠.(MIPS와 Sun) 그러나, 시간이 지남에 따라 인텔 등 CISC 제조업자들이 많은 RISC 기술들을 그들의 프로세서의 코어에 집어넣기 시작했습니다. 예를 들어, 복잡한 명령어에서 RISC 방식과 유사한 처리가 가능하도록 마이크로 명령어로 변형시킨 초기 파이프라인 단계의 도입이 있습니다. 이러한 혁신은 칩의 단위 면적당 박을 수 있는 트랜지스터의 숫자가 늘어남과 더불어 CISC가 경쟁력을 유지할 수 있게 해 주었습니다. 결론적으로 지금은 논쟁이 잦아들었고, 오늘날에는 두 타입의 프로세서 모두 빠르게 동작하도록 만들 수 있게 되었습니다.
TLB 안에는 뭐가 있나? :
하드웨어 TLB 안에는 뭐가 들어있는지 더 자세히 알아보자. 전형적으로, TLB는 32, 64, 128개의 entry를 가지고 fully-associative 하다. 기본적으로 이는 어떠한 변환도 TLB 안에 어디에든지 있을 수 있다는 것이다. 그리고 하드웨어는 자기가 찾고 싶은 번역 정보를 찾기 위해 엔트리를 전체 다 뒤져야 한다는 소리가 된다. TLB 엔트리는 당연하게도 VPN, PFN, 그리고 기타 비트로 이루어져 있다.
주소 번역이 버퍼 안에서 어디에서든지 일어날 수 있기 때문에, VPN과 PFN이 각각 엔트리에 있다는 것을 생각하라.(다시 한번 말하지만, TLB는 하드웨어 용어로 fully-associative 캐시다.) 아까도 말했지만, 하드웨어는 자기가 찾는 게 있는지 병렬적으로 모든 엔트리를 다 뒤져봐야 한다.
더 흥미로운 사항은 "기타 비트"다. 예를 들어, TLB는 흔히 유효성 비트로도 불리는 valid bit를 가질 수 있는데, 해당 엔트리의 변환이 유효한지 아닌지 알려준다. 또한 보호 비트라 고도 불리는 protection bit를 가질 수 있는데, 해당 페이지를 액세스 할 수 있는지 결정한다.(페이지 테이블 안의 그것과 유사한 셈이다.) 예를 들어, 코드 페이지는 읽기와 실행이 가능하지만, 힙 페이지는 읽기와 쓰기가 가능할 것이다. 또 다른 비트로는 주소-공간 식별자 또는 dirty bit 등이 있다. 나중에 더 자세히 이야기하자.
지나가는 글 : TLB Valid Bit =/= Page Table Valid Bit
흔히 혼동하는 실수 중에 하나는 TLB 안에 Valid bit와 페이지 테이블 안에 Valid bit를 혼동하는 것인데요. 페이지 테이블 안에서, PTE가 invalid로 마킹되어 있으면, 이는 해당 페이지가 프로세스에 의해 아직 할당되지 아니함을 의미하지요. 따라서 이는 옳게 동작하는 프로그램이 접근해서는 안 되는 페이지입니다. 이러한 invalid 페이지에 접근하는 행위는 일반적으로 OS에게 trap을 발동시켜 해당 프로세스를 종료시켜 버립니다.
대조적으로 TLB 안에 valid bit는 단순히 그 TLB 엔트리가 유효한 번역인지 아닌지를 알려주는 역할인데요. 예를 들어, 시스템 부팅 시에, TLB 엔트리들은 전부 invalid로 초기화되어 있을 겁니다. 왜냐하면 머신이 지금 새로 켜졌기 때문에 주소 변환들이 아직 캐싱되지 않았기 때문이죠. 일단 가상 메모리가 가능해지면, 그리고 프로그램이 돌기 시작하고 그들의 가상 주소 공간에 접근하기 시작하면, TLB는 서서히 채워지기 시작하고, 곧 valid entry로 가득 찰 겁니다.
TLB 안에 valid bit는 context 스위칭 시에도 꽤 유용한데요. 나중에 다시 이야기하겠지마는, 모든 TLB 엔트리를 invalid로 설정함으로써, 시스템은 실행 준비를 한 프로세스(이제 새로 전환되는 프로세스)가 의도치 않게 이전 프로세스의 가상 주소에서 물리 주소로의 번역을 사용하는 행위를 하지 못하도록 보장할 수 있는 역할을 해줍니다.
TLB의 이슈, Context 스위치 :
TLB의 도입으로 인해, 프로세스 간 스위칭 시에 몇 가지 새로운 이슈가 떠올랐다(그리고 심지어는 주소 공간까지도). 구체적으로 말해서, TLB는 가상 주소에서 물리 주소로 번역하는 정보를 담고 있는데, 중요한 것은 이게 오직 지금 돌고 있는 프로세스에서 유효하다는 소리다. 결과적으로, 한 프로세스에서 다른 프로세스로 스위칭이 발생하면, 하드웨어와 OS는 반드시 신경 써서 이제 교체될 새 프로세스가 의도치 않게 이전에 실행하던 프로세스로부터 사용해왔던 번역 정보를 쓰지 못하도록 보장해야 한다.
상황을 더 자세히 이해하기 위해서, 예를 하나 들어보자. 어떤 프로세스 P1이 지금 돌고 있다. 지금 TLB에는 P1 프로세스를 위한 주소 번역 정보들이 캐싱되어 있다고 해보자. 즉, P1의 페이지 테이블로부터 온 정보가 TLB에 실려 있다.
자, 이전 시간부터 매우 강조했던 사실이 기억나는가? 페이지 테이블이란? 프로세스별 구조체이다!
더 구체적으로, P1의 10번째 가상 페이지는 100번 물리 프레임에 매핑되어 있다. 이때, 또 다른 프로세스 P2가 등장한다. 그리고 OS는 곧장 Context switch를 수행하고 P2를 돌릴 준비를 한다. 근데 P2의 10번째 가상 페이지는 170번 물리 프레임에 매핑되어 있다. 만약에 두 프로세스의 엔트리가 동시에 TLB에 들어 있다면, TLB에는 가상 페이지 10번을 100번으로 번역해야 하는지? 170번으로 번역해야 하는지? 하드웨어는 어느 프로세스에 해당하는 엔트리인지 갈피를 못 잡을 것이다. 따라서 우리는 TLB가 다수의 프로세스를 오가는 상황에서 올바르고 효율적인 가상화를 지원할 수 있도록 몇 가지 추가 작업이 필요하다.
요지 : Context Switching 상황에서 어떻게 TLB 안에 내용을 관리할 것인가?
프로세스 사이에서 Context Switching이 발생하면, 지난 프로세스를 위한 TLB 내 번역 정보는 교체될 프로세스에게는 의미가 없다. 하드웨어와 OS는 이 위기를 어떻게 해결해야만 할까?
사실 몇 가지 해결책이 있다. 첫 번째 해결법은 스위칭 시에 그냥 TLB 내용을 flush 하는 것이다. 그래서 다음 프로세스가 실행되기 이전에 버퍼를 싸악 비워버리는 것이다. OS 기반 시스템에서, 이것은 외부(그리고 권한이 있는) 하드웨어 명령어로 성취될 수 있다. 그에 반해 하드웨어 관리 기반의 TLB의 경우에는 PTBR(Page Table Bage Register)가 교체 시에 flush가 활성화된다.(두 경우 모두 스위칭 시에 OS가 PTBR을 바꾸는 것은 마찬가지다.) 어느 경우든지, flush 명령어는 단순히 모든 valid bit를 0으로 설정해버리며, 본질적으로 TLB의 내용을 깨끗하게 비워내는 셈이다.
매 스위칭마다 TLB를 flush 함으로써, 새로 들어온 프로세스가 의도치 않게 TLB 안에서 틀린 주소 번역을 할 사고는 완전히 막았다고 볼 수 있다. 그런데 문제는 비용이다. 매번 프로세스가 새로 들어와서 데이터와 코드 페이지를 접근하려고 할 때마다 반드시 TLB 미스가 나게 된다. 만약에 OS가 프로세스 간의 스위칭을 자주 하게 되면, 매우 비효율적으로 돌아가게 될 것이다.
이러한 오버헤드를 막기 위해, 일부 시스템은 context switch 간에 TLB의 공유를 가능하게 하는 하드웨어 서포트를 달기도 한다. 특별히, 몇몇 하드웨어 시스템은 TLB 비트 중에 주소 공간 식별자 영역(ASID)을 제공한다. 어쩌면 이것을 프로세스 식별자(PID)의 일종으로 볼 수도 있겠지만, 일반적으로 훨씬 적은 비트를 가지고 있다. 예를 들어 ASID가 8 비트면 PID는 32비트다.
만약에 기타 비트 중에 ASID 영역을 채용해서, 프로세스 1, 프로세스 2를 서로 다른 비트를 부여해서 구분한다면, 쉽게 프로세스 간의 TLB를 공유할 수 있을 것이다. 즉, ASID의 도움으로, TLB는 서로 다른 두 프로세스로부터의 번역 정보를 혼동 없이 들고 있을 수 있게 된 것이다. 물론, 하드웨어는 어느 프로세스가 현재 동작 중인지, 어느 프로세스가 대기 중인지 구분할 줄 알아야 하고, 그러므로 OS는 콘텍스트 스위칭 시에 반드시 현재 프로세스에 해당하는 ASID로 몇 가지 특권 레지스터를 세팅해두고 있어야 한다.
다른 한편, 여러분들은 TLB 안에 매우 비슷하게 생긴 두 엔트리에 대한 또 다른 고찰을 할 수 있을지도 모른다. 아래 그림을 보면, 두 엔트리가 서로 다른 프로세스, 서로 다른 가상 페이지 번호, 그런데 서로 같은 물리 프레임 번호를 가지고 둘 다 유효한 그런 경우를 생각해볼 수 있다.
이런 상황은 예를 들어, 서로 다른 두 프로세스가 어떤 페이지를(예를 들면 코드 페이지라던지,) 공유하고 있을 때 발생할 수 있다. 이 경우 프로세스 1은 101번 물리 페이지를 프로세스 2와 공유하고 있는 것이다. 다만 P1은 이 페이지를 자기의 10번 가상 페이지에, 반면 P2는 50번 가상 페이지에 들고 있다는 차이가 있다. 코드 페이지를 공유한다는 것은 똑같은 내용을 굳이 여러 군데에 쓰고 있지 않다는 의미이므로 메모리 오버헤드를 줄여주는 유용한 장점이라고 할 수 있겠다.
교체 정책 :
굳이 TLB에만 해당하는 건 아니고 여느 캐시에게도 고려되어야 하는 사항이지만, 캐시 교체는 반드시 고려해야 하는 이슈다. 이전에 이미 얘기했지만, 캐시는 크기가 작고, 가능한 메인 메모리까지 다녀오는 횟수를 최소화하고 자주 쓰이는(앞으로 자주 사용될) 소중한 정보를 최대한 들고 있기를 원한다. 구체적으로, 엔트리가 꽉 찬 TLB에 새로운 엔트리를 넣어야 한다. 그럼 어느 것을 교체할 것인가?
요지 : TLB 교체 정책은 어떻게 디자인할 것인가
새 TLB 엔트리가 추가될 때, 어떤 TLB 엔트리를 치우고 자리를 차지해야 할까, 물론 우리의 Goal은 miss rate을 최소화하는 것이다.(즉, hit rate을 최대화하고 싶다.) 그래서 최종적으로 퍼포먼스를 향상하고 싶다.
우리는 페이지를 스토리지로 스왑 할 때 직면하는 문제들에 대해 몇 가지 정책을 자세히 다루어 볼 것이다. 여기, 몇 가지 유명한 정책들이 있다. 흔히 쓰이는 방법은 LRU(가장 오랫동안 참조되지 않은) 엔트리를 evict, 즉 쫓아내는 것이다. LRU는 우리가 그동안 공부한 시간 지역성의 원리를 잘 반영하는 정책이다. 메모리 참조 스트림에서 최근에 쓰이지 않은 엔트리는 쫓아내기 딱 좋은 후보로 볼 수 있다는 게 LRU의 가정이다.
또 다른 일반적으로 많이 쓰이는 정책으로는 랜덤 정책이 있다. 말 그대로 랜덤 하게 쫓아내는 것인데, 얼핏 보면 무지한 정책처럼 보이지만 그 단순함 자체 때문에 유용하고 corner-case 행위를 회피하게 해 준다. 예를 들어, 무척이나 "Reasonable"하게 들리는 LRU 정책이 가끔 매우 비합리적으로 행동할 때가 있다. n 사이즈의 TLB와 n+1 이상의 페이지가 필요한 프로그램 루프를 생각해보자, 이 경우에 LRU는 매번 miss를 낼 것인데, 랜덤 정책이 차라리 나을 수 있다는 뜻이다.
실제 TLB 엔트리 :
MIPS R4000의 TLB 구성을 한번 보자. 요즘 소프트웨어 관리 기반의 TLB를 사용하는 시스템의 경우, 아래 그림과 같이 다소 단순화된 MIPS TLB 엔트리를 사용한다.
MIPS R4000은 4KB 사이즈 페이지에 32-비트 주소 공간을 지원한다. 그러니까 이제 우리는 쉽게 가상 주소를 12-비트의 오프셋(4K = 2^12니까)과 20비트의 VPN으로 구분할 수 있다.(위에서 반복적으로 해봤으니까 이제 쉽게 이해할 수 있죠?) 그런데 이럴 수가, 위의 그림에서 VPN은 0~18, 19비트 밖에 없는 것이다. 사실 유저가 건드릴 수 있는 주소 공간은 전체 주소 공간의 절반이고, 나머지 절반은 커널이 관리하는 것이다. 따라서 19비트만 VPN에 사용된다. 이제 물리 프레임 번호는 34~57의 24비트로 되어 있는데, 그렇기 때문에 해당 구조는 최대 64GB의 물리 메모리까지 지원할 수 있는 셈이다.(왜냐하면 2^24 * 4KB = 64GB기 때문.)
그 외에도 흥미로운 포인트가 몇 군데 있다. 글로벌 비트라 불리는 G를 볼 수 있는데, 이는 프로세스 사이에서 전역적으로 공유되는 페이지를 위해 쓰인다. 따라서 글로벌 비트가 세팅되어 있으면, ASID는 무시된다. 왜냐하면 특정 프로세스가 소유한 구조가 아니라 모두를 위한 페이지기 때문이다. 8비트 크기의 ASID도 볼 수 있다. 이는 OS가 주소 공간 사이에서 총 256개의 프로세스까지 서로 구분할 수 있다는 의미다. 여러분들께 질문을 하나 남기겠다. 만약에 256개의 프로세스 이상을 실행해야만 하는 상황이 오면 그때 OS는 어떻게 해야 할까?
다음, 당신은 3개의 Coherence bit(C)를 볼 수 있을 것이다. 이는 페이지가 하드웨어에 의해 캐시 될지 결정한다는 것 정도만 숙지하자. Dirty bit(D)는 뒤에서 다시 다루겠지만, 해당 페이지에 쓰기가 발생했었는지 마킹해두는 용도다. Valid bit(V)는 위에서도 여러 번 이야기했듯이, 해당 번역이 유효한 지를 하드웨어에게 알려주는 용도다.
여기선 안 보이지만 페이지 마스크 영역도 있다. 이는 다수의 페이지 사이즈를 지원하는 기능이 있다. 곧 더 큰 페이지가 때때로 유용하다는 것을 보일 것이다. 64 비트를 전부 쓰지는 않고, 일부 공간은 남겨둔 모습이다.
MIPS TLB는 종종 32개 또는 64개의 엔트리를 가지는데, 어떤 사이즈를 가질지는 그들이 돌리는 유저 프로세스에 의해 주로 결정되곤 한다. 그런데, 사실 OS를 위해 보존되는 일은 잘 없다. wired 레지스터는 OS에 의해 세팅될 수 있는데, 하드웨어에게 OS를 위해 TLB 슬롯 몇 개를 남겨달라고 요청할 수 있다. 그럼 OS는 이 남겨준 엔트리를 가끔 발생하는, TLB 미스가 나서 문제가 터지는 등의 치명적인 시점에 접근할 수 있도록 어떤 코드와 데이터에 매핑하는데 쓸 수 있다.(대표적인 예로 OS가 출동하는 TLB 미스 핸들러 등이 그러하다.)
MIPS TLB는 소프트웨어 관리 기반이기 때문에, TLB를 업데이트하기 위한 몇 명령어들이 필요하긴 하다. 그래서 MIPS는 다음 4개의 명령어를 제공한다.
TLBP : 특정 번역 정보가 TLB 안에 있는지 알기 위해 뒤져본다.
TLBR : 레지스터가 가리키는 TLB 엔트리의 내용을 읽어온다.
TLBWI : 특정 TLB 엔트리를 교체한다.
TLBWR : 무작위로 TLB 엔트리를 교체한다.
OS는 TLB 내용을 관리하기 위해 이러한 명령어를 사용한다. 물론 이러한 명령어들은 특수 권한을 가지고 있을 때만 쓸 수 있도록 하는 게 매우 중요하다. 만약 유저 프로세스가 TLB의 내용을 맘대로 바꿀 수 있다면 어떻게 될지 상상해보라. 해당 머신을 접수해서, 악의적인 OS를 돌릴 수 있는 것이다. 이런 취약점은 심지어 Sun 사를 사라지게 만들었던 정도의 충격인 것이다.
팁 : RAM은 항상 RAM이 아니다. (컬러의 법칙)
Random-Access Memory라는 단어는 마치, 우리에게 메모리 내에 어느 영역이든지, 임의의 위치를 똑같이 빠르게 찾아갈 수 있을 것 같은 분위기를 풍깁니다. 그렇지만 그보다는 이런 식으로 생각하는 게 좋습니다. 캐시 등 하드웨어와 OS가 가진, 즉 현재 컴퓨터 구조 자체가 가진 본성 때문에, 메모리에서 특정 위치를 접근하는 행위 자체는 모두 비용인데요. 특히 찾아가려는 해당 페이지가 TLB에 없으면 비용이 더욱 커집니다. 어느 정도 나면, 차라리 TLB를 안 쓰느니만 못한 정도죠. 그러니까, 기억해두면 좋은 팁이 하나 있습니다. RAM은 항상 RAM이 아니다. 가끔 주소 공간으로 무작위적으로 접근하는 행위는, 특히 TLB가 커버칠 수 있는 범위 이상의 페이지 수를 가진 상황에서 심각한 퍼포먼스 페널티를 줄 수 있겠습니다. 우리의 조언자 중 한 분인 데이비드 컬러 박사님께서는 TLB를 많은 골칫거리의 원인으로 지목하곤 하셨는데요. 그의 이름을 기려서 흔히 컬러의 법칙이라고 합니다.
요약 :
지금까지 우리는 어떻게 하드웨어의 도움으로 주소변환을 빠르게 할 수 있는지 살펴보았다. 작은 특수목적의 온칩 주소-변환 캐시인 TLB를 제공함으로써 수많은 메모리 참조들은 메인 메모리 안에 있는 페이지 테이블까지 다녀오지 않고 처리될 수 있겠다는 희망을 갖게 되었다. 그러므로 많은 상황에서 프로그램의 퍼포먼스는 마치 거의 메모리 가상화가 되지 않은 것처럼 빠르게 처리될 수 있을 것이다.(가상 메모리에서 물리 메모리로 번역하는 오버헤드가 거의 느끼지 못할 수준으로 빠르다는 뜻.) 확실히 현대 컴퓨팅 시스템에서 페이징을 사용하게 된 것에 있어서 본질적인 역할을 해주었다.
그러나, TLB는 세상에 모든 프로그램들에게 꼭 이런 장밋빛 미래를 보여주는 것은 아니다. 특히 아주 짧은 시간 내에 프로그램이 접근하는 페이지의 개수가 TLB가 처리할 수 있는 페이지의 개수를 초과해버리면, 프로그램은 TLB 미스를 잔뜩 발생시킬 것이다. 결국 시스템은 TLB를 안 쓰느니만 못하게 느려질지도 모르는 것이다. 우리는 이미 먼저 TLB가 커버칠 수 있는 양을 초과해서 프로그램에서 발생하는 문제와 현상들을 언급한 적이 있다.
해결책 중에 하나로는, 다음 챕터에서 공부해볼 것인데, 더 큰 페이지 사이즈를 지원하는 것이다. 더 큰 페이지 사이즈 주소 공간에 중요한 데이터 구조체를 매핑함으로써, 효율적으로 TLB가 커버칠 수 있는 영역을 늘릴 수 있다. 더 큰 페이지 사이즈를 지원하는 것은 데이터베이스 관리 시스템(DBMS) 등에 의해 구현될 수 있는데, 이 녀석은 크고 임의 접근 가능한 특정 데이터 구조체를 가지고 있다.
또 다른 TLB 이슈에 대해 해 줄 중요한 이야기가 하나 있는데, TLB 접근이 CPU 파이프라인에서 보틀넥이 될 수 있다는 것이다. 특히 소위 phsically-indexed cache라고 불리는 녀석들인 경우에 그러하다. 이런 캐시들은 주소 변환이 캐시 접근 이전에 이루어져야만 하는데, 이는 수행을 더 느리게 만들 수 있다. 이런 잠재적 문제 때문에, 사람들은 가상 주소로 캐시를 접근하는 현명한 방법의 일종들을 뒤져보기 시작했다. 이를 통해 캐시 히트 났을 때 번역의 복잡한 스텝들을 피할 수 있게 된 셈이다. 이러한 virtually-indexed cache는 몇몇 퍼포먼스 문제들을 해결하게 되었지만, 새로운 하드웨어 디자인 이슈들을 발생시켰다. 다음 챕터에서 자세히 공부해보자.
출처 : REMZI H. ARPACI-DUSSEAU, ANDREA C. ARPACI-DUSSEAU, UNIVERSITY OF WISCONSIN–MADISON, "OPERATING SYSTEMS THREE EASY PIECES", Arpaci-Dusseau Books.
'OS' 카테고리의 다른 글
| [운영체제] 20. Paging: Smaller Tables (0) | 2022.01.25 |
|---|---|
| [운영체제] 18. Paging이란 (1) | 2022.01.21 |