30_페이지 테이블 구조 (page table structure)

30_페이지 테이블 구조 (page table structure)

 

현대의 컴퓨터 환경에서는 매우 큰 주소 공간을 가진다. (2^32 ~ 2^64) 이러한 환경에서는 페이지 테이블도 커진다.

 

예를 들어 32bit 환경에서 페이지의 크기가 4KB(2^12)이면 페이지 테이블은 100만개(2^32/2^12)로 구성되며 각 항목은 4byte로 구성되기 때문에 각 프로세스는 페이지 테이블만해도 4MB가 필요하다.

 

[계층적 페이지]

큰 페이지 테이블은 작은 조각으로 나누어 관리하는 것이 효율적이며 이러한 방법을 2단계 페이징 기법(two-level paging scheme)이라 한다.

 

2단계 페이지 기법은 페이지 자체가 다시 페이지화 되는 것으로 4KB의 크기를 가진 32bit 환경을 예로 들면 논리주소는 20bit 짜리 페이지 번호와 12bit의 페이지 변위로 이루어 진다. 그리고 페이지 테이블도 페이지로 나누어 지기 때문에 페이지 번호는 다시 10bit짜리 페이지 번호와 10bit짜리 페이지 변위로 나누어 진다.

 

주소 변환이 바깥에서 안쪽으로 들어오므로 이러한 방식을 포워드 매핑 (forward-mapped)페이지 테이블이라고도 부른다.

 

VAX 구조가 2단계 페이징을 지원한다. VAX는 페이지 크기가 512byte이고 32bit 환경이다. 프로세스의 논리 주소 공간은 동일한 4개의 영역으로 나누어지는데 각각은 2^30byte로 구성된다. 각 영역은 다른 공간 부분을 나타내며 논리 주소의 처음 2개 bit는 영역을 표시, 다음의 21bit는 그 영역에서의 페이지 번호, 마지막 9bit는 선택된 페이지 내에서의 변위를 나타낸다.

VAX에서 하나의 영역을 사용하는 프로세스의 1단계 페이지 테이블의 크기는 2^21bit * 항목당 4byte = 8MB 이다. VAX는 메인 메모리 사용량을 줄이기 위해 사용자 페이지 테이블도 페이지화 한다.

 

64비트 논리 주소 공간을 가진 시스템은 페이지 테이블을 페이지화 하더라도 큰 페이지를 가지고 있기 때문에 바깥 페이지 테이블을 다시 작게(3단계 페이징) 나눈다. 아니면 2번째 바깥 페이지 테이블도 페이징 시킴으로써 4단계 페이징 기법을 사용 할 수 있다.

 

• 3단계 페이징 사용 시스템 – SPARC 구조
• 4단계 페이징 사용 시스템 – Motorola 68030
• 7단계 페이징 사용 시스템 – UltraSPARC (논리주소 매핑에 너무 많은 메모리 접근이 발생하여 비현실적)

 

 

[해시형 페이지 테이블(Hashed Page Table)]

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

 

 

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

1. 가상 주소 공간으로부터 페이지 번호가 오면 그것을 해싱 한다.
2. 해시형 페이지 테이블에서 연결 리스트랄 따라가며 첫 번째 원소와 가상 페이지 번호를 비교한다.
3. 일치하면 그에 대응하는 페이지 프레임 번호(두 번째 필드)를 가져와 물리적 주소를 얻는다.
4. 일치하지 않으면 연결 리스트의 그 다음 포인터로 3의 순서를 반복한다.

 

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

 

 

[역 페이지 테이블(Inverted Page Table)]

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

 

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

 

 

역 페이지 테이블 구성 순서

• 가상 주소는 <process-id, page-number, offset> 세 가지 항목으로 구성
• 각 역 페이지 테이블의 항목은 <process-id, page-number>의 쌍으로 이루어져 있으며 process-id느 주소 공간 ID의 역할을 한다.
• 메모리 참조가 발생하면 <process-id, page-number>의 쌍으로 이루어진 가상 주소의 일부 메모리 서브시스템에 전달 된다.
• 역 페이지 테이블에서 일치하는 것이 있는지 검색 한다.
• 일치하는 것이 i 번째 항목에서 발견되면 물리 주소는 <i, offset>가 되고 일치 하는 것이 없으면 잘못된 메모리로 간주 한다.

 

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

 

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

 

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

 

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

 

 

[참고자료]

Operating System Concepts / 홍릉과학출판사