[OSTEP-20] Advanced Page Tables

개요

페이징 테이블의 두번째 문제점은 크기임, 페이지 테이블의 각 항목은 4바이트, 페이지 크기가 4KB 일 경우 주소공간에는 2^20의 가상 페이지가 존재함.

핵심 질문: 페이지 테이블을 어떻게 작게 만들까

단순한 배열 기반의 페이지 테이블은 크기가 크며 일반적인 시스템에서 메모리를 과도하게 차지함

간단한 해법: 더 큰 페이지

• 페이지 크기를 증가 시켜서 VPN 비트 수를 줄임
  • 10KB → 16KB ==> 2^20 → 2^18
    • 기존 페이지 테이블 대비 크기가 1/4로 감소
• 하지만 단순한 페이지 크기의 증가는 부작용을 수반함
  • 가장 큰 문제
    • 페이지 내부의 낭비 공간이 증가함, 내부 단편화의 증가로 이어짐
• 컴퓨터 시스템의 메모리가 금방 고갈되는 현상이 발생함 → 많은 컴퓨터 시스템들이 비교적 작은 페이지들을 사용함
  • 일반적으로 4KB, 8KB

멀티 페이지 크기

많은 컴퓨터 구조들 (MIPS, SPARC, x86-64) 가 멀티 크기 페이지를 지원한다.

하이브리드 접근 방법: 페이징과 세그멘트

• 두가지 방법을 조합하는 것을 hybrid 라고 부름, Dennis 는 페이징과 세그멘테이션을 결합하여 페이지 테이블 크기를 줄이는 아이디어를 냄
• 프로세스의 전체 주소 공간을 위해 하나의 페이지 테이블을 두는 대신
  • 논리 세그멘트마다 따로 페이지 테이블을 정의함

 

 

구현

• 세그멘테이션은 세그멘트의 물리 주소 시작 위치를 나타내는 base 레지스터, 크기를 나타내는 bound 또는 limit 레지스터가 존재함
• 베이스 레지스터는 페이지 테이블의 시작 주소를 갖음

예시

• 4KB 페이지를 갖는 32비트 가상 주소 공간이 4개의 세그멘트로 나뉘어져 있을 경우
• 하드웨어에 세 개의 베이스/바운드 레지스터 쌍이 코드와 힙 그리고 스택을 위해서 존재
• 하이브리드 기법에서 핵심은 세그멘트마다 바운드 레지스터가 따로 존재한다는 것
•  

문제점

• 세그멘테이션은 주소 공간의 사용에 있어서 특정 패턴을 가정하기 때문에 원하는 만큼 유연하지 못함
• 큰 공간을 커버하지만 드문드문 사용되는 힙의 경우에는 여전히 페이지 테이블의 낭비를 면치 못함
• 하이브리드 방식에서는 페이지 테이블 크기에 제한이 없고 다양한 크기를 갖기 때문에 외부 단편화를 유발함

멀티 레벨 페이지 테이블

목표: 사용하지 않는 주소 공간을 테이블에서 제거

• 선형 페이지 테이블을 트리 구조로 표현함, 매우 효율적이기 때문에 많은 현대 시스템에서 사용되고 있음
• 페이지 디렉토리 항목은 Valid 비트와 PFN 이 있으며 PED 항목이 유효하다는 것은 PDE가 가리키고 있는 페이지 내의 페이지 테이블에 최소한 하나의 PTE의 Valid 비트가 1로 설정되어있다는 것

개념

• 페이지 테이블을 페이지 크기의 단위로 나눔
• 페이지 디렉터리(page directory) 자료 구조를 사용해 테이블 각 페이지의 할당 여부와 위치 파악
• 페이지 디렉터리는 페이지 테이블을 구성하는 각 페이지의 존재여부 와 위치 정보 를 가지고 있음
•