페이지 테이블의 구조 (Structure of the Page Table)

페이지 테이블의 구조 (Structure of the Page Table)

1. 계층적 페이징(Hierarchical Paging)

대부분 현대 컴퓨터는 매우 큰 논리 주소 공간(2^32에서 2^64)을 지원한다. 이러한 환경에서는 페이지 테이블 자체가 상당히 커진다. 예를 들어, 32비트 논리 주소 공간을 가진 시스템을 생각해보자. 이 시스템에서 페이지의 크기가 4KB(2^12)라면 페이지 테이블은 약 100만(2^32/2^12)개의 항목으로 구성될 것이다. 각 항목은 다시 4B로 구성되기 때문에 각 프로세스는 페이지 테이블 하나만을 저장하기 위하여 4MB의 물리 주소 공간이 필요할 것이다. 이 경우, 모든 페이지 테이블을 주 메모리에서 연속적으로 할당하기를 바라지는 않을 것이다. 한 가지 간단한 해결 방법은 페이지 테이블을 여러 개의 작은 조각으로 나누는 것인데, 이것도 여러 가지 방법으로 가능하다.

한 가지 방법은 2단계 페이징 기법(two-level paging scheme)을 사용하는 것으로, 페이지 테이블 자체가 다시 페이징되는 것이다. 아래의 이미지는 바로 2단계 페이징 기법을 시각화한 것이다.

위에서 언급했던 페이지 크기가 4KB인 32비트 기계의 예를 다시 들어보자. 이 경우, 논리 주소는 20비트짜리 페이지 번호와 12비트짜리 페이지 변위로 구성된다. 이제는 페이지 테이블도 페이지로 나누어지기 때문에 페이지 번호는 다시 10비트짜리 페이지 번호와 10비트짜리 페이지 변위로 나누어진다. 즉, 논리주소는 다음과 같이 된다.

여기서, p1은 바깥 페이지 테이블의 색인이고, p2는 바깥 페이지 테이블이 가리키고 있는 페이지 내의 변위이다.

위의 이미지는 이 계층적 페이징 구조에 의한 주소 변환 기법을 나타내고 있다. 이 방식에서는 주소 변환이 바깥 페이지 테이블에서 시작하여 안쪽으로 들어오므로 이 방식을 전방 사상 페이지 테이블(forward-mapped page table)이라고 한다.

2. 해시 페이지 테이블 (Hashed Page Table)

주소 공간이 32bit보다 크면 해시 값이 가상 페이지 번호가 되는해시형 페이지 테이블을 많이 쓴다. 해시형 테이블의 각 항목은 연결 리스트를 가지고 있다. 해시 원소는 세 개의 필드(가상 페이지 번호, 매핑 페이지 프레임 번호, 연결 리스트 상의 다음 포인터)를 가지고 있다.

해시 알고리즘은 다음과 같은 순서로 운영 된다.

1) 가상 주소 공간으로부터 페이지 번호가 오면 그것을 해싱 한다.

2) 해시형 페이지 테이블에서 연결 리스트를 따라가며 첫 번째 원소와 가상 페이지 번호를 비교한다.

3) 일치하면 그에 대응하는 페이지 프레임 번호(두번째 필드)를 가져와 물리적 주소를 얻는다.

4) 일치하지 않으면 연결 리스트의 그 다음 포인터로 3의 순서를 반복한다.

해시형 페이지에서 각 항목들이 한 개의 페이지만 가리키는 대신 64bit에서는 해시 알고리즘을 약간 변경하여 클러스터형 페이지 테이블이라고 하여 각 항목들이 여러 개의 페이지를 가리킨다. 따라서, 한 개의 페이지 테이블 항목이 여러 페이지 프레임에 대한 매핑 정보를 지닐 수 있다. 클러스터형 페이지 테이블은 메모리 접근이 불연속적이면서 전 주소 공간으로 넓게 퍼져 나오는 경우에 유용하다.

3. 역 페이지 테이블 (Inverted Page Table)

테이블은 가상 주소에 대해 오름차순으로 정렬되어 있으며 운영체제는 이 테이블에서 원하는 페이지가 어느 곳에 있는지 계산하여 접근한다. 이러한 기법의 단점으로는 페이지 테이블의 크기이다.이러한 문제를 해결하기 위해 역 페이지 테이블(inverted page table)방법을사용한다.

 

역 페이지 테이블에서는 메모리 프레임마다 한 항목씩 할당한다. 각 항목은 프레임에 올라와 있는 페이지 주소, 그리고 그 페이지를 소유하고 있는 프로세스 ID를 표시하고 있다. 이렇게 되면 시스템에는 단 하나의 페이지 테이블만이 존재하게 되고 테이블 내 각 항목은 메모리 한 프레임을 가리키게 된다.

- 역 페이지 테이블 구성 순서

1) 가상 주소는 <process-id,page-number, offset> 세 가지 항목으로 구성된다.

2) 각 역 페이지 테이블의 항목은<process-id, page-number>의 쌍으로 이루어져 있으며 process-id는 주소 공간 ID의 역할을 한다.

3) 메모리 참조가 발생하면 <process-id,page-number>의 쌍으로 이루어진 가상 주소의 일부 메모리 서브시스템에 전달 된다.

4) 역 페이지 테이블에서 일치하는 것이 있는지 검색 한다.

5) 일치하는 것이 i 번째 항목에서 발견되면 물리주소는 <i, offset>가 되고 일치 하는 것이 없으면 잘못된 메모리로 간주한다.

 

역 페이지 테이블의 장점으로는 논리 페이지마다 항목을 가지는 대신 물리 프레임에 대응되는 항목만 테이블에 저장하기 때문에 메모리에서훨씬 작은 공간을 점유 한다.

단점으로는 역 페이지 테이블은 주소 변환 시간이 더 오래 걸릴 수 있으며 프레임에 따라 저장되어있어 탐색은 비효율적이다.

페이지 테이블을 해싱이 느린경우 최근에 사용된 항목들을 TLB 연관메모리 레지스터에 저장시켜 다음 참조 시 레지스터만 검사하면서 시간을 단축 시킨다.

 

역 페이지 테이블을 사용하는 시스템에서 메모리의 공유는 어렵다. 페이지 테이블이 공유된 물리 주소에 대해 하나의 가상 주소를 매핑하기 때문에 매핑 되지 못한 다른 가상 주소가 공유된 영역을 참조하게 되면 페이지 폴트(page fault)가 발생 한다.