운영체제: 메모리 관리 ② - 페이징 (Paging) 기초

지난 글에서는 논리 주소와 물리 주소의 개념, 주소 바인딩 시점, 그리고 초기 메모리 할당 방식인 연속 할당과 그 문제점(단편화)에 대해 알아보았습니다. 연속 할당 방식의 가장 큰 문제인 외부 단편화(External Fragmentation)를 해결하기 위해 등장한 것이 바로 불연속 할당(Noncontiguous Allocation) 기법이며, 그중 가장 널리 사용되는 핵심 기술이 페이징(Paging)입니다.

이번 글에서는 현대 운영체제 메모리 관리의 근간을 이루는 페이징 기법의 기본 원리, 주소 변환 과정, 페이지 테이블 구현 및 성능 향상을 위한 TLB, 그리고 페이지 테이블 크기 문제를 해결하기 위한 2단계 페이징(Two-Level Paging)까지 자세히 살펴보겠습니다.

https://core.ewha.ac.kr/publicview/C0101020140429132440045277?vmode=f

반효경 [운영체제] 19. Memory Management 2

설명이 없습니다.

core.ewha.ac.kr

1. 페이징 (Paging) 기본 개념

페이징은 외부 단편화 문제를 해결하고, 더 나아가 물리 메모리보다 큰 논리 주소 공간을 지원(가상 메모리)하기 위한 핵심 아이디어에서 출발합니다.

핵심 아이디어:
1. 프로세스의 논리 주소 공간(Logical Address Space)을 페이지(Page)라는 고정된 크기의 블록으로 나눕니다.
2. 물리 메모리(Physical Memory) 역시 페이지와 동일한 크기의 프레임(Frame)이라는 블록으로 나눕니다.
동작 방식:
- 프로세스가 실행될 때, 그 프로세스를 구성하는 페이지(들)가 물리 메모리의 비어있는 프레임(들)에 불연속적으로(Noncontiguous) 적재됩니다. 즉, 논리적으로 연속된 페이지들이 물리적으로는 여기저기 흩어져 있을 수 있습니다.
- 운영체제는 각 프로세스마다 페이지 테이블(Page Table)이라는 자료구조를 관리합니다. 이 테이블은 각 페이지가 어떤 프레임에 적재되었는지 매핑 정보를 저장합니다.
- CPU가 논리 주소를 참조하면, MMU는 페이지 테이블을 이용하여 해당 논리 주소가 속한 페이지에 대응하는 프레임 번호를 찾고, 이를 이용해 물리 주소를 계산하여 메모리에 접근합니다.
주소 변환 (Address Translation) 과정:
- CPU가 생성하는 논리 주소는 두 부분으로 구성됩니다.
  - 페이지 번호 (Page Number, p): 해당 주소가 속한 페이지의 번호. 페이지 테이블의 인덱스로 사용됩니다.
  - 오프셋 (Offset, d): 페이지 내에서의 상대적인 위치(변위).
- MMU는 다음과 같은 단계로 물리 주소를 계산합니다.
  1. 논리 주소에서 페이지 번호(p)를 추출합니다.
  2. 운영체제가 관리하는 해당 프로세스의 페이지 테이블에서 페이지 번호 p에 해당하는 항목(Entry)을 찾습니다.
  3. 이 항목에는 해당 페이지가 적재된 프레임 번호(Frame Number, f)가 저장되어 있습니다.
  4. MMU는 프레임 번호 f와 논리 주소의 오프셋(d)을 결합하여 최종 물리 주소(Physical Address)를 생성합니다.
    (물리 주소 = f * 프레임 크기 + d, 또는 간단히 (f, d))
  - 핵심: 오프셋(d) 값은 변환 과정에서 변경되지 않습니다. 페이지 내에서의 상대적인 위치는 논리 주소나 물리 주소나 동일하기 때문입니다. 오직 페이지 번호(p)가 프레임 번호(f)로 변환될 뿐입니다.
```
      논리 주소 (Logical Address)
      +-------------+-------------+
      | Page Number |   Offset    |
      |      (p)    |      (d)    |
      +-------------+-------------+
             |
             V
      +-------------+ <------- Page Table Base Register (PTBR)
      | Page Table  |
      |-------------|
      | Frame f0    |  (Entry 0)
      |-------------|
      | Frame f1    |  (Entry 1)
      |-------------|
      |   ...       |
p --> |-------------|
      | Frame f     |  (Entry p)  <-- 페이지 번호 p로 프레임 번호 f 찾기
      |-------------|
      |   ...       |
      +-------------+
             |
             V        물리 주소 (Physical Address)
      +-------------+-------------+
      | Frame Number|   Offset    |
      |      (f)    |      (d)    | <--- 오프셋(d)는 그대로 사용
      +-------------+-------------+
                  |
                  V
             [물리 메모리]
```

[Q&A]

Q: "페이지 크기는 어떻게 정해지나요? 크거나 작으면 어떤 영향이 있나요?"
A: 페이지 크기는 하드웨어(MMU)에 의해 결정되며, 보통 2의 거듭제곱 형태(예: 4KB, 8KB, 2MB, 1GB 등)입니다.
- 페이지 크기가 작으면:
  - 장점: 내부 단편화(Internal Fragmentation) 감소 (페이지의 마지막 부분이 덜 낭비됨). 메모리 활용률 증가.
  - 단점: 페이지 테이블의 크기가 커짐 (페이지 개수가 많아지므로). 페이지 테이블 접근 오버헤드 증가 가능성. 디스크 I/O 효율 감소 가능성.
- 페이지 크기가 크면:
  - 장점: 페이지 테이블 크기 감소. TLB(아래 설명)의 효율성 증가. 디스크 I/O 효율 증가.
  - 단점: 내부 단편화 증가.
- 최근 시스템은 메모리 용량이 커짐에 따라 더 큰 페이지 크기(Huge Page)를 지원하는 경향이 있습니다.
Q: "페이징은 외부 단편화는 해결하지만 내부 단편화는 발생시킨다고 했는데, 왜 그런가요?"
A: 외부 단편화는 가용 메모리가 작은 조각들로 흩어져 발생하는 문제입니다. 페이징은 물리 메모리를 고정 크기 프레임으로 나누고, 프로세스 페이지를 비어있는 어떤 프레임에든 적재할 수 있으므로, 프레임 단위로 관리가 되어 외부 단편화가 발생하지 않습니다. 하지만 내부 단편화는 발생합니다. 프로세스의 크기가 페이지 크기의 배수가 아닐 경우, 마지막 페이지는 해당 페이지 크기 전체를 다 사용하지 못하고 남는 공간이 생기게 됩니다. 이 남는 공간이 바로 내부 단편화입니다.

2. 페이지 테이블 구현 (Implementation of Page Table)

페이지 테이블은 논리 주소를 물리 주소로 변환하는 핵심 정보인데, 이 테이블은 어디에 저장되고 어떻게 접근할까요?

저장 위치: 페이지 테이블은 각 프로세스의 중요한 문맥 정보이므로, 주 메모리(Main Memory)에 상주합니다. 각 프로세스는 자신만의 페이지 테이블을 가집니다.
접근 방법 (레지스터 활용):
- 페이지 테이블 기준 레지스터 (Page-Table Base Register, PTBR): 현재 실행 중인 프로세스의 페이지 테이블이 메모리 어디에 시작하는지 그 시작 주소를 가지고 있는 특별한 CPU 레지스터입니다. 문맥 교환(Context Switch) 시 이 레지스터 값도 함께 교체됩니다.
- 페이지 테이블 길이 레지스터 (Page-Table Length Register, PTLR): 해당 프로세스의 페이지 테이블 크기(즉, 페이지 개수)를 저장하는 레지스터입니다. 논리 주소의 페이지 번호가 PTLR 값보다 크거나 같으면 유효하지 않은 접근(주소 공간 벗어남)이므로 메모리 보호 오류(Trap)를 발생시킵니다.
성능 문제: 메모리 접근 2배 증가!
- 페이지 테이블이 주 메모리에 있다면, CPU가 메모리에 한 번 접근할 때마다 두 번의 메모리 접근이 필요하게 됩니다.
  1. 페이지 테이블 접근: 논리 주소의 페이지 번호(p)를 이용해 PTBR + p 위치의 페이지 테이블 엔트리를 읽어 프레임 번호(f)를 가져옵니다. (메모리 접근 #1)
  2. 실제 데이터 접근: 얻어낸 프레임 번호(f)와 오프셋(d)을 조합하여 계산된 물리 주소로 실제 데이터나 명령어에 접근합니다. (메모리 접근 #2)
- 이는 메모리 접근 속도를 절반으로 떨어뜨리는 심각한 성능 저하를 유발합니다.

3. TLB (Translation Lookaside Buffer): 페이지 테이블 캐싱

페이지 테이블 접근으로 인한 성능 저하 문제를 해결하기 위해 대부분의 시스템은 TLB(Translation Lookaside Buffer)라는 고속의 하드웨어 캐시(Cache)를 사용합니다. TLB는 연관 메모리(Associative Memory) 방식으로 구현되어 매우 빠르게 검색이 가능합니다.

TLB란?
- 최근에 사용된 페이지 번호(p)와 프레임 번호(f)의 매핑 정보를 일부 저장해두는 작은 크기의 하드웨어 캐시입니다.
  (Key: Page #, Value: Frame #)
동작 방식:
1. CPU가 논리 주소를 생성하면, MMU는 먼저 TLB를 검색합니다.
2. TLB Hit: 만약 해당 페이지 번호(p)가 TLB에 존재하면, 즉시 프레임 번호(f)를 얻어 물리 주소를 계산하고 메모리에 접근합니다. (페이지 테이블 메모리 접근 불필요!)
3. TLB Miss: 만약 해당 페이지 번호(p)가 TLB에 없다면,
  a. 주 메모리에 있는 페이지 테이블에 접근하여 프레임 번호(f)를 얻어옵니다. (메모리 접근 #1 발생)
  b. 얻어온 (p, f) 매핑 정보를 TLB에 새로 저장합니다. (오래된 항목은 교체될 수 있음 - LRU 등)
  c. 프레임 번호(f)를 이용해 물리 주소를 계산하고 실제 데이터에 접근합니다. (메모리 접근 #2 발생)
문맥 교환 시 처리: TLB는 현재 실행 중인 프로세스의 주소 매핑 정보를 담고 있으므로, 문맥 교환이 발생하면 이전 프로세스의 TLB 내용은 비워야(Flush) 합니다. 그렇지 않으면 새로운 프로세스가 이전 프로세스의 주소 매핑 정보를 잘못 사용할 수 있습니다. (일부 시스템은 ASID(Address Space Identifier)를 이용해 프로세스별 TLB 항목을 구분하여 Flush 오버헤드를 줄이기도 합니다.)
유효 접근 시간 (Effective Access Time, EAT) 계산:
- TLB 검색 시간: ε (입실론, 매우 작음)
- 주 메모리 접근 시간: 1 (단위 시간)
- TLB 적중률 (Hit Ratio): α (알파, 0 ≤ α ≤ 1, 보통 매우 높음)
- EAT =
  (TLB 접근 시간 + 메모리 접근 시간) * TLB 적중률
  + (TLB 접근 시간 + 페이지 테이블 접근 시간 + 실제 메모리 접근 시간) * TLB 실패율
- 만약 ε이 매우 작아 무시 가능하고, α가 1에 가깝다면 (예: α = 0.99), EAT ≈ 2 - α ≈ 1.01 이 됩니다. 즉, TLB 덕분에 메모리 접근 시간이 거의 2배에서 거의 1배 수준으로 크게 향상됩니다.

[Q&A]

Q: "TLB는 캐시인데, 왜 페이지 테이블 전체를 캐싱하지 않고 일부만 저장하나요?"
A: TLB는 매우 빠른 검색 속도를 제공해야 하므로, 고가의 연관 메모리(Associative Memory) 또는 하드웨어적으로 구현된 캐시 구조를 사용합니다. 이러한 고속 메모리는 용량이 제한적이고 비쌉니다. 따라서 모든 페이지 테이블 엔트리를 저장할 수는 없고, 지역성(Locality) 원리에 기반하여 최근에 자주 사용된 매핑 정보만 저장하여 높은 적중률(Hit Ratio)을 달성하는 것을 목표로 합니다.
Q: "문맥 교환 시 TLB를 비우는(Flush) 오버헤드는 없나요?"
A: 네, 오버헤드가 있습니다. TLB를 비우면 새로운 프로세스가 실행될 때 처음에는 TLB Miss가 많이 발생하여 성능이 일시적으로 저하될 수 있습니다. 이 오버헤드를 줄이기 위해 일부 시스템에서는 ASID(Address Space ID) 또는 PCID(Process-Context ID) 같은 태그를 TLB 항목에 추가하여, 문맥 교환 시 전체를 비우지 않고 해당 프로세스 ID에 맞는 항목만 사용하도록 하는 최적화 기법을 사용합니다.

4. 2단계 페이징 (Two-Level Paging): 거대한 페이지 테이블 문제 해결

현대 컴퓨터 시스템은 64비트 아키텍처를 사용하며 매우 큰 논리 주소 공간을 지원합니다. 예를 들어, 32비트 시스템만 해도 2³² = 4GB의 논리 주소 공간을 가집니다.

문제점: 만약 페이지 크기가 4KB (2¹² 바이트)라면,
- 논리 주소는 20비트 페이지 번호(p)와 12비트 오프셋(d)으로 나뉩니다.
- 페이지 개수는 2²⁰ = 1M (약 100만 개) 입니다.
- 각 페이지 테이블 항목(PTE)이 4바이트라고 가정하면, 하나의 프로세스당 페이지 테이블 크기만 1M * 4B = 4MB가 됩니다!
- 만약 프로세스가 100개 실행된다면 페이지 테이블만으로 400MB의 메모리가 필요합니다.
- 더 큰 문제는, 대부분의 프로세스는 자신에게 할당된 4GB의 논리 주소 공간 중 극히 일부만 실제로 사용한다는 것입니다. 즉, 페이지 테이블의 대부분 항목은 사용되지 않는 공간을 가리키며 심각한 메모리 낭비를 유발합니다.
해결책: 페이지 테이블 자체를 페이징하자!
- 아이디어: 거대한 단일 페이지 테이블을 사용하는 대신, 페이지 테이블 자체를 여러 개의 페이지로 나누고, 실제로 필요한 부분만 메모리에 유지하는 방식입니다.
- 2단계 페이징 구조:
  1. 외부 페이지 테이블 (Outer Page Table): 논리 주소의 페이지 번호(p)를 다시 두 부분으로 나눕니다.
    - p1: 외부 페이지 테이블의 인덱스.
    - p2: 내부 페이지 테이블 내에서의 오프셋(또는 인덱스).
  2. 논리 주소는 이제 (p1, p2, d) 세 부분으로 구성됩니다.
  3. 주소 변환 과정:
    a. CPU가 논리 주소 (p1, p2, d) 생성.
    b. MMU는 p1을 인덱스로 사용하여 외부 페이지 테이블에 접근합니다.
    c. 외부 페이지 테이블의 해당 항목은 내부 페이지 테이블(두 번째 레벨 페이지 테이블)의 시작 주소(프레임 번호)를 가리킵니다.
    d. MMU는 이 주소와 p2를 이용하여 내부 페이지 테이블의 해당 항목에 접근합니다.
    e. 내부 페이지 테이블의 항목에는 최종 데이터가 있는 실제 데이터 프레임 번호(f)가 저장되어 있습니다.
    f. 프레임 번호 f와 오프셋 d를 결합하여 최종 물리 주소를 계산합니다.
```
      논리 주소 (Logical Address)
      +-----+-----+-------------+
      | p1  | p2  |   Offset(d) |
      +-----+-----+-------------+
        |      |
        V      |
  +-------------+ <------- PTBR (Outer Page Table 시작 주소)
  | Outer Page  |
  | Table       |
  |-------------|
  | Inner PT @f'|  (Entry p1) <--- p1으로 내부 페이지 테이블 주소(f') 찾기
  |-------------|
  |   ...       |
  +-------------+
        |
        V        +-------------+ <------- f' (Inner Page Table 시작 프레임)
        |        | Inner Page  |
        |        | Table       |
        +------->|-------------|
                 | Frame f     |  (Entry p2) <--- p2로 실제 데이터 프레임(f) 찾기
                 |-------------|
                 |   ...       |
                 +-------------+
                        |
                        V        물리 주소 (Physical Address)
                 +-------------+-------------+
                 | Frame f     |   Offset(d) |
                 +-------------+-------------+
                             |
                             V
                        [물리 메모리]
    
```
2단계 페이징의 장점:
- 메모리 절약: 프로세스가 사용하지 않는 논리 주소 공간에 대해서는 내부 페이지 테이블을 아예 할당하지 않을 수 있습니다. 외부 페이지 테이블의 해당 항목을 NULL(또는 유효하지 않음)으로 표시하면 됩니다. 이를 통해 페이지 테이블이 차지하는 메모리 공간을 획기적으로 줄일 수 있습니다.
단점: 주소 변환을 위해 메모리 접근 횟수가 한 번 더 늘어납니다. (외부 PT 접근 + 내부 PT 접근 + 실제 데이터 접근 = 총 3번). 이 문제는 TLB를 통해 대부분 완화됩니다. TLB Hit 시에는 한 번의 메모리 접근만 필요합니다.
32비트 예시 상세:
- 논리 주소 32비트, 페이지 크기 4KB (2¹² 바이트)
- 오프셋(d): 12비트
- 페이지 번호(p): 32 - 12 = 20비트
- 페이지 테이블 항목(PTE) 크기: 4바이트 (32비트)
- 하나의 페이지(4KB)에는 4KB / 4B = 1K (2¹⁰)개의 PTE를 저장할 수 있습니다.
- 따라서, 내부 페이지 테이블 하나를 가리키기 위한 인덱스(p2)는 10비트가 필요합니다. (2¹⁰ = 1K)
- 남은 페이지 번호 비트(p1)는 20 - 10 = 10비트가 됩니다. 이 p1이 외부 페이지 테이블의 인덱스가 됩니다.
- 결과: 논리 주소는 p1(10비트) | p2(10비트) | d(12비트) 로 구성됩니다.
64비트 시스템에서는?
- 64비트 주소 공간은 훨씬 더 큽니다 (2⁶⁴). 페이지 크기가 4KB라면 페이지 번호 비트가 52비트나 됩니다.
- 2단계 페이징만으로는 여전히 외부 페이지 테이블이 너무 커질 수 있습니다.
- 따라서 실제 64비트 시스템(x86-64 등)에서는 3단계, 4단계, 심지어 5단계 다중 레벨 페이징(Multi-Level Paging)을 사용하여 페이지 테이블 크기를 효율적으로 관리합니다. 원리는 2단계와 동일하게 단계적으로 테이블을 찾아 들어가는 방식입니다.

[Q&A]

Q: "2단계 페이징에서 사용되지 않는 주소 공간에 대해 내부 페이지 테이블을 할당하지 않는다는 것이 어떻게 메모리를 절약하나요?"
A: 예를 들어 4GB 논리 주소 공간을 가진 프로세스가 실제로는 10MB 정도만 사용한다고 가정해 봅시다. 단일 단계 페이징에서는 사용 여부와 관계없이 4GB 전체를 커버하는 4MB짜리 페이지 테이블이 필요했습니다. 2단계 페이징에서는 프로세스가 사용하는 10MB 영역에 해당하는 내부 페이지 테이블들만 할당하고, 나머지 대부분의 주소 공간에 대해서는 외부 페이지 테이블 항목을 NULL로 두어 해당 내부 페이지 테이블 자체를 생성하지 않습니다. 따라서 페이지 테이블이 차지하는 실제 메모리 크기가 사용량에 비례하여 크게 줄어듭니다.
Q: "다중 레벨 페이징은 메모리 접근 횟수를 너무 많이 늘리는 것 아닌가요?"
A: 네, 이론적으로는 그렇습니다. 4단계 페이징이라면 주소 변환에만 4번의 메모리 접근이 필요할 수 있습니다. 하지만 TLB(Translation Lookaside Buffer)의 존재 덕분에 이러한 성능 저하는 대부분 상쇄됩니다. TLB는 최종 변환 결과(논리 페이지 번호 → 물리 프레임 번호)를 캐싱하므로, TLB Hit가 발생하면 중간 단계의 페이지 테이블 접근 없이 바로 물리 주소를 얻을 수 있습니다. TLB 적중률이 매우 높기 때문에 실제 평균 메모리 접근 시간은 크게 증가하지 않습니다.

[마무리하며]

페이징은 연속 메모리 할당의 단편화 문제를 해결하고 현대 운영체제의 가상 메모리 시스템을 구현하는 핵심 기법입니다. 논리 주소를 페이지 번호와 오프셋으로 나누고, 페이지 테이블을 통해 물리 프레임 번호로 변환하는 과정이 핵심입니다. 페이지 테이블 접근으로 인한 성능 저하는 TLB라는 하드웨어 캐시를 통해 효과적으로 해결하며, 거대한 페이지 테이블 크기 문제는 다중 레벨 페이징 기법을 통해 관리합니다.

다음 글에서는 페이지 테이블의 구조와 보호 비트, 공유 페이지 등 페이징의 더 구체적인 내용과 세그멘테이션 기법에 대해 알아보겠습니다.

'운영체제 > 반효경 교수' 카테고리의 다른 글

운영체제: 가상 메모리 ① - 요구 페이징과 페이지 교체 기초 (0)	2025.04.15
운영체제: 메모리 관리 ③ - 페이징 심화 및 세그멘테이션 (0)	2025.04.14
운영체제: 메모리 관리 ① - 주소 변환과 메모리 할당 기초 (0)	2025.04.13
운영체제: 교착 상태 (Deadlock) - 원인과 해결 전략 (0)	2025.04.13
운영체제: 프로세스 동기화 - 모니터 (Monitor)를 이용한 병행 제어 (0)	2025.04.13

절차탁마

운영체제: 메모리 관리 ② - 페이징 (Paging) 기초

1. 페이징 (Paging) 기본 개념

2. 페이지 테이블 구현 (Implementation of Page Table)

3. TLB (Translation Lookaside Buffer): 페이지 테이블 캐싱

4. 2단계 페이징 (Two-Level Paging): 거대한 페이지 테이블 문제 해결

'운영체제 > 반효경 교수' 카테고리의 다른 글

티스토리툴바

운영체제: 메모리 관리 ② - 페이징 (Paging) 기초

1. 페이징 (Paging) 기본 개념

2. 페이지 테이블 구현 (Implementation of Page Table)

3. TLB (Translation Lookaside Buffer): 페이지 테이블 캐싱

4. 2단계 페이징 (Two-Level Paging): 거대한 페이지 테이블 문제 해결

'운영체제 > 반효경 교수' 카테고리의 다른 글

관련글

티스토리툴바