본 글의 내용은 Operating Systems: Three Easy Pieces의 Paging: Smaller Tables 챕터를 정리한 것입니다.

☑️ 개요

• 페이징으로 발생할 수 있는 문제는 페이지 테이블이 너무 커서 메모리를 많이 소모할 수도 있다는 것이다.

• 32비트 주소 공간에 페이지 크기가 4KB라면, VPN이 20비트가 되고, PTE의 크기가 4바이트 일 때, 페이지 테이블의 크기가 4MB(2^20*4)가 된다. 또한 프로세스마다 한 페이지 테이블이 존재하기 때문에, 프로세스의 개수가 늘어날 수록 페이지 테이블이 차지하는 메모리 양이 굉장히 커지게 된다.

☑️ 간단한 솔루션: 더 큰 페이지

• 이것을 해결할 방법은 더 큰 페이지를 사용하는 것이다.

• 32비트 주소 공간에, 16KB 페이지를 사용하면 VPN은 18비트가 되기 때문에 페이지 테이블의 크기는 1MB(2^18*4)로 줄어든다.

• 그러나 이 접근 방식은 또 다른 문제점을 야기하는데 그것은 페이지 내에 낭비되는 영역이 발생한다는 것이고, 이를 내부 단편화라고 한다.

• 따라서 대부분의 시스템은 일반적으로 작은 페이지 크기를 사용하며, 내부 단편화 문제는 간단하게 해결되지 않는다.

☑️ 하이브리드 접근

• 다른 방법으로는 페이징과 세그먼테이션을 결합하는 것이다.

• 페이징이 메모리를 낭비하게 되는 이유는 사용하지 않는 PTE도 메모리에 존재한다는 것에 있다. 그래서 전체 주소 공간에 단일 페이지 테이블을 사용하는 대신, 논리적인 세그먼트마다 하나의 페이지 테이블을 사용하는 접근을 할 수 있다.

• 이렇게 접근을 하면 base&bound 레지스터는 각 세그먼트의 페이지 테이블 물리 주소를 보관하게 된다.

• 그래서 주소의 상위 비트에 세그먼트를 가리키는 비트가 생긴다. TLB 미스가 발생하면 이 세그먼트 비트를 사용해 어떤 base&bound 레지스터를 사용할지 결정하고, 해당 세그먼트의 페이지 테이블에 접근한다.

• bound 레지스터는 최대 유효 페이지의 값을 저장하는데, 예를 들어 코드 세그먼트가 첫 3페이지(0, 1, 2)를 사용한다면 바운드 레지스터는 3으로 설정된다. 이 덕에 메모리를 상당히 절약하게 된다.

• 하지만 이것에도 문제가 있는데, 유연성이 부족하다는 것이다. 예를 들어 힙이 크지만 사용 빈도가 낮은 경우, 많은 메모리가 낭비된다.

• 그리고 세그먼테이션의 단점처럼 다시 외부 단편화를 발생시킨다. 페이지 테이블의 크기는 PTE의 배수가 될 수 있는데, 이로 인해 여유 공간을 찾는 게 더 복잡해진다.

☑️ Multi Level Page Table

• 다른 방법으로 유효하지 않은 영역을 메모리에서 모두 제거하는 것이 있다. 이것을 Multi level page table(다단계 페이지 테이블)이라고 부르는데, 선형적인 페이지 테이블을 트리와 같은 형태로 바꾼다.

• 다단계 페이지 테이블은 간단하게, 페이지 테이블을 페이지 크기 단위로 잘라낸 후, 유효하지 않은 PTE만 가지고 있는 페이지 테이블에게 메모리를 전혀 할당하지 않는다.

• 이때 페이지 디렉토리라는 새로운 구조를 사용하는데, 페이지 테이블의 전체 항목이 유효하지 않은 지를 확인한다.

• 위 그림으로 다단계 페이지 테이블의 구조를 확인할 수 있다. 페이지 디렉토리는 여러 개의 페이지 디렉터리 항목(PDE)로 구성된다.

• PDE에는 유효 비트, PFN이 존재하며, PTE와 유사하다고 할 수 있다. 여기서 유효 비트는 가리키는 페이지 테이블에 유효한 PTE가 최소한 하나라도 존재하는 지에 대한 여부를 의미한다.

• 이런 구조 덕분에 생기는 장점은 첫째로, 사용 중인 페이지 테이블만 메모리를 할당한다는 것이다.

• 둘째로 페이지 테이블을 신중하게 구축하면, 페이지 테이블이 한 페이지에 담기도록 할 수 있고 메모리 관리를 쉽게할 수 있다. 페이지 테이블을 새롭게 할당하거나 늘리려고 할 때 여유 페이지 하나만 더 가져오면 된다.

• 이런 다단계 페이지 테이블도 단점이 있는데, TLB 미스가 발생할 때 디렉토리용, PTE용 메모리 참조가 발생하여 두 번 로드해야 된다. (이것은 시간-공간 절충의 예시라고 할 수 있다)

• 또한 복잡해진다. 단순한 선형 페이지 테이블보다 복잡할 수 밖에 없다. 성능 개선 혹은 공간 절약을 위해 페이지 테이블 조회를 더 복잡하게 만들기도 한다.

☑️ 다단계 페이지 테이블 예시

• 위 그림이 페이지당 64바이트, 16KB의 주소 공간이라고 생각해보자.

• 따라서 오프셋은 6비트(2^6=64)가 되며, VPN은 8비트가 된다. 즉 페이지 테이블에 256(2^8)개의 PTE가 존재한다.

• PTE가 4바이트라면 페이지 테이블의 크기는 1KB(256 * 4B)가 된다. 또한 페이지가 64바이트이기 때문에 페이지마다 16개의 PTE를 담을 수 있다.

• 이제 VPN을 통해 페이지 디렉토리 인덱스를 얻어내야 하는데, 1KB의 페이지 테이블은 64바이트의 페이지가 16개로 이룰 수 있다. 한 페이지당 하나의 페이지 테이블을 할당하므로 PDE는 16개가 되고, 이는 VPN의 상위 4비트를 사용하면 된다.

• 페이지 디렉토리 인덱스를 통해 페이지 테이블을 찾으면, 이제 PTE 인덱스를 알아야 하는데, 이것을 VPN 하위 4비트에서 얻어낸다.

• 결과적으로 PTE 주소를 찾는 것은 위와 같은 과정을 거친다고 할 수 있다.

• 위 다단계 페이지 테이블을 통해 예시를 들 수 있다. VPN이 254라면, 16진수로 0x3F80 , 즉 11 1111 1000 0000 나타나지는데, 상위 4비트는 1111 이므로 15번째 PDE를 선택하게 된다.

• 그럼 PFN을 101 로 가리키고 있고, 하위 4비트는 1110 이므로 PFN 101 의 페이지 테이블에 찾아가 14번째 인덱스를 참조하면 PFN 55 를 발견하게 된다.

☑️ 두 개 이상의 단계

• 30비트의 가상 주소 공간과, 각 페이지의 크기가 512바이트라고 가정해보자.

• 그럼 오프셋 비트는 9비트(2^9=512)가 되고, VPN 비트는 21비트가 된다.

• PTE의 크기가 4바이트라면, 한 페이지에는 128개가 들어갈 수 있다. 그럼 우선적으로 VPN 비트의 최하위 7비트(2^7=128)가 PTE를 위해 사용된다고 생각할 수 있다. (각 페이지 테이블이 하나의 페이지에 들어가는 것을 목표로 하고 있음을 기억하자)

• 이제 상위 14비트가 남아있는데, 만약 2^14개의 PDE를 사용하게 되면 한 페이지에 한 테이블을 할당하겠다는 목표에 어긋나게 된다. 또한 페이지 디렉토리에 한 페이지가 아니라 128 페이지(2^14 * 4 / 2^9)를 사용하게 된다.

• 그래서 또 다른 페이지 디렉토리를 추가해야 한다. 최상위 7비트를 PDE로 사용하면 512바이트(2^7*4)로 한 페이지의 크기가 되고, 그 다음 페이지 디렉토리도 마찬가지다.

☑️ 주소 변환 과정: TLB 잊지 말기

• 위 코드에서 볼 수 있듯이, 페이지 테이블 접근 이전에 먼저 TLB를 확인한다.

• TLB 미스가 발생하면 모든 레벨의 페이지 테이블 조회를 수행해야 한다.

☑️ 거꾸로 된 페이지 테이블

• 극단적인 공간 절약을 위해 역 페이지 테이블(Inverted page table)을 사용하기도 한다.

• 이 방식은 프로세스당 하나의 페이지 테이블을 사용하지 않고, 각 물리 페이지에 대한 항목을 기록하는 단일 페이지 테이블을 사용한다.

• 해당 물리 페이지 항목은 특정 프로세스의 어떤 가상 페이지가 대응되는지를 알려준다.

• 이 방식은 선형 스캔이 비용이 많이 들기 때문에, 기본 구조 위에 해시 테이블을 사용하기도 한다.

• 결론적으로 페이지 테이블은 데이터 구조일 뿐이다. 더 작거나 크게 만들 수 있고, 느리거나 빠르게 만들 수 있다.

☑️ 페이지 테이블 스와핑

• 지금까지는 페이지 테이블이 물리 메모리에만 있다고 가정하였으나, 페이지 테이블이 너무 커서 한 번에 메모리에 들어갈 수 없는 경우가 많다.

• 따라서 테이블을 가상 메모리에 배치하여 메모리가 부족할 때 일부를 디스크로 스왑한다.

✅ 요약

• 단일 페이지 테이블은 유효하지 않은 PTE 또한 유지해야 하기 때문에 메모리 낭비가 발생한다.

• 이를 해결하기 위해 Multi level page table이 도입되었으며, 페이지 디렉토리가 PDE를 관리하며, 유효하지 않은 PDE는 페이지 테이블을 만들지 않는다.

• 다만 중첩된 페이지 테이블을 만드는 것으로 공간을 절약하면 TLB 미스 상황에서 더 많은 메모리 참조가 발생하면서 시간상 손해가 생긴다.

• 올바른 구조 선택은 주어진 환경에 따라 달라지며, 메모리가 제한된 시스템이라면 작은 구조가 좋겠지만, 많은 페이지를 적극적으로 사용하는 시스템에서는 TLB 미스 속도를 높이는 게 더 올바른 선택이 된다.