운영체제의 메모리 관리 6 - Virtual Memory Hardware

이전 글에서는 가상 메모리의 개념과 그것이 동작 가능한 근거인 지역성 원칙을 다뤘습니다. 가상 메모리가 효과적으로 동작하려면 두 가지가 필요하다고 짚었는데, 그 중 하나가 하드웨어 지원이었습니다. 이번 글에서는 그 하드웨어 측면이 어떻게 구성되어있는지 알아보겠습니다.

Page Table Entry (PTE)

4편에서 다룬 페이지 테이블은 가장 단순한 형태로, 페이지 번호에 대응되는 프레임 번호만 담고 있었습니다. 가상 메모리가 도입된다면 이런 형태로는 충분한 정보를 저장하지 못합니다. 어떤 페이지는 메인 메모리에 있고, 어떤 페이지는 디스크에 스왑되어 있기 때문입니다. 운영체제는 매 메모리 참조마다 그 페이지가 실제로 적재된 상태인지 아닌지를 판별할 수 있어야 합니다.

이를 위해 페이지 테이블 엔트리Page Table Entry에는 프레임 번호 외에 존재 비트Present Bit, P가 추가되어야 합니다. 이 비트가 1이면 해당 페이지는 메인 메모리에 적재되어 있고, 0이면 디스크에 있다는 뜻입니다. 프로세서가 P=0인 페이지를 참조하면 페이지 폴트Page Fault가 발생하고, 운영체제가 인터럽트를 받아 디스크로부터 페이지를 가져옵니다.

또 하나 중요한 비트는 수정 비트Modify Bit, M 또는 더티 비트Dirty Bit라 불리는 비트입니다. 이 비트는 해당 페이지가 메모리에 적재된 이후 쓰기가 한 번이라도 일어났는지를 표시합니다. 페이지를 디스크로 내보낼 때 M=0이면 디스크의 원본과 메모리의 내용이 동일하므로 디스크에 다시 쓸 필요가 없습니다. 디스크 I/O 한 번을 통째로 절약할 수 있는 셈입니다.

이외에도 읽기/쓰기 권한이나 사용자/커널 모드 접근 권한 등 보호를 위한 비트들이 함께 들어갑니다. 결국 페이지 테이블 엔트리는 단순한 페이지 - 프레임 번호 매핑 테이블을 넘어서, 그 페이지에 대한 메타데이터 집합으로 확장됩니다.

Multi-level Page Table

가상 주소 공간이 커지면서 페이지 테이블 자체의 크기가 새로운 문제로 떠오릅니다. VAX 아키텍처를 예로 들면, 한 프로세스의 가상 주소 공간이 2^31 = 2GB이고 페이지 크기가 512 bytes(2^9)이므로, 한 프로세스당 2^22개(페이지 개수 = 가상 주소 공간 / 페이지 크기)의 페이지 테이블 엔트리가 필요합니다. PTE 1개 크기가 보통 4~8 bytes 정도이므로, 페이지 테이블만으로 16~32MB의 메모리가 필요합니다. 더군다나 멀티프로그래밍 환경에서는 프로세스마다 페이지 테이블이 필요하므로 메인 메모리는 페이지 테이블을 다 넣기에도 부족해질 것입니다.

해결 방법은 페이지 테이블 역시 가상 메모리에 두는 것입니다. 즉 페이지 테이블도 페이징의 대상으로 취급하는 것입니다. 프로세스가 실행될 때 그 시점에 필요한 페이지 테이블 일부만 메인 메모리에 있으면 되고, 나머지는 디스크에 둡니다.

이 아이디어를 실제로 구현한 형태가 다단계 페이지 테이블Multi-level Page Table입니다. 가장 흔한 두 단계 구조에서는 페이지 디렉토리Page Directory가 최상위에 위치하고, 디렉토리의 각 엔트리가 하위 페이지 테이블을 가리킵니다. 가상 주소는 [디렉토리 인덱스 | 페이지 테이블 인덱스 | 오프셋] 형태로 분할되고, 주소 변환은 디렉토리에서 한 번, 페이지 테이블에서 한 번, 총 두 번의 룩업을 거칩니다. 페이지 디렉토리만 메인 메모리에 상주시키고 하위 페이지 테이블들은 필요할 때만 적재하면, 한 프로세스가 차지하는 페이지 테이블 메모리를 크게 줄일 수 있습니다.

Inverted Page Table

다른 접근도 있습니다. 일반 페이지 테이블의 크기는 가상 주소 공간의 크기에 비례합니다. 그러나 어차피 메모리에 실제로 존재하는 프레임의 수는 물리 메모리 크기에 의해 정해져 있습니다. 그렇다면 가상 페이지가 아니라 물리 프레임을 기준으로 테이블을 만들면 어떨까요?

이런 발상에서 출발한 것이 역방향 페이지 테이블Inverted Page Table입니다. 테이블의 엔트리 수가 물리 프레임 수와 같아서, 가상 주소 공간이 아무리 커져도 테이블 자체의 크기는 일정합니다.

동작은 이렇게 굴러갑니다. 가상 주소를 [페이지 번호 | 오프셋]으로 쪼갠 뒤, 페이지 번호를 해시 함수에 넣어 테이블의 인덱스를 얻습니다. 그 위치의 엔트리에는 [가상 페이지 번호, 프로세스 ID, 컨트롤 비트, 체인 포인터]가 들어 있습니다. 엔트리에 적힌 페이지 번호와 프로세스 ID가 찾고 있는 값과 일치하면, 그 엔트리가 자리잡은 위치(인덱스) 자체가 곧 프레임 번호가 됩니다. 일반 페이지 테이블이 "엔트리의 내용"으로 프레임 번호를 알려주는 것과 달리, 역방향 페이지 테이블은 "엔트리의 위치"가 프레임 번호인 셈입니다. 해시 충돌로 다른 페이지가 그 자리에 먼저 들어가 있다면 체인 포인터를 따라가며 일치하는 엔트리를 찾습니다.

이러한 구조 때문에 한 가지 단점이 따라옵니다. 일반 페이지 테이블은 페이지 번호 하나로 한 번에 엔트리에 도달하지만, 역방향 페이지 테이블은 매 참조마다 해시 계산과 (충돌 시) 체인 탐색을 거쳐야 합니다. 테이블 크기를 절약한 대가로 변환 비용이 늘어난 것입니다.

Translation Lookaside Buffer (TLB)

여기까지 쌓아 올린 구조를 보면 한 가지 비용이 눈에 띕니다. 가상 주소를 물리 주소로 변환하기 위해 페이지 테이블을 읽어야 하는데, 페이지 테이블 자체도 메인 메모리에 있습니다. 결국 모든 메모리 참조는 메모리에 두 번 접근하는 셈이 됩니다. 한 번은 페이지 테이블 엔트리를 가져오기 위해, 또 한 번은 실제 데이터를 가져오기 위해 접근하며 메모리에 접근할 때 비용이 두배가 됩니다.

이 비용을 줄이기 위해 도입된 것이 TLBTranslation Lookaside Buffer입니다. TLB는 최근에 사용된 페이지 테이블 엔트리를 담아두는 작은 캐시로, 프로세서 내부 또는 메모리 관리 유닛MMU에 위치합니다. 캐시의 동작 원리와 똑같습니다.

가상 주소가 들어오면 메모리 관리 유닛은 먼저 TLB에 해당 페이지 번호의 엔트리가 있는지 확인합니다. 만약 있다면TLB hit 메인 메모리의 페이지 테이블을 읽지 않고 곧장 프레임 번호를 얻어 물리 주소를 만듭니다. TLB에 PTE가 없다면TLB miss 메인 메모리의 페이지 테이블을 읽어 엔트리를 가져오고, 그 결과를 TLB에 채워 넣은 뒤 다음 단계로 넘어갑니다. 이때 페이지 테이블에서 P=0인 엔트리를 만나면 페이지 폴트가 일어나 디스크 I/O로 페이지가 메모리에 적재되고, 페이지 테이블이 갱신된 뒤 다시 명령어가 재실행됩니다.

TLB가 효과적으로 동작하는 근거 역시 5편에서 다룬 지역성 원칙입니다. 프로세스의 메모리 참조가 군집을 이루기 때문에, 직전에 본 페이지를 다시 볼 확률이 높고, 작은 캐시로도 대부분의 참조를 흡수할 수 있습니다. 가상 메모리가 디스크와 메인 메모리 사이의 지역성을 활용한다면, TLB는 메인 메모리와 프로세서 사이의 지역성을 활용한다고 볼 수 있습니다.

TLB와 메모리 캐시의 공존

현대 시스템에는 가상 메모리 외에도 별도의 메모리 캐시Cache가 존재합니다. 둘은 다른 계층의 캐시이므로, 한 번의 메모리 참조에서 두 캐시를 모두 거칠 수 있습니다. 일반적인 흐름은 다음과 같습니다.

1. 가상 주소가 들어오면 TLB를 먼저 본다.
   1. TLB hit이면 곧바로 물리 주소를 생성한다.
   2. miss이면 페이지 테이블을 거쳐서, 물리 주소를 생성한다.
2. 이 물리 주소를 들고 메모리 캐시에 가서 해당 워드가 있는지 확인한다.
   1. 캐시 hit이면 그 값을 프로세서에게 돌려준다.
   2. 캐시 miss이면 메인 메모리에서 블록을 가져와 캐시에 적재한 뒤 돌려준다.

이 두 단계를 거치면서, 가장 빈번한 경로는 모두 프로세서 근처에서 끝납니다. 메인 메모리까지 내려가는 일은 드물고, 디스크까지 내려가는 일은 더더욱 드뭅니다. 이 계층 구조가 가상 메모리를 실용적으로 만들어주는 하드웨어적 토대입니다.

페이지 크기는 어떻게 정할까

마지막으로 짚어둘 것은 페이지 크기Page Size에 대한 트레이드오프입니다. 페이지를 작게 잡으면 내부 파편화가 줄어들지만, 한 프로세스당 페이지 수가 많아져 페이지 테이블이 커집니다. 페이지를 크게 잡으면 그 반대입니다. 또한 페이지가 너무 작으면 지역성 원칙이 깨지기 쉽고, 너무 크면 한 페이지에 별로 관계없는 코드와 데이터가 섞여 들어가 디스크 I/O 효율이 떨어질 수 있습니다. 대부분의 현대 시스템이 4KB 안팎의 페이지 크기를 기본으로 쓰는 것은 이런 균형점에서 자리잡은 결과입니다.

5편에서 가상 메모리가 실용적이려면 하드웨어 지원과 효율적인 소프트웨어, 두 가지가 모두 필요하다고 짚었습니다. 이번 글로 그 중 하드웨어 측면이 채워졌습니다. 다음 글에서는 나머지 한 축인 페이지 교체 알고리즘Page Replacement Algorithm들을 알아보겠습니다.