멀티 레벨 페이지 테이블 (OSTEP 20장)

멀티 레벨 페이지 테이블

선형 페이지 테이블을 트리 구조로 표현한다.
매우 효율적인 방법으로 현대 시스템에서 사용되고 있음

멀티 레벨 페이지 테이블 기본 개념

1. 페이지 테이블을 페이지 크기의 단위로 나눈다. 
   페이지 테이블의 페이지가 유효하지 않은 항목만 있으면, 
   해당 페이지를 할당하지 않음 

2. 페이지 디렉토리라는 자료 구조를 사용하여, 페이지 테이블 각 페이지의 할당 여부와 위치 파악

**
선형 페이지 테이블은 배열이므로 스택이 맨 마지막에 배치 되어 중간에 불필요한 부분까지 페이지를 할당해야 함 

**
반면 다단계 페이지 테이블의 경우 필요한 부분에 대해서만 페이지를 할당하면 되므로, 
메모리를 절약할 수 있다. (페이지 테이블을 나눠 스택과 힙 사이의 공간이 존재하지 않음)

- 배열의 경우 1000번 인덱스에 값을 할당하면, 크기 1001인 배열을 생성해야 함
- 이 경우, 배열(페이지 테이블)을 크기가 10인 배열 100개를 생성해서 
마지막 배열만 메모리에 탑재했다고 보면 됨

<그림 23.3> 에서는 두 개의 유효한 페이지가 존재하며, 유효 페이지는 메모리에 존재한다.

페이지 디렉토리

2단계 페이지 페이블에서, 페이지 디렉터리의 각 항목은 페이지 테이블의 한 페이지를 나타낸다.
페이지 테이블을 구성하는 각 페이지의 존재 여부와 위치 정보를 가지고 있다. 
페이지 디렉터리 항목(PDE)들로 구성되며, 각 항목의 구성은 페이지 테이블의 각 항목과 유사
- 유효비트, 페이지 프레임 번호, 접근 권한 비트 등등

**
PTE 유효 비트와 PDE 유효 비트는 다르다. 
PTE의 경우 가상 메모리 페이지가 할당되었다는 뜻 //지연 로딩이라면 물리 프레임과 매핑 않을 수 있다. 
PDE의 경우 연결된 페이지 블록(PTE 묶음) 내에 페이지가 하나라도 할당된 경우 valid bit가 1이다.

멀티 레벨 페이지 테이블 장점

1. 멀티 레벨 테이블은 사용된 주소 공간의 크기에 비례하여 페이지 테이블 공간이 할당된다.
    - 보다 작은 페이지 테이블로 주소 공간을 표현

2. 페이지 테이블을 페이지 크기로 분할함으로써, 메모리 관리가 매우 용이
    - 페이지 테이블을 할당하거나 확장할 때, 
      운영체제는 free 페이지 폴에 있는 빈 페이지를 가져다 사용하면 된다.
    - 기존 선형 페이지 테이블은 연속된 물리 메모리 공간 사용하여 확장이 어렵고, 
      모든 페이지를 미리 할당하여 스왑 작업이 비효율적
    - 멀티 레벨 페이지 테이블의 경우 필요에 따라 할당하고 해제하므로, 
      확장이 쉽고, 스왑 영역으로 페이지를 옮기는 것이 쉬움
    - 페이지 디렉터리를 사용하여 페이지들의 위치를 파악하고 있어, 
      페이지 테이블을 위한 공간 할당이 매우 유연하다.

유의사항

TLB 미스 발생 시, 주소 변환을 위한 메모리 로드가 추가적으로 발생함 (추가 비용 발생)
- 선형 페이지 테이블은 한 번의 메모리 참조만으로 주소 정보를 TLB에 탑재
- 반면 멀티 레벨 페이지 테이블은 두 번 이상의 메모리 참조 필요
- 즉, 페이지 테이블 크기는 감소했으나 메모리 접근 시간 증가

멀티 레벨 페이지 테이블은 선형 페이지 테이블보다 복잡하게 만들어졌다.

2레벨 페이지 테이블 예제

16KB 크기의 가상 주소 공간 
14비트 가상 주소 길이 ( VPN - 8비트, Offset - 6비트 )
전체 페이지 테이블은 256개의 PTE를 가지고 있음 
→ 전체 크기 16KB = 256 * 64Byte

전체 페이지 테이블을 1KB로 나눔
→ 전체 16개의 페이지 테이블로 분할
→ 각 페이지 테이블은 16개의 PTE를 갖게 됨 

**
VPN 8비트 중 4비트는 각 페이지 테이블과 매핑된 PDE를 찾기 위한 것
→ 페이지 디렉터리 색인

// VPN에서 페이지 디렉터리 인덱스를 추출하고 나면 
PDEAddr = PageDirBase + (PDIndex * sizeof(PDE))
// 라는 식을 이용하여 페이지 디렉 토리 항목(PDE)의 주소를 찾을 수 있다. 

- 페이지 디렉터리 항목(PDE)이 invalid라고 표시되어 있으면, 
  이 주소 접근은 유효하지 않음
  → 예외 발생

- 해당 페이지 디렉터리 항목(**PDE)이 valid**라면 추가 작업 수행
  → 이 페이지 디렉터리 항목이 가리키고 있는 페이지 테이블의 
    페이지에서 원하는 페이지 테이블 항목을 읽어들이는 것이 목표, 
    이 PTE를 찾기 위해 VPN의 나머지 비트들을 사용

**
나머지 4비트는 각 페이지 테이블에서 PTE를 찾기 위한 것 → 페이지 테이블 색인

// 이 페이지 테이블 인덱스는 페이지 테이블 자체 인덱스로 사용된다. 다음과 같이 계산
PTEAddr = (PDE.PFN << SHIFT) + (PTIndex * sizeof(PTE))

 

<그림 23.5> 에서 페이지 디렉터리의 2개의 PDT가 유효하다.

각 PDT가 가리키는 페이지 테이블**의 PTE일부가 유효함 
→ PFN : 100의 페이지 테이블의 경우 코드 ~ 힙
→ PFN : 101의 페이지 테이블의 경우 스택 
그 외 페이지 테이블은 모두 유효하지 않음(invalid)

**
페이지 디렉터리를 위한 페이지 하나 할당
페이지 테이블을 위한 페이 둘 할당
총 세 개를 할당한다.

**
이는 실제 데이터 페이지까지 포함한 것이 아니라, 매핑 정보를 저장하는 페이지만 계산해서 3개
실제 데이터 페이지까지 포함할 경우
코드 2개, 힙 2개, 스택 2개로 총 9개의 페이지를 할당

주소 계산

11 1111 1000 0000
11 11 → 페이지 디렉터리 항목 101 선택
1110 → 101 페이지 테이블에서, 마지막에서 두 번째 PTE의 PFN 55 선택 
11 0111(PFN 55) + 00 0000(offset)
= 0x0DC0

3단계 페이지 테이블 예제

512 바이트 페이지, 30비트 가상 주소 길이 (VPN - 21비트, offset - 9 비트)
2^21의 PTE가 존재 - 2백만개  
페이지 테이블 전체 크기 - 8MB (2백만 * 4byte)

**
멀티 레벨 테이블에서 몇 단계를 둘지 결정하기 위해서 먼저 한 페이지에 몇 개의
페이지 테이블 항목을 저장할 수 있는지 계산해야 한다. 
한 페이지 크기 512, PTE 크기 4byte
→ 한 페이지에 128개의 PTE 저장 가능  (512 / 4 = 128)
VPN 중, 하위 7비트는 페이지 테이블 색인 인덱스

 

14비트가 페이지 디렉터리 색인 인덱스가 됨 
→ 페이지 디렉터리 또한 선형 자료구조 이므로 이렇게 되면 연속된 메모리 공간을 요구하여 
    멀티 레벨 테이블의 근본 취지가 훼손 됨 

**
이를 해결하기 위해 페이지 디렉터리 자체를 멀티 페이지들로 나누어 트리의 단계를 늘린다.

 

1. RD 0 인덱스를 사용하여 최상위 페이지 디렉터리의 특정 엔트리(PED1)를 찾는다.
    - 이 엔트리는 RD1 데릭터리가 위치한 물리 주소를 제공한다.

2. RD 1 인덱스를 사용하여 RD1 디렉터리의 특정 엔트리(PDE1)를 찾는다.
    - 이 엔트리는 페이지 테이블의 물리 주소를 제공

3. 페이지 테이블 색인을 사용하여, 페이지 테이블에서 페이지 테이블 엔트리를 찾는다.
    - 이 PTE에는 최종 물리 페이지 프레임 번호(PFN)가 들어 있다.

4. 마지막으로 오프셋을 PFN에 더하여 물리 주소의 최종 위치를 찾는다.

역 페이지 테이블

여러 개의 페이지 테이블 대신 시스템에 단 하나의 페이지 테이블만 둔다.
페이지 테이블은 물리 페이지를 가상 주소 상의 페이지로 변환한다. 
역 페이지 테이블의 각 항목은 물리 페이지를 사용 중인 프로세스 번호, 해당 가상 페이지 번호를 가지고 있다.
역 페이지 테이블은 주소 변환을 위해 전체 테이블을 검색해서 원하는 가상 주소 페이지를 갖는 항목을 찾아야 한다.
→ 순차 탐색은 속도가 느리다.
→ 탐색 속도 향상을 위해 주로 해시 테이블을 사용한다. 

**
역 페이지 테이블 역시 하나의 자료구조일 뿐이다. 

페이지 테이블을 디스크로 스와핑

모든 페이지 테이블을 메모리에 상주시키기에 양이 너무 클 수 있음
→ 일부 시스템들은 시스템의 메모리가 부족한 경우 페이지 테이블들을 디스크로 스왑하기도 한다.

기타

공간을 많이 소모하는 테이블 구조를 사용할수록 TLB 미스의 처리 속도가 빨라짐
공간을 적게 사용하면 상황은 반대가 된다.
-> 주어진 제약 조건들을 적절히 고려하여 적합한 자료 구조를 결정해야 함