[운영체제] Chapter9.4 Structure of the Page Table

9.4.1 Hierarchical Paging

대부분의 최신 컴퓨터 시스템은 큰 논리적 주소 공간($2^{32}$ to $2^{64}$)을 지원한다. 이러한 환경에서, 페이지 테이블 자체가 지나치게 커진다. 예를 들어, 32bit 논리 주소 공간이 있는 시스템에서, 페이지의 크기가 4KB($2^{12}$)인 경우, 페이지 테이블은 100만 개 이상의 항목($2^{20}$ = $2^{32}$/$2^{12}$)으로 구성될 수 있다. 각 항목이 4byte로 구성되어 있다고 가정하면, 각 프로세스는 페이지 테이블만을 위해 최대 4MB의 물리적 주소 공간이 필요할 수 있다. 분명히, 메인 메모리에 페이지 테이블을 연속으로 할당하고 싶지 않을 것이다. 이 문제에 대한 간단한 해결책 중 하나는 페이지 테이블을 더 작은 조각으로 나누는 것이다. 여러 가지 방법으로 이 분할을 달성할 수 있다.

한 가지 방법은 2단계 페이징 알고리즘을 사용하는 것이다. 여기서 페이지 테이블 자체도 페이징된다(그림 9.15).

예를 들어, 32bit 논리 주소 공간과 4KB 페이지 크기를 가진 시스템을 생각해보면, 논리 주소는 20bit로 구성된 페이지 번호와 12bit로 구성된 페이지 오프셋으로 나뉜다. 페이지 테이블을 페이징하기 때문에, 페이지 번호는 10bit 페이지 번호와 10bit 페이지 오프셋으로 더 나뉜다. 따라서 논리 주소는 다음과 같다:

여기서 $p_1$은 외부 페이지 테이블의 인덱스이고 $p_2$는 내부 페이지 테이블의 페이지 변위이다. 이 아키텍처의 주소 변환 방법은 그림 9.16에 나와있다.

주소 변환은 외부 페이지 테이블에서 안쪽으로 작동하기 때문에, 이 방식은 forward-mapped 페이지 테이블이라고도 한다.

64bit 논리 주소 공간이 있는 시스템의 경우, 2단계 페이징 방식은 더 이상 적절하지 않다. 이 점을 설명하기 위해, 이러한 시스템의 페이지 크기를 4KB($2^{12}$)라고 가정하면, 페이지 테이블은 최대 $2^{52}$개의 항목으로 구성된다. 2단계 페이징 방식을 사용하면, 내부 페이지 테이블은 알맞게 한 페이지 길이가 되거나 $2^{10}$개의 4byte 항목을 포함할 수 있다. 주소는 다음과 같다:

외부 페이지 테이블은 $2^{42}$개의 항목, 즉 $2^{44}$ byte로 구성되어 있다. 이렇게 큰 테이블을 피하는 분명한 방법은 외부 페이지 테이블을 더 작은 조각으로 나누는 것이다.

다양한 방법으로 외부 페이지 테이블을 나눌 수 있는데, 예를 들어, 외부 페이지 테이블을 페이지화하여 3단계 페이징 방식을 제공할 수 있다. 외부 페이지 테이블이 표준 크기 페이지($2^{10}$개 항목 또는 $2^{12}$byte)로 구성되어 있다고 가정한다. 이 경우, 64bit 주소 공간은 여전히 어렵다:

외부 페이지 테이블의 크기는 여전히 $2^{34}$byte(16GB)이다.

다음 단계는 4단계 페이징 방식이다. 64bit UltraSPARC(스팍)는 각 논리 주소를 변환하기 위해 7단계 페이징이 필요하다. 이 예에서, 64bit 아키텍처의 경우, 계층적 페이지 테이블이 일반적으로 부적절하다고 간주되는 이유를 알 수 있다.

9.4.2 Hashed Page Tables

32bit보다 큰 주소 공간을 처리하기 위한 한 가지 접근 방식은 hashed page table을 사용하는 것이다. 해시 값은 가상 페이지 번호이다. 해시 테이블의 각 상목에는 공일한 위치로 해시되는 요소의 linked list가 포함된다. 각 요소는 세 개의 필드로 구성된다: (1)가상 페이지 번호, (2) 매핑된 페이지 프레임 값, (3)linked listㅢ 다음 요소에 대한 포인터

알고리즘은 다음과 같이 동작한다: 가상 주소의 가상 페이지 번호가 해시 테이블에 해시된다. 가상 페이지 번호는 linked list의 첫 번째 요소의 필드 1과 비교된다. 일치하는 경우 패당 페이지 프레임(필드2)을 사용하여 원하는 물리적 주소를 형성한다. 일치하는 게 없으면, linked list의 후속 항목을 검색하여 일치하는 가상 페이지 번호를 찾는다. 이 방법은 그림 9.17에 나와있다.

64bit 주소 공간에 유용한 이 방식의 변형이 제안되었다. 이 변형은 클러스터형 페이지 테이블을 사용하는데, 이는 해시형 페이지 테이블과 유사하지만 해시 테이블의 각 항목이 단일 페이지가 아닌 여러 페이지를 참조한다는 점이 다르다. 따라서, 단일 페이지 테이블 항목은 여러 물리적 페이지 프레임에 대한 매핑을 저장할 수 있다. 클러스터형 페이지 테이블은 메모리 참조가 비연속적이고, 주소 공간 전체에 분산되어 있는 희소 주소 공간에 특히 유용하다.

9.4.3 Inverted Page Tables

일반적으로, 각 프로세스에는 연관된 페이지 테이블이 있다. 페이지 테이블에는 사용하는 각 페이지에 대한 하나의 엔트리가 았다. 이 테이블 표현은 프로세스가 페이지의 가상 주소를 통해 페이지를 참조하기 때문에, 자연스러운 것이다. 그런 다음 운영체제는 이 참조를 물리적 메모리 주소로 변환해야 한다. 테이블이 가상 주소로 정렬되므로, 운영 체제는 연관된 물리적 주소 엔트리가 테이블 어디에 있는지 계산하고 해당 값을 직접 사용할 수 있다. 이 방법의 단점 중 하나는 각 페이지 테이블이 수백만개의 엔트리로 구성될 수 있다는 것이다. 이러한 테이블은 다른 물리적 메모리가 어떻게 사용되고 있는지 추적하기 위해 대량의 물리적 메모리를 소모할 수 있다.

이 문제를 해결하기 위해, inverted page table을 사용할 수 있다. 역 페이지 테이블에는 메모리의 각 실제 페이지에 대한 항목이 하나씩 있다. 각 항목은 실제 메모리 위치에 저장된 페이지의 가상 주소와 페이지를 소유한 프로세스의 정보로 구성된다. 따라서, 시스템에는 페이지 테이블이 하나만 있으며, 물리적 메모리의 각 페이지에 대한 항목이 하나만 있다. 그림 9.18은 역 페이지 테이블의 작동을 보여준다.

역 페이지 테이블은 종종 페이지 테이블의 각 항목에 주소 공간 식별자를 저장해야 한다. 이는 테이블이 물리적 메모리를 매핑하는 여러 다른 주소 공간을 포함하기 때문이다. 주소 공간 식별자를 저장하면 특정 프로세스의 논리적 페이지가 해당 물리적 페이지 프레임에 매핑된다. 역 페이지 테이블을 사용하는 시스템의 예로는 64bit UltraSPARC과 PowerPC가 있다.

이 방법을 설명하기 위해 IBM RT에서 사용되는 역 페이지 테이블의 단순화된 버전을 설명한다. IBM은 역 페이지 테이블을 사용한 최초의 주요 회사로, IBM System 38부터 시작하여 RS/6000과 현재 IBM Power CPUs까지 이어졌다. IBM RT의 경우, 시스템의 각 가상 주소는 트리플로 구성된다:
<process-id, page-number, offset>

각 역 페이지 테이블 항목은 <process-id, page-number> 쌍이며, 여기서 process-id는 주소 공간 식별자의 역할을 한다. 메모리 참조가 발생하면, <process-id, page-number>로 구성된 가상 주소의 일부가 메모리 하위 시스템에 제공된다. 그런 다음 역 페이지 테이블에서 일치 항목을 검색한다. 일치 항목이 발견되면, 물리적 주소 <$i$, offset>이 생성된다. 일치 항목이 발견되지 않으면, 불법 주소 액세스가 시도된 것이다.

이 방식은 각 페이지 테이블을 저장하는 데 필요한 메모리의 양을 줄이지만, 페이지 참조가 발생할 때 테이블을 검색하는 데 필요한 시간을 늘린다. 역 페이지 테이블은 물리적 주소로 정렬되지만, 조회는 가상 주소에서 발생하기 때문에 일치 항목을 찾기 전에 전체 테이블을 검색해야 할 수 있따. 이 검색은 너무 오래 걸린다. 이 문제를 완화하기 위해, 섹션 9.4.2에서 설명한 대로 해시 테이블을 사용하여, 검색을 하나의 페이지 항목으로 제한한다. 물론, 해시 테이블에 대한 각 액세스는 프로시저에 메모리 참조를 추가하므로, 하나의 가상 메모리 참조에는 적어도 두 개의 실제 메모리 읽기가 필요하다. 하나는 해시 테이블 항목, 하나는 페이지 테이블에 대한 것이다.

역 페이지 테이블과 관련된 흥미로운 이슈 중 하나는 공유 메모리와 관련이 있다. 표준 페이징을 사용하면, 각 프로세스가 고유한 페이지 테이블일 가지므로, 여러 가상 주소를 동일한 물리적 주소에 매핑할 수 있따. 이 방법은 역 페이지 테이블과 함께 사용할 수 없다; 모든 물리적 페이지에 대해 가상 페이지 항목이 하나만 있기 때문에, 물리적 페이지는 두 개 이상의 공유 가상 주소를 가질 수 없다. 따라서, 역 페이지 테이블에서는, 가상 주소와 공유 물리적 주소의 매핑이 주어진 시간에 하나만 발생할 수 있다. 메모리를 공유하는 다른 프로세스가 참조하면 페이지 오류가 발생하고 매핑이 다른 가상 주소로 대체된다.

9.4.4 Oracle SPARC Solaris

마지막 예로, 오버헤드가 낮은 가상 메모리를 제공하기 위해 타이트하게 통합된 최신 64bit CPU와 운영체제를 생각해보자. SPARC CPU에서 실행되는 Solaris는 완전한 64bit 운영 체제이므로, 여러 레벨의 페이지 테이블을 유지하여 모든 물리적 메모리를 사용하지 않고도 가장 메모리 문제를 해결해야 한다. 이 접근 방식은 약간 복잡하지만 hashed page table을 사용하여 문제를 효율적으로 해결한다. 커널용과 모든 사용자용 두 개의 해시 테이블이 있다. 각각 가상 메모리에서 물리적 메모리로 메모리 주소를 매핑한다. 각 해시 테이블 항목은 가상 메모리의 연속된 영역을 나타내며, 각 페이지마다 별도의 해시 테이블 항목을 갖는 것보다 더 효율적이다. 각 항목에는 기본 주소와 페이지 수를 나타내는 span이 있다.

각 주소가 해시 테이블을 검색해야 하는 경우, 가상에서 물리적 변환은 너무 오래 걸리므로, CPU는 빠른 하드웨어 조회를 위해 translation table entries(TTEs)를 보관하는 TLB를 구현한다. 이러한 TTEs의 캐시는 최근에 액세스한 페이지당 항목이 포함된 translation storage buffer(TSB)에 상주한다. 가상 주소 참조가 발생하면, 하드웨어는 TLB에서 변환을 검색한다. 아무것도 발견되지 않으면, 하드웨어는 메모리 내 TSB를 탐색하여 조회를 발생시킨 가상 주소에 해당하는 TTE를 찾는다. 이 TLB 탐색 기능은 많은 최신 CPU에서 찾을 수 있다. TSB에서 일치 항목을 찾으면, CPU는 TSB 항목을 TLB에 복사하고 메모리 변환이 완료된다. TSB에서 일치하는 항목을 찾지 못하면, 커널이 중단되어 해시 테이블을 검색한다. 그런 다음 커널은 적절한 해시 테이블에서 TTE를 만들고, CPU 메모리 관리 장치가 TLB에 자동으로 로드할 수 있도록 TSB에 저장한다. 마지막으로, 인터럽트 핸들러는 제어권을 MMU로 반환하고, MMU는 주소 변환을 완료하고 메인 메모리에서 요청된 바이트나 단어를 검색한다.