[운영체제] Memory - TLB (Translation Look-Aside Buffer)

전윤혁·2024년 12월 9일
OSmemory
0

OS

목록 보기
10/18
post-thumbnail

이전 글에서 Paging을 다루며, 주소 변환 과정에서의 오버헤드와 메모리 공간 차지라는 두 가지 단점을 언급했다.

이번 글에서는 주소 변환 과정에서 오버헤드를 완화하는 방법인 TLB(Translation-Lookaside Buffer)에 대해서 알아보도록 하자!

1. TLB (Translation-Lookaside Buffer)

1) TLB 개념

페이징 방식에서 성능 문제는 주소 변환 정보(PTE, Page Table Entry)가 모두 메모리에 있는 페이지 테이블(Page Table)에 저장되기 때문에 발생하였다. 이를 해결하기 위해 등장한 것이 TLB(Translation Lookaside Buffer)이다.

TLB는 최근에 사용된 페이지 테이블 매핑 정보를 CPU 내부에 캐시(Cache)하여, 주소 변환을 빠르게 처리할 수 있도록 돕는다. 페이지 테이블을 CPU 내부에 전부 저장할 수는 없으니, 자주 사용되는 페이지의 매핑 정보만 CPU 내부에 캐시하는 것이다.

이 때 원하는 매핑이 TLB에 존재하는 상황을 TLB Hit, 존재하지 않는 상황을 TLB Miss라고 한다. 자세한 내용은 아래의 TLB 알고리즘을 통해 살펴보자.

2) TLB 알고리즘 (TLB Hit & Miss)

아래의 알고리즘은 페이징의 주소 변환 알고리즘이다.

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와 관련하여, 주목해서 볼 부분은 아래의 부분들이다.

(Success, TlbEntry) = TLB_Lookup(VPN)

해당 부분에서, 원하는 매핑 정보가 TLB에 존재하는지 먼저 확인한다.

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);
    }

Success가 True, 즉 TLB에 원하는 매핑 정보가 있는 경우는 TLB Hit에 해당한다. TLB Hit인 경우, TLB에서 페이지 프레임 번호를 추출한 후 메모리에 엑세스한다.

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

Success가 False, 즉 TLB에 원하는 매핑 정보가 없는 경우는 TLB Miss에 해당한다. TLB Miss인 경우, 매핑 정보를 찾기 위해 (힘들게) Page Table에 접근한 후, 해당 매핑 정보를 TLB에 Insert 해준다. 만약 TLB가 이미 가득 차있다면? TLB 교체 정책을 통해 Insert를 진행하는데, 이는 아래에서 알아보자.

3) Array 접근 예시

실제로 Array에 접근하는 과정을 살펴보며 TLB Hit과 TLB Miss를 살펴보자.

  • a[0]에 접근하는 시점에 TLB는 비어있으므로 TLB Miss가 발생하고, VPN = 6에 해당하는 PTE(PFN 연결 정보)를 가져온 후 TLB에 삽입한다.
  • a[1] ~ a[2]에서는 TLB Hit이 발생한다.
  • a[3]에서는 TLB Miss가 발생하고, a[4] ~ a[6]에서는 TLB Hit이 발생한다.
  • a[7]에서는 TLB Miss가 발생하고, a[8] ~ a[9]에서는 TLB Hit이 발생한다.

결과적으로 TLB Miss는 3회, TLB Hit은 7회가 발생한다.

4) Temporal Locality & Spatial Locality

  • Spatial Locality
    프로그램이 메모리 주소 x를 접근하면, 그 근처의 메모리 주소를 곧바로 접근할 가능성이 높다는 개념이다. 위의 Array 접근 예시에서는 Spatial Locality 이점을 통해 TLB Hit이 연속으로 발생했다.

  • Temporal Locality
    최근에 접근한 명령어나 데이터는 가까운 미래에 다시 접근될 가능성이 높다는 개념이다. 만약 위의 Array를 두 번 접근한다면, Temporal Locality의 이점을 통해 다수의 TLB Hit이 발생할 것이다.

2. TLB Miss Handling

앞서 TLB Miss 경우에 대한 알고리즘을 알아봤는데, 그렇다면 Hardware와 Software 중 누가 TLB Miss Handling을 수행하는 것일까? 결론부터 말하자면, 두 방식 모두 가능하다.

1) Hardware-managed

  • CISC 아키텍처에서는 TLB Miss를 하드웨어가 전적으로 처리한다.

  • 하드웨어는 페이지 테이블이 메모리 어디에 위치하는지 정확히 알고 있어야 하며, 이를 통해 페이지 테이블을 "탐색(walk)"하여 적절한 페이지 테이블 항목(PTE)을 찾아 원하는 매핑을 추출한다.

  • 이후, 해당 매핑을 TLB에 업데이트하고, 명령어를 재실행하여 주소 변환을 완료한다.

  • Intel x86 CPU가 Hardware-managed TLB의 대표적인 예시인데, "Multi-Level Page Table"이라는 개념을 추가로 사용한다. (다음 글에서 다뤄질 예정)

2) Software-managed

  • RISC 아키텍처에서는 TLB Miss를 소프트웨어가 관리한다.

  • TLB Miss가 발생하면, 하드웨어는 예외(trap)를 발생시키고, 운영 체제의 트랩 핸들러가 이를 처리한다.

  • 트랩 핸들러는 운영 체제 내의 코드로, TLB Miss가 발생한 경우 이를 처리하는 데 필요한 작업을 수행한다. 여기에는 페이지 테이블을 조회하고, TLB에 새로운 변환 정보를 삽입하며, 명령어를 재시작하는 등의 작업이 포함된다.

3. TLB Issue: Context Switching

1) Context Switching

TLB의 Context Switching과 관련된 이슈를 간단하게 짚고 넘어가보자.

위의 그림과 같이 두 개 이상의 프로세스가 존재할 때, TLB에 존재하는 각각의 엔트리가 어떤 프로세스에 대한 것인지 구분하기 어렵다!

단순히 생각하면, 프로세스가 바뀌기 직전에 현재 프로세스의 엔트리의 Valid Bit을 0으로 전부 바꿔주는 방법을 생각할 수 있다. (TLB에서 말하는 Valid Bit은 매핑 정보의 유효성으로, 해당 주소 공간의 사용 여부를 나타내는 Page Table의 Valid Bit과는 아예 다른 개념이다.)

하지만 Context Switching이 일어날 때마다 특정 프로세스의 Valid Bit을 전부 바꾸는 것은 비효율적이고 성능 저하를 초래할 수 있다. (이 또한 연산이므로) 따라서, 아래 그림과 같이 간단히 ASID(Address Space Identifier)를 기록하여 프로세스를 구분할 수 있다.

2) Another Case

이번에는, 두 개의 프로세스가 하나의 물리적 페이지를 공유하는 상황을 가정해보자.

위의 TLB를 보면, ASID 1, 2로 구분된 두 개의 프로세스가 같은 PFN(101)을 공유하는 것을 볼 수 있다. 이런 식으로 같은 물리 페이지를 공유하면, 두 개의 프로세스가 각각 별도의 물리적 페이지를 할당받는 것보다 메모리를 절약할 수 있다.

4. TLB Replacement Policy

앞선 설명에서, TLB가 이미 가득 찬 상태라면 교체 정책을 통해 Insert를 진행한다고 언급하였다. 앞서 언급한 Temporal Locality 기반의 흔히 사용되는 방법으로는 LRU(Least Recently Used)가 있다. LRU는 최근에 가장 오랫동안 사용되지 않은 항목을 교체하는 메모리 관리 알고리즘이다.

마치며

이번 글에서는 페이징의 성능 상 문제점을 완화하는 방법인 TLB에 대해서 알아봤다. 하지만 페이징 기법은 여전히 너무 많은 메모리 공간을 차지한다는 문제가 남아있다!

다음 글에서는 페이징의 메모리 공간 문제를 완화하는 방법에 대해 알아보자.

profile
전윤혁
전공/개발 지식 정리
이전 포스트

[운영체제] Memory - Paging

다음 포스트

[운영체제] Memory - Paging Smaller Tables

0개의 댓글