운영체제 11 - Faster Translations(TLBs) [Memory Virtualization]

Faster Translations(TLBs)

Paging은 상당한 성능 저하를 가져올 수 있다.
↑은 프로세스 주소 공간을 작은 고정된 크기, page로 나누고 각 page의 실제 위치(mapping information)을 메모리에 저장한다. 그리고 mapping information을 저장하는 자료구조를 page table이라 한다.
mapping intormaion을 저장을 위해 큰 memroy space를 요구된다.

---

Address-translation cashe(Translation-lookaside buffer)

TLB는 Memory-management unit, MMU의 일부이다. 자주 참조되는 가상 주소-실주소 변환정보를 저장하는 하드웨어 캐시이다. address-translation chase가 좀 더 적합한 명칭이다.

요즘날엔 MMU와 TLB는 CPU안에 존재한다.

[운영체제] MMU, page table, inverted page table, TLB

MMU와 TLB에 더 자세한 내용

가상 메모리 참조 시

1. 하드웨어는 먼저 TLB에 원하는 정보가 있는지 확인한다.
2. 만약 있다면 page table을 통하지 않고 변환을 (빠르게) 수행한다.
3. 없다면 조금 힘들어진다.

TLB Basic Algorithm

---

TLB: Address Translation 과정에서 VPN을 PFN으로 변환하려면 Page Table에 접근하여야 한다.
이 과정을 더 빠르게 하기 위해 자주 쓰이는 Translation들을 Memory Management Unit(MMU)에 저장하여 사용하는데 이렇게 저장한 Cache를 TLB라 한다.

위 코드는 Linear page table, 하드웨어로 관리되는 TLB로 구성되어 있다.

기본 알고리즘 정리:

1. Translation 요청이 들어오면 주소값에서 VPN을 추출한다.
2. 해당하는 Translation이 TLB에 있는 지 확인한다.
   3-1. TLB에 있다면 VPN을 PFN으로 변환하여 반환한다. (TLB Hit)
   3-2. TLB에 없다면 Page Table에 접근하여 PFN으로 변환하여 반환한다. (TLB Miss)
   그 후 해당 Translation을 TLB에 업데이트한다

---

Example: Accessing An Array

배열의 원소의 합을 구하는 예제

int sum = 0;
for(i=0; i<10; i++) sum += a[i];

위 코드는 총 10번의 translation이 발생한다. 하지만 이 때 a[0], a[3],a[7]에서는 TLB Miss가 발생하여 Page Table에서 변환해야하지만 나머지 7번의 접근, 즉 전체 Translation 중 70%에서는 TLB Hit가 발생하여 시간 절약이 가능하다. 이는 배열이 연속된 주소 공간에 있기 때문에 가능하다. 이를
Spatial locality(공간 지역성이라 한다.)

• 풀어쓴 내용
• a[0]은 가상주소 100번이다.→ 하드웨어는 VPN을 추출한다.→ VPN은 06이고, 이 때 TLB는 완전 초기화되어있기때문에(처음이라) TLB MISS가 뜬다. → 그 이후 VPN 06에 대한 Physical page number를 찾아 TLB를 검색한다. →이후 a[1],a[2]는 VPN 06과 같은 page이므로 TLB HIT가 뜬다.
  아래 3-9도 똑같다

배열 원소를 읽는 TLB 동작 중 HIT는 70%였고, 배열이 처음으로 접근되었지만 TLB는 공간 지역성(spatial locality)으로 인해 성능을 개선할 수 있다. (배열의 항목들이 page 내에 서로 인접해 있었기 때문)
page의 크기는 TLB 효용성에 매우 중요한 역할을 한다. PAGE 크기가 두배가 된다면 MISS 횟수가 더 줄어든다. 예제 프로그램이 루프 종료 후에도 배열을 사용한다면. TLB가 모든 주소 변환 정보를 저장할 정도로 크다면, 다 HIT가 뜬다. 이 경우 시간 지역성(temporal locality)로 인해 TLB 히트율이 높아진다.

실제로 많은 프로그램들이 공간 지역성(spatial locality), 시간지역성(temporal locality)을 띄고 있다.

※Spatial Locality: 프로그램이 메모리 x에 접근했다면, 다음번에는 x 근처의 메모리에 접근할 가능성이 높다
※Temporal Locality: 프로그램이 접근했던 메모리는 가까운 시간 내에 다시 접근할 가능성이 높다.

---

캐싱은 컴퓨터 시스템에서 사용되는 가장 근본적인 성능 개선 기술들 중 하나.
일반적인 경우를 빠르게(make the common case fast)하기 위해 오랜 시간 적용된 방법이다.
하드웨어 캐시 사용의 근본 취지는 명령과 데이터 참조에 있어서 locality을 활용하는 것이다. 일반적으로 지역성에는 두가지가 있다. temporal locality, spatial locality다!!!
temporal locality은 최근에 접근된 명령어 또는 데이터는 곧 다시 접근될 확률이 높다는 사실에 근거한다. for, while 등 반복문을 생각해보자.
spatial locality은 메모리 주소 x를 읽거나 쓰면, x와 인접한 메모리 주소를 접근할 확률이 높다는 사실에 근거한다. 배열을 순차적으로 읽는 프로그램이 spatial locality을 가지는 대표적인 예다.

모든 하드웨어 캐시의 목적은 필요한 메모리 내용을 매우 빠른CPU칩 내의 메모리에위치시키고, 접근 지역성을 최대한 활용하는 것이다. 이 원리는 명령어 캐시, 데이터캐시, 그리고 주소 변환 캐시 등(TLB)모든 하드웨어 캐시에 적용된다,CPU가 메모리내용을 참조할 때, (느린) 메모리를 직접 접근하는 것이 아니라, 우선 캐시에 사본이있는지 먼저 확인한다. 만약 캐시에 원하는 내용이 존재하면 프로세서는 원하는 내용을빠르게 접근할 수 있으며(즉, 몇CPU사이클 내에), 메모리를 접근하기 위해 비싼 시간(수nsec)을 쓰지 않아도 된다

그럼 캐시를 크게 만들면 되지 않을까? 크게 만들면 느려진다. 작으면 크기가 작다. 밸런스가 맞아야 빠르다!

Who Handles the TLB Miss?

---

TLB Miss 처리는 두가지 방법이 있다. 하드웨어, 소프트웨어.

Hardware-managed TLB(CISC)

하드웨어가 페이지 테이블에 대한 명확한 정보를 가지고 있어야한다. 메모리 상 위치(위 코드의 page-table base register를 통해서)와 정확한 형식을 파악하고 있어야한다.

Miss 발생 시 다음과 같은 일을 한다.

1. Page Table에서 PTE를 찾는다.
2. 필요한 변환 정보를 추출한다.
3. TLB로 갱신한 한다.
4. TLB 미스가 발생한 명령어를 재실행한다.

인텔 x86 CPU가 하드웨어로 관리되는 TLB의 대표적인 예다.
x86 CPU는 multi-level page table을 사용한다.

▪CIRS = complex-instruction set computers

Software-managed TLB(RISC)

1. 하드웨어가 예외(exception) 시그널 발생시킨다. 위 코드 11번째 줄
2. 예외 시그널을 받은 운영체제는 명령어 실행 잠정 중지하고, 실행 모드를 변경하여, 커널 모드로 변경하여 커널 코드 실행을 준비한다.

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

3. 커널 모드로 변경이 되면 Trap handler를 실행한다.
   이때 실행되는 Trap handler는 TLB 미스의 처리를 담당하는 운영체제 코드이다.
4. 트랩 핸들러는 페이지 테이블을 검색하여 변환 정보를 찾고, TLB 접근이 가능한 privileged instruction를 사용하여 TLB를 갱신한 후에 리턴한다.
5. Trap handler에서 리턴되면 하드웨어가 명령어를 실행한다.
6. Trap handler가 TLB를 갱신했으므로 이제는 TLB HIT가 날 것이다.

▪RISC = reduced instruction set computing

두 가지 중요한 사항을 다시 짚어보자.
첫 번째, TLB 미스를 처리하는 트랩 핸들러는 시스템 콜 호출시 사용되는 트랩 핸들러와의 차이가 있다.

System call의 호출의 경우는 Trap handler에서 리턴 후 System Call을 호출한 명령어의 "다음"명령어를 실행한다. 일반적인 프로시저 콜과 동일하다.
TLB의 경우는 다르다. TLB 미스 처리의 경우, Trap에서 리턴하면 Trap을 발생시킨 명령을 "다시" 실행해야하며, 재실행 시에는 TLB에서 히트가 발생한다. 트랩이 발생하면 운영체제는 트랩핸들러가 종료되었을 때 다시 실행을 계속할 명령어 주소(Program Counter 값)를 저장한다.
중요한 사실을 알 수 있다. 운영체제는 트랩 발생의 원인에 따라 현재 명령어의 PC값 혹은 다음 명령어의 PC값을 저장해야한다.

두 번째, TLB 미스 핸들러를 실행할 때, TLB 미스가 무한 반복되지 않도록 주의를 해야 한다. TLB 미스 핸들러를 접근하는 과정에서 TLB 미스가 발생하는 상황이다. 이를 위해 다양한 해법이 존재한다.

1. TLB 미스 핸들러를 물리 메모리에 위치 시키는 것도 한 방법이다. TLB 미스 핸들러의 주소는 '물리' 주소로 표시된다. 이 경우 해당 TLB 미스 핸들러는 unmap되어 있으며 주소 변환이 필요없다.
2. TLB의 일부를 핸들러 코드 주소를 저장하는 데 영구히 할당하는 것이다. 이렇게 되면 TLB 핸들러는 항상 TLB에서 히트된다. 이를 연결(wired) 변환이라 한다.

TLB를 소프트웨어로 관리하는 방식의 주된 장점은 유연성이다. 운영체제는 하드웨어 변경없이 페이지 테이블 구조를 자유로이 변경할 수 있다.

또 다른 장점은 단순함이다. TLB 제어 흐름에서 보는 것과 같이 미스가 발생하였을 때 하드웨어는 별로 할 일이 없다. 예외가 발생하면 운영체제의 TLB 미스 핸들러가 나머지 일을 처리한다.

---

TLB 구성

일반적인 TLB는 32, 64,128개의 entry를 가지며 fully associative 방식으로 설계된다. fully associative 방식에서 변환정보는 TLB 내에 어디든 위치할 수 있으며, 원하는 변환 정보를 찾는 검색은 TLB 전체에서 병렬적으로 수행된다.

TLB의 Entry는 PTE와 비슷하지만 VPN이 index 역할을 할 수 없기 때문에 VPN이 같이 저장되어야 한다. 그리고 뒤 쪽에는 PTE처럼 vaild, protection bit와 같은 flag들이 저장된다.

🔲TLB는 용량이 작기 때문에 여러 프로세스가 나누어 사용해야 하므로 Context Swich가 발생하면 기존에 남아있는 TLB Entry들 때문에 다른 프로세스가 엉뚱한 메모리로 접근하는 것을 막을 방법이 필요하다. → 이를 막기 위해 Context Switch 시마다 TLB를 비우면 되지만 이는 매우 비효율적인 방법이다.

---

Smashicons 디자인의 무료 벡터 아이콘