2-12장. 페이징 : 더 빠른 변환(TLB)

앞서 봤던 페이징은 상당한 성능 저하를 가져올 수 있다. 큰 메모리 공간이 요구되며 작업은 엄청난 성능 저하를 유발한다. 

 

운영체제의 실행 속도를 개선하려면, 도움이 필요하다. 대부분의 경우 하드웨어로부터 도움을 받는다. 주소 변환을 빠르게 하기 위해서 변환-색인 버퍼(Translation-lookaside buffer) 또는 TLB 부르는 것을 도입한다.

 

TLB는 칩의 메모리 관리부(MMU)의 일부다. 자주 참조되는 가상 주소-실주소 변환 정보를 저장하는 하드웨어 캐시이다. 주소-변환 캐시(Address-translation cache)가 좀 더 적합한 명칭이다. 가상 메모리 참조 시, 하드웨어는 먼저 TLB에 원하는 변환 정보가 있는지를 확인한다. 만약 있다면 페이지 테이블을 통하지 않고 변환을 빠르게 수행한다. 실질적으로 TLB는 페이징 성능을 엄청나게 향상한다.  TLB를 도입함으로써, 페이징이 사용 가능한 가상 메모리 기법이 된다.

 

TLB의 기본 알고리즘

위 코드는 가상 주소 변환이 이루어지는 과정을 대략적으로 나타내고 있다. 주소 변환부가 단순한 선형 페이지 테이블(즉, 배열로 이루어진 페이지 테이블)과 하드웨어로 관리되는 TLB로 구성되어 있다.

 

하드웨어 부분 알고리즘은 다음과 같이 동작한다. 먼저, 가상 주소(1번 라인)에서 가상 페이지 번호(VPN)를 추출한 후, 해당 VPN의 TLB 존재 여부를 검사한다.(2번 라인) 만약 존재하면 TLB 히트이고 TLB가 변환값을 갖고 있다는 것을 뜻한다. 이제 해당 TLB 항목에서 페이지 프레임 번호(PFN)를 추출할 수 있다. 해당 페이지에 대한 접근 권한 검사가 성공하면(4번 라인), 그 정보를 원래 가상 주소의 오프셋과 합쳐서 원하는 물리 주소(PA)를 구성하고, 메모리에 접근할 수 있다.(5~7번 라인)

 

TLB에 변환 정보가 존재하지 않는다면 (TLB 미스) 할 일이 많다. 여기서는 하드웨어가 변환 정보를 찾기 위해서 페이지 테이블에 접근하며(12-13번 라인), 프로세스가 생성한 가상 메모리 참조가 유효하고 접근 가능하다면, 해당 변환 정보를 TLB로 읽어 들인다.(16번 라인) 매우 시간이 많이 소요되는 작업이다. 페이지 테이블 접근을 위한 메모리 참조 때문이다.(13번 라인) TLB가 갱신되면 하드웨어는 명령어를 재실행한다. 이번에는 TLB에 변환 정보가 존재함으로, 메모리 참조가 빠르게 처리된다. 

 

모든 캐시의 설계 철학처럼, TLB 역시 "주소 변환 정보가 대부분의 경우 캐시에 있다"라는 가정을 전제로 만들어졌다. TLB는 프로세싱 코어와 가까운 곳에 위치하고 있고, 매우 빠른 하드웨어로 구성되기 때문에, 주소 변환 작업은 그다지 부담스러운 작업이 아니다. 미스가 발생하는 경우, 페이징 비용이 커진다. 페이지 테이블을 접근하여 변환 정보를 찾아야 한다. 메모리 참조가 추가된다. 이 상황이 자주 일어나면 프로그램은 상당히 느려지게 된다. 메모리 접근 연산은 다른 CPU 연산에 비해 매우 시간이 오래 걸린다. TLB 미스가 많이 발생할수록 메모리 접근 횟수가 많아진다. TLB 미스가 발생하는 경우를 최대한 피해야 한다.

 

예 : 배열 접근

TLB 작동 과정을 좀 더 명확히 알아보자. 간단한 가상 주소 트레이스를 대상으로 TLB로 인한 성능 개선을 알아보자. 이 예제에서는 가상 주소 100번지부터 10개의 4바이트 크기의 정수 배열이 존재한다. 가상 주소 공간은 8비트이며, 페이지 크기는 16바이트이다. 가상 주소는 4비트 VPN과 4비트 오프셋으로 구성된다.

 

위 그림은 16개의 페이지로 구성된 가상 주소 공간을 도식적으로 표현하고 있다. 배열의 첫 항목(a [0])은 (VPN=06, 오프셋=04)에서 시작한다. 세 개의 4바이트 정수가 페이지에 들어갈 수 있다. 배열은 다음 페이지(VPN=07)에서 계속된다. a[3] ... a[6]의 네 항목이 존재한다. 배열의 마지막 세 개의 항목(a[7] ... a[9])은 주소 공간(VPN=08)에 시작하는 다음 페이지에 들어 있다.

 

배열 원소의 합을 구하는 간단한 코드를 살펴보자. C 코드는 다음과 같다. 

 

정수 배열에 대한 메모리 접근만 보기로 하겠다. 첫 번째 배열의 항목 (a[0])이 접근된다. 가상 주소 100번이다. 하드웨어는 VPN을 추출한다. VPN이 06번이다. 하드웨어는 TLB에서 해당 VPN을 검색한다. TLB가 완전히 초기화되어 있다 가정하자. 첫 접근이다. TLB 미스가 발생한다. 미스가 발생하면 해당 VPN 06번에 대한 물리 페이지 번호를 찾아 TLB를 갱신한다.

 

다음은 a[1]을 읽는다. a[1]을 읽을 때에는 상황이 좋다. TLB 히트다. 해열의 두 번째 항목은 첫 번째 항목과 같은 페이지에 존재한다. 첫 번째 항목을 읽을 때, 이미 해당 페이지를 접근하였기 때문에, 필요한 변환 정보가 이미 TLB에 탑재되어 있다. 두 번째 항목을 읽을 때 역시 TLB 히트가 발생한다. a[2]에 대한 접근도 같은 식으로 TLB 사용에 성공한다. 이 항목도 a[0], a[1]과 같은 페이지에 있기 때문이다.

 

불행히도 a[3]을 읽을 때에는 상황이 안 좋다. TLB 미스다. 하지만, 그 다음 항목들(a[4] ... a[6])은 메모리 내에 같은 페이지에 있기 때문에 TLB 히트가 된다.

 

a[7]을 접근할 때 마지막 TLB미스가 발생한다. 하드웨어는 페이지 테이블을 참고하여 가상 페이지에 해당하는 물리 메모리를 파악한 후에 TLB를 갱신한다. 마지막 두 개의 접근(a[8], a[9])은 이미 갱신된 TLB에서 주소 변환 정보를 얻는다. 두 번의 TLB히트가 발생한다.

 

배열 원소를 읽은 TLB 동작을 정리해 보면 미스, 히트, 히트, 미스, 히트, 히트, 히트, 미스, 히트, 히트가 된다. 히트 회수를 총 접근 횟수로 나누어 얻는 TLB 히트 비율은 70%가 된다. 배열이 처음으로 접근되었지만, TLB는 공간 지역성(Spatial locality)으로 인해서 성능을 개선할 수가 있다.

 

공간 지역성

예제에서 보는 바와 같이 페이지 크기는 TLB의 효용성에 매우 중요한 역할을 한다. 페이지 크기가 두 배가 되면, TLB 미스 횟수가 더 줄어든다. 예제와 같이, 정수 배열을 연속적으로 접근하는 프로그램 같은 경우, TLB 사용은 큰 성능 개선 효과를 가져올 것이다. 페이지 접근 시 한 번의 미스만 발생하기 때문이다.

 

만약 예제 프로그램이 루프 종료 후에도 배열을 사용한다면, 성능은 더욱 개선될 것이다. 모든 주소 변환 정보가 TLB에 탑재되어 있기 때문이다. TLB가 모든 주소 변환 정보를 저장할 정도로 충분히 크다면 모두 히트를 얻는다. 이 경우에서는, 시간 지역성(Temporal locality)으로 인해 TLB의 히트율이 높아진다. 시간 지역성이란 한번 참조된 메모리 영역이 짧은 시간 내에 재 참조되는 현상을 일컫는다.

시간 지역성

다른 캐시와 마찬가지로 TLB의 성공 여부는 프로그램의 공간 지역성과 시간 지역성 존재 여부에 달려있다. 만약 프로그램이 공간 혹은 시간 지역성을 보이는 경우, TLB 사용 효과가 더욱 두드러지게 나타날 것이다. 실제로 많은 프로그램들이 공간 지역성이나 시간 지역성을 띄고 있다.

 

TLB 미스는 누가 처리할까?

TLB 미스의 처리는 어디서 담당할까? 두 가지 방법이 있다. 하드웨어와 소프트웨어(운영체제)이다. 과거 하드웨어는 복잡한 명령어들로 구성되어 있었다. 이를 CISC(Complex-Instruction Set Computers)라고 통칭했다. 하드웨어 엔지니어들은 운영체제 설계자를 믿지 못했던 이유로 TLB 미스를 하드웨어가 처리하도록 설계했다. 이를 위해서 하드웨어가 페이지 테이블에 대한 명확한 정보를 가지고 있어야 한다. 메모리 상 위치와 정확한 형식을 파악하고 있어야 한다. 미스 발생 시 하드웨어는 다음과 같은 일을 한다. 

 

1. 페이지 테이블에서 원하는 페이지 테이블 엔트리를 찾는다.

2. 필요한 변환 정보를 추출한다.

3. TLB를 갱신한다.

4. TLB 미스가 발생한 명령어를 재실행한다.

인텔 x86 CPU가 하드웨어로 관리되는 TLB의 대표적인 예이다. 

 

RISC(Reduced Instruction Set Computing)는 CISC보다 최근에 등장한 컴퓨터 구조이다. RISC 기반 컴퓨터는 소프트웨어 관리 TLB(Software-managed TLB)를 사용한다. RISC 기반 컴퓨터에서 TLB 미스를 처리하는 과정은 다음과 같다.

 

TLB 제어 흐름 알고리즘 (운영체제가 관리)

TLB에서 주소 찾는 것이 실패하면, 하드웨어는 예외 시그널을 발생시킨다(11번 라인). 예외 시그널을 받은 운영체제는 명령어 실행을 잠정 중지하고, 실행 모드를 커널 모드로 변경하여, 커널 코드 실행을 준비한다. 실행 모드를 커널 모드로 변경하는 작업의 핵심은 커널 주소 공간을 접근할 수 있도록 특권 레벨로 상향 조정하는 것이다. 커널 모드로 변경이 되면 트랩 핸들러(Trap handler)를 실행한다. 이때 실행되는 트랩 핸들러는 TLB 미스의 처리를 담당하는 운영체제 코드이다. 이 트랩 핸들러는 페이지 테이블을 검색하여 변환 정보를 찾고, TLB 접근이 가능한 "특권" 명령어를 사용하여 TLB를 갱신한 후에 리턴한다. 트랩 핸들러에서 리턴되면 하드웨어가 명령어를 재실행한다. 트랩 핸들러가 TLB를 갱신했으므로 이제는 TLB 히트가 날 것이다.

 

두 가지 중요한 사항을 다시 짚어보자. 첫 번째, TLB 미스를 처리하는 트랩 핸들러는 시스템 콜 호출 시 사용되는 트랩 핸들러와의 차이가 있다. 시스템 콜 호출의 경우는 트랩 핸들러에서 리턴 후 시스템 콜을 호출한 명령어의 "다음" 명령어를 실행한다. 일반적인 프로시저 콜과 동일하다. 프로시저 콜이 리턴되면, 프로시저를 호출한 다음 라인부터 실행이 시작된다. TLB의 경우는 다르다. TLB 미스 처리의 경우, 트랩에서 리턴하면 트랩을 발생시킨 명령을 "다시" 실행해야 하며, 재실행 시에는 TLB에서 히트가 발생한다. 트랩이 발생하면 운영체제는 트랩 핸들러가 종료되었을 때 다시 실행을 계속할 명령어 주소(PC 값)를 저장한다. 고로, 운영체제는 트랩 발생의 원인에 따라 현재 명령어 PC값 혹은 다음 명령어 PC값을 저장해야 한다.

 

두 번째, TLB 미스 핸들러를 실행할 때, TLB 미스가 무한 반복되지 않도록 주의를 해야 한다. TLB미스 핸들러를 접근하는 과정에서 TLB 미스가 발생하는 상황이다. 이를 위해 다양한 해법들이 존재한다. 예를 들면, TLB 미스 핸들러를 물리 메모리에 위치시키는 것도 한 방법이다. TLB 미스 핸들러의 주소는 핸들러의 '물리' 주소로 표시된다. 이 경우 해당 TLB 미스 핸들러는 unmap 되어 있으며 주소 변환이 필요 없다. 다른 방법으로 TLB의 일부 핸들러 코드 주소를 저장하는 데 영구히 할당하는 것이다. 이렇게 되면 TLB 핸들러는 항상 TLB에 히트된다. 이를 연결(Wired) 변환이라 한다.

 

TLB를 소프웨어로 관리하는 방식의 주된 장점은 유연성이다. 운영체제는 하드웨어 변경 없이 페이지 테이블 구조를 자유로이 변경할 수 있다. 또 다른 장점은 단순함이다. TLB 제어 흐름에서 보는 것과 같이 미스가 발생하였을 때 하드웨어는 별로 할 일이 없다. 예외가 발생하면 운영체제의 TLB 미스 핸들러가 나머지 일을 처리한다.

 

TLB의 구성 : 무엇이 있나?

하드웨어 TLB의 구성을 좀 더 상세히 살펴보자. 일반적인 TLB는 32, 64, 또는 128개의 엔트리를 가지며, 완전 연관(Fully associative) 방식으로 설계된다. 완전 연관 방식에서 변환 정보는 TLB 내에 어디든 위치할 수 있으며, 원하는 변환 정보를 찾는 검색은 TLB 전체에서 병렬적으로 수행된다. TLB의 구성은 아래와 같다.

 

변환 정보 저장 위치에 제약이 없도록, 각 항목마다 가상 페이지 번호(VPN)와 물리 페이지 번호(PFN)가 있다. 하드웨어 측면에서 보자면, TLB는 완전 연관 캐시이다. 변환 주소를 찾을 때, 하드웨어는 TLB의 각 항목을 동시에 검색한다. 

 

TLB 항목에서 VPN과 PFN을 제외한 "다른 비트들"에 대해서도 눈여겨볼 필요가 있다. TLB는 일반적으로 valid bit를 갖고 있다. 이 비트는 특정 항목이 유효한 변환 정보를 갖고 있는지 여부를 나타낸다. 보호(Protection) 비트라는 것도 있다. 보호 비트들은 페이지가 어떻게 접근될 수 있는지를 나타낸다. 그 쓰임새는 페이지 테이블에서와 같다. 예를 들어, 코드 페이지들에 대한 변환은 읽기와 실행이라고 표기가 되어 있으며 힙 페이지들은 읽기와 쓰기라고 표기되어 있을 수 있다. 그 외에 주소 공간 식별자(Address-space identifier), 더티 비트(Dirty bit) 등도 있다.

 

TLB의 문제 : 문맥 교환

TLB를 사용하게 되면 프로세스 간 문맥 교환 시, 새로운 문제가 등장한다. TLB에 있는 가상 주소와 실제 주소 간의 변환 정보는 그것을 탑재시킨 프로세스에서만 유효하다. 다른 프로세스들에게는 의미가 없다. 새로운 프로세스에서는 이전에 실행하던 프로세스의 변환 정보를 사용하지 않도록 주의해야 한다.

 

예제를 하나 살펴보자. 하나의 프로세스 A가 실행 중이라고 하자. 이 프로세스는 TLB가 자신에게 유효한 변환 정보를 캐싱하고 있다고 가정한다. 즉, A의 페이지 테이블의 내용을 갖고 있다고 가정한다. 이 예제에서는 A의 10번째 가상 페이지가 물리 프레임 100에 매핑되어 있다고 하자.

 

이 예제에서는 또 다른 프로세스 B가 있다고 가정하고 운영체제가 곧 문맥 교환을 수행하기로 결정하여 이 프로세스를 실행시키려고 한다. B의 10번째 가상 페이지는 물리 프레임 170에 매핑되어 있다고 가정하자. 두 프로세스의 항목들이 TLB에 존재한다고 하면 TLB의 내용은 다음과 같이 될 것이다.

 

위에 TLB에 문제가 있다. VPN 10에 대한 변환 정보가 두 개 존재하는 것이다. 10번 VPN이 PFN 100(A)과 PFN 170(B)으로 변환될 수 있다. 하지만, 어떤 프로세스를 위한 항목인지 알 길이 없다. TLB가 정확하고 효율적으로 멀티 프로세스 간의 가상화를 지원하기 위해서는 추가적 기능이 필요하다.

 

문제 해결 방법

이 문제는 여러 해법이 있을 수 있다. 한 방법은 문맥 교환을 수행할 때 다음 프로세스가 실행되기 전에 기존 TLB 내용을 비우는 것이다. 소프트웨어 기반의 시스템에서는 특별한 하드웨어 명령어를 사용하여 이 목적을 달성할 수 있다. 하드웨어로 관리되는 TLB는 페이지 테이블 베이스 레지스터가 변경될 때 비우기를 시작할 수 있다.(운영체제는 문맥 교환을 할 때 PTBR을 어쨌든 변경해야 한다) 둘 중 어느 경우든 비우는 작업은 모든 valid bit를 0으로 설정하는 것이다.

 

문맥 교환할 때마다 TLB를 비우면, 잘못된 변환 정보를 사용하는 상황을 방지할 수 있다. 하지만 이 방식은 공짜가 아니다. 새로운 프로세스가 실행될 때, 데이터와 코드 페이지에 대한 접근으로 인한 TLB 미스가 발생하게 된다. 문맥 교체가 빈번히 발생한다면, 이 또한 성능에 큰 부담을 가져올 수 있다.

 

이 부담을 개선하기 위해 몇몇 시스템에서는 문맥 교환이 발생하더라도 TLB의 내용을 보존할 수 있는 하드웨어 기능을 추가하였다. TLB 내에 주소 공간 식별자(Address space identifier, ASID) 필드를 추가하는 것이 그것이다. ASID는 프로세스 식별자(Process identifier, PID)와 대략적으로 유사하다. 단, ASID는 좀 더 적은 비트를 갖고 있다. 위에서 사용한 TLB 예제에 ASID 정보를 추가하면 프로세스들이 TLB의 공간을 공유할 수가 있다. 

 

주소 공간 식별자를 사용할 경우, 프로세스 별로 TLB 변환 정보를 구분할 수 있다. 올바른 주소 변환을 위해서 하드웨어는 현재 어떤 프로세스가 실행 중인지 파악하고 있어야 한다. 이를 위해, 문맥 전환 시, 운영체제는 새로운 ASID 값을 정해진 레지스터에 탑재한다.

 

추가적으로 TLB의 두 항목이 매우 유사한 경우를 생각해 볼 수도 있다. 이 예제에서는 두 개의 다른 VPN을 갖는 두 개의 다른 프로세스들의 두 항목이 동일한 물리 페이지를 가리키고 있다.

 

이러한 경우는 두 개의 프로세스들이 하나의 페이지를 공유하고 있을 때 발생할 수가 있다. 이 예제에서는 프로세스 1이 물리 페이지 101을 프로세스 2와 공유하고 있다. A는 이 페이지를 자신의 주소 공간의 10번째 페이지에 매핑하고 있으며 B는 자신의 주소 공간의 50번째 페이지에 매핑하고 있다. 코드 페이지를 공유하는 것은 사용되는 물리 페이지의 수를 줄일 수 있기 때문에 유용하다. 그리고 공유 페이지를 사용하면 메모리 부하도 줄일 수 있다.

 

TLB 교체 정책

모든 캐시가 그러하듯 TLB에서도 캐시 교체(Cache replacement) 정책이 매우 중요하다. TLB에 새로운 항목을 탑재할 때, 현재 존재하는 항목 중 하나를 교체 대상으로 선정해야 한다. 어느 것을 선택해야 할까?

 

흔한 방법은 가장 오래전부터 사용되었던 최저 사용 빈도(Least-recently-used, LRU) 항목을 교체하는 것이다. LRU는 메모리 참조 팬턴에서의 지역성을 최대한 활용하는 것이 목적이다. 사용되지 않은지 오래된 항목일수록, 앞으로도 사용될 가능성이 적으며, 교체 대상으로 적합하다는 가정에 근거한다. 

 

 

실제 TLB

마지막으로 실제 TLB가 어떻게 생겼는지 간략히 살펴보자. MIPS R4000을 예로 들겠다. MIPS R4000은 소프트웨어로 관리되는 TLB를 사용한다. 비교적 최근 시스템이다. MIPS의 간략화된 TLB 항목은 다음과 같다.

 

MIPS R4000은 32비트 주소 공간에 4KB 페이지를 지원한다. 일반적인 가상 주소 공간을 사용하기 때문에 VPN은 20비트 그리고 오프셋으로 12비트를 가질 것이라 예측할 수 있지만, 아니다. TLB에서 보는 바와 같이 19비트가 VPN에 할당되어 있다. 전체 주소 공간의 절반만 사용자 주소 공간으로 할당되어 있기 때문에, VPN에 19비트가 할당되어 있다. 물리 프레임 번호(PFN)로 24비트가 할당되어 있다. 64GB의 주 메모리 지원이 가능하다.(2^24개의 4KB 페이지들)

 

MIPS의 TLB에는 몇 가지 중요한 비트들이 더 있다. 전역 비트 (G)다. 이 비트는 프로세스들 간에 공유되는 페이지들을 위해 사용된다. 전역 비트가 설정되어 있으면 ASID는 무시된다. 8비트 길이의 ASID 필드가 있다. 운영체제는 이 부분을 보고 주소 공간들을 서로 구분한다. 

 

더티 비트는 페이지가 갱신되면 세팅되며, 유효 비트는 항목에 유효한 변환 정보가 존재하는지를 나타낸다. 그리고 페이지 마스크 필드도 있는데, 여러 개의 페이지 크기를 지원할 때 사용된다. 마지막으로 64번째 비트는 사용하지 않는다.