[OS] Paging 메모리 관리를 빠르게 하기 위한 TLB - OS 공부 13

안녕하세요 Pingu입니다!

 

지난 글에서는 메모리를 고정 크기로 할당하여 사용하는 paging에 대해 알아봤습니다. 하지만 지난 글에서 알아본 paging 기법에는 두 가지 큰 문제점이 있었는데요, 잦은 메모리 접근과 page table을 위한 메모리 낭비가 두 가지 문제점이었습니다. 이번 글에서는 앞서 말한 두 개의 문제 중 잦은 메모리 접근을 보완하기 위한 Translation Lookaside Buffer(TLB)에 대해 알아보도록 하겠습니다. 제가 공부할 때 참고하고 있는 OSTEP 책에서는 Chapter 19 - Translation Lookaside Buffers입니다.

Paging: Faster Translations(TLB)

Paging을 사용하여 메모리 가상화를 지원한다면 오버 헤드가 발생합니다. 메모리에 자주 접근하게 되고 page table을 위한 메모리도 존재해야 합니다. CPU가 메모리에 접근하여 page table 정보로 주소 변환을 하는 것은 매우 느린 변환 방법입니다. 이를 어떻게 좀 더 빠르게 만들 수 있을까요? 지금까지의 메커니즘들을 사용할 때 OS, HW의 도움을 받았던 것을 기억하시나요? 이번에도 역시 OS, HW의 도움을 받아 paging을 빠르게 만들어보려고 합니다. 메모리의 잦은 접근을 줄이기 위해 CPU의 MMU에 위치한 translation lookaside buffer(TLB)를 사용해보겠습니다. TLB에는 virtual page number(VPN)와 physical frame number(PFN) 정보가 쌍으로 존재하며 이를 사용해 주소변환을 하도록 도와주는 하드웨어 cache입니다. 이를 사용해 CPU는 paging 기법으로 주소변환을 할 때 메모리의 page table을 먼저 보는 것이 아닌 TLB를 먼저 확인하여 TLB에 정보가 존재한다면 해당 정보로 빠르게 주소변환을 할 수 있습니다. 이렇게 되면 주소 변환을 위해 메모리에 접근하는 일이 없으므로 주소 변환이 빠르게 수행됩니다.

TLB Basic Algorithm

그럼 먼저 page table과 TLB가 존재할 때 주소 변환이 어떻게 수행되는지 간단히 코드로 살펴보겠습니다.

VPN = (VirtualAddress & VPN_MASK) >> SHIFT
(Success, TLBEntry) = TLB_Lookup(VPN)

// TLB에 변환 정보가 존재한다면
if (Success == True)
    // 접근 가능한지 확인후 TLB의 정보로 바로 주소변환
    if (CanAccess(TLBEntry.ProtectBits) == True)
        Offset = VirtualAddress & OFFSET_MASK
        PhysAddr = (TLBEntry.PFN << SHIFT) | Offset
        Register = AccessMemory(PhysAddr)
    else
        RaiseException(PROTECTION_FAULT)

// TLB에 변환 정보가 없다면
if (Success == False)
    // 메모리에 존재하는 Page Table 조회
    PTEAddr = PTBR + (VPN * sizeof(PTE))
    PTE = AccessMemory(PTEAddr)
    // PTE에 접근 권한 없다면 오류 발생
    if (PTE.Valid == False)
        RaiseException(SEGMENTATION_FAULT)
    // PTE에 보안비트 확인 후 오류 발생
    else if (CanAccess(PTE.ProtectBits) == False)
        RaiseException(PROTECTION_FAULT)
    // 모든게 정상이라면 TLB에 변환 정보 저장 (다음에는 TLB로 변환하도록)
    else
        TLB_Insert(VPN, PTE.PFN, PTE.ProtectBits)
        RetryInstruction()

간단히 설명하자면 CPU가 주소변환을 할 때 TLB가 존재한다면 주소 변환을 위해 TLB부터 조회합니다. 원하는 변환 정보가 있다면 바로 변환을 하고 그렇지 않다면 메모리에 존재하는 page table에 접근하여 주소 변환 정보를 TLB에 저장합니다. 그리고 다시 주소변환을 시도합니다. 이때 역시 TLB부터 조회하게 되고 아까 메모리에서 주소 변환 정보를 저장했으니 주소 변환이 빠르게 발생하게 됩니다.

 

위와 같은 방식으로 진행이 되기 때문에 TLB가 존재하더라도 특정 page에 처음 접근할 때는 메모리 접근이 필요합니다. 요약하자면 주소 변환 정보가 TLB에 존재하지 않는다면 page table에 접근해야 한다는 것이죠. 따라서 TLB에 주소 변환 정보가 없는 상황을 줄이는 것이 중요합니다!

Example: Accessing An Array

그럼 TLB를 사용한 주소변환 방법이 TLB가 없는 상황에 비해 얼마나 메모리 접근이 적게 발생하는지 예를 보고 이해해보겠습니다. Page의 크기는 16 바이트이며 가상 주소 공간의 크기를 8비트 (2^8 = 196바이트)라고 가정하겠습니다. 이 상황에서 가상 주소 공간에 존재하는 페이지 수는 16개가 되겠죠? 이러한 상황에서 아래 코드를 실행한다고 생각해보겠습니다.

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

C언어에서 int 자료형은 4바이트의 크기를 가지기 때문에 배열의 크기는 40바이트입니다. 이 배열이 가상 주소 공간 100에서 시작한다고 가정하면 page table은 아래와 같이 그릴 수 있습니다.

즉 배열 요소 하나당 4바이트 이므로 하나의 page의 크기가 16 바이트인 현재 상황에서는 위와 같이 하나의 page 공간에 4개의 배열 요소가 들어갈 수 있는 것이죠. 간단하게 하기 위해서 변수 i, sum과 관련된 명령어는 무시하고 배열 a에만 집중해서 살펴보겠습니다.

 

먼저 TLB가 없는 상황에는 몇 번의 메모리 접근이 발생할까요? 총 10번의 반복이 발생하므로 반복마다 page table에 접근하여 주소 변환을 해줘야 할 것입니다. 그럼 TLB를 사용하면 어떻게 될까요?

 

그럼 이번에는 TLB를 사용하는 상황을 살펴보겠습니다. 위의 상황에서 가장 먼저 a[0]에 접근하게 될 것입니다. TLB를 사용하는 상황이므로 CPU는 TLB에 먼저 조회를 할 것입니다. 하지만 TLB에는 아무 정보가 없기 때문에 TLB miss(정보가 없음)이 발생합니다. 따라서 a[0]에 대한 주소 변환 정보를 page table에서 조회하여 해당 정보를 TLB에 저장하게 됩니다. 그런 뒤 a[1], a[2]에 접근할 때는 어떻게 될까요? 아까 a[0]을 접근할 때 해당 page의 주소 변환 정보를 TLB에 저장했으니 a[1], a[2]에 접근할 때는 TLB에서 정보를 가지고 올 수 있습니다. 이렇게 TLB에서 주소 변환이 성공하는 것을 TLB Hit라고 합니다.

 

하지만 a[3]에 접근할 때는 새로운 page이므로 역시나 TLB에 정보가 존재하지 않아서 TLB Miss가 발생하고 page table에 접근하게 됩니다. 그리고 같은 page에 존재하는 a[4], a[5], a[6]에 접근할 때는 TLB Hit가 발생하게 됩니다. 역시나 같은 이유로 a[7]에 접근할 때는 page table에 접근하게 되고 a[8], a[9]에 접근할 때는 TLB Hit가 발생합니다.

 

즉 a 배열에 대한 10번의 접근 중 3번의 TLB Miss와 7번의 TLB Hit가 발생했습니다. 즉 TLB hit rate는 7/10 = 70%입니다. 이는 page의 크기가 16바이트라서 70%라는 값이 나온 것입니다. 일반적으론 page 크기가 4KB이고 배열의 요소 개수도 1000개씩 된다면 거의 100%에 가까워집니다. 즉 TLB는 spatial locality(공간 지역성)으로 인해 성능을 향상하는 것입니다.

 

또한 이렇게 한 번 접근한 뒤에 다시 a 배열에 접근할 때는 이미 TLB에 모든 변환 정보가 존재하기 때문에 100%의 TLB hit rate로 주소 변환이 수행됩니다. 모든 cache와 마찬가지로 TLB도 하나의 cache로써 spatial, temporal locality(공간, 시간 지역성)으로 인해 TLB hit rate를 높이게 됩니다.

 

여기서 spatial locality(공간 지역성), temporal locality(시간 지역성)의 의미를 한 번 보고 넘어가겠습니다. 공간 지역성이란 어떤 요소에 접근 한 상황이라면 그 주변의 요소들에 접근할 가능성이 높다는 개념입니다. 아까의 예에서 배열과 같은 데이터에 접근할 때 순차적으로 접근하게 되므로 비슷한 공간에 있는 요소들에 접근하는 것을 알 수 있습니다. 시간 지역성이란 최근에 접근한 명령이나 데이터에 조만간 또 접근할 가능성이 높다는 개념입니다. 반복문에서 이를 확인할 수 있죠. 이러한 개념을 이용하여 하드웨어에서는 cache(캐시)라는 작고 빠른 메모리에 정보를 저장하여 지역성을 활용합니다. 그런데 이렇게 캐시가 좋은데 모든 데이터를 캐시에 저장하면 엄청나게 빠르고 좋지 않을까요? 하지만 이것은 아니라고 합니다. 캐시가 빠른 이유는 캐시의 크기가 작기 때문이며 캐시의 크기가 커진다면 지금의 캐시처럼 빠르지 않다고 합니다. 따라서 현재 존재하는 캐시를 잘 활용하는 것이 중요합니다!

Who Handles The TLB Miss?

그렇다면 이번에는 TLB Miss에 대해 좀 더 알아보겠습니다. 아까의 예에서 TLB Miss가 발생하면 메모리에 존재하는 page table에 접근해야 한다고 했는데, 이러한 처리는 누가 하는 것일까요? 이는 HW가 하는 방법과 OS가 하는 방법, 즉 2가지로 나뉩니다.

 

하드웨어에서 TLB Miss를 처리할 때 하드웨어는 page table이 메모리 어디에 존재하는지와 page table에 존재하는 정보를 정확하게 알아야 합니다. 이를 모른다면 하드웨어는 page table을 walk 하여 올바른 정보를 page table에서 TLB로 업데이트하고 주소 변환을 다시 시도합니다. 이러한 아키텍처는 Intel x86 아키텍처가 fixed multi level page table(고정 다중 레벨 페이지 테이블)을 사용하여 이러한 방법을 사용합니다.

 

이와 다른 아키텍처로 소프트웨어 즉 OS가 TLB를 관리하는 것입니다. TLB Miss가 발생하면 하드웨어는 현재 명령을 중지하고 권한을 Kernel Mode로 올린 뒤 trap 처리기로 예외를 발생시킵니다. 그런 뒤 page table을 조회하여 TLB를 업데이트하고 다시 주소 변환을 시도합니다. 여기서 중요한 것은 trap을 발생시킬 때 프로세스를 종료하는 것이 아니고 TLB를 업데이트 한 뒤에 다시 실행해야 한다는 부분입니다. 이러한 부분 때문에 OS로 TLB Miss를 처리할 때는 무한 루프에 빠지지 않도록 주의해야 합니다. 즉 TLB에 주소 변환 정보가 없어서 page table에 접근했는데도 존재하지 않는다면 무한 루프에 빠질 수 있습니다. 이런 문제를 방지하기 위해 TLB의 일부를 영구적으로 유효한 주소 변환을 위해 저장해 두고 이러한 상황을 처리할 수 있습니다.

 

이를 간단하게 코드로 나타내면 아래와 같습니다.

VPN = (VirtualAddress & VPN_MASK) >> SHIFT
(Success, TLBEntry) = TLB_Lookup(VPN)

// TLB에 변환 정보가 존재한다면
if (Success == True)
    // 접근 가능한지 확인후 TLB의 정보로 바로 주소변환
    if (CanAccess(TLBEntry.ProtectBits) == True)
        Offset = VirtualAddress & OFFSET_MASK
        PhysAddr = (TLBEntry.PFN << SHIFT) | Offset
        Register = AccessMemory(PhysAddr)
    else
        RaiseException(PROTECTION_FAULT)

// TLB에 변환 정보가 없다면
else
    // TLB Miss 핸들러 호출
    RaiseException(TLB_MISS)

 

이렇게 OS로 TLB를 관리하게 되면 가장 큰 장점은 flexibity(유연성)입니다. OS는 하드웨어의 변경 없이 page table을 구현하는 모든 자료 구조를 사용할 수 있습니다. 또 다른 장점은 simplicity(단순함)입니다. 즉 Miss가 발생해도 하드웨어가 할 일은 별로 없고 그저 OS TLB Miss 핸들러가 작동하여 이러한 문제를 해결합니다.

TLB Contents: What's In There?

그럼 이제는 TLB에는 어떠한 정보가 존재하는지 알아보도록 하겠습니다. TLB에는 32, 64, 128개의 entry가 존재할 수 있으며 이를 fully associative(캐시 내에 아무 장소에 mapping 될 수 있음)라고 합니다.  따라서 주소 변환 정보가 TLB의 어디에나 존재할 수 있으며 하드웨어가 전체 TLB를 병렬로 검색하여 주소 변환 정보를 찾을 수 있습니다. 이러한 TLB는 아래와 같은 구조를 가지고 있습니다.

Virtual Page Number, Physical Frame Number와 다른 비트들로 TLB가 구성되어 있는 것을 볼 수 있습니다. 여기서 다른 비트들은 현재 존재하는 주소 변환 정보가 유효한지에 대한 비트, page table에서 같은 page에 접근할 수 있는지 확인하는 protection 비트, context switch에 사용되는 address-space identifier 비트, 그리고 수정 여부에 대한 dirty bit 등 이 있습니다. 이런 비트 들에 대한 것은 잠시 후에 알아보도록 하겠습니다.

TLB Issue: Context Switches

TLB를 사용할 때 Context Switch가 발생한다면 어떻게 될까요? 여러 프로세스는 각자 자신의 가상 메모리 공간이 존재하고 각자의 가상 메모리 공간은 page로 쪼개지며 많은 프로세스가 존재할 때 page table의 index가 같은 경우가 발생할 수 있습니다. 예를 들어 프로세스 A의 VPN 1에 대한 주소 변환 정보가 TLB에 저장되어 있었는데 context switch가 발생하여 프로세스 B가 실행된다고 가정해보겠습니다. 프로세스 B에서도 VPN 1에 대해 주소 변환을 하려고 TLB를 확인할 때 단지 VPN 1이라는 값이 같다고 해서 TLB에서 주소 변환을 해버리면 큰 문제가 발생할 수 있습니다. 즉 이 문제를 좀 더 자세히 살펴보면..

위와 같이 프로세스 A, B의 VPN 10에 대한 주소 변환 정보가 TLB에 저장되어 있다고 가정하겠습니다. VPN은 10으로 동일하지만 PFN은 서로 다른 것을 볼 수 있습니다. 하지만 위와 같이 TLB에 정보를 저장하게 되면 어떤 정보가 어떤 프로세스의 정보인지 알 수 없습니다. 이렇게 되면 프로세스에서 서로의 주소 공간이 아닌 곳에 접근할 수 있게 되므로 아주 큰 문제입니다. 이를 해결하기 위한 방법은 무엇일까요?

 

첫 번째 방법은 Context switch가 발생할 때 기존 프로세스의 주소변환 정보를 TLB에서 모두 지워버리는 것입니다. 이를 flush라고 하는데, 이렇게 되면 TLB의 주소 변환 정보중 valid 비트의 값을 0으로 초기화하여 TLB의 내용을 지우게 됩니다. 이 방법으로 context switch가 발생할 때 문제는 해결할 수 있지만 이 방법이 좋은 방법일까요? 우선 context switch마다 이러한 작업을 추가적으로 해줘야 하므로 추가적인 비용이 발생합니다. 또한 context switch가 수행될 때마다 page table을 매번 다시 접근해줘야 하는 문제도 발생하게 됩니다.

 

이러한 오버헤드를 줄이기 위해 context switch가 발생해도 TLB를 유지하기 위해 HW의 도움을 받습니다. 현재 TLB구조에 ASID(Address Space Identifier)라는 정보를 추가하여 문제를 해결하는 것입니다! 그럼 한 번 ASID를 추가한 TLB의 구조를 볼까요?

이렇게 프로세스마다 다른 ASID정보를 저장하여 주소 변환을 잘 수행할 수 있도록 합니다. 지금까지는 VPN이 동일한 예를 봤었는데 PFN이 같은 상황, 즉 코드를 공유하고 있는 상황은 어떨까요?

위와 같이 PFN이 동일하게 되면, 즉 Page를 공유하게 된다면 메모리의 사용을 줄일 수 있으므로 메모리 공간을 좀 더 확보할 수 있습니다.

Issue: Replacement Policy

그렇다면 TLB에 저장 가능한 공간이 가득 찬 경우에 새로운 프로세스가 실행된다면, TLB의 어떤 데이터를 지우고 새로운 프로세스의 주소 변환 정보로 업데이트해야 할까요? 우선 일반적인 방법은 가장 오랜 시간 사용되지 않은 프로세스의 정보를 제거하는 LRU방법을 사용할 수 있을 것입니다. 또 다른 방법은 랜덤 하게 제거하는 방법입니다. 이렇게 TLB 정보를 교체할 때의 목표는 TLB hit rate를 유지하는 것입니다.

A Real TLB Entry

그럼 이제 실제 TLB를 살펴보도록 하겠습니다. 지금 볼 TLB는 OS가 TLB를 관리하는 시스템인 MIPS R4000의 TLB입니다.

MIPS R4000은 4KB 크기의 page와 가상 주소 공간으로 32비트 (2^32 = 4MB)를 지원합니다. 따라서 가상 주소는 20비트의 VPN과 12비트의 Offset으로 구성됩니다. 하지만 실제로는 VPN으로 19비트만 존재합니다. 이유는 메모리의 절반 크기를 kernel용으로 예약하기 때문입니다. 이를 통해 최대 64GB (2^24개의 4KB 페이지) 크기의 메모리 시스템을 지원할 수 있습니다.

 

MIPS의 TLB를 살펴보면 프로세스 간에 전역적으로 공유되는 page에 사용되는 G라는 비트가 존재합니다. 이 비트가 설정되면 ASID가 무시되게 됩니다. 또한 아까 context switch에 사용한 ASID도 존재합니다. 만약 한 번에 실행되고 있는 프로세스 수가 256(2^8)개 이상일 경우엔 OS가 어떻게 작동해야 할까요? 그리고 page가 하드웨어에 의해 캐싱되는 방식을 결정하는 3개의 coherence(C) 비트도 존재합니다. 또한 Page가 사용되었을 때 표시하는 D(dirty) 비트, 변환이 유효한지 하드웨어에 알려주는 Valid(V) 비트, page 크기를 여러 개 지원하는 page mask 비트(여기엔 없습니다)도 있습니다. 위의 그림에서 회색으로 나타난 부분은 사용되지 않는 비트입니다.

 

MIPS TLB에는 이러한 entry가 32개 혹은 64개 존재하며 대부분은 사용자 프로세스에서 사용됩니다. 하지만 TLB Miss를 처리하기 위한 핸들러들을 위해 일부는 OS용으로 예약이 되어있습니다.

 

MIPS TLB는 OS에 의해 관리되므로 TLB를 업데이트하기 위한 네 가지 규칙들이 필요합니다.  

1. TLBP는 특정 주소 변환 정보가 TLB에 존재하는지 확인합니다.
2. TLBR은 TLB의 정보를 레지스터로 읽습니다.
3. 특정 TLB 정보를 교체하는 TLBWI
4. 랜덤 하게 TLB 정보를 교체하는 TLBWR

위의 4가지를 사용하여 OS는 TLB의 내용을 관리합니다. 물론 이러한 것들은 User 모드에서는 사용되면 안 되고 Kernel모드에서만 사용되어야 합니다.

Summary

이번 글에서는 TLB를 사용하여 paging을 사용한 주소변환을 처리하는 방법에 대해 알아봤습니다. TLB를 사용하면 page table에 대한 메모리 접근이 줄어들어 성능을 향상시킬 수 있었습니다. 하지만 이러한 TLB 사용에는 몇 가지 문제가 있었습니다. Context Switch가 발생했을 때의 문제, TLB의 정보를 교체할 때의 문제가 있었습니다. 그리고 다음 글에서 알아볼 TLB가 관리할 수 있는 page보다 더 많은 page를 요구하는 프로세스를 처리하는 문제가 있습니다. 이 문제에 대해선 다음 글에서 알아보도록 하겠습니다!

 

감사합니다.