저번 시간에 '풀리지 않은 의문점'에서 페이지 테이블은 연속적이기 때문에 페이지 테이블을 새롭게 디자인할 필요가 있다고 했었다. 따라서 오늘은 페이지 테이블의 세 가지 구조를 다룬다. 세 가지 구조는 각각 아래와 같다. 이 글의 목차로 생각하면 된다.
1. 계층적 페이지 테이블 (Hierarchical Page Table)
2. 해시형 페이지 테이블 (Hashed Page Table)
3. 역페이지 테이블 (Inverted Page Table)
1. 계층적 페이지 테이블 (Hierarchical Page Table)
우선 페이지 테이블이 연속적일 경우 어떤 문제가 발생하는지 보자. 일반적으로 페이지의 크기는 4KB(2^12 B)로 잡는다. 32 비트 주소 체계와 64비트 주소 체계인 경우 페이지 테이블의 용량이 어떻게 되는지 보자.
1. 32 bit 주소체계
페이지 테이블 주소 공간 = 32 - 12 (bit) = 20 (bit)
페이지 테이블 용량 = 2^20 * 4byte = 4MB
※ 1 entry = 1 word = 32 bit = 4 byte
※ 2^20 개의 entry = 2^20 * 4byte
2. 64 bit 주소체계
페이지 테이블 주소 공간 = 64 - 12 (bit) = 52 (bit)
페이지 테이블 용량 = 2^52 * 8byte = 36PB
※ 1 entry = 1 word = 64 bit = 8 byte
※ 2^52 개의 entry = 2^52 * 8byte
32bit 주소체계까지는 납득이 된다. 페이지 테이블당 4MB정도... 많이 크기는 하지만 일단 오케이! 그런데 64비트 주소체계에서는 페이지 테이블당 무려 36PB를 잡아먹는다. 그것도 무려 '연속적인' 36PB 공간이 필요하다. 이는 말도 안 된다. 이에 대한 대안이 계층적 페이지 테이블이다. Page number를 다시 두 부분으로 나눠 페이지 테이블의 페이지 테이블을 만드는 것이다. 두 부분으로 나누면 2계층 페이지 테이블고, 세 부분으로 나누면 3계층 페이지 테이블이다. 2계층 페이지 테이블을 그림으로 나타내면 아래와 같다.
가장 상위 테이블을 'outer page table'이라 부르고, 그 하위에 있는 페이지 테이블을 'inner page table'이라고 부른다. outer page table 입장에서는 inner page table이 하나의 페이지기 때문에 inner page table은 물리적 메모리에 불연속적으로 할당될 수 있다.
2계층 페이지 테이블의 원리를 좀 더 자세히 살펴보자. 원리는 간단하다. 페이지 테이블이 한 개일 경우 논리적 주소를 두 부분으로 나눴듯이 page number를 다시 두 부분으로 나누면 된다. 말로 하면 헷갈리니깐 그림으로 보자.
위 그림은 32bit 주소체계에서 페이지 크기가 12인 경우 2계층 페이지 테이블 예시다. 'PT Number'는 outer page table의 인덱스가 될 것이고, 'PT Offset'은 inner page table의 몇번째 entry에 해당하는지에 대한 값이 될 것이다.
페이지 테이블의 용량은 어떻게 변했는지 살펴보자. Outer page table의 용량은 2^10 byte = 1KB로 대폭 감소했고, inner page table의 용량도 2^10 * byte = 1KB로 대폭 감소했다. 여기서 한 가지 아주 재미있는 사실을 발견할 수 있다. 저번 시간에 메모리의 프레임은 '페이지 크기'를 기준으로 한다고 했었다. 따라서 메모리 단위는 '페이지 크기'가 된다. 위 예시에서 우리는 페이지 크기를 '4KB'로 설정했고, outer page table과 inner page table의 용량도 '1KB'임을 확인했다 . 괜히 32비트를 10, 10, 12로 나눈 것이 아니라는 말이다. outer page table과 Inner page table의 크기를 프레임의 크기에 맞춘 것이다.
주저리 주저리 말이 좀 길어졌는데 계층적 페이지 테이블 핵심만 정리하면 아래와 같다.
1. 연속된 페이지 테이블의 크기를 대폭 감소시키는 효과
2. Outer page table만 커널 메모리에 저장
2. 해시형 페이지 테이블 (Hashed Page Table)
화질이 안 좋지만 이만한 그림이 없어서 첨부한다. 강의 시간에 교수님이 강의자료에 없는 자료를 가져와서 캡쳐해둔건데 이렇게 쓰일줄은 몰랐다. 해시형 페이지 테이블은 말 그대로 해시 테이블을 이용하는 방법이다. Page Number의 해시값으로 Hash Table에 접근한 뒤 연결리스트에서 Page Number와 일치하는 원소를 찾는 방식이다. 약간만 더 자세히 보면 아래와 같다.
위 그림과 같이 해시 페이지 테이블의 각 항목은 연결 리스트를 가지고 있다. 해시 원소는 세 개의 필드(가상 페이지 번호, 매핑 프레임 번호, 다음 원소 포인터)를 가지고 있다. 아래는 해시 알고리즘을 정리한 것이다.
1. Page Number 해싱
2. 해시 페이지 테이블에서 연결 리스트를 따라가며 첫 번째 필드값과 page number를 비교
---- 일치하면 그에 대응하는 프레임 번호(두번째 필드)를 가져와 물리적 주소를 얻는다
---- 일치하지 않으면 연결 리스트의 그 다음 포인터로 2번 반복
3. 역페이지 테이블 (Inverted Page Table)
메모리에 하나의 고정 크기 페이지 테이블만 두는 방법이다. 모든 프로세스는 하나의 페이지 테이블만 참조한다. 따라서 페이지 테이블의 엔트리 개수는 메모리의 프레임 수와 같다. 페이지 테이블 하나가 메인 메모리에 그대로 사상되기 때문에 페이지 테이블의 인덱스는 메인 메모리의 프레임 순서와 같다. 즉, 페이지 테이블의 f번째 엔트리는 메인 메모리의 f번째 프레임에 대한 사상 정보를 가지는 것이다.
위 그림이 역페이지 테이블을 아주 잘 나타내는 그림이다. 아주 열심히 그렸다.. 이제 모든 페이지는 'PID + page number'라는 고유 식별 정보를 갖는다. 이 고유 정보는 페이지 테이블에 저장되어 있고, 페이지 테이블의 인덱스로 메인 메모리의 프레임 위치를 찾은 뒤 페이지의 오프셋으로 데이터에 접근할 수 있다. 모든 프로세스는 하나의 페이지 테이블만 공유하고, 각각의 페이지는 하나의 프레임에 대응된다.
페이지 테이블의 크기가 굉장히 줄어들었다는 점은 좋지만, 치명적인 단점이 두 개 있다.
1. 메모리 공유 불가
모든 페이지와 프레임은 일대일 대응 관계이므로 프로세스간 메모리 공유가 불가능하다. 같은 프로세스 안에서도 페이지가 다르면 데이터 공유가 불가능한 상황이 발생한다.
2. 페이지 테이블 참조 오버헤드
주소의 사상은 굉장히 빈번하게 일어난다. 그런데 역페이지 테이블 방식은 사상을 할때마다 페이지 테이블에서 'pid / p' 값을 찾아야 한다. 최악의 경우 페이지 테이블의 끝까지 탐색할 수 있기 때문에 오버헤드가 굉장히 심하다. 왜 탐색을 해야할까? 그 이유는 페이지 테이블의 인덱스가 가지는 의미가 달라졌기 때문이다. 프로세스마다 페이지 테이블을 가지는 경우 페이지 테이블의 인덱스는 논리적 주소의 page number와 일치하기 때문에 바로 접근할 수 있다. 하지만 역페이지 테이블은 인덱스가 물리적 메모리의 프레임 위치기 때문에 논리적 주소로 바로 접근할 수 없다.
그러면 역페이지 테이블의 크기는 어떻게 구할까? 역페이지 테이블은 논리적 메모리가 아닌 물리적 메모리를 기준으로 한다는 것을 기억하고 있어야 한다. 아래 예제를 풀어보자. 정답은 접은글 펼치기를 하면 볼 수 있다.
Logical Address Space : 48 bit
Page Size : 2KB
Physical memory : 1GB
역페이지 테이블의 엔트리 개수는?
역페이지 테이블 엔트리 개수 = physical address space / page size
Physical address space = 1GB = 2^30
Page size = 2^11
Number of entries =2^(30-11) = 2^19 = 512K entries.
이번 글은 여기까지! 다음 글은 페이징의 단점과 해결 방법으로 다시 돌아오겠다.
