KAIST CS330 운영체제 및 실험 (Fall 2023, Prof. Youngjin Kwon) 교재: Operating Systems: Three Easy Pieces (OSTEP), Operating Systems: Principles and Practice (OSPP)

이전 글: [CS330] 5. 페이징과 TLB

1. 메모리 계층 구조와 스와핑

1.1 메모리 계층 구조 (Memory Hierarchy)

현대 컴퓨터 시스템은 성능과 용량의 트레이드오프를 관리하기 위해 계층적인 메모리 구조를 사용한다. 위로 갈수록 빠르고 비싸며, 아래로 갈수록 느리고 용량이 크다: Registers → Cache → Main Memory (RAM) → Disk Storage.

각 계층은 위 계층의 “백킹 스토어(backing store)” 역할을 수행한다. 특히 메인 메모리의 백킹 스토어는 디스크다.

1.2 스와핑이란 무엇인가?

**스와핑(Swapping)**은 물리 메모리가 부족할 때 디스크를 메모리 확장 공간으로 활용하는 메커니즘이다. 가상 주소(Virtual Address)와 물리 주소(Physical Address)의 위치가 독립적이라는 특성을 활용한다.

왜 스와핑이 필요한가?

  1. 물리 메모리의 한계: 프로세스가 필요로 하는 메모리가 물리 메모리보다 클 수 있다
  2. 메모리 독립성: 사용자 프로그램은 실제 물리 메모리 크기와 무관하게 동작해야 한다
  3. 참조의 지역성(Locality of Reference): 프로세스는 한 순간에 작은 양의 메모리만 활발히 사용한다
  4. 효율적 자원 활용: 현재 사용하지 않는 페이지를 디스크로 내보내고, 필요한 페이지만 메모리에 유지한다

1.3 스와핑의 종류

Process-level Swapping (프로세스 단위 스와핑)

  • 초기 시스템에서 사용하던 방식
  • 프로세스 전체를 임시로 디스크로 내보냈다가 나중에 다시 메모리로 가져온다
  • 스왑 단위가 커서 효율성이 떨어진다

Page-level Swapping (페이지 단위 스와핑)

  • 현대 운영체제에서 사용하는 방식
  • 페이지 단위로 swap-out (page-out) 및 swap-in (page-in)을 수행한다
  • 더 세밀한 제어가 가능하다

1.4 스왑 공간 (Swap Space)

스왑 공간은 디스크에 할당된 영역으로, 메모리 페이지를 저장한다. 스왑 공간의 크기가 사용 가능한 최대 메모리 페이지 수를 결정하며, 블록 크기는 페이지 크기와 동일하다 (일반적으로 4KB). 전용 파티션 또는 파일 시스템 내 파일로 구현된다.

2. 페이지 폴트와 페이지 교체

2.1 Present Bit

페이지 테이블 엔트리(PTE)에는 present bit가 있어서 페이지가 현재 물리 메모리에 있는지 디스크에 있는지를 나타낸다.

Present Bit 값의미
1페이지가 물리 메모리에 존재함
0페이지가 메모리에 없고 디스크에 있음

2.2 페이지 폴트 (Page Fault)

페이지 폴트는 프로세스가 현재 물리 메모리에 없는 페이지에 접근할 때 발생하는 이벤트다.

페이지 폴트가 발생하면:

  1. 하드웨어가 PTE를 검사하고 present bit가 0임을 발견한다
  2. 페이지 폴트 예외(exception)가 발생하여 운영체제로 제어가 넘어간다
  3. 운영체제는 페이지를 디스크에서 메모리로 가져와야 한다 (swap-in)
  4. 필요하다면 다른 페이지를 디스크로 내보낸다 (swap-out)

2.3 페이지 폴트 처리 과정

  1. Load 명령 실행 → 2. Page Fault 발생 (Trap to OS) → 3. OS가 페이지가 디스크에 있는지 확인 → 4. 디스크에서 페이지 읽기 → 5. Page Table 업데이트 → 6. 명령 재실행 (Reinstruction)

2.4 페이지 교체 (Page Replacement)

물리 메모리가 가득 찬 상태에서 새로운 페이지를 가져와야 할 때, 운영체제는 기존 페이지 중 하나를 선택하여 내보내야 한다. 이 과정을 **페이지 교체(page replacement)**라고 하며, 어떤 페이지를 내보낼지 결정하는 정책을 **페이지 교체 정책(page replacement policy)**이라고 한다.

2.5 페이지 축출 (Page Eviction)

페이지를 메모리에서 제거하는 방법은 페이지 타입에 따라 다르다:

페이지 타입상태축출 방법
Code Page-읽기 전용이므로 그냥 제거 (실행 파일에서 재로드 가능)
Data PageModified (dirty)스왑 공간에 기록
Unmodified (clean)스왑 공간에서 버림 (discard)
Anonymous PageClean, 스왑 이력 있음메모리에서 제거만 (디스크에 이미 존재)
Clean, 스왑 이력 없음새 스왑 공간 할당 후 기록 (Zero page는 예외)
Dirty, 스왑 이력 있음스왑 공간에 덮어쓰기
Dirty, 스왑 이력 없음새 스왑 공간 할당 후 기록

2.6 스와핑 시점 (When to Perform Swap)

운영체제는 항상 일정량의 여유 메모리를 유지하려고 한다 (Proactive Approach). 두 개의 임계값 **HW (High Watermark)**와 **LW (Low Watermark)**를 사용하며, Swap Daemon (Linux에서는 kswapd)이 백그라운드에서 메모리를 관리한다. Free Pages < LW이면 페이지 축출 시작, Free Pages > HW이면 잠든다.

3. 페이지 교체 알고리즘

3.1 목표: 페이지 폴트율 최소화

페이지 교체 정책의 목표는 **페이지 폴트율(page fault rate)**을 최소화하는 것이다. 디스크 접근 비용은 메모리 접근 비용보다 훨씬 크므로(100,000배 이상), 작은 미스율 차이도 전체 성능에 큰 영향을 미친다.

평균 메모리 접근 시간 (AMAT): AMAT = (P_Hit × T_M) + (P_Miss × T_D)

3.2 OPT (Optimal) - 최적 알고리즘

**Belady의 최적 교체 정책 (1966)**은 “미래에 가장 오랫동안 사용되지 않을 페이지"를 교체한다.

특징:

  • 어떤 페이지 참조 스트림(page reference string)에 대해서도 가장 낮은 폴트율을 보인다
  • 다른 알고리즘의 성능 비교 기준(benchmark)으로 사용된다
  • 실용적이지 않다: 미래를 예측해야 하므로 실제로는 구현 불가능하다

시뮬레이션 예시 (캐시 크기 = 3):

Reference String: 0 1 2 0 1 3 0 3 1 2 1

AccessHit/MissEvictCache State
0Miss-0
1Miss-0, 1
2Miss-0, 1, 2
0Hit-0, 1, 2
1Hit-0, 1, 2
3Miss20, 1, 3
0Hit-0, 1, 3
3Hit-0, 1, 3
1Hit-0, 1, 3
2Miss30, 1, 2
1Hit-0, 1, 2

Hit Rate = 6 / 11 = 54.6%

OPT는 페이지 2를 축출할 때 “가장 나중에 다시 참조될” 페이지를 선택한다.

3.3 FIFO (First-In First-Out)

FIFO는 가장 오래 전에 메모리에 로드된 페이지를 교체한다.

특징:

  • 구현이 매우 간단하다 (큐 자료구조 사용)
  • 가장 오래된 페이지가 사용되지 않을 것이라는 가정
  • 문제점: 오래된 페이지가 계속 사용될 수도 있다 (temporal locality 무시)

시뮬레이션 예시 (캐시 크기 = 3):

Reference String: 0 1 2 0 1 3 0 3 1 2 1

AccessHit/MissEvictCache State
0Miss-0
1Miss-0, 1
2Miss-0, 1, 2
0Hit-0, 1, 2
1Hit-0, 1, 2
3Miss01, 2, 3
0Miss12, 3, 0
3Hit-2, 3, 0
1Miss23, 0, 1
2Miss30, 1, 2
1Hit-0, 1, 2

Hit Rate = 4 / 11 = 36.4%

Belady’s Anomaly (벨레이디의 역설)

FIFO는 특이한 현상을 보인다: 메모리를 늘렸는데 오히려 페이지 폴트가 증가할 수 있다.

예시: Reference string 1 2 3 4 1 2 5 1 2 3 4 5를 실행하면, 3프레임일 때 9 miss, 4프레임일 때 10 miss가 발생한다. 이는 FIFO가 페이지의 실제 사용 패턴을 고려하지 않기 때문이다.

3.4 Random

Random은 무작위로 페이지를 선택하여 교체한다. 구현은 간단하지만 성능은 운에 따라 달라진다.

3.5 LRU (Least Recently Used)

LRU는 “가장 오래 전에 사용된 페이지"를 교체한다. Recency (최근성) 원리를 이용하여 과거의 사용 패턴으로 미래를 근사한다.

시뮬레이션 예시 (캐시 크기 = 3):

Reference String: 0 1 2 0 1 3 0 3 1 2 1

AccessHit/MissEvictCache State
0Miss-0
1Miss-0, 1
2Miss-0, 1, 2
0Hit-1, 2, 0
1Hit-2, 0, 1
3Miss20, 1, 3
0Hit-1, 3, 0
3Hit-1, 0, 3
1Hit-0, 3, 1
2Miss03, 1, 2
1Hit-3, 2, 1

Hit Rate = 7 / 11 = 63.6%

LRU는 OPT에 가까운 성능을 보이며, FIFO보다 훨씬 좋다.

LRU의 문제점: 구현 비용

완벽한 LRU는 모든 페이지 접근마다 접근 시간을 기록해야 하므로 오버헤드가 크다. 따라서 실제로는 LRU를 근사하는 알고리즘을 사용한다.

3.6 Clock Algorithm - LRU의 근사

Clock Algorithm은 LRU를 근사하는 실용적인 알고리즘이다.

하드웨어 지원: Use Bit (Reference Bit)

  • 페이지가 참조될 때마다 하드웨어가 use bit를 1로 설정한다
  • 하드웨어는 이 비트를 지우지 않는다 (OS의 책임)

동작 방식:

  1. 모든 페이지를 원형 리스트로 구성한다
  2. 시계 바늘(clock hand)이 특정 페이지를 가리킨다
  3. 페이지 교체가 필요할 때:
    • Use bit가 1이면: 0으로 바꾸고 다음 페이지로 이동
    • Use bit가 0이면: 해당 페이지를 축출

동작 예시: 초기 상태가 A(1) - B(1) - C(0) - D(1) - E(1)이고 시계 바늘이 B를 가리킬 때, B의 use bit = 1이므로 0으로 바꾸고 다음으로 이동. C의 use bit = 0이므로 C를 축출한다.

특징: LRU를 근사하며, 구현이 간단하고 성능은 LRU와 비슷하다. 실제 운영체제에서 널리 사용된다.

3.7 워크로드별 성능 비교

No-Locality Workload (지역성 없음)

페이지 참조가 완전히 무작위인 경우, 캐시가 충분히 크면 모든 알고리즘(OPT, LRU, FIFO, RAND)의 성능이 동일하다. 지역성이 없으므로 어떤 페이지를 교체해도 차이가 없다.

80-20 Workload (지역성 있음)

참조의 80%가 전체 페이지의 20%에 집중되는 경우, LRU가 “핫 페이지(hot pages)“를 캐시에 유지하여 우수한 성능을 보인다. OPT가 가장 좋고, LRU가 그 다음이며, FIFO와 RAND는 상대적으로 낮은 hit rate를 보인다.

Looping Sequential Workload (순차 반복)

50개 페이지를 순차적으로 반복 접근하는 경우 (0→1→…→49→0→1→…), LRU가 최악의 성능을 보인다. 캐시 크기가 50보다 작으면 LRU는 0% hit rate를 기록한다. LRU는 가장 최근에 사용된 페이지를 유지하지만, 다음에 필요한 페이지는 가장 오래 전에 사용된 페이지이기 때문이다. OPT와 FIFO는 상대적으로 좋은 성능을 보인다.

4. Working Set과 Thrashing

4.1 Working Set (작업 집합)

Working Set은 프로세스가 현재 활발히 사용하고 있는 페이지들의 집합이다. 시간과 프로그램 실행 단계에 따라 변하며, 참조의 지역성을 반영한다.

4.2 Thrashing (스래싱)

Thrashing은 물리 메모리가 부족하여 시스템이 대부분의 시간을 페이지 스와핑에 소모하는 현상이다. 실행 중인 프로세스들의 working set 합이 물리 메모리보다 클 때 발생하며, CPU 활용률이 급격히 떨어지고 시스템 반응성이 극도로 나빠진다.

해결 방법: 실행 중인 프로세스 수를 줄이거나 메모리를 추가한다.

5. 메모리 매핑 (Memory Mapping)

5.1 mmap이란?

**mmap()**은 파일이나 장치를 프로세스의 가상 주소 공간에 매핑하는 시스템 콜이다. 파일을 메모리처럼 접근할 수 있고, 여러 프로세스가 공유할 수 있으며, lazy loading으로 효율적이다.

5.2 메모리 매핑의 분류

메모리 매핑은 두 가지 축으로 분류된다:

매핑 타입: File-backed Mapping (실제 파일과 연결) vs Anonymous Mapping (파일 없이 메모리만 할당) 공유 방식: Shared Mapping (변경사항이 다른 프로세스나 파일에 반영) vs Private Mapping (변경사항이 해당 프로세스에만 보임, CoW 사용)

File-backedAnonymous
Shared프로세스 간 파일 공유, 데이터 교환IPC용 공유 메모리 (System V shm, POSIX shm)
Private실행 파일 로딩 (.text), 공유 라이브러리 (.so, .dll)malloc() 힙, 스택, 익명 메모리 할당

5.3 Copy-on-Write (CoW)

Private Mapping의 핵심 메커니즘:

  • 처음에는 모든 프로세스가 동일한 물리 페이지를 공유한다
  • 어떤 프로세스가 페이지를 수정하려고 하면, 운영체제가 해당 페이지를 복사한다
  • 이후 변경사항은 복사본에만 반영된다

fork()와 CoW: fork() 시스템 콜은 부모의 모든 페이지를 즉시 복사하지 않고, 부모와 자식이 동일한 물리 페이지를 공유한다 (read-only). 어느 한쪽이 페이지를 수정하면 page fault가 발생하고, 운영체제가 해당 페이지만 복사하여 독립적인 페이지를 할당한다. 이는 fork() 성능을 크게 향상시키며, 특히 fork() 직후 exec()을 호출하는 경우 복사가 거의 발생하지 않는다

6. 정리

스와핑 핵심 개념

  1. 스와핑은 디스크를 메모리 확장으로 활용하여 물리 메모리보다 큰 가상 메모리 공간을 지원한다
  2. Swap space는 페이지를 저장하는 디스크 영역이다
  3. Present bit는 페이지가 메모리에 있는지 디스크에 있는지를 나타낸다
  4. Page fault는 메모리에 없는 페이지 접근 시 발생하며, 운영체제가 디스크에서 페이지를 가져온다

페이지 교체 알고리즘 비교

알고리즘장점단점실용성
OPT최적 성능 (이론적 기준)미래 예측 불가능✗
FIFO구현 간단지역성 무시, Belady’s Anomaly△
Random구현 간단성능 예측 불가△
LRU우수한 성능, 지역성 활용구현 비용 높음✗
ClockLRU 근사, 구현 간단LRU보다 약간 떨어짐✓

Working Set과 Thrashing

  • Working set: 프로세스가 활발히 사용하는 페이지 집합
  • Thrashing: 메모리 부족으로 과도한 스와핑이 발생하는 현상
  • 해결: 프로세스 수 감소, 메모리 추가

메모리 매핑

매핑 타입SharedPrivate
File-backed프로세스 간 파일 공유실행 파일 로딩, 공유 라이브러리
AnonymousIPC용 공유 메모리malloc 힙, 스택

Copy-on-Write는 fork()와 Private Mapping의 효율성을 크게 향상시킨다.

다음 글: [CS330] 7. 동기화 - Lock과 Condition Variable