1. Page Table의 구조 (Structure of the Page Table)
Page table이 커지면 이를 효율적으로 관리하기 위한 다양한 기법이 필요하다.
- Hierarchical Paging (계층적 Paging)
- Hashed Page Tables
- Inverted Page Tables
2. Two-Level Page Table (Hierarchical Paging)
2.1 문제: Page Table이 너무 크다
32-bit 주소 체계, 4 KB (= 2^12) Page size일 때:
| 항목 | 값 |
|---|---|
| m (주소 비트 수) | 32 |
| n (Page offset 비트 수) | 12 |
| Page number 비트 수 (m - n) | 20 |
| Logical page 수 | 2^20 = 약 100만 개 |
| Page table entry 크기 | 4 Bytes |
| Page table 전체 크기 | 2^20 x 4 = 4 MB (= 2^22 bytes) |
| Page table 저장에 필요한 Frame 수 | 4 MB / 4 KB = 1 K (= 2^10) 개 |
프로세스 하나당 1,024개의 Frame을 Page table 저장에만 써야 한다.
2.2 해결: Page Table 자체를 Paging
- Page table 전체를 Disk에 저장
- Page table 자체를 Page 단위로 On-demand 로드
- Page table을 위한 Page table이 필요 ⇒ Two-Level Page Table
2.3 Two-Level Paging 주소 구조
32-bit 주소, 4 KB Page size에서 Logical address는 다음과 같이 분할된다:
| p1 (10 bits) | p2 (10 bits) | d (12 bits) |
| 필드 | 비트 수 | 역할 |
|---|---|---|
| p1 | 10 bits | Outer page table의 Index (1 K 개 항목) |
| p2 | 10 bits | Inner page table (Page of page table) 내의 Displacement (1 K 개 엔트리) |
| d | 12 bits | Page 내의 Offset (4 KB) |
2.4 Address Translation (Forward-Mapped Page Table)
동작 과정:
- p1을 사용하여 Outer page table에서 해당 Inner page table의 위치를 조회
- p2를 사용하여 Inner page table (Page of page table)에서 Physical frame 번호를 조회
- Frame 번호와 d를 결합하여 Physical address를 산출
3. Multilevel Paging과 성능
3.1 더 큰 주소 공간에서의 확장
- 주소 공간이 더 크면 3단계, 4단계 이상의 Paging이 필요 (B-tree와 유사한 구조)
- 각 Level은 별도의 테이블로 메모리에 저장
- Logical address를 Physical address로 변환하는 데 레벨 수 + 1번의 메모리 접근 필요
3.2 성능 분석
메모리 접근이 여러 번 필요하지만, TLB가 성능을 합리적인 수준으로 유지한다.
예제: 4-Level Paging
- TLB access time = 20 ns
- Memory access time = 100 ns
- TLB hit ratio = 98%
TLB hit: 20 + 100 = 120 ns (TLB 조회 + 실제 메모리 접근 1번)
TLB miss: 20 + 100 x 5 = 520 ns (TLB 조회 + Page table 4단계 + 실제 메모리 접근)
EAT = 0.98 x 120 + 0.02 x 520
= 117.6 + 10.4
= 128 ns
- 순수 메모리 접근(100 ns) 대비 28% 증가에 불과
- TLB hit ratio가 높으면 다단계 Paging의 오버헤드는 감수 가능
3.3 64-bit 주소 체계의 한계
- 64-bit 주소에 대해 Hierarchical paging을 적용하면 6단계가 필요 ⇒ 비현실적
- 현재 64-bit OS들은 실제로 48 bits만 주소 지정에 사용 ⇒ 4단계 Paging
4. Hashed Page Table
4.1 개념
- 32-bit 이상의 주소 공간에서 사용
- Virtual page number를 Hash function에 입력하여 Page table의 위치를 결정
- 같은 Hash 값에 매핑되는 엔트리들은 Chain(연결 리스트)으로 관리
4.2 동작 과정
- Logical address에서 Virtual page number (p)를 추출
- p를 Hash function에 입력 ⇒ Hash table의 특정 위치로 이동
- 해당 위치의 Chain에서 p와 일치하는 엔트리를 순차 검색
- 일치하는 엔트리를 찾으면 대응하는 Physical frame 번호 (r)를 추출
- Frame 번호 r과 Offset d를 결합하여 Physical address = (r, d) 생성
4.3 Chain 엔트리 구조
각 Chain 엔트리는 세 가지 필드를 포함:
| 필드 | 설명 |
|---|---|
| Virtual page number | Hash 충돌 시 비교용 |
| Physical frame number | 매핑된 Frame 번호 |
| Next pointer | Chain의 다음 엔트리를 가리킴 |
5. Inverted Page Table
5.1 문제: 왜 Page Table이 이렇게 큰가?
- 기존 Page table: Logical page 당 하나의 엔트리 ⇒ Page 수에 비례
- 실제로 메모리에 올라와 있는 Page는 소수
- 대부분의 엔트리가 낭비됨
5.2 해결: Physical frame 기준 Page Table
Inverted page table은 Logical page가 아닌 Physical page frame 당 하나의 엔트리를 가진다.
| 특징 | 설명 |
|---|---|
| 엔트리 수 | Physical memory의 Frame 수만큼 (고정) |
| 엔트리 내용 | Process ID (pid) + Page number |
| 범위 | 시스템 전체에서 하나의 Page table 공유 |
| 크기 | 전체 Physical memory frame 수에 비례 |
5.3 동작 과정
- CPU가 Logical address (pid, p, d)를 생성
- Inverted page table을 순차 검색하여 (pid, p)와 일치하는 엔트리를 찾음
- 일치하는 엔트리의 Index (i)가 곧 Physical frame 번호
- Physical address = (i, d)
5.4 장단점
| 설명 | |
|---|---|
| 장점 | Page table 크기가 Physical memory에 비례하여 작아짐 |
| 단점 1 | 전체 테이블을 순차 검색해야 함 ⇒ 느림 |
| 단점 2 | Page sharing이 불가능 (하나의 Frame에 하나의 pid만 매핑) |
5.5 단점 보완
| 보완책 | 설명 |
|---|---|
| Hash table | 검색 범위를 제한하여 탐색 속도 향상 (메모리 접근 1회 추가) |
| TLB | 자주 접근하는 Page의 변환 결과를 Cache하여 속도 향상 |
6. Segmentation
6.1 개념
Segmentation은 사용자 관점(User’s view)의 메모리 관리 기법이다.
프로그램은 다양한 가변 길이의 Segment들의 집합으로 구성된다:
- main()
- function (서브루틴)
- global variables
- stack
- symbol table
- arrays
6.2 Segmentation Architecture
Logical Address 구조
< segment-number (s), offset (d) >
Segmentation의 Logical address는 2차원이다: Segment 번호와 그 안에서의 Offset.
Segment Table
Segment table은 2차원 Logical address를 1차원 Physical address로 변환한다.
각 엔트리는 두 가지 정보를 포함:
| 필드 | 설명 |
|---|---|
| Base | Segment가 Physical memory에서 시작하는 실제 주소 |
| Limit | Segment의 길이 |
관련 레지스터
| 레지스터 | 설명 |
|---|---|
| STBR (Segment-Table Base Register) | Segment table이 메모리에서 위치하는 시작 주소 |
| STLR (Segment-Table Length Register) | 프로그램이 사용하는 Segment 수 |
Segment number s가 합법적이려면: s < STLR
6.3 Segmentation 예제
위 예제에서 5개의 Segment가 Physical memory의 서로 다른 위치에 배치되어 있다:
| Segment | Limit | Base |
|---|---|---|
| 0 | 1000 | 1400 |
| 1 | 400 | 6300 |
| 2 | 400 | 4300 |
| 3 | 1100 | 3200 |
| 4 | 1000 | 4700 |
6.4 Segmentation Hardware (주소 변환)
동작 과정:
- CPU가 Logical address (s, d)를 생성
- Segment number s로 Segment table에서 해당 엔트리 조회
- Offset d와 Limit 비교:
- d < Limit ⇒ 합법적 접근 ⇒ Base + d = Physical address
- d >= Limit ⇒ Trap (Addressing error)
7. Segmentation의 특성
7.1 Protection (보호)
Segment table의 각 엔트리에 Protection bit를 연결:
| 비트 | 설명 |
|---|---|
| Valid/Invalid bit | 0이면 불법 Segment |
| R/W/X bits | Read / Write / Execute 권한 |
7.2 Sharing (공유)
- Protection bit가 Segment 단위로 설정되므로, 코드 공유가 Segment 수준에서 이루어짐
- 공유 Segment를 사용하는 모든 프로세스는 동일한 Segment 번호를 사용해야 함
- 이유: Self-referencing code는 자신의 Segment 번호와 Offset으로 자기 자신을 참조하기 때문
위 예제에서 P1과 P2가 Editor(Segment 0)를 공유:
- 두 프로세스 모두 Segment 0의 Base = 43062, Limit = 25286
- Data segment(Segment 1)는 각각 별도로 보유
7.3 Allocation (할당)
- Segment는 가변 길이이므로, 메모리 할당은 Dynamic storage-allocation problem
- First-fit / Best-fit 전략 사용
- External fragmentation 발생 (Segment 사이에 빈 공간)
- Internal fragmentation은 없음 (정확한 크기만큼 할당)
8. Segmentation vs Paging 비교
| 특성 | Paging | Segmentation |
|---|---|---|
| 단위 크기 | 고정 (Fixed) | 가변 (Variable) |
| 사용자 인식 | 투명 (사용자 모름) | 사용자 관점 반영 |
| External fragmentation | 없음 | 있음 |
| Internal fragmentation | 있음 | 없음 |
| 공유 단위 | Page 단위 | Segment 단위 (논리적) |
| Protection | Page 단위 | Segment 단위 (의미 단위) |
9. Segmentation with Paging (세그먼테이션 + 페이징)
9.1 동기
Segmentation의 External fragmentation 문제를 Paging으로 해결한다.
핵심 아이디어: Segment 내부를 다시 Page로 분할
9.2 차이점
순수 Segmentation과의 차이:
- Segment table entry에 Segment의 Base address가 아니라, 해당 Segment의 Page table 시작 주소가 저장됨
9.3 Virtual Address 구조
| Segment number (s) | Page number (p) | Displacement (d) |
Virtual address v = (s, p, d)
9.4 Address Translation
동작 과정:
- Virtual address에서 Segment number (s)를 추출
- STBR + s로 Segment table에서 해당 엔트리 조회
- 엔트리: (Segment length, Page-table base)
- Offset d와 Segment length 비교:
- d >= Segment length ⇒ Trap
- d < Segment length ⇒ 계속 진행
- d를 Page number (p)와 Page offset (d’)으로 분할
- Page-table base + p로 해당 Segment의 Page table에서 Frame 번호 (f) 조회
- Physical address = (f, d’)
9.5 TLB 적용
TLB를 통합한 구조에서는:
- 먼저 (s, p)를 TLB에서 검색 (연관 저장장치)
- TLB hit: 바로 Frame 번호 p’를 얻음 ⇒ Physical address = (p’, d)
- TLB miss: Segment table ⇒ Page table을 순차적으로 조회
- STBR + s로 Segment table에서 Page table base (s’) 조회
- s’ + p로 Page table에서 Frame 번호 (p’) 조회
- 결과를 TLB에 캐싱
10. 핵심 정리
Page Table 구조 비교
| 구조 | Page Table 크기 | 메모리 접근 횟수 (TLB miss 시) | 특징 |
|---|---|---|---|
| Single-level | Logical page 수 x entry 크기 | 2 | 단순하지만 대형 주소 공간에서 비효율 |
| Two-level | Outer table + Inner tables | 3 | Page table 자체를 Paging |
| Multilevel | 여러 단계의 Table | Level + 1 | B-tree 구조와 유사 |
| Hashed | Hash table 크기 | 2 + Chain 탐색 | 32-bit 이상 주소 공간에 적합 |
| Inverted | Physical frame 수 x entry 크기 | 전체 탐색 or Hash 사용 | 시스템 전체에서 1개, Sharing 불가 |
EAT 공식 (다단계 Paging)
TLB hit 시: ε + β
TLB miss 시: ε + (Level + 1) x β
EAT = α x (ε + β) + (1 - α) x (ε + (Level + 1) x β)
여기서:
- ε = TLB lookup time
- β = Memory access time
- α = TLB hit ratio
- Level = Page table 단계 수
Segmentation with Paging의 이점
- Segmentation의 논리적 구분 (Protection, Sharing) 유지
- Paging으로 External fragmentation 제거
- 대부분의 현대 OS에서 변형된 형태로 사용