20. 페이징, 더 작은 페이지 테이블을 위하여 :
이번 시간엔 페이징의 도입으로 발생한 두 번째 문제를 고찰해볼 것이다. 페이지 테이블이 너무 크고, 메모리를 너무 많이 잡아먹는다는 것이다. 이번에도 linear page table을 생각해보자. 이전 시간에 말했지만 이 구조는 꽤 크다. 다시 한번 32비트 주소 공간과, 4KB 사이즈의 페이지(따라서 오프셋이 12비트 필요하다.)와 4-byte PTE에 대해 생각해보자. 그러므로 이 구조에서 대략 백만 개의 가상 페이지까지 가질 수 있다.(VPN이 20비트니까) 따라서 페이지 테이블이 4MB의 용량을 갖는다. 다시 한번 상기시켜 주자면, 페이지 테이블은 프로세스별 구조체다! 프로세스가 100개가 활성화되어 있다고 했을 때(사실 현대 시스템에서 그렇게 흔한 경우는 아니긴 하다.), 고작 페이지 테이블을 위해서 수백 메가바이트의 메모리를 할당해줘야 한다. 결과적으로, 우리는 이 무거운 짐을 줄일 수 있는 몇 가지 테크닉을 공부해 볼 것이다. 먼저 우리의 요지를 읽고 공부하러 떠나 보자.
요지 : 어떻게 페이지 테이블을 더 작게 만들까?
단순 배열-기반의 페이지 테이블(흔히 linear page table이라 불림)은 일반적인 컴퓨팅 머신의 메모리 크기와 비교해 보았을 때 너무 크다. 어떻게 페이지 테이블을 더 작게 만들까? 중요한 아이디어는 무엇인가? 새 데이터 구조를 적용한 결과 어떤 비효율성이 새로 발생하는지?
쉬운 해법 : 더 큰 페이지
페이지 테이블 사이즈를 줄일 수 있는 간단한 방법이 하나 있다. 더 큰 페이지를 사용하는 것이다. 우리 32비트 주소 공간을 다시 보자 그런데 이번엔 페이지 사이즈가 4배로 커져서 16KB다. 이제 우리는 오프셋에 14비트를 써야 한다. 그럼 자연스럽게 가상 페이지 번호는 18비트가 할당된다. 그러면 아까와 비교해서 가질 수 있는 가상 페이지가 1/4 토막이 났다. 그렇다면 단순 linear 페이지 테이블 기준 사이즈가 1MB가 되었다.(뭐 엄청 놀랄 일은 아니다. 페이지 개수가 1/4배가 된 것만큼 페이지 당 크기는 4배가 된 것뿐이다.)
그런데 이런 접근법의 가장 주된 문제는, 페이지가 커지면 그 페이지 내부의 낭비가 커진다는 것이다! 할당 유닛의 내부가 낭비된다는 이 개념은 "내부 단편화(internal fragmentation)"라고 불린다. 그러므로 이 경우 애플리케이션은 페이지를 할당받지만 그 조각의 극히 일부만 쓰고 나머지는 버리고 말 것이다. 이런 식이면 메모리는 이 "과하게 큰 페이지들"로 금방 꽉 차 버리고 만다. 그렇기에 대부분의 시스템은 범용보다 상대적으로 작은 크기의 페이지를 쓰게 되는 것이다.(x86은 4KB, SPARCv9은 8KB) 우리의 문제는 그리 쉽게 해결되진 않을 것이다. 슬프도다!
지나가는 글: 다수의 페이지 사이즈
한편으로는, MIPS, SPARC, x86-64 등 많은 아키텍처는 이제 다수의 페이지 사이즈를 지원하게 되었습니다. 종종 4KB나 8KB짜리 작은 페이지가 사용되었죠. 근데, 만약 어떤 "스마트한" 애플리케이션의 요청이 들어오면, 거대한 단일 페이지(예를 들면 4MB짜리)가 주소 공간의 특정 위치에 사용될 수 있습니다. 이러한 애플리케이션은 특정 공간 속에 자주 쓰이는 데이터 구조체가 TLB 상에서는 딱 하나의 엔트리만 차지할 수 있도록 하게 해 줍니다.
이러한 "큰 페이지" 용법은 데이터베이스 관리 시스템과 고성능 상용 애플리케이션에서 흔히 쓰이죠. 그런데 이렇게 페이지 사이즈를 여러 개 두는 이유는 꼭 페이지 테이블 공간을 줄이기 위해서만은 아니에요. TLB 미스가 많이 나는 대참사가 나지 않도록 더 큰 주소 공간을 프로그램이 접근할 수 있게 해 주니까, TLB의 부담을 줄여주는 효과도 있습니다.
그렇지만, 이렇게 다수의 페이지 사이즈를 사용하는 방식은 OS 내 가상 페이지 관리자를 확실히 복잡하게 만들기 때문에, 더 큰 페이지는 대부분 단순히 큰 페이지를 직접 요청하기 위한 애플리케이션에게 새 인터페이스를 선언하는 상황 정도에서만 쓰인다고 보시면 될 것 같습니다.
하이브리드 접근법 : 페이징과 세그먼트
여러분들은 살면서 언젠가 두 가지 합리적이지만 서로 다른 접근 방법이 있을 때, 그 두 개의 혼합이 혹시 최고의 결과를 내지는 않는가 시도해본 적이 있지 않은가? 우리는 이런 혼합의 결과물을 하이브리드라고 부른다. 예를 들어서, 초콜릿 따로 땅콩버터 따로 먹을게 아니라, 리스 피넛버터컵이라고 알려진 이 훌륭한 하이브리드를 한번 먹어보는 것은 어떨까.
오래전에, 멀틱스라는 운영체제의 창시자들(특히 잭 데니스 박사님)은 위와 같은 아이디어로 멀틱스 가상 메모리 시스템의 구조를 바꿔버렸다. 구체적으로, 데니스 박사님은 페이지 테이블의 메모리 오버헤드를 줄이기 위해 페이징과 세그멘테이션을 혼합에 대한 아이디어를 냈다. 우리는 전형적인 선형 페이지 테이블을 가지고 자세히 실험해봄으로써 이런 아이디어가 실제로 동작할 수 있는지 알아볼 것이다. 주소 공간 하나를 가정하자. 그리고 그 안에, 사용된 힙과 스택의 영역이 매우 적다고 해보자. 예를 들어, 매우 귀여운 16KB짜리 가상 주소 공간과 1KB 크기의 페이지 구조를 생각해보자.
위의 그림에서 볼 수 있듯이, VPN 0는 코드 페이지로 할당했고 물리 프레임 10번에 매핑했다. 힙 페이지는 VPN 4에 할당되어 컴파일 시에 아래로 쌓이게 되고, 물리 프레임 23번에 매핑했다. 스택 페이지는 VPN 14, 15에 할당되어 런타임 때 위로 쌓일 것이다. 이는 각각 물리 프레임 28, 4번에 매핑했다. 아래 선형 페이지 테이블을 보면 알 수 있듯이, 대부분의 엔트리가 안 쓰인다.
즉, invalid 엔트리로 가득 차 있다. 매우 비효율적이라는 생각이 들지 않는가? 이렇게 일부러 작은 페이지 테이블을 상정해서 봤는데도 75%의 엔트리가 놀고 있는데, 실제 32비트 주소 공간을 위한 페이지 테이블은 얼마나 비효율적이겠는가. 여러분들이 굳이 그 효율성을 직접 계산해보지 않아도, 충분히 끔찍하다는 것은 인정할 것이다.
그러므로, 여기 하이브리드 접근법을 제시한다. 프로세스를 위해 전체 주소 공간을 다 고려한 하나의 페이지 테이블을 가지는 대신에, 논리적 세그먼트당 하나씩 테이블을 들고 있는 구조를 써보는 건 어떤지? 그러니까 위 예제에서는 가상 주소 공간 상에서 코드, 힙, 스택을 위한 페이지 테이블을 따로 들고 있자는 소리다.
세그먼트를 조금 복습해보자면, 각 세그먼트가 물리 메모리 내에 어디에 있는지 알려주는 base 레지스터, 그리고 bound 또는 limit 레지스터라 불리는 녀석이 세그먼트의 사이즈를 알려준다. 우리의 하이브리드 해결법엔, 지금 말한 구조들을 메모리 관리 유닛이 들고 있다. 대신 우리가 가진 base 레지스터와 원래 이 녀석의 차이점이란 해당 세그먼트(지금 여기서는 코드, 힙, 스택을 말함)의 페이지 테이블의 물리 주소를 들고 있다는 점이라 할 수 있겠다. bound 레지스터는 페이지 테이블의 끝을 지시하는 데 사용된다.(즉, 유효한 페이지가 얼마나 많은지를 알려준다.)
예를 하나 들어보자, 32비트 주소 공간과 4KB 사이즈 페이지를 생각해보자. 그리고 주소 공간을 4개의 세그먼트로 잘라내자. 이 중 코드, 힙, 스택을 위해 3개를 사용할 것이다. 그리고 아래 그림처럼 주소 공간의 상위 2개 비트를 세그먼트를 구분하는데 쓸 것이다. 세그먼트 00은 놔두고, 01은 코드, 10은 힙, 11은 스택을 가리킨다고 약속하자.
그러니까 하드웨어는 코드, 힙, 스택을 위해 세 개의 베이스/바운드 쌍이 필요한 것이다. 프로세스가 실행 중일 때, 이 세 세그먼트들의 베이스 레지스터는 해당 세그먼트의 선형 페이지 테이블의 물리 주소를 들고 있을 것이다. 그러니까 이제부터는 시스템에서 돌고 있는 각 프로세스들은 페이지 테이블을 세 개씩 갖고 있다고 볼 수 있는 것이다. 콘텍스트 스위치가 발생하면, 이 레지스터들은 반드시 새로 들어올 프로세스에 해당하는 페이지 테이블들의 위치를 반영하기 위해 내용을 교체해야 하는 것이다.
하드웨어 관리 기반 TLB에서 TLB 미스가 났다고 하자. 즉, 여기서는 TLB 미스를 핸들링하는데 하드웨어의 책임이 지배적인 것이다. 하드웨어는 세그먼트 비트(SN)를 보고 어느 베이스/바운드 레지스터 쌍을 사용할지 결정한다. 그런 다음 하드웨어는 선택한 레지스터 안에 있는 물리 주소를 들고 그 PTE의 주소를 만들기 위해 VPN과 합친다.
SN = (VirtualAddress & SEG_MASK) >> SN_SHIFT
VPN = (VirtualAddress & VPN_MASK) >> VPN_SHIFT
AddressOfPTE = Base [SN] + (VPN * sizeof(PTE))
이 과정은 어쩐지 친숙해 보인다. 이것은 사실 이전에 선형 페이지 테이블을 만들었을 때랑 거의 유사하다. 유일한 차이점은 세 개의 세그먼트 베이스 레지스터 중에 하나를 선택한다는 점이다. 이런 하이브리드 기법의 가장 핵심적인 차이점은 세그먼트당 바운드 레지스터가 존재한다는 것, 그리고 각 바운드 레지스터가 각 세그먼트 안에 최대 유효 페이지의 값을 들고 있다는 점이다.
예를 들어, 코드 세그먼트가 가상 메모리의 첫 세 페이지를 차지하는 경우라면(즉, VPN 0, 1, 2를 쓰는 경우), 코드 세그먼트의 페이지 테이블은 오직 엔트리 3개만 할당해주고 바운드 레지스터를 3으로 설정해주면 끝이다. 만약 세그먼트의 끝부분을 넘어서 메모리 접근을 시도하면 예외처리를 발생시켜 여느 때와 같이 OS가 출동해서 해당 프로세스를 종료시켜 버릴 것이다. 이런 관점에서 봤을 때, 우리의 하이브리드 접근법은 선형 페이지 테이블에 비해서 엄청난 메모리 절약을 할 수 있음을 보여준다.
스택과 힙 사이에 할당되지 않은 페이지들은 더 이상 페이지 테이블 내에서 자리를 차지하지 않는다.(그러면서도 선형 페이지 테이블에서 invalid 처리를 해버린 것과 똑같은 효과를 낸다.) 그런데, 이쯤에서 여러분도 살짝 눈치챘겠지만, 이 방법이 마냥 좋기만 한 것은 아니다.
첫째, 이는 여전히 우리에게 세그멘테이션 사용을 요구한다. 이전에 이미 얘기 한 바 있지만, 세그멘테이션은 우리 생각만큼 유연한 녀석이 아니다. 이 녀석은 주소 공간에서 특정 사용 패턴을 가정하고 약속한 채로 사용되고 있는 것이다. 만약에 우리가 엄청 크지만 sparse 하게 사용되는 힙을 들고 있다면, 여전히 우리는 대부분의 페이지 테이블을 낭비하게 될 것이다.
둘째, 이러한 하이브리드는 또다시 외부 단편화 문제를 끌고 오게 된다. 대부분의 메모리가 페이지 사이즈에 맞춰 관리되는 반면, 페이지 테이블은 다수의 PTE로 인해 자의적인 사이즈를 갖게 된다. 그렇기에 메모리 안에서 빈 공간을 찾아다니기가 점점 더 복잡해질 것이다. 이런 이유 때문에 사람들은 더 작은 페이지 테이블을 구현하기 위한 더 좋은 방법을 계속해서 강구하게 되었다.
멀티 레벨 페이지 테이블 :
또 다른 접근법은 이제 세그멘테이션에 의존하지 말고 문제 해결을 시도하려고 했다. 어떻게 하면 페이지 테이블에 유효하지 않은 영역을 메모리에 두지 않고 제거해버릴 수 있을까? 멀티-레벨 페이지 테이블은 이러한 접근법 중 하나인데, 선형 페이지 테이블을 일종의 트리 구조로 바꾸는 것이다. 이 접근법은 매우 효율적이기 때문에 x86을 포함해서 많은 현대 시스템에도 채용하고 있다. 이제 이 방법에 대해 자세히 알아보자.
멀티 레벨 페이지 테이블의 기저에 깔린 기본 아이디어는 간단하다. 먼저, 페이지 테이블을 페이지 사이즈로 잘라낸다. 그런 다음, 잘라낸 조각의 PTE들이 전부 invalid 하면, 해당 페이지 테이블의 페이지는 할당하지 않는다. 어떤 페이지 테이블의 페이지 조각이 유효한지(만약 유효하다면, 메모리에 어디에 있는지), 추적하기 위해서는 페이지 디렉터리라고 불리는 새로운 구조체가 필요하다. 그러므로 페이지 디렉터리는 여러분들에게 어떤 페이지 테이블의 페이지가 어디에 있는지 알려줄 수도, 그렇지 않으면 해당 페이지 테이블 조각이 전체가 유효하지 않다고 알려줄 수 있을 것이다.
아래 그림은 각각 선형 페이지 테이블(대부분의, 특히 중간 영역이 유효하지 않은 공간으로 처리되어 있다.)과 멀티 레벨 페이지 테이블의 한 예이다.
페이지 디렉터리는 처음과 마지막 페이지 테이블 조각이 유효하다고 알려주고 있다. 그러므로 두 페이지 테이블만 메모리에 올라가 있는 셈이다. 이제 당신은 멀티 레벨 테이블이 무엇을 하는지 좀 더 분명히 보일 것이다. 이 녀석은 선형 페이지 테이블의 일부분을 사라지게 만들었다.(사라진 만큼의 물리 프레임은 다른 용도로 쓰일 수 있을 것이다.) 그리고 페이지 디렉터리에 할당된 페이지 테이블의 페이지를 추적하는 기능이 있는 것이다.
페이지 테이블은 여기서 간단히 2-레벨로 되어 있으며, 페이지 테이블의 페이지 사이즈만큼의 조각당 하나의 엔트리가 담당하고 있다. 이 녀석은 페이지 디렉터리 엔트리(PDE)를 많이 가지고 있다. PDE는 PTE와 유사하게도, valid bit와 페이지 프레임 번호(PFN)를 가지고 있다.
그러나, 위에서 힌트를 살짝 줬지만, PDE의 valid bit의 의미는 PTE의 그것과는 살짝 다르다고 할 수 있겠다. 즉, PDE가 유효하다는 것의 의미는, 해당 페이지 테이블 조각이 들고 있는 PTE 중에서 적어도 하나의 엔트리는 valid 하다는 뜻이다. 그러니까 하나라도 유효한 PTE를 가진 페이지 테이블의 조각을 가리키는 PDE는 valid bit가 1로 설정된다(어쩐지 논리합과 닮은 점이 있는 듯하다.). 만약 PDE가 유효하지 않다면, 해당 PDE의 내용은 정의되지 않는다. 멀티 레벨 페이지 테이블은 앞서 본 전략들 중에서도 몇 가지 명백한 장점이 보이는 것 같다.
첫째로, 매우 명백하게도 멀티 레벨 테이블은 당신이 쓰고 있는 주소 공간의 양에 비례해서 페이지 테이블 공간만을 할당해 준다. 그러므로 일반적으로 콤팩트하고 희소한 주소 공간을 잘 지원한다고 말할 수 있겠다.
둘째, 섬세하게 잘만 짠다면, 페이지 테이블의 각 조각들은 페이지 사이즈에 딱 맞춰 이쁘고 깔끔하게 잘릴 것이고, 메모리 관리를 쉽게 만들어 줄 것이다. OS는 필요할 때마다 쉽게 다음 빈 페이지를 집을 수도 있고 페이지 테이블을 확장할 수도 있을 것이다. 단순 선형 페이지 테이블은 VPN에 의해 인덱싱 되는 PTE의 배열일 뿐이며, 전체 테이블이 반드시 지속적으로 물리 메모리에 상주해야 한다는 점에서 대조적이다. 앞서 가정했듯이 32비트 주소 공간에 4KB 사이즈의 페이지 구조의 경우 전체 페이지 테이블이 4MB에 이르는데, 심지어 대부분의 공간은 유효하지 않고 사용되지도 않은 연속적인 엔트리들이 잔뜩 물리 메모리에 상주하고 있는, 이 거대한 덩어리를 사용한다는 것은 말만 들어도 힘들어 보인다.
멀티 레벨 구조에서는, 페이지 디렉터리라는 개념을 채용해서 간접 레벨을 추가했다. 이 디렉터리는 페이지 테이블의 일부 조각을 가리키고, 이러한 간접성은 우리가 페이지 테이블 중 필요한 조각만큼 물리 메모리 내 우리가 원하는 곳에 배치할 수 있게 해 준 것이다.
멀티 레벨 테이블에 비용이 있다는 것을 반드시 생각해야 한다. TLB 미스가 나면, 페이지 테이블로부터 올바른 정보 번역을 하기 위해 메모리로부터 2번의 load가 요구될 것이다.(한 번은 페이지 디렉터리를 위해, 또 다른 한 번은 PTE 자체를 위해.) 선형 페이지 테이블이 단 한 번의 load를 필요로 했던 것에 비하면 손해를 보는 것이다. 그러므로 멀티 레벨 페이지는 time-space trade-off(시공간 절충)의 한 예시가 될 수 있겠다.
우리는 더 작은 테이블을 원했는데(그래서 이루어졌다.), 그러나 공짜가 아니었다. 비록 TLB 히트가 난 상황에서 퍼포먼스는 명백히 동일할 것인데, 이 자그마한 테이블에겐 TLB 미스가 훨씬 더 큰 고통으로 다가올 것이다. 또 다른 명백한 단점으로는 complexity가 있겠다. TLB를 하드웨어가 주로 관리하든 아니면 OS가 관리하든, 멀티 레벨 구조는 의심할 여지없이 단순 선형 구조에 비해서 더 많은 관여가 필요해 보인다. 우리 연구자들은 종종 성능 향상 또는 오버헤드 감축을 위해 복잡성을 증대시키곤 한다. 이번 멀티 레벨 테이블 사례에서는 우리는 소중한 메모리를 절약하기 위해, 페이지 테이블을 뒤지는 동작을 더 어렵게 만든 셈이다.
팁: Complexity를 조심하세요.
시스템 디자이너는 반드시 시스템에 복잡성을 추가하는 것에 주의를 기울여야 합니다. 자고로 훌륭한 시스템 빌더란 의도한 업무 처리를 수행, 성취할 수 있으면서 최소한으로 복잡한 시스템을 구현하는 사람이죠. 예를 들어, 하드 디스크 공간이 충분히 넉넉하고 풍부한 상황에서 가능한 적은 바이트를 쓰기 위해 파일 시스템 동작을 어렵게 디자인해서는 안됩니다. 이와 비슷하게, 프로세서가 충분히 빠르고 훌륭하다면, 아마도 어떤 작업을 처리하기 위해 직접 어셈블리 어로 손 코딩을 하기보다는(어셈블리 어는 고급 어보다 훨씬 머신에 최적화된 언어지만, 다른 많은 프로그래머들에게 더 복잡하게 받아들여질 수 있기 때문에,) OS 내에서 깔끔하고 모두가 이해하기 쉬운 모듈로 코드로 작성하는 것이 더 좋을 겁니다.
그러니까 불필요한 복잡성을 조심하세요, 어설픈 최적화는 시스템을 이해하고, 유지하고, 디버깅하기 어렵게 만듭니다. 소설가 앙투안 드 생텍쥐페리는 이런 유명한 글을 남겼죠. "단언컨대, 완벽은 더 이상 뭔가 더할 게 없을 때 얻어지는 것이 아니고, 더 이상 뭔가 뺄 게 없을 때 얻어집니다." 그가 한 말은 아니지만 또 이런 명언도 있죠. "완벽한 것에 대해 말하는 것은 실제 달성하기보다 훨씬 쉽습니다."
멀티 레벨의 상세한 예시 :
예를 하나 들어보자. 64-바이트 페이지 사이즈와 그것들을 담고 있는 16KB 크기의 작은 주소 공간을 생각해보자. 그럼 페이지 번호를 위해 8비트(16KB/64byte = 2^8기 때문), 페이지 오프셋을 위해 6비트(2^6 byte기 때문)가 필요할 것이다. 그러므로, 여기서는 14비트의 주소 공간이 필요한 것이다. 앞서 계속 강조해왔듯이 단순 선형 페이지 테이블 방식을 쓴다면 256개의 엔트리가 필요할 것이고, 아주 적은 부분만이 쓰일 것이다.
그림에서 볼 수 있듯, 가상 페이지 0, 1에는 코드가, 가상 페이지 4, 5에는 힙, 가상 페이지 254, 255에는 스택이 있다. 나머지 250개 엔트리는 안 쓰인다. 여기서 2-레벨 페이지를 구현하려면, 먼저 이 페이지 테이블들을 페이지 사이즈만큼 잘라내야 한다. 각 PTE는 4byte라고 하자. 그럼 페이지 사이즈가 64byte니까 16개의 PTE씩 자르면 될 것이다. 따라서 총 256개의 페이지 테이블을 16개로 조각낸다고 볼 수 있다.
그럼 이제 기존의 가상 페이지 번호를 어떻게 활용해서 페이지 디렉터리에 인덱싱 하고, 그 16개의 페이지 테이블 조각들을 어떻게 디렉터리에 집어넣을지 생각할 필요가 있다. 페이지 테이블은 엔트리의 배열임을 생각해보면, 가상 페이지 번호를 활용하면 될 것 같다. 위에서도 말했지만 페이지 디렉터리의 엔트리엔 페이지 사이즈만큼의 페이지 테이블 조각들이 들어간다. 16개의 PDE가 있을 것이므로, VPN의 상위 4개 비트를 쓰면 좋을 것이다.
페이지 디렉터리 인덱스를 VPN으로부터 추출하면, 이를 이용하면 쉽게 아래 식처럼 PDE의 주소를 계산할 수 있다.
PDEAddr = PageDirBase + (PDIndex * sizeof(PDE))
이후에 번역 과정도 쉽게 구현할 수 있을 것이다. 만약 유효하지 않은 페이지 디렉터리 엔트리로 접근을 시도하면, 예외처리를 발생시킬 것이다.(이는 마치 유효하지 않은 페이지를 접근하는 행위와 같은 것이다.) 그런데 PDE가 유효하다면, 몇 가지 일을 더 해야 할 것이다. 구체적으로 설명하자면, 해당 PDE가 가리키는 페이지 테이블의 페이지 조각으로 가서 우리가 찾고 싶은 PTE를 fetch 해오는 것이다. PTE를 잘 찾아왔다면, VPN에 남아 있는 비트를 사용해서 페이지 테이블의 위치로 인덱싱해야 한다.
이 페이지 테이블 인덱스는 말 그대로 해당 페이지 테이블 조각의 원하는 엔트리로 찾아갈 수 있도록 해준다. 아래 식처럼 쉽게 계산할 수 있다.
PTEAddr = (PDE.PFN << SHIFT) + (PTIndex * sizeof(PTE))
페이지 디렉터리 엔트리로부터 얻은 물레 프레임 번호는 반드시 PTE의 주소를 형성하기 위해서 페이지 테이블 인덱스와 결합하기 전에 left-shift 되어야 함을 기억해야 한다.
이런 과정들을 모두 이해하려면, 이제 우리는 멀티 레벨 페이지 테이블에 어떤 값들을 채워나가고, 가상 페이지를 번역할 것이다. 이번 예제에서는 페이지 디렉터리부터 시작해보자. 아래 그림에서, PDE가 주소 공간에서 어떤 페이지 테이블의 페이지 조각을 설명하고 있음을 볼 수 있다.
물리 페이지 100번(페이지 테이블의 0번 페이지에 해당하는 물리 프레임이다.)에서 우리는 주소 공간의 첫 16개의 가상 페이지들을 위한 16개의 PTE가 적혀 있는 페이지 테이블의 첫 조각을 들고 있다. 그리고 중간 그림에 있는 페이지 테이블의 내용을 보라. 여기 페이지 테이블의 페이지 조각에는 가상 페이지 중 첫 16개에 해당하는 묶음의 매핑 정보를 담고 있다.
우리 예제에서, 가상 페이지 0번, 1번은 유효한 코드 세그먼트가 들어있고, 4번, 5번도 유효한 힙 세그먼트가 들어있다. 그러므로, 해당 테이블은 각 페이지 조각들의 매핑 정보를 담고 있는 것이다. 나머지 엔트리들은 invalid로 마킹되어 있다. 또 다른 유효한 페이지 테이블의 페이지 조각은 물리 프레임 101번에서 찾을 수 있다. 여기 페이지엔 주소 공간의 마지막 16개의 가상 페이지들의 매핑 정보가 들어 있다.
이 예제에서, 가상 페이지 254, 255번(스택 영역)은 유효한 매핑을 가지고 있다. 이 예제는 멀티 레벨 인덱스 구조가 얼마나 많은 공간을 아낄 수 있는지를 희망적으로 보여준다. 여기서는 선형 페이지 테이블 전체에 해당하는 크기인 16 페이지를 전부 다 할당하는 대신에, 단 3개의 페이지만을 할당했다.(하나는 페이지 디렉터리, 두 개는 유효한 매핑을 담고 있는 페이지 테이블 조각) 이런 식이라면 32비트 또는 64비트 주소 공간은 훨씬 더 많이 공간을 아낄 수 있음은 매우 명백하다.
마지막으로, 번역을 수행하기 위한 정보에 대해 써보자. 254번 가상 페이지의 0번째 바이트를 지시하는 주소는 11 1111 1000 0000(총 14비트)이다. 이때 최상위 4개 비트는 페이지 디렉터리가 인덱스를 위해 쓸 것이라고 이미 말한 바 있다. 그러므로, 1111이 선택되고, 이는 페이지 디렉터리의 가장 마지막 엔트리를 선택함을 의미한다. 이는 우리에게 페이지 테이블의 유효한 페이지 조각이 101번 물리 주소에 매핑됨을 의미한다. 그리고 그다음 VPN에서 4개 비트(1110)는 페이지 테이블의 페이지 조각을 인덱스 하고, 바람직한 PTE를 찾는데 쓸 것이다.
따라서 해당 페이지 테이블의 마지막 조각으로 가서 마지막에서 두 번째(14번 엔트리) 위치로 가서 원하는 페이지 테이블을 조회하고, 이를 통해 254번 페이지 테이블 엔트리가 물리 페이지 55번에 있음을 찾아낼 것이다. 물리 프레임 번호 55번과 기존에 가지고 있던 가상 주소의 오프셋(뒷자리 6개) 00 0000을 합치면 우리는 드디어 가고 싶었던 물리 주소를 얻을 수 있는 것이다.
PhysAddr = (PTE.PFN << SHIFT) + offset = 00 1101 1100 0000
이제 당신은 페이지 테이블의 페이지 조각이 어디 있는지 알려주는 페이지 디렉터리의 도움을 받아, 2-레벨 페이지 테이블을 어떻게 구성하는지 조금 알았을 것이다. 그러나 유감스럽게도, 우리의 할 일은 아직 끝나지 않았다. 이제 우리는 때때로, 2-레벨의 페이지 테이블로는 아직 충분하지 않음에 대해 이야기를 나눠볼 것이다.
2-레벨 전략, 그 너머 :
우리가 지금까지 알아본 예제에서는, 딱 2-레벨의 페이지 테이블 구조만을 가정해왔다. 즉, 페이지 디렉터리와 페이지 테이블의 페이지 사이즈만큼의 조각들로. 근데 어떤 때에는 더 깊은 트리 구조가 가능하기도 하다.(그리고 실제로, 그래야만 한다.)
왜 더 깊은 멀티 레벨 테이블 구조가 유용한 지 예를 하나 들어보자. 이번에는 30비트짜리 가상 주소 공간을 가정하자. 그리고 페이지 사이즈는 512바이트로 작게 잡자. 이제 수도 없이 많이 했으니 바로 감이 오는가? 21비트는 가상 페이지 번호를 주고 나머지 9비트는 페이지 오프셋이 된다. 기억하는가? 우리 목표는 페이지 테이블을 단일 페이지 사이즈 크기에 맞춰서 잘라내어 멀티 레벨 페이지 테이블을 구축하는 것이다. 근데 우리는 오직 큰 페이지 테이블만을 걱정해왔는데, 페이지 디렉터리가 매우 커지면 어떡하지라는 고민은 왜 못하겠는가?
페이지 테이블을 조각내기 위해 얼마나 많은 레벨의 멀티 레벨 테이블을 구축할지 결정하기 위해서는, 먼저 한 페이지에 얼마나 많은 PTE가 들어가는지부터 세보는 것에서 시작하는 것이다. 페이지 사이즈가 512바이트, PTE를 4바이트로 가정하자. 그럼 단일 페이지 안에 PTE가 128개가 들어간다. 그러면 VPN 중 오른쪽 7비트를 페이지 테이블의 페이지 조각을 인덱싱 하는데 할당하기로 결정할 수 있을 것이다. 아래처럼 말이다.
자, 이제 페이지 디렉터리는 몇 비트를 가져갈까? 정답, 21-7=14비트다. 이렇게 되면 페이지 디렉터리는 16K 개의 엔트리를 갖게 되고 이는 당연히도 한 페이지 안에 안 들어간다. PDE도 4바이트라고 가정하면 디렉터리를 위해 128페이지가 필요하다. 이런 식이면 애초에 멀티 레벨을 하려고 했던 이유(페이지 테이블들의 조각들을 따로 한 번에 이쁘게 모아보기.)가 무의미해진다.
이런 말썽을 해결하기 위해, 우리는 트리 레벨을 더 구축하기로 했다. 이번엔 페이지 디렉터리를 잘라내는 것이다. 그리고 더 상위의 디렉터리를 추가해서 하위 디렉터리의 페이지 조각들을 가리키게 만드는 것이다. 이제, 상위 페이지 디렉터리를 인덱싱할 때, 우리는 아래 그림과 같이 가상 주소의 최상위 비트(PD Index 0)를 쓰게 된다.
이 인덱스 값은 최상위 페이지 디렉터리로부터 하위 페이지 디렉터리 엔트리를 fetch 하는데 쓰인다. 만약 유효한 접근이었다면, 하위 페이지 디렉터리는 상위 레벨 PDE와 VPN의 일부(PD Index 1)로부터 물리 프레임 번호를 결합해올 수 있다. 마지막으로, 유효한 접근임을 확인한 뒤에, 하위 PDE로부터 주소를 결합하여 페이지 테이블 인덱스를 사용해서 PTE 주소를 만들 수 있다. 후, 설명이 다소 길었다. 이제 멀티 레벨 테이블을 거시적으로 살펴볼 수 있을 것이다.
변환 프로세스, TLB도 기억하자! :
2-레벨 페이지 테이블을 사용한 주소 변환 프로세스 전체를 요약하기 위해, 우리는 다시 알고리즘적 control flow를 볼 필요가 있다. 아래 코드는 하드웨어 관리 기반의 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 // first, get page directory entry
12 PDIndex = (VPN & PD_MASK) >> PD_SHIFT
13 PDEAddr = PDBR + (PDIndex * sizeof(PDE))
14 PDE = AccessMemory(PDEAddr)
15 if (PDE.Valid == False)
16 RaiseException(SEGMENTATION_FAULT)
17 else
18 // PDE is valid: now fetch PTE from page table
19 PTIndex = (VPN & PT_MASK) >> PT_SHIFT
20 PTEAddr = (PDE.PFN << SHIFT) + (PTIndex * sizeof(PTE))
21 PTE = AccessMemory(PTEAddr)
22 if (PTE.Valid == False)
23 RaiseException(SEGMENTATION_FAULT)
24 else if (CanAccess(PTE.ProtectBits) == False)
25 RaiseException(PROTECTION_FAULT)
26 else
27 TLB_Insert(VPN, PTE.PFN, PTE.ProtectBits)
28 RetryInstruction()
일단 복잡한 멀티 레벨 페이지 테이블 접근을 시작하기 전에 하드웨어는 먼저 TLB를 체크한다.(2, 3) 만약 히트가 나면, 그 페이지 테이블 접근 전체를 생략하고 바로 물리 주소를 만들 수 있다. 오직 TLB가 miss 날 때에야 하드웨어가 아까 설명한 전체적으로 뒤지는 과정을 수행하는 것이다. 여기서 우리는 멀티 레벨 페이지의 비용에 대해 생각해볼 수 있다.(유효한 번역을 찾기 위해 두 번의 추가 메모리 접근을 필요로 하는 것이다.)
역전 페이지 테이블 :
페이지 테이블을 더 극도로 공간 절약하고 싶다면 역전 페이지 테이블이 있을 것이다. 여기서는, 다수의 페이지 테이블을 가지는 대신에(누누이 말했지만, 일반적인 페이지 테이블은 프로세스 당 자료구조다.), 시스템의 각 물리 주소를 위한 엔트리로 이루어진 단 하나의 페이지 테이블만 가지고 있다. 엔트리는 어느 프로세스가 해당 페이지를 사용 중인지, 그리고 어느 프로세스의 가상 페이지가 이 물리 페이지에 대응하는지를 매핑하고 있다.
올바른 엔트리를 찾는 것은 이제 이 자료구조를 뒤지면 된다. 선형적으로 스캔하는 것은 비용이 많이 들기 때문에, 조금 더 쉽게 뒤지기 위해서 해시 테이블이 기본 구조로 자주 채용된다. PowerPC가 대표적인 아키텍처라고 할 수 있다.
더 일반적으로는, 역전 페이지 테이블은 우리가 최초부터 이야기했던 것을 반영하고 있는 셈이다. 페이지 테이블은 그냥 자료구조일 뿐이다. 여러분들은 자료구조를 써서 다양한 미친 짓을 할 수 있다. 더 작게 또는 더 크게 만들거나, 더 느리게 또는 더 빠르게 만들거나. 멀티 레벨과 역전 페이지 테이블은 그냥 수많은 그런 버전의 두 예시일 뿐이다.
페이지 테이블을 스토리지로 스왑 하기 :
이제 우리의 마지막 가정에 대해 이야기를 나눠보자. 우리는 지금까지 페이지 테이블이 커널 소유의 물리 메모리에 상주하고 있다 했었다. 우리가 아무리 위에서 별별 기법을 총동원해서 페이지 테이블의 사이즈를 줄였다 하더라도, 그럼에도 불구하고, 여전히 메모리에 페이지 테이블을 때려 박는 것은 충분히 부담스러울 수 있다.
그러므로, 어떤 시스템들은 그런 페이지 테이블을 커널 가상 메모리에 둔다. 그럼으로써 시스템이 메모리 공간이 약간 타이트해졌을 때 이 페이지들의 일부를 스토리지 쪽으로 스왑 해놓는 것을 허용하는 것이다. 나중에 어떻게 페이지들을 메모리에 넣고 꺼내는지(구체적으로, VAX/VMS에 대한 사례 학습이 될 것이다.) 더 자세히 이해해보고 공부할 것이다.
마치며 :
우리는 진짜 페이지 테이블들이 어떻게 구성되는지 알아보았다.(그냥 선형 배열뿐 아니라 더 복잡한 구조에 대해서도) 이런 테이블들의 트레이드-오프는 시공간 속에 있는 것이다. 즉, 더 큰 테이블이라면 더 빠르게 TLB 미스를 고칠 수 있고, 그에 inverse 한 관계(수학에서는 이를 이異라고 한다. 역, 이, 대우할 때 그것이다.)도 가능한 것이다. 그러니까 주어진 환경과 제한조건에 강하게 의존하는 이런 구조들을 올바로 선택하는 것이 우리 아키텍처 전문가들이 해내야 할 일이라고 할 수 있겠다.
메모리 바운드한 시스템(수많은 옛날 컴퓨팅 머신에 해당한다.)에서는 작은 자료구조가 말이 된다. 만약 어떤 시스템이 대량의 페이지를 활발히 사용할 수 있는 워크로드를 감당할 수 있는, 합리적인 용량의 메모리를 갖추고 있다면, 더 큰 페이지 테이블을 채용해서 TLB 미스가 났을 때 빠르게 복구할 수 있도록 하는 게 정답일 것이다.
소프트웨어가 관리하는 TLB에서는, 하드웨어 관리 기반의 경우보다 자유도가 높아, 전체 자료구조 공간을 운영체제 혁신가의 지혜로 자유롭게 꾸밀 수 있을 것이다.(그 혁신가가 누구냐고? 바로 여러분이다.) 여러분들이 짠 새 구조체는 무엇인가? 그것으로 무엇을 해결할 수 있는가? 부디 이런 질문들을 잠들 때에도 고민해주기 바란다. 그리고 운영체제 개발자들과 같이 커다란 꿈을 꿔주길 바란다.
출처 : REMZI H. ARPACI-DUSSEAU, ANDREA C. ARPACI-DUSSEAU, UNIVERSITY OF WISCONSIN–MADISON, "OPERATING SYSTEMS THREE EASY PIECES", Arpaci-Dusseau Books.
'OS' 카테고리의 다른 글
| [운영체제] 19. TLB란 (0) | 2022.01.24 |
|---|---|
| [운영체제] 18. Paging이란 (1) | 2022.01.21 |