페이지 테이블의 세 가지 구조

페이지 테이블

앞선 포스팅에서 살펴본 페이지 테이블은 연속적이다. 용량이 다양한 메모리가 연속적으로 할당되는 것에 대해 외부 단편화라는 문제점이 있어서 페이징 기법을 도입하였다. 하지만 페이지 테이블이 연속적이면 모순되는 것이다.

 

하지만 말로만 들었을 때는 뭐가 문제이지?라는 생각을 할 수 있다. 그럼 먼저 페이지 테이블이 연속적일 경우에 어떤 문제가 발생하는 지부터 살펴보자.

연속적인 페이지 테이블

일반적으로 페이지의 크기는 4KB(=2^12Byte)로 잡는다. 32비트 주소 체계와 64비트 주소 체계의 경우 페이지 테이블의 용량이 어떻게 되는 지 살펴보자.

 

우선 아래는 가상 메모리 주소를 나타낸다. 가상 메모리 주소는 다음과 같이 page number와 offset으로 구성되어 있다. page number는 페이지의 개수와 연관이 있고, offset은 페이지의 크기와 연관이 있다.

 

이를 생각하면서 다음을 보자.

<32 bit 주소 체계>

페이지의 크기 = 4KB = 2^12 Byte (offset과 연관)
논리 메모리 주소 공간 = 32 - 12 bit = 20 bit (page number)
(전체 32비트에서 페이지의 크기인 12비트를 제외)
페이지 테이블 용량 = 2^20 * 4byte = 4MB

즉, page 개수가 2^20개이므로, page table의 entry 수는 2^20개이다.

1 entry = 1 word = 32 bit = 4 byte 이므로
2^20개의 entry = 2^20 * 4 byte 이다.

즉, 32 bit 주소 체계에서 테이블의 용량은 4MB이다.

<64 bit 주소 체계>

페이지의 크기 = 4KB = 2^12 Byte (offset와 연관)
논리 메모리 주소 공간 = 64 - 12 bit = 52 bit (page number)
(전체 64비트에서 페이지의 크기인 12비트를 제외)
페이지 테이블의 용량 = 2^52 * 8 byte = 36PB

즉, page 개수가 2^52개이므로, page table의 entry 수는 2^52개이다.

1 entry = 1 word = 64 bit = 8 byte 이므로
2^52개의 entry = 2^52 * 8 byte 이다.

즉, 64 bit 주소 체계에서 테이블의 용량은 36PB이다

 

32 bit 주소 체계까지는 페이지 테이블 당 용량이 4MB정도이므로 크긴 하지만 수용 가능하다. 하지만 64bit 주소 체계에서는 페이지 테이블 당 무려 36PB를 잡아먹는다. 그곳도 심지어 ‘연속적인’ 공간이어야 한다. 페이지 테이블은 프로세스 당 하나씩 생성되기 때문에 프로세스가 많아질수록 진짜 감당 불가능하다. 아니 사실 프로세스가 하나만 실행되더라도 36PB는 너무 크다.

 

이에 대한 대안으로 페이지 테이블의 구조를 다양하게 바꾸어볼 수 있다. 여기에 대해 살펴보자.

---

페이지 테이블 구조

페이지 테이블은 다음과 같이 세 가지 구조로 나타내 볼 수 있다.

계층적 페이지 테이블, Hierarchical Page Table

논리적 주소에서 page number 파트를 다시 일정 부분으로 나누어 페이지 테이블의 페이지 테이블을 만드는 방식이다.

 

즉, 두 부분으로 나누면 2계층 페이지 테이블이고, 세 부분으로 나누면 3계층 페이지 테이블이 된다. 2계층 페이지 테이블을 그림으로 나타내면 다음과 같다.

 

2계층 페이지 테이블 예시

가장 상위 테이블을 outer page table이라 부르고, 그 하위에 있는 페이지 테이블을 innter page table이라 부른다. outer page table 입장에서는 inner page table이 하나의 페이지이기 때문에 innter page table은 물리적 메모리에 불연속적으로 할당될 수 있다.

계층적 페이지 테이블의 원리

2계층 페이지 테이블의 원리를 좀 더 자세히 살펴보자. 페이지 테이블이 한 개일 경우 논리적 주소를 두 부분으로 나누었듯이, 계층을 추가하면 page number를 다시 두 부분으로 나누면 된다. 그림을 통해 확인해보자.

위 그림은 32bit 주소체계에서 페이지 크기가 12인 경우 2계층 페이지 테이블의 예시이다. PT는 page table을 줄여 쓴 것으로 위의 Page Number의 20비트를 10비트씩 각각 나누어 PT Number와 PT offset으로 나타내었다. PT Number가 outer page table의 인덱스가 될 것이고, PT Offset은 innser page table의 몇 번째 entry에 해당하는 지에 대한 값이 될 것이다.

---

해시형 페이지 테이블, Hashed Page Table

page number의 해시 값으로 hash table에 접근한 뒤 연결 리스트에서 page number와 일치하는 원소를 찾는 방식이다.

아래 그림을 보면 더 쉽게 이해할 수 있을 것이다.

 

논리 주소에서 page number에 해당하는 값을 hash function에 넣고, 반환 값을 해시 태이블의 index로 접근한다. 해당 위치에서 page number와 일치하는 원소를 찾을 수 있다.

 

조금 더 자세한 그림을 보자.

위 그림과 같이 해시 페이지 테이블의 각 항목은 연결 리스트를 가지고 있다. 연결 리스트에는 세 개의 필드(가상 페이지 번호, 매핑 물리 프레임 번호, 다음 원소 포인터)를 가지고 있다.

 

page number가 3227이라면 3227을 해시 함수에 넣어 12라는 해시 값을 얻는다. hash table에서 index 12에 접근하여 연결 리스트를 따라가며 page number가 3227에 해당하는 블록을 찾아 물리 주소를 구할 수 있다.

 

과정을 정리하면 다음과 같다.

1. Page number 해싱
2. 해시 페이지 테이블에서 해싱 값에 해당하는 인덱스로 접근
3. 연결 리스트를 따라가며 첫 번째 필드 값과 page number를 비교
   1. 일치하면 그에 대응하는 두 번째 필드 값인 frame 번호를 가져와 물리적 주소를 얻음
   2. 일치하지 않으면 연결 리스트의 그 다음 포인터로 이동하여 a 반복

---

역페이지 테이블, Inverted Page Table

메모리에 하나의 고정 크기 페이지 테이블만 두고, 모든 프로세스가 하나의 페이지 테이블을 이용하는 기법이다.

위 그림처럼 시스템에 하나의 페이지 테이블만 존재하며, 테이블 내 항목은 메모리의 한 프레임에 매핑된다. 모든 프로세스가 하나의 페이지 테이블을 참조하기 때문에 페이지 테이블 하나가 메인 메모리에 그대로 사상된다. 즉, 페이지 테이블의 인덱스가 메인 메모리의 프레임 순서와 같다.

 

논리 주소는 process id(pid), page number(p), offset(d)로 구성되어 있고,

물리 주소는 메모리 프레임 번호(i), offset(d)로 구성되어 있다.

 

주소 변환 절차는 다음과 같다.

1. 논리 주소에서 pid와 p를 보고 page table에서 같은 것을 찾는다
2. pid와 p가 일치하는 항목을 페이지 테이블의 index i에서 발견했다.
3. 메모리 프레임 번호(i)와 offset(d)를 기반으로 접근해야 할 메모리 주소를 확인한다.

단점

페이지 테이블의 크기가 굉장히 줄어들었다는 점은 좋지만, 치명적인 단점이 두 가지 있다.

메모리 공유 불가

 

모든 페이지와 프레임은 일대일 대응 관계이므로 프로세스간 메모리 공유가 불가능하다. 같은 프로세스 안에서도 페이지가 다르면 데이터 공유가 불가능한 상황이 발생한다.

페이지 테이블 참조 오버헤드

 

주소의 사상은 굉장히 빈번하게 일어난다. 그런데 역페이지 테이블 방식은 사상을 할 때마다 페이지 테이블에서 ‘pid, p’ 값을 찾아야 한다. 최악의 경우 테이블 끝까지 탐색 해야 할 수도 있기 때문에 오버헤드가 굉장히 심하다.

 

프로세스마다 페이지 테이블을 가지는 경우 페이지 테이블의 인덱스는 논리적 주소의 page number와 일치하기 때문에 바로 접근할 수 있다. 하지만 역페이지 테이블은 인덱스가 물리적 메모리의 프레임 위치이기 때문에 논리적 주소로 바로 접근할 수 없다.

---

참고자료

[ 운영체제 ] 메모리 관리2 - 페이지 테이블의 세 가지 구조