Operating Systems : Three Easy Pieces를 보고 번역 및 정리한 내용들입니다.

페이징은 주소 공간을 작고 고정된 사이즈의 단위로 나누기 때문에 많은 양의 매핑 정보를 필요로 한다. 매핑 정보는 보통 물리 메모리에 저장되기 때문에, 페이징은 논리적으로 프로그램에 의해 만들어진 주소를 찾기 위한 추가적인 메모리를 필요로 한다. 명령어를 가져오거나, 데이터를 로드 및 저장할 때마다 주소 변환 정보를 찾기 위해 메모리에 접근하는 것은 비효율적이다.

어떻게 주소 변환의 속도를 높이고, 페이징이 필요하는 추가적인 메모리 참조를 피할 수 있을까?

주소 변환의 속도를 높이기 위해서는 변환 색인 버퍼(translation lookaside buffer, TLB)라 부르는 추가적인 하드웨어를 사용한다. TLB는 MMU의 부분으로, 자주 쓰이는 가상-물리 주소 변환을 위한 하드웨어 캐시다. 가상 메모리 참조가 일어나면, 하드웨어는 이제 원하는 변환이 TLB에 있는지를 먼저 확인하고, 만약에 있다면 메모리의 페이지 테이블에 접근하지 않고 변환을 빠르게 수행한다.

VPN = (VirtualAddress & VPN_MASK) >> SHIFT
(Success, TlbEntry) = TLB_Lookup(VPN)
if (Success == True) // TLB Hit
	if (CanAccess(TlbEntry.ProtectBits) == True)
		Offset = VirtualAddress & OFFSET_MASK
		PhysAddr = (TlbEntry.PFN << SHIFT) | Offset
		Register = AccessMemory(PhysAddr)
	else
		RaiseException(PROTECTION_FAULT)
else                 // TLB Miss
	PTEAddr = PTBR + (VPN * sizeof(PTE))
	PTE = AccessMemory(PTEAddr)
	if (PTE.Valid == False)
		RaiseException(SEGMENTATION_FAULT)
	else if (CanAccess(PTE.ProtectBits) == False)
		RaiseException(PROTECTION_FAULT)
	else
		TLB_Insert(VPN, PTE.PFN, PTE.ProtectBits)
		RetryInstruction()

1. TLB Basic Algorithm

위 코드는 하드웨어가 가상 주소 변환을 처리하는 알고리즘을 간단히 보여준다. 단 이때는 선형 페이지 테이블(linear page table)과 하드웨어로 관리되는 TLB를 사용한다고 가정한다.

먼저 가상 주소로부터 VPN을 추출하고 TLB가 해당 VPN의 변환을 담고 있는지를 확인한다. 만약 TLB가 해당 변환을 담고 있다면(TLB 히트, TLB hit), 이 경우 우리는 PFN을 TLB의 엔트리에서 구하고 오프셋을 더해 원하던 물리 주소를 얻어 메모리에 접근한다.

만약 CPU가 TLB에서 해당 VPN의 변환을 찾지 못하면(TLB 미스, TLB miss), 하드웨어는 변환을 찾기 위해 페이지 테이블에 접근하고, TLB를 해당 변환으로 업데이트한다. 이 일련의 행동들은 페이지 테이블에 접근하기 위한 추가적인 메모리 참조를 필요로 하기 때문에 비싸다. 마지막으로, TLB가 업데이트되고 나면 하드웨어는 명령을 재시도한다. 변환은 TLB에서 찾을 수 있기 때문에 메모리 참조는 빠르게 이루어진다.

TLB는 다른 캐시들과 마찬가지로, 보통의 경우 변환을 캐시에서 찾을 수 있을 것이라는 전제 아래 만들어져있다. 하지만 TLB 미스가 자주 일어나게 되는 경우, 프로그램은 눈에 띄게 느려진다. TLB 미스가 일어났을 때 일어나는 일련의 동작들은 높은 비용을 가지고 있기 때문이다. 어떻게 TLB 미스를 최소한으로 줄일 수 있을까?

2. Example: Accessing An Array

이 예시에서는 4 바이트 정수들을 담은 길이 10의 배열들을 사용한다. 이 배열은 가상 주소 100에서 시작한다고 하자. 가상 주소 공간은 8비트로, 16바이트의 페이지들로 이루어져있다고 가정한다.

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

단순화하기 위해서, i나 sum에 대한 메모리 접근은 제외하고 배열에 대한 메모리 접근만 고려한다고 가정한다.

배열의 첫 원소 a[0]에 접근할 때에는 당연히 TLB 미스가 일어난다. TLB 미스가 일어난 후 앞서의 동작들이 수행되면, a[0]이 있는 페이지에 대한 변환 정보는 TLB에 올라가게 된다. 다음 원소인 a[1]에 접근할 때에는 TLB 히트가 일어나는데, 그 이유는 a[1]과 a[0]이 같은 페이지에 있기 때문이다. a[2]에 접근할 때도 마찬가지로 TLB 히트가 된다.

문제는 a[3]은 지금까지 접근해온 곳과 다른 페이지에 있기 때문에 TLB 미스가 일어난다는 것이다. a[3]에 접근한 후 a[6]까지는 다시 TLB 히트, a[7]은 미스, a[9]까지는 다시 히트가 된다. 따라서 이 열 번의 배열 원소 접근에서는 3번의 미스, 7번의 히트가 일어나게 되고, TLB 히트율은 70%이다.

각 원소들에 대한 접근이 처음임에도 TLB 히트가 일어나는 이유는 배열의 공간 지역성(spatial locality) 덕분이다. 배열의 원소들은 같은 페이지, 혹은 공간적으로 가까운 페이지들에 연속적으로 위치하고 있기 때문에, 각 페이지의 첫 번째 원소에 접근할 때만 TLB 미스가 일어나게 되는 것이다.

만약 페이지의 크기를 16바이트가 아난 32바이트로 늘린다면 미스는 더 줄어들 게 된다. 보통 사용하는 페이지 사이즈는 4KB이기 때문에, 이렇게 밀도 높은 배열 기반의 접근은 높은 TLB 성능을 가지게 된다.

만약 프로그램이 위 루프가 끝나고 배열에 재접근한다면 더 높은 TLB 히트율을 얻을 수 있을 것이다(시간 지역성, temporal locality). 다른 캐시들과 마찬가지로 TLB의 성공은 공간적, 시간적 지역성에 크게 의존하고 있음을 볼 수 있다.

3. Who Handles The TLB Miss?

TLB 미스를 처리하는 주체에는 하드웨어와 소프트웨어가 있다.

옛날에는 하드웨어가 복잡 명령어 집합(complex instruction set)을 사용했고, 하드웨어가 TLB 미스를 전부 처리했다. 이를 위해 하드웨어는 페이지 테이블이 메모리의 어디에 위치 했는지를 알아야했고, 그 정확한 형식도 알아야 했다. 미스가 일어나면 하드웨어는 페이지 테이블을 순회해 해당하는 페이지 테이블 엔트리를 찾고 원하던 변환을 찾아 TLB를 업데이트하고 명령을 재실행한다.

더 현대적인 설계에서는 소프트웨어로 관리되는 TLB를 사용한다. TLB 미스가 일어나면 하드웨어는 그저 예외를 일으키고 현재의 명령 스트림을 멈춘다. 이후 하드웨어는 CPU를 커널 모드로 전환하고 트랩 핸들러로 점프한다. OS에서 트랩 핸들러가 실행되면, 그 코드는 페이지 테이블에서 변환을 찾아보고, TLB 업데이트를 위한 특권 명령을 사용한다. 트랩이 끝난 후에는 하드웨어가 명령어를 재실행한다.

다만 이 경우에 사용되는 return-from-trap 명령은 앞서 다뤘던 return-forom-trap과는 조금 다르다. 후자의 경우는 트랩이 일어나면, 그 이후의 명령부터 재실행했만, 지금은 이 트랩을 발생시킨 명령어부터 시작해야 하기 떄문이다. 어떻게 트랩이나 예외가 발생하는지에 따라 하드웨어는 다른 PC를 저장해둬야 한다.

TLB 미스 처리 코드를 실행할 때 OS는 TLB 미스의 무한 연쇄가 일어나지 않도록 추가적인 신경을 써줘야 하는데, 이에 대해서도 많은 해결책들이 있다. 그 중 한 가지는 TLB 미스 핸들러를 물리 메모리에 두는 것이고, 또 다른 것에는 TLB의 몇몇 엔트리를 영구적으로 유효한 변환을 위해 예약하고 그 중 일부를 핸들러 코드를 위해 사용하는 것이다.

소프트웨어-관리 접근법의 가장 큰 장점은 융통성이다. OS는 페이지 테이블을 구현하기 위해, 하드웨어의 변화 없이도 여러 자료 구조들을 사용할 수 있다. 다른 이점은 간단함이다. 하드웨어는 미스가 일어났을 때 별 다른 일을 하지 않고 예외를 일으키기만 하고, OS의 TLB 미스 핸들러가 나머지를 전부 처리한다.

4. TLB Contents: What's In There?

하드웨어 TLB에 대해 좀 더 자세히 알아보자. 전형적인 TLB는 32, 64, 128개의 엔트리를 가지고 있고, 완전 연관 사상 방식(fully-associative)을 사용한다. 기본적으로 이 방식은 변환이 어떤 것이든 TLB의 어디엔가 위치시킬 수 있고, 하드웨어는 원하는 변환을 찾기 위해 전체 TLB를 병렬적으로 탐색한다. 이때 사용되는 TLB 엔트리는 다음과 같은 형식을 가진다.

VPN | PFN | other bits

여기서 other bit에는 다음과 같은 정보들이 들어갈 수 있다.

• valid bit: 엔트리가 유효한 변환을 가지고 있는지를 표시.
• protection bit: 페이지가 어떻게 접근될 수 있는지를 표시.
• address-space specifier: 어떤 프로세스의 주소 공간인지를 표시.
• dirty bit: 메모리에 올라온 후 수정된 적이 있는지를 표시.
• ...

5. TLB Issue: Context Switches

TLB는 현재 실행되고 있는 프로세스의 가상-물리 변환을 가지고 있으며, 이 변환들은 다른 프로세스들에게는 별 의미가 없다. 따라서 문맥 전환이 일어나는 경우 OS는 다음으로 실행될 프로세스가 현재 실행되고 있는 프로세스의 변환 정보들을 사용하지 않도록 해야 한다. 그런데 프로세스들은 각각의 고유한 가상 주소 공간을 사용하며, 하드웨어는 자신에게 주어진 가상 주소가 어떤 프로세스의 것인지를 알지 못한다.

이 문제에 대한 첫 번째 해결책은 첫 번째는 문맥 전환이 일어날 때마다 TLB를 비우는(flush) 것이다. 소프트웨어 기반의 시스템에서 이는 명시적인 특권적 하드웨어 명령으로 이루어지며 하드웨어로 관리되는 TLB의 경우에는 페이지 테이블 베이스 레지스터가 변할 때 TLB를 비우도록 한다. 어느 경우든 flush는 TLB 내의 모든 valid bit을 0으로 만들면서 TLB의 내용을 비운다.

다만 이와 같은 방식을 사용하면 프로세스가 실행될 때마다 한 번은 반드시 TLB 미스가 일어나게 된다는 문제가 있다. OS가 프로세스 전환을 자주 한다면 그 비용은 더 높아진다.

이 오버헤드를 줄이기 위해서 몇몇 시스템들은 TLB를 문맥 전환을 하면서도 공유할 수 있게 하기 위한 하드웨어적인 해결법을 사용한다. 바로 주소 공간 식별자(address space specifier, ASID)를 TLB의 필드에 추가하는 것이다. 이 ASID는 PID와 비슷하지만 그것보다는 적은 비트를 사용함.

ASID를 이용함으로써 TLB는 서로 다른 프로세스들을 서로 구분할 수 있게 된다. 물론 변환을 위해서 하드웨어는 지금 실행되고 있는 프로세스가 어떤 건지도 알아야 하며, 따라서 OS는 문맥 전환이 일어날 때 현재 실행 중인 프로세스의 ASID를 담은 특권 레지스터를 설정해줘야 한다.

6. Issue: Replacement Policy

다른 캐시들에서와 마찬가지로 TLB에서도 캐시 교체를 생각해줘야 한다. 캐시 교체를 위한 접근법들에는 제일 오랫동안 사용되지 않은 엔트리(least-recently used, LRU)를 퇴출하는 방식이 있고, 랜덤하게 임의로 한 엔트리를 퇴출시키는 방법도 있다. 이와 관련한 정책들은 페이지에서 디스크로의 스왑 문제를 공부할 때 더 자세하게 배울 것이다.

7. Summary

하드웨어가 어떻게 주소 변환을 빠르게 만드는지를 봤다. TLB를 주소 변환의 캐시로 사용함으로써 대부분의 메모리 참조는 메인 메모리에 접근하지 않고도 이루어질 수 있게 되며, 보통의 경우 프로그램은 가상화되지 않았을 때만큼 빨라진다.

그렇다고 TLB가 만능인 것은 아니다. 만약 짧은 시간동안 프로그램이 접근하는 페이지의 수가 TLB에 있는 페이지의 수를 초과하면 페이지는 더 많은 TLB 미스를 만들어 느리게 작동할 것이다. 이러한 현상을 TLB의 커버리지(coverage)를 벗어났다고 말하는데, 이 문제에 대한 한 가지 해결법으로는 더 큰 페이지 사이즈를 사용하는 것이 있다.

또한 TLB는 병목 현상을 일으키기도 한다. 물리적으로 인덱싱 된 캐시의 경우 주소 변환이 캐시에 접근하기 전에 일어나야 하므로 속도 저하를 일으킨다. 이 문제를 해결하기 위해서는 가상 주소로 인덱싱을 할 수 있는데, 이는 몇 가지 성능 문제들을 해결할 수는 있지만, 하드웨어 설계에 다른 이슈들을 만들기도 한다.