9. Memory Management(2)

Structure of the Page Table

• Hierarchical Paging

  • 논리 주소 공간을 여러 페이지 테이블로 분할

• Hashed Page Tables

• Inverted Page Tables

Two-Level Page-Table Scheme (Hierarchical Paging)

• 문제: 프로그램이 큰 주소 공간을 가짐

  • 32비트 주소와 4KB ($2^{12}$) 페이지 크기일 때 (m = 32, n = 12)
  • $m - n = 20$, 즉 $2^{20}$개의 논리 페이지
  • $2^{20}$개의 페이지 테이블 항목
  • 페이지 테이블 크기 = $2^{22}$ 바이트 (4MB, 각 항목이 4바이트일 경우)
  • 4MB 페이지 테이블을 저장하려면, 프로세스당 $2^{10} = 1K$개의 페이지 프레임 필요

• 해결:

  • 전체 페이지 테이블을 디스크에 저장
  • 페이지 테이블 자체도 페이지 단위로 요청 시 로딩 → 페이지 테이블을 위한 페이지 테이블 필요

Two-Level Page-Table Scheme

      outer-page
        table
          ↓
     +----------+       +----------+       +----------+
     |    1     | ----> |   500    |       |   page   | → 메모리 내 실제 페이지
     |    2     | ----> |   100    | →     |   100    |
     |    3     |       |   300    |       |   page   |
     |   ...    |       |   600    |       |   table  |
     +----------+       +----------+       +----------+

(어디에 논리 페이지에 대한 물리 페이지 번호를 저장하는 페이지 테이블 프레임이 있는가?)
(어디에 논리 페이지에 해당하는 실제 물리 페이지가 있는가?)

Two-Level Paging Example

• 논리 주소 (32비트 머신, 4KB 페이지 크기 기준)는 다음과 같이 나뉨:

  • 페이지 번호 (20비트)
  • 페이지 오프셋 (12비트)

• 페이지 번호는 두 부분으로 다시 나뉨:

  • 10비트 외부 페이지 번호: outer-page table에 접근
  • 10비트 내부 페이지 번호: page table 내에 접근

• 즉, 논리 주소 구성:

page number                page offset
   p₁       p₂                 d
   10       10                12

• 여기서:
  • p₁: outer-page table 내 인덱스
  • p₂: 내부 page table에서의 displacement

Address-Translation Scheme

• 2단계 32비트 페이징 구조의 주소 변환 방식:

logical address:   p₁ | p₂ | d
                       ↓
                outer-page table
                       ↓
                 page of page table
                       ↓
                       d

<Forward-mapped page table>

Multilevel Paging and Performance

• 더 큰 주소 공간의 경우,

  • 세 번째 페이지는 (B-트리처럼) 데이터 블록이 아닌, 또 다른 레벨의 페이지 테이블
  • 각 레벨이 메모리에 별도로 저장되므로, 논리 주소를 실제 주소로 변환할 때 최대 4회의 메모리 접근이 필요함

• 메모리 접근 시간이 5배로 증가하더라도, TLB를 통해 성능은 합리적인 수준으로 유지됨

  • 4단계 페이지 테이블에서도 TLB 히트율이 98%일 경우,

    $$EAT = 0.98 \times 120 + 0.02 \times 520 = 128~\text{nanoseconds}$$

    (메모리 접근 시간이 100ns일 때, TLB 접근 시간 = 20ns)

• 하지만 64비트 주소 체계에서는 6단계 페이징이 요구됨

  • 현실적으로 부적절함
  • 현대 64비트 운영체제에서는 48비트 주소를 사용하므로, 보통 4단계 페이징 사용

Hashed Page Tables

• 주소 공간이 32비트보다 클 경우에 적합
• 가상 페이지 번호를 해시 함수로 페이지 테이블에 매핑
  • 이 테이블은 동일 해시 위치에 대응하는 항목들의 체인으로 구성됨
  • 체인 내부에서 가상 페이지 번호와 일치하는 항목을 찾으면 해당 물리 주소를 반환

logical address (P | d)
   ↓
[hash function]
   ↓
[hash table] → [p1→p2→...] → 비교 → 일치 → [physical address]

Inverted Page Table

• 문제: 페이지 테이블이 너무 큼

  • 페이지 테이블의 크기는 전체 페이지 수에 비례
  • 논리 페이지마다 하나의 테이블 항목이 필요
  • 그러나 실제로는 동시에 적은 수의 페이지만 메모리에 존재함

• 해결: 논리 페이지가 아닌 물리적 페이지 프레임당 하나의 테이블 항목만 유지

  • 각 항목은 프로세스 ID 포함
  • 하나의 시스템 전역 페이지 테이블 사용
  • 필요한 항목 수는 물리 프레임 수와 동일
  • 모든 프로세스가 공유하는 구조

Inverted Page Table Architecture

• 단점:

  • 테이블 전체를 검색해야 함
  • 페이지 공유 불가능

• 해결책:

  • 해시 테이블을 사용해 검색 범위 제한 (한 번의 메모리 조회)
  • TLB와 병행 사용하여 속도 향상

CPU
 ↓
[logical address] → [search]
                         ↓
                  +------→ [page table]
                  |             ↓
[hash table] -----+         [physical address]

Segmentation

• 사용자의 메모리 관점을 지원하는 메모리 관리 기법
• 프로그램은 다양한 길이의 세그먼트들로 구성됨
• 세그먼트는 논리적 단위 (예: main(), 함수, 전역 변수, 스택, 심볼 테이블, 배열 등)

User's view of a program:

+--------------+
| subroutine   |
+--------------+
| stack        |
+--------------+
| symbol table |
+--------------+
| main program |
+--------------+

Segmentation Architecture

• 논리 주소 구조: <segment-number, offset>

• 세그먼트 테이블

  • 논리 주소를 물리 주소로 매핑
  • 각 항목은 다음 포함:
    • base: 세그먼트가 위치한 시작 물리 주소
    • limit: 세그먼트의 길이

• STBR (Segment-table base register):

  • 세그먼트 테이블의 물리 위치를 가리킴

• STLR (Segment-table length register):

  • 사용 가능한 세그먼트 수를 나타냄
  • 유효한 세그먼트 번호 조건: segment number < STLR

Example of Segmentation

User's view:

+--------------+    +--------------+
| subroutine   |    | segment 0    |
+--------------+    +--------------+
| stack        |    | segment 3    |
+--------------+    | segment 4    |
| symbol table |    | segment 1    |
+--------------+    | segment 2    |
| main program |    | segment 5    |
+--------------+    | segment 6    |
| segment 1    |    | segment 7    |
| segment 2    |    +--------------+
                   physical memory

세그먼트 테이블:

• segment 0 → base: 1400, limit: 1000
• segment 1 → base: 6300, limit: 400
• segment 2 → base: 4300, limit: 400 ...

Segmentation Hardware

logical address = (s, d)

          +--------+       +----------------+
CPU  ---> |   s    | ----> |  segment table |
          +--------+       +----------------+
                             |      |
                             v      v
                          limit    base
                             |      |
                             v      v
                       if d < limit?
                             | yes
                             v
                        physical address = base + d
                             |
                             v
                        physical memory

else → trap (addressing error)

Segmentation Architecture (Cont.)

• 보호 (Protection)

  • 세그먼트 테이블 항목마다 다음을 포함:
    • valid/invalid bit = 0 → illegal segment
    • RWX 권한 비트

• 공유 (Sharing)

  • 세그먼트 수준에서 공유가 발생
  • 공유 세그먼트의 경우, 모든 프로세스가 동일한 세그먼트 번호를 사용해야 함
    • 예: 자기참조 코드가 segment number와 offset으로 자신을 참조

• 할당 (Allocation)

  • 세그먼트의 길이는 가변적이므로, 메모리 할당은 동적 할당 문제
  • first fit / best fit 전략 사용
  • 외부 단편화 발생, 내부 단편화는 없음

Sharing of Segments

Process P1:
  segment 0 = editor
  segment 1 = data1

Process P2:
  segment 0 = editor
  segment 1 = data2

→ physical memory에서 editor는 공유되고,
   data1, data2는 각자 분리되어 저장됨

Segmentation with Paging

• 외부 단편화 문제는 세그먼트를 페이지로 나누는 것으로 해결 가능

• 이 방식은 순수 segmentation과 다름:

  • 세그먼트 테이블 항목은 세그먼트의 base 주소가 아니라, page table의 base 주소를 포함

• 가상 주소 형식:

Segment number s | Page number p | Displacement d
→ Virtual address V = (s, p, d)

Segmentation with Paging: Address Translation

logical address = (s, p, d)

   ↓
[STBR]
   ↓
segment table
   ↓
segment length, page-table base

   ↓
if p < segment length?
   ↓
yes → page table → frame → +d → physical address → memory
no  → trap (addressing error)

Segmentation with Paging (TLB incorporated)

• 가상 주소 구조:

  $$v = (s, p, d)$$

  • s: 세그먼트 번호
  • p: 페이지 번호
  • d: 변위 (offset)

• 흐름 요약:

1. 세그먼트 테이블 시작점 레지스터가 주소 b를 가리킴
2. 세그먼트 번호 s를 더해 해당 세그먼트 항목 주소 b + s로 접근
3. 세그먼트 테이블에서:
   • 페이지 사상표(page table)의 시작 주소 **s′**를 얻음
4. (s, p) 쌍이 TLB(연관 저장 장치)에 있는지 먼저 확인
   • 있으면 TLB에 저장된 p′ 값으로 바로 매핑
   • 없으면:
     • 페이지 사상표에서 p를 인덱스로 사용하여 페이지 프레임 번호 **p′**를 조회
     • TLB에 새 항목으로 저장 가능
5. 페이지 프레임 번호 **p′**와 변위 d를 더해 실제 주소 r을 계산

   $$r = p′ + d$$

가상주소 v = (s, p, d)
    ↓
TLB에서 (s, p) 조회
   ├─ 있으면 → p′ 얻음
   └─ 없으면
       └─ 세그먼트 테이블 시작 주소 b + s 접근
           └─ 세그먼트 s의 page table 주소 s′ 획득
               └─ page table에서 p 인덱스로 p′ 조회
                   └─ TLB에 (s, p) → p′ 저장

p′ + d → 실주소 r

FileSystem - 교수님 강의 내용 요약

페이지 테이블의 한계

• 하나의 page table이 너무 커질 경우, 연속적인 메모리 공간을 차지하기 어려움
• 1024개의 entry가 필요할 경우, 각각의 entry는 4KB frame으로 구성됨

다단계 페이지 테이블

• 페이지 테이블을 계층 구조로 나누어 관리
• Outer Page Table → Inner Page Table → Data Page
• 각 테이블은 하나의 frame에 1024개 entry를 가짐
• Logical Address: 상위 10비트 (outer index), 중간 10비트 (inner index), 하위 12비트 (offset)

주소 변환 방식

1. Logical Address를 10/10/12 비트로 나눔
2. Outer index → inner page table의 위치
3. Inner index → data page의 위치
4. offset을 더해서 최종 physical address 계산

64비트 주소 체계

• 너무 많은 entry로 인해 현실적으로 사용 어려움
• 실제 구현에서는 48비트만 사용 (4레벨 구조)
• TLB가 이 과정을 캐시하여 성능 저하 방지

Inverted Page Table

개념

• 기존 page table이 logical → physical 변환이라면,
• Inverted page table은 physical → logical 변환
• 전체 물리 메모리를 기준으로 하나의 page table만 유지

장점

• 프로세스마다 page table을 만들지 않아도 됨
• 메모리 절약 가능

문제점

• associative search 필요 → 성능 저하
• 공유 어려움 (PID 기반 매칭 필요)
• Sharing에 제약 많고 탐색시간이 증가함

해결 시도

• Hashing 기반 탐색 구조 사용
• Chain이 없는 hash function 설계가 핵심

Segmentation

개념

• 메모리를 의미 단위(함수, 라이브러리, 스택 등)로 나눔
• Logical address = segment 번호 + offset
• 주소 변환 시 base address + offset 방식

장점

• 의미 단위 공유 가능
• 다양한 protection level 부여 가능

단점

• 연속적 메모리 요구 → external fragmentation 발생 가능

Segmentation with Paging

개념

• Segmentation을 기반으로, 각 segment 안에 paging 기법 적용
• 각 segment는 paging 기법을 통해 내부 주소 공간 관리

장점

• 공유 단위 유지 (segment)
• paging을 통해 내부 fragmentation 해결

주소 변환 방식

1. Logical address = segment 번호 + offset
2. segment 번호 → 해당 segment의 page table 주소
3. offset → page index + page offset
4. 최종적으로 frame 번호 + offset으로 physical address 계산

정리: 주소 변환 과정

전체 흐름

• CPU가 logical address 생성 (seg#, page#, offset)
• TLB 실패 시 → segment table/page table 탐색
• frame 번호 획득 후 offset 더하여 physical address 생성

결론

• Multi-level paging, inverted page table, segmentation, segmentation with paging은 각기 다른 상황에서 trade-off를 가지는 메모리 관리 기법
• 효율적인 메모리 사용과 공유, 보호 수준 제공을 위한 다양한 구조적 시도