[OS] 10. Multi-Level Page Tables

sunny·2024년 4월 12일

os

목록 보기
8/9

이 글은 건국대학교 2024년 1학기 운영체제 수업과 『Operating Systems: Three Easy Pieces』 를 참고하여 작성되었습니다.

『Operating Systems: Three Easy Pieces』
20장. Paging: Smaller Tables

지난 글에서 다룬 TLB를 통해 page table을 사용할 때 발생하는 문제점인 속도 문제를 어느 정도 해결할 수 있었지만, 아직 메모리 낭비 문제에 대한 해결책을 찾지 못했습니다. 이번 글에서는 page table의 큰 용량 문제를 해결할 수 있는 방법인 Multi-Level Page Table에 대해 다뤄볼 예정입니다.

어떻게 하면 page table을 더 작게 만들 수 있을까?

1. 페이지 크기를 키운다.

페이지의 크기를 키우면 한 프로세스를 구성하는 페이지의 개수, 즉, PTE의 개수도 줄어들게 됩니다. 따라서 page table의 크기도 작아집니다.

32bit address space에서 페이지 1개 크기가 4KB, 16KB 비교

페이지 1개의 크기4KB16KB
offset bit12-bit14-bit
VPN bit20-bit18-bit
page table 1개당 PTE의 개수222^20^0 개212^18^8 개
page table의 크기222^22^2 Byte = 4MB222^20^0 Byte = 1MB

페이지 1개의 크기가 4배가 되면, page table의 크기가 1/4배 되는 것을 볼 수 있습니다. 페이지의 개수가 줄어들면서 TLB hit rate도 높일 수 있다는 장점이 있습니다.

하지만 이 방법의 가장 큰 단점은 internal fragmentation이 발생한다는 것입니다. 페이지의 크기가 커졌기 때문에 하나의 페이지 안에서 일부만 사용되고 나머지 공간이 낭비됩니다.

2. Segmentation과 Paging기법을 결합

우선 linear page table을 사용하는 경우를 살펴보면, 힙과 스택에 할당된 공간 중 일부 부분만 사용됩니다. 이 경우 page table 대부분이 비어있어 회색 부분은 모두 낭비되는 것을 알 수 있습니다.

결합 방식을 사용하면, 한 프로세스의 주소 공간에 하나의 페이지 테이블을 두는 대신 논리 세그먼트마다 페이지 테이블을 따로 둡니다. 위 예제에서는 한 프로세스가 코드, 힙, 스택 당 하나씩 총 3개의 페이지 테이블을 가지고 있는 것입니다. segmentation 기법에서는 base register가 segment의 물리 주소 시작 위치를 가리켰지만, 결합 방식에서는 segment의 page table 시작 주소를 가리킵니다. bound register도 물리 주소의 크기가 아닌 segment의 최대 유효 페이지 개수를 나타냅니다.

예시 : 32-bit 가상 주소 공간, 페이지 1개의 크기는 4KB, 한 프로세스 당 3개의 segment가 존재

  • 2-bit : 소속 세그먼트를 나타냄
  • 12-bit : 페이지 내 offset
  • 나머지 18-bit : VPN

이 때, CPU는 가상 주소로 부터 소속 세그먼트와 VPN을 얻어 해당 페이지와 매핑되어 있는 PTE의 주소를 알 수 있습니다. 이 방식은 기존 linear page table에서 VPN과 PTE 주소를 알아내는 방식이 유사하지만, 세그먼트 베이스 레지스터를 사용한다는 차이점이 있습니다.

// 1. 어떤 segment에 속해있는지 파악
SN = (VirtualAddress & SEG_MASK) >> SN_SHIFT

// 2. VPN 얻기
VPN = (VirtualAddress & VPN_MASK) >> VPN_SHIFT

// 3. 해당하는 segment의 base register를 가져옴 (Base[SN]) -> BR과 VPN을 사용하여 해당 PTE의 주소를 가져옴
AddressOfPTE = Base[SN] + (VPN * sizeof(PTE))

💡 각 segment의 페이지 테이블은 연속적이어야 한다.

문제점

  1. 이 방법에서는 각 segment의 page table은 여전히 연속적이다. 따라서 각 segment의 page table 내에서 메모리 낭비가 일어날 수 있다.
    ex) malloc을 통해 동적 메모리 할당을 많이 한 후, 맨 마지막에 할당한 것만 free를 하지 않고, 나머지는 다 free를 함 → free되어 사용되지 않는 공간은 여전히 heap segment의 페이지 테이블로서 자리를 차지하게 된다.

  2. external fragment가 발생할 수 있다.
    이제부터는 페이지 테이블의 크기가 가변적 : segment의 크기가 커지면 그에 비례하여 해당 segment의 페이지 테이블의 크기도 커진다. → 그렇게 되면 커진 페이지 테이블에 적합한 메모리 공간을 찾아야 하는 문제 발생

이러한 문제점 모두 없이 페이지 테이블의 크기를 줄이기 위해 고안된 방법이 바로 Multi-Level Page Table 입니다.

Multi-Level Page Tables

1. 멀티 레벨 페이지 페이블의 구조

multi-level page table에서는 page table에 대한 정보를 page directory와 page table에 나눠서 계층적으로 저장합니다. 그리고 페이지 테이블은 한 페이지의 크기씩 쪼개어져 관리됩니다.

예를 들어, PTE 1개의 크기가 32-bit이고 한 페이지의 크기가 4KB인 시스템에서는 페이지 디렉토리가 4KB이고, 212^10^0개 만큼의 page directory entry (PDE) 로 구성되어 있습니다. 또한 페이지 페이블은 페이지 1개의 크기인 4KB 단위로 쪼개어져서 관리됩니다. 그리고 하나의 페이지 테이블도 212^10^0개 만큼의 PTE로 구성되어 있습니다.

아래의 그림을 통해 알 수 있듯이,


왼쪽은 linear page table, 오른쪽은 2-level page table 의 모습입니다.

linear page table에선 PTBR 이라고 불리는 레지스터가 페이지 테이블의 베이스 주소를 가리킵니다. 그리고 한 페이지 테이블에 해당하는 PTE는 연속적으로 메모리에 위치합니다. 사용되지 않는 PTE도 메모리에 할당되기 때문에 공간이 낭비되는 단점이 있습니다.

반면에 2-level page table에선 PDBR 이라고 불리는 레지스터가 페이지 디렉토리의 베이스 주소를 가리킵니다. (멀티 레벨 페이지 테이블에선 PTBR이 존재하지 않습니다.) 페이지 디렉토리를 이루는 각각의 PDE는 PFN (page frame number)라 불리는 페이지 테이블의 위치 정보를 가지고 있으므로, 페이지 테이블을 이루는 각각의 페이지는 불연속적으로 존재할 수 있습니다. 따라서 페이지 테이블의 공간 할당이 매우 유연하고 메모리 자원 활용에 효율적이라는 장점을 가집니다. 또한 하나의 페이지 테이블에 valid한 PTE가 존재하지 않는다면 해당 페이지 테이블 조각은 메모리가 할당되지 않습니다. 이를 통해 메모리를 절약할 수 있습니다.

페이지 디렉토리는 valid bit와 PFN으로 구성되어 있습니다. valid bit는 해당 PDE가 가리키는 페이지 테이블에 유효한 PTE가 하나라도 있는지를 나타내는 정보입니다. PFN은 page frame number의 번호로, 페이지 테이블 조각의 base 주소를 의미합니다.

2. 주소 변환 과정 살펴보기

// 1
VPN = (VirtualAddress & VPN_MASK) >> SHIFT

// 2
(Success, TlbEntry) = TLB_Lookup(VPN)

// 3-1. TLB Hit
if (Success == True)     
	if (CanAccess(TlbEntry.ProtectBits) == True)         
		Offset = VirtualAddress & OFFSET_MASK
		PhysAddr = (TlbEntry.PFN << SHIFT) | Offset 
		Register = AccessMemory(PhysAddr)  // 4 
	else
		RaiseException(PROTECTION_FAULT)
  1. 가상주소로 VPN 얻기
  2. 해당 VPN과 매핑된 PTE가 TLB에 있는지 찾기 TLB look up
  1. TLB hit 일 경우, page table에 접근 없이 물리 주소를 얻을 수 있음
  2. 찾고자 하는 page의 실제 물리 주소에 접근 (page table에 접근하는거 아님!)
// 3-2. TLB Miss 
else 
	PDIndex = (VPN & PD_MASK) >> PD_SHIFT		
	PDEAddr = PDBR + (PDIndex * sizeof(PDE))    // 4
	PDE = AccessMemory(PDEAddr)					// 5
	
	if (PDE.Valid == False)
		RaiseException(SEGMENTATION_FAULT)
	else
		PTIndex = (VPN & PT_MASK) >> PT_SHIFT
		PTEAddr = (PDE.PFN << SHIFT) + (PTIndex * sizeof(PTE))	// 6
		PTE = AccessMemory(PTEAddr)		// 7
		if (PTE.Valid == False)
			RaiseException(SEGMENTATION_FAULT)
		else if (CanAccess(PTE.ProtectBits) == False)
			RaiseException(PROTECTION_FAULT)
		else
			TLB_Insert(VPN, PTE.PFN, PTE.ProtectBits)		// 8
			RetryInstruction()
  1. TLB miss 일 경우,
  2. PDE 가져오기
    a. PDIndex 구하기 : VPN을 사용하여 page directory 내의 인덱스 값을 구한다
    b. PDEAddr 구하기 : PDBR과 PDIndex를 사용하여 PDE 주소를 얻는다
    c. 메모리에 접근해서 PDE를 가져온다 PDE = AccessMemory(PDEAddr)
  3. PTE 가져오기
    a. PTIndex 구하기 : VPN을 사용하여 page table 내에서의 인덱스 값을 구한다
    b. PTEAddr 구하기 : PDE 속 PFN과 PTIndex를 사용하여 PTE 주소를 얻는다
    c. 메모리에 접근해서 PTE를 가져옴 PTE = AccessMemory(PTEAddr)
  4. 가져온 PTE를 TLB에 넣고 retry()

3. multi-level page table의 단점

첫번째 단점은 Time-space trade-off 입니다. 멀티 레벨 페이지 테이블을 사용하면 메모리 공간을 효율적으로 사용할 수 있지만, TLB miss 발생 시 메모리에 2번 접근해야 하므로 성능이 나빠집니다. level이 많이질 수록 메모리에 접근하는 횟수가 증가합니다.
이 때문에 TLB hit rate를 높이는 것이 매우 중요해집니다.

두번째 단점은 complexity 입니다. 위의 슈도코드에서 볼 수 있듯이, 이전에 비해 주소 변환 과정이 더 복잡해졌습니다.

4. 예시

예시 1

  • Address space of size 16KB, with 64-byte pages
    각 PTE는 4-byte이다.

  • 이를 통해 알 수 있는 사실

    • 하나의 프로세스는 16KB(=212^14^4-byte)의 가상 주소 공간을 갖는다.
    • 주소를 표현하기 위해 14-bit가 필요하다.
    • 그리고 한 프로세스는 총 282^8 개의 페이지로 구성된다.
    • offset을 표현하기 위해 6-bit가 필요하다.
    • VPN을 표현하기 위해 나머지 8-bit를 사용한다.
    • 페이지 디렉토리와 페이지 테이블 하나당 16개의 엔트리를 가지고 있으므로, 엔트리를 인덱싱 하기 위해서 각각 4-bit 씩 필요하다.

예시 2

  • 8-bit addressing, with 16-byte pages
    각 PTE는 4-byte이다.

  • 이를 통해 알 수 있는 사실

    • 하나의 프로세스는 282^8-byte의 가상 주소 공간을 갖는다.
    • 한 프로세스는 총 242^4 개의 페이지로 구성된다.
    • offset을 표현하기 위해 4-bit가 필요하다.
    • VPN을 표현하기 위해 나머지 4-bit를 사용한다.
    • 페이지 디렉토리와 페이지 테이블 하나당 4개의 엔트리를 가지고 있으므로, 엔트리를 인덱싱 하기 위해서 각각 2-bit 씩 필요하다.

5. 실제 시스템 살펴보기

1️⃣ x86-32 : 2-Level Paging

  • 32-bit 컴퓨터, with 4KB pages

  • 이를 통해 알 수 있는 사실

    • 각 PTE, PDE의 크기는 32-bit이다.
    • offset을 표현하기 위해 12-bit가 필요하다.
    • VPN을 표현하기 위해 나머지 20-bit를 사용한다.
    • 페이지 디렉토리와 페이지 테이블 하나당 212^10^0개의 엔트리를 가지고 있으므로, 엔트리를 인덱싱 하기 위해서 각각 10-bit 씩 필요하다.

  • CR3 : intell에서 PDBR 역할을 하는 레지스터. OS는 context switch가 일어날 때마다 CR3 값을 바꿔줘야 한다.
  • PTE 1개가 4KB를 담당한다.
    = PDE 1개 (page table 1개) 가 4MB를 담당한다.
    = page directory 1개가 4GB를 담당한다.
    = 한 프로세스 당 4GB의 가상주소를 갖는다.
  • 리눅스의 경우 높은 주소 1GB를 OS에 할당하고, 나머지 3GB를 응용프로그램에게 할당한다.

모든 프로세스는 동일한 커널 영역을 공유합니다. 이를 위해 모든 프로세스의 페이지 디렉토리에서 상위 282^8개의 PDE가 커널 영역을 매핑하는 데 사용됩니다. 새로운 프로세스가 만들어질 때마다 PID가 0인 idle process의 상위 256개 PDE를 그대로 카피해옴으로써 구현 가능합니다.

2️⃣ x86-64 : 4-Level Paging

  • 64-bit 컴퓨터, with 4KB pages
    단, 48-bit addressing을 사용한다. (64-bit를 모두 사용하면 level이 너무 커지기 때문)

  • 이를 통해 알 수 있는 사실

    • 각 PTE, PDE 등의 크기는 64-bit이다.
    • offset을 표현하기 위해 12-bit가 필요하다.
    • VPN을 표현하기 위해 나머지 36-bit를 사용한다.
    • 페이지 디렉토리와 페이지 테이블 하나당 292^9개의 엔트리를 가지고 있으므로, 엔트리를 인덱싱 하기 위해서 각각 9-bit 씩 필요하다.

  • PDE도 direct하게 페이지를 가리킬 수 있다.
    이 때의 페이지는 2MB 크기로, huge page 라고 한다.
    (PTE 1개가 4KB를 담당한다 = PDE 1개가 2MB를 담당한다)

kernel 영역을 표현할 때에는 맨 앞이 F로 채워진 48-bit 주소를 사용하고,
user 영역을 표현할 때에는 맨 앞이 0으로 채워진 48-bit 주소를 사용합니다. 64-bit 컴퓨터는 32-bit 컴퓨터와 다르게 user 와 kernel이 동일한 크기의 메모리를 사용합니다.

profile
sunny
이전 포스트

[OS] 9. TLB : Translation-Lookaside Buffer

다음 포스트

[OS] 11. Swapping

0개의 댓글