[OS] 메인 메모리(4) - 페이지 테이블의 구조(Structure of the Page Table)

 

서론

---

이전 게시글에서는 TLB(translation look-aside buffer)가 포함된 페이징 시스템에서 논리 주소를 물리 주소로 변환하는 방법에 대해 정리했었습니다. 이번 게시글에서는 페이지 테이블을 구성하는 가장 일반적인 방법인 아래 세 가지 방법에 대해 한번 살펴보겠습니다.

• 계층적 페이지
• 해시 페이지 테이블
• 역 페이지 테이블

이 장의 목표
1. 논리 주소와 물리 주소의 차이점과 주소를 변환할 때 MMU(메모리 관리 장치)의 역할을 정리해 본다.(이전 게시글)
2. 메모리를 연속적으로 할당하기 위해 최초, 최적, 및 최악 접합 전략을 적용해 본다.(이전 게시글)
3. 단편화에 대해 알아보고 단편화의 두 가지 종류 내부 및 외부 단편화의 차이점을 정리해 본다. (이전 게시글)
4. 외부 단편화 문제를 해결하기 위한 페이징 기법을 살펴본다. (이전 게시글)
5. TLB(translation look-aside buffer)가 포함된 페이징 시스템에서 논리 주소를 물리 주소로 변환한다. (이전 게시글)
6. 계층적 페이징, 해시 페이징 및 역 페이지 테이블을 설명한다. (현재 게시글)

 

1. 계층적 페이지(hierachical Paging)

---

요즘 많은 현대 컴퓨터는 매우 큰 주소 공간(2^32 ~ 2^64)을 가집니다. 이러한 환경에서는 페이지 테이블도 상당히 커집니다. 예를 들어, 32비트 논리 주소 공간을 가진 시스템을 생각해 봅시다. 이 시스템에서 페이지 크기가 4KB(2^12)라면 페이지 테이블은 100만(2^20 = 2^32 / 2^12) 개 이상의 항목으로 구성될 것입니다. 각 항목은 다시 4B로 구성되기 때문에 각 프로세스는 페이지 테이블만을 위해서도 4 MB의 공간이 필요하게 될 것입니다. 이러한 경우 모든 페이지 테이블을 메인 메모리에서 연속적으로 할당하기에는 상당한 무리가 있습니다. 그래서 한 가지 방법은 페이지 테이블을 여러 개의 작은 조각으로 나누는 것인데 이것도 여러 가지 방법이 가능합니다.

 한 가지 방법은 2단계 페이징 기법(two-level paging scheme)으로서 페이지 테이블 자체가 다시 페이징 되게 하는 것입니다.(아래 이미지)

2단계 페이지 테이블 기법

앞에서 4 KB의 크기를 가진 32비트 기계의 예를 다시 들어봅시다. 이 경우 논리 주소는 20비트짜리 페이지 번호와 12비트짜리 페이지 오프셋으로 이루어집니다. 이제는 페이지 테이블도 페이지로 나누어지기 때문에, 페이지 번호는 다시 10비트짜리 페이지 번호와 10비트짜리 페이지 오프셋으로 나누어집니다. 즉, 논리 주소는 다음과 같이 됩니다

여기서 p1은 바깥 페이지 테이블의 인덱스이고, p2는 안쪽 페이지 테이블의 페이지 내의 오프셋입니다. 아래 이미지는 이 구조에 의한 주소 변환 기법을 나타내고 있습니다.

2단계 32비트 페이징 구조에서의 주소 변환

이 방식에서는 주소 변환이 바깥 페이지 테이블에서 시작하여 안쪽으로 들어오므로 이 방식을 forward-mapped 페이지 테이블이라고도 부릅니다. 

 64비트 논리 주소 공간을 가진 시스템에서는 2단계 페이징 기법도 적절하지 못합니다. 이 점을 설명하기 위해서 페이지 크기가 4 KB(2^12)라고 가정해봅시다. 이 경우 페이지 테이블은 2^52 항목으로 구성될 것입니다. 2단계 페이징 기법을 사용하면 안쪽 페이지 테이블은 1페이지가 되거나 2^10개의 4B짜리 항목을 가지게 될 것입니다. 주소는 다음과 같이 나타내질 것입니다.

 바깥 페이지 테이블은 2^42 항목을 가지게 되고 2^44 바이트로 구성될 것입니다. 이와 같이 큰 바깥 테이블을 피하는 방법은 바깥 페이지 테이블을 작게 나누는 것입니다. 이 방식은 32비트 프로세서에서 효율성과 유연성을 향상하기 위해 사용됩니다.

 이와 같은 방법에는 여러 가지가 있을 수 있습니다. 첫째로, 바깥 페이지 테이블을 페이지 시킴으로써 3단계 페이지 방법을 만들 수 있습니다. 바깥 페이지 테이블은 표준 크기 페이지들로 구성된다고 가정해봅시다(2^10 항목, 또는 2^12 바이트). 이 경우 64비트 주소 공간은 여전히 관리하기가 어렵습니다.

바깥 페이지 테이블은 여전히 2^34바이트(16 GB)의 크기를 요구합니다.

 다음 단계는 2번째 바깥 테이블 자체를 페이징 하는 등의 4단계 페이징 기법을 사용할 수 있을 것입니다. 64비트 구조는 7단계를 페이징 해야 하며 각 논리 주소를 매핑하기 위해 너무 많은 메모리 접근을 필요로 하기 때문에 비현실적입니다. 이 예에서 일반적으로 우리는 64비트 구조에서는 계층적 페이지 테이블이 부적합하다는 것을 알 수 있습니다.

 

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

---

주소 공간이 32비트보다 커지면 가상 주소를 해시로 사용하는 해시 페이지 테이블을 많이 사용합니다. 해시 페이지 테이블의 각 항목은 연결 리스트를 가지고 있습니다. 이곳에는 충돌을 일으켜서 모두 이곳으로 해시되는 원소들이 매달리게 됩니다. 각 원소는 세 개의 필드를 가집니다.

1. 가상 페이지 번호
2. 매핑되는 페이지 프레임 번호
3. 연결 리스트상의 다음 원소 포인터

여기서는 알고리즘이 다음과 같이 동작합니다.

1. 가상 주소 공간으로부터 페이지 번호가 오면 그것을 해싱한다.
2. 그것으로 해시 페이지 테이블에서 연결 리스트를 따라가며 첫 번째 원소와 가상 페이지 번호를 비교해 본다.
3. 만약 일치하면 그에 대응하는 페이지 프레임 번호를 가져와 물리 주소를 얻는다.
4. 일치하지 않다면 연결 리스트의 그다음 원소로 똑같은 일을 반복한다.

아래 이미지는 위 과정을 잘 나타내고 있습니다.

해시 페이지 테이블

64비트 시스템에서 유용하도록 변형된 해시 테이블 기법이 제안되었습니다. 이 변형 기법은 해시 테이블과 비슷한 클라스터 페이지 테이블을 사용합니다. 해시 페이지 테이블의 각 항목이 한 개의 페이지만 가리키는 것에 반해 클러스터 페이지 테이블의 각 항목은 여러(예를 들면 16개) 페이지를 가리킵니다. 따라서 한 개의 페이지 테이블 항목이 여러 페이지 프레임에 대한 변환 정보를 지닐 수 있습니다. 클러스터 페이지 테이블은 성긴(sparse, 메인 메모리에서 stack영역과 heap영역 사이에 비어있는 메모리) 주소 공간에 유용하게 사용됩니다. 즉 메모리 액세스가 비연속적이면서 전 주소 공간으로 넓게 퍼져 나오는 경우에 유용합니다.

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

---

보통 프로세스는 각자 하나씩 페이지 테이블을 가지고 또 페이지 테이블은 프로세스가 사용하는 페이지마다 하나의 항목을 가집니다. 프로세스는 페이지의 가상 주소를 통하여 페이지를 참조하기 때문에 이 테이블 구조는 자연스럽습니다. 운영체제는 프로세스가 가상 페이지 주소를 제시할 때마다 그것을 실제 페이지 주소로 변환시켜 주어야 합니다. 페이지 테이블은 가상 주소에 대해 오름차순으로 정렬되어 있고 운영체제는 테이블 내의 어느 곳에 원하는 물리 페이지가 있는지를 계산할 수 있고, 이 값을 통해서 메모리를 액세스 할 수 있습니다. 이 기법의 단점 중 하나는 각 페이지 테이블 항목의 개수가 수백만 개가 될 수 있다는 것입니다. 이러한 테이블은 물리 메모리의 사용을 추적하기 위해 많은 양의 물리 메모리를 소비합니다.

 이 문제를 해결하는 한 방법이 역 페이지 테이블(inverted page table)입니다. 역 페이지 테이블에서는 메모리 프레임마다 한 항목씩을 할당합니다. 각 항목은 그 프레임에 올라와 있는 페이지 주소, 그리고 그 페이지를 소유하고 있는 프로세스의 ID를 표시하고 있습니다. 이렇게 되면 시스템에는 단 하나의 페이지 테이블만이 존재하게 되고, 테이블 내 각 항목은 메모리 한 프레임씩을 가리키게 됩니다. 아래 이미지는 역 페이지 테이블의 운용 방식을 나태내고 있습니다.

역 페이지 테이블

역 페이지 테이블은 종종 각각의 페이지 테이블 엔트리에 저장되는 주소 공간 ID(address-space indentifier)를 요구합니다. 왜냐하면 주소 공간 ID를 저장함으로써 특정 프로세스의 논리 페이지가 그에 상응하는 물리 페이지 프레임과 매핑되었다는 것을 보장해주기 때문입니다.

시스템상에서 가상 주소는 세 가지 항목으로 구성되어 있습니다.

<process-id, page-number, offset>

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

이 방법은 논리 페이지마다 항목을 가지는 대신 물리 프레임에 대응되는 항목만 테이블에 저장하기 때문에 메모리에서 훨씬 작은 공간을 점유합니다. 그러나 다른 한편 역 페이지 테이블은 주소변환 시간이 더 오래 걸릴 수 있습니다. 역 페이지 테이블은 물리 주소에 따라 정렬되어 있고 탐색은 가상 주소를 기준으로 하므로 페이지 전체를 탐색하여야 할 수도 있습니다. 때문에 이 탐색은 매우 오래 걸릴 수도 있습니다. 이 문제를 해결하기 위해서 위에서 설명한 것처럼 하나 또는 기껏해야 몇 번의 페이지 테이블을 탐색하도록 해시 테이블을 사용합니다. 물론 접근마다 해시 테이블을 참조해야 하므로 메모리 참조 횟수를 증가시키게 됩니다.(해시 테이블 한번, 페이지 테이블 한번). 성능 향상을 위하여 해시 테이블이 참조되기 전에 이전 게시글에 설명한 것처럼 TLB가 참조된다는 것을 기억해야 합니다.

 

[OS] 메인 메모리(1) - 물리, 논리주소 및 연속 메모리 할당

[OS] 메인 메모리(2) - 페이징 기법

[OS] 메인 메모리(3) - TLB(translation look-aside buffers)

이번 게시글로 메인 메모리에 대한 정리를 끝내고 다음 게시글부터는 가상 메모리에 대해 한번 정리해 보겠습니다.