[운영체제] Page table의 3가지 구조 - Hierarchical, Hashed, Inverted Page table

 

목차

• 🐤  계층적 페이지 테이블 (Hierarchical page table)
• 🐦  해시 페이지 테이블 (Hashed page table)
• 🐧  역페이지 테이블 (Inverted page table)

 

페이징(Paging)이란?

[운영체제] 비연속할당(Noncontiguous allocation) - 페이징(Paging)

 

페이징(Paging)은 외부 단편화를 해결하고 메모리를 효율적으로 사용할 수 있는 장점이 있습니다.

하지만, 이러한 페이징에도 큰 문제점이 하나 존재합니다.

 

Page table이 메모리에 함께 적재되면서 많은 크기를 차지한다는 부분이었습니다.

32-bit 운영체제에서 CPU가 만들어내는 논리 주소의 크기는 32bits이며, Page의 사이즈는 2^12(4KB)이므로 나머지 20개의 bit는 페이지의 최대 개수라고 할 수 있습니다.

 

만약, 2^20 = 1M(대략 100만)개의 페이지가 있다면, Page table 또한 각 페이지들이 물리 주소와 매핑될 수 있도록 1M개의 Page entry를 가지고 있어야 합니다.

각 Page table entry가 최소한의 사상 정보인 frame number(Integer 형태 가정)만을 가지고 있다고 하더라도 한 페이지 테이블의 크기는 4MB(= 4Byte * 1M)입니다.

100개의 프로세스를 실행시킨다면 400MB의 페이지 테이블이 물리 메모리 공간을 차지합니다.

 

극단적으로 64-bit 운영체제에서는 Page의 사이즈가 8KB(2^13)이며, 나머지 51개의 bit가 page number를 나타내는 용도로 사용됩니다. 그렇다는 것은 page entry가 2^51개 존재해야 함을 의미합니다...

 

메모리는 한정적인 자원이기 때문에 400MB만큼 내어줄 정도로 여유롭지 않습니다.

그렇기 때문에 이러한 메모리 공간의 비효율적인 사용을 가능한 효율적으로 사용할 수 있도록 제시된 3가지 Page table이 있습니다.

 

 

 

🐤   계층적 페이지 테이블 (Hierarchical page table)

계층적 페이지는 기존에 프로세스 하나당 하나의 Page table을 사용하던 것을 여러 개로 나누어 사용하는 방식을 의미합니다.

계층을 나눈 횟수만큼 level이 증가하여 두 번 나누었다면 2-level page table, 세 번 나누었다면 3-level page table이라는 이름을 붙입니다.

 

'계층적 페이지 테이블을 사용할 때 Logical address의 구조'

2-level page table을 기준으로 살펴보겠습니다.

만약, page number가 22bits만큼 차지하고 있었다면, 2-level page table에서는 2개로 나누어 사용합니다.

즉, 페이지 테이블이 2개가 존재한다는 것을 의미하는데, 여기서 바깥쪽 페이지 테이블을 Outer page table, 안쪽 페이지 테이블을 Inner page table이라고 부릅니다.

 

 

'주소 변환 과정'

기존 Page table에서 주소 변환시, 아래와 같이 총 2단계를 거쳤습니다.

1. 메모리의 Page table을 참조한다.

2. 변환된 물리 주소를 바탕으로 메모리를 참조한다.

 

하지만 계층적 페이지 테이블은 Page table이 하나 더 늘어난 만큼 과정이 하나 추가됩니다.

우선, Outer page number(p1)는 Outer page table의 Index를 의미하는데, MMU는 이를 바탕으로 Inner page table을 인덱싱합니다.

Inner page number(p2)는 Inner page table의 Index를 의미하며, 이를 바탕으로 Page table entry를 찾고 Offset(d)과 함께 최종 물리 주소로 변환하는 과정을 거칩니다.

 

바깥부터 안쪽으로 향한다는 의미에서 forward-mapped page table이라고도 부릅니다.

 

2^22개의 page table entry를 2^12 + 2^10으로 대폭 줄일 수 있다는 장점을 가지고 있습니다.

또한, 페이지 테이블을 Paging하기 때문에 기존에 메모리를 효율적으로 사용할 수 있습니다.

 

하지만, 계층을 나누면 나눌수록 페이지 테이블의 크기는 줄어들지만 개수는 늘어나게 됩니다.

다시 말해, 각 페이지 테이블을 참조하기 위해 level이 커질 수록 메모리를 자주 참조해주어야 한다는 단점이 발생합니다.

ex) 2-level page table : 사상 한 번당 메모리 3번 참조

• outer page table 참조 1회
• inner page table 참조 1회
• 최종 변환된 물리 주소 참조 1회

 

 

🐦   해시 페이지 테이블 (Hashed page table)

'Hashed page table 구조'

해시 페이지 테이블은 Page number에 해시 함수를 적용한 값을 바탕으로 Hash table의 entry를 참조합니다.

만약 해시 함수를 적용한 값이 동일한 Entry에 대해서는 충돌(collision)이 발생하게 됩니다.

이를 해결하기 위해 Hash page table의 Entry는 Linked list 자료구조를 사용합니다.

 

그림처럼 특정 entry는 Linked list로 연결되어 있음을 확인할 수 있습니다.

처음부터 하나씩 page number를 비교하면서 동일한 값을 찾을 때까지 연결리스트를 따라가면서 탐색을 합니다.

 

Hash table과 Linked list를 사용하기 때문에 반드시 page의 개수만큼 entry가 필요하지 않기 때문에 크기를 줄일 수 있습니다.

만약 linked list의 크기가 5라면 기존 Page table보다 5배만큼 크기를 줄일 수 있습니다.

 

 

 

🐧   역페이지 테이블 (Inverted page table)

'Inverted page table 구조'

Page table의 문제는 한 프로세스당 Page table을 가지고 있어야 하기 때문에, 사용되지 않는 page가 있더라도 어찌됐든 page의 최대 개수만큼 page table entry를 가지고 있어야 했습니다.

이러한 문제를 해결하기 위해 등장한 개념이 Inverted page table입니다.

 

역페이지 테이블은 물리 메모리를 그대로 사상하고 있으며, 모든 프로세스가 하나의 페이지 테이블을 참조합니다.

그렇기 때문에 페이지 테이블의 entry 개수는 물리 메모리의 frame 개수와 동일하며 고정되어 있다는 점이 특징입니다.

 

모든 프로세스가 역페이지 테이블을 참조하기 때문에, 어떤 프로세스의 사상 정보를 가지고 있는지 구분하기 위해 pid를 함께 사용하여 참조합니다. 0번째 entry부터 순차적으로 pid와 page number를 비교하며 탐색하며, 일치하는 page table entry를 발견했을 때의 인덱스가 곧 frame number가 됩니다.

그 이유는 역페이지 테이블이 물리 메모리를 그대로 사상했기 때문에, i번째 index가 i번째 frame number와 동일하기 때문입니다.

 

페이지를 고정 크기로 관리하며, 페이지 테이블의 크기를 줄일 수 있다는 장점을 가지고 있습니다.

하지만, 기존에 page table에서 entry를 인덱싱하는 방식과 달리, pid와 page number를 비교하며 순차 탐색하기 때문에 O(n)만큼의 시간 복잡도가 소요됩니다.

최악의 경우 탐색하고자 하는 entry가 n-1번째에 위치한다면, 탐색에 많은 시간이 소요됩니다.

 

 

 

 

 

github : https://github.com/tmdgh1592

tmdgh1592 - Overview