[운영체제 아주 쉬운 세 가지 이야기 - Virtualization] 19. Translation Lookaside Buffers
이 글은 제 개인적인 공부를 위해 작성한 글입니다.
틀린 내용이 있을 수 있고, 피드백은 환영합니다.
개요
페이징은 상당한 성능 저하를 가져올 수 있다. 페이징은 프로세스 주소 공간을 작은 고정된 크기인 페이지로 나누고 각 페이지의 실제 위치인 매핑 정보를 메모리에 저장한다. 매핑 정보를 저장하는 자료 구조를 페이지 테이블이라고 하고, 정보 저장을 위해 큰 메모리 공간이 요구된다.
무엇보다 중요한 것은 가상 주소에서 물리 주소로의 변환을 위해 메모리에 존재하는 매핑 정보를 읽어야 한다는 사실이다. 페이지 테이블 접근을 위한 메모리 읽기 작업은 엄청난 성능 저하를 유발한다. 모든 load/store 명령어 실행이 추가적인 메모리 읽기를 수반하는 상황을 가정한다면 머리 아프다.
어떻게 하면 주소 변환을 빨리 할 수 있고, 페이징에서 발생하는 추가 메모리 참조를 피할 수 있을까? 어떤 하드웨어가 추가로 필요하고 운영체제가 어떤 식으로 개입해야 할까?
운영체제의 실행 속도를 개선하려면, 대부분의 경우 하드웨어로부터 도움을 받는다. 주소 변환을 빠르게 하기 위해서 우리는 변환-색인 버퍼(translation lookaside buffer, TLB)라고 부르는 것을 도입한다. TLB는 칩의 메모리 관리부(memory management unit, MMU)의 일부이고 자주 참조되는 가상 주소-실주소 변환 정보를 저장하는 하드웨어 캐시이다. 주소-변환 캐시(address-translation cache)가 좀 더 적합한 명칭이다.
가상 메모리 참조 시, 하드웨어는 먼저 TLB에 원하는 변환 정보가 있는지 확인한다. 만약 있다면 페이지 테이블을 통하지 않고 변환을 빠르게 수행한다. TLB를 도입함으로써 페이징 성능을 엄청나게 향상시키고, 페이징이 “사용 가능”한 가상 메모리 기법이 된다.
TLB의 기본 알고리즘
위 그림은 가상 주소 변환이 이루어지는 과정을 대략적으로 나타내고 있다. 주소 변환부가 단순한 선형 페이지 테이블(linear page table, 즉 배열)과 하드웨어로 관리되는 TLB로 구성되어 있다.
하드웨어 부분의 알고리즘은 다음과 같이 동작한다.
- 가상 주소에서 가상 페이지 번호 VPN을 추출한 후, 해당 VPN의 TLB 존재 여부를 검사한다.
- TLB 히트라면 해당 TLB 항목에서 페이지 프레임 번호 PFN를 추출한다.
- 해당 페이지에 대한 접근 권한 검사가 성공하면 그 정보를 원래 가상 주소의 오프셋과 합쳐서 원하는 물리 주소 PA를 구성하고, 메모리에 접근할 수 있다.
- TLB 미스라면 페이지 테이블에 접근한다.
- 프로세스가 생성한 가상 메모리 참조가 유효하고 접근 가능하다면, 해당 변환 정보를 TLB로 읽어들인다. 이는 페이지 테이블 접근을 위한 메모리 참조 때문에 많은 시간이 소요된다.
- TLB가 갱신되면 하드웨어는 명령어를 재실행한다.
모든 캐시의 설계 철학처럼, TLB 역시 “주소 변환 정보가 대부분의 경우 캐시에 있다”, 즉 캐시에서 히트라는 가정을 전제로 만들어졌다. TLB는 프로세싱 코어와 가까운 곳에 위치하고 있고, 매우 빠른 하드웨어로 구성되기 때문에, 주소 변환 작업은 그다지 부담스러운 작업이 아니다.
TLB 미스가 발생하는 경우에 페이지 테이블에 접근하여 변환 정보를 찾아야 하기에 페이징 비용이 커진다. 이러한 메모리 참조는 다른 CPU 연산에 비해 시간이 매우 오래 걸리기에 자주 일어나면 프로그램은 상당히 느려지게 된다. TLB 미스가 많이 발생할수록 메모리 접근 횟수가 많아지니 TLB 미스가 발생하는 경우를 최대한 피해야 한다.
TLB 미스는 누가 처리할까
TLB 미스를 처리하는 두 가지 방법이 있다. 하드웨어와 소프트웨어(운영체제)이다.
과거 하드웨어는 복잡한 명령어들로 구성되어 있었고, 이를 CISC(complex instruction set computer)라고 부른다. 하드웨어 엔지니어들은 엉뚱한 방법쓰기를 좋아하는 운영체제 개발자들의 특성 때문에 그들을 완전히 신뢰할 수가 업성ㅆ다. 이런 이유로 TLB 미스를 하드웨어가 처리하도록 설계했다.
이를 위해서 하드웨어가 페이지 테이블에 대한 명확한 정보를 가지고 있어야 한다. 메모리 상 위치와 정확한 형식을 파악하고 있어야 한다. 미스 발생 시 하드웨어는 다음과 같은 일을 한다.
- 페이지 테이블에서 원하는 페이지 테이블 엔트리를 찾는다.
- 필요한 변환 정보를 추출한다.
- TLB를 갱신한다.
- TLB 미스가 발생한 명령어를 재실행한다.
인텔 x86 CPU가 하드웨어로 관리되는 TLB의 대표적인 예이다. x86 CPU는 멀티 레펠 페이지 테이블(multi-level page table)을 사용하낟. CR3 레지스터가 페이지 테이블 주소를 가지고 있다.
RISC(reduced instruction set computing)는 CISC보다 최근에 등장한 컴퓨터 구조이다. RISC 기반 컴퓨터는 소프트웨어 관리 TLB(software-managed TLB)를 사용한다. RISC 기반 컴퓨터에서 TLB 미스를 처리하는 과정은 다음과 같다.
- TLB에서 주소 찾는 것이 실패하면, 하드웨어는 예외 시그널을 발생시킨다.
- 예외 시그널을 받은 운영체제는 명령어 실행을 잠정 중지하고, 실행 모드를 커널 모드로 변경하여, 커널 코드 실행을 준비한다.
- 커널 주소 공간에 접근할 수 있도록 특권 레벨을 상향 조정하여 트랩 핸들러(trap handler)를 실행한다. 이때 실행되는 트랩 핸들러는 TLB 미스의 처리를 담당하는 운영체제 코드이다.
- 이 트랩 핸들러는 페이지 테이블을 검색하여 변환 정보를 찾고, TLB 접근이 가능한 “특권” 명령어를 사용하여 TLB를 갱신한 후에 리턴한다.
- 트랩 핸들러에서 리턴되면 하드웨어가 명령어를 재실행하여 TLB 히트를 낼 수 있다.
두 가지 중요한 사항이 있다.
첫 번째, TLB 미스를 처리하는 트랩 핸들러는 시스템 콜 호출 시 사용되는 트랩 핸들러와의 차이가 있다. 시스템 콜 호출의 경우는 일반적인 프로시저 콜과 동일하게 트랩 핸들러에서 리턴 후 시스템 콜을 호출한 명령어의 “다음” 명령어를 실행한다.
TLB 미스 처리의 경우, 트랩에서 리턴하면 트랩을 발생시킨 명령을 다시 실행해야 하며, 재실행 시에는 TLB에서 히트가 발생한다. 트랩이 발생하면 운영체제는 트랩 핸들러가 종료되었을 때 다시 실행을 계속할 명령어 주소(Program Counter 값)을 저장한다.
여기서 중요한 사실은 운영체제는 트랩 발생 원인에 따라 현재 명령어의 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 | 다른 비트들 |
변환 정보 저장 위치에 제약이 없도록, 각 항목마다 가상 페이지 번호 VPN과 물리 페이지 번호 PFN이 있다. 하드웨어 측면에서 보자면, TLB는 완전 연관 캐시이다. 변환 주소를 찾을 떄, 하드웨어는 TLB의 각 항목을 동시에 검색한다.
TLB 항목에서 VPN과 PFN을 제외한 “다른 비트들”에 대해서도 눈여겨 볼 필요가 있다.
TLB는 일반적으로 valid bit를 가지고 있다. 이 비트는 특정 항목이 유효한 변환 정보를 가지고 있는지 여부를 나타낸다.
보호(protection) 비트는 페이지가 어떻게 접근될 수 있는지를 나타낸다. 쓰임새는 페이지 테이블에서와 같다. 예를 들어, 코드 페이지들에 대한 변환은 읽기와 실행이라고 표기가 되어 있으며 힙 페이지들은 읽기와 쓰기라고 표기되어 있을 수 있다.
그 외에, 주소 공간 식별자(address space identifier), 더티 비트(dirty bit 등도 있다.
여담
TLB valid bit != 페이지 테이블 valid bit
페이지 테이블의 어떤 엔트리가 무효로 표시되어 있다면 해당 페이지는 프로세스에 할당되지 않았다는 것을 의미한다.
TLB의 valid bit는 TLB에 탑자되어 있는 해당 변환 정보가 유효한지를 나타내기 위해 사용된다. 예를 들어, 시스템이 시작되면 어떤 변환 정보도 아직 캐시되지 않았기 때문에 일반적으로 TLB의 모든 항목은 “무효”로 초기화되어 있다. 가상 메모리가 초기화되고, 프로그램들이 실행을 시작하여 자신의 가상 주소 공간을 접근하게 되면, TLB는 곧 유효한 항목들로 채워지게 된다.
TLB의 문제 : 문맥 교환
TLB를 사용하게 되면 프로세스 간 문맥 교환 시, 새로운 문제가 등장한다. TLB에 있는 가상 주소와 실제 주소 간의 변환 정보는 그것을 탑재시킨 프로세스에서만 유효하고 다른 프로세스들에게는 의미가 없다. 새로운 프로세스에서는 이전에 실행하던 프로세스의 변환 정보를 사용하지 않도록 주의해야 한다.
에제를 하나 살펴보자. 하나의 프로세스 P1이 실행 중이고 이 프로세스는 TLB가 P1의 페이지 테이블의 내용을 가지고 있다. 예를 들어, P1의 10번째 가상 페이지가 물리 프레임 100에 매핑되어 있다고 하자.
또 다른 프로세스 P2가 있고, 운영체제가 곧 문맥 교환을 하기로 하여 P2를 실행시키려고 한다. P2의 10번째 가상 페이지는 물리 프레임 170에 매핑되어 있다.
위의 TLB에는 문제가 있다. VPN 10에 대한 변환 정보가 두 개 존재하는 것이다. 10번 VPN이 PFN 100(P1)과 PFN 170(P2)으로 변환될 수 있다.
하지만, 어떤 프로세스를 위한 항목인지 알 길이 없다. TLB가 정확하고 효율적으로 멀티 프로세스 간의 가상화를 지원하기 위해서는 추가적인 기능이 필요하다.
문맥 교환 시 실행 될 프로세스에게는 이전 프로세스가 사용한 TLB 정보는 의미가 없다. 하드웨어 또는 운영체제는 이러한 문제를 해결하기 위해 무엇을 해야 하는가?
한 가지 방법은 문맥 교환을 수행할 때 다음 프로세스가 실행 되기 전에 기존 TLB 내용을 비우는 것이다. 소프트웨어 기반의 시스템에서 특별하고 특권을 갖는 하드웨어 명령어를 사용하여 이 목적을 달성할 수 있다. 하드웨어로 관리되는 TLB는 페이지 테이블 베이스 레지스터가 변경될 때 비우기를 시작할 수 있다.
둘 중 어느 경우든 비우는 작업은 모든 valid bit를 0으로 설정하는 것이다.
문맥 교환 시 마다 TLB를 비우면 잘못된 변환 정보를 사용하는 상황을 방지할 수 있지만, 비용이 비싸다. 새로운 프로세스가 실행될 때, 데이터와 코드 페이지에 대한 접근으로 인한 TLB 미스가 발생하기 된다. 문맥 교환이 빈번하다면 이는 성능에 큰 부담이다.
이를 개선하기 위해 몇몇 시스템에서 문맥 교환이 발생하더라도 TLB의 내용을 보존할 수 있는 하드웨어 기능을 추가하였다. TLB 내에 주소 공간 식별자(address space identifier, ASID) 필드를 추가하는 것이 그것이다. ASID는 프로세스 식별자(process identifier, PID)와 유사하지만, 좀 더 적은 비트를 가지고 있다.
위 사진은 ASID 필드를 추가한 TLB의 예시이다.
ASID를 사용할 경우, 프로세스 별로 TLB 변환 정보를 구분할 수 있다. 올바른 주소 변환을 위해서 하드웨어는 현재 어떤 프로세스가 실행 중인지 파악하고 있어야 한다. 이를 위해 문맥 교환 시 운영체제는 새로운 ASID 값을 정해진 레지스터에 탑재해야 한다.
추가적으로 TLB의 두 항목이 동일한 페이지를 가리키는 경우를 생각해 볼 수 있다. 두 개의 프로세스들이 코드 페이지와 같은 하나의 페이지를 공유하고 있을 때 발생할 수 있다. 코드 페이지를 공유하는 것은 사용되는 물리 페이지의 수를 줄일 수 있기 때문에 유용하고, 메모리 부하도 줄일 수 있다.
이슈 : 교체 정책
모든 캐시가 그러하듯이 TLB에서도 캐시 교체(cache replacement) 정책이 매우 중요하다. TLB에서 새로운 항목을 탑재할 때, 현재 존재하는 항목 중 하나를 교체 대상으로 선정해야 한다.
TLB에 새로운 항목을 추가할 때 어떤 항목을 교체해야 할까? 목표는 미스율을 줄이거나 히트 비율을 증가시켜 성능을 개선하는 것이다.
디스크와 메모리 간의 페이지 스와핑 부분에서 자세하게 다루기 때문에 몇 개의 일반적인 정책들만 알아보자.
최저 사용 빈도(least recently used, LRU) 항목을 교체하는 것은 가장 흔한 방법이다. LRU는 메모리 참조 패턴에서의 지역성을 최대한 활용하는 것이 목적이다. 사용되지 않은지 오래된 항목일수록, 앞으로도 사용될 가능성이 작으며, 교체 대상으로 적합하다는 가정에 근거한다.
다른 일반적인 방법은 랜덤 정책이다. 무작위로 교체 대상을 선택하고 때때로 잘못된 결정을 내릴 수도 있다. 하지만, 구현이 간단하고 예상치 못한 예외 상황의 발생을 피할 수 있다는 장점이 있다.
요약
지금까지 주소 변환을 더 빠르게 처리하기 위한 하드웨어 기법인 TLB(Translation Lookaside Buffer)에 대해 알아보았다. 칩 상의 작은 전용 TLB를 주소 변환 캐시로 사용하여 대부분의 메모리 참조들은 메인 메모리 상의 페이지 테이블을 읽지 않고도 처리가 가능하게 되었다.
TLB의 사용으로 일반적인 경우에 프로그램은 메모리 가상화 기능이 없는 것과 동일한 성능을 보일 것이기 때문에 TLB는 운영 체제 입장에서 훌륭한 성과일 뿐만 아니라 현대 시스템에서 페이징을 사용하기 위한 필수 요소이다.
하지만 TLB가 모든 프로그램에서 항상 제대로 작동하는 것은 아니다. 특히, 프로그램이 짧은 시간 동안 접근하는 페이지들의 수가 TLB에 들어갈 수 있는 수보다 많다면 그 프로그램은 많은 수의 TLB 미스를 발생할 것이고 느리게 동작할 것이다. 이러한 현상을 TLB 범위(TLB coverage)를 벗어난다고 한다.
다음 장에서 다룰 한가지 해법은 더 큰 페이지 크기를 지원하도록 하는 것이다. 큰 페이지들을 위한 지원은 데이터베이스 관리 시스템(database management system, DBMS)과 같은 프로그램에서 주로 사용되며, 이러한 프로그램의 자료 구조들은 클 뿐만 아니라 임의적으로 접근된다.
참고