Memory Management Strategies

Kamator0·2026년 5월 20일

멀티프로그래밍을 위한 메모리 관리

핵심 요구사항

멀티프로그래밍(multiprogramming)이란 여러 프로세스가 동시에 물리 메모리에 적재되어 실행되는 것을 말한다. 이를 위해 다음 두 가지가 반드시 필요하다:

동시 적재: 여러 프로세스가 물리 메모리에 함께 존재해야 한다.
보호 메커니즘: 사용자 프로세스가 운영체제 메모리와 다른 프로세스의 메모리에 접근하지 못하도록 막아야 한다.

Base Register & Limit Register

가장 기본적인 메모리 보호 구현 방법은 두 개의 레지스터를 사용하는 것이다:

레지스터	역할	예시
Base Register (기저 레지스터)	해당 프로세스에 할당된 가장 작은 합법적 물리 주소	30004
Limit Register (한계 레지스터)	해당 프로세스의 주소 범위(크기)	12090

하드웨어 기반 주소 보호

CPU가 user mode에서 생성하는 모든 주소에 대해 하드웨어가 자동으로 다음을 검사한다:

CPU가 생성한 주소
       │
       ▼
   주소 ≥ base?
   ├── NO → trap (주소 오류)
   └── YES
         │
         ▼
   주소 < base + limit?
   ├── NO → trap (주소 오류)
   └── YES → 메모리 접근 허용

핵심 포인트:

이 검사는 하드웨어가 자동으로 수행한다 (소프트웨어 개입 없음).
허용 범위를 벗어난 접근 시 trap이 발생하여 운영체제가 개입한다.
Base/Limit 레지스터 값 변경은 특권 명령(privileged instruction)이므로 커널 모드에서만 가능하다.

논리 주소 vs 물리 주소

개념 정의

용어	영어	설명
논리 주소 (= 가상 주소)	Logical address / Virtual address	CPU가 생성하는 주소
가상 주소 공간	Virtual address space	실행 중인 프로그램이 생성하는 모든 주소의 집합
물리 주소	Physical address	실제 DRAM 상의 주소
물리 주소 공간	Physical address space	논리 주소에 대응되는 모든 물리 주소의 집합

MMU (Memory Management Unit)

프로세서 내부의 하드웨어로, 가상 주소를 물리 주소로 변환한다.
MMU의 구체적인 매핑 방법은 프로세서 아키텍처마다 다르다.
중요한 점: 주소 변환은 하드웨어가 자동으로 수행하며, 소프트웨어의 도움 없이 이루어진다.

핵심 관계

CPU가 생성하는 주소 = 논리(가상) 주소
                          │
                      [ MMU 변환 ]
                          │
                          ▼
              메모리에 보내는 주소 = 물리 주소

가상 주소의 필요성

가상 주소가 없다면?

만약 사용자 프로그램이 실제 물리 주소를 직접 다룬다면 다음과 같은 문제가 생긴다:

사용자가 직접 프로그램을 특정 물리 메모리에 로드해야 한다.
다른 프로그램의 메모리를 훼손하지 않도록 메모리 연산을 주의 깊게 작성해야 한다.

이것은 매우 비현실적이고 고통스러운 일이다.

가상 주소가 제공하는 해결책

사용자 프로그램은 실제 물리 주소를 절대 보지 않는다.
모든 프로세스에게 주소 0부터 시작하는 것 같은 환상(illusion)을 제공한다.
프로그램 로더가 프로그램을 적절한 물리 메모리 위치에 배치하고, MMU가 프로그램의 가상 주소를 물리 주소로 변환한다.

Relocation Register를 사용한 간단한 주소 변환

가장 간단한 MMU 구현은 relocation register(재배치 레지스터, base register와 동일)를 사용하는 것이다:

                    relocation register
                    ┌───────┐
                    │ 14000 │
                    └───┬───┘
                        │
  CPU ──► 논리주소 346 ──►[+]──► 물리주소 14346 ──► 메모리
                        MMU

물리 주소 = relocation register 값 + CPU가 생성한 논리 주소

사용자 프로세스가 생성하는 모든 주소에 relocation register 값이 더해진다.
사용자 프로그램은 주소 346만 알고, 실제 물리 주소 14346은 모른다.

메모리 매핑과 보호

두 레지스터의 역할

레지스터	저장하는 값
Relocation Register	가장 작은 물리 주소 (= base address)
Limit Register	논리 주소의 범위 (= 프로세스 크기)

동작 과정

  CPU가 생성한
  논리 주소(d)
       │
       ▼
  d < limit register?
  ├── NO → trap (주소 오류)
  └── YES
        │
        ▼
  d + relocation register = 물리 주소 → 메모리 접근

컨텍스트 스위칭 시

스케줄러가 프로세스를 선택하여 실행시킬 때, 해당 프로세스의 PCB에 저장된 relocation/limit 레지스터 값을 로드한다.
따라서 프로세스마다 다른 base/limit 값을 가진다.

예시: Process 1 (base=30004, limit=12090)

Process 1이 논리 주소 5000을 생성하면:
1. 5000 < 12090 (limit)? → YES, 범위 내
2. 물리 주소 = 30004 + 5000 = 35004
3. 메모리 주소 35004에 접근

Process 1이 논리 주소 15000을 생성하면:
1. 15000 < 12090 (limit)? → NO, 범위 밖
2. trap 발생 → 운영체제가 불법 접근 처리

연속 메모리 할당

동기

멀티프로그래밍을 위해 여러 프로세스가 물리 메모리에 동시에 존재해야 하며, 각 프로세스의 메모리를 보호하기 위해 relocation/limit 레지스터가 필요하다.

개념

연속 메모리 할당(Contiguous Memory Allocation)이란 각 프로세스가 물리 메모리의 하나의 연속된 영역에 적재되는 방식이다.

┌──────────────┐ 0
│  Process 0   │
├──────────────┤ 10000
│  Process 1   │
├──────────────┤ 15000
│  Process 2   │
├──────────────┤ 25000
│  Process 3   │
├──────────────┤ 30000
│  (빈 공간)    │
└──────────────┘

다중 파티션 할당 (Multiple-Partition Allocation)

Hole: 사용 가능한 메모리 블록. 다양한 크기의 hole이 메모리 여기저기에 산재한다.
프로세스가 도착하면, 충분히 큰 hole에서 메모리를 할당받는다.
프로세스가 종료되면 메모리를 반환하여 다른 프로세스가 사용할 수 있게 된다.
운영체제는 (a) 할당된 파티션과 (b) 빈 파티션(hole) 정보를 관리한다.

동적 변화 예시

[초기 상태]        [P5 종료]         [P9 도착]
┌────────┐       ┌────────┐       ┌────────┐
│   OS   │       │   OS   │       │   OS   │
├────────┤       ├────────┤       ├────────┤
│   P5   │       │  hole  │       │   P9   │
├────────┤       ├────────┤       ├────────┤
│   P8   │  →    │   P8   │  →    │   P8   │  → ...
├────────┤       ├────────┤       ├────────┤
│   P2   │       │   P2   │       │   P2   │
└────────┘       └────────┘       └────────┘

외부 단편화

정의

프로세스가 반복적으로 메모리에 적재되고 제거되면, 빈 공간이 작은 조각들로 분산된다. 전체 빈 공간을 합치면 요청을 만족할 수 있지만, 연속된 공간이 없어서 새 프로세스를 할당할 수 없는 상황을 외부 단편화(External Fragmentation)라 한다.

┌────────┐
│   OS   │
├────────┤
│  hole  │  ← 작은 빈 공간
├────────┤
│   P9   │
├────────┤
│  hole  │  ← 작은 빈 공간
├────────┤
│   P2   │
├────────┤
│  hole  │  ← 작은 빈 공간
└────────┘

→ hole들을 합치면 충분하지만, 연속되지 않아서 큰 프로세스를 할당 불가!

해결 방법

방법 1: 압축 (Compaction)

메모리 내용을 재배치(shuffle)하여 모든 빈 공간을 하나의 큰 블록으로 모으는 것.

조건: 재배치가 동적(dynamic)이고 실행 시점(execution time)에 이루어져야만 가능하다.

[압축 전]              [압축 후]
┌────────┐           ┌────────┐
│   OS   │           │   OS   │
├────────┤           ├────────┤
│  hole  │           │   P9   │
├────────┤    →      ├────────┤
│   P9   │           │   P2   │
├────────┤           ├────────┤
│  hole  │           │   P10  │
├────────┤           ├────────┤
│   P2   │           │ 큰 hole │ 
├────────┤           │        │
│  hole  │           │        │
└────────┘           └────────┘

방법 2: 비연속 주소 공간 (Non-contiguous Address Space)

프로세스에게 물리 메모리가 어디든 사용 가능한 곳에 할당될 수 있도록 한다. 즉, 한 프로세스가 물리적으로 떨어진 여러 조각에 흩어져 적재될 수 있다.

→ 이것이 바로 페이징(Paging)의 핵심 아이디어!

페이징

동기

현대 시스템에서 프로세스는 빈번하게 종료, swap out/in 된다.
연속 할당 방식에서는 외부 단편화 때문에 멀티프로그래밍 정도가 줄어든다.
다양한 크기의 메모리 조각을 빈 공간에 맞추는 것은 매우 번거롭다.

페이징이란?

페이징(Paging)은 프로세스의 물리 주소 공간이 비연속적(noncontiguous)일 수 있도록 허용하는 메모리 관리 기법이다.

핵심 개념

용어	영어	설명
페이지 (Page)	Page	가상 메모리를 고정 크기로 나눈 논리적 블록
프레임 (Frame)	Page Frame	물리 메모리를 같은 크기로 나눈 물리적 블록
페이지 테이블	Page Table	페이지와 프레임 간의 매핑 정보를 담는 테이블

가상 주소 공간          물리 주소 공간
┌────────┐            ┌────────┐ Frame 0
│ Page 0 │╲           │        │
├────────┤ ╲          ├────────┤ Frame 1
│ Page 1 │  ╲─────────│ Page 0 │ ← Page 0은 Frame 1에
├────────┤  ╱─────────├────────┤ Frame 2
│ Page 2 │╱           │        │
├────────┤    ┌───────├────────┤ Frame 3
│ Page 3 │────┘       │ Page 2 │ ← Page 2는 Frame 3에
└────────┘            ├────────┤ Frame 4
                      │ Page 1 │ ← Page 1은 Frame 4에
                      ├────────┤ ...
                      │ Page 3 │ ← Page 3은 Frame 7에
                      └────────┘

기본 동작

프로세스가 실행될 때, 페이지들이 backing store(디스크)에서 사용 가능한 아무 프레임에나 로드된다.
주소 변환: CPU의 가상 주소가 페이지 프레임 번호 + 페이지 내 오프셋으로 변환된다.
하드웨어 지원: MMU가 소프트웨어 도움 없이 자동으로 페이지→프레임 변환을 수행한다.

페이지 테이블 예시

논리 메모리       페이지 테이블      물리 메모리
┌────────┐       ┌───┬───┐       ┌────────┐ Frame 0
│ Page 0 │──────►│ 0 │ 1 │──────►│        │
├────────┤       ├───┼───┤       ├────────┤ Frame 1
│ Page 1 │──────►│ 1 │ 4 │──┐    │ Page 0 │ ← PTE[0]=1
├────────┤       ├───┼───┤  │    ├────────┤ Frame 2
│ Page 2 │──────►│ 2 │ 3 │──┼──► │        │
├────────┤       ├───┼───┤  │    ├────────┤ Frame 3
│ Page 3 │──────►│ 3 │ 7 │  │    │ Page 2 │ ← PTE[2]=3
└────────┘       └───┴───┘  │    ├────────┤ Frame 4
                            └──► │ Page 1 │ ← PTE[1]=4
                                 ├────────┤ ...
                                 ├────────┤ Frame 7
                                 │ Page 3 │ ← PTE[3]=7
                                 └────────┘

PTE (Page Table Entry): 페이지 테이블의 각 항목. Page 번호를 인덱스로, 대응되는 Frame 번호를 값으로 저장한다.
각 프로세스는 자신만의 페이지 테이블을 가진다.

주소 변환 아키텍처

주소 구조

CPU가 생성하는 논리 주소는 두 부분으로 나뉜다:

┌─────────────────┬──────────────┐
│  Page Number(p) │ Page Offset(d)│
└─────────────────┴──────────────┘
     m - n 비트         n 비트

필드	역할
Page Number (p)	페이지 테이블의 인덱스. 해당 페이지가 매핑된 프레임 번호를 찾는다.
Page Offset (d)	해당 페이지(= 프레임) 내에서의 바이트 위치

물리 주소 계산

물리 주소 = Frame번호 × Page크기 + Offset

또는 비트 수준에서:

논리 주소:  [ p (페이지 번호) | d (오프셋) ]
                    │                │
        페이지 테이블 조회    그대로 복사
                    │                │
                    ▼                │
물리 주소:  [ f (프레임 번호) | d (오프셋) ]

오프셋(d)은 논리 주소에서 물리 주소로 그대로 복사된다.
페이지 번호(p)만 프레임 번호(f)로 변환된다.

페이지 크기

하드웨어가 결정한다.
보통 2의 거듭제곱: 512 bytes ~ 16 MB (아키텍처에 따라 다름).
가상 주소 공간 크기가 2^m이고, 페이지 크기가 2^n bytes일 때:
- 오프셋 비트 수 = n
- 페이지 번호 비트 수 = m - n

예시: 32-byte 물리 메모리, 4-byte 페이지

가상 주소 공간: 16 (= 2^4) → m = 4
페이지 크기: 4 bytes (= 2^2) → n = 2
오프셋: 2비트, 페이지 번호: 4 - 2 = 2비트

가상 주소 0 계산:

Page number = 0 ÷ 4 = 0
Page offset = 0 % 4 = 0

가상 주소 13 계산:

Page number = 13 ÷ 4 = 3
Page offset = 13 % 4 = 1

예시: 16비트 주소, 4KB 페이지

슬라이드의 상세 예시 (가상 주소 8196 → 물리 주소 24580):

Incoming virtual address: 8196 (= 0x2004)

16비트 주소에서 12비트 오프셋 (페이지 크기 4KB = 2^12):
→ 상위 4비트 = page number, 하위 12비트 = offset

8196 = 0010 0000 0000 0100
       ────  ────────────────
       p=2    d=4 (offset)

페이지 테이블에서 page 2 조회 → frame number = 110 (이진수) = 6

물리 주소 = 110 | 000000000100
           = 1100 0000 0000 0100
           = 24580 (10진수)

즉, 물리 주소 = 6 × 4096 + 4 = 24580

내부 단편화

정의

내부 단편화(Internal Fragmentation)란 프로세스에 할당된 메모리가 실제 필요한 메모리보다 약간 더 큰 경우 발생한다. 프레임 단위로 할당하므로, 마지막 페이지는 프레임을 가득 채우지 못할 수 있다.

예시

페이지(프레임) 크기: 2,048 bytes
프로세스 크기: 72,766 bytes
필요한 페이지: 72,766 ÷ 2,048 = 35페이지 + 1,086 bytes 나머지
할당: 36 프레임 (35개는 꽉 참, 1개는 부분적으로만 사용)
내부 단편화 = 2,048 - 1,086 = 962 bytes (사용되지 않는 공간)

┌──────────┐          ┌──────────┐
│  Page 1  │────────► │  Frame 1 │ (가득 참)
├──────────┤          ├──────────┤
│  Page 2  │────────► │  Frame 2 │ (가득 참)
├──────────┤          ├──────────┤
│   ...    │          │   ...    │
├──────────┤          ├──────────┤
│ Page 35  │────────► │ Frame 35 │ (가득 참)
├──────────┤          ├──────────┤
│ Page 36  │────────► │ Frame 36 │ ← 1,086 bytes만 사용
│(1,086 B) │          │          │   962 bytes 낭비!
└──────────┘          └──────────┘  (내부 단편화)

외부 단편화 vs 내부 단편화 정리

구분	외부 단편화	내부 단편화
발생 원인	가변 크기 할당	고정 크기(프레임) 할당
문제	빈 공간이 흩어져서 연속 할당 불가	프레임 내부에 안 쓰는 공간 발생
해당 방식	연속 메모리 할당	페이징
해결책	압축 / 페이징	페이지 크기를 줄임 (trade-off 있음)

(trade-off)

page size	internal fragmentation	PTE 개수	page table 크기
크게	커짐 (낭비 많음)	적음	작음
작게	줄어듦 (낭비 적음)	많아짐	커짐

메모리 보호 — Protection Bit

동기

운영체제와 다른 프로세스의 코드/데이터에 대한 불법 접근을 방지해야 한다.

방법: 페이지 테이블 엔트리에 Protection Bit 추가

각 PTE에 보호 비트(protection bit)를 둔다:

비트 값	의미	설명
`r-x`	Read + Execute	읽기 및 실행만 가능 (코드 영역)
`r--`	Read Only	읽기만 가능 (상수 데이터)
`rw-`	Read + Write	읽기/쓰기 가능 (일반 데이터, 스택, 힙)

동작

페이지 번호로 PTE를 조회할 때, 프레임 번호와 함께 보호 비트도 확인한다. 예를 들어, read-only 페이지에 쓰기를 시도하면 trap이 발생한다.

대표적 예시

영역	보호 수준
커널 코드/데이터	사용자 프로세스에 대해 읽기 전용
프로세스 텍스트(코드)	자기 자신 및 다른 프로세스에 대해 읽기 전용
프로세스 데이터/스택/힙	해당 프로세스에 읽기/쓰기

Valid-Invalid Bit

동기

프로세스의 가상 주소 공간 중 일부 페이지만 물리 메모리에 매핑되어 있을 수 있다. 매핑되지 않은 페이지에 접근하면 적절한 조치가 필요하다.

왜 모든 페이지가 매핑되지 않는가?

가상 메모리 > 물리 메모리: 물리 메모리가 부족하여 모든 페이지를 동시에 올릴 수 없다.
프레임 교체: 메모리 부족으로 특정 프레임이 교체(evict)되면, 해당 페이지와 프레임의 매핑이 무효화된다.

메커니즘

각 PTE에 valid-invalid bit을 추가한다:

비트 값	의미
v (valid)	해당 페이지가 물리 프레임에 매핑되어 있음
i (invalid)	해당 페이지가 어떤 프레임에도 매핑되지 않음

예시

가상 주소 공간              페이지 테이블              물리 메모리
(00000 시작)
                   ┌───┬───────┬────────┐
┌──────────┐       │ 0 │   2   │   v    │    Frame 2: page 0
│  page 0  │       ├───┼───────┼────────┤
├──────────┤       │ 1 │   3   │   v    │    Frame 3: page 1
│  page 1  │       ├───┼───────┼────────┤
├──────────┤       │ 2 │   4   │   v    │    Frame 4: page 2
│  page 2  │       ├───┼───────┼────────┤
├──────────┤       │ 3 │   7   │   v    │    Frame 7: page 3
│  page 3  │       ├───┼───────┼────────┤
├──────────┤       │ 4 │   8   │   v    │    Frame 8: page 4
│  page 4  │       ├───┼───────┼────────┤
├──────────┤       │ 5 │   9   │   v    │    Frame 9: page 5
│  page 5  │       ├───┼───────┼────────┤
└──────────┘       │ 6 │   0   │   i    │  ← invalid! 매핑 없음
                   ├───┼───────┼────────┤
                   │ 7 │   0   │   i    │  ← invalid! 매핑 없음
                   └───┴───────┴────────┘

Page 6, 7에 접근 시: 커널이 불법 접근으로 판단하고 trap을 발생시킨다.
이 trap은 page fault로 이어질 수 있으며, 운영체제가 해당 페이지를 디스크에서 로드할 수 있다 (demand paging).

공유 페이지

동기

시나리오: 40개의 프로세스가 동일한 텍스트 에디터를 사용한다고 하자.

코드 크기: 150 KB
데이터 크기: 50 KB (프로세스마다 고유)
프로세스당 200 KB 할당 시: 40 × 200 KB = 8,000 KB 필요

하지만 텍스트 코드는 읽기 전용(read-only)이고 실행 중 변하지 않는다(pure code, reentrant code). 같은 코드를 40번 복사하는 것은 메모리 낭비이다.

해결: 공유 페이지

코드 페이지: 물리 메모리에 단 하나의 사본만 유지. 모든 프로세스의 페이지 테이블이 같은 프레임을 가리킨다.
데이터 페이지: 프로세스마다 다른 프레임에 매핑된다.

절약 효과

코드: 150 KB × 1 = 150 KB (40개가 공유)
데이터: 50 KB × 40 = 2,000 KB
총: 2,150 KB (8,000 KB에서 크게 절약!)

예시 (3개 프로세스가 에디터 공유)

P1의 페이지 테이블         물리 메모리
┌──────┬──────┐          ┌────────────┐ 
│ ed1  │  3   │──┐       │            │ Frame 0
│ ed2  │  4   │──┼──┐    ├────────────┤ 
│ ed3  │  6   │──┼──┼──┐ │  data 1    │ Frame 1 ← P1 전용 데이터
│data1 │  1   │  │  │  │ ├────────────┤ 
└──────┴──────┘  │  │  │ │  data 3    │ Frame 2 ← P3 전용 데이터
                 │  │  │ ├────────────┤ 
 P2의 페이지 테이블  │  │  │ │  ed 1      │ Frame 3← 코드 공유!
┌──────┬──────┐  │  │  │ ├────────────┤ 
│ ed1  │  3   │──┘  │  │ │  ed 2      │ Frame 4 ← 코드 공유!
│ ed2  │  4   │─────┘  │ ├────────────┤ 
│ ed3  │  6   │────────┘ │            │ Frame 5
│data2 │  7   │          ├────────────┤ 
└──────┴──────┘          │  ed 3      │ Frame 6 ← 코드 공유!
                         ├────────────┤ 
 P3의 페이지 테이블          │  data 2    │ Frame 7 ← P2 전용 데이터
┌──────┬──────┐          └────────────┘
│ ed1  │  3   │──────────► Frame 3 (같은 프레임!)
│ ed2  │  4   │──────────► Frame 4 (같은 프레임!)
│ ed3  │  6   │──────────► Frame 6 (같은 프레임!)
│data3 │  2   │──────────► Frame 2 (P3 전용)
└──────┴──────┘

핵심: 세 프로세스의 ed1, ed2, ed3 페이지가 모두 같은 물리 프레임(3, 4, 6)을 가리킨다. 데이터 페이지만 프로세스별로 다른 프레임에 매핑된다.

공유 페이지의 대표적 활용

컴파일러, 윈도우 시스템, 런타임 라이브러리, 데이터베이스
System V IPC의 공유 메모리(shared memory)

계층적 페이지 테이블

문제: 페이지 테이블이 너무 크다

시나리오: 32비트 논리 주소 공간, 4 KB 페이지, PTE 크기 4 bytes

PTE 수 = 2^32 / 2^12 = 2^20 = 1,048,576개
페이지 테이블 크기 = 2^20 × 4 = 4 MB
각 프로세스마다 연속된 4 MB 메모리가 페이지 테이블에만 필요하다!

현대 시스템은 32~64비트 주소를 지원하므로, 페이지 테이블 자체가 매우 커진다.

해결: 계층적 페이지 테이블

페이지 테이블 자체도 비연속적으로 물리 메모리에 저장하자! 즉, 페이지 테이블을 또 페이징하는 것이다.

Two-Level Paging (2단계 페이징)

32비트 주소, 4 KB 페이지 기준:

논리 주소 (32비트):
┌────────────┬────────────┬──────────────┐
│   p1 (10)  │   p2 (10)  │   d (12)     │
└────────────┴────────────┴──────────────┘
  1단계 인덱스  2단계 인덱스   페이지 오프셋

필드	비트 수	역할
p1	10	1단계(outer) 페이지 테이블의 인덱스
p2	10	2단계(inner) 페이지 테이블 페이지의 인덱스
d	12	프레임 내 오프셋

주소 변환 과정

논리 주소: [p1 | p2 | d]

Step 1: p1 → outer page table에서 조회
         → 2단계 페이지 테이블의 프레임 번호를 얻음

Step 2: p2 → 해당 2단계 페이지 테이블에서 조회
         → 최종 데이터 프레임 번호를 얻음

Step 3: 프레임 번호 + d(오프셋) → 물리 주소

┌──────────┐
│  p1 = 3  │
│  p2 = 7  │
│  d = 100 │
└──┬───────┘
   │
   ▼  p1=3
┌──────────┐       outer page table
│   ...    │       (1단계, 2^10 = 1024개 엔트리)
│ entry[3] │──────►┌──────────┐
│   ...    │       │   ...    │  page of page table
└──────────┘       │ entry[7] │──────►┌──────────┐
                   │   ...    │       │  Frame F │
                   └──────────┘       └──┬───────┘
                   (2단계 테이블 중 하나)     │
                                         │ + offset d=100
                                         ▼
                                    물리 주소 = F × 4096 + 100

왜 계층화하면 좋은가?

1단계 페이지 테이블: 2^10 × 4 bytes = 4 KB (딱 한 프레임)
2단계 페이지 테이블: 각각 4 KB이지만, 실제로 사용하는 것만 메모리에 올리면 된다.
프로세스가 전체 가상 주소 공간의 일부만 사용하면, 대부분의 2단계 테이블은 필요 없으므로 메모리 절약!

세그멘테이션

Motivations : 프로그래머의 관점

프로그래머는 메모리를 하나의 선형 주소 공간으로 보지 않는다. 대신 다음과 같은 논리적 단위(세그먼트)로 인식한다:

Main program (메인 프로그램)
Library function (라이브러리 함수)
Thread stack (스레드 스택)
Heap (힙)
Symbol table (심볼 테이블)

각 세그먼트가 얼마나 커질지, 어디에 배치될지 프로그래머는 모르며, 가상 메모리에서 어디로 가는지 관리하고 싶지도 않다.

세그먼트란?

프로그래머가 인식하는 논리적 단위
종류: 텍스트 코드, 전역 변수, 힙, 스택, 공유 라이브러리 등
가상 주소를 가변 크기 세그먼트로 나눈다 (페이징은 고정 크기)

주소 체계

세그멘테이션에서 가상 주소는 2차원이다:

< segment number, offset >

예시 코드에서:

display 함수: <seg 0, offset 500>
malloc 함수 (C 라이브러리): <seg 2, offset 0>

세그먼트 테이블

필드	역할
base	해당 세그먼트가 물리 메모리에서 시작하는 주소
limit	해당 세그먼트의 길이

주소 변환 하드웨어

CPU가 생성한 가상 주소: <s, d>
        │           │
        │           ▼
        │       d < limit?
        │       ├── NO → trap (주소 오류)
        │       └── YES
        │                │
        ▼                ▼
  세그먼트 테이블[s]의     물리 주소 = base + d
  base/limit 조회

예시

세그먼트 테이블:
┌─────┬───────┬───────┐
│ seg │ limit │ base  │
├─────┼───────┼───────┤
│  0  │ 1000  │ 1400  │
│  1  │  400  │ 6300  │
│  2  │  400  │ 4300  │
│  3  │ 1100  │ 3200  │
│  4  │ 1000  │ 4700  │
└─────┴───────┴───────┘

주소 변환 예시:
• <segment 2, byte 53>:
  - 53 < 400 (limit)? YES
  - 물리 주소 = 4300 + 53 = 4353

• <segment 3, byte 852>:
  - 852 < 1100 (limit)? YES
  - 물리 주소 = 3200 + 852 = 4052

세그멘테이션 vs 페이징

특성	세그멘테이션	페이징
분할 크기	가변 (세그먼트마다 다름)	고정 (모든 페이지 동일)
프로그래머 인식	있음 (논리적 단위)	없음 (투명)
주소 형식	<세그먼트 번호, 오프셋>	<페이지 번호, 오프셋>
외부 단편화	있음	없음
내부 단편화	없음	있음 (마지막 페이지)

Case Study: Intel Pentium

개요

Intel Pentium 아키텍처는 순수 세그멘테이션과 세그멘테이션 + 페이징을 모두 지원한다.

CPU ──► Segmentation Unit ──► Paging Unit ──► Physical Memory
        (가상 주소)     (선형 주소)    (물리 주소)
         MMU

세그멘테이션 특성

항목	값
세그먼트 최대 크기	4 GB
프로세스당 최대 세그먼트 수	2^14 (16,384개)
Private segment	최대 2^13개 (프로세스 전용)
Shared segment	최대 2^13개 (프로세스 간 공유)

Descriptor Table

테이블	역할
LDT (Local Descriptor Table)	프라이빗 세그먼트의 매핑 정보
GDT (Global Descriptor Table)	공유 세그먼트의 매핑 정보

가상 주소 구조

┌─────────────┬───┬─────┬──────────────────┐
│  s (13비트)  │ g │  p  │   offset         │
└─────────────┴───┴─────┘──────────────────┘
  세그먼트 번호  GDT  보호       세그먼트 내 오프셋
               /LDT
  ◄──── selector ────►

- s: 세그먼트 번호 (13비트)
- g: GDT(1) 또는 LDT(0) 선택
- p: 보호 수준 (2비트)

앞에서 Proccess당 Segment수가 $2^{14}$ 라 했는데 gdt ldt를 구분하는 것이 각각 1, 0 이기 때문에 $2^{13}$ + $2^{13}$ 임으로 맞다.
강의 교안에는 없지만
이걸 Intel에서는 RPL (Requested Privilege Level)이라고 불러. CPU가 세그먼트에 접근할 때 이 값을 확인해서, 현재 실행 중인 코드의 권한 수준보다 높은 권한이 필요한 세그먼트에 접근하려 하면 protection fault를 발생시켜.
실제로 Linux에서는 Ring 1, 2를 안 쓰고 Ring 0(커널)과 Ring 3(유저)만 사용해. 이것도 이식성 때문인데, ARM 같은 아키텍처는 2단계(커널/유저)만 지원한다.

페이징 특성

페이지 크기: 4 KB 또는 4 MB 선택 가능
4 KB 페이지: 2단계 페이징 사용

32비트 선형 주소:
┌────────────┬────────────┬──────────────┐
│  p1 (10)   │  p2 (10)   │   d (12)     │
└────────────┴────────────┴──────────────┘

CR3 레지스터 → Page Directory (1단계)
                      │
                      ▼ p1으로 인덱싱
                Page Table (2단계)
                      │
                      ▼ p2로 인덱싱
                   Frame + d(오프셋) → 물리 주소

CR3 레지스터: 현재 프로세스의 Page Directory를 가리킨다.
컨텍스트 스위칭 시 CR3 값이 교체된다.

Appendix: Linux에서의 세그멘테이션과 페이징

Linux에서 세그멘테이션의 무력화

Linux는 Intel의 세그멘테이션 하드웨어를 사실상 사용하지 않는다.

방법: 모든 세그먼트의 base = 0x0000으로 설정

Intel 원칙:
CPU → [세그먼트 테이블: base 더함 (유효)] → [페이지 테이블: frame 변환] → 물리 메모리

Linux:
CPU → [세그먼트 테이블: base=0 (무변화)] → [페이지 테이블: frame 변환] → 물리 메모리
                    ↓
            VA → seg 테이블 통과
            → 0x0 + VA = VA
            주소값 변화 없음!

결과: 가상 주소(VA) = 선형 주소. 세그먼트 테이블을 거쳐도 주소가 바뀌지 않는다.

무력화하는 이유: 이식성 (Portability)

세그멘테이션은 Intel x86 전용 기능이다.
Linux와 Windows는 ARM, RISC-V 등 다양한 CPU에서도 동작해야 한다.
세그멘테이션을 활용하면 다른 CPU로 포팅이 불가능하다.
따라서 메모리 보호와 주소 변환 모두 페이지 테이블이 전담한다.

Intel vs Linux 가상 주소 공간 비교

[Intel 원칙]                          [Linux]
세그먼트마다 0x0000 시작               단일 가상 주소 공간
CPU 주소 = <seg#, offset>            CPU 주소 = 단일 숫자

┌───────────────┐ 0x0000              ┌───────────────┐ 0x1000
│ seg 0 Text    │                     │  Text         │ 0x1000~0x1FFF
│ 0x0000-0x0FFF │                     ├───────────────┤ 0x2000
├───────────────┤ 0x0000              │  Data         │ 0x2000~0x2FFF
│ seg 1 Data    │                     ├───────────────┤ (미사용)
│ 0x0000-0x0FFF │                     ├───────────────┤ 0x4000
├───────────────┤ 0x0000              │  Heap         │ 0x4000~0x5FFF
│ seg 2 Heap    │                     ├───────────────┤ (미사용)
│ 0x0000-0x1FFF │                     ├───────────────┤ 0x7000
├───────────────┤ 0x0000              │  Stack        │ 0x7000~0x7FFF
│ seg 3 Stack   │                     └───────────────┘
│ 0x0000-0x0FFF │
└───────────────┘

Intel: seg=0의 0x0200 ≠ seg=2의 0x0200    Linux: 0x4200 → Heap만 해당
       (오프셋 같아도 다른 위치)                    (단일 숫자로 구분 가능)
       → seg# 필수!                              → seg# 불필요!

Linux의 세그먼트 테이블

seg #	이름	base	limit	결과
0 Text	hello, main	0x0000	0xFFFF...	VA = 선형 (변화 없음)
1 Data	global	0x0000	0xFFFF...	VA = 선형 (변화 없음)
2 Heap	*heap	0x0000	0xFFFF...	VA = 선형 (변화 없음)
3 Stack	local	0x0000	0xFFFF...	VA = 선형 (변화 없음)

모든 base가 0x0000이므로, 선형주소 = 0x0 + VA = VA 그대로.

Linux에서의 페이징 — 전체 흐름 예시

예제 코드의 변수들:

hello() 함수: VA = 0x1000
global = 42: VA = 0x2000
*heap = 99 (malloc): VA = 0x4200
local = 1: VA = 0x7800
페이지 크기: 0x1000 (4 KB)

물리 주소 계산 공식

page# = 선형주소 ÷ 페이지크기
offset = 선형주소 % 페이지크기
물리주소 = frame# × 페이지크기 + offset

변환 과정 상세

1) hello() — VA 0x1000
   세그먼트: seg 0, base=0x0 → 선형주소 = 0x1000
   페이징:  page#=1, offset=0x000 → page 1 → frame 3
   물리주소: 0x3000

2) global=42 — VA 0x2000
   세그먼트: seg 1, base=0x0 → 선형주소 = 0x2000
   페이징:  page#=2, offset=0x000 → page 2 → frame 5
   물리주소: 0x5000

3) *heap=99 — VA 0x4200 ★
   세그먼트: seg 2, base=0x0 → 선형주소 = 0x4200
   페이징:  page#=4, offset=0x200 → page 4 → frame 7
   물리주소: 0x7200

4) local=1 — VA 0x7800
   세그먼트: seg 3, base=0x0 → 선형주소 = 0x7800
   페이징:  page#=7, offset=0x800 → page 7 → frame 1
   물리주소: 0x1800

Protection Bit과 Valid Bit 예시

Appendix의 예제 코드 기반 페이지 테이블:

Page #	내용	Frame #	Protection	Valid
Page 0	Code (main 기계어)	Frame 3	r-x (읽기+실행)	✓ valid
Page 1	Read-only data (read_only=42)	Frame 6	r-- (읽기 전용)	✓ valid
Page 2	Stack (data, valid, invalid)	Frame 1	rw- (읽기/쓰기)	✓ valid
Page 3	Heap (malloc → *valid=777 → free)	Frame 7	rw-	✓→✗ (free 후 invalid)
Page 4	NULL (invalid = NULL)	—	—	✗ invalid (매핑 없음 → page fault!)

메모리 접근 순서:
1. valid bit 확인 → invalid이면 page fault
2. protection bit 확인 → 위반 시 segfault
3. 물리 프레임 접근

판단방법

CPU가 주소 변환 중 invalid bit 발견 → trap 발생 (하드웨어 레벨)
커널의 exception handler로 진입
Page fault handler가 "이 주소가 유효한 범위인가?" 판단

유효한 주소인데 메모리에 없을 뿐 → page fault 처리 (디스크에서 로딩 후 재시작)
유효하지 않은 주소 → segmentation fault (SIGSEGV 시그널 → 프로세스 종료)

Pagefault가 trap(발생방식)이고 segmentation fault는 결과!

공유 페이지 예시 (fork)

3개 프로세스가 editor() 함수를 공유하는 경우:

가상 주소 공간          페이지 테이블 엔트리       물리 메모리

[Process P0]
 editor() 0x55e...  → page 0 → frame 0 (공유) ──► Frame 0: editor() 코드
 my_data=0         → page 1 → frame 1       ──► Frame 1: my_data(P0)=0

[Process P1]
 editor() 0x55e...  → page 0 → frame 0 (공유) ──► Frame 0: (같은 프레임!)
 my_data=1         → page 1 → frame 2       ──► Frame 2: my_data(P1)=1

[Process P2]
 editor() 0x55e...  → page 0 → frame 0 (공유) ──► Frame 0: (같은 프레임!)
 my_data=2         → page 1 → frame 3       ──► Frame 3: my_data(P2)=2

핵심 관찰:

editor() 함수의 가상 주소는 세 프로세스 모두 동일 (0x55e7e9b8b1a9) → 같은 코드 페이지 공유
my_data의 가상 주소도 세 프로세스 모두 동일 (0x7ffebf567de0) → 하지만 페이지 테이블이 다른 물리 프레임으로 매핑
가상 주소가 같아 보여도, 프로세스마다 독립된 페이지 테이블이 있으므로 물리 프레임은 다르다
따라서 my_data 값은 프로세스별로 독립적 (0, 1, 2)

핵심 개념 요약표

개념	핵심 요약
Base/Limit Register	연속 할당에서 프로세스 메모리 보호를 위한 하드웨어 레지스터
논리(가상) 주소	CPU가 생성하는 주소. 프로그램이 보는 주소
물리 주소	실제 DRAM의 주소. 메모리 버스에 나가는 주소
MMU	가상→물리 주소 변환을 수행하는 하드웨어
Relocation Register	가장 간단한 MMU. 모든 주소에 base값을 더함
연속 메모리 할당	프로세스를 하나의 연속 영역에 배치. 외부 단편화 발생
외부 단편화	전체 빈 공간은 충분하지만 연속 공간이 부족한 문제
내부 단편화	고정 크기 프레임 할당 시 마지막 프레임의 낭비
페이징	고정 크기 page/frame으로 비연속 할당. 외부 단편화 해결
페이지 테이블	page→frame 매핑 정보 저장. 프로세스마다 하나
Protection Bit	PTE에 r/w/x 권한 정보 저장
Valid-Invalid Bit	PTE에 해당 페이지의 물리 매핑 유무 표시
공유 페이지	읽기 전용 코드를 여러 프로세스가 같은 프레임으로 공유
계층적 페이지 테이블	페이지 테이블 자체를 페이징하여 메모리 절약
세그멘테이션	가변 크기 논리 단위로 분할. <seg#, offset> 주소
Linux 세그멘테이션	base=0으로 무력화, 실질적으로 paging만 사용
Intel Pentium	Segmentation + Paging 모두 지원. 2단계 변환

Kamator0

이전 포스트

JaneStreet 26년 5월 Puzzle [Arch Madness]

다음 포스트