01-dialogue-threeeasy

1. 핵심 문제 상황

OS라는 복잡한 시스템의 동작 원리를 어떻게 하면 효과적으로 학습하고 구조적으로 이해할 것인가의 문제
단순히 지식을 전달받는 듣는 것에서 벗어나 어떻게 스스로 사고하고 실제 코드를 작성하는 실천을 통해 깊게 이해에 도달할 것인가의 문제

2. 강의 도입 질문

OS 학습의 근간이 되는 세 가지 핵심 주제(가상화, 병행성, 영속성)는 각각 무엇을 의미하는가?
왜 이 과목의 학습 방법으로 직접해보는것이 가장 강조되는가?
복잡한 아이디어를 이해하기 위해 교수와 학생이 대화 형식을 빌려 사고할 시간을 갖는 이유는 무엇인가?

3. 핵심 비유

아주 쉬운 세 가지 이야기(Three Easy Pieces) : OS의 방대한 세부 주제를 가상화, 병행성, 영속성이라는 세 가지 핵심 아이디어로 요약해 접근하는 방식
가상화, 병행성, 영속성 : OS가 물리적 자원을 관리하고 동시성 문제를 해결하며 데이터를 안전하게 보존하기 위해 사용하는 세 가지 주요 매커니즘

4. 이후 어떤 개념을 공부하는가

CPU 스케줄링 결정 방식, 가상 메모리 시스템의 과부하 처리, 가상 머신 모니터의 동작 원리 디스크 상의 정보 관리 및 분산 시스템 구축의 기초 개념들

02-intro

1. 도입 배경

해결하려는 문제 : 컴퓨터 시스템을 사용하기 편리하면서도 정확하고 올바르게 동작시켜야 하는 책임이 필요함
필요성 : 물리적 자원(CPU, 메모리, 디스크)을 효율적이고 공정하게 관리하여 사용자에게 강력한 가상 형태의 자원을 제공해야 함
강의 도입 질문
- 프로그램이 실행될 때 프로세서 내부에서는 실제로 어떤 일이 일어나는가?
- 단 하나의 CPU만 있는 시스템에서 어떻게 여러 개의 프로그램이 동시에 실행되는 것처럼 보일 수 있는가?

2. 소주제

프로그램 실행의 기초와 Von Neumann 모델
OS의 정의와 자원 관리자로서의 역할
CPU 가상화와 시분할 정책
메모리 가상화와 주소 공간
병행성 문제와 원자성
영속성과 파일 시스템
OS 설계 목표 및 역사

3. 핵심 개념 정리

API별 역할 및 특징(C언어)

OS의 목적은 하드웨어(CPU, 메모리, 디스크)를 직접 제어해야 한다 때문에 메모리 주소(포인터)에 직접 접근할 수 있는 기능을 가진 C언어를 예시로 사용한다

라이브러리 함수
- malloc( ) : 힙 메모리를 할당받기 위해 호출하는 라이브러리 API
쓰레드 라이브러리
- Pthread_create( ) : 동일한 메모리 공간에서 함께 실행될 새로운 쓰레드를 생성
System Call
- open( ) : 파일을 생성하고 열기 위해 사용되는 시스템 콜
- write( ) : 열린 파일에 데이터를 기록
- close( ) : 더 이상 해당 파일을 사용하지 않음을 OS에 알리고 닫음

개념별 정의

가상화(Virtualization) : 물리적 자원을 이용해 일반적이고 사용이 편리한 가상 형태의 자원을 생성하는 기법
주소 공간(Address space) : 각 프로세스가 갖는 자신만의 가상 메모리 영역으로 OS가 이를 물리 메모리로 매핑함
병행성(Concurrency) : 프로그램이 동시에 여러 일을 하려 할 때 발생하는 문제들을 해결하는 주제
영속성(Persistence) : 전원이 꺼져도 데이터를 안전하게 보존하기 위한 하드웨어(SSD/HDD)와 소프트웨어(파일 시스템)의 체계

개념 간 관계

OS는 하드웨어의 도움을 받아 가상화를 구현하고 API를 통해 사용자에게 기능을 제공하며 정책을 통해 자원을 관리

4. 동작 흐름

System Call(영속성)

open( ) : 시스템 콜로 파일을 생성
write( ) : 시스템 콜로 데이터를 파일에 씀 (ex. “hello world”)
close( ) : 시스템 콜로 파일을 닫아 작업을 완료

성능/안정성 영향 요소

오버헤드 최소화 : 가상화 기능을 제공하면서도 시간적/공간적 낭비를 줄이는 것이 주요 설계 목표임
보호와 고립 : 한 프로세스의 오류가 다른 프로세스나 OS에 영향을 주지 않도록 격리해야함

5. 구조 요약

OS는 물리 자원(CPU, 메모리, 디스크)을 추상화해 사용자에게 가상 머신과 표준 라이브러리 역할을 수행
주요 구성 요소
- CPU 가상화 : 시분할을 통한 다수 프로그램 동시 실행
- 메모리 가상화 : 프로세스별 전용 주소 공간 제공
- 병행성 관리 : 공유 데이터 접근 시 발생하는 비결정성 해결
- 영속성 관리 : 파일 시스템을 통한 데이터 영구 저장
- 자원 관리자 : 자원의 효율적이고 공정한 배분

6. 키워드

Von Neumann : 반입-해석-실행의 순차적 모델
System Call : OS 기능을 요청하는 인터페이스
Time Sharing : CPU를 짧게 나누어 여러 프로그램을 실행하는 기법
Atomic : 명령어들이 한 번에 분리되지 않고 실행되어야 하는 성질
Isolation : 프로세스를 다른 프로세스로부터 고립시키는 원칙

정리

OS는 가상화를 통해 복잡한 하드웨어를 사요하기 쉬운 자원으로 변환하고 관리하는 소프트웨어임

혼동 금지

커널 모드 vs 사용자 모드

커널 모드는 하드웨어 저권을 갖지만 사용자 모드는 특권 명령어 실행이 제한됨

Mechanism vs Policy

기법(어떻게)과 정책(어느 것)은 모듈성을 위해 분리되어야함

03-dialogue-virtualization

가상화(virtualization)

1. 핵심 문제 상황

물리적 자원(ex. 책에서 복숭아 라는 예시를 사용)은 하나 뿐이지만 이를 먹고 싶어 하는 사람(응용 프로그램)은 매우 많음
자원을 실제로 공유하고 있음에도 불구하고 사용자(응용 프로그램)가 이를 눈치채지 못하게 하면서 각자가 전용 자원을 소유한 것 같은 환상(illusion)을 어떻게 심어줄 것인가의 문제

2. 강의 도입 질문

어떻게 하나의 진짜 복숭아로부터 많은 가상 복숭아를 만들어 모두를 행복하게할 수 있는가?
자원을 공유하는 동안 사용자가 낮잠을 자거나 다른 일을 하게 하여 눈치채지 못하게 하는 OS의 마술은 무엇인가?
시스템에 딱 한 개의 CPU만 존재할 때 OS는 어떻게 각 응용 프로그램이 자신만 사용하는 CPU를 가졌다고 믿게 만드는가?

3. 핵심 비유

가상 복숭아 : 한정된 실제 자원을 여러 사용자가 각자 소유한 것처럼 느끼게 만드는 OS의 가상활ㄹ 상징
CPU 가상화 : 단 한 개의 물리적 CPU를 각 응용 프로그램이 독점적으로 사용하는 여러 개ㅢ CPU인 것처럼 보이게 해 마술 같은 환상을 만들어 내는 작업

04-cpu-intro

1. 도입 배경

해결하려는 문제 : 실제 물리 CPU는 적으나 사용자는 웹 브라우저, 게임 등 수 많은 프로그램을 동시에 실행하길 원함
필요성 : 물리적 한계를 극복하고 사용자에게 무한에 가까운 CPU가 있다는 환상을 제공해야함
강의 도입 질문
- 디스크에 잠들어 있는 프로그램에 어떻게 생명을 불어넣는가?
- 단 하나의 CPU로 어떻게 백 개의 프로그램을 동시에 돌리는 것처럼 속일 수 있는가?

2. 소주제 지도

프로세스의 정의 및 하드웨어 상태
프로세스 API 개요
프로세스 생성의 구체적 단계
프로세스 상태 및 전이 메커니즘
자료 구조 : PCB와 xv6 사례

3. 핵심 개념

Process : 실행 중인 프로그램
시분할(Time Sharing) : 하나의 프로세스를 실행하고 중단한 뒤 다른 것을 실행하는 방식으로 CPU를 공유하는 기법
기법(Mechanism) : 기능을 구현하는 저수준 방법이나 규칙(ex. context switch)
정책(Policy) : 결정을 내리기 위한 고수준 알고리즘(ex. 스케줄링 정책)
머신 상태(Machine State) : 프로세스가 실행되는 동안 읽거나 갱신하는 레지스터(program counter, 스택 포인터 등)와 메모리(주소 공간)

개념간의 관계

OS는 기법(어떻게)와 정책(어느 것)을 분리해 모듈성을 확보함

4. 동작 흐름

프로그램에서 프로세스로의 변환

탑재(Load) : 디스크의 코드와 정적 데이터를 메모리(주소 공간)로 읽어 들임
- 현대 OS의 특징 : 실행 시 필요한 부분만 탑재하는 늦은 탑재(Lazy Loading) 방식 사용
스택 할당 : 지역 변수, 함수 인자, 리턴 주소를 위한 실행시간 스택을 할당하고 argc, argv로 초기화함
힙 할당 : 동적 데이터 구조(malloc 요청 등)를 위한 공간 할당
I/O 초기화 : 기본적으로 표준 입력(STDIN), 출력(STDOUT), 에러(STDERR)에 해당하는 파일 디스크립터를 부여함
시작 : main( ) 루틴으로 분기해 CPU 제어권을 프로세스에 넘김

하드웨어 ←> OS 상태 전이 메커니즘

실행(Running) : 프로세서에서 명령어를 실행 중인 상태
준비(Ready) : 실행할 준비는 되었으나 OS가 다른 프로세스를 실행 중이라 대기하는 상태
대기(Blocked) : 입출력 요청 등 특정 이벤트가 완료될 때까지 실행이 중단된 상태
상태 변화 흐름
- 실행 → 대기 : 입출력 시작 시 OS가 감지해 전환
- 대기 → 준비 : 입출력 완료 인터럽트 발생 시 전환
- 준비 → 실행 : 스케줄러의 정책에 따라 선택됨

5. 구조 요약

OS의 CPU 가상화 전략

물리 자원 추상화 : 프로그램을 프로세스라는 개념으로 변환
시분할 메커니즘 : 빠른 context switch으로 동시 실행 환상 제공
자원 분할 : CPU는 시분할(시간 단위 공유), 디스크는 공간 분할(영역 단위 공유)

프로세스 구성

메모리(코드/데이터/스택/힙) + 레지스터(Program Counter/SP) + I/O 정보(열린 파일)

6. 핵심 포인트

키워드

Process : 실행 중인 프로그램
PCB(Process Control Block) : 각 프로세스 정보를 저장하는 C 자료 구조
Context Switch(문맥 교환) : 현재 레지스터 값을 저장하고 다음 프로세스 값을 복원하는 기법
Zombie : 종료되었으나 메모리에 남아 부모의 wait( )을 기다리는 상태
Program Counter(PC) : 다음 실행할 명령어 주소를 가진 레지스터

요약

OS는 기법(context switch)과 정책(스케줄링)을 통해 단일 CPU를 여러 가상 CPU로 변환해 프로세스를 관리함

혼동 금지

준비 vs 대기

준비는 CPU만 주어지면 즉시 실행 가능하나 대기는 특정 사건(I/O 등)이 해결되어야만 준비 상태로 갈 수 있음

05-cpu-api

프로세스 api 전체 요약

1. 도입 배경

해결하려는 문제 : 프로세스를 생성하고 제어하기 위해 OS는 어떤 인터페이스를 제공해야 하며 어떻게 설계해야 유용하고 편리한가?
필요성 : 시스템의 실제적인 측면을 이해하고 사용자가 프로그램을 실행하거나 중단하는 등 시스템과 상호작용하는 근본적인 방법을 파악해야함
강의 도입 질문
- 왜 Unix는 프로세스를 생성할 때 복사(fork)와 교체(exec)라는 두 단계를 거치는가?
- Shell은 어떻게 우리가 입력한 명령어를 실제 프로그램으로 실행시키는가?

2. 소주제 지도

fork( ) 시스템 콜 : 프로세스 복제 생성
wait( ) 시스템 콜 : 자식 프로세스 대기
exec( ) 시스템 콜 : 프로그램 덮어쓰기 및 실행
API 설계의 이유와 Shell의 동작 원리
기타 API
- kill( )
- ps
- top

3. 핵심 개념

1. fork( )

역할 : 호출한 프로세스의 복사본인 새로운 프로세스(자식)를 생성함
인자 : 없음
반환값 : 부모에게는 자식의 PID, 자식에게는 0을 반환(실패 시 음수)
상태변화: 자식은 자신만의 주소 공간, 레지스터, PC를 갖지만 부모의 상태를 복제한 시점부터 실행을 시작함

2. wait( )

역할 : 자식 프로세스가 종료될 때까지 부모의 실행을 중지시킴
인자 : 자식의 상태 정보를 저장할 정수형 포인터(필요 없으면 NULL)
반환값 : 종료된 자식의 PID

3. exec( ) 계열(execvp 등)

역할 : 현재 실행 중인 프로세스를 새로운 프로그램으로 완전히 대체함
인자 : 실행 파일 이름, 인자 배열
상태변화 : 현재 주소 공간을 새 프로그램의 코드/데이터로 덮어쓰고 스택/힙을 초기화함, 성공 시 호출지로 리턴하지 않음

개념간 관계

fork( )로 복제하고 exec( )로 교체하는 분리된 구조는 쉘이 exec( ) 호출 전 입출력 재지정 등을 수행할 수 있게 함

4. 동작 흐름

입출력 재지정 과정

fork( ) 호출 : 부모 프로세스가 복제되어 자식 프로세스 탄생
close(STDOUT_FILENO) (자식) : 자식이 자신의 표준 출력을 닫음
open(./p4.output", ...) (자식) : 새 파일을 열면 비어있는 디스크립터인 1번(표준 출력 위치)에 할당됨
execvp("wc", ...) (자식) : wc 프로그램이 실행되면서 모든 출력이 화면이 아닌 파일로 향함
wait( ) (부모) : 자식의 작업이 끝날 때까지 부모가 대기 후 리턴
성능/안정성 영향 요소 : fork/exec의 분리는 강력하지만 복제 후 바로 교체되는 과정의 비효율성을 줄이기 위해 COW(Copy-on-Write)같은 최적화가 필요함

5. 구조 요약

Unix 프로세스 생성 3단계 : fork(복제) → exec(대체) → wait(동기화)
Lampson’s Law : 올바르게 선택하라 단순함도 추상화도 올바른 선택을 대신할 수 없다
주요 특징 : 비결정성(Nondeterminism) - 스케줄러에 따라 시행 순서가 매번 다를 수 있음

6. 핵심 포인트

키워드

PID : 프로세스 식별 번호
Parent/Child : 프로세스를 생성한 자와 생성된 자
Nondeterminism : 실행 순서를 단정 지을 수 없는 성징
Trap : 시스템 콜 호출 시 사용되는 특별한 하드웨어 명령어
Signal : 외부 사건을 프로세스에 전달하는 메커니즘

요약

Unix는 fork( )와 exec( )의 분리를 통해 프로세스 생성 전후의 강력한 제어권과 유연성을 확보함

혼동 금지

exec( )는 새 프로세스를 만드는 것이 아니라 현재 프로세스를 새 프로그램으로 갈아끼우는 것임

06-cpu-mechanisms

제한적 직접 실행 원리

1. 도입 배경

해결하려는 문제 : 시스템에 과중한 오버헤드를 주지 않으면서(성능), 동시에 CPU에 대한 통제권(제어)을 유지하며 어떻게 CPU를 가상화할 것인가?
필요성 : 제어권을 상실하면 한 프로세스가 컴퓨터를 영원히 장악하거나 접근해서는 안 되는 정보에 접근할 위험이 있음
강의 도입 질문
- OS는 어떻게 프로그램의 실행을 중단하고 다른 프로세스로 전환시킬 수 있는가?
- 프로세스가 디스크 읽기 같은 특권 명령어를 실행해야 할 때 OS는 어떻게 개입하는가?

2. 제한적 직접 실행 원리 지도과정

기본 원리 : 제한적 직접 실행
문제점 1: 제한된 연산(사용자/커널 모드, 시스템 콜)
문제점 2: 프로세스 간 전환(타이머 인터럽트, context switch)
병행성 및 인터럽트처리
측정 및 성능

3. 핵심 개념

개념별 정의 및 하드웨어 구조

제한적 직접 실행(Limited Direct Execution, LDE) : 프로그램을 CPU 상에서 직접 실행하되 특정 시점에 OS가 개입해 시스템을 통제하는 기법
사용자 모드(User Mode) : 응용 프로그램이 실행되는 모드, 하드웨어 자원에 대한 접근 권한이 일부 제한
커널 모드(Kernel Mode) : OS가 실행되는 모드로 모든 특수한 명령어를 포함해 원하는 모든 작업 수행 가능(즉 사용자 모드와 달리 하드웨어 자원에 대한 접근 가능)
Trap : 시스템 콜 호출 시 사용되는 특별한 하드웨어 명령어로 커널 안으로 분기하며 특권 수준을 상향 조정함
Trap Table : 부팅 시 커널이 초기화하는 구조, 예외 사건 발생 시 실행할 트랩 핸들러의 주소를 하드웨어에게 전달
Timer Interrupt : 수 밀리 초마다 발생해 현재 프로세스를 중단시키고 OS가 제어권을 다시 획득하게 함
문맥 교환(Context Switch) : 현재 실행 중인 프로세스의 레지스터 값을 저장하고 곧 실행될 프로세스의 레지스터 값을 복원하는 기법

4. 동작 흐름

하드웨어 ←> OS 타임라인

부팅 단계(커널 모드)
1. OS가 트랩 테이블을 초기화함
2. 하드웨어가 시스템 콜 핸들러, 타이머 핸들러 등의 주소를 기억
3. OS가 인터럽트 타이머를 시작함
실행 단계(사용자 모드)
1. OS가 return-from-trap 명령어를 통해 사용자 프로세스를 시작함
2. 프로세스가 시스템 콜을 호출하거나 타이머 인터럽트가 발생하면 하드웨어가 레지스터를 커널 스택에 저장하고 커널 모드로 진입
3. OS 트랩 핸들러가 요청을 처리하거나 스케줄러를 통해 프로세스 전환을 결정
4. Context Switch 시 switch( )루틴이 현재 프로세스(A)의 커널 레지스터를 PCB에 저아하고 새 프로세스(B)의 레지스터를 복원
5. return-from-trap 명령어로 새로운 프로세스 실행을 시작함
성능 영향 요소 : Context Switch 시 레지스터 저장/복원뿐 아니라 CPU 캐시, TLB 등의 정보 갱신 비용이 발생함

5. 구조 요약

LDE의 두 과제 : 성능(직접 실행) + 제어(모드 전환/인터럽트)
제어권 획득 방식
- 협조 방식 : 프로세스가 yield나 시스템 콜로 스스로 양보함
- 비협조 방식 : 타이머 인터럽트를 통해 강제적으로 제어권을 가져옴
Context Switch 핵심
- 하드웨어가 사용자 레지스터를 커널 스택에 저장
- OS가 커널 레지스터를 프로세스 구조체에 저장

6. 핵심 포인트

키워드

LDE : 효율성을 위해 프로그램을 CPU에서 직접 실행하는 원리
Trap : 사용자 모드에서 커널 모드로 진입하기 위한 수단
Kernel Stack : 커널 모드 진입 시 하드웨어 상태를 저장하는 장소
Privileged Instruction : 커널 모드에서만 실행 가능한 특권 명령어
Timer Interrupt : 비협조적 프로세스로부터 제어를 뺏는 하드웨어 장치
Context Switch : 프로세스 간 실행 상태를 전환하는 메커니즘

정리

OS는 하드웨어 모드 전환과 타이머 인터럽트를 이용해 직접 실행의 성능을 유지하면서도 시스템 통제권을 확보함

혼동 금지

시스템 콜(Trap의 일종)은 의도적인 제어권 양도이나 타이머 인터럽트는 하드웨어에 의한 강제적 양도임

07-cpu-sched

스케줄링 개요

1. 도입 배경

해결하려는 문제: 스케줄링 정책을 생각하기 위한 기본적인 프레임워크를 어떻게 만들 것인가?
필요성 : 한정된 자원(CPU)을 효율적으로 사용하기 위해 어떤 프로세스를 언제 실행할지 결정하는 고수준 정책이 필요함
강의 도입 질문
- 모든 작업의 실행 시간을 미리 알 수 있다면 어떤 정책이 가장 효율적일까?
- 성능(반환 시간)과 공정성(응답 시간) 중 무엇을 우선시해야 하는가?

2. 소주제 지도

워크로드 가정 및 평가 항목
선입선출(FIFO) 및 호위함 효과
최단 작업 우선(SJF)및 최소 잔여시간 우선(STCF)
응답 시간과 RR
입출력 연산의 고려

3. 핵심 개념

알고리즘별 특징

FIFO(First-In-First-Out): 단순하고 구현하기 쉬우나 실행 시간이 긴 작업이 먼저 도착하면 짧은 작업들이 대기하는 호위함 효과가 발생함
SJF(Shortest Job First): 가장 짧은 실행 시간을 가진 작업을 먼저 실행함, 모든 작업이 동시에 도착할 때 반환 시간 기준 최적임
STCF(Shortest Time-to-Completion First): 선점형 SJF임, 새로운 작업 도착 시 잔여 시간이 가장 짧은 작업을 선택함 임의의 도착 시간 조건에서 반환 시간 기준 최적임
RR(Round Robin): 작업을 타임 슬라이스(타임 퀀텀) 단위로 번갈아 실행함 응답 시간 최적화에 유리하지만 반환 시간은 나쁨

수식항 의미

반환 시간 $(T_{t u r na ro u n d})$ : 작업이 완료된 시각에서 도착 시각을 뺀 시간 $(T_{co m pl e t i o n} - T_{a rr i v a l})$
응답 시간 $(T_{res p o n se})$ : 작업이 도착할 때부터 처음 스케줄 될 때까지의 시간 $(T_{f i rs t r u n} - T_{a rr i v a l})$

개념 간 관계

반환 시간 최적화(SJF / STCF) ←> 응답 시간 최적화(RR)는 서로 상충(Trade-off) 관계임

4. 동작 흐름

FIFO 호위함 효과
- 조건: A(100s), B(10s), C(10s), 도착(T=0)
- 순서: A(100s) → B(110s) → C(120s)
- 계산: 평균 반환 시간 ⇒ (100 + 110 + 120)/3 = 110s
SJF
- 조건: A(100s), B(10s), C(10s), 도착(T=0)
- 순서: B(10s) → C(20s) → A(120s)
- 계산: 평균 반환 시간 ⇒ (10 + 20 + 120)/3 = 50s
STCF
- 조건: A(100s), B(10s), C(10s), A 도착(T=0), B/C 도착(T=10)
- 순서: A(10s) → B(10s, 선점 실행) → C(10s, 선점 실행) → A(110s, 재개)
- 계산: 평균 반환 시간 ⇒ ((120-0) + (20-10) + (30-10)) / 3 = 50s
RR
- 조건: A,B,C(5s씩 사용), 동시 도착, 타임 슬라이스=1s
- 순서: A → B → C → A → B → C… 순환
- 계산: 평균 응답 시간 ⇒ (0+1+2)/3 = 1s

성능 영향 요소

타임 슬라이스가 짧을수록 응답 시간은 좋아지나 Context Switch 비용(캐시, TLB 갱신 등)으로 인한 오버헤드 증가

5. 요약

워크로드 5대 가정
- 동일 실행 시간
- 동시 도착
- 완료까지 실행
- CPU만 사용
- 사전 실행 시간 인지
스케줄링 알고리즘 분류
- 반환 시간 중심: FIFO(비선점), SJF(비선점), STCF(선점)
- 응답 시간 중심: RR(선점/타임 슬라이싱)
입출력 고려
- I/O 요청 시 프로세스를 대기 사태로 전환하고 다른 프로세스로 중첩 실행해 자원 이용률 극대화

6. 핵심 정리

키워드

Workload: 프로세스가 실행되는 상황
Convoy Effect: 긴 작업 뒤에 짧은 작업들이 밀리는 현상
Non-preemptive(비선점): 작업을 끝날 때까지 실행하는 방식
Preemptive(선점): 실행 중인작업을 중단시키고 다른 작업을 시작할 수 있는 방식
Time Slice: RR에서 작업을 전환하는 일정 시간 단위
Amortization: 고정 비용(Context Switch)을 상쇄하기 위해 타임 슬라이스를 조절하는 기술

요약

스케줄링은 반환 시간(SJF/STCF)과 응답 시간(RR) 사이의 상충 관계를 고려해 CPU 자원을 배분하는 정책임

혼동 금지

SJF는 모든 작업이 동시 도착할 때 최적 임의 시간에 도착할 경우 선점형인 STCF가 최적

08-cpu-sched-mlfq

스케주링: 멀티 레벨 피드백 큐(MLFQ)

1. 도입 배경

해결하려는 문제: 프로세스에 대한 사전 정보가 없는 상태에서 대화형 작업의 응답 시간을 최소화하고 동시에 짧은 작업을 먼저 실행해 반환 시간을 최적화하는 스케줄러를 어떻게 설계할 것인가?
강의 도입 질문
- 미래(작업의 실행 시간)를 알 수 없는 상태에서 어떻게 과거의 경험을 통해 최선의 결정을 내릴 수 있는가?
- 사용자나 프로그램이 스케줄러를 속여 CPU를 독접하는 것을 어떻게 방지할 것인가?

2. 소주제 지도

MLFQ의 정의와 두 가지 기본 규칙
우선순위 변경 규칙(규칙 3, 4a, 4b)과 동작 예시
현재 MLFQ의 문제점: 기아 상태와 스케줄러 조작
해결책 1: 우선순위 상향 조정(Priority Boost)
해결책 2: 더 나은 시간 측정(조작 방지)
MLFQ 조정 및 부두 상수

3. 핵심 개념

기본 규칙

규칙 1: Priority(A) > Priority(B)이면, A가 실행된다
규칙 2: Priority(A) = Priority(B)이면 A와 B는 RR 방식으로 실행된다
규칙 3: 작업이 시스템에 진입하면 가장 높은 우선순위(최상위 큐)에 배치된다
규칙 4(최종): 주어진 단계에서 시간 할당량을 모두 소진하면(CPU를 몇 번 양도했든 상관없이) 우선순위는 낮아짐
규칙 5(부스트): 일정 기간 S가 지나면 시스템의 모든 작업을 최상위 큐로 이동시킴

4. 동작 흐름

문서 수치 예제 기반 스케줄 순서 재현

긴 작업의 우선순위 변화
- T=0: 작업 진입(Q2) 타임 슬라이스 10ms 소진 → Q1으로 강등
- Q1에서 다시 10ms 소진 → Q0으로 강등 후 계속 머무름
조작 방지 메커니즘
- 기존 규칙 4a/4b: 9ms 사용 후 I/O 호출 → 동일 큐 유지 가능(조작 가능)
- 새 규칙 4: I/O 호출 여부와 상관없이 해당 큐에서 소진한 총 시간이 타임 슬라이스(ex. 10ms)에 도달하면 무조건 강능
우선 순위 상향 조정 예시
- S=50ms마다 부스트 발생 시 Q0에서 굶고 있던 긴 작업이 Q2로 이동해 다른 짧은 작업들과 경쟁할 기회를 얻음
성능/안정성 영향 요소
- 상향 조정 주기 S: 너무 크면 기아 발생, 너무 작으면 대화형 작업 응답성 저해(voodoo constants)
- 큐별 타임 슬라이스: 상위 큐는 짧게(대화형 최적화), 하위 큐는 길게(CPU 집중 작업 최적화) 설정

5. 구조 요약

MLFQ 핵심 기법 : 과거를 통해 미래를 예측하는 피드백 루프
주요 구성 요소
- 다단계 큐(우선 순위별 차등 관리)
- 동적 우선순위 할당(규칙 3~4)
- 기아 방지 장치(규칙 5: Priority Boost)
- 시간 할당량 누적 기록(조작 방지)

6. 핵심 정리

키워드

MLFQ: 멀티레벨 피드백 큐
Starvation(기아): 대화형 작업이 너무 많아 긴 작업이 실행되지 못하는 현상
Priority Boost: 기아 방지를 위해 모든 작업을 상위 큐로 올리는 것
Gaming the Scheduler: 스케줄러를 속여 CPU를 독점하려는 시도
Voodoo Constants: 정확한 결정에 흑마술이 필요한 것 같은 설정 값(S 등)

요약

MLFQ는 프로세스에 대한 사전 정보 없이도 과거 동작을 관찰해 응답 시간과 반환 시간을 동시에 최적화하는 스케줄러임

혼동 금지

MLFQ는 각 작업에 고정된 우선순위를 부여하는 것이 아닌 작업의 특성에 따라 동적으로 우선순위를 변경

09-cpu-sched-lottery

비례 배분 스케줄링

1. 도입 배경

해결하려는 문제: 반환 시간이나 응답 시간을 최적화하는 대신 각 작업에게 CPU의 일정 비율을 어떻게 보장할 것인가?
필요성: 특정 비율로 CPU를 배분하는 정교한 제어가 필요한 환경(ex. 가상화 데이터 센터)에서 유용함
강의 도입 질문
- 어떻게 하면 CPU 자원을 정확히 정해진 비율로 나눌 수 있을까?
- 무작위성을 스케줄링에 도입했을 때의 장점은 무엇인가?

2. 소주제 지도

추첨권(Ticket)의 개념과 무작위성
추첨 기법: 화폐, 양도, 팽창
추첨 스케줄링 구현 및 공정성 분석
보폭 스케줄링(Stride Scheduling)

3. 핵심 개념

알고리즘별 특징

추첨 스케줄링(Lottery Scheduling): 추첨권(티켓)을 통해 자원의 몫을 나타내며 무작위로 당첨자를 결정함 실행 시간이 길어질수록 실제 배분 비율이 목표 비율에 근접함
보폭 스케줄링(Stride Scheduling): 결정론적(Deterministic) 방식. 각 작업은 추첨권 수에 반비례하는 보폭을 가지며 가장 적은 Pass값을 가진 작업을 선택함

수식 및 지표

불공정 지표(U) : $U = 첫번째작업종료시간 / 두번째작업종료시간$ 이 1에 가까울수록 공정함 보폭(Stride) 계산: $St r i d e = 임의의큰값 / 작업의추첨권수$

개념 간 관계

추첨 스케줄링(확률적) → 보폭 스케줄링(결정론적) 보폭 스케줄링은 정확하지만 상태 정보(Pass)를 유지해야 하므로 새 작업의 진입 처리가 복잡함

4. 동작 흐름

문서 수치 예제 기반 스케줄 순서 재현

추첨 스케줄링 구현

총 추첨권 수(400)를 파악함
getrandom(0, 400)으로 당첨 번호(ex. 300)를 생성함
리스트 순회: A(100) → B(50) → C(250)
카운터 누적: A(100<300) → B(150<300) → C(400>300)
결과: 작업 C가 당첨되어 실행됨

보폭 스케줄링 실행 추적

조건: A(보폭 100), B(보폭 200), C(보폭 40). 초기 Pass(상태 정보)는 모두 0
모두 0이므로 A 선택 → 실행 후 Pass(A) = 100
현재 Pass(A:100, B:0, C:0) 중 최소값 B 선택 → 실행 후 Pass(B)=200
현재 Pass(A:100, B:200, C:0) 중 최소값 C 선택 → 실행 후 Pass(C) = 40
현재 Pass(A:100, B:200, C:40) 중 최소값 C 선택 → 실행 후 Pass(C) = 80
결과: 추첨권 비율에 맞춰 결정론적으로 실행됨

성능/안정성 영향 요소

무작위 방식은 가볍고 빠르지만(상태 정보 불필요) 작업의 길이가 짧을 경우 목표 비율을 정확히 맞추지 못함

5. 구조 요약

비례 배분 2대 기법: 추첨(무작위/확률) vs 보폭(결정론/정확)
추첨권 관리 기법
- 화폐(Currency): 로컬 티켓을 글로벌 티켓으로 변환
- 양도(Transfer): 클라이언트가 서버에게 일시적으로 티켓 증여
- 팽창(Inflation): 신뢰 관계에서 스스로 티켓 수 조절
구현 핵심: 리스트를 내림차순 정렬하면 검색 효율이 극대화됨

6. 핵심 정리

키워드

Ticket: 자원 배분 비율을 나타내는 단위
Randomness: 특이 상황에 강하고 관리가 가벼운 무작위 추첨 방식의 장점
Unfairness Metric( $U$ ): 두 작업의 종료 시간 비율
Stride: 티켓 수에 반비례하는 값( $L a r g e Va l u e / T i c k e t s$ )
Pass: 작업이 실행될 때마다 Stride 만큼 증가하는 누적값

요약

비례 배분 스케줄링은 티켓을 통해 각 작업에 정해진 비율의 CPU 시간을 할당하는 기법

혼동 금지

보폭 스케줄링은 추첨 방식보다 정확하지만 새로 도착한 작업의 Pass 값을 어떻게 설정할지(0으로 두면 CPU 독점 위험)의 문제가 있음

10-cpu-sched-multi

멀티 프로세서 스케줄링

1. 도입 배경

해결하려는 문제: 단일 CPU 스케줄링 원칙을 어떻게 다중 CPU 환경으로 확장할 것이며 하드웨어 캐시와 동기화 문제를 어떻게 해결할 것인가?
필요성: 싱글코어 성능 개선의 한계를 멀티코어 프로세서가 대중화되었으나 전통적 프로그램은 하나의 CPU만 사용하므로 이를 병렬로 실행하고 스케줄링할 기법이 필수적임
강의 도입 질문
- CPU가 여러 개인 시스템에서 프로세스가 CPU를 옮겨 다닐 때 어떤 성능 저하가 발생하는가?
- 모든 CPU가 하나의 작업 큐를 공유할 때 발생하는 병목 현상은 무엇인가?

2. 소주제 지도

배경: 멀티프로세서 구조와 하드웨어 캐시
캐시 일관성 문제와 버스 스누핑
동기화 및 Lock의 필요성
캐시 친화성(Cache Affinity)
단일 큐 스케줄링(SQMS)
멀티 큐 스케줄링(MQMS)
워크로드 불균형과 작업 훔치기
Linux 멀티프로세서 스케줄러 사례

3. 핵심 개념

개념별 정의 및 하드웨어 구조

캐시 일관성(Cache Coherence): 여러 CPU가 동일한 메모리 주소를 각자의 캐시에 갱신할 때 모든 CPU가 가장 최신 데이터를 볼 수 있도록 보장하는 하드웨어 메커니즘임
Bus Snooping: 캐시가 메모리 버스를 감시해 데이터 변경 발생 시 자신의 사본을 무효화하거나 갱신하는 하드웨어 기법임
캐시 친화성(Cache Affinity): 프로세스가 이전에 실행되었던 CPU에서 다시 실행될 때 캐시와 TLB에 남은 상태 정보를 재사용해 성능을 높이는 성질
SQMS: 모든 CPU가 단일 작업 큐를 공유하는 방식임. 구현이 단순하나 Lock 경합으로 인한 확장성 문제가 있음
MQMS: CPU마다 개별 큐를 두는 방식임. 확장성과 캐시 친화성이 좋으나 워크로드 불균형 문제가 발생함

개념 간 관계

멀티프로세서 환경에서는 캐시 일관성을 위해 하드웨어가 개입하고 소프트웨어(OS)는 캐시 친화성을 고려하여 SQMS나 MQMS 정책을 선택함

4. 동작 흐름

단계 시퀀스: 캐시 일관성 위반 시나리오

데이터 탑재: CPU 1이 메모리 주소 A를 읽어 자신의 캐시에 값 D를 저장함
데이터 갱신: CPU 1이 캐시의 주소 A 값을 D로 변경함(메모리 반영 지연)
프로세스 이주: OS가 해당 프로세스를 CPU 2로 이동시킴
결함 발생: CPU 2가 주소 A를 읽을 때 메모리에서 최신값 D가 아닌 옛날 값 D를 가져오는 문제가 발생함

단계 시퀀스: 작업 훔치기(Work Stealing)

불균형 감지: 작업 개수가 적은 (소스) 큐가 다른 (대상) 큐를 검사함
비교: 대상 큐가 소스 큐보다 훨씬 가득 차 있는지 확인함
이주: 워크로드 균형을 맞추기 위해 대상 큐에서 하나 이상의 작업을 소스 큐로 가져옴
성능 영향 요소
- Lock Contention(락 경합): SQMS에서 CPU 개수가 늘어날수록 단일 큐 접근을 위한 락 대기 시간이 증가해 실제 작업 시간이 줄어듦
- 캐시 친화성 무시: SQMS에서 작업이 CPU를 옮겨 다닐 때마다 캐시를 새로 채워야 하므로 성능이 저하됨

5. 구조 요약

멀티프로세서 스케줄링의 3대 과제
- 확장성
- 캐시 친화성
- 워크로드 불균형
구조 비교
- SQMS: 단일 공유 큐 + 중앙 집중식 락 → 단순함, 균형 용이, 확장성 낮음
- MQMS: CPU별 개별 큐 + 분산 락 → 확장성 높음, 친화성 높음, 불균형 위험
해결책: 작업 훔치기를 통한 동적 워크로드 균형 조정

6. 핵심 정리

키워드

Temporal Locality: 최근 접근한 데이터의 재접근 경향
Spatial Locality: 인접 주소 데이터의 접근 경향
Bus Snooping: 버스 감시를 통한 캐시 일관성 유지 기법
Cache Affinity: 동일 CPU 실행을 선호하는 성능 최적화 원리
Scalability: 프로세서 추가 시 성능이 비례해서 향상되는 능력
Migration: 작업 큐 간의 프로세스 이동
Work Stealing: 여유 큐가 바쁜 큐의 작업을 뺏어오는 기법

요약

멀티프로세서 스케줄링은 하드웨어의 캐시 메커니즘을 고려하면서 확장성(MQMS)과 균형(작업 훔치기) 사이의 최적점을 찾는 과정임

혼동 금지

캐시 일관성은 하드웨어가 해결하는 문제이나 캐시 친화성은 OS 스케줄러가 성능 향상을 위해 고려해야 할 정책적 요소임

11-cpu-dialogue

CPU 가상화 정리 대화 도입 요약

1. 핵심 문제 상황

CPU 가상화를 구현하기 위해 필요한 Trap, Timer Interrupt, Context Switch 등 하드웨어와 OS 간의 복잡한 상호작용을 어떻게 구조적으로 이해할 것인가의 문제
반환 시간과 응답 시간이라는 서로 대립하는 평가 기준 사이에서 최선의 해결책을 찾는 것이 아닌 사고를 피하며 실용적인 절충안을 찾아야 하는 공학적 선택의 문제

2. 강의 도입 질문

OS가 왜 편집증 환자처럼 시스템의 제어권을 독점하려 하면서도 프로그램은 가능한 효율적으로 실행되길 원하는가?
가게에서 껌을 사는 상황(짧은 작업)과 신용카드 결제가 안 되는 상황(긴 작업)의 비유를 통해 스케줄링의 어떤 원칙을 설명할 수 있는가?

3. 핵심 비유

제한적 직접 실행(Limited Direct Execution): 효율성을 위해 프로그램을 CPU에서 직접 실행하되 악성 프로세스를 통제하기 위해 OS가 제어권을 유지하는 핵심 기법
똑똑한 스케줄러(MLFQ 등): 과거의 경험을 바탕으로 짧은 작업(SJF 방식)과 대화형 작업(RR 방식)의 장점을 동시에 살리려는 지능적인 정책

12-dialogue-vm

메모리 가상화 도입 요약

1. 핵심 문제 상황

CPU 가상화 단계를 넘어 옷장 속의 진짜 큰 괴물이라 불리는 훨씬 더 복잡한 메모리 가상화 문제를 해결해야함
프로그래머가 이 변수를 어디에 저장해야 하는지 고민하지 않도록 어떻게 사용하기 쉬운 시스템과 대용량의 연속된 주소 공간을 제공할 것인가의 문제

2. 강의 도입 질문

사용자 프로그램이 생성하는 모든 주소는 실제 물리 주소인가? 아니면 OS가 만든 환상인가?
OS가 각 프로세스에게 자신만의 커다란 전용 메모리를 가진 것 같은 환상을 제공하려는 이유는 무엇인가?
잘못된 프로그램이 다른 프로그램의 메모리를 함부로 읽거나 덮어쓰지 못하게하려면 어떤 원칙이 필요한가?

3. 핵심 비유

옷장 속의 큰 괴물: 하드웨어와 OS의 상호작용이 매우 상세하고 복잡하게 얽혀 있는 메모리 가상화의 난이도를 상징함
가상 주소: 사용자 프로그램이 생성하는 모든 주소는 가상이며 OS는 하드웨어의 도움을 받아 이를 실제 물리 주소로 변환함

13-vm-intro

주소 공강의 개념 전체 요약

1. 도입 배경

해결하려는 문제: 초기의 단순한 메모리 구조를 넘어 사용자가 기대하는 사용의 편의성, 고성능, 신뢰성을 어떻게 동시에 제공할 것인가의 문제
필요성: 멀티프로그래밍과 시분할 시대가 도래하면서 여러 프로세스가 안전하게 메모리를 공유하고 대화형 응답을 보장받아야 할 필요가 생김
강의 도입 질문
- OS는 어떻게 물리 메모리를 공유하는 다수 프로세스에게 전용의 커다란 주소 공간이 있다는 환상을 줄 수 있는가?
- 사용자 프로그램이 보는 모든 주소는 실제 물리 주소인가? 아니면 OS가 만든 가상 주소인가?

2. 소주제 지도

초기 시스템의 메모리 모델
멀티프로그램과 시분할의 발전
주소 공간의 정의와 구성 요소
가상 메모리 시스템의 3대 목표
- 투명성
- 효율성
- 보호
가상 주소의 실제 사례 확인

3. 핵심 개념

개념별 정의

주소 공간(Address Space): 실행 중인 프로그램이 가정하는 메모리의 모습으로 프로그램의 코드, 스택, 힙 등 모든 메모리 상태를 포함하는 OS의 추상화 개념
가상 메모리(VM): 실제로는 물리 메모리가 공유 자원이지만 각 프로세스는 자신만의 물리 메모리를 갖는 것처럼 보이게 하는 가상화 기법
주소 변환(Address Translation): 프로세스가 생성하는 가상 주소를 하드웨어와 OS의 도움을 받아 실제 정보가 저장된 물리 주소로 매핑하는 과정

구성 요소의 관계

Code: 주소 공간 상단에 위치하는 정적인 영역
Heap: 코드 아래에서 시작해 아래 방향으로 확장되는 동적 할당 영역
Stack: 주소 공간 하단에서 시작해 위쪽 방향으로 확장되는 함수 호출 및 지역 변수 영역

4. 동작 흐름

주소 가상화의 진화

초기 시스템: 물리 주소 0부터 OS가 상주하고 그 위에 하나의 프로그램이 직접 실행되는 구조
초기 시분할 방식: 한 프로세스를 실행하다가 중단할 때 메모리 전체 내용을 디스크에 저장하고 다음 프로세스 상태를 탑재했으나 이는 메모리가 커질수록 너무 느려지는 문제가 있었음
현대적 가상화: 프로세스를 메모리에 그대로 유지하면서 하드웨어 자원을 통해 가상 주소를 물리 주소로 실시간 변환해 다수의 프로세스가 동시에 메모리에 상주할 수 있게 함

하드웨어 ←> OS 상호작용 예시

프로세스 A가 가상 주소 0에서 탑재(Load) 연산을 수행하면 하드웨어는 OS가 설정한 매핑 정보를 바탕으로 이를 실제 물리 주소로 변환해 읽어옴
프로그램에서 포인터 주소를 출력하면 이는 항상 가상 주소이며 실제 물리 위치는 오직 OS와 하드웨어만이 알고있음

5. 구조 요약

가상 메모리 시스템의 계층 구조: 사용자 프로그램(가상 주소 생성)→ 하드웨어 (주소 변환 회로)→ 물리 메모리(데이터 실제 저장)
주소 공간 3대장
- Code(상단 영역)
- Heap(아래로 확장)
- Stack(위로 확장)

6. 핵심 정리

키워드

Address Space: 프로세스가 보는 메모리 추상화
Virtual Address: 사용자 수준 프로그램이 다루는 모든 주소
Transparency: 가상화의 존재가 응용 프로그램에 보이지 않아야함
Efficiency: 시간적/공간적 오버헤드 최소화
Protection & Isolation: 프로세스 간 간섭 차단

요약

OS는 주소 공간이라는 추상화를 통해 실제 물리 메모리를 가상화해 프로세스에게 전용 메모리 환상을 제공

혼동 금지

가상 메모리의 투명성(Transparency)은 정보 공개가 아닌 사용자가 가상화 시스템의 동작을 인지하지 못하도록 숨기는 것을 의미

14-vm-api

메모리 관리 api 요약

1. 도입 배경

해결하려는 문제: Unix/C 프로그램에서 안정적인 소프트웨어를 구축하기 위해 메모리를 어떻게 효울적으로 할당하고 관리할 것인가의 문제
필요성: 프로그래머가 직접 메모리를 관리해야 하는 Heap의 특성상 발생할 수 잇는 수많은 버그와 실수를 방지하는 방법을 익혀야함
강의 도입 질문
- 함수가 리턴된 후에도 값이 유지되어야 하는 변수는 어디에 저장해야 하는가?
- free( )를 호출할 때 왜 우리는 해제할 메모리의 크기를 알려주지 않아도 되는가?

2. 소주제 지도

메모리 공간의 종류: Stack과 Heap
malloc( )과 sizeOf( )연산자의 활용
free( ) 함수와 메모리 해제
흔한 메모리 관리 오류 7가지
OS의 지원 시스템 콜
- brk
- sbrk
- mmap
기타 할당 함수
- calloc
- realloc

3. 핵심 개념

API별 상세

malloc(size_t size)
- 역할: Heap 공간에 요청한 바이트 크기만큼 메모리를 요청
- 인자: 요청할 바이트 수(통상 sizeof활용)
- 반환값: 성공 시 새로 할당된 공간의 void 포인터, 실패 시 NULL
free(void *ptr)
- 역할: 더 이상 사용되지 않는 힙 메모리를 시스템에 반환함
- 인자: malloc( )에 의해 반환되었던 포인터
- 상태변화: 할당되었던 메모리가 빈 공간 리스트로 돌아가며 이후 해당 포인터 접근 시 오류 발생 가능

개념별 정의

Stack: 컴파일러에 의해 할당과 반환이 자동으로 이루어지는 자동 메모리 영역
Heap: 할당과 반환이 프로그래머에 의해 명시적으로 처리되는 영역으로 버그의 주원인이 됨
Header: 할당된 메모리 청크 직전에 위치하며 해당 영역의 크기와 매직 넘버 등 관리 정보를 저장

4. 동작 흐름

Heap 할당 및 해제 흐름

공간 요청: 프로그래머가 malloc(sizeof(int)) 등을 호출해 공간을 요청
라이브러리 탐색: 메모리 할당 라이브러리가 Heap 내 빈 공간을 찾으며 부족할 경우 brk나 mmap 시스템 콜로 OS에게 더 많은 메모리 요구
포인터 반환: 할당된 영역의 시작 주소를 반환하며 실제 반환 주소 직전에는 크기 정보가 담긴 헤더가 생성됨
메모리 사용: 반환된 포인터를 통해 데이터를 읽고 씀
해제 요청: free( )를 호출하면 라이브러리가 포인터 연산을 통해 헤더를 찾아 크기를 파악한 뒤 공간을 반환함
성능/안정성 영향 요소
1. 시간/공간 오버헤드: sizeof는 실행시간이 아닌 컴파일 시간에 결정되므로 성능에 이점이 있음
2. 보안 취약점: 버퍼 오버플로우나 초기화되지 않은 읽기는 시스템 보안에 치명적일 수 있음

5. 구조 요약

C 프로그램 메모리 이분법: Stack(자동/단기) vs Heap(명시적/장기)
메모리 관리 계층: 사용자 프로그램 → malloc/free 라이브러리 → brk/mmap 시스템 콜 → OS
Header의 구조: Size(영역 크기) + Magic Number(무결성 검사)

6. 핵심 정리

키워드

Automatic Memory: 스택 메모리의 다른 이름
void pointer: malloc이 반환하는 타입 미지정 포인터
Memory Leak: 메모리 해제를 잊어 자원이 소진되는 현상
Dangling Pointer: 해제된 메모리를 가리키는 유효하지 않은 포인터
Double Free: 이미 해제된 메모리를 다시 해제하려는 실수
Segmentation Fault: 불법적인 메모리 접근 시 발생하는 오류
brk/sbrk: Heap의 마지막 위치(break)를 변경하는 시스템 콜

요약

Heap 메모리는 명시적으로 할당(malloc)하고 반드시 해제(free)해야 하는 프로그래머의 무거운 책임임

혼동 금지

sizeof(pointer)는 포인터 자체의 크기(4/8 Byte)를 반환하며 할당받은 배열 전체의 크기를 알려주지 않음

15-vm-mechanism

주소 변환의 원리 요약

1. 도입 배경

해결하려는 문제: 효율성(성능 저하 최소화)과 제어(프로세스가 자신의 메모리외 접근 방지)를 동시에 만족하며 어떻게 메모리를 가상화할 것인가?
필요성: 프로그램에게 전용 메모리를 소유하고 있다는 환상을 제공하면서도 실제로는 여러 프로그램이 물리 메모리를 안전하게 공유해야함
강의 도입 질문
- 프로세스가 가상 주소 0번지를 참조할 때 OS는 어떻게 이를 실제 물리 메모리의 다른 위치로 연결하는가?
- 잘못된 메모리 접근을 시도하는 프로세스를 하드웨어는 어떻게 감지하고 차단하는가?

2. 소주제 지도

주소 변환의 개념과 가성
주소 변환 사례 및 어셈블리 분석
동적 재배치(베이스와 바운드)의 원리
하드웨어 지원 및 요구사항 요약
OS의 이슈 및 책임
제한적 직접 실행(LDE) 타임라인
내부 단편화 문제

3. 핵심 개념

개념별 정의 및 하드웨어 구조

주소 변환(Address Translation): 가상 주소를 정보가 실제 존재하는 물리 주소로 하드웨어가 변환하는 기술
Base Register: 주소 공간이 탑재된 실제 물리 메모리의 시작 주소를 저장함
Bound Register: 주소 공간의 크기(한계)를 저장해 프로세스가 허용된 범위 밖을 접근하는지 검사함
MMU(Memory Management Unit): 주소 변환과 범위 검사를 수행하는 프로세서의 일부 하드웨어 구조
내부 단편화(Internal Fragmentation): 할당된 영역 내부의 빈 공간이 사용되지 않아 발생하는 낭비 현상

개념 간 관계

OS는 부팅 시 예외 핸들러를 설치하고 실행 시 하드웨어의 Base/Bound 레지스터를 설정해 주소 변환의 기반을 마련함

4. 동작 흐름

[파이프라인] 가상 주소 → 바운드 검사 → 베이스 합산 → 물리 주소

하드웨어 ←> OS 타임라인(부팅/실행 단계)

부팅 단계(커널 모드)
1. OS가 Trap 테이블을 초기화함(시스템 콜, 타이머, 불법 메모리 접근 핸들러 등)
2. OS가 빈 공간 리스트를 초기화해 메모리 관리 준비를 마침
실행 및 주소 변환 단계
1. 프로세스 시작: OS가 베이스/바운드 레지스터를 설정하고 return-from-trap으로 프로세스 실행
2. 주소 변환: 하드웨어가 명령어 반입/탑재/저장 시 가상 주소를 물리 주소로 자동 변환함
3. 범위 위반: 프로세스가 바운드를 벗어난 접근 시 하드웨어가 CPU 예외를 발생시킴
4. OS 개입: 예외 핸들러가 실행되어 위반 프로세스를 종료하고 메모리를 회수함

Context Switch 시

OS는 현재 프로세스의 베이스/바운드 값을 PCB에 저장하고 새 프로세스의 값을 하드웨어 레지스터에 복원함

5. 구조 요약

주소 변환 공식: 물리 주소 = 가상 주소 + Base Register
보호 메커니즘: 0⇐ 가상 주소 < Bound Register인지 매번 확인
OS의 3대 시점 책임
- 프로세스 생성 시 메모리 할당
- 종료 시 메모리 회수
- Context Switch시 레지스터 관리

6. 핵심 정리

키워드

Dynamic Relocation: 실행 시 주소를 재배치하는 기술
Transparency: 가상화의 존재를 프로그램이 모르게 하는 성질
Privileged Instruction: Base/Bound 설정 등 커널만 수행 가능한 명령어
Fress List: 미사용 물리 메모리 영역을 관리하는 자료 구조

요약

하드웨어의 Base/Bound Register를 이용한 주소 변환은 성능 저하 없이 메모리 고립과 보호를 실현하는 핵심 메커니즘임

혼동 금지

정적 재배치는 소프트웨어(로더)가 주소를 미리 바꾸는 방식이나 보호 기능이 없음

16-vm-segmentation

세그멘테이션 요약

1. 도입 배경

해결하려는 문제: Base-Bound 방식에서는 스택과 힙 사이의 사용하지 않는 거대한 가상 공간조차 물리 메모리를 차지하여 메모리 낭비가 심함
필요성: 32bit(4GB)와 같은 대용량 주소 공간을 지원하려면 실제 사용 중인 영역만 물리 메모리에 탑재하는 유연한 방식이 필수적임
강의 도입 질문
- Stack과 Heap 사이의 거대한 빈 공간을 어떻게 하면 물리 메모리에 할당하지 않을 수 있을까?
- 세그멘트 폴트라는 용어는 실제 어떤 하드웨어 메커니즘에서 유래되었는가?

2. 소주제 지도

세그멘테이션의 기본 개념 및 베이스/바운드 일반화
주소 변환 메커니즘(VPN 및 오프셋 파악)
Stack 세그멘트의 특수 처리(역방향 확장)
메모리 공유 및 보호 비트
소단위(Fine-grained) vs 대단위(Coarse-grained)
OS의 역할 및 외부 단편화 문제

3. 핵심 개념

개념별 정의 및 하드웨어 구조

세그멘테이션: 주소 공간을 Code, Stack, Heap 등 논리적 단위(세그멘트)로 나누고 각 세그멘트마다 독립적인 Base/Bound 쌍을 부여하는 기법
드문드문 사용되는 주소 공간(Spare Address Space): 실제 사용영역 사이에 큰 빈 공간이 존재하는 주소 공간으로 세그멘테이션을 통해 물리 메모리 낭비 없이 수용 사용함
세그멘트 레지스터: MMU 내부에 존재하며 각 세그멘트의 물리 시작 주소(Base), 크기(Bounds), 확장 방향 등을 저장함
보호 비트(Protection Bit): 세그멘트별 읽기/쓰기/실행 권한을 설정해 프로세스 간 고립을 강화함
외부 단편화(External Fragmentation): 가변 크기의 세그멘트들이 할당되고 해제되면서 물리 메모리가 작은 조각들로 나뉘어 전체 빈 공간은 충분해도 연속된 공간이 부족해 할당이 불가능해지는 현상

4. 동작 흐름

주소 변환 과정

가상 주소 → 세그멘트 선택(상위 비트) → 오프셋 추출 → 바운드 검사 → 베이스+오프셋 → 물리 주소

Stack 세그멘트 변환(역방향 확장) 단계 시퀀스

세그멘트 확인: 가상 주소 상위 비트를 통해 스택 세그멘트임을 확인
음수 오프셋 계산: 하위 비트(오프셋)에서 세그먼트의 최대 가능 크기를 빼서 음수 오프셋을 구함
물리 주소 생성: 베이스 주소(물리 끝 지점)에 음수 오프셋을 덯마
성능/안정성 영향 요소
- 외부 단편화: 가변 길이 할당의 고유 문제로 메모리 이용률을 저해함
- 압축(Compaction): 단편화 해결을 위해 세그멘트를 복사해 모으는 작업이나 CPU 시간을 많이 소모하는 고비용 연산임

5. 구조 요약

세그멘테이션 핵심: 논리적 의미 단위로 쪼개어 따로 배치하자
구성 요소 및 단계
1. 가상 주소 분할: Segment Select(ex.2bit) + Offset(ex.12bit)
2. 하드웨어 테이블(MMU): 세그멘트별 Base, Bounds, Grow Positive
3. 공유 자원: 동일 물리 코드를 여러 AS에 읽기 전용으로 매핑
4. OS 역할: Context Switch시 레지스터 저장/복원, 빈 공간 관리(Free List)

6. 핵심 정리

키워드

Segment: 논리적인 연속 주소 공간 단위
Base/Bound 일반화: 단일 레지스터 쌍을 여러 개로 확장한 개념
Explicit Approach: 주소 비트 일부를 세그멘트 선택에 사용
Implicit Approach: 주소 생성 방식(Program Counterm, SP 등)으로 세그멘트 판단
Coarese-grained: 소수의 큰 세그멘트로 관리
External Fragmentation: 가변 크기 할당으로 인한 물리 메모리 조각화

요약

세그멘테이션은 주소 공간을 논리적 단위로 나누어 물리 메모리에 분산 배치함으로써 낭비를 줄이지만 외부 단편화라는 숙제를 남김

혼동 금지

내부 단편화는 할당 영역 내부의 낭비(베이스-바운드 특징)임 외부 단편화는 할당 영역 사이 빈 공간의 조각화임

17-vm-freespace

빈 공간 관리 요약

1. 도입 배경

해결하려는 문제: 관리 공간이 가변 크기의 빈 조각들로 구성될 때 발생하는 외부 단편화 문제를 어떻게 해결할 것인가?
필요성: 전체 빈 공간이 요청보다 크더라도 연속된 영역이 없으면 할당이 실패하므로 효율적인 공간 활용과 오버헤드 최소화가 필수적임
강의 도입 질문
- free(ptr)를 호출할 때 사용자는 왜 해제할 메모리의 크기를 알려주지 않아도 되는가?
- 메모리를 조각내지 않으면서도 다양한 크기의 요청을 신속하게 처리하는 마법 같은 전략이 있을까?

2. 소주제 지도

기본 가정 및 malloc/free 인터페이스
저수준 기법: 분할(Splitting)과 병합(Coalescing)
할당 크기 추적: Header의 구조
빈 공간 리스트의 내장 및 Heap의 확장
고급 접근법: 개별 리스트, 슬랩 할당, 버디 할당

3. 핵심 개념

API별 역할

malloc(size_t size): 요청한 바이트 이상의 공간을 찾아 void 포인터로 반환하며 내부적으로는 헤더 크기만큼 더 큰 공간을 할당함
free(void *ptr): 전달된 포인터 직전의 헤더를 찾아 크기를 파악한 후 해당 영역을 빈 공간 리스트에 반환함

개념별 정의

분할(Splitting): 요청을 만족하는 빈 청크를 찾아 이를 할당할 부분과 남은 빈 부분으로 나누는 기법임
병합(Coalescing): 인접한 빈 공간들을 하나의 큰 청크로 합쳐 단편화를 방지하는 기법
Header: 할당된 청크 직전에 위치하며 크기와 매직 넘버(무결성 검사용)를 저장하는 자료 구조
외부 단편화(External Fragmentation): 빈 공간은 충분하나 작게 조각나 있어 큰 요청을 충족하지 못하는 현상

4. 동작 흐름

파이프 라인

요청(size) → 리스트 탐색 → 분할/할당 → 포인터 반환

메모리 할당 및 해제 단계 시퀀스

할당 요청: malloc(100)호출 시 헤더(8바이트)를 포함한 108바이트의 빈 공간을 리스트에서 탐색함
분할: 적합한 청크(ex. 4088Byte)를 찾으면 108 바이트는 할당하고 남은 3980 바이트는 새로운 빈 노드로 관리함
해제 요청: free(ptr) 호출 시 ptr - sizeof(header) 연산으로 헤더를 찾아 해제할 크기를 파악함
리스트 삽입: 해제된 청크를 빈 공간 리스트에 추가함
병합: 리스트 순회 중 인접한 빈 청크가 발견되면 하나로 합침
성능/안정성 영향 요소
- 탐색 비용: 리스트가 길어질수록 최적/최악 적합 전략은 전체 탐색으로 인해 성능이 저하됨
- 매직 넘버: 헤더의 매직 넘버가 기대치와 다르면 프로그래머의 잘못된 해제 시도를 감지해 오류를 발생시킴

5. 구조 요약

빈 공간 관리의 계층: 응용 프로그램 ←> malloc 라이브러리(리스트 관리) ←> OS(sbrk/mmap으로 힙 확장)
메모리 할당 전량 4가지
- 최적(Best): 요청과 가장 비슷한 크기 선택(공간 절약, 탐색 느림)
- 최악(Worst): 가장 큰 청크 선택(큰 빈 공간 유지 시도, 탐색 느림)
- 최초(First): 첫 번째 적합 청크 선택(탐색 빠름, 앞부분 단편화 위험)
- 다음(Next): 마지막 탐색 지점부터 시작(전체 균등 분산)

6. 핵심 정리

키워드

Internal Fragmentation(내부 단편화): 할당된 청크 내부의 미사용 공간
External Fragmentation(외부 단편화): 할당된 청크들 사이의 미사용 공간
Free List: 힙 내 빈 청크들의 주소와 크기를 관리하는 리스트
Slab Allocator: 자주 사용되는 커널 객체 전용의 빈 공간 리스트
Binary Buddy: 2의 거듭제고 크기로 분합/병합해 관리를 단순화하는 할당기

요약

빈 공간 관리는 헤더를 통해 할당 크기를 추적하고 분할과 병합 기법을 사용해 외부 단편화를 최소화하며 가변 크기 요청을 처리함

혼동 금지

내부 단편화는 요청보다 큰 블럭을 할당했을 때 내부에서 남는 공간(버디 할당)이고 외부 단편화는 블럭들 사이에 흩어진 빈 공간임

18-vm-paging

페이징의 원리 요약

1. 도입 배경

해결하려는 문제: 세그멘테이션처럼 가변 크기로 분할할 때 발생하는 외부 단편화 문제를 해결하고 공간 관리의 유연성을 확보함
필요성: 주소 공간의 사용 방식(Heap/Stack 확장 방향 등)에 대한 가정 없이도 효율적인 가상화를 지원하기 위함
강의 도입 질문
- 가변 크기 분할의 고질병인 외부 단편화를 근본적으로 없애려면 공간을 어떻게 나누어야 하는가?
- OS는 물리 메모리에 흩어져 있는 조각들을 어떻게 하나의 연속된 가상 주소 공간으로 묶어 보여주는가?

2. 소주제 지도

페이징의 기본 개념 및 페이지/프레임 정의
주소 변환 메커니즘: VPN과 오프셋
페이지 테이블의 저장 위치와 크기 문제
페이지 테이블 항목(PTE)의 구성 비트
페이징의 오버헤드: 속도 저하 문제
실제 메모리 트레이스 분석

3. 핵심 개념

개념별 정의 및 하드웨어 구조

Page: 프로세스의 주소 공간을 고정 크기 단위로 나눈것
Page Frame: 물리 메모리를 페이지와 동일한 고정 크기로 나눈 슬롯
Page Table: 프로세스마다 존재하며 가상 페이지 주소를 물리 프레임 주소로 매핑하는 자료 구조
VPN(Virtual Page Number): 가상 주소 중 페이지를 식별하는 상위 비트 부분
Offset: 페이지 내에서 실제 데이터의 위치를 나타내는 하위 비트 부분
PTE 비트들
- Valid bit: 해당 변환이 유효한지(할당된 영역인지) 표시
- Protection bit: 읽기/쓰기/실행 권한 표시
- Present bit: 페이지가 실제 메모리에 있는지 디스크에 있는지 표시
- Dirty bit: 메모리에 반입된 후 수정되었는지 표시
- Reference bit: 페이지가 최근에 접근되었는지 추적

4. 동작 흐름

파이프라인

가상 주소 → VPN/Offset 분할 → PTE 탐색 → PFN 결합 → 물리 주소

하드웨어 ←> OS 타임라인(실행 단계)

주소 생성: 프로세스가 가장 주소를 생성함
VPN 추출: 하드웨어가 VPN_MASK와 SHIFT 연산을 통해 VPN을 추출함
PTE 주소 계산: 페이지 테이블 베이스 레지스터(PTBR)와 VPN을 이용해 원하는 PTE의 메모리 주소를 찾음
PTE 반입: 하드웨어가 실제 물리 메모리에서 PTE를 읽어옴(추가 메모리 참조 발생)
권한 및 유효성 검사: Valid/Protection 비트를 확인해 위반 시 예외 발생
물리 주소 구서: PFN을 SHIFT 연산 후 원래 오프셋과 OR 연산해 결합함
데이터 접근: 최종 물리 주소를 통해 메모리에서 실제 데이터를 탑재함
성능 영향 요소: 모든 메모리 참조 시 페이지 테이블 접근을 위한 추가적인 메모리 읽기가 필요해 프로세스 속도가 2배 이상 느려질 수 있음

5. 구조 요약

페이징 핵심: 가변 크기를 버리고 고정 크기를 택해 외부 단편화를 제거하자
구성 요소 7단계
1. 가상 주소 분할: VPN + Offset
2. PTBR: 메모리 내 페이지 테이블 시작 주소 보관
3. 인덱싱: VPN으로 PTE 위치 파악
4. PTE 확인: PFN 확보 및 상태 비트 검사
5. 변환: VPN을 PFN으로 교체
6. 물리 주소 형성: PFN + Offset
7. 실제 접근: 물리 주소의 데이터 로드

6. 핵심 정리

키워드

Paging: 고정 크기 분할 기법
Page Frame: 물리 메모리의 고정 슬롯
VPN: 가상 주소의 페이지 번호 부분
PFN: 물리 메모리의 프레임 번호
PTBR: 페이지 테이블 위치를 저장하는 레지스터
Internal Fragmentation: 고정 크기 할당으로 인해 페이지 내부가 낭비되는 현상
AMAT: 평균 메모리 접근 시간 계산 지표

요약

페이징은 주소 공간을 고정 크기 페이지로 나누어 물리 메모리에 분산 배치함으로써 외부 단편화를 해결하는 메커니즘임

혼동 금지

오프셋은 주소 변환 과정에서 변하지 않고 그대로 유지됨(페이지 내 위치는 동일하기 때문)

19-vm-tlbs

페이징: 더 빠른 변환(TLB) 요약

1. 도입 배경

해결하려는 문제: 페이징은 주소 변환을 위해 메모리에 있는 페이지 테이블을 읽어야 하므로 모든 메모리 참조 시 추가적인 메모리 읽기가 발생해 성능이 심각하게 저하됨
필요성: 가상 메모리 참조 시 페이지 테이블을 거치지 않고 빠르게 주소 변환을 수행할 하드웨어 지원이 필수적임
강의 도입 질문
- 모든 명령어 실행 시마다 발생하는 추가적인 메모리 참조를 어떻게 피할수 있는가?
- OS는 하드웨어와 어떤 식으로 협력해 주소 변환 속도를 높이는가?

2. 소주제 지도

TLB의 정의와 기본 알고리즘
배열 접근을 통한 TLB 성능 분석
하드웨어 관리혀(CISC) vs 소프트웨어 관리형(RISC) TLB 미스 처리
TLB의 하드웨어 구성 요소
문맥 교환 시의 TLB 관리(Flush 및 ASID)
TLB 교체 정책 및 실제 사례(MIPS R4000)

3. 핵심 개념

개념별 정의 및 하드웨어 구조

TLB(Translation-lookaside Buffer): 칩의 메모리 관리부(MMU)의 일부로 자주 참조되는 가상 주소-실주소 변환 정보를 저장하는 하드웨어 캐시
TLB Hit: 하드웨어가 TLB에서 원하는 가상 페이지 번호(VPN)를 찾아 페이지 테이블을 통하지 않고 빠르게 변환을 수행하는 상태
TLB Miss: TLB에 변환 정보가 없어 페이지 테이블에 접근해 정보를 가져와야 하는 상태 → 성능 저하 유발
ASID(Address Space Identifier): 문맥 교환 시 프로세스를 구분하기 위해 TLB 항목에 추가된 식별자로 서로 다른 프로세스가 TLB 공간을 공유할 수 있게함
완전 연관(Fully Associative): 변환 정보가 TLB 내 어디든 위치할 수 있으며 하드웨어가 전체 항목을 동시에 병렬 검색하는 방식

개념 간 관계

프로그램의 지역성(공간적/시간적)이 높을수록 TLB 히트율이 올라가 AMAT(평균 메모리 접근 시간)이 단축됨

4. 동작 흐름

파이프 라인

가상주소 → VPN 추출 → TLB 검색 → (히트 시) 물리 주소 구성/(미스 시) 페이지 테이블 참조 → TLB 갱신 → 명령어 재실행

단계 시퀀스: 소프트웨어 관리형 TLB 미스 처리(RISC)

miss 발생: 하드웨어가 TLB에서 주소를 찾는 데 실패하면 exception을 발생시킴
trap 발생: 실행 모드를 커널 모드로 변경하고 OS의 트랩 핸들러로 제어권을 넘김
페이지 테이블 검색: trap 핸들러(OS 코드)가 페이지 테이블에서 변환 정보를 찾음
TLB 갱신: 특권 명령어를 사용해 해당 정보를 TLB에 삽입함
리턴 및 재실행: 트랩 핸들러가 종료되면 하드웨어 미스를 발생시켰던 명령어를 다시 실행해 TLB 히트를 유도함
상태/데이터 구조 변화: context Switch시 모든 항목의 Valid bit를 0으로 설정(Flush)하거나 ASID 레지스터를 새 프로세스 값으로 갱신함
성능 영향 요소: TLB 미스 시 페이지 테이블 접근을 위한 추가 메모리 참조가 발생하며 미스 처리 핸들러 자체의 위치나 방식에 따라 오버헤드가 달라짐

5. 구조 요약

TLB의 역할: 페이징의 성능 문제를 해결하는 주소 변환 캐시
동작 방식 3단계
1. TLB 확인(히트 시 즉시 변환)
2. 미스 시 페이지 테이블 접근(하드웨어 또는 OS 핸들러)
3. TLB 갱신 후 명령어 재실행
주요 필드
- VPN
- PFN
- Valid
- Prot
- ASID

핵심 정리

키워드

TLB: 주소 변환 정보를 담는 MMU 내 하드웨어 캐시
Spatial Locality: 인접한 주소의 데이터가 곧 접근될 성질
Temporal Locality: 최근 접근된 데이터가 곧 다시 접근될 성질
Flush: Context Switch시 TLB의 모든 유효 비트를 0으로 만드는 작업
ASID: 프로세스별 주소 공간 식별 번호
LRU: 가장 오래저에 사용된 항목을 교체하는 정책
Wired: TLB 미스 핸들러 등을 위해 예약된 영구 매핑 영역

요약

TLB는 하드웨어 캐싱 기술을 통해 페이지 테이블 접근 횟수를 획기적으로 줄여 페이징 시스템을 실용적으로 만듬

혼동 금지

TLB Valid bit vs 페이지 테이블 Valid bit

TLB Vallid bit는 해당 변환 정보를 캐시에 있느냐를 나타냄 페이지 테이블 Valid bit는 해당 페이지가 주소 공간에 할당되었느냐를 나타냄

CISC vs RISC

미스 처리를 하드웨어가 전담하느냐(CISC OS 핸들러가 전담하느냐(RISC)의 차이

20-vm-smalltables

페이징: 더 작은 테이블 요약

1. 도입 배경

해결하려는 문제: 선형 페이지 테이블은 주소 공간의 상당 부분이 사용되지 않더라도 모든 항목을 메모리에 유지해야 하므로 메모리 낭비가 매우 심함
필요성: 32bit 주소 공간에서 프로세스당 약 4MB의 페이지 테이블이 필요한데 프로세스가 100개만 있어도 400MB를 주소 변환에만 쓰게 되는 부담을 해결해야함
강의 도입 질문
- 실제로는 몇 페이지만 사용하는 프로세스에게 왜 수백만 개의 페이지 테이블 항목이 필요한가?
- 어떻게 하면 사용하지 않는 주소 공간에 대한 변환 정보를 메모리에서 완전히 제거할 수 있을까?

2. 소주제 지도

대형 페이지를 통한 크기 감소의 한계
하이브리드 접근법: 페이징과 세그멘테이션의 결합
멀티 레벨 페이지 테이블(가장 중요한 현대적 해법)
역 페이지 테이블 및 기타 자료 구조
페이지 테이블의 디스크 스와핑

3. 핵심 개념

개념별 정의 및 하드웨어 구조

Multi-level Page Table: 선형 페이지 테이블을 트리 구조로 표현하며 유효하지 않은 항목만 있는 페이지 테이블 페이지는 아예 할당하지 않는 기법임
Page Directory: 페이지 테이블을 구성하는 각 페이지의 할당 여부와 위치 정보를 관리하는 상위 수준의 자료구조
PDE(Page Directory Entry): 페이지 디렉터리의 항목으로 유효 비트와 해당 페이지 테이블 페이지의 물리 프레임 번호(PFN)를 포함함
하이브리드 방식: 세그멘트마다 별도의 페이지 테이블을 두어 스택과 힙 사이의 빈 공간에 대한 낭비를 줄임
역 페이지 테이블(Inverted Page Table): 시스템에 단 하나의 페이지 테이블만 두며 물리 페이지가 어떤 가상 주소에 매핑되어 있는지 저장함

4. 동작 흐름

파이프라인

가상 주소 → PDIndex 추출 → PDE 확인 → PTIndex 추출 → PTE 확인 → 물리 주소

단계 시퀀스: 2단계 페이지 테이블 주소 변환

VPN 분할: VPN의 상위 비트를 PDIndex(페이지 디렉터리 인덱스)로 하위 비트를 PTIndex(페이지 테이블 인덱스)로 나눔
PDE 검색: PDEAddr = PageDirBase + (PDIndex * sizeof(PDE))공식을 통해 PDE를 읽음
PDE 유효성 검사: PDE의 유효 비트가 0이면 즉시 예외 발생 1이면 해당 PFN을 통해 페이지 테이블 페이지를 찾음
PTE 검색: PTEAddr = (PDE.PFN << SHIFT) + (PTIndex * sizeof(PTE)) 공식을 통해 실제 PTE를 읽음
물리 주소 구성: PTE에서 얻은 PFN과 원래 가상 주소의 오프셋을 결합함
성능 영향 요소(TIme-Space Trade-off)
- 공간: 사용되지 않는 페이지 테이블 페이지를 할당하지 않아 메모리를 획기적으로 절약함
- 시간: TLB 미스 시 주소 변환을 위해 메모리를 두번(PD 접근 + PT 접근) 읽어야 하므로 선형 테이블보다 느려짐

5. 구조 요약

멀티 레벨 테이블의 핵심: 빈 공간은 기록조차 하지 말자(Sparse Address Space 지원)
주요 구성 단계
1. 페이지 테이블을 페이지 단위로 쪼개기
2. 쪼개진 페이지가 전부 비어있으면 메모리 할당 취소
3. 페이지 디렉터리를 두어 할당된 페이지들의 위치만 관리
장점: 사용량에 비례한 메모리 사용, 페이지 단위 할당으로 인한 관리의 유연성

6. 핵심 정리

키워드

Internal Fagmentation: 대형 페이지 사용 시 페이지 내부 공간이 낭비되는 현상
Page Directory: 페이지 테이블의 목차 역할
PDE/PTE: 각각 목차 항목과 실제 주소 변환 항목
Sparse Address Space: 중간중간 비어있는 주소 공간
Multi-level Hierarchy: 2단계를 넘어 3단계, 4단계로 확장 가능함

요약

멀티 레벨 페이지 테이블은 페이지 디렉터리를 도입해 실제 사용 중인 주소 공간에 대해서만 페이지 테이블을 할당함으로써 메모리 효율을 극대화함

혼동 금지

PDE 유효 비트가 0이면 해당 영역의 모든 페이지가 할당되지 않은것 PTE 유효 비트가 0이면 그 특정 가상 페이지만 항당되지 않은 것임

21-vm-beyondphys

물리 메모리 크기의 극복: 메커니즘 요약

1. 도입 배경

해결하려는 문제: 실제 물리 메모리는 한정되어 있으나 다수의 프로세스가 동시에 실행되면서 각자 큰 가상 주소 공간을 요구하는 상황을 어떻게 해결할 것인가?
필요성: 프로그래머가 메모리 용량 부족을 걱정하지 않고 편리하게 개발할 수 있도록 무한한 메모리라는 환상을 제공해야함(과거의 수동적인 메모리 오버레이 방식 탈피)
강의 도입 질문
- 프로세스가 실제 물리 메모리보다 더 큰 메모리를 사용하려고 할 때 OS는 무엇을 숨기고 있는가?
- 메모리에 없는 페이지를 읽으려 할 때 하드웨어와 OS는 어떻게 협력하는가?

2. 소주제 지도

Swap Space의 개념과 역할
Present Bit를 이용한 페이지 존재 여부 판별
Page Fault 발생 및 처리 메커니즘
하드웨어 및 소프트웨어의 상세 제어 흐름
교체 시점 결정: 워터마크와 페이지 데몬

3. 핵심 개념

개념별 정의 및 하드웨어 구조

Swap Space: 메모리에서 쫓겨난 페이지들을 보관하기 위해 확보된 디스크 상의 일정 곤간
Present Bit: 각 페이지 테이블 항목(PTE)에 포함된 비트로 해당 페이지가 실제 물리 메모리에 있는지(1) 아니면 디스크로 스왑 아웃 되었는지(0)를 나타냄
Page Fault: 가상 메모리 참조 시 해당 페이지의 Present Bit가 0일때 발생하는 예외 상황
Page-fault Handler: 페이지 폴트 발생 시 OS가 실행하는 특수 코드로 디스크에서 페이지를 읽어 메모리에 탑재함
Watermark: 여유 메모리 공간을 일정 수준 유지하기 위해 설정된 최댓값(HW)과 최솟값(LW) 지표

개념 간 관계

하드웨어가 Present Bit를 검사해 부재를 감지하면(페이지 폴트), OS가 스왑 공간에서 데이터를 가져오고 PTE를 갱신

4. 동작 흐름

하드웨어 ←> OS 타임라인

가상 주소 생성: 프로세스가 메모리 참조 명령 실행
TLB 검사(하드웨어)
- TLB Hit: 물리 주소로 즉시 변환 및 메모리 접근
- TLB Miss: 페이지 테이블 검색 진행
PTE 검사 및 변환(하드웨어)
- Present Bit = 1: PFN을 추출해 TLB에 탑재 후 명령어 재실행
- Present Bit = 0: 페이지 폴트 예외 발생 및 OS로 제어권 전환
페이지 폴트 처리(OS)
- 여유 프레임 확보: 메모리에 빈 공간이 없으면 교체 알고리즘(EvictPage)을 실행해 페이지를 내보냄
- DiskRead: PTE의 디스크 주소 정보를 이용해 스왑 공간에서 페이지를 읽어옴
- PTE 갱신: 읽어온 페이지의 PFN을 기록하고 Present Bit를 1로 설정
명령어 재실행: 폴트를 일으킨 명령어를 다시 실행해 TLB Hit를 유도
성능/안정성 영향 요소: 페이지 폴트 발생 시 디스크 I/O가 수반되므로 시스템 속도가 1만 배 이상 느려질 수 있음

5. 구조 요약

메모리 계층의 확장: 레지스터 → 캐시 → 물리 메모리 → 디스크(스왑 공간)
OS의 역할
1. 페이지 위치 관리(PTE 내 디스크 주소 저장)
2. 스왑 인/아웃 제어(I/O 작업 중 프로세스 차단)
3. 여유 공간 확보(페이지 데몬 실행)
성능 최적화: 다수의 페이지를 묶어 한 번에 처리하는 클러스터링 기법 활용

6. 핵심 정리

키워드

Swap Space: 페이지 보관용 디스크 영역
Present Bit: 메모리 상주 여부 표시 비트
Page Fault: 부재 페이지 접근 시 하드웨어 예외
Page-fault Handler: 페이지 부재를 처리하는 OS 소프트웨어
Swap Daemon(Page Daemon): 여유 공간 확보를 위해 백그라운드에서 동작하는 쓰레드
High/Low Watermarks: 페이지 교체를 시작/중단하는 기준점

요약

OS는 Present Bit를 통한 하드웨어 예외(페이지 폴트)와 스왑 공간이라는 소프트웨어적 관리를 통해 물리적 한계를 넘는 가상 메모리를 구현한다

혼동 금지

페이지 폴트는 불법 접근이 아니라 단지 메모리에 데이터가 없어 디스크에서 가져와야 하는 정상적인 미스 상황을 의미

22-vm-beyondphys-policy

물리 메모리 크기 극복: 정책 통합 요약

1. 도입 배경

해결하려는 문제: 물리 메모리가 가득 찼을 때 OS는 어떤 기준(정책)으로 페이지를 내보내야 시스템 성능 저하를 최소화할 수 있는가?
필요성: 디스크 I/O는 메모리 접근보다 월등히 느리므로(ex. 10만 배) 미스율을 조금만 줄여도 전체 AMAT 성능을 크게 개선할 수 있음
강의 도입 질문
- 미래의 접근 패턴을 안다면 어떤 페이지를 버리는 것이 가장 완벽한가?
- 과거의 사용 이력이 미래를 예측하는 데 도움이 될까?

2. 소주제 지도

캐시 관리 지표(AMAT)
기본 정책: Optimal, FIFO, Random
과거 정보 활용: LRU, LFU
워크로드 분석: 80/20, 순환형
LRU 근사 구현: Clock 알고리즘
기타 고려사항: Dirty 페이징, 쓰레싱

3. 핵심 개념

평균 메모리 접근 시간(AMAT): 캐시 시스템의 성능을 측정하는 지표임
- 수식: $A M A T = (P_{H i t} * T_{M}) + (P_{M i ss} * T_{D})$
- 항의 의미
  - $P_{H i t}$ (히트 확률)
  - $T_{M}$ (메모리 접근 시간)
  - $P_{M i ss}$ (미스 확률)
  - $T_{D}$ (디스크 접근 시간)
최적 교체 정책(Optimal/MIN): 가장 나중에 접근될 페이지를 교체하여 미스를 최소화함 현실적으로 구현 불가능하나 비교 기주으로 사용됨
FIFO(First-In First-Out): 먼저 들어온 페이지를 먼저 내보냄. 구현이 단순하지만 페이지의 중요도를 판단하지 못함
무작위 선택(Random): 메모리 압박 시 무작위로 페이지를 선택함. 성능이 운에 좌우됨
LRU(Least Recently Used): 가장 오래전에 사용된 페이지를 교체함. 과거의 최근성 정보를 활용함
LFU(Least Frequently Used): 가장 적은 빈도로 사용된 페이지를 교체함
시계 알고리즘(Clock): 하드웨어의 use bit(또는 reference bit)를 사용하여 LRU를 근사함. 시계 바늘이 돌며 1이면 0으로 바꾸고 통과, 0이면 교체 대상으로 선정

4. 동작 흐름

AMAT 계산 예제

조건: $P_{H i t} = 0.9$ , $T_{M} = 100 n s$ , $T_{D} = 10 m s$
계산: $(0.9 * 100 n s) + (0.1 * 10000000 n s) = 90 n s + 1000000 n s = 1.00009 m s$
결과: 미스율 10%만으로도 AMAT가 약 1 $μ s$ 로 증가해 성능이 크게 저하됨

참조 스트림(0,1,2,0,1,3,0,3,1,2,1) 기반 정책 재현

Optimal(캐시 크기 3): 페이지 3 참조 시 가장 미래에 쓰일 2를 제거함
FIFO(캐시 크기 3): 페이지 3 참조 시 가장 먼저 들어온 0을 제거함 이후 재참조 시 또 미스 발생
LRU(캐시 크기 3): 페이지 3 참조 시 가장 오래전(T=2)에 쓰인 2를 제거

워크로드별 성능 양상

순차 반복(0~49 반복): 캐시 크기가 49일때 LRU/FIFO의 히트율은 0%임

5. 구조 요약

평가 지표: 히트율 극대화 → AMAT 최소화
정책의 진화: 단순 구조(FIFO) → 과거 이력(LRU) → 현실적 근사(Clock)
하드웨어 지원: Use bit(참조 여부), Dirty bit(변경 여부/Drity 페이지 교체 시 디스크 쓰기 비용 발생으로 기피됨)
Thrashing: 가용 메모리보다 요구량이 많아 시스템이 페이징 작업만 반복하는 마비 상태

6. 핵심 정리

키워드

AMAT: 평균 메모리 접근 시간
Optimal(MIN): 미래를 아는 최적 정책
Belady’s Locality: 최근 참조된 것이 다시 참조될 경향
Temporal Locality: 최근 참조된 것이 다시 참조될 경향
Spatial Locality: 인접 주소가 참조될 경향
Stack Property: 캐시 크기 $N + 1$ 이 $N$ 의 내용을 포함하는 성질(LRU 등)
Dirty bit: 페이징 수정 여부 표시
Thrashing: 과도한 페이징으로 인한 시스템 마비

요약

페이지 교체 정책은 과거 사용 기록(지역성)을 활용해 미래를 예측함으로써 매우 느린 디스크 I/O 횟수를 최소화하는 것을 목표로함

혼동 금지

FIFO vs LRU

FIFO는 메모리 진입 시점 기준 LRU는 마지막 사용 시점 기준

Valid bit vs Use bit

Valid bit는 주소 공간 할당 여부 Use bit는 최근 참조 여부

23-vm-vax

VAX/VMS 가상 메모리 시스템 요약

1. 도입 배경

해결하려는 문제: 다양한 사양의 기계에서 실행되어야 하는 범용 OS가 어떻게 하드웨어의 결함(작은 페이지 크기 등)을 소프트웨어로 보완해 효율적인 가상 메모리를 제공할 것인가?
필요성: VAX-11 하드웨어는 페이지 크기가 512 바이트로 매우 작아 페이지 테이블이 비대해지는 문제가 있었음, 하드웨어적 reference bit가 부족해 정교한 교체 정책 구현에 제약이 있었음
강의 도입 질문
- OS는 하드웨어가 제공하지 않는 기능(ex. reference bit)을 어떻게 소프트웨어로 에뮬레이트할 수 있는가?
- Null Pointer 역참조 시 발생하는 세그멘테이션 오류는 실제 하드웨어 주소 공간의 어떤 설계 때문인가?

2. 소주제 지도

VAX-11 메모리 관리 하드웨어 구조: P0, P1, S공간
VMS 주소 공간 구성 및 null pointer 보호
페이지 교체 정책: 세그멘트된 FIFO및 Second-chance 리스트
고급 최적화 기법: Demand Zeroing, Copy-on-Write

3. 핵심 개념 정리

개념별 정의 및 하드웨어 구조

P0/P1/S 공간: 주소 공간을 하위 절반(사용자 프로세스 공간 P0/P1)과 상위 절반(시스템 공간 S)으로 나눈 하이브리드 구조
커널 가상 메모리 내 페이지 테이블: 사용자 페이지 테이블을 시스템 가상 메모리(S 공간)에 배치해 메모리 압박을 줄이고 페이지 테이블 자체를 스왑할 수 있게함
세그멘트된 FIFO: 프로세스별로 상주 집합 크기(RSS)를 제한하고 내부적으로 FIFO 교체를 수행해 메모리 독점(Memory Hog)을 방지
Second-chance 리스트 (Clean/Dirty): FIFO에서 쫓겨난 페이지를 즉시 제거하지 않고 전역 리스트에 보관해 재사용 기회를 주는 기법
Demand Zeroing: 페이지 할당 즉시 0으로 채우지 않고 실제 접근 시 Trap을 통해 0으로 초기화된 물리 페이지를 매핑하는 Lazy 방식
Copy-on-Write(COW): 페이지 복사 시 즉시 복사하지 않고 읽기 전용으로 공유하다가 쓰기 발생시에만 실제 복사본을 만드는 최적화 기법

4. 동작 흐름

하드웨어 ←> OS 타임라인

주소 변환 단계(실행 시)
1. 프로세스가 가상 주소 생성(P0 또는 P1)
2. 하드웨어가 해당 세그멘트의 페이지 테이블 주소를 시스템 공간(S)에서 참조
3. 하드웨어 TLB가 변환 정보를 검색하며 미스 시 시스템 페이지 테이블(물리 메모리 상주)을 거쳐 2단계 변환 수행
Context Switch 단계
1. OS가 현재 프로세스의 P0, P1 베이스/바운드 레지스터를 저장함
2. 새 프로세스의 P0, P1 정보를 레지스터에 복원
3. 주의: 시스템 공간(S) 레지스터는 변경하지 않아 모든 프로세스가 커널을 공유함
페이지 교체 단계
1. 프로세스가 RSS 제한을 초과해 FIFO에 의해 페이지 추출
2. 추출된 페이지가 Clean이면 전역 클린 리스트로, Dirty면 전역 더티 리스트로 이동
3. 페이지 폴트 발생 시 전역 리스트에서 해당 페이지를 찾아 즉시 회수(Soft Miss)하거나 디스크에서 읽음
성능/안정성 영향 요소
- 작은 페이지 크기(512GB)로 인한 I/O 비효율을 해결하기 위해 여러 페이지를 묶어 쓰는 클러스터링을 적용

5. 구조 요약

VAX VM 구조
- 사용자 P0(Heap) + 사용자 P1(Stack) + 시스템 S(kernel)
- 널 포인터 보호: 페이지 0을 접근 불가능으로 설정해 버그 검출
- 교체 정책 핵심:
  - (1) 프로세스별 RSS 제한
  - (2) 전역 Second-chance 리스트 활용

6. 핵심 정리

키워드

Hybird Paging/Segmentation: VAX-11의 기본 주소 변환 방식
System Space (S): 모든 프로세스가 공유하는 커널 영역
Rss(Resident Set Size): 프로세스가 메모리에 가질 수 있는 최대 페이지 수
Second-chance List: 쫓겨난 페이지에게 주는 재사용 기회 리스트
Clustering: 디스크 I/O 효율을 위해 페이지를 묶어서 처리하는 것
Demand Zeroing: 보안과 효율을 위해 접근 시점에 페이지를 0으로 초기화
COW: 쓰기 발생 전까지 페이지 복사를 미루는 기법

요약

VAX/VMS는 하이브리드 주소 공간 설계와 Second-chance 리스트 기반의 효율적 교체 정책을 통해 하드웨어의 물리적 제약을 소프트웨어적으로 극복한 시스템임

혼동 금지

VAX 하드웨어는 reference bit가 없으므로 OS가 protection bit를 조절해 이를 에뮬레이트해야함

24-vm-dialogue

메모리 가상화 정리

1. 핵심 문제 상황

방대한 메모리 가상화 지식을 단순히 시험용으로 암기하는 것이 아닌 실제 현장에서 시스템이 예상과 다르게 동작할 때 (ex. 예상보다 느린 메모리 접근 속도) 이를 진단하고 해결할 수 있는 개념적 모델을 어떻게 구축할 것인가의 문제

2. 강의 도입 질문

모든 데이터가 하드웨어 캐시에 들어감에도 불구하고 메모리 접근이 예상보다 느리다면 무엇을 의심해야하는가?
가상 메모리를 실제적으로 가능하게 만드는 가장 핵심적인 하드웨어 장치는 무엇인가?
프로그래머가 프로그램 내에서 출력하는 주소값이 실제 데이터가 저장된 물리 주소가 아니라는 사실이 왜 중요한가?

3. 핵심 비유

가상 주소의 환상: 프로그램 내의 주소는 실제 물리 위치가 아닌 OS가 프로그래머에게 심어준 환상일 뿐이며 이를 통해 시스템은 정보를 보호하고 가상화를 구현함
TLB(주소 변환 캐시): 가상 메모리 시스템이 심각하게 느려지는 것을 방지해 가상 메모리를 실제적으로 가능하게 만드는 시스템의 핵심 보조 장치

Quartz 4

Explorer

OSTP 1(virtualization(가상화))

01-dialogue-threeeasy

1. 핵심 문제 상황

2. 강의 도입 질문

3. 핵심 비유

4. 이후 어떤 개념을 공부하는가

02-intro

1. 도입 배경

2. 소주제

3. 핵심 개념 정리

API별 역할 및 특징(C언어)

개념별 정의

개념 간 관계

4. 동작 흐름

System Call(영속성)

성능/안정성 영향 요소

5. 구조 요약

6. 키워드

정리

혼동 금지

커널 모드 vs 사용자 모드

Mechanism vs Policy

03-dialogue-virtualization

1. 핵심 문제 상황

2. 강의 도입 질문

3. 핵심 비유

04-cpu-intro

1. 도입 배경

2. 소주제 지도

3. 핵심 개념

개념간의 관계

4. 동작 흐름

프로그램에서 프로세스로의 변환

하드웨어 ←> OS 상태 전이 메커니즘

5. 구조 요약

OS의 CPU 가상화 전략

프로세스 구성

6. 핵심 포인트

키워드

요약

혼동 금지

준비 vs 대기

05-cpu-api

1. 도입 배경

2. 소주제 지도

3. 핵심 개념

1. fork( )

2. wait( )

3. exec( ) 계열(execvp 등)

개념간 관계

4. 동작 흐름

입출력 재지정 과정

5. 구조 요약

6. 핵심 포인트

키워드

요약

혼동 금지

06-cpu-mechanisms

1. 도입 배경

2. 제한적 직접 실행 원리 지도과정

3. 핵심 개념

개념별 정의 및 하드웨어 구조

4. 동작 흐름

하드웨어 ←> OS 타임라인

5. 구조 요약

6. 핵심 포인트

키워드

정리

혼동 금지

07-cpu-sched

1. 도입 배경

2. 소주제 지도

3. 핵심 개념

알고리즘별 특징

수식항 의미

개념 간 관계

4. 동작 흐름

성능 영향 요소