운영체제 15. 페이징 : 더 빠른 변환(TLB)

운영체제

15. 페이징 : 더 빠른 변환(TLB)

• 변환 - 색인 버퍼(TLB : translation - lookaside buffer)
• MMU의 일부다. 자주 참조되는 가상 주소 - 실 주소 변환 정보를 저장하는 하드웨어 캐시다. 주소 - 변환 캐시(address translation cache)가 조금 더 적합한 명칭이다. 가상 메모리 참조 시, 하드웨어는 먼저 TLB에 원하는 변환 정보가 있는지를 확인한다. 만약 있다면 페이지 테이블(모든 변환 정보를 가지고 있다.) 를 통하지 않고 변환을 수행한다. 실질적으로 TLB는 페이징 성능을 엄청나게 향상시킨다.

15.1 TLB의 기본 알고리즘

• 하드웨어 부분의 알고리즘은 다음과 같이 동작한다. 먼저, 가상 주소에서 가상 페이지 번호(VPN : Virtual Page number)을 추출한 후, 해당 VPN의 TLB 존재 여부를 검사한다. 만약 존재하면 TLB 히트이고 TLB가 변환 값을 갖고 있다는 것을 뜻한다. 이제 해당 TLB 항목에서 페이지 프레임 번호(PFN : page frame number)을 추출할 수 있다. 해당 페이지에 대한 접근 권한 검사가 성공하면 그 정보를 원래 가상 주소의 오프셋과 합쳐서 원하는 물리 주소(PA)를 구성하고, 메모리에 접근 할 수 있다.
• TLB에 정보가 존재하지 않는다면 TLB 미스이다. 이 경우 하드웨어가 변환 정보를 찾기위해서 페이지 테이블에 접근하며, 프로세스가 생성한 가상 메모리 참조가 유효하고 접근 가능하다면, 해당 변환 정보를 TLB로 읽어들인다.

15.2 예제 : 배열접근

• 페이지 크기는 TLB 효용성에 매우 중요한 역할을 한다. 페이지 크기가 2배가 되면, TLB 미스 횟수가 더 줄어든다. 일반적인 경우 페이지는 4KB이다.
• TLB의 성공 여부는 공간 지역성과 시간 지역성 존재 여부에 달려있다.

15.3 TLB 미스는 누가 처리할까

• 하드웨어와 소프트웨어 두 가지 방법이 있다.

하드웨어 처리 방식 - CISC

1. 페이지 테이블에서 원하는 페이지 테이블 엔트리를 찾는다.
2. 필요한 변환 정보를 추출한다.
3. TLB를 갱신한다
4. TLB 미스가 발생한 명령어를 재실행한다.

소프트웨어 처리 방식 - RISC

• TLB에서 주소 찾는 것이 실패하면, 하드웨어는 예외(exception) 시그널을 발생시킨다. 예외 시그널을 받은 운영체제는 명령어 실행을 잠정 중지하고, 실행모드를 커널모드로 변경하여, 커널 코드 실행을 준비한다. 실행모드를 커널모드로 변경하는 작업의 핵심은 커널 주소 공간을 접근할 수 있도록 특권 레벨(privilege level)로 상향 조정하는 것이다. 커널 모드로 변경이 되면 트랩 핸들러(trap handler)를 실행한다. 이때 실행되는 트랩 핸들러는 TLB 미스의 처리를 담당하는 운영체제 코드이다. 이 트랩 핸들러는 페이지 테이블을 검색하여 변환 정보를 찾고, TLB 접근이 가능한 ‘특권’ 명령어(Privaileged instruction)을 사용하여 TLB를 갱신한 후에 리턴한다. 트랩 핸들러에서 리턴되면 하드웨어가 명령어를 재 실행한다.
• 두 가지 중요 사항
  • 첫 번째, TLB 미스를 처리하는 트랩 핸들러는 시스템 콜 호출 시 사용되는 트랩 핸들러와의 차이가 있다. 시스템 콜 호출의 경우는 트랩 핸들러에서 리턴 후 시스템 콜을 호출한 명령어의 ‘다음’ 명령어를 실행한다. 일반적인 프로시저 콜과 동일하다. TLB 미스 처리의 경우, 트랩에서 리턴하면 트랩을 발생시킨 명령을 ‘다시’ 실행해야 하며, 재 실행시에는 TLB에서 히트가 발생한다. 트랩이 발생하면 운영체제는 트랩 핸들러가 종료 되었을 때 다시 실행을 계속할 명령어 주소(Program Counter 값)를 저장한다. 운영체제는 트랩 발생의 원인에 따라 현재 명령어의 pc값 혹은 다음 명령어의 pc값을 저장 해야 한다.
  • 두 번째, TLB 미스 핸들러를 실행할 때, TLB 미스가 무한 반복되지 않도록 주의해야 한다. TLB 미스 핸들러를 접근하는 과정에서 TLB 미스가 발생하는 상황이다. 이를 위해 다양한 해법들이 존재한다. TLB 미스 핸들러를 물리 메모리에 위치시키는 것도 한 방법이다. TLB 미스 핸들러의 주소는 핸들러의 물리 주소로 표시된다. 이 경우 해당 TLB 미스 핸들러는 unmap 되어 있으며 주소 변환이 필요 없다. 다른 방법으로는 TLB의 일부를 핸들러 코드 주소를 저장하는데 영구히 할당하는 것이다. 이렇게 되면 TLB 핸들러는 항상 TLB에서 히트된다. 이를 연결변환 이라고 한다.
• TLB를 소프트웨어로 관리하는 방식의 주된 장점은 유연성이다. 운영체제는 하드웨어 변경없이 페이지 테이블 구조를 자유로이 변경할 수 있다. 또 다른 장점은 단순함이다. 미스가 발생했을 때 하드웨어는 별로 할 일이 없다. 하드웨어는 단지 예외를 일으키고 운영체제의 TLB 미스 핸들러가 나머지 일을 처리한다.

15.4 TLB의 구성 : 무엇이 있나

• 하드웨어 TLB, 일반적인 TLB는 32,64 또는 128개의 엔트리를 가지며, 완전 연관 방식으로 설계된다. 완전 연관 방식에서 변환정보는 TLB 내에 어디든 위치할 수 있으며, 원하는 변환 정보를 찾는 검색은 TLB 전체에서 병렬적으로 수행된다.
• TLB의 구성
  • VPN | PFN | 다른 비트들
• 변환 정보 저장 위치에 제약이 없도록, 각 항목마다 가상 페이지 번호와 물리 페이지 번호가 있다. 하드웨어 측면에서 보자면, TLB는 완전 연관 캐시이다. 변환 주소를 찾을 때, 하드웨어는 TLB의 각 항목을 동시에 검색한다.
• TLB 항목에서 VPN과 PFN을 제외한 다른 비트들에 대해서도 눈여겨 볼 필요가 있다. TLB는 Valid bit 보호 비트, 주소공간 식별자, 더티 비트 등도 있다.

15.5 TLB의 문제 : 문맥교환

• TLB를 사용하게 되면 프로세스 간(주소 공간들로 인해) 문맥 교환 시, 새로운 문제가 등장한다. TLB에 있는 가상 주소와 실제 주소간의 변환 정보는 그것을 탑재시킨 프로세스에서만 유효하다. 다른 프로세스들에게는 의미가 없다. 새로운 프로세스에서는 이전에 실행하던 프로세스의 변환 정보를 사용하지 않도록 주의해야 한다.
• TLB가 정확하고 효율적으로 멀티 프로세스 간의 가상화를 지원하기 위해서는 추가적 기능이 필요하다,.
• 한 방법은 문맥교환을 수행할 때 다음 프로세스가 실행되기 전에 기존 TLB 내용을 비우는 것이다. 소프트웨어 기반의 시스템에서는 특별한(그리고 특권을 갖는) 하드웨어 명령어를 사용하여 이 목적을 달성할 수 있다. 하드웨어로 관리되는 TLB는 페이지 테이블 베이스 레지스터가 변경될 때 비우기를 시작할 수 있다.(운영체제는 문맥교환을 할 때 PTBR을 어쨌든 변경해야 한다.)둘 중 어떤 경우를 비우는 작업은 모든 Valid bit를 0으로 설정을 하는 것이다.
• 문맥교환할 때마다 TLB를 비우며, 잘못된 변환 정보를 사용하는 상황을 방지할 수 있다. 하지만, 이 방식은 공짜가 아니다. 새로운 프로세스가 실행될 때, 데이터와 코드 페이지에 대한 접근으로 인한 TLB 미스가 발생하게 된다. 문맥교체가 빈번히 발생한다면 이 또한 성능에 큰 부담을 가져올 수 있다.
• 이 부담을 개선하기 위해 몇몇 시스템에서는 문맥교환이 발생하더라도 TLB의 내용을 보존할 수 있는 하드웨어 기능을 추가하였다. TLB내에 주소 공간 식별자(ASID : address space identifier) 필드를 추가하는 것이 그것이다. ASID는 프로세스 식별자(PID)와 대략적으로 유사하다. 단, ASID는 좀 더 적은 비트를 갖고 있다.
• 주소 공간 식별자를 사용할 경우, 프로세스 별로 TLB 변환 정보를 구분할 수 있다. 올바른 주소 변환을 위해서 하드웨어는 현재 어떤 프로세스가 실행중인지 파악하고 있어야 한다. 이를 위해, 문맥 전환 시, 운영체제는 새로운 ASID 값을 정해진 레지스터에 탑재해야 한다.

15.6 이슈 : 교체정책

• 모든 캐시가 그러하듯이 TLB에서도 캐시교체(Cache replacement) 정책이 매우 중요하다. TLB에 새로운 항목을 탑재할 때, 현재 존재하는 항목 중 하나를 교체 대상으로 선정해야 한다.
• 한 가지 흔한 방법은 최저 사용 빈도(LRU : least - recently - used) 항목을 교체하는 것이다. LRU는 메모리 참조 패턴에서의 지역성을 최대한 활용하는 것이 목적이다. 사용된지 오래된 항목일 수록, 앞으로도 사용될 가능성이 작으며, 교체 대상으로 적합하다는 가정에 근거한다. 또 다른 일반적인 방법은 랜덤 정책이다. 랜덤 정책에서는 교체 대상을 무작위로 정한다. 랜덤 교체 정책은 때때로 잘못된 결정을 내릴 수도 있다. 하지만, 랜덤 교체 정책은 구현이 간단하고 예상치 못한 예외 상황의 발생을 피할 수 있다는 장점이 있다. LRU는 모든 접근에 대해 미스를 유발한다. 그에 반해 랜덤의 경우에는 훨씬 더 잘 동작한다.