Operating System: 13. 페이징, 더 작은 테이블

페이지 크기가 4KB(2^12)이고, 페이지 테이블의 각 항목은 4바이트인
32비트 주소공간을 가정해보자. 주소 공간에는 대략 백만개(2^20)의 
가상페이지가 존재한다. 즉, 페이지 테이블 항목의 크기(4바이트 * 100만개)는
약 4MB가 된다. 일반적으로 프로세스는 자기 자신의 페이지 테이블을 갖으므로
이런 엄청난 메모리 부담을 어떻게 해결할 수 있을까?

1. 더 큰 페이지

• 페이지 크기를 증가시켜 페이지 테이블을 감소시키는 방법이다.

32비트 주소 공간에서 페이지 크기가 16KB라면
VPN과 오프셋은 각 몇 비트일까?

- 16KB = 2^14
- 18비트의 VPN과 14비트의 오프셋을 갖게된다.
- 기존 페이지 테이블 대비 크기가 1/4로 감소된다.
(페이지 크기가 정확히 4배 증가했기 때문이다)

부작용

• 내부 단편화(internal fragmentation) 문제, 즉 페이지 내부의 낭비 공간이 증가한다.
• 응용프로그램이 여러 페이지를 할당받았지만, 할당받은 일부만을 사용하기에 컴퓨터 메모리가 금방 고갈된다.
• 일반적으로 많은 컴퓨터 시스템에서 비교적 작은 페이지를 사용한다(4KB, 8KB).

2. 페이징과 세그먼트

• 힙과 스택에서 실제로 전체 공간 중 작은 부분만 사용되는 경우 아래의 페이지 테이블을 보자.

• 페이지 테이블이 대부분 비어 있는 공간 낭비가 심각하다. (32비트 주소 공간에서는 낭비가 더욱 클 것이다)
• 페이징과 세그먼트의 결합 방식은 하나의 페이지 테이블을 두는 대신, 논리 세그먼트 마다 페이지 테이블을 두는 방식이다.
• 하드웨어에 세 개(코드, 스택, 힙)의 베이스/리밋 레지스터 쌍이 존재한다고 가정한다.
• 각 세그먼트 베이스 레지스터는 세그먼트 페이지 테이블의 시작 물리주소를 갖는다.

SN           = (VirtualAddress & SEG_MASK) >> SN_SHIFT
VPN          = (VirtualAddress & VPN_MASK) >> VPN_SHIFT
AddressOfPTE = Base[SN] + (VPN * sizeof(PTE))

문제점

• 1. 세그먼테이션은 주소 공간의 사용에 있어 특정 패턴을 가정하기에 유연하지 못하다.
  • 드문 드문 사용되는(sparsely used) 힙의 경우에는 여전히 테이블의 낭비를 면치 못할 수 있다.
• 2. 외부 단편화를 유발한다.
  • 페이지 테이블 크기는 페이지 테이블 항목 크기의 정수배가 되어야 하므로, 메모리 상에서 페이지 테이블용 공간을 확보하는 것이 더 복잡하다.

3. 멀티 레벨 페이지 테이블

• 멀티 레벨 페이지 테이블에서는 선형 페이지 테이블을 트리 구조로 표현한다.
• 기본 개념
  • 1. 페이지 테이블을 페이지 크기의 단위로 나눈다.
  • 2. 페이지 테이블의 페이지가 유효하지 않은 항목만 있으면, 해당 페이지를 할당하지 않는다.
  • 3. 페이지 디렉토리(page directory)라는 자료구조를 사용하여 페이지 테이블을 각 페이지의 할당 여부와 위치를 파악한다.
• 간단한 2단계 페이지 테이블에서, 페이지 디렉터리의 각 항목은 페이지 테이블의 한 페이지를 나타낸다.
• 페이지 디렉터리는 페이지 디렉터리 항목(page directory entries, PDE)들로 구성된다.
• valid bit를 가지고 있는데, PDE가 유효하다는 것은 그 항목이 가리키고 있는(PFN을 통해서) 그 항목이 가리키고 있는 페이지들 중 최소한 하나가 유효하다는 것을 의미한다.
  • 즉, PDE가 가리키고 있는 페이지 내의 최소한 하나의 PTE의 valid bit가 1로 설정되어 있다. 만약 PDE가 유효하지 않다면, PDE는 실제 페이지가 할당되어 있지 않은 것이다.

장점

1. 멀티 레벨 테이블은 사용된 주소 공간의 크기에 비례하여 페이지 테이블 주소 공간이 할당된다.
   • 그렇기에 보다 작은 크기의 페이지 테이블로 주소공간을 표현할 수 있다.
2. 페이지 테이블을 페이지 크기로 분할함으로써 메모리 관리가 매우 용이하다.
   • 페이지 테이블을 할당하거나 확장할 때, 운영체제는 free 페이지 풀에 있는 빈 페이지를 가져다 쓰면 된다. 즉, 선형 페이지 테이블처럼 연속된 물리 공간이 필요하지 않다. 빈 공간이 산재되어 있더라도 페이지 디렉터리를 이용하여 그 위치를 파악할 수 있기 때문이다.

단점

1. TLB 미스 시, 주소 변환을 위해 추가 비용이 발생한다.
   • TLB 히트 시 성능은 동일하지만, TLB 미스 시 두 배의 시간이 소요된다.
   • 페이지 디렉터리와 PTE 접근을 위해 각각 한 번씩(선형 페이지 테이블에서는 한 번의 접근만으로 주소 정보를 TLB로 탑재했다) 메모리 로드가 발생한다.
2. 페이지 테이블 검색은 단순 선형 페이지 테이블 경우보다 더 복잡하다.

멀티 레벨 페이징 예제

64바이트(2^7) 페이지를 갖는 16KB(2^14) 크기의 주소공간 일 때,
VPN과 오프셋은 각 몇 비트일까?

- 8비트의 VPN과 6비트의 오프셋을 갖게된다.

• 가상 페이지 0과 1은 코드, 가상 페이지 4와 5는 힙 그리고 가상 페이지 254, 255은 스택으로 사용된다.
• 전체 테이블은 (이 예제에서) 256개의 항목을 가지고 있다.
• 각 PTE는 4바이트라 가정한다.
• 페이지 테이블 크기는 4 * 256 (1KB)이다.
• 페이지 64바이트라 한다면 페이지 테이블은 16개의 64바이트 페이지로 분할된다.
• 페이지 테이블은 256개의 항목으로 16개의 페이지로 나뉘어 있다.
• 페이지 디렉터리는 페이지 테이블의 각 페이지마다 하나씩 있어야 하기에 총 16개의 항목이 있어야 한다. 즉, 4개의 비트를 사용하여 디렉터리를 구성한다.

• VPN에서 페이지-디렉터리 인덱스(page-directory index)를 추출하고 나면 PDEAddr = PageDirBase + (PDIndex * sizeof(PDE))라는 간단한 식으로 페이지-디렉터리 항목(PDE)의 주소를 찾을 수 있다.
• 페이지-테이블 인덱스(page-table index)는 페이지 테이블 자체 인덱스로 사용된다. PTE의 주소는 PTEAddr = (PDE.PFN << SHIFT) + (PTIndex * sizeof(PTE))로 계산할 수 있다.

• 1. 페이지 디렉터리 항목을 보면 주소 공간에 2개의 유효한 영역이 있고, 그 사이에 무효한 매핑들이 존재한다.
• 2. 물리 페이지 100에 페이지 테이블의 첫 16개 항목이 존재한다. 이 항목들은 가상 주소 공간의 첫 16개 페이지에 대한 물리 주소를 가진다.
• 3. 페이지 테이블의 첫 번째 페이지에는 첫 16개의 VPN과 물리 페이지 주소가 있다.
• 4. 선형 페이지 테이블의 열여섯 개의 페이지들을 모두 할당하는 대신 단지 세 개만 할당하였다. 페이지 디렉터리를 위해서 한 페이지, 유효한 매핑 정보를 갖고 있는 페이지 테이블 내의 두 부분을 위해 두 페이지를 할당하였다.
• 주소 변환 과정(VPN 254의 0번째 바이트를 가리키는 주소: 11 1111 1000 0000)
  • 1. 페이지 디렉터리 내 각 항목을 가리키기 위해 VPN의 상위 4비트를 사용
    • 1111은 페이지 디렉터리의 마지막 엔트리. 페이지 디렉터리의 15번째 엔트리에는 물리 주소 101이 저장되어 있다.
  • 2. VPN의 다음 4비트(1110)을 인덱스로 사용하여, 페이지 테이블의 해당 페이지에서 원하는 PTE를 찾는다.
    • 1110은 101번 페이지의 16개 항목 중에 마지막에서 두 번째 항목이다. 여기에 55가 저장되어 있다.
  • 종합하면, 가상 주소 페이지 254(1111 1110)는 물리 페이지 55에 존재한다. 오프셋을 결합하여 물리 주소를 구할 수 있다. PhysAddr = (PTE.PFN << SHIFT) + offset

2단계 이상 페이지 테이블

• 멀티 레벨 페이지 테이블의 목적은 페이지 테이블의 모든 분할된 부분들이 단일 페이지 크기에 맞도록 하는 것이다.

  멀티 레벨 테이블은 몇 단계로 두어야 할까?
  

  1. 먼저 한 페이지에 몇 개의 페이지 테이블 항목을 저장할 수 있을지 계산한다.
  2. 페이지 크기가 512바이트이고, PTE의 크기가 4바이트라면 한 페이지에 128개의 PTE를 넣을 수 있다. 즉, 페이지 테이블의 페이지를 인덱스로 쓰려면 VPN의 하위 7비트가 필요하다.

• 앞의 그림을 보면, 페이지 디렉터리를 위해서 14개의 비트가 남는다.
  • 페이지 디렉터리를 위해서 128페이지 분량의 연속된 메모리가 필요하다.
  • 이는 페이지 테이블을 페이지 단위로 나누어 배치할 수 있는 멀티 레벨 페이지의 근본 취지가 훼손된 것이다.

• 이 문제를 해결하기 위해서 페이지 디렉터리 자체를 멀티 페이지들로 나누어서 트리의 단계를 늘리도록 한다.
  • 페이지 디렉터리의 페이지들을 가리킬 수 있도록 그 위에 새로운 페이지 디렉터리를 추가한다.
• 동작 과정
  • 1. 가상 주소의 최상위 비트들을(PT Index 0) 사용하여 상위 단계의 페이지 디렉터리에서 엔트리를 찾는다.
  • 2. 이 인덱스를 사용하여 상위 단계 페이지 디렉터리에서 페이지 디렉터리 항목을 가져온다.
  • 3. 만약 유효하다면, 상위 단계 페이지 디렉터리에서 얻은 물리 주소와 두 번째 단계의 페이지 디렉터리 인덱스(PD Index 1)을 결합하여 페이지 테이블 인덱스가 존재할 물리 페이지를 구한다.
  • 4. 해당 페이지가 유효할 경우, 최종적으로 PTE 주소는 2단째 단계의 페이지 디렉터리 항목에서 얻은 페이지 테이블의 물리 주소와 페이지 테이블 인덱스를 결합하여 구한다.

4. 역 페이지 테이블(inverted page table)

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