[OSTEP] 가상화 CH19 페이징 - 더 빠른 변환 TLB

CH19 페이징 - 더 빠른 변환 TLB 

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

이 페이지 테이블을 저장하고 관리하기 위해 상당한 메모리 공간이 필요하고,

주소 변환을 위해 매번 메모리에서 페이지 테이블을 참조해야 하기 때문에, 페이징은 성능 저하를 유발할 수 있다 

핵심 질문 - 주소 변환 속도를 어떻게 향상할까
주소 변환을 어떻게 빨리할 수 있을까? 페이징에서 발생하는 추가 메모리 참조를 어떻게 피할 수 있을까? 어떤 하드웨어가 필요할까? 운영체제가 어떤 식으로 개입해야 할까? 

운영체제의 실행 속도를 개선하기 위해서 대부분의 경우 하드웨어로부터 도움을 받는다 

변환-색인 버퍼 Translation-Lookaside Buffer, TLB 는 자주 참조되는 가상 주소 - 실주소 변환 정보를 저장하는 하드웨어 캐시이다 

TLB 는 주소-변환 캐시 Address-Translation Cache 가 더 정확한 명칭이며, 칩의 메모리 관리부 Memory-Management Unit ,MMU 의 일부이다 

 

가상 메모리 참조 시, 1) 하드웨어는 먼저 TLB 에 원하는 변환 정보가 있는지를 확인하고 

2) 만약 있다면 페이지 테이블을 통하지 않고 변환을 빠르게 수행한다 

19.1 TLB의 기본 알고리즘 

주소 변환부가 단순 선형 페이지 테이블 Linear Page Table 이라고 가정했을 때 하드웨어의 알고리즘은 아래와 같다 

1) 가상 주소에서 가상 페이지 번호 Virtual Page Num, VPN 을 추출한다 

2) 해당 VPN 의 TLB 존재 여부를 검사한다

3) 만약 존재하면 TLB 히트! TLB가 변환 값을 갖고 있다는 뜻이다

4) 해당 TLB 항목에서 페이지 프레임 번호 Page Frame Number, PFN 을 추출한다

5) 해당 페이지에 대한 접근 권한 검사가 성공하면

6) 그 정보를 원래 가상 주소의 오프셋과 합쳐서 원하는 물리 주소 PA 를 구성하고 

메모리에 접근할 수 있다!

 

하지만 TLB에 뱐환 정보가 존재하지 않는다면 (TLB 미스) 할 일이 많다 

1) 하드웨어가 변환 정보를 찾기 위해 페이지 테이블에 접근하고

2) 프로세스가 생성한 가상 메모리 참조가 유효하고 접근 가능하다면

3) 해당 변환 정보를 TLB로 읽어 들인다 - 페이지 테이블 접근을 위한 메모리 참조 때문에 시간이 매우 많이 소요되는 작업이다 

4) TLB가 갱신되면 하드웨어는 명령어를 재실행한다 - 갱신되면 TLB에 변환 정보가 존재하기 때문에 메모리 참조가 빠르게 처리된다 

🐣 결론은 TLB 미스가 많이 발생할수록 메모리 접근 횟수가 많아지고, 페이징 비용이 커진다 

19.2 배열 접근 

가상 주소 트레이스가 10개의 4바이트 크기의 정수 배열이라고 가정하면 첫번째 배열의 항목에 접근할 때 TLB가 비어 있기 때문에 TLB 미스가 발생하고, 하드웨어는 페이지 테이블을 참고하여 가상 페이지를 물리 메모리에 매핑하여 TLB를 갱신한다

배열의 항목들이 페이지 내에서 서로 인접해 있기 때문에, 페이지에서 첫번째 항목을 접근할 때만 TLB 미스가 발생한다 

이후에는 공간 지역성 Spartial Locality 으로 인해서 추가적인 TLB 미스 없이 빠르게 접근할 수 있다 

 

또한 TLB 성능은 아래 요인들에 의해 영향을 받을 수 있다 

1) 페이지 크기가 커지면 TLB 미스 횟수가 더 줄어든다 

2) 정수 배열을 연속적으로 접근하는 경우도 TLB 성능이 개선된다 

3) 루프 종료 후에도 배열을 사용한다면 성능은 더욱 개선될 것이다 - 모든 주소 변환 정보가 TLB에 탑재되어 있기 때문

4) TLB가 모든 주소 변환 정보를 저장할 정도로 충분히 크다면 시간 지역성 Temporal Locality 으로 인해 TLB 히트율이 높아진다 

시간 지역성 Temporal Locality 최근에 접근된 명령어 또는 데이터는 곧 다시 접근될 확률이 높다 
공간 지역성 Spatial Locality 프로그램이 메모리 주소 x 를 읽거나 쓰면, x 와 인접한 메모리 주소를 접근할 확률이 높다 
ex. 시간 지역성 - for 나 while 등의 반복문/ 공간 지역성 - 배열을 순차적으로 읽는 프로그램 
모든 하드웨어 캐시의 목적은 필요한 메모리 내용을 매우 빠른 CPU 칩 내의 메모리에 위치시키고,
접근 지역성을 최대한 활용하는 것이다, 캐시의 용량을 키우는 것을 불가하니 "작은" 캐시를 "잘" 사용해야 한다 

19.3 TLB 미스는 누가 처리할까 

첫번째 방법, 과거 하드웨어는 CISC Complex-Instruction Set Computers 라는 복잡한 명령어들도 구성되어 있었고

TLB 미스를 하드웨어가 처리하도록 설계했기 때문에 하드웨어가 페이지 테이블에 대한 명확한 정보를 가지고 있어야 했다 

미스 발생 시 하드웨어는 1) 페이지 테이블에서 원하는 페이지 테이블 엔트리를 찾고 2) 필요한 변환 정보를 추출하여 3) TLB를 갱신한 후 4) TLB 미스가 발생한 명령어를 재실행했다 

두번째 방법, RISC Reduced Instruction Set Computing 기반 컴퓨터는 소프트웨어 관리 TLB Software-Managed TLB를 사용한다

TLB에서 주소 찾는 것이 실패하면 1) 하드웨어는 예외 Exception 시그널을 발생시킨다 2) 운영체제는 명령어 실행을 잠정 중지하고 3) 실행 모드를 커널 모드로 변경하여 커널 코드 실행을 준비한다 4) 커널 모드로 변경되면 트랩 핸들러 Trap Handler 를 실행한다 

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

 

여기서 중요한 사항 두 가지가 있다

1) TLB 미스를 처리하는 트랩 핸들러는 시스템 콜 호출의 트랩 핸들러와는 다르다

시스템 콜 호출의 경우는 시스템 콜을 호출한 명령어의 "다음" 명령어를 실행하고

TLB 미스의 경우는 트랩을 발생시킨 명령을 "다시" 실행해야 한다 

운영체제는 트랩 발생 원인에 따라 현재 명령어의 PC 값 혹은 다음 명령어의 PC 값을 저장해야 한다

2) TLB 미스 핸들러를 실행할 때, TLB 미스가 무한 반복되지 않도록 주의해야 한다 

한 가지 예방법은 TLB 미스 핸들러를 물리 메모리에 위치시킨다 (주소 변환이 필요 없다)

다른 예방법은 TLB의 일부를 핸들러 코드 주소를 저장하는 데 영구히 할당하는 것이다 (연결 Wired 변환) 

🐣 2-1) TLB 미스 핸들러 자체도 가상 메모리 주소를 사용하기 때문에, 물리 메모리에 위치하게 하면, TLB 를 사용할 필요 없이 핸들러가 실행되므로 TLB 미스가 발생하지 않는다 2-2) Wired TLB는 주소 변환을 빠르게 할 수 있도록 도와주는 TLB의 특정 슬롯을 "고정"시킨다

 

TLB를 소프트웨어로 관리하는 방식의 주된 장점은 아래 두 가지이다 

1) 유연성 - 운영체제는 하드웨어 변경 없이 페이지 테이블 구조를 자유로이 변경할 수 있다 

2) 단순함 - 미스가 발생하였을 때 하드웨어는 단지 예외를 일으키고 운영체제의 TLB 미스 핸들러가 나머지 일을 처리한다 

19.4 TLB 의 구성 - 무엇이 있나?

하드웨어 TLB 는 32, 64, 128개의 엔트리를 가지며 완전 연관 Fully Associative 방식으로 설계된다 

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

/* TLB 의 구성 */
VPN | PFN | 다른비트들 

TLB 에 VPN 과 PFN 말고 다른 비트들도 있다 

1) Valid bit - 특정 항목이 유효한 변환 정보를 가지고 있는지 여부 

🐣 Page Table 의 Valid bit 는 할당 여부를 나타내고, TLB 의 Valid bit 는 해당 변환 정보의 유효 여부를 나타낸다 🐣

2) Protection bit - 페이지가 어떻게 접근될 수 있는지 (페이지 테이블의 쓰임새와 같음)

3) 주소 공간 식별자 Address-Space Identifier

4) 더티 비트 Dirty bit 

19.5 TLB 의 문제 - 문맥 교환 

TLB에 있는 가상 주소와 실제 주소 간의 변환 정보는 그 프로세스에서만 유효하기 때문에

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

핵심 질문 - 문맥 교환 시 TLB 내용을 어떻게 관리하는가
문맥 교환 시 실행될 프로세스에게는 이전 프로세스가 사용한 TLB 정보는 의미가 없다
하드웨어 또는 운영체제는 이러한 문제를 해결하기 위해 무엇을 해야 하는가? 

1) 기존 TLB 내용을 비우는 것 

잘못된 변환 정보를 사용하는 상황을 방지할 수 있다는 장점이 있지만

새로운 프로세스가 실행될 때 데이터와 코드 페이지에 대한 접근으로 TLB 미스가 발생한다는 단점이 있다 

2) TLB 내에 주소 공간 식별자 Address Space Identifier, ASID 필드를 추가하는 것 

ASID 는 프로세스 식별자 Process Identifier 와 대략적으로 유사하지만 비트가 적다 (ASID 8bit, PID 32bit)

ASID 로 프로세스 별로 TLB 변환 정보를 구분하고, 문맥 전환 시 새로운 AISD 값을 정해진 레지스터에 탑재한다 

19.6 이슈 - 교체 정책 

TLB에 새로운 항목을 탑재할 때, 현재 존재하는 항목 중 하나를 교체 대상으로 선정해야 한다 

핵심 질문 - TLB 교체 정책은 어떻게 설계하는가
TLB 에 새로운 항목을 추가할 때 어떤 항목을 교체해야 할까?
목표는 미스율을 줄여 (or 히트 비율을 증가시켜서) 성능을 개선하는 것이다 

1) 최저 사용 빈도 Least-Recently-Used, LRR 항목을 교체하는 것

사용된지 오래된 항목일수록, 앞으로 사용될 가능성이 적어 교체 대상으로 적합할 수 있다 

2) 랜덤 Random 정책 

때때로 잘못된 결정을 내릴 수도 있지만, 의외로 예상치 못한 예외 상황의 발생을 피할 수 있다 

19.7 실제 TLB 

이렇게 생겼다 

 

실제 TLB: MIPS R4000

• 주소 공간의 반은 커널이 사용하기 때문에, 사용자에게 할당되는 공간도 전체의 반이다. 그래서 32비트 주소 공간에서 페이지 비트 수는 20이 아닌 19가 된다.
• **전역 비트(G)**는 프로세스들이 공유하는 페이지를 나타내며, G가 설정되어 있으면 식별자 ASID값은 무시된다.
• ASID 필드를 보고 OS가 주소공간을 서로 구분한다.
• dirty bit는 페이지의 수정 여부를 나타내며, valid bit는 페이지의 적재 여부를 나타낸다.
• page mask field는 여러 개의 페이지 크기를 지원할 때 사용된다.
• TLB 또한 운영체제를 위해서 몇 개의 공간들이 예약되어 있다. ↓(예: TLB 미스 핸들러) 운영체제는 TLB 미스가 나서는 안되는 코드와 데이터를 위해서 이 공간을 활용한다.
• MIPS R4000은 소프트웨어 기반 TLB이기에 시스템 명령어를 지원해야 하는데, 이 모든 명령어들은 **‘실행 권한 privileged’**를 가져야 한다.
• RAM은 어느 데이터에 접근하든 같은 속도로 접근할 수 있기에 Random Access Memory 이지만, 사실 TLB에 캐싱되어 있지 않은 메모리에 접근하는 시간과 TLB에 캐싱되어 있는 메모리에 접근하는 시간은 다를 수 밖에 없다. 따라서 RAM은 항상 RAM이 아니다.

19.8 요약

TLB는 페이징을 사용하기 위한 필수 요소이지만, 모든 프로그램에서 항상 제대로 동작하는 것은 아니다 

CPU 파이프라인에서 물리적으로 인덱스된 캐시 Physically-indexed cache 가 사용될 때 TLB 접근은 병목이 될 수 있고,

가상적으로 인덱스된 캐시 Virtually Indexed Cache 는 일부 성능 문제를 해결하지만 새로운 하드웨어 설계 문제들을 수반한다