Process API

프로세스 생성·종료 API

fork(): 부모 프로세스에는 자식 PID(>0), 자식 프로세스에는 0을 반환하며, 실패 시 –1 반환 및 errno 설정

exec*() 계열: execvp(), execl(), execle() 등으로 현재 프로세스를 완전히 새로운 프로그램 이미지로 덮어씀. 열려 있는 파일 디스크립터와 PID는 그대로 유지됨

wait() / waitpid(): 부모가 자식 프로세스의 종료를 대기하며, 반환값으로 종료된 자식의 PID를 받고, WIFEXITED, WEXITSTATUS 매크로로 종료 코드를 해석

시그널(signal) API

kill(pid, sig): 특정 프로세스나 프로세스 그룹에 시그널 전송 (예: SIGINT, SIGTSTP). 일반 사용자는 동일 UID 프로세스에만, root는 모든 프로세스에 시그널 송신 가능

signal(sig, handler): 사용자 정의 시그널 핸들러 등록. 비동기 이벤트(타이머, I/O 완료 등)를 프로세스에 전달

권한과 격리

UID 기반 권한 검사로, 사용자는 자신의 프로세스만 제어

슈퍼유저(root)만이 시스템 전체의 프로세스 관리 및 시그널 송신 권한을 가짐

유용한 시스템 모니터링 도구

ps / top: 프로세스 상태·자원 사용량 실시간 모니터링

killall: 프로세스 이름 기준 일괄 시그널 전송

macOS 등에서 MenuMeters 같은 GUI 유틸리티 활용 가능

요약

PID (Process ID): 각 프로세스를 식별하는 고유 번호

프로세스 생성 API: fork(), exec(), wait()

• fork(): 부모 프로세스의 거의 완전한 복사본인 자식 프로세스를 생성
• exec(): 현재 프로세스 이미지를 새로운 프로그램으로 덮어쓰기
• wait(): 부모가 자식의 종료를 대기

프로세스 제어: 시그널(kill(), signal())을 이용해 중단, 일시 중단, 종료 가능

• 시그널: 프로세스 제어(중단·재개·종료 등)를 위해 OS가 보내는 소프트웨어 인터럽트

사용자 격리: 일반 사용자는 자신의 프로세스만 제어하고, root는 모든 프로세스를 관리

• superuser(root): 모든 프로세스와 시스템 자원에 대한 무제한 권한 사용자

Direct Execution

개요

운영체제에서 CPU 가상화를 구현할 때 충돌하는 두 가지 목표는

• 성능: 가능한 한 네이티브 속도로 프로그램을 실행
• 제어: 언제든 OS가 CPU 제어권을 회수할 수 있어야 함

이 둘을 모두 만족시키는 방식이 바로 제한적 직접 실행(Limited Direct Execution)입니다.

제한적 직접 실행 메커니즘

1. 트랩 테이블 초기화 (부팅 시)
2. return‑from‑trap으로 사용자 모드 진입 -> main() 실행
3. 직접 실행: 대부분의 명령은 하드웨어에서 바로 실행
4. 트랩/시스템 콜/인터럽트 발생 시: 하드웨어가 CPU 모드를 커널로 전환하고, 커널 핸들러로 분기 -> 작업 후 다시 사용자 모드 복귀
5. 타이머 인터럽트를 통해 비협력적 스케줄링(시간분할) 유도

문제 #1: 제한된 연산

사용자 모드 vs 커널 모드

• 사용자 모드에서는 특권 명령 실행 시 트랩 발생
• 커널 모드에서는 모든 하드웨어·메모리 자원 접근 허용

시스템 콜 프로토콜

1. 라이브러리 함수(open(), read() 등)가 트랩 명령어 실행
2. 하드웨어가 사용자 레지스터를 커널 스택에 저장, 커널 모드 진입
3. 트랩 테이블에 등록된 핸들러로 분기해 서비스 수행
4. return‑from‑trap으로 사용자 모드 복귀

문제 #2: 프로세스 전환

타이머 인터럽트 기반 비협력적 전환

컨텍스트 스위치 프로토콜

1. 타이머 인터럽트 -> 하드웨어가 사용자 레지스터를 커널 스택에 저장
2. OS switch() 호출:
   • 이전 프로세스 A의 커널 레지스터를 PCB로 저장
   • 다음 프로세스 B의 레지스터를 PCB에서 복원 -> 커널 스택 교체
3. return‑from‑trap -> B의 레지스터 복원 후 사용자 모드로 복귀

동시성 고려사항

인터럽트 중첩: 시스템 콜 처리 중 또 다른 인터럽트 발생

해결 기법:

• 인터럽트 비활성화 구역 최소화
• 락(lock) 메커니즘으로 핵심 자료구조 보호
• 멀티프로세서 환경에서는 더 정교한 동시성 제어 필요

요약 및 측정 과제

Limited Direct Execution Protocol:

1. 트랩 테이블 “baby‑proofing”
2. 사용자 코드 직접 실행
3. 트랩·인터럽트 시 커널 개입
4. 타이머 인터럽트로 시간분할 전환

측정 과제:

• gettimeofday()로 시스템 콜 비용 측정
• 파이프+sched_setaffinity()로 컨텍스트 스위치 비용 측정

핵심 용어

Limited Direct Execution: 효율성과 제어권 보장을 위한 하드웨어+OS 협력 기법

Trap / return-from-trap: 시스템 콜 진입·복귀용 특권 명령어

User Mode / Kernel Mode: 권한 제한 모드 vs 특권 모드

Context Switch: 프로세스 전환을 위한 레지스터 저장/복원 프로토콜

Trap Table: 트랩 핸들러 주소 목록, 부팅 시 OS가 설정

CPU Scheduling

스케줄링 개요

운영체제 스케줄러는 컨텍스트 스위치 등 저수준 메커니즘 위에 작동하는 고수준 정책(스케줄링 규율)을 결정합니다. 이 장에서는 대표적인 스케줄링 정책을 살펴보고, 각 정책의 가정, 성능 메트릭, 장단점을 분석합니다.

작업 부하 가정 (Workload Assumptions)

1. 각 작업(job)이 동일한 실행 시간
2. 모든 작업이 동시에 도착
3. 시작되면 중단 없이 완료까지 실행
4. I/O 없이 CPU만 사용
5. 각 작업의 런타임(실행 시간)을 미리 알고 있음

실제 환경과는 거리가 있지만, 이후 장에서 순차적으로 완화해 나갑니다.

스케줄링 메트릭 (Scheduling Metrics)

Turnaround Time: 작업 완료 시각 − 도착 시각 (T_completion − T_arrival)

Fairness: 예) Jain’s Fairness Index. 성능 최적화와 공정성은 종종 상충합니다.

FIFO (First In, First Out)

정의: 도착 순서대로 작업 실행

장점: 구현이 간단

단점: 긴 작업이 앞에 오면 짧은 작업들이 대기하는 컨보이 효과 발생

SJF (Shortest Job First)

비선점형: 실행 시간이 짧은 작업부터 순차 실행

FIFO 대비 평균 Turnaround를 획기적으로 개선

전제: 작업 런타임을 알아야 함

STCF / PSJF (Shortest Time‑to‑Completion First)

선점형 SJF: 새 작업 도착 시 남은 실행 시간이 가장 짧은 작업을 즉시 실행

Late‑arrival 문제 해소, 평균 Turnaround 최적화

응답 시간(Response Time)

정의: 작업 도착 시각부터 첫 실행 시각까지의 시간 (T_first_run − T_arrival)

STCF 등은 Turnaround에 좋지만, 응답 시간은 열악

라운드 로빈(Round Robin)

Time Slice(퀀텀) 단위로 작업을 순환 실행(시간 분할)

장점: 공정성 유지, 응답 시간 대폭 개선

단점: Context Switch 오버헤드 -> 퀀텀 길이 결정 시 trade‑off 필요

Amortization 팁

퀀텀을 늘려 Context Switch 비용을 희석(Amortize)해 오버헤드를 줄일 수 있음

퀀텀(time slice): Round Robin 스케줄링에서, 한 프로세스가 연속으로 CPU를 차지하는 최대 시간 단위입니다. 보통 수 밀리초(ms) 단위로 설정합니다.

컨텍스트 스위치(Context Switch) 비용:

• 프로세스 A -> B 전환 시, A의 레지스터·PC·스택 포인터 등을 저장하고, B의 상태를 복원하는 데 드는 오버헤드(수십~수백 마이크로초).
• 이 시간만큼 CPU는 “실제 작업”이 아니라 “스위칭 작업”에 소비됩니다.

퀀텀이 짧으면

• 더 자주 컨텍스트 스위치가 발생 -> 오버헤드가 누적 -> 유용한 계산 시간이 줄어듦.

퀀텀을 늘리면

• 한 번 스위치 후 오랫동안 동일 프로세스가 CPU를 사용 -> 스위치 횟수 감소
• 전체 실행 시간 대비 스위치 비용 비율이 작아져 “희석(amortize)”됨
• 따라서 CPU는 실제 작업(버스트) 수행에 더 많은 시간을 쓸 수 있게 됩니다.

I/O 통합 (Incorporating I/O)

CPU 버스트와 I/O 버스트를 독립 작업으로 간주

I/O 대기 중인 작업이 Blocked 상태가 되면 다른 작업을 실행해 CPU 활용도를 극대화

CPU 버스트

• 프로세스가 연속해서 CPU 연산만 수행하는 구간입니다.
• 예를 들어, 숫자를 계산하거나 메모리에 올라온 데이터를 처리하는 순수 계산 작업이 계속 이어질 때를 가리킵니다.
• 길이가 다양하게 나타나며, 계산량이 많은 작업일수록 길게 유지됩니다.

I/O 버스트

• 프로세스가 디스크, 네트워크, 터미널 같은 I/O 장치와 입출력 작업을 수행하는 구간입니다.
• 예컨대 파일을 읽거나 쓰고, 네트워크로 데이터를 주고받고, 키보드 입력을 기다리는 동안을 말합니다.
• 이 구간 동안에는 CPU를 거의 사용하지 않고, 대신 I/O 장치의 응답을 기다립니다.

무(無) 오라클(No More Oracle)

런타임 정보를 모르는 현실을 반영해야 함

이후 장에서 MLFQ(Multi‑Level Feedback Queue)로 과거 실행 패턴을 이용해 미래 행동을 예측하는 기법 소개 예정

요약

두 계열의 스케줄러:

1. 길이 기반(SJF, STCF) -> Turnaround 최적화, 응답 시간 미흡
2. 공정성 기반(RR) -> Response Time 최적화, Turnaround 악화

I/O, 예측 불가능성 등을 다루기 위해 혼합 기법과 예측 메커니즘이 필요합니다.

Multi‑Level Feedback

동기 및 기본 개념

목표: 짧은(interactive) 작업에는 빠른 응답, 긴(CPU‑bound) 작업에는 공정한 진행 보장

피드백 기반 우선순위 조정: 과거 CPU 사용 패턴을 관찰해 우선순위를 동적으로 변경

MLFQ의 다섯 가지 규칙

1. Rule 1: 우선순위(A) > 우선순위(B) -> A 실행
2. Rule 2: 우선순위 동일 -> 해당 큐의 time‑slice(quantum)로 Round Robin
3. Rule 3: 새 작업은 최상위 큐(Q0)에 배치
4. Rule 4: 주어진 큐에서 할당된 시간을 모두 사용하면(할당 여러 번 분할 사용 포함) 한 단계 낮은 큐로 강등
5. Rule 5: 일정 기간 S마다 모든 작업을 최상위 큐로 승격(스타베이션 방지 및 행동 변화 반영)

우선순위 부스트 (Rule 5)

필요성: 낮은 큐에 내려간 CPU‑bound 작업이 무한 대기(starvation) 되는 문제 해결

“voo‑doo constant” 문제: Boost 주기 S 설정이 워크로드마다 달라, 적절한 값을 찾기 어려움

Anti‑Gaming을 위한 개선 (Rule 4 개정)

원래 Rule 4a/4b: I/O 전에는 같은 큐 유지 가능 -> CPU 독점(gaming) 유발

개선된 Rule 4: I/O 여부와 상관없이 할당된 총 시간을 모두 사용하면 강등 -> 공정성 확보

파라미터 튜닝

큐 수, 큐별 quantum, boost 주기 S 등을 워크로드에 맞춰 조정

Quantum 차별화:

• 상위 큐(Q0): 짧은 quantum(≈10 ms) -> 반응성 향상
• 하위 큐(Q2 이상): 긴 quantum(수십 ~ 수백 ms) -> CPU‑bound 효율 향상

실제 시스템 구현 예

Solaris TS: 60개 큐, 20 ms->수백 ms로 증가하는 quantum, 약 1 s마다 boost

FreeBSD (4.3BSD): decay‑usage 방식으로 우선순위 수식 계산, 사용량 시간 경과에 따라 감소시켜 boost 효과

사용자·관리자 조언(Advice)

nice(스케줄러), madvise(메모리), 파일 시스템 프리페치 등 다양한 부분에서 hint 제공 가능

일부 시스템은 OS 전용 높은 우선순위 큐를 예약해 사용자 작업과 격리

요약

• Interactive 성능: 짧은 작업에 빠른 응답 제공 (SJF/STCF 유사)
• Fairness: 긴 작업도 starvation 없이 주기적 실행 보장
• 적응성: 워크로드 변화에 따라 우선순위 동적 조정

MLFQ는 “다단계 큐 + 실행 피드백”이라는 간단한 아이디어로, 다양한 작업 부류를 균형 있게 처리하는 강력한 스케줄링 기법입니다.

Lottery Scheduling

Proportional Share Scheduling 개념

목표: 시스템 자원(CPU 시간)을 티켓 수나 가중치에 비례하여 공정하게 분배

적용: 가상화 환경에서 가상 머신에 CPU 사이클을 할당하거나, 프로세스별 우선순위를 가변적으로 설정할 때 유용

Lottery Scheduling

아이디어: 각 작업에 티켓을 할당하고, 매 스케줄링 시 무작위로 티켓을 추첨

특징:

• 단순성: 티켓 풀에 번호만 넣었다 뽑으면 됨
• 확률적 공정성: 충분히 긴 시간 동안, 각 작업이 할당된 티켓 비율에 따라 CPU 시간을 차지
• 유연성: 티켓 수 조절로 우선순위 부여 단점:
• 무작위성으로 인해 짧은 시간 구간에서는 불공정할 수 있음
• 티켓 풀이 클수록 추첨 비용 증가 (보통 선형 검색)

Stride Scheduling

아이디어: Lottery를 결정론적 방식으로 구현

구성 요소:

• Stride = L / tickets (L은 큰 상수, 예: 10,000)
• 각 작업은 pass 값을 가지며, 매 실행마다 자신의 stride를 pass에 더함
• 다음 실행 작업은 최소 pass 값을 가진 작업을 선택

장점: 예측 가능하고, 확률적 변동이 없음

단점: stride 계산에 오버헤드, 티켓 재할당 시 복잡도

Completely Fair Scheduler (CFS)

Linux의 CFS는 가중치 기반 Round‑Robin을 확장한 형태입니다.

가중치(Weight)와 nice 레벨

UNIX의 nice 값을 −20~+19 범위로 지정해 프로세스 우선순위를 설정

CFS는 nice 값을 weight 테이블(40개 항목)로 매핑, 기본 weight₀=1024 -> time_slice 계산 시 사용

time slice 계산

n개의 runnable 프로세스에 대해:

\[timeslice_k = {weight_k\over \displaystyle\sum_{k=0}^{k=n}{weight_k}} \times SchedLatency\]

예: A(nice = –5, weight = 3121), B(nice = 0, weight = 1024), sched_latency=48 ms -> A ≈ 36 ms, B ≈ 12 ms

vruntime 업데이트

실제 실행 시간(runtimeᵢ)에 대해:

\[vruntime_i += {weight_0\over weight_i} \times runtime_i\]

가중치가 클수록 vruntime 증가율이 느려, 더 많은 CPU 시간이 보장됨

자료구조: 레드-블랙 트리

runnable 프로세스를 vruntime 기준으로 정렬된 레드‑블랙 트리에 저장

다음 실행할 프로세스를 최소 vruntime 노드에서 O(log n) 시간에 선택

sleep -> runnable 전환 시 vruntime을 트리의 최소 vruntime으로 조정해 starvation 방지

장단점 및 활용

장점:

• 확장성: 수천 개 프로세스에서도 O(log n) 스케줄링
• 공정성: 가중치에 따른 비례 분배, nice 값 조절 가능 단점:
• I/O 집중 작업은 wakeup 후 과도한 CPU 점유 가능
• 티켓/가중치 할당 정책은 여전히 관리자가 결정해야 함

적용 예: 가상화 플랫폼(ESX Server), 클라우드 환경, 대규모 데이터 센터

Address Spaces

예시 주소 공간 구조

가상 주소 공간은 크게 세 영역으로 나뉩니다:

• 코드(Code): 프로그램 명령어가 저장되는 고정 크기 세그먼트
• 힙(Heap): malloc() 등으로 동적할당된 데이터가 위치하며, 코드 바로 아래에서 위로 성장
• 스택(Stack): 지역 변수·함수 인자·리턴 주소를 저장하며, 주소 공간의 끝(최상위)에서 아래로 성장

이처럼 힙과 스택을 주소 공간의 양 끝에 배치하면 두 영역이 서로 충돌 없이 성장할 수 있습니다

메모리 가상화의 핵심 과제

가상화 목표: 여러 프로세스가 각각 32비트(또는 64비트)처럼 보이는 큰 주소 공간을 가지면서도, 실제로는 하나의 물리 메모리를 공유하도록 만드는 것

작동 원리: 프로세스가 가상 주소(예: 0)를 참조하면, 하드웨어 MMU와 운영체제가 협력해 실제 물리 주소(예: 320 KB)로 투명하게 변환합니다

가상 메모리 시스템의 설계 목표

투명성(Transparency)

• 애플리케이션은 메모리가 가상화되었다는 사실을 인지하지 못해야 하며, 마치 자신만의 물리 메모리가 있는 것처럼 동작해야 합니다.

효율성(Efficiency)

• 시간적 오버헤드(TLB 활용 등)와 공간적 오버헤드(페이지 테이블 등 지원 구조) 양쪽을 최소화해야 합니다.
• 하드웨어 TLB 같은 지원 장치를 활용해 성능 저하를 줄입니다.

보호(Protection) / 격리(Isolation)

• 프로세스 간, 그리고 프로세스와 커널 간 메모리 접근을 엄격히 분리해, 하나의 오류가 다른 프로세스나 OS를 손상시키지 않도록 보장합니다

“모든 주소는 가상 주소”

사용자 프로그램이 출력하는 포인터 값(예: main() 위치, malloc() 반환 주소, 스택 변수 주소)은 모두 가상 주소입니다.

실제 물리 주소는 운영체제와 하드웨어만이 알고 있으며, 가상 주소는 단지 “메모리 레이아웃의 환상”임을 기억해야 합니다

요약

운영체제의 가상 메모리 서브시스템은

1. 각 프로세스에 프라이빗, 크고 희소한 주소 공간을 제공하고,
2. 하드웨어(TLB, MMU)와 협력하여 가상 주소를 물리 주소로 변환하며,
3. 투명성, 효율성, 격리라는 세 가지 핵심 목표를 달성하도록 설계됩니다. 이후 장들에서는 페이지 테이블, TLB, 다단계 페이지 테이블, 교체 정책 등의 메커니즘과 정책을 단계적으로 학습해 나갑니다

Address Translation

동적 재배치(Dynamic Relocation) 개요

“Base-and-bounds” 방식으로, 프로세스가 생성하는 가상 주소에 하드웨어가 base 레지스터 값을 더해 물리 주소로 변환하며, bounds 레지스터로 범위 검사까지 수행합니다. 이를 통해 프로세스마다 독립된 연속 물리 영역을 제공하면서도 CPU에서 직접 실행 속도를 유지합니다

하드웨어 요구사항

1. 특권 모드(Privileged/User Mode): 사용자 모드에서만 실행 가능한 명령을 제한하고, 커널 모드에서만 base/bounds 설정 등 특권 작업을 허용합니다.
2. Base/Bounds 레지스터: 각 CPU MMU에 한 쌍의 레지스터가 있어, 가상 주소에 base를 더하고 bounds를 체크하는 전용 회로가 필요합니다.
3. 주소 변환 및 예외 처리 회로: 가상->물리 변환을 빠르게 수행하고, bounds 위반 시 예외(trap)를 발생시켜 OS 예외 핸들러로 분기하도록 지원합니다.
4. 특권 명령어: OS가 부팅 시와 컨텍스트 스위치 시 base/bounds 값을 설정·갱신할 수 있도록 하는 명령이 있어야 합니다

운영체제 책임

메모리 할당/회수

• 프로세스 생성 시, free list 같은 자료구조를 검색해 물리 메모리 슬롯을 할당하고, 종료 시 해당 슬롯을 다시 회수해 표시합니다.

Base/Bounds 관리

• 컨텍스트 스위치 시 CPU base/bounds 레지스터 값을 현재 프로세스 PCB에 저장하고, 새 프로세스의 값을 복원해야 합니다.
• 또한, 프로세스 이동(migration)이 필요할 때는 메모리 복사 후 PCB의 base 값을 업데이트합니다.

예외 핸들링

• 부팅 시 트랩 테이블에 “out‑of‑bounds” 및 “privileged instruction” 예외 핸들러 주소를 설정하고, 실행 중 예외 발생 시 해당 핸들러를 호출해 보통 프로세스를 강제 종료합니다.

부팅 초기화

• 트랩 테이블 설정, 타이머 인터럽트 초기화, 프로세스 테이블·free list 초기화 등을 수행해 시스템을 준비합니다

동작 타임라인 요약

부팅 시 (Boot)

1. 트랩 테이블(시스템 콜·타이머·메모리 예외) 초기화
2. 인터럽트 타이머 시작
3. 프로세스·free list 구조 초기화

실행 중 (Runtime)

1. 프로세스 A 실행: 가상 주소 변환은 전부 하드웨어가 처리
2. 타이머 인터럽트 발생 -> 커널 전환 -> 컨텍스트 스위치(A->B)
3. B 실행 중 “bad load” 발생 -> bounds 예외 -> OS가 B 종료·메모리 회수
4. 이후도 모두 LDE(제한적 직접 실행) 프로토콜로 동작

장점·한계

장점:

• 매우 적은 하드웨어 추가 논리로 빠른 주소 변환
• 프로세스 간 메모리 격리(보호) 보장
• 프로세스는 번역 사실을 전혀 인지하지 못하는 투명성

한계:

• 내부 단편화(Internal Fragmentation): 고정 크기 슬롯에 주소 공간을 배치하므로 빈 공간이 낭비될 수 있음
• 더 세밀한 메모리 활용을 위해 세그멘테이션이나 페이징 같은 고급 기법이 필요합니다

Segmentation

가상 주소와 오프셋

가상 주소는 (segment, offset) 쌍으로 표현됩니다.

오프셋 처리:

• 순방향(positive) 오프셋: 코드·힙 영역처럼 위로 성장하는 세그먼트
• 역방향(negative) 오프셋: 스택처럼 아래로 성장하는 세그먼트

하드웨어는 세그먼트 레지스터에서 base와 size를 읽고,

1. 오프셋의 절대값이 size 이하인지 검사(범위 검사)
2. PA = base + offset 계산
3. 위반 시 예외(trap) 발생

보호 및 공유

세그먼트별 보호 비트(읽기·쓰기·실행)를 설정해, 변경 불가능한 코드 세그먼트를 여러 프로세스가 공유할 수 있습니다.

코드 세그먼트를 읽기 전용으로 표시하면, OS는 실제로 물리 메모리를 하나만 할당해 두고 각 프로세스의 세그먼트 레지스터에 같은 base를 지정해 공유합니다.

이로써 불필요한 메모리 복제를 줄이면서도 프로세스 간 격리는 유지됩니다

Coarse‑ vs Fine‑grained Segmentation

Coarse‑grained: 보통 코드·힙·스택처럼 몇 개의 큰 세그먼트만 사용

Fine‑grained: Multics 등에서는 수천 개의 작은 세그먼트를 지원

• 하드웨어는 메모리에 세그먼트 테이블을 두고, 해시나 트리 구조로 각 세그먼트를 빠르게 조회

Fine‑grained는 유연하지만, 하드웨어·OS 복잡도와 관리 오버헤드를 크게 증가시킵니다

OS의 추가 지원

컨텍스트 스위치

• 프로세스 전환 시, 각 프로세스의 세그먼트 레지스터(base, size, 보호 비트)를 PCB에 저장·복원해야 합니다.

세그먼트 성장/축소

• malloc()으로 힙 확장 시, 라이브러리가 sbrk() 같은 시스템 콜을 통해 OS에 요청 -> OS는 물리 메모리를 할당하고 세그먼트 크기 레지스터를 갱신합니다.

Free‑Space Management

• 여러 프로세스의 가변 크기 세그먼트가 물리 메모리에 흩어지면서 외부 단편화가 발생합니다.
• 컴팩션(빈 공간 통합)은 가능하지만, 메모리 복사 비용이 매우 높습니다.
• 대신 free‑list 알고리즘(best‑fit, first‑fit, buddy 등)을 사용해 큰 빈 영역을 유지하려 노력합니다.

외부 단편화와 컴팩션 예시

외부 단편화: 24 KB의 빈 공간이 있지만, 3 × 8 KB로 분산되어 있어 20 KB 요청을 만족하지 못하는 상황

컴팩션:

• 모든 세그먼트를 한쪽으로 몰아붙여 연속된 빈 공간을 확보
• 그러나 복사 오버헤드가 크고, 반복 시 또 다른 컴팩션이 필요해 비효율적일 수 있습니다

요약 및 한계

장점:

• 빠른 주소 변환(하드웨어만으로 계산)
• 가변 크기 세그먼트로 희소(sparse) 주소 공간 효과적 지원
• 코드 공유를 통한 메모리 절약

단점:

• 외부 단편화 문제(변수 크기 세그먼트 할당)
• 여전히 완전히 유연한 희소 주소 공간 지원에는 한계

다음 단계로, 페이지 기반 가상 메모리가 이 한계를 어떻게 극복하는지 배우게 됩니다.

Free Space Management

힙 확장(Heap Growth)

sbrk()/brk() 시스템 콜로 힙을 확장

OS는 free list에서 필요한 만큼의 물리 페이지를 찾아 프로세스 주소 공간에 매핑한 뒤, 새로운 힙 끝 주소를 반환합니다

기본 할당 전략 (17.3)

전략	장점	단점
Best Fit	요청 크기와 근접한 블록을 할당하여 내부 단편화 감소	전체 리스트를 탐색 -> 높은 검색 비용
Worst Fit	가장 큰 블록을 사용해 큰 잔여 블록 유지	전체 탐색 비용 높음, 외부 단편화 증가 경향
First Fit	리스트 앞에서 첫 번째 적합 블록 할당 -> 빠른 검색	작은 블록이 리스트 앞에 누적될 수 있음
Next Fit	마지막 검색 위치부터 탐색 시작 -> 블록 분산, First Fit 유사 성능	First Fit과 비슷한 성능, 리스트 순서 관리 필요

고급 기법

Segregated Lists

• 자주 요청되는 크기에 대해 전용 리스트 유지
• 장점: 특정 크기 할당/해제가 매우 빠름, 단편화 감소
• 단점: 풀 크기 결정의 어려움
• 예시: Solaris의 Slab Allocator

Buddy Allocation

• 전체 메모리를 2^N 크기 블록으로 관리
• 요청 크기에 맞게 반으로 분할하며 power-of-two 블록 할당
• 해제 시 인접한 “버디” 블록이 비어 있으면 병합(coalesce)
• 장점: coalescing이 단순(주소의 특정 비트 차이로 판별)
• 단점: 내부 단편화 발생 가능

기타 자료구조

• 성능·확장성 위해 균형 이진 트리, 스플레이 트리, 부분 순서 트리 등 활용

실제 할당기 설계 고려사항

속도 vs. 단편화

• 빠른 검색(First/Next Fit)과 낮은 단편화(Best Fit) 간 트레이드오프

단순성 vs. 확장성

• Buddy, Segregated Lists는 단순하지만 멀티코어 동시성 잠금 비용 고려 필요
• Hoard, jemalloc 같은 현대 할당기는 멀티스레드·다중 프로세서 환경에서 최적화

Introduction to Paging

페이징의 동기와 개요

세그멘테이션처럼 가변 크기 대신, 고정 크기 페이지(예: 4 KB)와 고정 크기 프레임(물리 메모리 단위)으로 주소 공간을 분할

단편화(fragmentation) 관리가 단순해지며, 연속성이 필요 없는 할당·회수가 자유롭게 이루어짐

페이지 테이블의 저장 위치

각 프로세스마다 페이지 테이블을 유지하여, 가상 페이지 번호(VPN)->물리 프레임 번호(PFN)를 매핑

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

• 가상 페이지 수 = \(2^{32} / 2^{12} = 2^{20}\)
• PTE 크기 4B -> 페이지 테이블 크기 ≈ 4 MB

MMU 내부에 두기에는 너무 커서, 일반 물리 메모리에 놓고 필요 시 스와핑도 가능

페이지 테이블 항목(PTE)의 구성

Valid/Present 비트: 페이지가 메모리에 상주하는지

Protection 비트: 읽기/쓰기/실행 권한

Dirty 비트: 페이지가 수정되었는지

Accessed 비트: 페이지가 참조되었는지 (교체 정책 시 활용)

Physical Frame Number (PFN): 실제 물리 프레임 번호

x86 PTE 예시 필드: P, R/W, U/S, PWT, PCD, A, D, PFN

페이징 성능 오버헤드

주소 변환 경로:

1. 가상 주소 -> VPN/오프셋 분할 -> MMU의 PTBR(Page Table Base Register)에서 PTE 주소 계산
2. 메모리에서 PTE 읽기 -> PFN 획득
3. PFN + 오프셋 결합 -> 최종 물리 주소 계산
4. 물리 메모리 접근

메모리 접근 횟수가 두 배 이상 증가 -> 성능 저하

이 오버헤드를 줄이기 위해 TLB가 후속 장에서 소개됨

메모리 접근 트레이스 예시

간단한 배열 초기화 코드(for (i…) array[i]=0;)를 통해

• 명령어 페치, 페이지 테이블 접근, 데이터 접근이 실제로 몇 번 발생하는지 추적
• 각 루프 반복마다 발생하는 페이지 테이블 워크의 수를 시각화하여, 오버헤드의 크기를 정량적으로 파악할 수 있음

Translation Lookaside Buffers

TLB 기본 알고리즘

1. 가상 주소에서 VPN을 추출한 뒤, 하드웨어 TLB를 조회
2. 히트 시 PFN을 꺼내 오프셋과 결합해 물리 주소 반환
3. 미스 시 트랩을 발생시켜 OS(또는 하드웨어)가 페이지 테이블을 조회·TLB 갱신 후 명령 재시도

배열 접근 예제

배열을 순차 접근할 때, 같은 페이지 내 참조는 높은 TLB 히트율을 보이고

페이지 경계를 넘어갈 때마다 미스가 발생함을 그래프로 시각화하여 보여 줌

TLB Miss 처리 주체

하드웨어 관리형 TLB (예: x86): 미스 시 CPU가 직접 페이지 테이블 워크 수행

소프트웨어 관리형 TLB (예: MIPS/SPARC): 미스가 예외(trap)로 전환되어 OS 커널이 처리 후 재시도

TLB 엔트리 구성

주요 필드: VPN, PFN, Valid/Present, Protection (R/W/X), Dirty, Accessed, ASID, Cache coherence bits 등

ASID를 활용해 프로세스별 엔트리 구분 가능

컨텍스트 스위치 이슈

프로세스 간 VPN -> PFN 매핑 충돌 방지를 위해

• 전체 플러시 or
• ASID 사용(플러시 없이 프로세스별 매핑 유지)

교체 정책

정책	교체 대상	장점	단점
OPT	앞으로 가장 나중에 다시 사용될 블록	이론적으로 최소 미스율 (하한)	미래 참조 정보가 필요해 실제 구현 불가
LRU	가장 오랫동안 사용되지 않은(가장 최근에 참조되지 않은) 블록	실제 워크로드에서 OPT에 근접하는 성능	“가장 최근 사용 시각”을 추적하기 위한 하드웨어/소프트웨어 오버헤드
FIFO	가장 먼저 캐시에 들어온(적재된) 블록	구현이 매우 간단 (원형 큐 포인터)	접근 패턴 무시 → Belády 역설(캐시 크기 증가 시 미스율 증가 가능)
Random	무작위로 선택된 블록	구현이 가장 단순, 오버헤드 최소	중요한 지역성 정보 전혀 반영 못함 → 성능이 예측 불가능하고 대체로 비효율적

실제 TLB 엔트리: MIPS R4000 사례

VPN: 19비트 (32비트 주소 공간의 하위 절반)

PFN: 24비트(최대 64 GiB 물리 메모리 지원)

기타: Global bit, 8비트 ASID, Dirty, Valid, Cache bits, Page mask(슈퍼페이지)

소프트웨어 관리: TLBP, TLBR, TLBWI, TLBWR 특권 명령어로 OS가 직접 엔트리 관리

요약

TLB를 통한 페이지 테이블 접근 캐싱으로, 가상 메모리 오버헤드를 대부분 제거

TLB 커버리지를 초과하는 워크로드는 심각한 성능 저하 초래

슈퍼페이지, 가상 색인 캐시 등 추가 기법으로 오버헤드 완화 가능

Advanced Page Tables

문제 제기

• 선형(linear) 페이지 테이블은 32비트 주소 공간, 4 KB 페이지, 4 B/PTE 기준으로 약 4 MB 크기를 가짐.
• 프로세스가 수십~백 개라면, 페이지 테이블만 수백 MB를 차지해 메모리 부담이 매우 큼

핵심 질문(CRUX)

• “페이지 테이블을 어떻게 더 작게 만들까? 새로운 자료구조가 도입되면 어떤 비효율이 생기는가?”

더 큰 페이지(Bigger Pages)

페이지 크기를 4 KB -> 16 KB로 네 배 늘리면, VPN 비트 수가 20 -> 18로 감소해 페이지 테이블 엔트리 수도 1/4로 줄어듦(약 1 MB)

장점: 선형 구조 유지, 구현 간단

단점:

• 내부 단편화(internal fragmentation) 증가
• 대형 페이지는 TLB 커버리지 관점에서는 유리하지만, 메모리 사용 패턴에 따라 유연성 저하

하이브리드(segmentation + paging)

Multics 아이디어: 먼저 세그먼트(예: 코드·데이터·스택)로 주소 공간을 나누고, 각 세그먼트마다 선형 페이지 테이블 사용

동작:

• 세그먼트 수만큼 소형 페이지 테이블 보유 -> 전체 크기 감소
• TLB 미스 시, 세그먼트 선택 후 해당 페이지 테이블 조회

장점: 주소 공간의 큰 비사용 영역 분리 가능, 메모리 절약

단점:

• 세그먼트 수만큼 레지스터·PDE 필요 -> 구현 복잡
• 외부 단편화(external fragmentation) 발생, 관리 오버헤드

다단계 페이지 테이블(Multi‑Level Page Tables)

아이디어: 선형 테이블을 트리 구조로 분할

1. 페이지 디렉터리(PD, Page Directory): 각 엔트리가 “페이지 테이블 페이지” 하나를 가리킴
2. 두 단계 조회: PD -> 특정 페이지 테이블 페이지(PTE 페이지) -> 최종 PTE

장점:

• 실제 사용 중인 가상 페이지에 대응하는 PTE 페이지만 메모리에 할당 -> 절감 효과
• 페이지 테이블 공간이 “주소 공간에서 사용된 크기”에 비례
• 비연속된 물리 페이지도 자유롭게 사용 가능(프리 페이지 풀 활용)

단점:

• TLB 미스 시 두 번의 메모리 접근 필요 -> 페이지 테이블 조회 비용 증가
• 자료구조·하드웨어·소프트웨어 구현 복잡도 상승

시간·공간 절충 (Time‑Space Trade‑Off)

선형 테이블: 조회 단순·TLB 미스 시 한 번 접근, 공간 비효율

다단계 테이블: 공간 효율 극대화, 조회 비용·복잡도 증가

설계 시 목표 워크로드와 시스템 제약에 따라 적절한 기법 선택이 필요