페이징 : 더 빠른 변환

이번 포스트에서는 저번 포스트에서 알아본 페이징의 주소 변환을 더 빠르게 하는 방법을 알아보겠습니다.

먼저 저번 포스트에 알아본 바로는 페이징은 성능 저하를 유발할 수 있습니다.

페이징은 주소 공간을 작은 크기로 나누고 각 페이지의 실제 위치를 메모리에 저장합니다.

이를 저장하는 자료구조를 페이지 테이블이라 했었고, 이를 위해 큰 공간이 필요하다는 것을 알게되었습니다.

이것을 해결하기 위해 이번 포스트에서는 변환 색인 버퍼 ( Translation Lookaside Buffer ) 또는 TLB라고 부르는 것을 도입하겠습니다.

TLB에는 자주 참조되는 VPN과 PFN의 정보가 함께 저장되어있어, 주소 변환 캐시(Address Translation Cache)라고도 불립니다.

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()

위 코드는 가상 주소 변환이 이루어지는 과정을 대략적으로 보여줍니다.

위 코드는 주소 변환부가 단순한 선형 페이지 테이블과 하드웨어로 관리되는 TLB로 구성되어 있다고 가정한 코드입니다.

1. 가상 주소에서 VPN을 추출한 후, 해당 VPN이 TLB에 존재하는지 여부를 검사합니다.
2. 만약 존재하면, TLB hit이 되고 TLB가 변환 값을 갖고 있다는 것을 의미합니다.
3. 이제 해당 TLB 항목에서 PFN을 추출할 수 있게 되며, 해당 페이지에 대한 접근 권한 검사가 성공하면 그 정보를 원래 가상 주소의 오프셋과 합쳐서 물리주소를 구성하고 메모리에 접근하게 됩니다.
4. 만약 존재하지 않으면 할 일이 많아지게 됩니다.
5. 하드웨어가 변환 정보를 찾기위해 페이지 테이블에 접근하고, 프로세스가 생성한 가상 메모리 참조가 유효하고 접근이 가능하면 정보를 TLB로 읽어들이게 됩니다. ( 시간이 많이 소요됩니다. )
6. TLB가 갱신되면 하드웨어는 명령어를 재실행하고, 이제는 TLB에 정보가 있으니 빠르게 실행되게 됩니다.

모든 캐시의 설계 철학처럼, TLB도 주소 변환 정보가 대부분의 경우 캐시에 존재한다는 가정을 전제로 만들어져있습니다.

미스가 발생하는 것이 아니라면, 페이징 비용이 작지만 만약에 발생하다면 커지게 됩니다.

예제 : 배열 접근

이제 TLB의 작동과정을 알아보기 위해 아래와 같은 코드를 실행하고 TLB 작동과정을 테스트해보겠습니다.

이 예제에서는 가상 주소 100번지부터 10개의 4byte 크기의 정수 배열이 존재합니다.

가상 주소 공간은 8bit이며, 페이지 크기는 16byte입니다.

가상 주소는 4bit VPN과 4bit offset으로 구성됩니다.

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

위 코드를 실행하게 된다면,첫 항목인 a[0]을 접근하게 되었을 때 하드웨어는 VPN을 추출하고 VPN이 6이라는 것을 알게 됩니다.

TLB가 완전히 초기화 되어있다고 가정했을 때, TLB에는 해당 VPN에 대한 PFN을 가지고 있지 않으므로 TLB 미스를 발생시키게 됩니다.

미스가 발생하면, 물리 페이지 번호를 찾게 되고 TLB를 갱신합니다. 그 후 a[0]의 물리 메모리에 접근하게 됩니다.

이제 a[1]과 a[2]의 VPN은 6이기 때문에 TLB에 정보가 있습니다.

TLB 갱신과정이 일어나지 않고, 물리 메모리에 빠르게 접근하게 됩니다.

마찬가지로, a[3]의 VPN인 7은 TLB에 없습니다. 다시 한 번 갱신 작업이 일어나야 합니다.

하지만, 그 다음 a[4], a[5] ,a[6]은 이미 갱신된 TLB에서 PFN을 빠르게 얻게 됩니다.

또, a[7]을 보게 되면 VPN인 8은 TLB에 없고, 갱신이 일어나게 됩니다.

여기서도 마찬가지로 a[8],a[9]는 이미 갱신된 TLB에서 PFN을 빠르게 얻게 됩니다.

이렇게 10개의 배열 원소를 읽는 동안 미스는 3번, 히트는 7번 일어났습니다.

히트 횟루를 총 접근 회수로 나누어 얻는 TLB 히트 비율은 70%가 됩니다.

그렇게 높은 수치가 아니지만, 만약 실제와 같이 큰 페이지에서 연속하는 정수배열을 접근하게 되면 TLB의 사용은 큰 성능 개선을 가져올 것입니다. ( 이것은 공간 지역성(spatial locality)으로 인한 성능 개선 결과입니다. )

그리고 만약, 예제 프로그램이 이 이후에도 배열을 또 다시 사용하게 된다면 TLB 히트 비율은 더 높아지게 될 것입니다. 이미 구해져 있기 때문에 TLB는 계속 히트하게 될 것입니다. ( 이것은 시간 지역성(temporal locality)으로 인한 성능 개선 결과입니다. )

공간 지역성은 어떤 요소에 접근한 상황일 때, 그 주변 요소에 접근할 가능성이 높다는 것을 의미합니다.

시간 지역성이란 한번 참조된 메모리 영역이 짧은 시간 내에 재 참조될 가능성이 높다는 것을 의미합니다.

TLB 미스는 누가 처리할까?

두 가지 방법이 존재하는데 하드웨어를 이용한 방법부터 알아보겠습니다.

하드웨어가 TLB 미스를 관리하기위해 하드웨어가 페이지 테이블에 대한 명확한 정보를 가지고 있어야 했으며, 메모리 상 위치와 정확한 형식을 파악하고 있어야했습니다.

미스 발생시 페이지 테이블에서 원하는 페이지 테이블 엔트리를 찾고, 필요한 변환 정보를 추출하여, TLB를 갱신한후, TLB 미스를 발생시킨 명령어를 재실행합니다.

다른 방법으로는 OS를 이용하여 관리하는 방법입니다.

TLB 미스가 발생하면 하드웨어는 예외 시그널을 발생 시키고, 예외 시그널을 받은 OS는 명령어 실행을 중지하고 실행 모드를 커널 모드로 변경하여 커널 코드를 실행합니다. ( 아래 코드 )

커널 모드로 변경하면 Trap Handler(TLB 미스의 처리를 담당하는 운영체제의 코드 )를 실행하여, 변환정보를 찾고 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
    RaiseException(TLB_MISS)

OS를 이용한 방법에서 중요한 사항 두 가지를 짚고 넘어가겠습니다.

1. TLB 미스를 처리한는 트랩 핸들러는 시스템 콜 호출 시 사용되는 트랩 핸들러와의 차이가 있습니다.
2. TLB 미스 핸들러를 실행할 때, TLB 미스가 무한 반복 되지 않도록 주의해야합니다.

TLB의 구성 : 무엇이 있나?

TLB는 32, 64, 또는 128개의 엔트리를 가지며, 완전 연관 ( fully associative ) 방식으로 설계 됩니다.

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

TLB의 구성은 아래와 같습니다.

TLB는 VPN, PFN, 다른 비트들로 구성되어 있는 것을 볼 수 있는데, 다른 비트들에는 valid bit, protection bit, dirty bit등 여러 기타 비트들이 존재하게 됩니다.

TLB의 문제 : Context Switches

TLB를 사용하게 되면 프로세스간 Context Switch시, 새로운 문제가 등장합니다.

TLB의 주소 변환 정보는 그것을 탑재시킨 프로세스에만 유효합니다.

다른 프로세스에는 의미가 없으며, 새로운 프로세스에서는 이전에 실행하던 프로세스의 주소 변환 정보를 사용하지 않도록 해야합니다.

이를 해결하기위하여, 하나의 예제를 보겠습니다.

P1이라는 프로세스가 실행중이고, VPN 10이 PFN 100에 매핑되어있다고 가정하겠습니다.

또 다른 P2가 있고, OS가 Context Switch를 위해 이 프로세스를 실행하기 위해 준비중이라고 가정하겠습니다.

이 프로세스는 VPN 10이 PFN 170에 매핑되어있다고 가정하겠습니다.

방금 가정한 TLB 정보를 나타내면 위 그림과 같아질 것입니다.

그런데 위 TLB는 문제가 있습니다. VPN 10에 해당하는 변환 정보가 두 개 존재한다는 것입니다.

이것을 해결하는 방법은 여러가지가 있습니다.

1. Context Switch가 발생할 때 기존 프로세스의 주소 변환 정보를 TLB에서 제거하는 것입니다. 내용을 전부 지워버리기 때문에 안전하지만, 이는 Context Switch마다 TLB 미스가 발생하게 된다는 단점이 존재하기 때문에 비용이 커지는 작업입니다.
2. TLB의 내용을 보존하고, 주소 공간 식별자 ( Address Space Identifier, ASID ) 를 추가하는 것입니다. ASID는 PID와 유사한 역할을 하고, TLB의 정보를 구분할 수 있습니다.
   

추가적으로 TLB의 두 항목이 매우 유사한 경우도 생각해볼 수 있습니다.

이 경우에는 두 개의 프로셋스가 하나의 페이지 ( 코드 페이지가 같은 경우 ) 를 공유할 때 발생 할 수 있습니다.

이 예제에서는 프로세스 1이 물리 페이지 101을 프로세스 2와 공유하고 있습니다.

프로세스1은 이 페이지를 자신의 주소 공간의 10번째 페이지에 매핑하고 있고, 프로세스2는 자신의 주소 공간의 50번째 페이지에 매핑하고 있습니다.

코드 페이지를 공유하게 되면 프로세스가 사용하는 물리 페이지를 줄일 수 있습니다.

이슈 : 교체 정책

TLB에서 캐시 교체 정책은 매우 중요합니다.

TLB에 새로운 항목을 탑재할 때, 현재 존재하는 항목 중 하나를 교체 대상으로 선정해야하는데, 어떻게 선정할까요?

한가지 흔한 방법은 LRU(Least-Recently-Used, 최저 사용 빈도) 알고리즘을 사용한 방법입니다.

최근에 가장 적게 사용한 것이니 교체 대상으로 적합하다는 것이 근거입니다.

또 다른 일반적인 방법은 랜덤 정책입니다.

랜덤 정책은 때때로 잘못된 결정을 내릴 수 있다는 단점이 있지만, 구현이 간단하고 예상치 못한 예외 상황을 피할 수 있습니다.

요약

이번 포스트는 TLB를 통한 페이징 속도 개선에 대해 알아보았습니다.

이제 메인 메모리상의 페이지 테이블을 읽지 않고 처리가 가능하게 도이었고, TLB의 사용으로 일반적인 경우에 프로그램은 메모리 가상화 기능이 없는 것과 동일한 성능을 보여줄 것입니다.

하지만, TLB가 언제나 좋은 제대로 작동하는 것이 아닙니다.

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

이러한 문제를 해결하기 위한 방법을 다음 포스트에서 알아보겠습니다.