Virtual Memory Management

Kamator0·2026년 5월 30일

TLB (Translation Look-aside Buffer)

구조

개념

TLB는 최근에 접근한 page → frame 매핑을 캐싱하는 mmu에 위치한 하드웨어(SRAM)이다.

왜 필요한가?

Page table은 DRAM에 존재한다. 따라서 메모리 접근 한 번을 하려면:

Page table 조회 (메모리 접근 1번)
실제 데이터 접근 (메모리 접근 1번)

→ 총 2번의 메모리 접근이 필요하다. 이 오버헤드를 줄이기 위해 자주 쓰는 매핑을 TLB에 저장한다.

동작 흐름

CPU가 논리 주소 <p, d> (page number, offset) 생성
TLB hit → 바로 frame 번호를 얻어 물리 주소 <f, d> 생성
TLB miss → DRAM의 page table을 조회하여 frame 번호 획득 → TLB에 캐싱

Demand Paging (요구 페이징)

동기 (Motivation)

프로그램 전체를 메모리에 올릴 필요가 없다. 실제로는 프로그램의 일부만 실행되고, 나머지는 거의 쓰이지 않는다.

에러 처리 코드 (exception code)
100×100 배열 중 10×10만 사용
거의 사용되지 않는 기능들

핵심 개념

프로그램 실행 중 실제로 필요한 페이지만 메모리에 올린다. 한 번도 접근하지 않는 페이지는 영원히 물리 메모리에 올라오지 않는다.

이점 (Benefits)

프로그램이 물리 메모리 크기에 제약받지 않음
더 많은 프로그램을 동시에 실행 가능 (degree of multiprogramming 향상)
각 프로그램의 로딩/스왑에 필요한 I/O 감소 → 실행 속도 향상

페이지 로딩 절차

Backing store(디스크)에 있는 페이지를 물리 메모리의 free frame에 복사
해당 페이지의 Page Table Entry(PTE)에 frame 번호 세팅
Valid-invalid bit을 v(valid)로 설정

예시

Page Fault

정의

프로세스가 메모리에 올라와 있지 않은 페이지에 접근을 시도할 때, 즉 valid-invalid bit가 i(invalid)인 페이지에 접근할 때 발생하는 예외(exception/trap)이다.

처리 절차 (Steps in Handling a Page Fault)

Reference: 프로세스가 페이지에 접근 시도
Trap: MMU가 invalid bit를 감지하여 커널에 exception 발생
Page is on backing store: 커널이 디스크에서 해당 페이지 위치 확인
Bring in missing page: 디스크에서 free frame으로 페이지 로딩
Reset page table: PTE를 갱신 (frame 번호 + valid bit 설정)
Restart instruction: 페이지 폴트를 발생시킨 명령어를 다시 실행

핵심 포인트

Page fault handler 처리 전에 프로세스의 context를 PCB에 저장
Handler 완료 후 정확히 같은 명령어(page fault가 발생한 명령어)부터 재시작

Segmentation Fault vs Page Fault

구분	Page Fault	Segmentation Fault
원인	유효한 주소이나 메모리에 없음	잘못된/허용되지 않은 주소 접근
복구	가능 (페이지 로딩 후 재시작)	불가능 (프로세스 종료)

Performance of Demand Paging (성능 분석)

Effective Memory Access Time (유효 메모리 접근 시간)

Effective Access Time = (1 - p) × ma + p × page_fault_time

ma: Memory access time (보통 10~200 나노초)
p: Page fault rate (0 ≤ p ≤ 1)

Page Fault Service Time의 구성

Page fault interrupt 처리 (≪ 1ms)
디스크에서 페이지 읽기: 약 8ms (seek time + rotational time + transfer time)
프로세스 재시작 (≪ 1ms)

→ 평균 page fault service time ≈ 8ms

계산 예시

Memory access time = 200ns
Page fault rate = 1/1000

EAT = (1 - 1/1000) × 200 + (1/1000) × 8,000,000
    = 199.8 + 8000
    = 8,199.8ns ≈ 8.2μs

→ Page fault가 1000번에 1번만 발생해도 메모리 접근 시간이 약 40배 느려진다!

Page Replacement

동기

Page fault 발생 시 free frame이 없으면 어떻게 할 것인가?

3가지 해결책

방법	설명	단점
Solution 1: Process Termination	페이지 폴트를 일으킨 프로세스 종료	너무 극단적
Solution 2: Process Swapping (Swap-Out)	프로세스 전체를 디스크로 내보냄	오버헤드 큼
Solution 3: Page Replacement	사용 안 하는 frame 하나를 찾아 교체	가장 일반적

Page Replacement 절차 (Steps)

Swap out victim page: Victim 페이지를 디스크(swap space)에 기록
Change to invalid: Victim의 PTE valid bit를 i로 변경
Swap desired page in: 필요한 페이지를 해당 frame에 로딩
Reset page table for new page: 새 페이지의 PTE 갱신

Page-Out vs Swap-Out 차이

구분	단위	목적
Page-Out	페이지 1개	Victim 페이지를 swap space로
Swap-Out	프로세스 전체	프로세스의 모든 페이지를 디스크로

Modify (Dirty) Bit

Page replacement 시 disk I/O를 줄이기 위한 최적화이다.

페이지가 수정(write)되면 하드웨어가 modify bit를 1로 설정
교체 시 modify bit 확인:
- modify bit = 1 → 디스크에 write 필요 (page-out + page-in = disk I/O 2번)
- modify bit = 0 → 디스크에 이미 같은 내용이 있으므로 그냥 덮어씀 (page-in만 = disk I/O 1번)

Page Replacement Algorithms

Reference String

메모리 참조의 순서를 나열한 것. 교체 알고리즘을 평가할 때 사용한다.

예시: 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1

FIFO Page Replacement

방법: 메모리에 가장 오래 머물러 있던 페이지를 교체한다. (들어온 순서대로 쫓아냄)

구현: FIFO queue. Queue의 head에 있는 페이지를 교체.

예시 (3 frames, reference string: 7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1):

→ 15번 page fault

장점: 구현이 매우 간단
단점: 자주 사용되는 페이지도 오래됐다는 이유로 쫓아낼 수 있음

Optimal (OPT) Page Replacement

방법: 앞으로 가장 오래 사용되지 않을 페이지를 교체한다.

문제: 미래의 reference string을 알아야 하므로 실제 구현 불가능

용도: 다른 알고리즘의 성능을 비교하기 위한 이론적 하한선(baseline)

예시 (3 frames, 같은 reference string): → 9번 page fault (최소)

LRU (Least Recently Used) Page Replacement

방법: 가장 오랫동안 사용되지 않은 페이지를 교체한다.

핵심 아이디어: "미래를 볼 수 없으니, 과거를 보고 추정하자" → OPT의 근사(approximation)

예시 (3 frames, 같은 reference string): → 12번 page fault

구현 방법 1: Counter

각 PTE에 counter(논리적 시계 값) 기록
페이지 참조 시 현재 시간을 counter에 저장
교체 시 counter가 가장 작은(가장 오래된) 페이지 선택
단점: 매번 page table 전체를 탐색해야 함 + 매 메모리 접근마다 write 발생

구현 방법 2: Stack

페이지 번호의 stack 유지
참조되면 stack에서 빼서 top에 삽입
가장 최근 = top, 가장 오래된 = bottom
단점: 매 참조마다 stack 재정렬 → 큰 오버헤드

결론: 순수 LRU는 하드웨어 지원 없이는 오버헤드가 너무 커서 실용적이지 않다.

LRU-Approximation Page Replacement

동기

실제 컴퓨터 시스템은 순수 LRU를 지원할 만한 충분한 하드웨어를 제공하지 않는다. 따라서 근사(approximation) 기법이 필요하다.

Reference Bit 기반

하드웨어가 제공하는 reference bit 활용
페이지가 참조되면 하드웨어가 자동으로 bit를 1로 설정
커널이 주기적으로 모든 bit를 0으로 클리어
일정 시간 후 bit를 검사하면 "사용됨/안 됨"을 알 수 있음
한계: 사용 순서는 알 수 없음 (어떤 페이지가 먼저 사용됐는지 모름)

Second-Chance Algorithm (Clock Algorithm)

기본 구조: Circular queue + clock pointer

동작:
1. 포인터가 가리키는 페이지의 reference bit 확인
2. bit = 0 → 이 페이지를 교체 (victim)
3. bit = 1 → bit를 0으로 클리어하고 다음 페이지로 이동 (second chance 부여)
4. 한 바퀴 돌아와도 모두 1이면 → 결국 처음 페이지가 교체됨 (모든 bit가 0으로 클리어된 상태)

핵심: FIFO의 단순함 + reference bit로 최근 사용 여부 반영

Enhanced Second-Chance Algorithm

동기: 수정된(dirty) 페이지를 교체하면 디스크에 write가 필요해서 시간이 더 걸린다. I/O를 줄일 필요가 있다.

방법: Reference bit + Modify bit(dirty bit)를 ordered pair로 사용

(reference, modify)	의미	교체 우선순위
(0, 0)	최근 사용 안 됨 + 수정 안 됨	최우선 교체 (best)
(0, 1)	최근 사용 안 됨 + 수정됨	차선 (교체 시 disk write 필요)
(1, 0)	최근 사용됨 + clean	곧 다시 쓰일 가능성
(1, 1)	최근 사용됨 + 수정됨	최후 순위 (worst)

효과: 단순 Second-Chance보다 disk I/O를 줄일 수 있음

Counting-Based Page Replacement

각 페이지의 참조 횟수를 counter로 관리한다.

알고리즘	방법	근거
LFU (Least Frequently Used)	참조 횟수가 가장 적은 페이지 교체	적게 쓰인 페이지 = 앞으로도 안 쓰일 것
MFU (Most Frequently Used)	참조 횟수가 가장 많은 페이지 교체	적게 쓰인 페이지 = 방금 들어와서 아직 안 쓰인 것

단점: 큰 메모리 필요 + 적절한 count 값을 가진 페이지를 찾는 탐색 오버헤드
만약 counter 4byte를 page table에 추가하면 page table의 frame(page)증가
실제 OS 구현은 방법이 없다

알고리즘 비교 요약

알고리즘	Page Fault (3 frames)	실용성	핵심 특징
FIFO	15	⭐⭐⭐	가장 간단
OPT	9	❌ (구현 불가)	이론적 최적
LRU	12	⭐⭐ (오버헤드 큼)	과거 기반 OPT 근사
Second-Chance	-	⭐⭐⭐	FIFO + reference bit
Enhanced Second-Chance	-	⭐⭐⭐	+ dirty bit로 I/O 최적화

진화 방향

OPT (이론적 최적, 구현 불가)
  ↓ 근사
LRU (정확하지만 오버헤드 큼)
  ↓ 근사
Reference Bit (싸지만 순서 모름)
  ↓ 활용
Second-Chance / Clock (FIFO + reference bit)
  ↓ 개선
Enhanced Second-Chance (+ dirty bit로 I/O 최적화)

Thrashing (쓰래싱)

정의

프로세스가 active하게 사용하는 페이지를 담을 frame이 부족하여, 빈번하고 빠르게 page fault가 반복 발생하는 현상이다.

발생 시나리오

프로세스가 충분한 frame을 갖고 있지 않음
실행 시 빈번한 page fault 발생
다른 프로세스의 페이지를 교체하지만(context switching), 그 페이지도 곧 다시 필요해짐
또 page fault → 또 교체 → 또 fault... (악순환)

Thrashing과 CPU Utilization

Degree of multiprogramming(proccess 갯수)을 올리면 처음에는 CPU utilization 증가
어느 지점을 넘으면 thrashing 발생 → CPU utilization 급락
그래프가 올라갔다 갑자기 뚝 떨어지는 형태

해결책

Solution 1: Local Replacement Algorithm

프로세스가 다른 프로세스의 frame을 빼앗을 수 없게 함
문제: thrashing이 완전히 해결되지는 않음 (자기 자신의 frame 내에서도 부족할 수 있음)

Solution 2: Locality Model 기반 Working-Set

커널이 프로세스에게 현재 locality를 수용할 만큼의 frame을 할당
"프로세스가 몇 개의 frame을 필요로 하는가?"를 locality model로 판단

Locality Model (지역성 모델)

정의

Locality: 함께 활발하게 사용되는 페이지들의 집합

두 가지 유형

유형	설명	예시
Temporal Locality (시간적 지역성)	최근 접근한 데이터가 곧 다시 접근될 가능성	루프에서 같은 변수 반복 참조
Spatial Locality (공간적 지역성)	접근한 위치 근처의 데이터가 곧 접근될 가능성	배열 순차 접근, 함수 호출 시 인접 코드

프로그램 구조와 Locality

예: Func0(page 11)이 malloc(page 12)을 호출하고 Func1(page 10)을 호출하면, page 10, 11, 12가 함께 사용되는 locality를 형성한다.

→ 이 locality의 페이지들을 모두 메모리에 유지하면 page fault를 줄일 수 있다.

Working-Set Model (작업 집합 모델)

정의

Δ (working-set window): 고정된 수의 최근 페이지 참조 수 (예: 10,000 instruction)
Working Set: 최근 Δ번의 참조에서 접근된 페이지들의 집합
Working Set은 프로그램 locality의 근사값

예시

page reference table:
...2 6 1 5 7 7 7 5 1 6 2 3 4 1 2 3 4 4 3 4 3 4 4 1 3 2 3 4 4 3 4 4 4...
                        ↑ t1                              ↑ t2

Δ = 10일 때:
- WS(t1) = {1, 2, 5, 6, 7}
- WS(t2) = {3, 4}

Δ의 크기

Δ가 너무 작으면: 전체 locality를 포함하지 못함
Δ가 너무 크면: 여러 locality가 겹침
Δ = ∞: 프로세스 실행 동안 접근한 모든 페이지

시스템 전체 관점

D = Σ WSSi (전체 프로세스의 working set 크기 합)
D > m (총 가용 frame 수) → Thrashing 발생 가능
- 해결: 프로세스 하나를 suspend하여 swap out
D < m → 여유 있음
- 새 프로세스를 시작할 수 있음

Copy-On-Write (COW, 쓰기 시 복사)

동기

fork() 시 부모 프로세스의 메모리를 자식에게 전부 복사하면 오버헤드가 크다.

핵심 아이디어

fork() 직후, 부모와 자식이 같은 물리 frame을 공유
둘 중 하나가 해당 페이지에 write를 시도하면 그때서야 복사 (Copy-On-Write)

절차

fork() 시 자식 프로세스의 page table이 부모와 같은 frame을 가리킴
두 프로세스 모두 read-only로 설정
자식(또는 부모)이 특정 페이지에 write 시도
COW 발생: 커널이 해당 페이지의 내용을 새 frame에 복사
write를 시도한 프로세스의 page table이 새 frame을 가리키도록 갱신
수정은 새 frame에서 진행 → 다른 프로세스에는 영향 없음

이점

fork() 시 대량 복사 오버헤드 제거
실제로 수정되는 페이지만 복사 → 메모리와 시간 절약
exec()를 바로 호출하는 경우 (fork + exec 패턴) 복사가 거의 일어나지 않음

핵심 용어 정리

용어	영문	설명
요구 페이징	Demand Paging	필요한 페이지만 메모리에 올리는 기법
페이지 폴트	Page Fault	메모리에 없는 페이지에 접근 시 발생하는 예외
페이지 교체	Page Replacement	free frame이 없을 때 victim을 골라 교체
Page-In	Page-In	디스크 → 물리 메모리 (페이지 1개)
Page-Out	Page-Out	물리 메모리 → 디스크 (페이지 1개)
Swap-Out	Swap-Out	프로세스 전체를 디스크로 내보냄
참조 비트	Reference Bit	페이지 참조 시 하드웨어가 설정하는 비트
수정 비트	Modify/Dirty Bit	페이지 수정 시 하드웨어가 설정하는 비트
쓰래싱	Thrashing	빈번한 page fault로 CPU가 거의 일을 못 하는 상태
지역성	Locality	함께 사용되는 페이지들의 집합
작업 집합	Working Set	최근 Δ번 참조에서 접근된 페이지 집합
쓰기 시 복사	Copy-On-Write	fork() 시 실제 write가 발생할 때만 페이지 복사
유효 접근 시간	Effective Access Time	page fault율을 반영한 실제 메모리 접근 시간

Kamator0

이전 포스트

Linking

다음 포스트