페이징 ⭐⭐⭐
페이징 ⭐⭐⭐¶
개요¶
페이징(Paging)은 물리 메모리를 고정 크기 블록(프레임)으로 나누고, 프로세스의 논리 주소 공간도 같은 크기의 블록(페이지)으로 나누어 비연속적으로 할당하는 메모리 관리 기법입니다. 외부 단편화를 완전히 제거할 수 있습니다.
목차¶
1. 페이징의 기본 개념¶
1.1 페이지와 프레임¶
┌─────────────────────────────────────────────────────────────────────────┐
│ 페이징의 기본 구조 │
├─────────────────────────────────────────────────────────────────────────┤
│ │
│ 논리 주소 공간 (프로세스) 물리 주소 공간 (RAM) │
│ │
│ ┌────────────────┐ ┌────────────────┐ │
│ │ 페이지 0 │ ──────────────────▶ │ 프레임 1 │ │
│ ├────────────────┤ ├────────────────┤ │
│ │ 페이지 1 │ ─────┐ │ 프레임 2 │ │
│ ├────────────────┤ │ ├────────────────┤ │
│ │ 페이지 2 │ ───┐ │ │ 프레임 3 │ ◀────────┐ │
│ ├────────────────┤ │ │ ├────────────────┤ │ │
│ │ 페이지 3 │ ─┐ │ └────────────▶ │ 프레임 4 │ │ │
│ └────────────────┘ │ │ ├────────────────┤ │ │
│ │ │ │ 프레임 5 │ ◀─────┐ │ │
│ │ │ ├────────────────┤ │ │ │
│ │ └───────────────▶│ 프레임 6 │ │ │ │
│ │ ├────────────────┤ │ │ │
│ └─────────────────▶│ 프레임 7 │ │ │ │
│ └────────────────┘ │ │ │
│ │ │ │
│ 페이지 크기 = 프레임 크기 (예: 4KB) │ │ │
│ 페이지는 어떤 프레임에든 배치 가능! │ │ │
│ 외부 단편화 없음! │ │ │
│ │ │ │
│ 다른 프로세스의 페이지들 ─────────────────────────────────────────┘ │ │
│ (같은 물리 메모리 공유) │ │
└─────────────────────────────────────────────────────────────────────────┘
1.2 주요 용어¶
| 용어 | 설명 |
|---|---|
| 페이지 (Page) | 논리 주소 공간의 고정 크기 블록 |
| 프레임 (Frame) | 물리 메모리의 고정 크기 블록 |
| 페이지 테이블 | 페이지 → 프레임 매핑 정보 |
| 페이지 번호 (p) | 논리 주소에서 페이지 식별 |
| 오프셋 (d) | 페이지/프레임 내 위치 |
2. 주소 변환¶
2.1 논리 주소 구조¶
┌─────────────────────────────────────────────────────────────────────────┐
│ 논리 주소 구조 (32비트 예시) │
├─────────────────────────────────────────────────────────────────────────┤
│ │
│ 32비트 논리 주소 │
│ ┌─────────────────────────────┬─────────────────┐ │
│ │ 페이지 번호 (p) │ 오프셋 (d) │ │
│ │ 20비트 │ 12비트 │ │
│ └─────────────────────────────┴─────────────────┘ │
│ │
│ 페이지 크기 = 2^12 = 4KB │
│ 최대 페이지 수 = 2^20 = 약 100만 개 │
│ 최대 주소 공간 = 2^32 = 4GB │
│ │
└─────────────────────────────────────────────────────────────────────────┘
2.2 주소 변환 과정¶
┌─────────────────────────────────────────────────────────────────────────┐
│ 주소 변환 과정 │
├─────────────────────────────────────────────────────────────────────────┤
│ │
│ 논리 주소: 0x00005A34 │
│ │
│ 1. 주소 분리 (페이지 크기: 4KB = 0x1000) │
│ ┌───────────────────────────────────────┐ │
│ │ 0x00005A34 │ │
│ │ = 0x00005 (페이지 번호) + 0xA34 (오프셋)│ │
│ └───────────────────────────────────────┘ │
│ │
│ 2. 페이지 테이블 조회 │
│ ┌────────────┬────────────┐ │
│ │ 페이지 번호 │ 프레임 번호 │ │
│ ├────────────┼────────────┤ │
│ │ 0 │ 2 │ │
│ │ 1 │ 7 │ │
│ │ 2 │ 1 │ │
│ │ 3 │ 5 │ │
│ │ 4 │ 8 │ │
│ │ 5 │ 3 │ ◀── 페이지 5 → 프레임 3 │
│ └────────────┴────────────┘ │
│ │
│ 3. 물리 주소 계산 │
│ 물리 주소 = (프레임 번호 × 페이지 크기) + 오프셋 │
│ = (3 × 0x1000) + 0xA34 │
│ = 0x3000 + 0xA34 │
│ = 0x3A34 │
│ │
│ 결과: 논리 주소 0x5A34 → 물리 주소 0x3A34 │
│ │
└─────────────────────────────────────────────────────────────────────────┘
2.3 C언어 구현¶
#include <stdio.h>
#include <stdint.h>
#define PAGE_SIZE 4096 // 4KB
#define PAGE_BITS 12 // log2(4096)
#define NUM_PAGES 1024 // 페이지 테이블 엔트리 수
typedef struct {
uint32_t frame_number;
uint8_t valid; // 유효 비트
uint8_t read_only; // 읽기 전용
uint8_t modified; // 수정됨 (dirty bit)
} PageTableEntry;
PageTableEntry page_table[NUM_PAGES];
// 논리 주소 → 물리 주소 변환
uint32_t translate_address(uint32_t logical_address) {
// 1. 페이지 번호와 오프셋 분리
uint32_t page_number = logical_address >> PAGE_BITS;
uint32_t offset = logical_address & (PAGE_SIZE - 1);
printf("논리 주소: 0x%08X\n", logical_address);
printf("페이지 번호: %u, 오프셋: 0x%X\n", page_number, offset);
// 2. 페이지 테이블 범위 검사
if (page_number >= NUM_PAGES) {
printf("ERROR: 페이지 번호 초과!\n");
return -1;
}
// 3. 유효 비트 검사
if (!page_table[page_number].valid) {
printf("PAGE FAULT: 페이지 %u가 메모리에 없음\n", page_number);
return -1; // 페이지 폴트 처리 필요
}
// 4. 물리 주소 계산
uint32_t frame_number = page_table[page_number].frame_number;
uint32_t physical_address = (frame_number << PAGE_BITS) | offset;
printf("프레임 번호: %u\n", frame_number);
printf("물리 주소: 0x%08X\n", physical_address);
return physical_address;
}
int main() {
// 페이지 테이블 초기화
page_table[0] = (PageTableEntry){.frame_number = 2, .valid = 1};
page_table[1] = (PageTableEntry){.frame_number = 7, .valid = 1};
page_table[2] = (PageTableEntry){.frame_number = 1, .valid = 1};
page_table[5] = (PageTableEntry){.frame_number = 3, .valid = 1};
// 주소 변환 테스트
translate_address(0x00000A34); // 페이지 0
printf("\n");
translate_address(0x00005A34); // 페이지 5
return 0;
}
2.4 계산 예제¶
┌─────────────────────────────────────────────────────────────────────────┐
│ 주소 변환 계산 예제 │
├─────────────────────────────────────────────────────────────────────────┤
│ │
│ 문제: 페이지 크기 = 1KB, 논리 주소 = 4500 │
│ │
│ 풀이: │
│ 1. 페이지 크기 = 1024 = 2^10 바이트 │
│ → 오프셋 = 10비트 │
│ │
│ 2. 논리 주소 분리: │
│ 페이지 번호 = 4500 / 1024 = 4 (정수 나눗셈) │
│ 오프셋 = 4500 % 1024 = 404 │
│ │
│ 검증: 4 × 1024 + 404 = 4096 + 404 = 4500 ✓ │
│ │
│ 3. 페이지 테이블 조회: 페이지 4 → 프레임 7 │
│ │
│ 4. 물리 주소 = 프레임 7 × 1024 + 404 │
│ = 7168 + 404 │
│ = 7572 │
│ │
│ 이진수로 확인: │
│ - 논리 주소 4500 = 0001 0001 1001 0100 │
│ ├─────────┤├─────────┤ │
│ 페이지 4 오프셋 404 │
│ │
│ - 물리 주소 7572 = 0001 1101 1001 0100 │
│ ├─────────┤├─────────┤ │
│ 프레임 7 오프셋 404 (동일!) │
│ │
└─────────────────────────────────────────────────────────────────────────┘
3. 페이지 테이블¶
3.1 페이지 테이블 엔트리 (PTE)¶
┌─────────────────────────────────────────────────────────────────────────┐
│ 페이지 테이블 엔트리 구조 (32비트) │
├─────────────────────────────────────────────────────────────────────────┤
│ │
│ 31 12 11 4 3 2 1 0 │
│ ┌──────────────────────────────────┬──────────┬─┬─┬─┬─┐ │
│ │ 프레임 번호 (20비트) │ 예약 │D│A│U│V│ │
│ └──────────────────────────────────┴──────────┴─┴─┴─┴─┘ │
│ │
│ V (Valid): 유효 비트 │
│ 0 = 페이지가 메모리에 없음 (페이지 폴트 발생) │
│ 1 = 페이지가 메모리에 있음 │
│ │
│ U (User): 사용자 접근 허용 │
│ 0 = 커널 모드만 접근 가능 │
│ 1 = 사용자 모드에서도 접근 가능 │
│ │
│ A (Accessed): 접근됨 비트 │
│ 접근 시 하드웨어가 1로 설정 │
│ 페이지 교체 알고리즘에서 사용 │
│ │
│ D (Dirty): 수정됨 비트 │
│ 쓰기 시 하드웨어가 1로 설정 │
│ 페이지 아웃 시 디스크에 써야 하는지 결정 │
│ │
└─────────────────────────────────────────────────────────────────────────┘
3.2 페이지 테이블 저장 위치¶
┌─────────────────────────────────────────────────────────────────────────┐
│ 페이지 테이블과 PTBR │
├─────────────────────────────────────────────────────────────────────────┤
│ │
│ CPU │
│ ┌────────────────────────────────────────┐ │
│ │ │ │
│ │ PTBR (Page Table Base Register) │ │
│ │ ┌────────────────────────────────┐ │ │
│ │ │ 0x00100000 │───┼───────┐ │
│ │ └────────────────────────────────┘ │ │ │
│ │ │ │ │
│ │ PTLR (Page Table Length Register) │ │ │
│ │ ┌────────────────────────────────┐ │ │ │
│ │ │ 1024 │ │ │ │
│ │ └────────────────────────────────┘ │ │ │
│ │ │ │ │
│ └────────────────────────────────────────┘ │ │
│ │ │
│ ▼ │
│ 물리 메모리 │
│ ┌────────────────────────────────────────────────────┐ │
│ │ │ │
│ │ 주소 0x00100000 │ │
│ │ ┌───────────────────────────────────────────┐ │ │
│ │ │ 페이지 테이블 (프로세스 A) │ │ │
│ │ │ ┌──────────────┬────────────────────┐ │ │ │
│ │ │ │ 페이지 0 │ 프레임 5 | V=1 │ │ │ │
│ │ │ │ 페이지 1 │ 프레임 2 | V=1 │ │ │ │
│ │ │ │ 페이지 2 │ 프레임 8 | V=1 │ │ │ │
│ │ │ │ ... │ ... │ │ │ │
│ │ │ └──────────────┴────────────────────┘ │ │ │
│ │ └───────────────────────────────────────────┘ │ │
│ │ │ │
│ └────────────────────────────────────────────────────┘ │
│ │
│ 컨텍스트 스위칭 시: PTBR 값을 새 프로세스의 페이지 테이블 주소로 변경 │
│ │
└─────────────────────────────────────────────────────────────────────────┘
3.3 메모리 접근 문제¶
┌─────────────────────────────────────────────────────────────────────────┐
│ 2번의 메모리 접근 문제 │
├─────────────────────────────────────────────────────────────────────────┤
│ │
│ 페이징 사용 시 메모리 접근: │
│ │
│ CPU ──▶ 논리 주소 발생 │
│ │ │
│ ▼ │
│ [1] 페이지 테이블 접근 (메모리 접근 #1) │
│ │ │
│ ▼ │
│ 프레임 번호 획득 │
│ │ │
│ ▼ │
│ [2] 실제 데이터 접근 (메모리 접근 #2) │
│ │ │
│ ▼ │
│ 데이터 획득 │
│ │
│ 문제: 메모리 접근이 2배로 느려짐! │
│ 해결: TLB (Translation Lookaside Buffer) 사용 │
│ │
└─────────────────────────────────────────────────────────────────────────┘
4. TLB (Translation Lookaside Buffer)¶
4.1 TLB 개념¶
┌─────────────────────────────────────────────────────────────────────────┐
│ TLB 구조 │
├─────────────────────────────────────────────────────────────────────────┤
│ │
│ CPU 내부 또는 MMU 내부의 고속 캐시 │
│ │
│ ┌────────────────────────────────────────────────────────────┐ │
│ │ TLB │ │
│ ├────────────────────────────────────────────────────────────┤ │
│ │ 페이지 번호 │ 프레임 번호 │ ASID │ Valid │ │
│ ├──────────────────┼───────────────────┼────────────┼─────────┤ │
│ │ 5 │ 3 │ 1 │ 1 │ │
│ │ 2 │ 7 │ 1 │ 1 │ │
│ │ 12 │ 9 │ 2 │ 1 │ │
│ │ 0 │ 1 │ 1 │ 1 │ │
│ │ ... │ ... │ ... │ ... │ │
│ └────────────────────────────────────────────────────────────┘ │
│ │
│ ASID (Address Space ID): 프로세스 식별자 │
│ → 컨텍스트 스위칭 시 TLB 전체를 비우지 않아도 됨 │
│ │
│ 엔트리 수: 보통 64 ~ 1024개 (매우 작음, 그러나 매우 빠름) │
│ │
└─────────────────────────────────────────────────────────────────────────┘
4.2 TLB를 사용한 주소 변환¶
┌─────────────────────────────────────────────────────────────────────────┐
│ TLB를 사용한 주소 변환 │
├─────────────────────────────────────────────────────────────────────────┤
│ │
│ 논리 주소 │
│ │ │
│ ▼ │
│ ┌─────────────────────────────────┐ │
│ │ 페이지 번호 추출 │ │
│ └─────────────────────────────────┘ │
│ │ │
│ ▼ │
│ ┌─────────────────────────────────┐ │
│ │ TLB에서 검색 │ │
│ └─────────────────────────────────┘ │
│ │ │
│ ├───────────────────────────────────┐ │
│ │ │ │
│ TLB Hit TLB Miss │
│ │ │ │
│ ▼ ▼ │
│ 프레임 번호 페이지 테이블 접근 │
│ 즉시 획득 (메모리 접근) │
│ │ │ │
│ │ ▼ │
│ │ TLB 업데이트 │
│ │ │ │
│ └───────────────────────────────────┘ │
│ │ │
│ ▼ │
│ 물리 주소 계산 │
│ │ │
│ ▼ │
│ 메모리 접근 │
│ │
└─────────────────────────────────────────────────────────────────────────┘
4.3 유효 접근 시간 (EAT)¶
┌─────────────────────────────────────────────────────────────────────────┐
│ 유효 접근 시간 계산 │
├─────────────────────────────────────────────────────────────────────────┤
│ │
│ 파라미터: │
│ - TLB 검색 시간: ε (예: 10ns) │
│ - 메모리 접근 시간: m (예: 100ns) │
│ - TLB 적중률: α (예: 0.98 = 98%) │
│ │
│ EAT 공식: │
│ EAT = α × (ε + m) + (1-α) × (ε + 2m) │
│ ↑ TLB Hit 시 ↑ TLB Miss 시 │
│ │
│ 예제 계산: │
│ ε = 10ns, m = 100ns, α = 0.98 │
│ │
│ EAT = 0.98 × (10 + 100) + 0.02 × (10 + 200) │
│ = 0.98 × 110 + 0.02 × 210 │
│ = 107.8 + 4.2 │
│ = 112ns │
│ │
│ 비교: │
│ - TLB 없을 때: 200ns (2번 메모리 접근) │
│ - TLB 있을 때: 112ns │
│ - 성능 향상: 약 44% │
│ │
│ TLB 적중률이 높을수록 성능 향상이 큼 │
│ α = 0.99일 때: EAT = 0.99×110 + 0.01×210 = 112ns │
│ │
└─────────────────────────────────────────────────────────────────────────┘
5. 다단계 페이지 테이블¶
5.1 문제점¶
32비트 주소 공간, 4KB 페이지 크기의 경우: - 페이지 수 = 2^32 / 2^12 = 2^20 = 약 100만 개 - PTE 크기 = 4바이트 - 페이지 테이블 크기 = 100만 × 4 = 4MB (프로세스당!)
5.2 2단계 페이지 테이블¶
┌─────────────────────────────────────────────────────────────────────────┐
│ 2단계 페이지 테이블 │
├─────────────────────────────────────────────────────────────────────────┤
│ │
│ 32비트 논리 주소: │
│ ┌──────────────┬──────────────┬──────────────┐ │
│ │ p1 (10비트) │ p2 (10비트) │ d (12비트) │ │
│ │ 외부 페이지 │ 내부 페이지 │ 오프셋 │ │
│ └──────────────┴──────────────┴──────────────┘ │
│ │ │ │ │
│ │ │ │ │
│ ▼ │ │ │
│ ┌────────────┐ │ │ │
│ │ 외부 페이지 │ │ │ │
│ │ 테이블 │ │ │ │
│ │ (1단계) │ │ │ │
│ ├────────────┤ │ │ │
│ │ ... │ │ │ │
│ │ p1 엔트리 │────────┼──────┐ │ │
│ │ ... │ │ │ │ │
│ └────────────┘ │ │ │ │
│ │ ▼ │ │
│ │ ┌────────────┐ │
│ │ │ 내부 페이지 │ │
│ │ │ 테이블 │ │
│ │ │ (2단계) │ │
│ │ ├────────────┤ │
│ │ │ ... │ │
│ └▶ │ p2 엔트리 │───▶ 프레임 번호 │
│ │ ... │ │ │
│ └────────────┘ │ │
│ │ │
│ ▼ │
│ 물리 주소 = 프레임 × 4KB + d │
│ │
└─────────────────────────────────────────────────────────────────────────┘
5.3 64비트 시스템의 4단계 페이지 테이블¶
┌─────────────────────────────────────────────────────────────────────────┐
│ 64비트 4단계 페이지 테이블 (x86-64) │
├─────────────────────────────────────────────────────────────────────────┤
│ │
│ 64비트 가상 주소 (실제 사용: 48비트) │
│ ┌──────────────────────────────────────────────────────────────┐ │
│ │ 미사용 │ PML4 │ PDPT │ PD │ PT │ Offset │ │
│ │ (16) │ (9) │ (9) │ (9) │ (9) │ (12) │ │
│ └──────────────────────────────────────────────────────────────┘ │
│ │ │ │ │ │ │
│ ▼ ▼ ▼ ▼ │ │
│ ┌───────┐ ┌───────┐ ┌───────┐ ┌───────┐ │ │
│ CR3 ──▶ │ PML4 │─▶│ PDPT │─▶│ PD │─▶│ PT │───┼───▶ 물리 주소 │
│ │ Table │ │ Table│ │ Table │ │ Table │ │ │
│ └───────┘ └───────┘ └───────┘ └───────┘ │ │
│ │ │
│ 각 레벨: 512 엔트리 (2^9), 8바이트/엔트리 │ │
│ 테이블 크기: 512 × 8 = 4KB (= 1 페이지) │ │
│ │ │
│ PML4: Page Map Level 4 │ │
│ PDPT: Page Directory Pointer Table │ │
│ PD: Page Directory │ │
│ PT: Page Table │ │
│ │
└─────────────────────────────────────────────────────────────────────────┘
5.4 다단계 테이블의 장점¶
// 다단계 페이지 테이블의 메모리 절약 예시
// 프로세스가 사용하는 메모리:
// - 코드: 0x00000000 ~ 0x00100000 (1MB, 256페이지)
// - 스택: 0xBFF00000 ~ 0xC0000000 (1MB, 256페이지)
// 단일 페이지 테이블: 4MB 필요 (100만 엔트리 모두)
// 2단계 페이지 테이블:
// - 1단계 테이블: 4KB (1024 엔트리)
// - 2단계 테이블: 필요한 것만!
// - 코드 영역: 1개 × 4KB
// - 스택 영역: 1개 × 4KB
// 총: 4KB + 4KB + 4KB = 12KB (4MB → 12KB로 절약!)
typedef struct {
uint32_t present : 1;
uint32_t writable : 1;
uint32_t user : 1;
uint32_t reserved : 9;
uint32_t frame : 20; // 다음 레벨 테이블 또는 프레임
} PageTableEntry;
// 2단계 주소 변환
uint32_t translate_two_level(uint32_t virtual_addr) {
uint32_t p1 = (virtual_addr >> 22) & 0x3FF; // 상위 10비트
uint32_t p2 = (virtual_addr >> 12) & 0x3FF; // 중간 10비트
uint32_t offset = virtual_addr & 0xFFF; // 하위 12비트
// 1단계 테이블 접근
PageTableEntry* level1 = (PageTableEntry*)PTBR;
if (!level1[p1].present) {
// 2단계 테이블이 없음
page_fault_handler();
return -1;
}
// 2단계 테이블 접근
PageTableEntry* level2 = (PageTableEntry*)(level1[p1].frame << 12);
if (!level2[p2].present) {
// 페이지가 메모리에 없음
page_fault_handler();
return -1;
}
// 물리 주소 계산
uint32_t frame = level2[p2].frame;
return (frame << 12) | offset;
}
6. 해시 페이지 테이블¶
6.1 구조¶
┌─────────────────────────────────────────────────────────────────────────┐
│ 해시 페이지 테이블 │
├─────────────────────────────────────────────────────────────────────────┤
│ │
│ 가상 페이지 번호 │
│ │ │
│ ▼ │
│ ┌─────────────┐ │
│ │ 해시 함수 │ │
│ └─────────────┘ │
│ │ │
│ ▼ │
│ 해시 테이블 │
│ ┌───────────────────────────────────────────────────────────────┐ │
│ │ 인덱스 │ 체인 │ │
│ ├────────┼───────────────────────────────────────────────────────┤ │
│ │ 0 │ [p=102, f=5] → [p=2050, f=12] → NULL │ │
│ │ 1 │ NULL │ │
│ │ 2 │ [p=55, f=8] → NULL │ │
│ │ 3 │ [p=1003, f=3] → [p=7, f=22] → [p=4099, f=1] → NULL │ │
│ │ ... │ ... │ │
│ └────────┴───────────────────────────────────────────────────────┘ │
│ │
│ p = 가상 페이지 번호 │
│ f = 물리 프레임 번호 │
│ │
│ 장점: 희소한 주소 공간에서 효율적 (64비트 시스템) │
│ 단점: 해시 충돌 시 체인 검색 필요 │
│ │
└─────────────────────────────────────────────────────────────────────────┘
6.2 구현¶
#define HASH_TABLE_SIZE 1024
typedef struct HashEntry {
uint64_t virtual_page;
uint64_t physical_frame;
struct HashEntry* next;
} HashEntry;
HashEntry* hash_table[HASH_TABLE_SIZE];
// 해시 함수
uint32_t hash(uint64_t virtual_page) {
return virtual_page % HASH_TABLE_SIZE;
}
// 프레임 번호 검색
int64_t lookup(uint64_t virtual_page) {
uint32_t index = hash(virtual_page);
HashEntry* entry = hash_table[index];
while (entry != NULL) {
if (entry->virtual_page == virtual_page) {
return entry->physical_frame;
}
entry = entry->next;
}
return -1; // 페이지 폴트
}
// 매핑 추가
void insert(uint64_t virtual_page, uint64_t physical_frame) {
uint32_t index = hash(virtual_page);
HashEntry* new_entry = malloc(sizeof(HashEntry));
new_entry->virtual_page = virtual_page;
new_entry->physical_frame = physical_frame;
new_entry->next = hash_table[index];
hash_table[index] = new_entry;
}
7. 역 페이지 테이블¶
7.1 개념¶
┌─────────────────────────────────────────────────────────────────────────┐
│ 역 페이지 테이블 │
├─────────────────────────────────────────────────────────────────────────┤
│ │
│ 일반 페이지 테이블: │
│ - 각 프로세스마다 별도의 테이블 │
│ - 가상 주소 → 물리 주소 매핑 │
│ - 테이블 크기 = 가상 주소 공간에 비례 │
│ │
│ 역 페이지 테이블: │
│ - 시스템 전체에 하나의 테이블 │
│ - 물리 프레임별로 엔트리 │
│ - 테이블 크기 = 물리 메모리 크기에 비례 │
│ │
│ ┌──────────────────────────────────────────────────────────────┐ │
│ │ 프레임 번호 │ PID │ 가상 페이지 번호 │ 보호 비트 │ │
│ ├─────────────┼───────────┼───────────────────┼───────────────┤ │
│ │ 0 │ 1 │ 0x1234 │ R/W │ │
│ │ 1 │ 2 │ 0x0001 │ R/W │ │
│ │ 2 │ 1 │ 0x1235 │ R/O │ │
│ │ 3 │ 3 │ 0x5678 │ R/W │ │
│ │ ... │ ... │ ... │ ... │ │
│ │ N │ 2 │ 0x0002 │ R/W │ │
│ └─────────────┴───────────┴───────────────────┴───────────────┘ │
│ │
│ 검색: (PID, 가상 페이지 번호)로 프레임 번호 찾기 │
│ │
└─────────────────────────────────────────────────────────────────────────┘
7.2 장단점¶
┌─────────────────────────────────────────────────────────────────────────┐
│ 역 페이지 테이블 장단점 │
├─────────────────────────────────────────────────────────────────────────┤
│ │
│ 장점: │
│ ┌─────────────────────────────────────────────────────────────────┐ │
│ │ 1. 메모리 절약 │ │
│ │ - 물리 메모리 4GB, 프레임 4KB │ │
│ │ - 엔트리 수 = 4GB / 4KB = 1M개 │ │
│ │ - 엔트리당 16바이트 → 총 16MB (프로세스 수와 무관!) │ │
│ │ │ │
│ │ 2. 64비트 시스템에서 효율적 │ │
│ │ - 가상 주소 공간이 매우 크지만 │ │
│ │ - 물리 메모리는 상대적으로 작음 │ │
│ └─────────────────────────────────────────────────────────────────┘ │
│ │
│ 단점: │
│ ┌─────────────────────────────────────────────────────────────────┐ │
│ │ 1. 검색 시간 │ │
│ │ - 순차 검색: O(n) - 너무 느림 │ │
│ │ - 해시 테이블 사용 필요 │ │
│ │ │ │
│ │ 2. 메모리 공유 어려움 │ │
│ │ - 하나의 프레임에 하나의 (PID, 페이지) 쌍만 저장 │ │
│ │ - 공유 메모리 구현 복잡 │ │
│ └─────────────────────────────────────────────────────────────────┘ │
│ │
│ 사용 예: IBM PowerPC, UltraSPARC, IA-64 │
│ │
└─────────────────────────────────────────────────────────────────────────┘
연습 문제¶
문제 1: 주소 변환¶
페이지 크기가 4KB인 시스템에서 다음 조건일 때 물리 주소를 계산하시오.
- 논리 주소: 25000
- 페이지 테이블: 페이지 6 → 프레임 4
정답 보기
1. 페이지 크기 = 4KB = 4096바이트
2. 페이지 번호 = 25000 / 4096 = 6 (정수 나눗셈)
오프셋 = 25000 % 4096 = 424
검증: 6 × 4096 + 424 = 24576 + 424 = 25000 ✓
3. 페이지 테이블 조회: 페이지 6 → 프레임 4
4. 물리 주소 = 프레임 4 × 4096 + 424
= 16384 + 424
= 16808
문제 2: TLB EAT 계산¶
다음 조건에서 유효 접근 시간(EAT)을 계산하시오.
- TLB 접근 시간: 20ns
- 메모리 접근 시간: 100ns
- TLB 적중률: 95%
정답 보기
EAT = α × (ε + m) + (1-α) × (ε + 2m)
= 0.95 × (20 + 100) + 0.05 × (20 + 200)
= 0.95 × 120 + 0.05 × 220
= 114 + 11
= 125ns
비교: TLB 없을 때 200ns, TLB 있을 때 125ns (37.5% 향상)
문제 3: 페이지 테이블 크기¶
32비트 가상 주소 공간, 4KB 페이지, 4바이트 PTE인 시스템에서: 1. 단일 페이지 테이블의 크기는? 2. 2단계 페이지 테이블을 사용할 때 주소 비트 할당은?
정답 보기
1. 단일 페이지 테이블:
- 페이지 수 = 2^32 / 2^12 = 2^20 (약 100만)
- PTE 크기 = 4바이트
- 테이블 크기 = 2^20 × 4 = 4MB
2. 2단계 페이지 테이블:
- 총 32비트 = 오프셋(12비트) + 페이지 테이블(20비트)
- 20비트를 두 레벨로 분할: 10비트 + 10비트
주소 구조: [p1: 10비트][p2: 10비트][offset: 12비트]
각 레벨 테이블:
- 엔트리 수 = 2^10 = 1024
- 테이블 크기 = 1024 × 4 = 4KB (= 1 페이지에 딱 맞음)
문제 4: 다단계 테이블 메모리¶
프로세스가 다음 영역만 사용할 때, 2단계 페이지 테이블의 총 크기를 계산하시오.
- 코드: 0x00000000 ~ 0x00400000 (4MB)
- 데이터: 0x10000000 ~ 0x10100000 (1MB)
- 스택: 0xBFF00000 ~ 0xC0000000 (1MB)
정답 보기
페이지 크기 = 4KB, 2단계 테이블 (10비트 + 10비트 + 12비트)
1단계 인덱스 분석:
- 코드 (0x00000000~0x00400000): p1 = 0
- 데이터 (0x10000000~0x10100000): p1 = 64
- 스택 (0xBFF00000~0xC0000000): p1 = 767
필요한 테이블:
- 1단계 테이블: 1개 × 4KB = 4KB
- 2단계 테이블: 3개 × 4KB = 12KB (인덱스 0, 64, 767에 해당)
총 크기 = 4KB + 12KB = 16KB
비교: 단일 테이블이었다면 4MB 필요
절약률: (4MB - 16KB) / 4MB = 99.6% 절약!
문제 5: 역 페이지 테이블 설계¶
물리 메모리가 1GB이고 페이지 크기가 8KB인 시스템에서 역 페이지 테이블을 설계하시오. - 엔트리에 필요한 필드와 크기 - 테이블의 총 크기
정답 보기
1. 프레임 수 = 1GB / 8KB = 2^30 / 2^13 = 2^17 = 131,072개
2. 엔트리 구조:
- PID: 16비트 (최대 65536 프로세스)
- 가상 페이지 번호: 51비트 (64비트 주소 - 13비트 오프셋)
- 보호 비트: 4비트 (R/W/X/Valid)
- 기타: 9비트 (여유)
총: 80비트 = 10바이트 (또는 패딩해서 16바이트)
3. 테이블 크기:
- 엔트리 수: 131,072
- 엔트리 크기: 16바이트
- 총 크기: 131,072 × 16 = 2MB
이는 물리 메모리(1GB)의 0.2%에 해당
다음 단계¶
13_Segmentation.md에서 세그멘트 기반 메모리 관리를 배워봅시다!
참고 자료¶
- Silberschatz, "Operating System Concepts" Chapter 9
- Intel 64 and IA-32 Architectures Software Developer's Manual
- AMD64 Architecture Programmer's Manual
- Linux kernel source:
arch/x86/mm/pgtable.c