가상화 - 메모리 가상화 : 더 빠른 변환을 위한 TLB

페이징은 주소 공간을 작은 크기(페이지)로 나누고 각 페이지의 실제 위치(매핑 정보)를 메모리에 저장하는 기법이다.

이때, 매핑 정보를 저장하는 자료 구조를 페이지 테이블이라 하며, 큰 메모리 공간을 요구한다. 

그런데 더욱 문제가 되는 것은 가상 주소에서 물리 주소로의 주소 변환을 위해 메모리에 존재하는 매핑 정보를 읽어야 한다는 사실이다.

페이지 테이블 접근을 위한 메모리 읽기 작업은 엄청난 성능 저하를 유발한다.

 

운영체제의 실행 속도를 개선하려면 도움이 필요하다. 대부분의 경우 하드웨어로부터 도움을 받는다.

주소 변환을 빠르게 하기 위해서 메모리 관리부(MMU)의 변환 색인 버퍼(TLB, Translation Lookaside Buffer)를 이용할 수 있다.

TLB는 자주 참조되는 가상 주소-실제 주소 변환 정보를 저장하는 하드웨어 캐시이다.

가상 메모리 참조 시 하드웨어는 TLB에 원하는 변환 정보가 있는지를 먼저 확인한다.

만약 있다면 모든 변환 정보를 갖고 있는 페이지 테이블을 통하지 않고 변환을 빠르게 수행한다.

TLB의 기본 알고리즘

상기의 알고리즘은 아래와 같이 동작한다.

먼저, 가상 주소에서 가상 페이지 번호(VPN)를 추출한 후, TLB에서 해당 VPN의 존재 여부를 검사한다.

만약 존재하면, TLB가 변환 정보를 갖고 있다는 의미이다(TLB 히트).

이후, 해당 TLB 항목에서 페이지 프레임 번호(PFN)를 추출하고, 해당 페이지에 대한 접근 권한 검사를 진행한다.

검사가 성공하면, 페이지 프레임 번호와 가상 주소의 오프셋을결합하여 물리 주소를 구성하고, 메모리에 접근한다.

TLB에 변환 정보가 존재하지 않는다면(TLB 미스), 변환 정보를 찾기 위해 메모리에 접근한다.

메모리 참조가 유효하고, 접근 가능하다면 해당 변환 정보를 TLB로 읽어 들인다. TLB가 갱신되면 하드웨어는 명령어를 재실행한다.

TLB 미스는 누가 처리할까?

TLB 미스는 하드웨어 혹은 소프트웨어로 처리될 수 있다.

TLB 미스를 하드웨어로 처리하기 위해서는 하드웨어가 페이지 테이블에 대한 명확한 정보를 가지고 있어야 한다.

하드웨어는 페이지 테이블 베이스 레지스터를 통해 페이지 테이블의 메모리 상 위치와 정확한 형식을 파악해야 한다.

미스 발생 시, 하드웨어는 페이지 테이블에서 원하는 페이지 테이블 엔트리를 찾고 필요한 변환 정보를 추출하여 TLB를 갱신한다.

이후, TLB 미스가 발생한 명령어를 재실행한다. 인텔 x86 CPU가 하드웨어로 관리되는 TLB의 대표적인 예이며, 

CR3 레지스터가 페이지 테이블 주소를 갖고 있으며, 멀티 레벨 페이지 테이블을 사용한다. 

 

TLB 미스를 소프트웨어로 처리하는 과정은 다음과 같다. TLB에서 주소를 찾는 것이 실패하면, 하드웨어는 예외 시그널을 발생시킨다.

예외 시그널을 받은 운영체제는 명령어 실행을 잠정 중단하고, 실행 모드를 커널 모드로 변경하여 커널 코드 실행을 준비한다.

실행 모드를 커널 모드로 변경하는 작업의 핵심은 특권 레벨을상향 조정하여 커널 주소 공간에 접근할 수 있도록 하는 것이다.

커널 모드로 변경이 되면 트랩 핸들러를 실행한다. 이때 실행되는 트랩 핸들러는 TLB 미스의 처리를 담당하는 운영체제 코드이다. 

이 트랩 핸들러는 페이지 테이블을 검색하여 변환 정보를 찾고 TLB 접근이 가능한 특권 명령어를 사용하여 TLB를 갱신한 후에 리턴한다.

트랩 핸들러에서 리턴되면 하드웨어가 명령어를 재실행한다. 

TLB의 구성

일반적인 TLB는 32, 64, 128개의 엔트리를 가지며 완전 연관 방식으로 설계된다.

완전 연관 방식에서 변환 정보는 TLB 내에 어디든 위치할 수 있으며, 원하는 변환 정보를 찾는 검색은 TLB 전체에서 병렬적으로 수행된다.

TLB 항목의 구성은 아래와 같다. VPN, PFN과 더불어 다른 비트들이 존재한다.

TLB에서의 Valid Bit와 페이지 테이블에서의 Valid Bit는 다르다. 페이지 테이블에서 어떤 페이지 테이블 항목이 Invalid 하다면, 

해당 페이지는 할당되지 않았음을 의미한다. 정상적인 프로그램은 해당 페이지를 접근하지 않으며, 유효하지 않은 페이지를 접근할 경우,

운영체제는 트랩을 발생시킨다. 반면에, TLB의 Valid Bit는 TLB에 탑재되어 있는 해당 변환 정보가 유효한지를 나타내기 위해 사용된다.

예를 들어, 시스템이 시작되면 어떤 변환 정보도 아직 캐시되지 않았기 때문에 TLB의 모든 항목은 Invalid로 초기화되어 있다.

프로그램들이 실행을 시작하여 자신의 가상 주소 공간을 접근하게 되면, TLB가서서히 채워지면서 Valid로 바뀐다.

TLB의 Valid Bit는 문맥 전환 시에도 상당히 유용하다. 문맥 전환 시, 시스템은 모든 TLB 항목을 Invalid로 세팅하여, 

새로운 프로세스가 이전 프로세스의 변환 정보를 사용하는 것을 원천적으로 차단한다.

TLB의 문제

TLB에 있는 가상 주소와 실제 주소 간의 변환 정보는 그것을 탑재시킨 프로세스에서만 유효하다. 

문맥 전환시 새로운 프로세스에서는 이전에 실행하던 프로세스의 변환 정보를 사용하지 않도록 주의해야 한다.

이 문제는 여러 가지 해법이 있을 수 있다. 한 방법은 문맥 전환을 수행할 때 기존 TLB 내용을 비우는 것이다.

비우는 작업은 모든 Valid Bit을 0으로 설정하면 된다. 그런데 문맥 전환 시마다 TLB를 비우는 것은 결코 공짜가 아니다.

매번 새롭게 TLB를 채워야하고 그때마다 TLB 미스가 발생한다. 문맥 전환이 빈번하게 발생한다면 성능에 큰 부담을 가져올 수 있다.

이 부담을 개선하기 위해 몇몇 시스템에서는 문맥 전환이 발생하더라도 TLB 내용을 보존할 수 있는 하드웨어 기능을 추가하였다.

TLB내에 아래와 같이 주소 공간 식별자(ASID, Address Space Identifer) 필드를 추가하는 것이다.

이를 사용하면 프로세스 별로 TLB 변환 정보를 구분할 수 있다.

교체 정책

모든 캐시가 그러하듯이 TLB에서도 캐시 교체 정책이 매우 중요하다.

TLB에 새로운 항목을 탑재할 때, 현재 존재하는 항목 중 하나를 교체 대상으로 선정해야 하는 경우가 발생할 수 있다.

이때 어느 것을 선택해야 할까? 목표는 미스율을 줄여 성능을 개선하는 것이다.

한 가지 흔한 방법은 가장 오래 전부터 사용되었던 최저 사용 빈도(LRU, Least Recently Used) 항목을 교체하는 것이다.

사용된지 오래된 항목일수록, 앞으로 사용될 가능성이 작으며 교체 대상으로 적합하다는 가정에 근거한다.

또 다른 일반적인 방법은 교체 대상을 무작위로 정하는 랜덤 정책이다. 

요약

지금까지 주소 변환을 더 빠르게 처리하기 위해 TLB라는 하드웨어 캐시를 이용하는 방법을 살펴보았다.

캐싱은 컴퓨터 시스템에서 사용되는 가장 근본적인 성능 개선 기술들 중 하나이다.

하드웨어 캐시 사용의 근본 취지는 명령과 데이터 참조에 있어서 지역성을 활용하는 것이다.

일반적으로 지역성에는 두 가지가 있다. 시간 지역성과 공간 지역성이 그것이다. 

시간 지역성은 최근에 접근된 명령어 또는 데이터는 곧 다시 접근될 확률이 높다는 사실에 근거한다.

공간 지역성은 프로그램이 메모리 주소 x를 읽거나 쓰면 x와 인접한 메모리 주소를 접근할 확률이 높다는 사실에 근거한다.

모든 하드웨어 캐시의 목적은 필요한 메모리 내용을 매우 빠른 CPU 칩 내의 메모리에 위치시키고, 지역성을 최대한 활용하는 것이다.

 

그런데 TLB가 모든 프로그램에서 항상 제대로 동작하는 것은 아니다.

프로그램이 짧은 시간 동안 접근하는 페이지들의 수가 TLB에 들어갈 수 있는 수보다 많다면 많은 수의 TLB 미스가 발생할 것이다.

사실 TLB는 현대 시스템에서 페이징을 사용하기 위한 필수 요소이다. 

일반적인 경우 페이지는 4KB이다. 페이지 크기는 TLB의 효용성에 매우 중요한 역할을 한다.

페이지 크기가 늘어나면 TLB 미스 횟수는 줄어들 수 있다.