1. 운영체제는 왜 필요한가

여러분이 키보드를 누르면 모니터에 글자가 뜨고, 음악 플레이어는 백그라운드에서 노래를 흘려보내고, 브라우저는 동영상을 재생합니다. 이 모든 일이 한 대의 컴퓨터에서, 그것도 동시에 벌어지죠. 그런데 사실 CPU 코어 하나는 한 번에 한 가지 명령어밖에 처리하지 못해요. 그렇다면 누가 이 난장판을 정리하고 있는 걸까요?

그 정체가 바로 운영체제(operating system, OS)입니다. OS는 하드웨어 위에 앉아서 응용 프로그램이 마치 자기 혼자 컴퓨터를 독차지한 것처럼 느끼게 만들어 줍니다. 일종의 무대 뒤 연출자라고 보면 돼요. 관객(=프로그램) 입장에서는 매끄러운 공연을 보지만, 무대 뒤에서는 조명, 음향, 배우 교체가 정신없이 돌아가고 있죠.

2. 가상화 — OS의 가장 큰 무기

OS가 부리는 마법의 핵심 단어는 가상화(virtualization)입니다. 물리적인 자원 하나를 마치 여러 개인 것처럼, 혹은 실제와 다른 형태인 것처럼 보여 주는 기술이죠.

예를 들어 CPU가 하나뿐이어도, OS는 매 순간마다 어떤 프로그램의 코드를 잠깐 돌리고, 잽싸게 다른 프로그램으로 갈아치우는 식으로 "여러 개의 가상 CPU"라는 환상을 만들어 냅니다. 인간이 눈치채기엔 너무 빠른 속도로 갈아끼우니까, 우리는 그저 모든 게 동시에 돌아가는 줄로만 아는 거예요. 메모리도 마찬가지입니다. 물리 메모리는 하나지만, 각 프로그램은 자기만의 거대한 가상 주소 공간을 갖고 있다고 믿게 되죠.

잠깐, 그러면 이런 의문이 들지 않나요? "프로그램끼리 서로의 데이터를 훔쳐보면 어쩌지?" 좋은 질문입니다. OS는 가상화를 통해 격리(isolation)도 함께 제공해요. 각 프로그램은 자기만의 가상 세계 속에서 살기 때문에, 옆집 프로세스의 변수에 함부로 손을 댈 수 없습니다.

3. API와 시스템 콜

그렇다면 응용 프로그램은 어떻게 OS의 마법을 빌릴까요? 답은 시스템 콜(system call)입니다. OS는 자신이 제공하는 서비스들을 일종의 메뉴판처럼 정리해 두고, 프로그램은 그 메뉴를 호출하는 방식으로 OS의 도움을 받죠.

// 파일을 읽는 단순한 예시
int fd = open("data.txt", O_RDONLY);
char buf[128];
read(fd, buf, sizeof(buf));
close(fd);

위 코드에서 open, read, close는 그냥 라이브러리 함수처럼 보이지만 실제로는 커널에게 "이 일 좀 부탁해" 하고 넘겨주는 통로입니다. 프로그램은 디스크가 어떻게 회전하는지, 어느 섹터에 데이터가 있는지 전혀 몰라도 됩니다. OS가 알아서 처리해 주거든요.

4. OS의 세 가지 사명

이 책의 1부에서 우리는 OS가 떠맡은 세 가지 큰 일을 차례로 살펴볼 거예요. 가상화(virtualization), 동시성(concurrency), 그리고 영속성(persistence)이죠. CPU 가상화는 그중 첫 단추입니다. 하나의 CPU를 어떻게 쪼개서 여러 프로세스에게 나눠 줄 것인가, 어떻게 안전을 보장하면서도 빠르게 돌릴 것인가 — 다음 챕터부터 본격적으로 파고듭니다.

마무리

운영체제는 하드웨어를 그대로 노출시키는 대신, 잘 다듬어진 추상화로 포장해 우리에게 건네줍니다. 가상화로 자원을 나누고, 시스템 콜로 서비스를 제공하며, 격리로 안전을 지키죠. 다음 장부터는 이 추상화의 첫 번째 주인공인 "프로세스"를 만나러 갑니다.

1. 프로세스란 무엇인가

프로세스(process)는 한마디로 "지금 실행 중인 프로그램"입니다. 디스크에 가만히 누워 있는 실행 파일은 그저 텍스트 덩어리일 뿐이에요. 그 파일이 메모리에 올라오고 CPU가 명령어를 한 줄씩 처리하기 시작하는 순간, 비로소 프로세스라는 살아 있는 존재가 됩니다.

프로그램과 프로세스의 차이는 마치 요리책과 실제 요리의 차이와 비슷해요. 요리책에는 레시피가 적혀 있을 뿐이지만, 실제 요리는 재료가 있고, 불 위에서 끓고, 시간이 흐르면 식어 버리죠. 프로세스도 그래요. 자기만의 메모리 상태, 레지스터 값, 열어 놓은 파일 목록 같은 살아 있는 정보들을 들고 있습니다.

2. 프로세스를 구성하는 기계 상태

프로세스 하나를 정확하게 묘사하려면 어떤 정보가 필요할까요? OS 입장에서는 다음 항목들을 알아야 합니다.

첫째, 메모리(주소 공간)입니다. 코드, 전역 변수, 힙, 스택이 여기에 담겨요. 둘째, CPU 레지스터입니다. 프로그램 카운터(PC)가 어디를 가리키고 있는지, 스택 포인터(SP)는 어디인지, 일반 레지스터에는 어떤 값이 들어 있는지 모두 프로세스의 일부예요. 셋째, 입출력 정보입니다. 어떤 파일을 열어 두었는지, 어떤 소켓이 연결돼 있는지 같은 것들이죠.

이 모든 상태를 한 묶음으로 보관해 두는 자료구조를 프로세스 제어 블록(Process Control Block, PCB)이라고 부릅니다. 리눅스 커널에서는 task_struct라는 이름으로 등장하는데, 이 구조체 한 덩이가 곧 한 프로세스의 신분증인 셈이죠.

3. 프로세스의 생애주기

프로세스는 태어나서 죽기까지 여러 상태를 오갑니다. 보통 다음 세 가지가 핵심이에요.

실행(Running) — CPU 위에서 진짜로 명령어를 실행 중인 상태. 준비(Ready) — 당장 CPU만 주어지면 돌아갈 수 있는데, 자기 차례를 기다리는 상태. 대기(Blocked) — 어떤 사건이 끝나기를 기다리느라 잠들어 있는 상태. 예를 들어 디스크에서 데이터가 오기를 기다리는 동안에는 굳이 CPU를 차지하고 있을 필요가 없잖아요? 그럴 때 프로세스는 대기 상태로 빠지고, 그 사이 다른 친구가 CPU를 쓰는 거죠.

// 의사 코드: 상태 전이의 큰 그림
Running  -- 타임 슬라이스 만료 -->  Ready
Running  -- I/O 요청           -->  Blocked
Blocked  -- I/O 완료           -->  Ready
Ready    -- 스케줄러가 선택    -->  Running

4. 프로세스를 만들고 띄우는 과정

OS가 프로그램 하나를 새 프로세스로 띄우려면 대략 이런 일을 합니다. 디스크에 있는 실행 파일을 읽어 메모리로 적재하고, 스택과 힙을 위한 공간을 확보하고, 표준 입출력 같은 기본 파일 디스크립터를 열어 주고, 마지막으로 프로그램의 시작점(main 함수의 진입 지점)으로 점프하죠. 그 순간부터 그 프로세스는 자기만의 인생을 살기 시작합니다.

마무리

프로세스는 OS가 사용자에게 보여주는 가장 기초적인 추상화입니다. 한 대의 기계 위에서, 마치 각자만의 컴퓨터를 가진 듯한 환영을 만들어 주는 무대 장치죠. 다음 장에서는 이 프로세스를 실제로 만들어 내고 조작하는 시스템 콜들 — fork()와 그 친구들을 만나러 갑니다.

1. fork() — 자기 복제 마법

유닉스 계열에서 새 프로세스를 만드는 가장 기본적인 시스템 콜은 fork()입니다. 이름 그대로 "포크 모양으로 갈라진다"는 뜻이에요. 부모 프로세스가 fork()를 호출하면, OS는 그 프로세스의 거의 완벽한 복사본을 만들어 줍니다. 그 결과 두 개의 프로세스가 생기고, 둘은 마치 쌍둥이처럼 같은 코드를 실행하게 되죠.

#include <stdio.h>
#include <unistd.h>

int main() {
    pid_t pid = fork();
    if (pid < 0) {
        perror("fork failed");
    } else if (pid == 0) {
        printf("나는 자식이에요. 내 PID는 %d\n", getpid());
    } else {
        printf("나는 부모. 자식의 PID는 %d\n", pid);
    }
    return 0;
}

흥미로운 건 fork()가 한 번 호출되었는데 두 번 반환된다는 점이에요. 부모에게는 새로 태어난 자식의 PID를, 자식에게는 0을 돌려줍니다. 같은 코드를 같은 자리에서 실행하지만, 반환값에 따라 둘은 서로 다른 길을 걷게 되죠. 이게 처음 보면 좀 어지러울 수 있는데, 익숙해지면 묘하게 우아한 설계라는 걸 알게 됩니다.

2. wait() — 부모의 기다림

그런데 잠깐, 부모와 자식이 동시에 돌아가면 출력 순서가 뒤죽박죽 되지 않을까요? 맞습니다. 누가 먼저 출력될지는 스케줄러 마음이에요. 만약 부모가 자식이 끝날 때까지 기다리고 싶다면 wait() 시스템 콜을 쓰면 됩니다.

pid_t pid = fork();
if (pid == 0) {
    // 자식이 할 일
    printf("자식 끝!\n");
} else {
    int status;
    wait(&status);  // 자식이 끝날 때까지 잠듦
    printf("부모: 자식이 떠났구나\n");
}

wait()을 쓰면 결과 출력이 정해진 순서대로 나오게 만들 수 있어요. 그리고 자식의 종료 코드도 함께 받아올 수 있죠.

3. exec() — 영혼 갈아끼우기

fork()만 있으면 아쉬운 게 하나 있어요. 자식이 부모랑 똑같은 코드만 돌릴 수 있다는 점이죠. 그래서 짝꿍처럼 등장하는 게 exec() 계열 함수예요. exec()를 호출하면 현재 프로세스의 메모리 이미지가 통째로 새 프로그램으로 교체됩니다. PID는 그대로지만, 안에서 돌아가는 코드와 데이터는 전혀 다른 프로그램이 되는 거죠.

pid_t pid = fork();
if (pid == 0) {
    char *args[] = {"ls", "-l", NULL};
    execvp("ls", args);
    // 여기 도달하면 exec 실패한 것
    perror("exec failed");
}

이 패턴이 바로 셸(shell)이 명령어를 실행하는 방식이에요. 셸은 fork()로 자식을 만들고, 그 자식이 exec()로 실제 명령(예: ls, grep)을 부르는 거죠.

4. 왜 한 번에 안 만들고 두 단계로?

처음 보면 의문이 들어요. "그냥 새 프로그램을 띄우는 시스템 콜 하나 만들면 되지, 왜 fork와 exec를 굳이 분리했지?" 이게 사실 유닉스 설계의 묘미입니다.

fork()와 exec() 사이의 그 짧은 틈에서 부모는 자식의 환경을 자유롭게 손볼 수 있어요. 예를 들어 표준 출력을 파일로 돌려놓는다거나(리다이렉션), 다른 프로세스와 파이프로 연결한다거나 하는 일이죠. 만약 한 방에 새 프로그램을 띄워 버리면 이런 세팅을 끼워 넣을 자리가 없어요. 두 단계로 쪼갠 덕분에 셸의 강력한 기능들 — cmd1 | cmd2 > out.txt 같은 — 이 자연스럽게 가능해진 거죠.

마무리

fork(), exec(), wait()은 유닉스 프로세스 모델의 삼총사입니다. 셋이 합쳐지면 셸도 만들 수 있고, 데몬 서버도 만들 수 있고, 컨테이너도 만들 수 있죠. 단순한 인터페이스가 어떻게 풍부한 표현력을 낳는지 보여 주는 좋은 예입니다.

1. 직접 실행의 유혹과 위험

가장 빠르게 프로그램을 돌리는 방법은 뭘까요? 그냥 CPU에 코드를 통째로 올려놓고 시작점에서 점프하면 됩니다. 이걸 직접 실행(direct execution)이라고 불러요. 빠르긴 하죠. 그런데 이렇게만 하면 큰 문제가 두 가지 생깁니다.

첫째, 프로그램이 마음대로 디스크를 지우거나, 다른 프로세스의 메모리를 들여다보거나, 키보드 입력을 가로챌 수 있어요. 둘째, 한 프로그램이 무한 루프에 빠지면 CPU가 영원히 그 프로그램에 묶여 버립니다. 이래서야 OS가 통제권을 유지할 수가 없죠.

그래서 OS는 "직접 실행"에 두 가지 안전장치를 덧붙입니다. 권한을 제한하는 장치 하나, 그리고 CPU를 되찾아오는 장치 하나. 이걸 합쳐서 제한적 직접 실행(Limited Direct Execution)이라고 부르는 거예요.

2. 사용자 모드와 커널 모드

현대 CPU는 적어도 두 가지 권한 수준을 지원합니다. 사용자 모드(user mode)에서는 명령어 일부만 쓸 수 있어요. 디스크에 직접 접근하거나, 인터럽트를 끄거나 하는 위험한 명령은 막혀 있죠. 반면 커널 모드(kernel mode)에서는 모든 명령어를 자유롭게 쓸 수 있어요.

프로그램은 평소엔 사용자 모드에서 돕니다. 그러다가 디스크 읽기 같은 특권이 필요한 일을 해야 할 때, 시스템 콜을 통해 잠시 커널 모드로 올라가요. OS가 일을 마치면 다시 사용자 모드로 내려와서 프로그램이 이어서 돌아가죠. 이 모드 전환이 바로 트랩(trap)이라는 메커니즘으로 일어납니다.

3. 트랩 테이블 — 미리 약속된 비상구

프로그램이 시스템 콜을 부른다고 해서 아무 데나 점프할 수 있게 두면 보안이 다 무너지겠죠. 그래서 OS는 부팅 시점에 트랩 테이블(trap table)을 만들어 둡니다. "이런 종류의 트랩이 발생하면 커널의 이 위치에서 처리하라"는 일종의 전화번호부예요.

프로그램이 int 0x80이나 syscall 같은 트랩 명령을 실행하면 CPU는 자동으로 커널 모드로 전환되고, 트랩 테이블에 적힌 정해진 핸들러로 점프합니다. 임의의 커널 코드로 갈 순 없는 거죠. 안전한 비상구가 미리 정해져 있는 셈입니다.

// 사용자 코드 (의사코드)
mov  eax, 1       // syscall 번호 (예: write)
mov  edi, 1       // fd (stdout)
mov  rsi, msg
mov  rdx, len
syscall           // 여기서 트랩 발생, 커널 모드로 전환

4. CPU를 되찾아오는 두 가지 방법

이제 두 번째 문제, CPU를 되찾아오는 방법을 봅시다. 두 가지 접근이 있어요.

협력적(cooperative) 방식 — 프로그램이 알아서 시스템 콜이나 yield()를 호출해 주기를 기대하는 방식이에요. 잘 짜인 프로그램이라면 동작은 하겠지만, 누군가 무한 루프 한 줄만 짜 놔도 시스템 전체가 마비됩니다. 너무 순진하죠.

선점적(preemptive) 방식 — OS가 타이머 인터럽트를 켜 두고, 정해진 시간(예: 10밀리초)이 지날 때마다 강제로 CPU를 빼앗습니다. 이 인터럽트가 발생하면 CPU는 자동으로 커널의 인터럽트 핸들러로 점프해요. 거기서 OS는 "지금 돌고 있는 녀석 자, 이제 그만!" 하고 다른 프로세스로 갈아치울 수 있습니다.

이 갈아치우는 작업을 문맥 교환(context switch)이라고 합니다. 현재 프로세스의 레지스터들을 그 PCB에 저장하고, 다음 프로세스의 레지스터들을 복원해서 CPU에 올려 주죠. 마치 책을 읽다가 페이지에 책갈피를 끼우고, 다른 책을 펼쳐서 책갈피가 있던 곳부터 다시 읽는 것과 비슷해요.

마무리

제한적 직접 실행은 단순한 아이디어 두 개의 조합이에요. 권한을 분리하고, 시계로 통제권을 회수한다. 이 둘이 합쳐져서 OS는 빠른 속도와 안전함을 동시에 얻어 냅니다. 다음 장에서는 이렇게 회수한 CPU를 누구에게 줄지 결정하는 스케줄러를 살펴봅니다.

1. 두 가지 평가 기준

스케줄링 정책을 비교하려면 먼저 잣대가 필요합니다. 가장 자주 쓰이는 두 가지가 있어요.

첫째, 처리 시간(turnaround time) — 작업이 시스템에 들어와서 끝날 때까지 걸린 총 시간이에요. 짧을수록 좋겠죠. 둘째, 응답 시간(response time) — 작업이 들어온 뒤 처음으로 CPU를 잡고 돌기 시작하기까지 걸린 시간입니다. 대화형 프로그램에선 이게 작아야 사람이 답답해하지 않아요.

그런데 잠깐, 이 둘은 종종 충돌합니다. 응답 시간을 줄이려면 자주 갈아치워야 하지만, 그러면 문맥 교환 오버헤드가 늘어 처리 시간이 나빠질 수 있죠. 스케줄러 설계는 결국 이런 트레이드오프 게임이에요.

2. 단순한 가정으로 출발하기

이론을 처음 다룰 땐 실제 세계의 복잡함을 잠깐 잊어 봅시다. 다음과 같은 비현실적인 가정에서 시작할게요. 모든 작업은 도착 시점이 같다, 모든 작업은 실행 시간이 미리 알려져 있다, 작업은 CPU만 쓰고 I/O는 안 한다, 그리고 한 번 시작하면 끝까지 달린다(선점 없음). 이 가정들을 하나씩 깨면서 정책을 발전시켜 갑니다.

3. FIFO — 줄 서서 차례대로

가장 단순한 정책은 도착한 순서대로 처리하는 FIFO(First-In, First-Out)예요. 직관적이고 구현도 쉽지만, 한 가지 큰 문제가 있어요. 만약 첫 번째 작업이 100초짜리 거대한 일이고, 그 뒤에 1초짜리 짧은 일들이 줄지어 있다면? 짧은 일들이 모두 100초 넘게 기다려야 끝납니다. 이걸 호위 효과(convoy effect)라고 불러요. 트럭 한 대가 좁은 길을 막으니 뒤차들이 줄줄이 발이 묶이는 셈이죠.

// FIFO에서 처리 시간 평균 계산 예시
A: 길이 100, 도착 0
B: 길이 10,  도착 0+
C: 길이 10,  도착 0+

A 종료 = 100, B 종료 = 110, C 종료 = 120
평균 처리 시간 = (100+110+120) / 3 = 110초

4. SJF — 짧은 일부터

호위 효과를 줄이는 자연스러운 아이디어는 짧은 작업을 먼저 돌리는 것이에요. 이 정책을 SJF(Shortest Job First)라고 부릅니다. 위 예시에서 SJF로 돌리면 B와 C가 먼저 끝나고 A가 마지막이 되니까, 평균 처리 시간이 확 줄어들죠.

이론적으로 SJF는 처리 시간 측면에서 최적입니다. 하지만 두 가지 큰 단점이 있어요. 작업의 길이를 미리 알아야 한다는 점, 그리고 짧은 작업이 도중에 도착하면 이미 돌고 있는 긴 작업을 못 끊는다는 점이요.

5. STCF — 끊고 갈아타기

두 번째 단점을 해결하려면 선점(preemption)이 필요합니다. 새로 들어온 작업이 더 짧으면, 돌고 있던 작업을 잠깐 멈추고 갈아탑시다. 이게 STCF(Shortest Time-to-Completion First)예요. 평균 처리 시간 면에서는 정말 강력하죠.

그런데 응답 시간은? STCF는 응답 시간엔 별로 좋지 않아요. 길이가 비슷한 여러 작업이 동시에 도착하면 어떤 한 작업은 한참을 기다려야 자기 차례가 옵니다. 대화형 프로그램에는 부적절하죠.

6. 라운드 로빈 — 시간을 잘라 나눠 주기

응답 시간을 줄이려면 어떻게 할까요? 답은 시간을 잘게 잘라 모든 작업에게 골고루 돌리는 것이에요. 이걸 라운드 로빈(Round Robin, RR)이라고 부릅니다. 각 작업에게 정해진 타임 슬라이스(예: 10ms)만큼만 돌게 하고, 시간이 다 되면 다음 차례로 넘기는 거죠.

RR은 응답 시간이 아주 짧아요. 모든 작업이 거의 즉시 한 번씩 CPU를 잡아 보니까요. 하지만 처리 시간 면에선 손해예요. 짧은 일도 자기 차례를 기다리며 시간을 흘려보내야 하거든요. 그리고 타임 슬라이스를 너무 작게 잡으면 문맥 교환 오버헤드가 폭증합니다. 이 균형 잡기가 RR 설계의 핵심이에요.

마무리

FIFO에서 시작해 SJF, STCF, RR까지 — 우리는 처리 시간과 응답 시간이라는 두 마리 토끼를 두고 줄다리기를 했어요. 어느 한쪽도 모든 면에서 완벽하진 않죠. 그렇다면 작업의 성격을 미리 모르는 일반적인 환경에선 어떤 스케줄러를 써야 할까요? 다음 장의 MLFQ가 그 답을 들고 옵니다.

1. 작업을 미리 아는 척하지 않기

SJF와 STCF는 작업의 실행 시간을 안다고 가정했어요. 하지만 실제 OS에서 누군가 "이 프로그램은 정확히 7.3초 걸려요"라고 미리 알려 주는 일은 없죠. 그래서 진짜 영리한 스케줄러는 미래를 예측하지 않고, 과거의 행동을 관찰하면서 추론합니다. 이게 MLFQ의 핵심 아이디어예요.

"방금 전까지 짧게 짧게 CPU를 쓰다가 I/O 하러 간 친구라면, 다음에도 비슷할 거다." 이런 가정을 깔고 우선순위를 동적으로 조정하는 거죠. 일종의 행동 기반 등급제예요.

2. 여러 층의 큐

MLFQ는 이름 그대로 여러 단계의 우선순위 큐를 둡니다. 가장 높은 큐부터 가장 낮은 큐까지 죽 늘어놓고, 다음 두 가지 규칙을 깔아요.

규칙 1: 두 작업의 우선순위가 다르면 더 높은 쪽이 먼저 돈다. 규칙 2: 우선순위가 같다면 그 큐 안에서 라운드 로빈 방식으로 돈다.

여기까진 그냥 다층 우선순위 큐예요. 핵심은 다음입니다 — 작업이 어느 큐에 속할지를 그 작업의 행동에 따라 OS가 동적으로 바꿔 줍니다.

3. 우선순위를 어떻게 조정할까

가장 단순한 규칙으로 시작해 봅시다. 새로 들어온 작업은 가장 높은 큐에 넣어 시작해요. 일단 한 번 후하게 대접해 주는 거죠. 그리고 다음 규칙을 둡니다.

규칙 3: 작업이 자기 타임 슬라이스를 다 써 버리면 한 단계 강등시킨다. 규칙 4: 타임 슬라이스가 끝나기 전에 자발적으로 CPU를 놓으면(예: I/O 대기) 같은 큐에 머무르게 둔다.

이 규칙들이 합쳐지면 마법이 일어나요. 짧고 대화형인 작업은 CPU를 살짝 쓰고 I/O로 빠지니까 계속 높은 큐에 남아 있고, 응답 시간이 빠릅니다. 반대로 긴 CPU 바운드 작업은 타임 슬라이스를 매번 다 쓰니까 점점 아래 큐로 밀려 내려가요. 결국 자연스럽게 SJF 비슷한 효과가 나타나는 거죠.

4. 스케줄러를 속이는 사람들

그런데 여기에 빈틈이 있어요. 두 가지 문제예요.

첫째, 굶주림(starvation). CPU 바운드 작업이 한 번 아래 큐로 떨어지면, 위 큐에 새 작업이 계속 들어올 때 영원히 차례가 안 올 수 있어요. 둘째, 게이밍(gaming). 누군가 자기 작업의 우선순위를 떨어뜨리지 않으려고 타임 슬라이스가 끝나기 직전에 의도적으로 잠깐 I/O를 발생시키는 식의 꼼수를 부릴 수 있죠.

두 문제를 한 방에 해결하는 트릭이 있어요. 일정 시간마다 모든 작업을 가장 높은 큐로 끌어올리는 겁니다(이걸 priority boost라고 불러요).

규칙 5: 일정 주기 S마다 모든 작업을 최상위 큐로 올려놓는다.

이걸 도입하면 굶주림은 사라져요. 어떤 작업도 영원히 묻혀 있지는 않으니까요. 그리고 게이밍을 시도해도 어차피 주기적으로 리셋되니 큰 이득이 없어집니다.

5. 시간의 누적으로 등급을 매기기

또 하나의 개선은 작업이 한 큐에서 사용한 누적 시간을 추적하는 거예요. 단순히 "한 번에 타임 슬라이스를 다 썼는지"가 아니라, 그 큐에서 누적으로 얼마나 많은 시간을 사용했는지를 기준으로 강등시키는 방식이죠.

규칙 3'(개선): 한 큐 안에서 누적 사용 시간이 정해진 한도를 넘으면 강등시킨다(I/O로 잠깐씩 끊는다고 해서 봐주지 않는다).

// MLFQ 규칙 요약
1. 우선순위 높은 큐가 먼저
2. 같은 큐는 RR
3. 누적 시간 한도 초과 시 강등
4. 새 작업은 최상위 큐에서 시작
5. 주기 S마다 모두 최상위로 부스트

마무리

MLFQ는 "과거의 행동으로 미래를 추측한다"는 직관을 우아하게 구현한 스케줄러예요. 미래를 미리 알지 못해도 SJF와 RR의 좋은 면을 동시에 얻어 낼 수 있죠. 실제로 솔라리스, BSD 계열, 윈도우 등 많은 OS가 MLFQ에 가까운 구조를 채택했어요. 직관과 현실의 행복한 만남이라고 할 만합니다.

1. 응답 시간 대신 비율

지금까지 살펴본 스케줄러들은 모두 처리 시간이나 응답 시간을 최적화하려 했어요. 그런데 어떤 환경에선 이런 지표보다 "각 작업이 받는 CPU 비율"이 더 중요해요. 예를 들어 클라우드 서버에서 고객 A는 50%, B는 30%, C는 20%만큼 받기로 계약했다고 합시다. 이런 상황에선 "비례 배분(proportional share)"이라는 새로운 사고방식이 필요합니다.

2. 추첨 스케줄링의 아이디어

가장 먼저 살펴볼 방식은 추첨 스케줄링(lottery scheduling)이에요. 발상이 재미있어요. 각 프로세스에게 추첨 티켓을 몇 장씩 나눠 줍니다. 매 스케줄링 시점마다 OS는 모든 티켓 중에서 무작위로 한 장을 뽑고, 그 티켓을 가진 프로세스에게 CPU를 줍니다.

// 의사 코드
totalTickets = sum(ticketsOf(p) for p in runnable)
winner = random_int(0, totalTickets - 1)
counter = 0
for p in runnable:
    counter += ticketsOf(p)
    if counter > winner:
        run(p)
        break

티켓을 100장 가진 A와 50장 가진 B가 있다면, 장기적으로 A는 약 2/3, B는 약 1/3의 CPU를 받게 됩니다. 운에 맡기는 방식이지만, 시간이 길어질수록 비율이 점점 정확해져요.

3. 왜 무작위인가

조금 이상하게 들리지 않나요? 정확하게 비율을 맞추려면 차라리 결정론적으로 돌리는 게 낫지 않을까요? 사실 추첨 방식엔 두 가지 강점이 있어요.

첫째, 구현이 매우 단순합니다. 복잡한 자료구조도 필요 없고, 어떤 작업이 언제 들어오고 나가도 문제없이 작동해요. 둘째, 새로운 작업이 끼어들거나 떠나도 자연스럽게 잘 적응합니다. 큐의 상태를 정교하게 관리할 필요가 없어요. 단점은? 짧은 시간 단위에선 비율이 안 맞을 수 있다는 점이죠.

4. 보폭 스케줄링 — 결정론적 형제

무작위가 마음에 들지 않는다면 보폭 스케줄링(stride scheduling)을 쓸 수 있어요. 각 작업에게 자기 티켓 수에 반비례하는 보폭(stride)을 줍니다. 그리고 작업마다 누적값(pass)을 추적해요. 매 스케줄링 시점에 누적값이 가장 작은 작업을 골라 돌리고, 끝나면 그 작업의 누적값에 보폭을 더합니다.

// 의사 코드
stride(p) = LARGE_CONST / tickets(p)
pass(p)   = 0  (초기)

while True:
    p = argmin(pass(p) for p in runnable)
    run(p, one_slice)
    pass(p) += stride(p)

티켓을 많이 받은 작업은 보폭이 짧으니 누적값이 천천히 올라가고, 그래서 자주 선택됩니다. 결정론적이라 비율이 정확하게 맞아떨어져요. 다만 새 작업이 합류할 때 그 누적값을 어떻게 초기화할지 같은 잔걱정이 늘어납니다.

5. 리눅스의 CFS — 비례의 또 다른 얼굴

현대 리눅스가 오랫동안 써 온 CFS(Completely Fair Scheduler)도 사실 비례 배분의 한 변형이에요. 각 프로세스의 누적 가상 실행 시간(vruntime)을 추적하고, 가장 작은 vruntime을 가진 프로세스를 다음 차례로 돌리죠. nice 값(우선순위)에 따라 vruntime이 누적되는 속도가 달라지니까, 결국 우선순위에 비례한 CPU 배분이 됩니다.

CFS는 추첨도 보폭도 아니지만, 정신적으로는 보폭 스케줄링과 같은 가족이에요. 우선순위 큐 대신 빨강-검정 트리(Red-Black Tree) 같은 자료구조로 vruntime을 정렬해 두고, 가장 작은 노드를 빠르게 꺼내 쓰는 거죠.

마무리

비례 배분 스케줄링은 "누가 얼마나 받느냐"라는 질문에 직접 답하는 정책입니다. 추첨 방식의 우아한 단순함, 보폭 방식의 결정론적 정확함, CFS의 산업적 성숙함 — 모두 같은 가족 안의 다른 얼굴이에요. 자원을 비율로 통제하고 싶다면 가장 먼저 떠올려야 할 도구들입니다.

1. 멀티코어가 흔해진 시대

한때 컴퓨터에 CPU 하나만 있는 시절이 있었어요. 그땐 스케줄러도 비교적 단순했죠. 그런데 어느 순간부터 칩 안에 코어가 둘, 넷, 여덟, 열여섯 개씩 박히기 시작했어요. 클럭을 무한정 올릴 수 없게 된 하드웨어 업계가 "그럼 CPU를 여러 개로 늘려요" 쪽으로 방향을 튼 거죠. 그 결과 OS 스케줄러도 새 시대에 맞게 다시 설계해야 했습니다.

2. 캐시 친화성 — 같은 자리를 좋아한다

멀티프로세서 환경에서 가장 먼저 알아야 할 개념은 캐시 친화성(cache affinity)이에요. 각 CPU 코어는 자기만의 캐시(L1, L2 등)를 가지고 있어서, 한 프로세스가 한 코어에서 한참 돌면 그 코어의 캐시에 그 프로세스의 데이터가 따끈따끈하게 채워져요.

그런데 스케줄러가 그 프로세스를 다른 코어로 옮기면 어떻게 될까요? 새 코어의 캐시에는 그 데이터가 없으니까 메모리에서 다시 끌어와야 합니다. 캐시가 식고, 성능이 뚝 떨어지죠. 그래서 좋은 스케줄러는 가능하면 같은 프로세스를 같은 코어에 머물게 하려 합니다. 이걸 친화성을 지킨다고 표현해요.

3. 단일 큐 vs 다중 큐

멀티프로세서 스케줄러를 만드는 큰 갈래가 둘 있어요.

단일 큐(SQMS, Single-Queue Multiprocessor Scheduling) — 모든 코어가 하나의 공용 준비 큐를 공유합니다. 어떤 코어가 비면, 그 큐에서 다음 작업을 꺼내 가요. 구현이 단순하고 부하 분산도 자연스럽죠. 단점은 명확합니다. 큐가 공용이니 락이 필요하고, 코어 수가 늘어날수록 그 락이 병목이 됩니다. 그리고 캐시 친화성도 지키기 힘들어요. 작업이 매번 어느 코어로 갈지 정해져 있지 않으니까요.

다중 큐(MQMS, Multi-Queue Multiprocessor Scheduling) — 코어마다 자기 큐를 둡니다. 락 경합이 줄고, 한 코어 안에서 친화성을 잘 지킬 수 있죠. 다만 부하가 한쪽 큐에만 몰리면 다른 코어가 놀게 되는 부하 불균형(load imbalance)이 생겨요.

4. 마이그레이션과 작업 훔치기

다중 큐의 부하 불균형을 해결하려면 가끔 작업을 다른 코어로 옮겨야 해요. 이걸 마이그레이션(migration)이라고 부릅니다.

가장 흔한 전략은 작업 훔치기(work stealing)예요. 자기 큐가 비어 한가해진 코어가, 바빠 보이는 다른 코어의 큐를 슬쩍 들여다보고 작업 하나를 가져오는 거죠. "남의 일감을 훔쳐 온다"는 다소 도둑스러운 이름이지만, 사실 매우 합리적인 전략입니다. 너무 자주 훔치면 친화성이 깨지니까, 적당히만 시도해야 해요.

// 의사 코드: 매우 단순한 work stealing
on_idle_core(C):
    if my_queue.empty():
        for V in other_cores:
            if V.queue.size() > threshold:
                t = V.queue.pop_one()
                my_queue.push(t)
                break

5. 리눅스 진영의 실험

리눅스 커널의 스케줄러 역사를 잠깐 들여다보면 흥미로워요. 초기엔 단일 큐 기반의 O(n) 스케줄러를 썼다가, 코어 수가 늘면서 O(1) 스케줄러로 옮겨갔고, 그 뒤 CFS(Completely Fair Scheduler)가 자리를 잡았어요. CFS는 코어마다 자기 트리를 두고, 주기적으로 부하를 확인해서 작업을 옮기는 식으로 멀티프로세서 환경에 잘 적응합니다.

BSD 계열의 ULE 스케줄러도 비슷한 방향성을 갖고 있어요. 코어별 큐 + 마이그레이션 휴리스틱이라는 큰 그림은 거의 모든 현대 OS의 표준이 됐죠.

마무리

멀티프로세서 스케줄링은 단일 CPU 스케줄링의 모든 고민에 캐시, 락, 부하 균형이라는 새로운 변수가 더해진 게임이에요. 답은 항상 트레이드오프 사이의 절묘한 줄타기입니다. 단일 큐의 단순함과 다중 큐의 확장성, 친화성과 균형, 결정론과 무작위 — 좋은 스케줄러는 이 사이를 똑똑하게 오가며 길을 찾아내요. 1부의 마지막 장을 끝낸 여러분, 이제 CPU 가상화의 큰 그림이 머릿속에 그려지지 않나요?

1. 옛날 옛적, 메모리가 한 덩어리였을 때

아주 초창기 컴퓨터를 떠올려 보자. 그 시절의 메모리는 그냥 하나의 큰 덩어리였어. 운영체제 코드가 한쪽에 들어 있고, 나머지 공간은 지금 실행 중인 프로그램 하나가 통째로 가져다 썼지. 멀티태스킹? 그런 게 어디 있어. 한 번에 한 프로그램이 끝나야 다음 프로그램 차례가 오는 식이었거든.

그러다가 사람들이 욕심을 내기 시작했어. "한 컴퓨터에서 여러 프로그램을 동시에 돌리면 좋지 않을까?" 그래서 등장한 것이 시분할(time sharing)이지. 그런데 시분할을 하려면 메모리도 잘 나눠 써야 해. 매번 프로그램을 디스크로 통째로 내렸다 다시 올렸다 하면 너무 느려서 못 쓸 정도가 되거든. 그래서 결국 "메모리에 여러 프로그램을 동시에 올려두자"는 결론에 다다랐어.

2. 동거의 어려움: 보호와 격리

여러 프로그램이 한 메모리에 올라타면 곧바로 새로운 문제가 튀어나와. 프로그램 A가 실수로 프로그램 B의 메모리를 덮어쓰면? 또는 악의적으로 운영체제의 코드 영역을 건드리면? 그건 곧 시스템 전체의 붕괴야. 그래서 우리에게 필요한 건 두 가지지. 첫째, 각 프로그램이 다른 프로그램의 메모리를 함부로 읽거나 쓰지 못하게 막는 보호(protection). 둘째, 그러면서도 각자 자유롭게 메모리를 쓸 수 있는 환상.

이 환상의 이름이 바로 주소 공간(address space)이야. 한국어로는 좀 어색하지만, 영어 그대로 받아들이면 "내가 쓸 수 있는 주소들의 공간"이라는 뜻이지. 운영체제는 모든 프로세스에게 "여기는 너만의 우주야. 0번지부터 주욱 쓰면 돼"라고 속삭여 줘. 실제로는 물리 메모리 어디 구석에 처박혀 있는지 모르겠지만, 프로세스 입장에서는 깔끔한 일직선 메모리가 자기 앞에 펼쳐져 있는 것처럼 보여.

3. 주소 공간의 구조

그럼 이 가상의 우주는 어떻게 생겼을까? 일반적인 프로세스의 주소 공간은 대략 이렇게 나뉘어 있어.

0x0000  ┌──────────────┐  <- 낮은 주소
        │  코드 (text) │  프로그램 명령어들
        ├──────────────┤
        │     데이터    │  전역 변수
        ├──────────────┤
        │      힙      │  ↓ malloc으로 자라남
        │      ...     │
        │      ...     │  ↑ 스택은 위로 자라남(아래쪽으로)
        │     스택     │
0xFFFF  └──────────────┘  <- 높은 주소

코드는 프로그램이 시작되면 거의 변하지 않는 영역이고, 데이터는 전역 변수가 사는 곳이야. 재미있는 부분은 힙(heap)과 스택(stack)이지. 이 둘은 실행 도중에 크기가 변해. 그래서 한쪽 끝에서 시작해 서로 마주보고 자라는 구조로 배치하는 게 흔해. 가운데 빈 공간이 두 영역의 완충지대가 되는 거지. 만약 둘이 부딪히면? 그건 메모리가 부족하다는 신호야.

4. 가상 메모리의 세 가지 목표

운영체제가 이 추상화를 만들 때 추구하는 목표는 보통 세 가지로 요약돼.

• 투명성(transparency): 프로그램이 가상 메모리의 존재를 의식하지 않아도 정상적으로 돌아가야 해. 프로그래머가 매번 "내 진짜 주소가 어디지?"를 신경 쓴다면 망한 추상화지.
• 효율성(efficiency): 추상화는 좋은데, 너무 느리면 안 돼. 시간 효율(주소 변환이 빨라야 함)과 공간 효율(메타데이터가 너무 많지 않아야 함) 둘 다 중요해.
• 보호(protection): 한 프로세스가 다른 프로세스나 운영체제의 메모리를 무단으로 건드리면 안 돼. 격리(isolation)라는 표현도 자주 쓰여.

이 세 마리 토끼를 다 잡는 게 앞으로 수많은 챕터에서 우리가 따라갈 여정이야.

1. 두 종류의 메모리: 스택과 힙

C 프로그래머의 머릿속에는 메모리가 두 종류로 나뉘어 있어. 하나는 스택, 다른 하나는 힙이지. 함수 안에서 그냥 int x;라고 선언한 변수는 자동으로 스택에 자리를 잡았다가, 함수가 끝나면 같이 사라져. 컴파일러가 알아서 다 챙겨주니까 편하지만, 함수 밖으로 그 데이터를 들고 나갈 수는 없어.

반면 힙은 프로그래머가 직접 관리해야 하는 영역이야. 함수가 끝나도 살아남아야 하는 데이터, 또는 크기를 미리 알 수 없는 데이터는 힙에 올려야 해. 그리고 그 통로가 바로 malloc과 free지.

2. malloc과 free, 사용법은 단순하지만

API 자체는 정말 단순해. 받고 싶은 바이트 수를 넘기면 그만큼의 공간을 가리키는 포인터를 돌려주고, 다 쓴 뒤에는 그 포인터를 free에 다시 넘겨주면 돼.

#include <stdlib.h>

int *arr = malloc(sizeof(int) * 100);  // int 100개 분량
if (arr == NULL) { /* 실패 처리 */ }
arr[0] = 42;
// ... 사용 ...
free(arr);
arr = NULL;  // 댕글링 방지의 작은 습관

여기서 sizeof를 빼먹는 사고가 생각보다 자주 일어나. malloc(100)은 그냥 100바이트지, int 100개가 아니거든. 64비트 환경에서 int가 4바이트라면 sizeof(int) * 100 = 400바이트가 정답이야. 컴파일러는 이런 산수를 대신 해주지 않아.

3. 자주 발생하는 실수들

malloc/free는 단순하지만, 동시에 C에서 가장 많은 버그가 모이는 곳이기도 해. 흔한 사고들을 정리해 보면 이래.

• 잊어버리고 free 안 함: 메모리 누수(memory leak). 짧게 도는 프로그램은 그냥 종료되면서 다 회수되지만, 서버처럼 오래 도는 프로그램에서는 누적되면 결국 메모리가 바닥나.
• 두 번 free: 같은 포인터를 free에 두 번 넘기면 할당기의 내부 자료구조가 깨져. 운이 좋으면 즉시 죽고, 운이 나쁘면 한참 뒤에 엉뚱한 곳에서 죽지.
• free 후 사용(use-after-free): 해제한 메모리를 다시 읽거나 쓰는 것. 보안 취약점의 단골 메뉴야.
• 버퍼 오버플로: 할당받은 크기를 넘어서 쓰는 것. 인접한 메모리를 망가뜨리지.
• 널 포인터 역참조: malloc이 NULL을 돌려줬는데 그걸 그대로 쓰는 것. 항상 반환값을 확인해야 해.

4. 그 밑에서 진짜 일하는 시스템 콜

그럼 malloc 자체는 시스템 콜일까? 아니야. malloc은 C 라이브러리에 있는 함수일 뿐이고, 진짜 운영체제에 메모리를 달라고 부탁하는 건 더 아래 단계야. 유닉스 계열에서는 전통적으로 brk나 sbrk로 힙의 끝을 늘리거나, mmap으로 익명 영역을 받아오지.

malloc은 운영체제로부터 큰 덩어리를 받아두고, 사용자가 작은 단위로 요청할 때마다 거기서 잘라 주는 일종의 도매상 같은 역할을 해. 매번 시스템 콜을 부르면 너무 느려서 효율이 안 나오거든. 그래서 라이브러리가 자기 안에서 빈 공간 관리를 따로 하는 거야. 이 빈 공간 관리가 얼마나 까다로운지는 17장에서 본격적으로 다룰 거야.

1. 변환이라는 이름의 마술

가상 메모리의 핵심 메커니즘은 결국 한 줄로 요약돼. "프로그램이 내놓은 가상 주소를 하드웨어가 실시간으로 물리 주소로 바꿔준다." 이걸 주소 변환(address translation)이라고 불러. 이게 매번 명령어가 메모리를 건드릴 때마다, 그러니까 초당 수억 번씩 일어나는 일이라는 게 포인트야. 느리면 시스템 전체가 느려져.

그러니 변환은 거의 전적으로 하드웨어의 일이고, 운영체제는 그 하드웨어가 참고할 자료구조를 잘 세팅해 두는 역할을 맡아. 일종의 분업이지. 이 분업 덕분에 가상화는 비현실적인 속도로 굴러갈 수 있어.

2. 가장 단순한 그림: 베이스와 바운드

본격적인 페이징으로 가기 전에, 먼저 아주 간단한 모델을 보자. 동적 재배치(dynamic relocation)라고도 불러. 아이디어는 이래. CPU에 두 개의 레지스터를 둬. 하나는 베이스(base), 다른 하나는 바운드(bound)야. 프로세스가 가상 주소 V를 내놓으면, 하드웨어는 이렇게 계산해.

물리주소 = base + V    (단, V < bound)
V >= bound 이면 트랩(trap) → 운영체제가 처리

예를 들어 base = 32KB, bound = 16KB로 세팅된 프로세스가 가상 주소 4096(= 4KB)에 접근하면, 실제로는 32KB + 4KB = 36KB 위치를 읽어. 만약 가상 주소 20KB를 요청하면 bound를 넘으니 트랩이 발생하고, 운영체제가 "넌 권한 없어"라며 프로세스를 끝내버리지.

3. OS가 하는 일과 하드웨어가 하는 일

이 단순한 모델에서도 OS와 하드웨어의 협력은 분명해. 정리해 보면 이래.

┌──────────────┬──────────────────────────────────┐
│ 하드웨어     │ 매 메모리 접근마다 base+V 계산  │
│              │ V >= bound면 예외 발생           │
│              │ 권한 비트 확인 (커널 모드 등)    │
├──────────────┼──────────────────────────────────┤
│ 운영체제     │ 프로세스 생성 시 빈 물리 영역 배정│
│              │ 컨텍스트 스위치 시 base/bound 교체│
│              │ 예외 발생 시 처리(보통 종료)     │
│              │ 빈 메모리 목록 관리              │
└──────────────┴──────────────────────────────────┘

컨텍스트 스위치 때 베이스와 바운드를 잊지 않고 바꿔주는 게 특히 중요해. 안 바꾸면 프로세스 A가 B의 메모리를 들여다보는 사고가 일어나거든. 이런 레지스터들은 보통 PCB(Process Control Block) 안에 따로 저장돼.

4. 단순함의 대가: 내부 단편화

베이스/바운드 방식은 멋지게 단순하지만, 큰 단점이 있어. 프로세스의 주소 공간 전체를 물리 메모리에 연속된 한 블록으로 통째로 올려야 한다는 거지. 사용자가 힙과 스택 사이에 큰 빈 공간을 두면, 그 빈 공간조차 물리 메모리를 차지하면서 같이 자리만 잡고 있어. 이걸 내부 단편화(internal fragmentation)라고 해. 메모리는 비싼데 안 쓰는 곳에 쌓아두는 셈이지.

그래서 다음 챕터부터는 이 한계를 깨려고 시도해. 주소 공간을 더 작은 조각으로 쪼개서, 각 조각을 물리 메모리의 다른 곳에 따로따로 배치할 수는 없을까? 이 발상의 첫 걸음이 세그멘테이션이야.

1. 한 덩어리로는 부족하다

15장에서 본 베이스/바운드는 깔끔하지만 주소 공간 전체를 통째로 옮긴다는 게 답답해. 코드, 데이터, 힙, 스택이 한 묶음으로 다녀야 하니, 가운데 비어 있는 공간까지 물리 메모리에 자리를 차지하는 거지. 그래서 사람들은 "이 영역들을 따로 떼어서 각자 다른 곳에 두면 안 될까?"라는 생각을 했어.

이 발상이 세그멘테이션이야. 주소 공간을 의미 단위의 세그먼트로 쪼개고, 세그먼트마다 자기만의 베이스와 바운드를 두는 거지. 보통 코드, 힙, 스택을 각각의 세그먼트로 다뤄.

2. 가상 주소의 해석

세그멘테이션 하드웨어는 가상 주소를 받으면 그게 어느 세그먼트에 속하는지 먼저 알아내야 해. 흔한 방법은 가상 주소의 위쪽 비트로 세그먼트를 구분하고, 나머지 비트를 세그먼트 안에서의 오프셋으로 쓰는 거야. 14비트 가상 주소를 예로 들면 이런 식이지.

비트 13 12 │ 11 10 9 8 7 6 5 4 3 2 1 0
   세그먼트 │          오프셋
     00     │   → 코드 세그먼트
     01     │   → 힙 세그먼트
     11     │   → 스택 세그먼트

예를 들어 힙 세그먼트의 base가 32KB, bound가 4KB일 때, 가상 주소 비트가 01 0000 0001 0100이면 세그먼트 1번(힙), 오프셋 20이라는 뜻이고, 물리 주소는 32KB + 20번지가 되는 거야. 오프셋이 4KB(bound)를 넘기면 세그멘테이션 폴트가 나지. 어디서 많이 들어본 단어 같지?

3. 위로 자라느냐 아래로 자라느냐

스택은 다른 세그먼트와 다르게 주소가 큰 쪽에서 작은 쪽으로 자라. 그래서 세그먼트 디스크립터에 "이 세그먼트는 어느 방향으로 자란다"는 비트가 추가로 필요해. 이 비트를 보고 하드웨어는 오프셋 계산을 다르게 해줘. 또 세그먼트마다 "읽기/쓰기/실행" 권한도 따로 줄 수 있어. 코드 세그먼트는 보통 실행 가능하지만 쓰기 불가, 데이터 세그먼트는 읽기/쓰기 가능 같은 식이지. 이 권한 덕분에 누군가 코드 영역을 변조하려는 시도를 막을 수 있어.

4. 공유와 외부 단편화

세그멘테이션에는 자연스러운 장점이 하나 있어. 코드 세그먼트는 읽기 전용이니 여러 프로세스가 같은 물리 위치를 공유해도 문제가 없거든. 라이브러리 코드 같은 걸 한 부 올려두고 모두가 같이 보는 식으로 메모리를 절약할 수 있지.

하지만 어두운 면도 있어. 세그먼트는 크기가 제각각이라, 프로세스가 들어왔다 나갔다 하다 보면 물리 메모리가 누더기처럼 변해. 큰 세그먼트가 들어갈 자리가 분명 충분히 있는데, 그게 작은 조각들로 흩어져 있어서 못 들어가는 상황이 생기지. 이걸 외부 단편화(external fragmentation)라고 해. 해결책은 보통 두 가지야. 첫째, 빈 공간을 똑똑하게 골라 쓰는 알고리즘(이건 17장 주제). 둘째, 가끔 한 번씩 메모리를 압축(compact)해서 빈 조각을 모으는 것. 후자는 비싼 작업이라 자주 못 해.

1. 가변 크기의 세계는 까다롭다

모든 요청이 같은 크기라면 빈 공간 관리는 식은 죽 먹기야. 비어 있는 칸들의 리스트를 만들어 두고 하나 빼서 주면 되거든. 문제는 우리가 다루는 요청들이 거의 항상 가변 크기라는 점이야. malloc(8), malloc(192), malloc(40) 같은 식으로 마구 들어오지. 어떤 게 들어올지 알 수 없으니 빈 공간도 다양한 크기로 흩어져.

이 챕터의 알고리즘들은 사실 운영체제가 직접 쓰기보다, malloc 같은 사용자 라이브러리에서 더 많이 쓰여. 하지만 OS도 비슷한 문제를 풀어야 할 때가 많아. 핵심 아이디어는 어디서나 통하는 셈이지.

2. 빈 공간 리스트와 헤더

가장 흔한 자료구조는 빈 공간 리스트(free list)야. 빈 칸들을 연결 리스트로 엮어 두는 거지. 그런데 사용자가 free(ptr)을 부르면 우리는 그 ptr이 가리키는 영역의 크기를 알아야 해. 다시 리스트에 돌려놓으려면 크기 정보가 필요하니까. 그래서 보통 사용자에게 돌려주는 영역 바로 앞에 헤더를 숨겨 둬.

┌─────────────┬──────────────────────┐
│ 헤더(크기,  │ 사용자에게 주는 영역 │
│ 매직넘버)   │ (포인터는 여기 가리킴)│
└─────────────┴──────────────────────┘
              ↑
              malloc 반환값

그래서 사용자가 100바이트를 요청하면 실제로는 헤더 크기까지 더한 만큼이 통으로 쪼개져. 매직 넘버를 같이 넣어두면 free 시점에 "이거 진짜 우리가 준 영역 맞아?"를 한번 검사할 수도 있지.

3. 어디서 잘라줄까: 배치 전략

요청이 들어왔을 때, 빈 칸 여러 개 중 어디서 자를지 정하는 정책이 여럿 있어.

• 최초 적합(first fit): 리스트를 처음부터 훑어 들어갈 만한 빈 칸이 처음 나오면 거기서 자른다. 빠르지만 앞쪽이 누더기가 되기 쉬워.
• 최적 적합(best fit): 모든 빈 칸을 다 보고 가장 딱 맞는 칸을 고른다. 외부 낭비는 적은 편이지만 매번 전체를 훑어야 해서 느려. 그리고 너무 작은 자투리 조각이 많이 생긴다는 부작용도 있지.
• 최악 적합(worst fit): 가장 큰 칸을 골라 거기서 잘라낸다. 자투리를 크게 남기려는 발상인데, 실험적으로 잘 안 되는 편이야.
• 다음 적합(next fit): 최초 적합인데 매번 처음이 아니라 마지막 검색 위치에서 이어서 시작한다. 앞쪽 누더기 문제를 좀 완화해.

4. 합치기, 분리하기, 그리고 분리 리스트

free가 호출되면 인접한 빈 칸들과 합쳐주는 게 중요해(coalescing). 이걸 안 하면 작은 빈 칸들이 잔뜩 생겨서, 분명히 빈 공간은 충분한데 큰 요청을 못 들어주는 상황이 벌어져. 반대로 큰 빈 칸을 잘라 작은 요청에 답하는 건 분할(splitting)이라고 해.

또 한 가지 흔한 기법은 분리 리스트(segregated lists)야. 자주 등장하는 작은 크기 몇 가지에 대해서는 따로 리스트를 두는 거지. 예를 들어 16, 32, 64바이트 요청은 각각 전용 리스트에서 즉답으로 처리하면, 매번 리스트를 훑을 필요가 없어. 이걸 더 정교하게 한 게 슬랩(slab) 할당기 같은 커널 안의 자료구조야.

또 다른 고전인 버디 시스템(buddy system)은 메모리를 2의 거듭제곱 단위로만 잘라. 분할과 합치기가 단순한 비트 연산으로 되니까 빠르고 깔끔해. 단점은 항상 2의 제곱으로 올림하느라 내부 단편화가 좀 생긴다는 거야.

1. 균일함의 위력

페이징의 아이디어는 단순해. 가상 주소 공간을 일정 크기(보통 4KB)의 페이지(page)로 자르고, 물리 메모리도 같은 크기의 프레임(frame)으로 자르는 거지. 그런 다음 각 가상 페이지가 어느 물리 프레임에 들어가 있는지를 표로 기록해 둬. 이 표가 바로 페이지 테이블(page table)이야.

모든 조각이 같은 크기이기 때문에 빈 칸이 어디든 상관없이 어떤 페이지든 들어갈 수 있어. 외부 단편화 문제가 사라지지. 빈 프레임 리스트만 잘 관리하면 메모리 배치가 간단해져.

2. 가상 주소를 자르는 법

페이징에서 가상 주소는 두 부분으로 쪼개져. 위쪽은 가상 페이지 번호(VPN), 아래쪽은 페이지 안에서의 오프셋이지. 페이지 크기가 4KB(2^12)라면 오프셋은 12비트, 나머지가 VPN이야.

32비트 가상 주소, 4KB 페이지의 경우:

비트 31 ........... 12 │ 11 ......... 0
       VPN(20비트)    │  오프셋(12비트)

변환:
  VPN → 페이지 테이블에서 PFN(물리 프레임 번호) 조회
  물리 주소 = (PFN << 12) | 오프셋

오프셋은 변환하지 않고 그대로 따라가. 페이지 안에서의 위치는 가상이든 물리든 똑같으니까. 페이지 테이블이 해 주는 일은 "가상 페이지 X는 물리 프레임 Y야" 한 줄 매핑일 뿐이야.

3. 페이지 테이블 엔트리(PTE)

페이지 테이블의 한 줄을 PTE라고 불러. PTE는 단순히 PFN만 들고 있는 게 아니라 여러 비트를 같이 가지고 있어. 흔히 보이는 비트들은 이래.

• 유효 비트(valid): 이 페이지가 실제로 매핑되어 있는지. 아니라면 접근 시 폴트.
• 존재 비트(present): 페이지가 메모리에 올라와 있는지, 아니면 디스크로 쫓겨났는지(스와핑 챕터에서 다시 등장).
• R/W 비트: 읽기 전용인지 쓰기도 가능한지.
• U/S 비트: 사용자 모드에서도 접근 가능한지, 커널 전용인지.
• 참조 비트(accessed), 더티 비트(dirty): 최근에 읽혔는지/쓰기가 일어났는지. 쫓아낼 페이지를 고를 때 단서로 써.

4. 페이지 테이블은 거대하다

페이징의 진짜 골칫거리는 페이지 테이블 자체의 크기야. 32비트 주소에 4KB 페이지면 한 프로세스당 2^20 = 약 100만 개의 PTE가 필요해. PTE 하나가 4바이트라면 한 프로세스당 4MB짜리 페이지 테이블이 통째로 메모리에 상주해야 한다는 뜻이지. 프로세스가 수백 개라면? 끔찍하지.

그리고 두 번째 문제는 속도야. 모든 메모리 접근마다 페이지 테이블을 한 번 읽어야 하니, 메모리를 두 번씩 만지는 셈이거든. 그대로 두면 너무 느려. 이 두 문제 — 크기와 속도 — 를 해결하는 게 다음 두 챕터의 주제야. 19장에서는 TLB로 속도를, 20장에서는 다단계 테이블로 크기를 잡지.

1. 두 번 읽는 비극

페이징을 액면 그대로 구현하면 메모리 한 번 읽기가 사실상 두 번 읽기로 뻥튀기 돼. 페이지 테이블을 보고, 그다음에 진짜 데이터를 읽으니까. 다단계 테이블을 쓰면 한 번 변환에 두세 번씩 메모리를 만져야 해서 더 끔찍해지지. 이대로는 가상 메모리가 너무 비싸.

다행히 우리에겐 거의 모든 시스템 설계의 만능 키가 있어. 캐시야. 자주 쓰는 변환 결과를 CPU 안에 캐싱해 두면 같은 페이지에 대한 변환은 즉시 답할 수 있어. 이 캐시의 이름이 TLB(Translation Lookaside Buffer)야. 한국어로 옮기면 어색하니 그냥 TLB라고 부르자.

2. TLB가 일하는 흐름

가상 주소가 들어오면 하드웨어가 가장 먼저 하는 일이 TLB를 뒤지는 거야. 만약 해당 VPN에 대한 매핑이 TLB에 있으면(TLB hit), 페이지 테이블은 거들떠보지도 않고 즉시 PFN을 얻어. 없으면(TLB miss), 그제서야 페이지 테이블을 따라가서 매핑을 찾고, 결과를 TLB에 채워 넣고, 다음번에는 빠르게 답하지.

가상주소 → VPN 추출 → TLB 조회
  ├─ hit  → PFN 즉시 사용 → 메모리 접근
  └─ miss → 페이지 테이블 워크
            ├─ 매핑 있음 → TLB 채우기 → 재시도
            └─ 매핑 없음 → 페이지 폴트(OS 개입)

이상적으로는 TLB에서 거의 다 처리돼서 페이지 테이블을 만질 일이 별로 없어. 우리가 짜는 프로그램이 보통 적은 수의 페이지 안에서 한참 머무는 경향이 있기 때문이야. 이런 경향을 지역성(locality)이라고 하지.

3. miss는 누가 처리하나

TLB miss가 났을 때 누가 페이지 테이블을 뒤져 TLB를 채울지에 대한 두 가지 학파가 있어.

• 하드웨어 워킹: 하드웨어가 직접 페이지 테이블의 형식을 알고 있고, miss가 나면 알아서 따라간다. x86이 대표적이야. 빠르지만 페이지 테이블 형식이 하드웨어에 묶인다는 단점이 있어.
• 소프트웨어 워킹: TLB miss 시 트랩이 발생해 OS가 처리한다. MIPS 같은 RISC 계열에서 이 길을 갔지. OS가 페이지 테이블 형식을 자유롭게 정할 수 있다는 유연함이 있어.

요즘 대세는 하드웨어 워킹이지만, 소프트웨어 방식의 사상은 운영체제 설계자에게 더 많은 자유를 주는 매력이 있어.

4. 컨텍스트 스위치라는 함정

한 가지 미묘한 문제가 있어. TLB는 가상 주소를 가지고 있지만, 가상 주소는 프로세스마다 의미가 달라. 프로세스 A의 VPN 5와 프로세스 B의 VPN 5는 서로 다른 데이터를 가리켜. 그러니 컨텍스트 스위치가 일어나면 TLB의 내용이 갑자기 거짓말이 되지.

가장 단순한 해결책은 스위치 시 TLB를 통째로 비우는 거야. 안전하지만, 스위치 직후에 TLB miss가 폭발적으로 일어난다는 단점이 있지. 더 나은 방법은 각 TLB 엔트리에 ASID(Address Space ID)를 붙이는 거야. 일종의 프로세스 식별자지. 같은 VPN이라도 ASID가 다르면 다른 매핑으로 취급하니까, 비울 필요 없이 공존할 수 있어.

그리고 또 하나, 페이지 테이블이 변경됐을 때(예: 페이지를 매핑 해제했을 때) 그 변경이 TLB에 반영되지 않으면 옛날 매핑이 그대로 남아 사고가 나. 그래서 OS는 매핑 변경 시 해당 TLB 엔트리를 무효화(invalidate)하는 명령을 명시적으로 내려야 해. 멀티코어에서는 이걸 모든 코어에 전파해야 하는데, 이걸 TLB shootdown이라고 부르고 꽤 비싸.

1. 큰 표 하나의 문제

18장에서 본 단일 단계 페이지 테이블의 가장 큰 약점은, 비어 있는 영역에 대해서도 PTE 자리를 만들어 둬야 한다는 점이야. 보통 프로세스의 주소 공간은 코드 조금, 데이터 조금, 힙 일부, 스택 일부만 쓰고 가운데 어마어마한 빈 공간이 있거든. 그 빈 공간의 PTE까지 통째로 들고 있는 건 낭비지.

그래서 사람들이 떠올린 발상이 "표를 또 페이지 단위로 잘라 보자"였어. 안 쓰는 부분의 표는 아예 메모리에 만들지도 말고, 필요할 때만 채우는 거지.

2. 다단계 테이블의 구조

2단계 테이블을 보자. 가상 주소의 VPN을 둘로 더 쪼개. 위쪽 비트는 페이지 디렉터리(PD) 안에서의 인덱스, 아래쪽은 페이지 테이블(PT) 안에서의 인덱스로 쓰는 거지. 페이지 디렉터리의 한 칸은 어느 페이지 테이블이 어디 있는지를 가리켜.

가상 주소: │ PD 인덱스 │ PT 인덱스 │ 오프셋 │

CR3(레지스터)
   ↓
┌──────────┐
│ Page Dir │  → 각 칸은 한 PT의 위치(또는 비어 있음)
└──────────┘
   ↓
┌──────────┐
│ PageTable│  → 각 칸은 PTE
└──────────┘
   ↓
물리 프레임 + 오프셋

가상 주소 공간 중 사용 안 하는 영역에 해당하는 PD 칸은 비어 있다고 표시해 두면 돼. 그러면 그 영역의 PT는 아예 만들지 않아도 되니까 메모리가 절약되지. 사용하는 영역만 PT를 만들면 되니, 희소(sparse)한 주소 공간에서 효과가 커.

3. 공간을 절약한 대가

공짜 점심은 없어. 다단계로 가면 한 번의 변환에 메모리 접근이 더 많이 필요해. 2단계라면 PD 한 번, PT 한 번, 그리고 진짜 데이터 한 번 — 총 세 번이지. 64비트에서 흔히 쓰는 4단계 테이블은 PD 워크에만 네 번이 들어. 그래서 TLB의 도움이 더더욱 중요해져.

다단계의 또 다른 장점도 있어. 표 자체를 페이지 단위로 자르면, 페이지 테이블의 일부를 메모리에 두지 않고 디스크로 쫓아낼 수도 있어. 진짜로 큰 가상 공간을 다룰 때 의미가 있는 옵션이지.

4. 다른 길들: 역 페이지 테이블과 해시

다단계 말고도 다른 접근들이 있어.

• 역 페이지 테이블(inverted page table): 가상 페이지마다 한 줄이 아니라, 물리 프레임마다 한 줄을 둬. 그리고 각 줄에 "이 프레임이 어느 프로세스의 어느 가상 페이지냐"를 적어. 표 크기가 물리 메모리에 비례해서 작아지지만, 검색이 어려워서 보통 해시를 곁들여 써.
• 해시 페이지 테이블: VPN을 해싱해서 PTE를 찾는 방식. 충돌 처리가 추가로 필요해.

현실에서 가장 흔한 건 역시 다단계지만, 시스템마다 트레이드오프가 다르니까 다른 옵션도 알아 두면 좋아.

5. 64비트의 계단식 행렬

64비트 환경에서는 가상 주소가 너무 길어서 한두 단계로는 어림도 없어. 그래서 보통 4단계나 5단계 트리로 짠 페이지 테이블을 써. 리눅스에서 흔히 보는 PGD, PUD, PMD, PT 같은 약자들이 바로 그 단계들이야. 이 깊은 트리를 매번 따라가면 너무 느릴 것 같지만, 그 비용을 거의 다 가려 주는 친구가 있지. 19장에서 만난 TLB야. TLB hit이 잘 나는 한, 다단계의 깊이는 보이지 않는 곳에서만 일을 해.

1. 메모리는 작고, 욕심은 크다

가상 주소 공간을 통해 우리는 각 프로세스에게 큰 우주를 주겠다고 약속했어. 그런데 실제 물리 메모리는 그렇게 크지 않아. 100개 프로세스가 각자 4GB짜리 우주를 갖겠다고 하면? 합치면 400GB지만 우리에겐 16GB짜리 RAM밖에 없을 수도 있지.

해결책은 옛날부터 똑같았어. 자주 안 쓰는 페이지는 디스크 같은 더 느리고 큰 저장소로 잠시 옮겨 두고, 필요할 때 다시 메모리로 가져오는 거지. 이걸 스와핑(swapping) 또는 페이지 교체라고 해. 이렇게 디스크 위에 추가로 마련된 영역을 스왑 공간(swap space)이라고 부르고.

2. PTE의 존재 비트와 페이지 폴트

페이지가 메모리에 있을 수도, 디스크에 있을 수도 있다는 사실을 다루기 위해 PTE에는 존재 비트(present bit)가 있어. 이 비트가 켜져 있으면 페이지가 메모리에 있다는 뜻이고, 꺼져 있으면 디스크 어딘가에 있다는 뜻이야. 두 번째 경우, PTE의 나머지 비트들은 PFN 대신 디스크 위 위치(스왑 슬롯 번호 같은 것)를 담는 데 재활용돼.

존재 비트가 꺼진 페이지에 누가 접근하면 어떻게 되냐고? 하드웨어가 페이지 폴트를 일으키지. 그러면 OS가 끼어들어 다음 일들을 해.

1. PTE를 보고 페이지가 디스크 어디에 있는지 알아낸다.
2. 비어 있는 물리 프레임을 하나 잡는다. 없으면 누군가를 쫓아낸다(이건 22장 주제).
3. 디스크에서 해당 페이지를 그 프레임으로 읽어 온다.
4. PTE를 갱신해서 이제 메모리에 있다고 표시하고 PFN을 적는다.
5. 실패했던 명령어를 다시 실행시킨다. 이번에는 성공.

이 모든 일은 프로그램에게는 보이지 않아. 그저 그 명령어가 평소보다 좀 느렸을 뿐이지. 다만 디스크 접근은 메모리보다 수만 배 느리니까, 페이지 폴트가 너무 자주 나면 프로그램이 거의 멈춘 것처럼 보여.

3. 디스크 I/O 대기 동안 무얼 할까

페이지 폴트 처리 중 디스크에서 데이터를 가져오는 시간은 OS 입장에서는 영원처럼 길어. 그동안 CPU를 놀릴 수는 없으니, 폴트를 일으킨 프로세스를 블록 상태로 바꾸고 다른 프로세스를 스케줄링해. 디스크 I/O가 끝나면 인터럽트가 와서 OS에게 "그 페이지 가져왔어"라고 알려주고, 그제야 원래 프로세스를 깨워 재시도시키지. 이게 페이징의 또 다른 매력이야. 다른 프로세스들의 일과 자연스럽게 겹쳐 돌릴 수 있다는 점.

4. 언제 쫓아내는가: 워터마크

페이지 폴트가 났을 때 그제야 빈 프레임을 찾으려 하면 늦어. 그래서 OS는 보통 두 개의 임계값을 두고 미리미리 청소해. 가용 프레임 수가 LOW 워터마크 아래로 내려가면 백그라운드 데몬(리눅스의 kswapd 같은 친구)이 깨어나서 페이지를 디스크로 내보내, 가용 프레임이 HIGH 워터마크에 닿으면 다시 잠들지.

가용 프레임 수
   ▲
HI ┤────────●──────●──── 데몬 잠듦
   │       /        \
LO ┤──●───/          \─── 데몬 깨어남
   │  ↑
   └──┴──────────────────► 시간

이렇게 미리 비축해 두면 폴트가 났을 때 기다림 없이 즉시 빈 프레임을 줄 수 있어. 또 한꺼번에 여러 페이지를 묶어 디스크에 쓰면 디스크 효율이 좋아진다는 부수 효과도 있지.

1. 좋은 정책의 기준

스왑 정책의 목표는 단순해. 페이지 폴트를 적게 일으키는 거야. 디스크 접근은 메모리보다 압도적으로 느리니까, 폴트 한 번 줄이는 게 다른 모든 최적화보다 훨씬 큰 효과를 내거든. 그래서 우리는 평균 메모리 접근 시간(AMAT)을 분석에 자주 써.

AMAT = T_M + (P_miss × T_D)
  T_M : 메모리 접근 시간 (수십 나노초)
  T_D : 디스크 접근 시간 (수 밀리초)
  P_miss : 페이지 폴트 비율

T_D가 T_M보다 수만 배 크기 때문에, P_miss를 1%만 줄여도 평균 접근 시간이 크게 좋아져. 정책의 핵심은 P_miss를 어떻게 줄이느냐야.

2. 이상적인 정책: 가장 늦게 쓸 놈을 쫓아내라

이론적으로 가장 좋은 정책은 분명해. "앞으로 가장 오랫동안 안 쓸 페이지를 쫓아내라." 이걸 최적(optimal) 또는 MIN 정책이라고 불러. 미래를 알고 있다면 이게 최적이라는 게 증명돼 있어.

물론 우리는 미래를 모르지. 그래서 최적 정책은 직접 쓸 수 없어. 하지만 다른 정책이 얼마나 좋은지 평가할 때 기준선으로 쓰여. "이 정책이 최적에 비해 얼마나 못한가?" 이게 바로 우리가 던지는 질문이야.

3. 흔한 정책들

실제로 쓰이는 정책들을 보자.

• FIFO: 가장 먼저 들어온 페이지를 가장 먼저 쫓아낸다. 구현은 간단한데 결과는 종종 별로야. 자주 쓰이는 페이지도 그냥 들어온 순서대로 쫓겨날 수 있거든.
• 랜덤: 그냥 아무거나 쫓아낸다. 의외로 평균은 나쁘지 않지만, 운이 나쁘면 핵심 페이지를 날릴 수도 있어.
• LRU(Least Recently Used): 가장 오랫동안 안 쓰인 페이지를 쫓아낸다. "최근에 안 쓴 건 앞으로도 안 쓸 가능성이 높다"는 가정이지. 지역성을 잘 활용해서 보통 좋은 결과를 줘.
• LFU(Least Frequently Used): 가장 적게 사용된 페이지를 쫓아낸다. 일부 워크로드에 강하지만 옛날의 인기와 지금의 인기를 구분하기 어려워.

FIFO에는 또 한 가지 재미있는 함정이 있어. 어떤 워크로드에서는 메모리를 늘렸는데 오히려 폴트가 늘어나는 현상이 나타나거든. 이걸 벨라디의 변칙(Belady's anomaly)이라고 해. LRU 같은 스택 정책은 이런 변칙이 발생하지 않는다는 게 증명돼 있어.

4. 진짜 LRU는 비싸다, 그래서 시계로

LRU를 진짜로 구현하려면 모든 메모리 접근에 대해 어느 페이지가 언제 쓰였는지 추적해야 해. 하드웨어 도움 없이는 너무 비싸. 그래서 현실에서는 LRU의 근사를 써. 가장 유명한 게 시계(clock) 알고리즘이야.

아이디어는 단순해. 페이지들을 원형 배치로 늘어놓고 한 손이 시계처럼 돌아. 손이 가리키는 페이지의 참조 비트를 검사해. 비트가 1이면 0으로 만들고 손을 다음으로 넘겨. 비트가 0이면 그 페이지를 쫓아내. 이러면 최근에 쓰인 페이지는 한 바퀴 도는 동안 살아남고, 오래 안 쓰인 페이지가 자연스럽게 희생양이 돼. 진짜 LRU는 아니지만 비용이 훨씬 싸면서 거의 비슷한 효과를 내지.

      ┌─ A(1) ─┐
      B(0)     C(1)
      │         │
      H(1)     D(0)  ← 손이 여기 닿으면 D를 쫓아냄
      │         │
      G(0)     E(1)
      └─ F(1) ─┘
  (괄호 안: 참조 비트)

여기에 더티 비트를 곁들이면 더 좋아. 더티가 아니면 그냥 버리면 되지만, 더티이면 디스크에 다시 써야 해서 비싸. 그래서 가급적 깨끗한 페이지를 먼저 쫓아내려고 하지. 시계 알고리즘에 더티 비트를 더한 변형이 흔히 쓰여.

5. 트래싱과 워킹 셋

아무리 좋은 정책이라도 메모리가 절대적으로 부족하면 답이 없어. 모든 프로세스가 자주 쓰는 페이지를 합친 양이 물리 메모리보다 크면, 끝없이 페이지를 디스크에서 가져오고 다시 내보내는 일이 반복돼. 시스템이 거의 디스크 I/O만 하면서 일은 진행이 안 되지. 이걸 트래싱(thrashing)이라고 해.

해법은 결국 두 가지뿐이야. 메모리를 더 사거나, 일부 프로세스를 강제로 잠재워서 액티브 워킹 셋을 줄이는 거지. 이렇게 한 사이클 동안 자주 만지는 페이지 집합을 워킹 셋(working set)이라고 부르고, 이걸 의식한 정책들도 많아. 어떤 운영체제는 트래싱이 감지되면 일부 프로세스를 통째로 메모리 밖으로 내보내(스왑 아웃) 다른 프로세스가 살 만한 공간을 만들어 주기도 하지. 좀 잔인하지만 시스템 전체를 살리려는 결단이야.

1. 프로세스 안에 또 다른 흐름

지금까지는 한 프로세스가 하나의 흐름으로 코드를 위에서 아래로 차례차례 실행한다고 봐 왔어. 그런데 이 가정을 살짝 흔들어 보자. 같은 주소 공간을 공유하면서도, PC(program counter)와 스택, 그리고 레지스터 집합만 따로 가진 작은 실행 단위 — 이게 바로 쓰레드(thread)야. 같은 집에 사는 가족 구성원이라고 생각하면 쉬워. 거실(힙)과 부엌(전역 변수)은 같이 쓰지만, 각자 자기 방(스택)은 따로 쓰는 거지.

이 작은 변화가 가져오는 파급력은 생각보다 커. 멀티코어 CPU의 모든 코어를 한 프로그램이 동시에 활용할 수 있게 되고, I/O 같은 느린 작업을 기다리는 동안에도 다른 일을 진행할 수 있게 돼. 한 마디로 "기다림"과 "병렬"을 동시에 잡을 수 있다는 거야. 매력적이지?

2. 쓰레드가 만드는 새로운 풍경

운영체제 입장에서 쓰레드는 또 하나의 스케줄링 단위야. 컨텍스트 스위치도 일어나고, 레지스터를 저장하고 복원하는 절차도 있어. 다만 프로세스 전환과 다른 점이 있다면, 주소 공간을 통째로 바꾸지 않아도 된다는 거. 페이지 테이블을 갈아끼우는 비싼 작업이 빠지니까 상대적으로 가벼워. 쉽게 말해서, 쓰레드 전환은 같은 집 안에서 방만 옮기는 거고, 프로세스 전환은 아예 다른 집으로 이사 가는 거라고 보면 돼.

한 프로세스 안의 쓰레드들은 코드, 힙, 전역 변수를 모두 공유해. 즉, 한 쓰레드가 어떤 변수에 값을 쓰면 다른 쓰레드가 즉시 그 결과를 볼 수 있다는 뜻이지. 좋은 점이자 동시에 가장 무서운 점이야. 데이터를 공유하니까 통신이 빠르지만, 동시에 서로의 작업을 짓밟을 수도 있거든.

3. 첫 번째 충돌 — 단순한 카운터

가장 단순해 보이는 예제로 시작해 보자. 전역 변수 counter가 0이고, 두 쓰레드가 각각 이 값을 100만 번씩 1 증가시킨다고 하자. 직관적으로는 200만이 나와야 해. 그런데 막상 돌려보면? 어떤 날은 1,738,492, 어떤 날은 2,000,000, 어떤 날은 1,234,567 — 매번 다른 값이 나와.

// 두 쓰레드가 동시에 실행
for (int i = 0; i < 1000000; i++) {
    counter = counter + 1;
}

왜 이런 일이 일어날까? 우리는 counter = counter + 1을 한 줄짜리 명령으로 보지만, CPU는 이걸 보통 세 단계로 쪼개서 실행해. 메모리에서 값을 레지스터로 읽기(load), 레지스터 값을 1 증가(add), 그리고 다시 메모리에 쓰기(store). 이 세 단계 사이에 컨텍스트 스위치가 끼어들면 재앙이 시작돼.

4. 레이스 컨디션의 정체

쓰레드 A가 counter(=50)를 레지스터로 읽었어. 51로 증가시켰지. 그런데 store 직전에 스케줄러가 "잠깐, 다른 쓰레드 좀 돌릴게"라며 B로 넘겨버려. B도 똑같이 counter(=50)를 읽고 51로 만든 다음 메모리에 51을 쓰지. 그리고 A가 다시 깨어나서 자기가 들고 있던 51을 메모리에 써. 결과는? 분명히 두 번 증가시켰는데 counter는 51이야. 한 번이 통째로 사라진 거지.

이렇게 여러 흐름이 공유 자원에 접근하는 순서에 따라 결과가 달라지는 상황을 레이스 컨디션(race condition)이라고 불러. 그리고 이런 사고가 일어나는 코드 구간 — 동시에 실행되면 안 되는 영역 — 을 임계 영역(critical section)이라고 해. 임계 영역 안에서는 한 번에 한 쓰레드만 들어가야 한다는 성질을 상호 배제(mutual exclusion)라고 하고.

5. 그래서 우리에게 필요한 것

여기서 한 가지 결론이 나와. 우리에겐 임계 영역을 보호할 수 있는 어떤 장치가 필요해. 하드웨어가 제공하는 특별한 명령(예를 들면 test-and-set 같은)을 기반으로 만들어진 동기화 기본기(synchronization primitive)가 그거야. 락(lock)이 가장 대표적이고, 그 위에 조건 변수(condition variable), 세마포(semaphore) 같은 것들이 쌓여 있어.

또 하나 중요한 사실. 쓰레드끼리는 단순히 "동시에 같은 데이터를 만지면 안 된다" 차원의 문제만 있는 게 아니야. "B가 어떤 조건을 만족시켜 줄 때까지 A는 기다려야 한다" 같은 순서 문제도 있어. 예를 들어 부모 쓰레드가 자식 쓰레드의 작업이 끝날 때까지 기다리는 join이 그렇지. 이건 락만으론 못 풀어. 그래서 조건 변수가 따로 필요해.

6. 이 챕터의 미리보기

앞으로 우리가 다룰 주제를 살짝 정리해 보면 이래. 먼저 쓰레드를 어떻게 만들고 다루는지(API), 그리고 락은 어떤 원리로 만드는지(하드웨어 명령에서 시작해서 ticket lock, queue lock까지), 자료구조에 락을 어떻게 끼워 넣어야 성능을 잃지 않는지, 마지막으로 조건 변수를 활용한 기다림과 신호 패턴까지. 한 챕터씩 차근차근 들어가 보자. 동시성은 빨리 배우는 게 아니라, 자주 의심하고 자주 실험해서 익숙해지는 거야.

1. POSIX 쓰레드 — 표준이 된 친구

유닉스 계열에서 가장 널리 쓰이는 쓰레드 라이브러리는 pthread야. 이름 그대로 POSIX threads의 줄임말이지. 우리가 흔히 보는 함수들은 보통 pthread_라는 접두사를 달고 있어. 처음 보면 함수 이름이 길고 인자가 많아서 부담스럽지만, 핵심만 추리면 별거 없어. 만들고(create), 합치고(join), 잠그고(lock), 풀고(unlock), 기다리고(wait), 깨우고(signal). 이 여섯 동사가 90%야.

2. 쓰레드 만들기와 합치기

쓰레드를 만드는 함수는 이런 모양이야.

#include <pthread.h>

int pthread_create(pthread_t *thread,
                   const pthread_attr_t *attr,
                   void *(*start_routine)(void *),
                   void *arg);

네 개의 인자가 있어. 첫 번째는 새로 만들 쓰레드의 식별자를 받을 포인터, 두 번째는 스택 크기 같은 속성을 지정하는 포인터(보통 NULL을 줘), 세 번째는 이 쓰레드가 실행할 함수, 네 번째는 그 함수에 전달할 인자야. 함수의 시그니처가 void *를 받고 void *를 돌려주는 형태로 통일되어 있다는 점에 주목해. 어떤 타입이든 이 안에 욱여넣을 수 있게 하기 위한 일반화 트릭이야.

그리고 부모가 자식을 기다리는 함수는 pthread_join이야.

int pthread_join(pthread_t thread, void **value_ptr);

두 번째 인자는 자식 쓰레드의 반환값을 받을 포인터인데, 필요 없으면 NULL을 넘겨도 돼. 여기서 자주 하는 실수가 하나 있어. 자식 쓰레드에 인자를 넘길 때 부모 함수의 지역 변수 주소를 그대로 넘기는 경우야. 부모가 먼저 끝나버리면? 그 스택 프레임은 사라져. 자식이 그 주소를 읽으면 쓰레기 값이 나와. 굉장히 미묘하지. 그래서 인자는 보통 동적으로 할당하거나, 충분히 오래 사는 변수를 가리키게 만들어야 해.

3. 락 잠그기와 풀기

임계 영역을 보호하는 가장 기본적인 도구가 mutex야. 사용법은 단순해.

pthread_mutex_t lock = PTHREAD_MUTEX_INITIALIZER;

pthread_mutex_lock(&lock);
// 임계 영역
counter++;
pthread_mutex_unlock(&lock);

중요한 건 두 가지야. 첫째, mutex는 반드시 초기화되어야 해. 위처럼 매크로로 정적 초기화하거나, 동적이라면 pthread_mutex_init을 호출해야 해. 초기화 안 된 mutex를 잠그려고 하면 행동이 미정의(undefined)야. 둘째, lock과 unlock은 짝을 맞춰야 해. 잠그고 안 풀면? 다른 쓰레드는 영원히 기다려. 데드락 발생. 풀기만 두 번 하면? 라이브러리에 따라 행동이 다르지만 대개 좋지 않은 일이 생겨.

한 가지 더, 반환값을 무시하지 마. 락 함수도 실패할 수 있어. 메모리 부족, 잘못된 초기화, 데드락 감지 등으로. 실무에서는 보통 매크로나 래퍼 함수로 감싸서 실패 시 즉시 어설션을 터뜨리는 식으로 처리해. 디버깅에 절대적으로 유리해.

4. 조건 변수 — 기다림의 표준 도구

락만으로 안 되는 게 있어. "어떤 조건이 참이 될 때까지 기다리고 싶다"는 거. 그걸 위한 게 조건 변수야.

pthread_cond_t  cond  = PTHREAD_COND_INITIALIZER;
pthread_mutex_t lock  = PTHREAD_MUTEX_INITIALIZER;

// 기다리는 쪽
pthread_mutex_lock(&lock);
while (ready == 0)
    pthread_cond_wait(&cond, &lock);
pthread_mutex_unlock(&lock);

// 깨우는 쪽
pthread_mutex_lock(&lock);
ready = 1;
pthread_cond_signal(&cond);
pthread_mutex_unlock(&lock);

여기 패턴이 좀 묘해. wait는 락을 잡은 채로 호출해. 그러면 wait 안에서 자동으로 락을 풀고 잠들어. 신호를 받고 깨어날 때 wait가 락을 다시 잡고 돌아와. 이 "락을 풀고 잠드는" 단계가 원자적이라는 게 핵심이야. 그렇지 않으면 풀고 잠들기 사이에 신호가 와서 영원히 못 깨는 사고가 나거든.

그리고 ready를 if가 아니라 while로 감싸는 거 보이지? 이게 정말 중요해. 신호가 와서 깨어났더라도, 다른 쓰레드가 먼저 자원을 가져갔을 수도 있고, 어떤 구현은 spurious wakeup(이유 없는 깨어남)도 있어. 그래서 깨어나면 조건을 다시 확인해야 안전해. 이 원칙은 거의 모든 OS, 모든 언어의 조건 변수 사용에 통하는 황금률이야.

5. 컴파일과 작은 함정들

pthread를 쓸 때 컴파일 시 -pthread 또는 -lpthread를 빼먹는 사람이 많아. 이거 안 붙이면 어떤 시스템에선 컴파일은 되는데 락이 사실상 동작 안 하는 식으로 무력화돼버리기도 해. 컴파일러가 pthread 활성 모드로 돌아가야 메모리 모델, 에러 코드 등이 제대로 잡히거든.

또 하나, 헤더에서 선언만 보고 동작을 추측하지 마. pthread 함수 대부분이 0(성공) 또는 양의 에러 코드(실패)를 반환해. errno를 안 쓴다는 점이 일반 시스템 콜과 달라. 처음 만나면 자주 헷갈리는 부분이야.

6. 다른 언어들의 쓰레드

요즘은 pthread 직접 호출보다 고수준 추상을 쓰는 경우가 더 많아. C++의 std::thread, Java의 Thread/ExecutorService, Go의 goroutine, Rust의 std::thread 같은 것들. 내부적으론 결국 OS의 쓰레드 메커니즘을 부르고 있지만, 안전성이나 사용성을 더 챙겨주지. Rust는 컴파일러가 데이터 레이스를 못 만들게 막아 버리는 게 압권이고, Go는 쓰레드가 아니라 채널로 소통하라는 철학을 들고 와. 다만 이런 고수준 도구를 잘 쓰려면 결국 밑바닥에서 무슨 일이 일어나는지를 알아야 해. 그래서 우리는 pthread로 시작하는 거야.

1. 락이 보장해야 하는 것

락은 그냥 "잠겼다/안 잠겼다"를 나타내는 변수가 아니야. 락이 진짜로 충족해야 하는 성질은 세 가지로 정리할 수 있어. 첫째, 상호 배제 — 락을 잡은 쓰레드만 임계 영역에 들어갈 수 있어야 해. 둘째, 공정성 — 한 쓰레드가 영원히 락을 못 잡고 굶주리는(starvation) 일이 없어야 해. 셋째, 성능 — 경쟁이 없을 때는 빠르고, 경쟁이 있을 때도 너무 비싸지 않아야 해. 이 셋을 동시에 만족시키는 게 의외로 까다로워.

2. 첫 시도 — 인터럽트 끄기

가장 단순한 발상은 이래. "그냥 임계 영역 동안 인터럽트를 꺼버리면 컨텍스트 스위치가 안 일어나니까 안전하지 않을까?" 단일 CPU에서는 그럴듯한 아이디어야. 그런데 이 방법엔 치명적인 결함이 있어. 첫째, 인터럽트를 끄려면 특권 명령이 필요하니 사용자 코드에서 못 해. 둘째, 사용자 코드가 임계 영역 안에서 무한 루프를 돌면 시스템 전체가 멈춰. 셋째, 멀티프로세서에서는 한 CPU의 인터럽트만 꺼도 다른 CPU에서 임계 영역에 진입할 수 있으니까 무용지물이야. 결론: 안 됨.

3. 두 번째 시도 — 단순 플래그

그럼 이렇게 해 볼까?

typedef struct { int flag; } lock_t;

void lock(lock_t *L) {
    while (L->flag == 1)
        ;            // 잠겨 있으면 빙빙 돌며 기다림
    L->flag = 1;     // 내가 잡음
}
void unlock(lock_t *L) {
    L->flag = 0;
}

코드만 보면 멀쩡해 보이지만, 정확히 우리가 카운터 예제에서 본 것과 같은 함정에 빠져 있어. flag를 읽고 1로 쓰는 그 사이가 원자적이지 않아. 두 쓰레드가 동시에 flag == 0을 읽고 둘 다 통과해서 둘 다 flag = 1을 써버릴 수 있어. 결국 둘 다 임계 영역에 들어가는 거지. 락이 락 역할을 못 하는 락. 좀 슬프지?

4. 하드웨어의 도움 — Test-and-Set

여기서 우리는 하드웨어에게 손을 내밀어. 현대 CPU는 "값을 읽으면서 동시에 새 값을 써넣는" 원자적 명령을 제공해. 그중 가장 유명한 게 test-and-set이야.

// 의사코드 — 실제 CPU에선 단일 명령으로 원자적 실행
int TestAndSet(int *ptr, int new_val) {
    int old = *ptr;
    *ptr = new_val;
    return old;
}

이걸 쓰면 가장 단순한 spin lock을 이렇게 만들 수 있어.

void lock(lock_t *L) {
    while (TestAndSet(&L->flag, 1) == 1)
        ;   // 누가 이미 잡고 있으면 빙빙 돈다
}
void unlock(lock_t *L) {
    L->flag = 0;
}

이제 진짜로 정확해. 두 쓰레드가 동시에 lock을 호출해도, test-and-set이 원자적이라서 둘 중 한 쓰레드만 0을 받아 진입해. 다른 한 쓰레드는 1을 받아서 계속 돌지. x86에는 xchg, 이전 시스템에서는 ll/sc 같은 명령이 비슷한 역할을 해.

5. Compare-and-Swap, 그리고 락프리의 세계

또 다른 강력한 명령이 compare-and-swap(CAS)이야. "현재 값이 기대값과 같으면 새 값으로 바꾸고, 그렇지 않으면 아무것도 안 한다"는 의미지.

int CompareAndSwap(int *ptr, int expected, int new_val) {
    int actual = *ptr;
    if (actual == expected)
        *ptr = new_val;
    return actual;
}

CAS는 락을 만들 수도 있고, 더 나아가서 락 자체를 안 쓰는 락프리(lock-free) 자료구조를 만드는 데도 쓰여. 예를 들어 락프리 스택의 push는 "현재 top을 읽고, 새 노드의 next를 거기에 연결한 다음, CAS로 top을 새 노드로 바꿔치기"하는 식으로 구현돼. 실패하면 다시 시도해. 락이 없는데도 정확성이 보장되는 마법 같은 세계지. 다만 ABA 문제 같은 미묘한 함정이 있어 그렇게 만만하진 않아.

6. 스핀 락 vs 블로킹 락

지금까지 본 락은 모두 스핀 락이야. 락이 잠겨 있으면 CPU를 점유한 채로 빙빙 도는 거지. 단일 CPU에서는 거의 재앙이야. 락을 잡고 있는 쓰레드는 스케줄링되지 못한 채 CPU를 다 빼앗기고, 락을 기다리는 쓰레드만 빙빙 돌면서 시간을 낭비하니까. 멀티 CPU에서도 임계 영역이 길면 비효율적이야. 100밀리초 동안 락을 들고 있는데, 그동안 다른 코어가 빙빙 돈다고 생각해 봐. 그냥 잠들었다가 깨우는 게 훨씬 낫지.

그래서 현실의 mutex는 보통 하이브리드야. 짧게 스핀하다가, 일정 시간 안에 락을 못 잡으면 블로킹 모드로 전환해 OS의 대기 큐에 들어가 잠들지. 그리고 락이 풀릴 때 OS가 깨워. 리눅스의 futex가 정확히 이 아이디어야. 사용자 공간에서 빠른 경로로 처리하다가 경쟁이 생기면 커널 호출로 잠드는 식이지.

7. 공정성 문제와 ticket lock

단순 test-and-set 락에는 공정성 문제가 있어. 운 나쁜 쓰레드는 락이 풀리는 순간마다 다른 쓰레드가 먼저 채가서 영원히 못 들어갈 수 있거든. 이걸 해결하는 우아한 방법이 ticket lock이야. 은행 번호표를 떠올리면 돼. 들어오는 순서대로 번호를 받고, 자기 번호가 호명될 때까지 기다리는 거지.

typedef struct {
    int ticket;   // 다음에 발급할 번호
    int turn;     // 지금 통과 중인 번호
} ticket_lock_t;

void lock(ticket_lock_t *L) {
    int my = FetchAndAdd(&L->ticket, 1); // 번호표 뽑기
    while (L->turn != my)
        ;
}
void unlock(ticket_lock_t *L) {
    L->turn += 1;
}

여기서는 fetch-and-add라는 또 다른 원자 명령이 등장해. 값을 더하면서 더하기 전 값을 반환하는 거야. 모든 쓰레드는 자기 번호를 받게 되고, turn이 자기 번호가 되는 순서대로 정확히 한 번씩 통과해. 굶주림이 없어진 거지. 깔끔하지?

8. 더 나은 대기 — 큐 기반 락

스핀 락의 또 다른 개선은 큐 기반 락이야. 락을 기다리는 쓰레드들이 그냥 같은 변수를 빙빙 도는 게 아니라, 자기만의 노드를 큐에 추가하고 그 노드의 플래그만 보면서 기다려. 락이 풀리면 큐의 다음 노드 플래그만 바꿔 그 쓰레드를 깨워. 이렇게 하면 캐시 일관성 트래픽이 확 줄어들고(자기 노드만 보니까), 공정성도 자연스럽게 보장돼. MCS 락이 대표적인 예야.

리눅스 커널에선 단순한 스핀 락에서 큐 스핀 락으로 옮겨갔어. 코어 수가 많아지면 단순한 스핀 락은 캐시 라인 한 줄을 두고 모든 코어가 싸우게 되는데, 이게 진짜 비싸거든. 큐 락은 이 비용을 코어 수에 무관하게 일정하게 만들어 줘.

9. 메모리 모델, 그리고 우리가 보는 것의 한계

마지막으로 한 가지 더. 현대 CPU와 컴파일러는 명령 순서를 마음대로 바꿔. 한 코어에서 보면 순서대로 실행되는 것 같지만, 다른 코어에서 보면 그렇지 않을 수 있어. 그래서 락 구현에는 메모리 배리어(memory barrier)가 필수적으로 들어가. "여기 위의 쓰기는 여기 아래의 읽기 전에 모두 보여야 한다"는 식으로 강제하는 거지. 다행히 pthread_mutex_lock 같은 표준 락은 이런 배리어를 내부적으로 처리해 주니까 우리는 신경 안 써도 되지만, 자기만의 락프리 알고리즘을 짜려면 메모리 모델을 깊이 이해해야 해. 이게 동시성 프로그래밍의 진짜 어려움이 시작되는 지점이야.

1. 가장 단순한 길 — 큰 자물쇠 한 개

자료구조에 동시성을 더하는 가장 쉬운 방법은 거대한 락 하나로 자료구조 전체를 감싸는 거야. 모든 함수의 시작에서 락을 잡고, 끝에서 풀어. 이걸 흔히 coarse-grained locking이라고 불러. 카운터를 예로 들어 보자.

typedef struct {
    int             value;
    pthread_mutex_t lock;
} counter_t;

void counter_inc(counter_t *c) {
    pthread_mutex_lock(&c->lock);
    c->value++;
    pthread_mutex_unlock(&c->lock);
}

정확성은 완벽해. 그런데 성능은? 코어가 2개일 때보다 16개일 때 더 빨라야 정상인데, 오히려 느려지는 일이 흔해. 왜? 모든 쓰레드가 락 하나를 두고 싸우니까. 락은 직렬화 지점이고, 직렬화 지점이 하나면 코어 수가 늘어도 거기서 막혀. 이른바 "확장성이 없다"는 상황이야.

2. 어림셈 카운터 — 더하기를 미루는 트릭

카운터처럼 단순한 자료구조도 코어가 많아지면 병목이 돼. 해결 아이디어 중 하나가 어림셈 카운터(approximate counter)야. 각 코어마다 자기만의 로컬 카운터를 두고, 보통은 거기에만 더해. 로컬 값이 어떤 임계치(threshold)에 도달하면 그제서야 전역 카운터에 합쳐 넣는 거지.

// 의사코드
void inc_local(int cpu) {
    local[cpu]++;
    if (local[cpu] >= S) {
        lock(global_lock);
        global += local[cpu];
        local[cpu] = 0;
        unlock(global_lock);
    }
}

전역 락을 잡는 빈도가 1/S로 줄어드니 경쟁이 확 줄어. 대신 어느 순간에 전역 값을 읽으면 정확한 값보다 약간 작을 수 있어 — 아직 합쳐지지 않은 로컬 값들이 있으니까. 그래서 "어림"이라는 이름이 붙은 거야. 정확도와 성능 사이의 트레이드오프를 S로 조절할 수 있다는 게 매력 포인트야.

3. 동시성 연결 리스트

연결 리스트 삽입을 동시성 안전하게 만들어 보자. 단순 버전은 이래.

void list_insert(list_t *L, int key) {
    node_t *n = malloc(sizeof(node_t));
    n->key = key;
    pthread_mutex_lock(&L->lock);
    n->next = L->head;
    L->head = n;
    pthread_mutex_unlock(&L->lock);
}

여기서 자주 하는 실수 두 가지. 하나는 malloc을 락 안에서 부르는 것 — 굳이 그럴 필요 없어. malloc은 자체적으로 안전하고, 임계 영역을 짧게 유지하는 게 더 중요해. 그래서 위에서는 malloc을 락 밖으로 뺐어. 다른 하나는 에러 경로에서 unlock을 빼먹는 거. 락 안에서 실패해서 일찍 반환하는 경우, 모든 경로에 unlock을 짝맞춰 넣어야 해. C에서는 goto fail 패턴이나 wrapper 매크로로 처리하는 게 흔해.

4. 손-맞잡기 락 — fine-grained의 시작

리스트 전체를 락 하나로 보호하면, 100만 개 노드의 리스트에서도 한 번에 한 작업만 가능해. 더 잘게 나눌 수 있을까? 가능해. 손-맞잡기(hand-over-hand) 락 또는 lock coupling이라고 불리는 기법이야. 노드마다 락을 두고, 순회할 때 "현재 노드의 락을 잡고, 다음 노드의 락을 잡은 뒤, 현재 노드의 락을 푸는" 식으로 진행해. 마치 손을 번갈아 잡으며 사다리를 오르는 것 같지.

이론적으로는 두 작업이 리스트의 다른 부분에 있으면 동시에 진행될 수 있어. 그런데 현실에서는 노드마다 락을 잡고 푸는 비용이 워낙 비싸서, 짧은 리스트에서는 오히려 큰 락 하나가 더 빠른 경우가 많아. 이게 동시성의 진짜 미묘한 부분이야. 이론적 동시성과 실제 성능은 다른 이야기야.

5. 동시성 큐

큐는 양 끝(머리와 꼬리)에서만 작업이 일어나니까, 머리 락과 꼬리 락을 따로 두는 게 자연스러워.

typedef struct {
    node_t *head, *tail;
    pthread_mutex_t head_lock;
    pthread_mutex_t tail_lock;
} queue_t;

void q_enqueue(queue_t *q, int v) {
    node_t *n = malloc(sizeof(node_t));
    n->v = v; n->next = NULL;
    pthread_mutex_lock(&q->tail_lock);
    q->tail->next = n;
    q->tail = n;
    pthread_mutex_unlock(&q->tail_lock);
}

이 디자인의 트릭은 더미 노드(dummy node)에 있어. 큐를 비어 있을 때도 머리와 꼬리가 항상 어떤 노드를 가리키게 더미를 하나 두면, 머리와 꼬리의 락이 같은 노드를 동시에 만질 일이 없어져. 그래서 enqueue와 dequeue가 진짜로 병렬 실행될 수 있어.

6. 동시성 해시 테이블

해시 테이블은 동시성과 천생연분이야. 버킷마다 락을 따로 두면, 다른 버킷에 매핑되는 키들은 서로 간섭 없이 작업할 수 있거든. 키들이 잘 분포되어 있다는 가정 아래 거의 선형에 가까운 확장성을 얻을 수 있어. 자바의 ConcurrentHashMap이 정확히 이런 구조를 사용해. 다만 해시 테이블 전체를 리사이즈해야 할 때가 까다로워. 모든 버킷의 락을 잡거나, 점진적 리사이즈 트릭을 써야 해.

7. 락프리, 그리고 그 너머

락을 줄이는 극단적 방향이 아예 락을 없애는 거야. 앞 챕터에서 본 CAS만으로 큐, 스택, 해시 테이블을 만들 수 있어. 락프리 자료구조의 매력은 어떤 쓰레드도 다른 쓰레드 때문에 영원히 막히지 않는다는 거야 — 즉, 락을 들고 있는 쓰레드가 죽거나 페이지 폴트로 사라져도 다른 쓰레드는 계속 진행할 수 있어. 운영체제 커널이나 실시간 시스템에서 특히 유용해.

대가는 명확해. 코드가 어렵고, ABA 문제, 메모리 회수(free 시점) 문제, 메모리 모델에 대한 깊은 이해가 필요해. 그리고 "락프리"가 항상 "더 빠르다"를 의미하지도 않아. 경쟁이 적은 환경에선 단순한 mutex가 더 빠르기도 해. 그래서 보통의 권장은 이래. 표준 라이브러리가 제공하는 자료구조를 먼저 쓰고, 측정하고, 정말로 병목이 되었을 때만 직접 락프리로 내려가라.

8. 정리하며

락 기반 동시성 자료구조의 설계는 결국 두 축의 줄다리기야. 락의 입자성(coarse vs fine)과 락의 구현(spin vs block, simple vs ticket vs MCS). 어떤 자료구조든 일단 큰 락 하나로 정확하게 만들고, 측정해서 병목을 찾고, 거기에 맞춰 나누는 게 현실적인 워크플로우야. 정확성이 먼저, 성능은 그 다음. 이 순서를 절대 바꾸지 마.

1. 락만으로는 부족한 이유

부모가 자식 쓰레드의 작업이 끝날 때까지 기다리는 상황을 상상해 봐. 단순한 발상으로는 이런 코드를 짤 수 있어.

volatile int done = 0;

void *child(void *arg) {
    // ... 작업 ...
    done = 1;
    return NULL;
}

void parent(void) {
    while (done == 0)
        ;   // 빙빙 돌면서 기다림
}

동작은 해. 그런데 두 가지 문제가 있어. 하나는 부모가 CPU를 잡아먹으며 빙빙 도니까 비효율적이라는 점. 자식이 5초 동안 일한다면 부모도 5초 동안 멍청하게 CPU를 태우고 있어. 다른 하나는 done 변수의 메모리 가시성과 컴파일러 최적화에 대한 가정이 너무 약하다는 점. volatile 같은 키워드만으로는 멀티코어에서 보장이 약해.

그래서 우리에겐 진짜 도구가 필요해. 그게 조건 변수야.

2. 조건 변수의 동작

조건 변수에는 세 가지 핵심 동작이 있어. wait, signal, broadcast. 그리고 항상 락과 짝을 이뤄. wait는 "지금 잠들고, 누가 깨워주면 일어날게"라는 뜻이고, signal은 "이 조건 변수에서 자고 있는 쓰레드 하나를 깨워라"라는 뜻이고, broadcast는 "전부 다 깨워라"라는 뜻이야.

pthread_mutex_t lock = PTHREAD_MUTEX_INITIALIZER;
pthread_cond_t  cond = PTHREAD_COND_INITIALIZER;
int done = 0;

void *child(void *arg) {
    pthread_mutex_lock(&lock);
    done = 1;
    pthread_cond_signal(&cond);
    pthread_mutex_unlock(&lock);
    return NULL;
}

void parent_wait(void) {
    pthread_mutex_lock(&lock);
    while (done == 0)
        pthread_cond_wait(&cond, &lock);
    pthread_mutex_unlock(&lock);
}

여기서 묘한 부분은 pthread_cond_wait야. 이 함수는 호출 순간 락을 풀고 잠들어. 그리고 누가 신호를 보내 깨어날 때, 락을 다시 잡고 돌아와. 락을 풀고 잠드는 그 사이가 원자적으로 처리돼. 그렇지 않으면 미묘한 사고가 나거든.

3. 왜 if가 아니라 while인가

조건을 검사할 때 if (done == 0) 가 아니라 while (done == 0)을 쓰는 이유는 정말 중요해. 세 가지 이유가 있어.

첫째, signal은 "어떤 쓰레드 하나는 깨워질 것이다"라고 약속할 뿐, "깨어났을 때 조건이 참이라는 것"을 약속하지 않아. 깨어난 쓰레드와 조건을 만족시킨 쓰레드 사이에 다른 쓰레드가 끼어들어 조건을 다시 거짓으로 만들 수 있어. 깨어나서 다시 확인하는 게 안전해.

둘째, spurious wakeup. 어떤 구현은 신호 없이도 wait가 종종 깨어나는 일이 있어. POSIX 규약은 이걸 명시적으로 허용해. 그래서 깨어났다는 사실 자체는 조건의 증거가 아니야.

셋째, broadcast로 여럿이 깨어나는 경우, 그중 하나만 진짜 일을 진행할 수 있고 나머지는 다시 자야 해. while 루프가 그걸 자연스럽게 처리해 줘.

그래서 조건 변수의 황금률은 이거야: wait는 항상 while 루프 안에서, 락을 잡은 채로.

4. 생산자-소비자 — 고전 중의 고전

조건 변수가 가장 빛나는 예제가 생산자-소비자(producer-consumer) 문제야. 생산자가 항목을 만들어 버퍼에 넣고, 소비자가 꺼내가. 버퍼가 가득 차면 생산자는 기다려야 하고, 비어 있으면 소비자가 기다려야 해. 단순한 한 칸 버퍼부터 시작해 보자.

int  buffer;
int  count = 0;
pthread_mutex_t mu  = PTHREAD_MUTEX_INITIALIZER;
pthread_cond_t  empty = PTHREAD_COND_INITIALIZER;
pthread_cond_t  full  = PTHREAD_COND_INITIALIZER;

void put(int v) {
    pthread_mutex_lock(&mu);
    while (count == 1)
        pthread_cond_wait(&empty, &mu);
    buffer = v;
    count = 1;
    pthread_cond_signal(&full);
    pthread_mutex_unlock(&mu);
}

int get(void) {
    pthread_mutex_lock(&mu);
    while (count == 0)
        pthread_cond_wait(&full, &mu);
    int v = buffer;
    count = 0;
    pthread_cond_signal(&empty);
    pthread_mutex_unlock(&mu);
    return v;
}

여기서 조건 변수 두 개를 따로 쓴 점에 주목해. 한 개로 합쳐 놓고 broadcast로 다 깨우면 동작은 하지만 비효율적이야. 생산자는 "버퍼가 비었다(empty)" 신호를 기다리고, 소비자는 "버퍼가 찼다(full)" 신호를 기다려. 신호의 의미가 다르면 변수를 분리하는 게 더 깔끔해.

5. 다중 생산자/소비자와 broadcast

생산자와 소비자가 여러 명일 때, signal 대신 broadcast가 필요한 경우가 생겨. 예를 들어 N칸 버퍼에 여러 소비자가 있고, 한 생산자가 한 항목을 추가했어. 만약 broadcast로 모든 소비자를 깨우면 그중 하나만 항목을 가져가고 나머지는 다시 잠들지. while 루프가 있으니까 안전해. 그런데 signal로 단 하나만 깨우면, 그 깨어난 쓰레드가 우연히 잘못된 종류였을 때 진전이 안 일어날 수 있어. 그래서 "내가 누굴 깨우는지 정확히 모르겠을 땐 broadcast"가 안전한 기본값이야. 다만 broadcast는 thundering herd라고 불리는, 모두가 동시에 깨어나 락을 잡으려 몰려드는 비용이 있어. 가능하면 조건 변수를 잘 나눠서 signal로 충분하게 만드는 게 더 좋아.

6. Mesa vs Hoare 시맨틱스 — 깨어남의 두 철학

조건 변수에는 역사적으로 두 가지 의미론이 있어. Hoare 시맨틱스는 "신호를 받은 쓰레드가 즉시 실행되고, 신호를 보낸 쓰레드는 그동안 멈춰 있다"는 거야. 즉, 신호를 받는 즉시 조건이 보장돼. 우아하지만 구현이 까다로워.

Mesa 시맨틱스는 "신호는 그냥 큐에 넣어 놓는 힌트다. 신호를 보낸 쓰레드는 계속 실행되고, 신호를 받은 쓰레드는 나중에 락을 다시 잡아 깨어난다"는 거야. 그 사이에 누가 끼어들 수 있어서 깨어난 시점에 조건이 거짓일 수 있어. 그래서 while 루프가 필수야.

현대의 거의 모든 구현 — pthread, Java, C# 등 — 은 Mesa 시맨틱스야. 우리가 앞에서 본 황금률 "wait는 while 안에서"가 바로 이 시맨틱스의 직접적 결과지. Hoare 시맨틱스는 형식적 증명에 편하지만 현실 시스템에선 거의 안 써.

7. 자주 만나는 함정들

조건 변수에서 가장 흔한 버그 다섯 가지를 정리해 볼게. 지나치다 싶을 정도로 자주 만나니까 외워둬도 좋아.

첫째, 락 없이 wait를 호출하기. wait는 락을 잡은 채로 호출해야 해. 안 그러면 행동이 미정의야.

둘째, 조건을 if로 검사하기. 앞에서 말한 그 이유들 때문에 while이어야 해.

셋째, 신호를 보내고 락을 안 풀기. 신호를 받은 쓰레드는 wait 안에서 락을 다시 잡으려고 해. 보낸 쪽이 락을 안 풀면 그 쓰레드는 못 깨어나.

넷째, 상태를 안 바꾸고 신호만 보내기. signal은 단지 잠든 쓰레드를 깨울 뿐이야. 깨어난 쓰레드는 어떤 상태가 참이 됐는지를 검사로 확인해야 하는데, 상태가 안 바뀌었으면 다시 잠들어. 결국 누군가 깨어나기는 했지만 진전은 없어.

다섯째, 두 종류 이상의 이벤트를 한 조건 변수로 처리하기. "버퍼가 찼다"와 "버퍼가 비었다"를 한 변수로 다루면 broadcast 폭발이 일어나. 이벤트 종류마다 변수를 따로 두는 게 좋아.

8. 세마포와 비교 — 한 줄짜리 미리보기

조건 변수와 함께 자주 등장하는 도구가 세마포(semaphore)야. 다음 챕터들에서 본격적으로 다룰 텐데, 한 줄로 요약하면 "내부 카운터를 가진 동기화 도구"야. 조건 변수와 달리 신호를 잃어버리지 않아. 0이 아닌 카운터로 저장되니까. 어떤 종류의 문제는 세마포로 더 우아하게 풀리고, 어떤 종류는 조건 변수가 더 자연스러워. 둘 다 도구함에 있어야 진짜 동시성 프로그래머야.

9. 마무리

조건 변수는 동시성에서 가장 미묘하지만, 한 번 마음속에 모델이 잡히면 굉장히 쓸모 있는 도구야. 락과 짝을 이루고, 상태 변수와 함께 살고, while 루프 안에서 기다리고, 상태를 바꾼 후에 신호를 보낸다 — 이 네 가지 원칙만 지키면 대부분의 사고를 피할 수 있어. 동시성 코드는 "신호와 기다림을 어떻게 안전하게 끼워 넣을 것인가"라는 질문의 연속이야. 그 질문에 답하는 첫 번째 도구가 바로 조건 변수야. 다음 챕터에선 이 위에 세마포를 얹어 보자.

1. 세마포어, 일단 정의부터

세마포어(semaphore)는 본질적으로 정수 하나에 두 개의 원자적 연산을 묶어놓은 객체다. 만든 사람은 다익스트라(Dijkstra)로 알려져 있고, 네덜란드어로 P와 V라는 약어를 쓰는 전통이 있는데 우리는 그냥 POSIX 스타일대로 sem_wait와 sem_post로 부르자. 외울 게 늘어나는 건 사양이다.

초기화는 이렇게 한다.

#include <semaphore.h>

sem_t s;
sem_init(&s, 0, 1);  // 두 번째 인자 0은 "프로세스 간 공유 X"
                       // 세 번째 인자가 초기값

핵심은 두 연산이다. sem_wait()는 값을 1 줄이는데, 만약 결과가 음수가 되면 깨어날 때까지 잠든다. sem_post()는 값을 1 올리고, 자고 있던 누군가가 있으면 깨운다. 둘 다 원자적이라는 점이 가장 중요한 약속이다.

이 단순한 정의로부터 락도, 조건 변수도, 생산자-소비자도, 독자-작가도, 다 만들 수 있다는 게 세마포어의 매력이다. 마치 만능 도구처럼 들리지만, 실제로는 양날의 검이라는 사실은 잠시 후에 짚어보자.

2. 이진 세마포어 = 락의 사촌

가장 단순한 사용법부터 보자. 세마포어를 1로 초기화하면 그게 곧 락이다. 한 명이 들어가면 0이 되고, 다음 사람은 0에서 1을 빼면서 잠든다. 들어갔던 사람이 post하면 잠든 사람이 깨어나 들어간다. 이렇게 0과 1만 오가는 세마포어를 이진 세마포어(binary semaphore)라고 부른다.

sem_t mutex;
sem_init(&mutex, 0, 1);

sem_wait(&mutex);
// 임계 구역
shared_counter++;
sem_post(&mutex);

락이랑 거의 똑같지 않냐고? 거의 똑같다. 다만 락은 "잠근 쓰레드만 풀 수 있다"는 소유권 개념이 있는 반면, 세마포어는 누가 post하든 상관없다. 이게 나중에 동기화 패턴을 짤 때 의외로 유용해지는데, 동시에 락보다 실수하기도 쉽다는 뜻이기도 하다.

근데 이게 왜 동작하는지 한 번 더 짚고 가자. 세마포어가 락 역할을 할 수 있는 건, 값이 양수일 때는 그냥 통과하고 음수가 될 위기에 처하면 잠든다는 단순한 규칙 덕분이다. 카운터가 진입 권한의 개수처럼 행동하기 때문에, 1로 시작하면 동시에 한 명만 들어갈 수 있는 셈이다.

3. 카운팅 세마포어 — 자원이 여러 개일 때

그럼 초기값을 N으로 두면 어떻게 될까. 동시에 N개의 쓰레드가 들어갈 수 있는 구역이 만들어진다. 이걸 카운팅 세마포어(counting semaphore)라고 부른다. 자원의 개수가 정해진 상황, 예를 들어 DB 커넥션 풀이 5개라거나, 동시 다운로드를 3개로 제한하고 싶다거나 하는 시나리오에 맞춤이다.

sem_t pool;
sem_init(&pool, 0, 5);  // 동시 5명까지

void worker() {
    sem_wait(&pool);
    use_connection();
    sem_post(&pool);
}

이게 락만으로 어색하게 흉내낼 수 있긴 하다. 카운터 변수와 락, 조건 변수까지 동원해서 "5보다 작으면 들어가고 아니면 기다려" 패턴을 짤 수 있겠지. 근데 세마포어 한 줄로 끝나는 걸 굳이 그렇게 할 이유가 있을까. 도구는 적재적소다.

4. 순서 강제하기 — 0으로 초기화하는 트릭

세마포어를 1로 두면 락, N으로 두면 자원 카운터. 그럼 0으로 두면? 이게 의외로 강력하다. 누군가 post해주기 전까지는 무조건 잠드는 게이트가 되기 때문이다.

예를 들어 부모 쓰레드가 자식이 끝날 때까지 기다리고 싶다고 하자.

sem_t done;
sem_init(&done, 0, 0);  // 초기값 0

void *child(void *arg) {
    do_work();
    sem_post(&done);   // "나 끝났어"
    return NULL;
}

int main() {
    pthread_t t;
    pthread_create(&t, NULL, child, NULL);
    sem_wait(&done);   // 자식이 끝날 때까지 블록
    printf("자식 종료 확인\n");
}

부모가 먼저 wait에 도달하면 0에서 -1로 가야 하니 잠든다. 자식이 post하면 깨어나 진행한다. 반대로 자식이 먼저 post해도 값이 1이 되어 있다가 부모가 wait할 때 그냥 통과한다. 어느 순서로 도착하든 항상 자식이 끝난 뒤에 부모가 진행하는 게 보장된다. 이게 0 초기화 세마포어의 마법이다.

5. 생산자-소비자 — 빈 칸과 찬 칸

이제 본격적인 응용으로 가자. 큐에 데이터를 넣는 생산자와 빼가는 소비자가 있다. 큐 크기는 N. 우리에게 필요한 건 두 가지 동기화다. 첫째, 생산자는 큐가 가득 차면 멈춰야 한다. 둘째, 소비자는 큐가 비면 멈춰야 한다. 그리고 큐 자체에 대한 상호배제도 있어야 한다.

여기서 세마포어 두 개를 다른 의미로 쓰는 게 핵심이다. 하나는 "남아있는 빈 칸 수", 또 하나는 "찬 칸 수". 그리고 임계 구역 보호용 이진 세마포어 하나.

#define N 10
int buffer[N];
int fill = 0, use = 0;

sem_t empty;  // 빈 슬롯 수
sem_t full;   // 찬 슬롯 수
sem_t mutex;  // 버퍼 보호용

void init() {
    sem_init(&empty, 0, N);  // 처음엔 다 비어있음
    sem_init(&full,  0, 0);
    sem_init(&mutex, 0, 1);
}

void put(int v) {
    sem_wait(&empty);    // 빈 칸 하나 점유
    sem_wait(&mutex);
    buffer[fill] = v;
    fill = (fill + 1) % N;
    sem_post(&mutex);
    sem_post(&full);     // 찬 칸 하나 늘었음
}

int get() {
    sem_wait(&full);     // 찬 칸 하나 소비
    sem_wait(&mutex);
    int v = buffer[use];
    use = (use + 1) % N;
    sem_post(&mutex);
    sem_post(&empty);    // 빈 칸 하나 늘었음
    return v;
}

잠깐, 여기서 순서가 중요하다는 점을 짚자. sem_wait(&mutex)를 sem_wait(&empty)보다 먼저 하면 어떻게 될까? 큐가 가득 찼는데 생산자가 mutex를 잡고 그 다음 empty에서 잠들면, 소비자도 mutex 못 잡아서 큐를 못 비운다. 둘 다 영원히 잠. 전형적인 데드락이다. 자원 점유 순서는 농담거리가 아니다.

6. 독자-작가 락 — 공정함의 함정

읽기는 동시에 여러 쓰레드가 해도 안전하다. 쓰기는 혼자만 해야 한다. 이 비대칭을 살리고 싶을 때 쓰는 게 독자-작가 락(reader-writer lock)이다. 세마포어로 어떻게 만들까.

typedef struct _rwlock_t {
    sem_t lock;       // 카운터 보호
    sem_t writelock;  // 작가 진입 게이트
    int readers;      // 현재 읽고 있는 수
} rwlock_t;

void rwlock_init(rwlock_t *rw) {
    rw->readers = 0;
    sem_init(&rw->lock, 0, 1);
    sem_init(&rw->writelock, 0, 1);
}

void rwlock_acquire_readlock(rwlock_t *rw) {
    sem_wait(&rw->lock);
    rw->readers++;
    if (rw->readers == 1)
        sem_wait(&rw->writelock);  // 첫 독자가 작가 차단
    sem_post(&rw->lock);
}

void rwlock_release_readlock(rwlock_t *rw) {
    sem_wait(&rw->lock);
    rw->readers--;
    if (rw->readers == 0)
        sem_post(&rw->writelock);  // 마지막 독자가 작가 풀어줌
    sem_post(&rw->lock);
}

void rwlock_acquire_writelock(rwlock_t *rw) { sem_wait(&rw->writelock); }
void rwlock_release_writelock(rwlock_t *rw) { sem_post(&rw->writelock); }

독자가 끊임없이 도착하면 작가는 영원히 못 들어간다. 이게 독자 기아 현상이다. 해결책은 여러 갈래다. 작가가 대기 중일 때는 새 독자를 받지 않는다거나, 도착 순서대로 줄을 세운다거나. 근데 한 가지 분명한 사실. 모든 동기화 문제가 그렇듯, 공정함을 추가할수록 코드는 길어지고 성능은 떨어진다. 정말 독자가 압도적으로 많은 워크로드인지 먼저 확인해라. 일반 락이 더 빠른 경우가 의외로 흔하다.

7. 식사하는 철학자 — 데드락의 교과서

다섯 명이 둥근 식탁에 앉아있고, 각자 사이에 젓가락이 한 짝씩, 총 다섯 짝이 놓여있다. 한 그릇의 면을 먹으려면 양쪽 젓가락을 둘 다 잡아야 한다. 누가 봐도 부족하다. 이 시나리오를 세마포어로 바보같이 풀면 데드락에 빠지는 걸 직접 보여주는, 동시성 책의 단골이다.

sem_t fork[5];

void philosopher(int i) {
    while (1) {
        think();
        sem_wait(&fork[i]);             // 왼쪽 집기
        sem_wait(&fork[(i + 1) % 5]);   // 오른쪽 집기
        eat();
        sem_post(&fork[i]);
        sem_post(&fork[(i + 1) % 5]);
    }
}

모두가 동시에 왼쪽을 집으면, 모두가 오른쪽을 영원히 기다린다. 데드락의 표준 사례다. 해결 방법 중 하나는 한 명만 순서를 뒤집는 것. 마지막 철학자만 오른쪽을 먼저 집게 만들면 순환 대기가 깨진다.

void philosopher(int i) {
    while (1) {
        think();
        if (i == 4) {
            sem_wait(&fork[(i + 1) % 5]);
            sem_wait(&fork[i]);
        } else {
            sem_wait(&fork[i]);
            sem_wait(&fork[(i + 1) % 5]);
        }
        eat();
        sem_post(&fork[i]);
        sem_post(&fork[(i + 1) % 5]);
    }
}

한 줄짜리 변경으로 데드락이 사라진다. 세상의 많은 동시성 버그가 이런 식이라는 게 위안이자 비극이다. 깊은 통찰 한 줄이면 풀리는데, 그 한 줄을 못 봐서 며칠을 헤맨다.

8. 세마포어로 조건 변수 만들기, 그리고 그 반대도

락과 조건 변수 두 개의 기본기로 세마포어를 만들 수 있고, 세마포어로 락과 조건 변수를 흉내낼 수도 있다. 이론적 등가성. 그렇다고 두 도구가 동등하게 쉬운 건 아니다. 조건 변수의 wait는 항상 락과 함께 쓰고, 깨어났을 때 조건을 다시 확인하는 패턴이 강제된다. 세마포어는 그런 가드레일이 없어서 자유로운 만큼 실수도 자유롭다. 도구의 표현력과 안전성은 보통 반비례한다.

실무 권장은 단순하다. 상호배제만 필요하면 락. 어떤 조건이 만족될 때까지 기다려야 하면 조건 변수. 자원 카운트나 순서 신호처럼 "몇 개 있다"는 정수 의미가 자연스러우면 세마포어. 골라 쓸 수 있을 때 한 도구를 모든 곳에 쓰는 사람이 가장 위험하다.

1. 사건의 분포 — 의외의 통계

대규모 오픈소스 프로젝트의 동시성 버그를 분석한 연구들을 보면, 데드락보다 비-데드락 버그가 더 많다. 비율은 연구마다 다르지만 대체로 비-데드락 버그가 더 많거나 비슷하다. 이 사실은 우리에게 중요한 메시지다. 데드락은 잘 알려져 있어서 다들 경계하지만, 정작 더 자주 일어나는 건 "락은 다 잡았는데도 결과가 이상한" 버그들이라는 뜻이다.

비-데드락 버그는 다시 두 가지로 크게 나뉜다. 하나는 원자성 위반(atomicity violation), 다른 하나는 순서 위반(order violation). 이름은 거창하지만 실체는 단순하다. 그리고 단순한 만큼 자주 등장한다.

2. 원자성 위반 — "한 번에 끝났어야 하는데"

코드를 짠 사람의 머릿속에서는 "이 두 줄은 한 묶음"이었는데, 실행 환경은 그렇게 약속한 적이 없는 경우다. MySQL 코드베이스에서 발견된 패턴을 단순화해보자.

// Thread 1
if (thd->proc_info) {
    fputs(thd->proc_info, log);
}

// Thread 2
thd->proc_info = NULL;

1번 쓰레드가 if로 NULL이 아님을 확인한 직후, 2번 쓰레드가 NULL로 바꾼다. 1번이 다시 깨어나 fputs를 호출하면 그대로 NULL 역참조. 한 영역에 묶여 있어야 할 검사와 사용 사이에 다른 손이 끼어든 것이다. 흔히 TOCTOU(time-of-check to time-of-use)라고도 부르는 패턴의 동시성 판이다.

해결책은 단순하다. 검사와 사용 전체를 동일한 락으로 감싸면 된다. 그리고 proc_info를 수정하는 모든 코드가 같은 락을 쓰도록 강제한다. 이게 어려운 게 아니라, 코드가 커지면서 "이게 어떤 락이랑 묶여 있더라"가 흐려지는 게 어렵다.

3. 순서 위반 — "A가 먼저 끝났어야 하는데"

또 다른 단골은 순서가 보장되지 않은 채 의존성을 가진 코드다.

// Thread 1: 초기화 담당
void init() {
    mThread = PR_CreateThread(...);
}

// Thread 2: 새 쓰레드의 본체
void worker() {
    mState = mThread->State;  // mThread가 아직 안 만들어졌으면?
}

1번이 mThread를 만들기 전에 2번이 실행되면 NULL을 역참조한다. 락만 걸어서는 해결되지 않는다. 락은 "동시에 못 들어가" 보장이지 "누가 먼저 끝나" 보장이 아니다. 이런 경우엔 조건 변수나 세마포어로 명시적인 happens-before 관계를 만들어줘야 한다.

pthread_mutex_t m = PTHREAD_MUTEX_INITIALIZER;
pthread_cond_t  c = PTHREAD_COND_INITIALIZER;
int mtInitDone = 0;

void init() {
    mThread = PR_CreateThread(...);
    pthread_mutex_lock(&m);
    mtInitDone = 1;
    pthread_cond_signal(&c);
    pthread_mutex_unlock(&m);
}

void worker() {
    pthread_mutex_lock(&m);
    while (mtInitDone == 0)
        pthread_cond_wait(&c, &m);
    pthread_mutex_unlock(&m);
    mState = mThread->State;
}

플래그 변수와 조건 변수의 콤보다. 본질은 "초기화가 끝났다는 사실을 명시적으로 알려줘라"라는 것이다. 묵시적 가정을 코드에 박아넣지 마라.

4. 데드락의 네 가지 조건

데드락이 일어나려면 다음 네 가지가 동시에 성립해야 한다. 이게 무너지면 데드락은 안 생긴다. 정리해두면 진단할 때 체크리스트로 쓸 수 있다.

• 상호배제(mutual exclusion): 자원은 한 번에 하나의 쓰레드만 쓸 수 있다.
• 점유와 대기(hold-and-wait): 어떤 자원을 잡은 채 다른 자원을 기다린다.
• 비선점(no preemption): 강제로 자원을 빼앗을 수 없다.
• 순환 대기(circular wait): A는 B를 기다리고 B는 C를, 그리고 결국 누군가 A를 기다리는 구조가 만들어진다.

네 개가 모두 만족돼야 한다는 건 곧, 하나만 깨뜨려도 데드락은 못 일어난다는 뜻이다. 예방 전략은 이 네 항목 중 어떤 걸 깨뜨릴지 고르는 일이다.

5. 데드락 예방 전략들

순환 대기 깨기 — 락 순서 정하기. 가장 자주 쓰이는 방법이다. 모든 락에 전역 순서를 매기고, 항상 낮은 번호부터 잡는다. 그러면 사이클이 생길 수 없다. 락이 주소로 비교 가능하다면 주소 기준으로 자동화하기도 좋다.

void transfer(account_t *a, account_t *b, int amt) {
    account_t *first  = (a < b) ? a : b;
    account_t *second = (a < b) ? b : a;
    pthread_mutex_lock(&first->lock);
    pthread_mutex_lock(&second->lock);
    a->balance -= amt;
    b->balance += amt;
    pthread_mutex_unlock(&second->lock);
    pthread_mutex_unlock(&first->lock);
}

점유와 대기 깨기 — 한 번에 다 잡기. 모든 필요한 락을 미리 한꺼번에 잡고, 그동안은 새 락을 추가로 잡지 않는다. 단순하지만 모든 락 후보를 미리 알아야 하고, 동시성을 떨어뜨린다. 큰 시스템에서는 비현실적인 경우가 많다.

비선점 깨기 — trylock 패턴. pthread_mutex_trylock으로 시도해보고, 실패하면 갖고 있던 걸 모두 풀고 다시 시작한다. 이걸 잘못 쓰면 라이브락(livelock) — 두 쓰레드가 양보만 무한히 반복하는 상황 — 이 생긴다. 무작위 백오프를 섞어주면 완화된다.

top:
    pthread_mutex_lock(&L1);
    if (pthread_mutex_trylock(&L2) != 0) {
        pthread_mutex_unlock(&L1);
        usleep(rand() % 100);
        goto top;
    }
    /* ... */

상호배제 깨기 — lock-free 자료구조. 가장 야심찬 방향이다. 원자 연산(compare-and-swap 등)으로 락 자체를 제거한다. 빠르고 데드락 프리지만, 제대로 짜기가 정말 어렵다. 본인이 대학원생이거나 시간이 많지 않다면 검증된 라이브러리를 써라.

6. 데드락 회피 — 동적인 접근

예방이 정적인 규칙이라면, 회피(avoidance)는 실행 시점에 "이 락을 지금 줘도 안전한가?"를 매번 검사하는 방식이다. 은행원 알고리즘(banker's algorithm)이 대표적인데, 시스템 전체의 자원 요청 그래프를 매번 갱신해야 해서 오버헤드가 크다. 실제 OS 코드에서 쓰이는 경우는 드물고, 학문적으로 의미가 더 크다.

실무에서는 보통 예방 쪽으로 간다. 회피는 문제 자체를 피하는 게 아니라 매번 검사하는 비용을 감수하는 셈이라, 락이 빈번한 코어 경로에선 받아들이기 어렵다.

7. 데드락 탐지와 복구

예방도 회피도 안 하면, 남은 옵션은 "일단 일어나게 두고 발견하면 부순다"이다. 자원 할당 그래프에서 사이클을 찾아 데드락을 탐지하고, 한쪽 쓰레드를 강제로 종료하거나 트랜잭션을 롤백해서 복구한다. 데이터베이스가 이런 식으로 동작한다. SELECT ... FOR UPDATE가 서로 엮여 데드락이 나면, DB는 한쪽을 victim으로 골라 트랜잭션을 무효화한다.

OS 커널은 보통 이 정도 사치를 못 누린다. 커널은 멈추면 시스템이 멈춘다. 그래서 커널 코드에선 처음부터 데드락이 안 생기게 짜는 정적 규칙을 더 선호한다. 코드 리뷰 단계에서부터 락 순서가 검사된다.

8. 그래도 가장 좋은 건 락을 줄이는 것

모든 동기화 버그의 가장 깔끔한 해결책은 동기화를 안 하는 것이다. 무슨 황당한 소리냐고? 진심이다. 공유 데이터를 줄이고, 가능하면 데이터를 쓰레드별로 분리하고, 변경 불가능한 자료구조를 쓰면 락 자체가 필요 없어진다. 락이 없으면 데드락도 없고 원자성 위반도 없다.

현대 시스템 설계에서 메시지 전달, 액터 모델, 함수형 자료구조 같은 패러다임이 인기 있는 이유다. 공유를 최소화한 설계는 디버깅이 쉽다. 락을 화려하게 쓰는 코드보다, 락을 안 쓰게 만든 코드가 보통 더 똑똑한 코드다.

그렇다고 락이 사라지는 건 아니다. OS 커널은 본질적으로 공유 자원의 집합이고, 어딘가에는 결국 락이 필요하다. 다만 우리가 락을 어디에 두느냐의 설계 결정이 시스템의 성격을 결정한다. 락은 약이지만, 약이 너무 많으면 그게 곧 병이다.

1. 다른 길이 있다 — 이벤트 루프

지금까지 우리는 동시성을 "여러 쓰레드"의 관점으로 봤다. 그런데 또 다른 모델이 있다. 단일 쓰레드 안에서 이벤트를 받아 처리하고, 그 처리 중에 블로킹 작업이 필요하면 등록만 해두고 다음 이벤트로 넘어가는 방식. 이게 이벤트 기반 동시성이다.

구조 자체는 놀랍도록 간단하다. 의사코드로 적으면 이렇다.

while (1) {
    events = waitForEvents();
    for (e in events) {
        processEvent(e);
    }
}

전부다. 메인 쓰레드는 이벤트가 들어올 때까지 기다리다가, 들어오면 핸들러를 부르고, 끝나면 다시 기다린다. 무한 루프 한 줄에 모든 게 들어있다. 이걸 이벤트 루프(event loop)라고 부른다. Node.js, nginx, Redis, 브라우저의 자바스크립트 엔진, 거의 모든 GUI 프레임워크가 이 패턴이다.

2. select와 poll — 첫 세대 다중화

이벤트 루프가 동작하려면 핵심 능력이 하나 필요하다. "여러 파일 디스크립터 중 어느 하나라도 데이터가 들어오면 알려줘"라고 OS에 요청할 수 있어야 한다. 이게 I/O 다중화(multiplexing)이고, 가장 오래된 인터페이스가 select다.

#include <sys/select.h>

fd_set readfds;
FD_ZERO(&readfds);
FD_SET(server_fd, &readfds);
FD_SET(client_fd, &readfds);

struct timeval tv = {5, 0};
int n = select(maxfd + 1, &readfds, NULL, NULL, &tv);

if (n > 0) {
    if (FD_ISSET(server_fd, &readfds)) accept_new_client();
    if (FD_ISSET(client_fd, &readfds)) read_from_client();
}

읽기 집합, 쓰기 집합, 예외 집합을 비트맵으로 넘기고, 그 중 하나라도 준비되면 돌아온다. 단순하지만 한계가 있다. 비트맵 크기가 컴파일 시점에 정해져 있고(보통 1024), 매번 호출할 때마다 전체 집합을 커널에 복사한다. 디스크립터가 많아지면 그게 다 비용이다.

poll은 비트맵 대신 배열을 쓰고 1024 한계가 없지만, 본질적인 O(N) 스캔은 그대로다. 컴퓨터 한 대가 클라이언트 만 명을 동시에 받아야 하는 시대가 오자, 이 방식의 비효율이 문제가 됐다. 1999년쯤 이른바 C10K 문제다.

3. epoll, kqueue — 다음 세대

해결책은 "관심 있는 디스크립터 목록을 매번 넘기지 말고, 커널에 등록만 해두고 변경분만 전달받자"는 발상이었다. 리눅스의 epoll, BSD/Mac의 kqueue가 그 결과물이다.

#include <sys/epoll.h>

int epfd = epoll_create1(0);

struct epoll_event ev;
ev.events = EPOLLIN;
ev.data.fd = server_fd;
epoll_ctl(epfd, EPOLL_CTL_ADD, server_fd, &ev);

struct epoll_event events[64];
int n = epoll_wait(epfd, events, 64, -1);
for (int i = 0; i < n; i++) {
    handle(events[i].data.fd);
}

한 번 등록해두면 이후엔 준비된 fd 목록만 받는다. O(N)이 사실상 O(준비된 개수)로 줄어든다. 동시 접속 수가 만 명이어도 그 순간 데이터가 온 fd가 백 개라면 백 개만 받는다. 이걸로 단일 쓰레드 서버가 수만 개의 연결을 다룰 수 있게 됐다.

4. 핵심 규칙 — 절대 블록되지 마라

이벤트 루프가 빨라지려면 한 가지 절대 규칙이 있다. 핸들러 안에서 블로킹 호출을 하지 마라. 한 핸들러가 멈춰있는 동안 전체 이벤트 루프가 멈춘다. 단일 쓰레드라는 건 곧 단일 진행 흐름이라는 뜻이고, 그게 막히면 다른 클라이언트는 모두 함께 기다린다.

이건 단순한 조언이 아니라 시스템 전체의 정의다. 그래서 이벤트 기반 시스템에선 모든 I/O가 비동기여야 한다. 디스크 읽기, 네트워크 호출, DB 쿼리, 다 마찬가지다. read가 데이터를 기다리는 동안 멈추면 안 되고, "데이터 오면 콜백 불러줘"로 바뀌어야 한다.

그런데 여기서 함정이 하나 있다. 디스크 I/O는 의외로 블로킹이 흔하다. 네트워크 소켓은 O_NONBLOCK으로 비블로킹 모드를 쓸 수 있지만, 일반 파일 시스템 read는 페이지 캐시 미스가 나면 그냥 블록된다. 이걸 제대로 해결하려면 진짜 비동기 I/O가 필요하다.

5. 비동기 I/O — POSIX AIO와 io_uring

고전적인 답은 POSIX AIO(aio_read, aio_write)였다. API는 일찍 정의됐지만 구현이 들쭉날쭉했고, 리눅스에선 한참 동안 별로 좋지 않았다. 그래서 실무에선 별도의 워커 쓰레드 풀에 디스크 I/O를 떠넘기는 우회 기법이 흔히 쓰였다. "이벤트 기반인데 사실 뒤에 쓰레드가 있다"는 약간 부끄러운 비밀.

요즘 리눅스의 답은 io_uring이다. 사용자 공간과 커널 사이에 두 개의 ring buffer를 두고, 시스템 콜 없이 큐에 요청을 쌓고 결과를 회수한다. 진짜 비동기 디스크 I/O를 거의 처음으로 깔끔하게 제공한다. 새로 시작하는 고성능 서버라면 이쪽을 진지하게 검토할 가치가 있다.

// 개념만 — 실제로는 io_uring_prep_*, submit, wait_cqe 등을 사용
struct io_uring_sqe *sqe = io_uring_get_sqe(&ring);
io_uring_prep_read(sqe, fd, buf, len, offset);
io_uring_submit(&ring);
// ... 다른 일 ...
struct io_uring_cqe *cqe;
io_uring_wait_cqe(&ring, &cqe);  // 완료 회수

6. 콜백 지옥과 그 탈출구

이벤트 기반의 가장 유명한 단점은 콜백 지옥(callback hell)이다. 동기 코드라면 위에서 아래로 줄줄이 적었을 로직이, 콜백 안에 콜백 안에 콜백으로 들여쓰기가 점점 깊어진다.

// 동기였다면
data = read_file("a");
result = process(data);
write_file("b", result);

// 콜백이라면
read_file("a", function(data) {
    process(data, function(result) {
        write_file("b", result, function() {
            // 진짜 끝
        });
    });
});

구조적으로는 똑같은데 가독성이 무너진다. 게다가 한 흐름이 여러 콜백에 쪼개져 있으니 상태 변수를 따로 관리해야 한다. "현재 어디까지 진행됐지?"를 명시적으로 들고 다녀야 한다는 뜻이다. 이걸 manual stack management라고 비꼬는 사람도 있다. 컴파일러가 해줄 일을 사람이 하고 있으니까.

해결책으로 등장한 게 프로미스/퓨처, 그리고 async/await다. 표면적으로는 동기 코드처럼 보이지만 컴파일러가 뒤에서 콜백 변환을 해준다. 자바스크립트, C#, 파이썬, 러스트가 다 이 길을 갔다. 결과적으로 같은 이벤트 루프 위에서 돌면서도 코드는 동기 흐름처럼 읽힌다.

// 같은 일을 async/await로
async function pipeline() {
    const data = await readFile("a");
    const result = await process(data);
    await writeFile("b", result);
}

7. 멀티코어 시대의 한계

단일 쓰레드 이벤트 루프의 매력은 락이 없다는 것이다. 그런데 단일 쓰레드라는 건 곧 단일 코어라는 뜻이기도 하다. 16코어 서버에서 이벤트 루프 하나만 돌리면 코어 15개가 논다.

현대적인 답은 보통 "코어 수만큼 이벤트 루프를 띄우고 각자 다른 연결을 처리한다"이다. nginx의 워커 프로세스, Node.js의 cluster, Go의 goroutine 위 런타임, 다 비슷한 발상이다. 각 루프가 자기 데이터만 만지면 락이 필요 없고, 정말 공유해야 할 게 있을 때만 메시지로 주고받는다. 본질적으로 멀티프로세스 모델로 회귀하는 셈인데, 이게 가장 실용적인 해법이라는 게 시간이 지나며 입증됐다.

8. 쓰레드냐 이벤트냐 — 결국 둘 다 쓴다

둘 중 무엇이 절대적으로 우월하냐는 식의 논쟁은 한 시절 뜨거웠지만, 지금 보면 답은 "둘 다 쓴다"다. CPU 바운드 작업은 쓰레드/프로세스로 코어를 활용하고, I/O 바운드 작업은 이벤트 루프로 다중화한다. 둘을 결합한 하이브리드 런타임이 오늘날의 표준이다.

고(Go)의 goroutine은 외형적으로는 가벼운 쓰레드처럼 보이지만, 런타임이 내부적으로 작은 수의 OS 쓰레드 위에 협력적으로 스케줄링한다. 자바의 가상 쓰레드도 비슷한 방향이다. 둘 사이의 경계가 흐려지고 있다는 뜻이다. 사용자 입장에서는 동기 코드처럼 짜고, 런타임이 알아서 이벤트 루프 위로 분산한다.

그러니 어떤 모델을 고를지는 절대적 우월이 아니라 도구 적합성의 문제다. 락 추론이 어렵고 I/O가 압도적인 워크로드라면 이벤트 모델이 빛난다. CPU 작업이 많고 단순하다면 쓰레드/프로세스가 자연스럽다. 그리고 대부분의 실제 서비스는 두 성격이 섞여 있어서, 결국 두 도구를 같이 쓰는 시스템 설계로 귀결된다.

1. 컴퓨터는 사실 바깥 세상이 더 시끄럽다

지금까지 우리가 본 컴퓨터는 이상하리만큼 조용했어. CPU가 메모리에서 명령어를 읽고, 레지스터를 굴리고, 다시 메모리에 쓰고. 이 폐쇄적인 세계 안에서는 모든 게 ns 단위로 깔끔하게 돌아가지. 그런데 사용자가 키를 누르는 순간, 디스크가 돌아가야 하는 순간, 네트워크에서 뭔가 도착하는 순간 — 갑자기 이 깔끔한 세계는 산만해져. 외부 장치들은 CPU보다 수천, 수백만 배 느리고, 자기 마음대로 시간을 쓰거든.

그래서 운영체제 입장에서 입출력 장치는 늘 골칫거리이자 꼭 풀어야 할 문제야. CPU를 놀리지 않으면서 동시에 느린 장치도 챙겨야 하니까.

2. 표준 장치 모델 — 인터페이스와 내부 구현

장치는 보통 두 부분으로 나눠 볼 수 있어. 하나는 OS와 대화하는 인터페이스고, 다른 하나는 실제 일을 처리하는 내부 구현이야. 인터페이스 쪽에는 보통 세 가지 레지스터가 보여. 상태(status), 명령(command), 데이터(data) 레지스터지. OS는 이 세 칸에 적당한 값을 써넣거나 읽어 오면서 장치와 약속된 프로토콜로 소통해.

+--------------------+--------------------+
|  Registers (외부)  |  내부 마이크로컨트롤러 |
|  status / cmd / data | + 펌웨어 + 메모리      |
+--------------------+--------------------+
        ↑                    ↓
        OS가 보는 면      실제 일하는 면

내부 구현은 그야말로 장치 따라 천차만별. 어떤 디스크는 작은 CPU와 펌웨어를 품고 있고, 어떤 NIC은 자기만의 DMA 엔진과 큐를 갖고 있어. OS는 이 내부를 모르고도 잘 돌아가야 해. 추상화의 힘이지.

3. 폴링 — 지치도록 물어보기

가장 단순한 방법은 폴링이야. CPU가 "아직 멀었어?"를 계속 물어보는 거지. 코드는 이렇게 생겼어.

// 폴링 패턴: 장치가 준비될 때까지 빙빙 돌기
while ((read_status(reg) & READY_BIT) == 0)
    ;                       // busy-wait
write_data(reg, buf);
write_command(reg, START);
while ((read_status(reg) & DONE_BIT) == 0)
    ;                       // 또 busy-wait

코드가 간단해서 좋긴 한데, 장치가 느린 동안 CPU는 그냥 같은 비트만 계속 들여다보는 신세야. 만약 디스크 한 번 읽는 데 5ms가 걸린다면, 그 사이 CPU는 수백만 사이클을 헛돌리는 셈. 실시간 처리가 필요하거나 장치가 진짜 빠를 때만 합리적이야.

4. 인터럽트 — 장치가 먼저 부른다

그래서 등장한 게 인터럽트야. CPU가 명령을 던져 놓고는 다른 프로세스 일을 해. 장치는 일이 끝나면 "저 끝났어요" 하고 신호를 보내. CPU는 하던 일을 잠시 중단하고 인터럽트 핸들러로 점프해서 결과를 가져가지. 폴링과 비교하면 CPU가 다른 유용한 일을 할 수 있다는 점이 결정적인 차이야.

다만 인터럽트가 늘 정답은 아냐. 장치가 너무 빨라서 인터럽트가 폭주하면, 컨텍스트 스위치 비용이 폴링 비용보다 더 커져. 그래서 고속 NIC 같은 장치는 인터럽트와 폴링을 섞은 하이브리드 방식(예: NAPI)을 써. 또 인터럽트 모금 방식(coalescing)으로 여러 이벤트를 한 번에 묶어서 알리기도 해.

5. DMA — CPU 대신 데이터를 옮겨주는 친구

인터럽트로 CPU가 자유로워진 건 좋은데, 여전히 큰 데이터 블록을 메모리에서 장치로 옮길 때 CPU가 한 바이트씩 끌어다 쓰면 의미가 없어. 그래서 DMA(Direct Memory Access) 컨트롤러가 등장해. CPU는 DMA에게 "메모리 0x80000부터 4KB를 디스크 컨트롤러로 보내" 한마디만 해. 그러면 DMA가 알아서 버스를 잡고 데이터를 옮긴 뒤 끝나면 인터럽트로 알려줘.

CPU ── (시작 명령) ──▶ DMA Controller
                          │  버스 사용
                          ▼
   Memory ◀──── 데이터 전송 ────▶ Device
                          │
CPU ◀── (완료 인터럽트) ──┘

DMA가 없는 세상은 상상하기 싫어. 4KB 블록 전송 동안 CPU가 4096번 read/write 루프를 돌고 있어야 하니까.

6. 메모리 매핑 vs 포트 매핑 I/O

장치 레지스터에 접근하는 방법도 두 갈래야. 포트 매핑 I/O는 x86의 in/out 명령처럼 별도의 I/O 주소 공간을 두고 접근하는 방식. 반대로 메모리 매핑 I/O는 장치 레지스터를 메모리 주소 공간 한 자락에 매핑해 두고, 일반 load/store 명령으로 접근해. 후자는 인스트럭션 추가가 필요 없고 캐싱·가상 메모리와 통합하기 쉬워서 요즘 플랫폼이 많이 쓰는 방식이지.

7. 장치 드라이버 — 다양성을 한 줌으로 가둔다

세상에는 SSD도 있고, USB 마우스도 있고, GPU도 있어. OS가 이 모든 장치를 일일이 따로 다루면 커널은 미궁이 돼. 그래서 OS는 추상 인터페이스를 하나 정해 두고(예: 블록 장치는 read/write/seek 같은 함수 포인터 테이블), 각 장치마다 그 인터페이스를 구현하는 드라이버를 둬. 파일 시스템은 드라이버 인터페이스 위에서 일하니까 장치가 바뀌어도 파일 시스템 코드는 그대로야.

1. 디스크의 모양을 그려보자

하드 디스크 안에는 거울처럼 매끈한 원반이 여러 장 겹쳐 있어. 이걸 플래터(platter)라고 해. 각 플래터는 양면 다 자성을 띤 코팅이 발려 있어서, 헤드(head)가 그 위에 살짝 떠다니면서 0과 1을 읽고 써. 모든 플래터는 같은 축(스핀들)에 꽂혀 한 덩어리로 회전해. 보통 7,200 rpm이나 10,000 rpm.

     ┌──────────────────────┐
     │  ●━━━━━━━━━━━━━━━●  │  ← 트랙(track)
     │ ●  ┌────┐  ┌──┐ ●  │
     │ ●  │섹터│  │..│ ●  │  ← 섹터(sector, 보통 512B/4KB)
     │ ●  └────┘  └──┘ ●  │
     │  ●━━━━━━━━━━━━━━━●  │
     └──────────┬───────────┘
                │ 스핀들 (회전)

하나의 플래터 위에는 동심원이 잔뜩 그어져 있어. 이걸 트랙(track)이라 부르고, 트랙은 다시 잘게 나뉘어 섹터(sector)가 돼. 섹터가 디스크 입출력의 기본 단위지. 여러 플래터의 같은 트랙 번호를 한 묶음으로 보면 실린더(cylinder)가 돼.

2. 한 섹터를 읽는 데 걸리는 시간

디스크는 단일 시간으로 설명할 수 없는 장치야. 한 요청을 처리하는 동안 세 가지 시간이 더해져.

• 탐색 시간(seek time): 헤드를 원하는 트랙으로 옮기는 시간. 가까운 트랙은 빠르고, 가장 안쪽에서 바깥으로 가는 풀 스트로크(full stroke)는 느려.
• 회전 지연(rotational latency): 원하는 섹터가 헤드 밑으로 돌아올 때까지 기다리는 시간. 평균적으로 한 바퀴의 절반.
• 전송 시간(transfer time): 실제로 비트를 읽거나 쓰는 시간. 회전 속도와 트랙 밀도가 결정해.

예를 들어 7,200 rpm 디스크라면 한 바퀴가 약 8.33ms, 그래서 평균 회전 지연이 약 4.17ms야. 탐색 시간은 빠르면 1ms, 느리면 10ms 넘게 걸리기도 해. 결국 큰 데이터를 한 번에 시퀀셜하게 읽으면 빠르고, 작은 블록을 띄엄띄엄 읽으면 끔찍하게 느려져. 이 비대칭이 디스크의 거의 모든 성격을 만들어.

3. FCFS — 가장 게으른 스케줄러

요청이 들어온 순서대로 그냥 처리하는 게 FCFS(First-Come-First-Served)야. 공평하긴 하지만 헤드가 디스크 양 끝을 미친 듯이 왔다 갔다 할 수 있어. 만약 큐에 트랙 10, 200, 12, 195 순으로 들어왔다면 헤드는 10 → 200 → 12 → 195로 멀리 갔다가 또 멀리 가버리지.

4. SSTF — 가장 가까운 친구부터

SSTF(Shortest Seek Time First)는 현재 헤드 위치에서 가장 가까운 요청을 먼저 처리해. 평균 탐색 시간이 확 줄어드는 대신 단점이 명확해. 헤드 근처에 요청이 계속 들어오면 멀리 있는 요청은 영원히 안 처리될 수 있어. 기아(starvation) 문제지.

FCFS:  10 ─→ 200 ─→ 12 ─→ 195   (헤드 이동 합 = 큼)
SSTF:  10 ─→ 12  ─→ 195 ─→ 200  (가까운 곳부터)

5. SCAN과 C-SCAN — 엘리베이터처럼 움직이기

그래서 디스크 스케줄러는 종종 엘리베이터에 비유돼. SCAN은 헤드를 한쪽 끝으로 쭉 진행시키며 그 길에 있는 요청을 모두 처리하고, 끝에 닿으면 방향을 뒤집어. 마치 백화점 엘리베이터가 위로 갈 땐 위로만 가는 것처럼.

C-SCAN(Circular SCAN)은 한쪽 끝에 도달하면 처리 없이 곧장 반대쪽 끝으로 점프한 뒤 다시 한 방향으로 진행해. 일정한 응답 시간을 보장한다는 면에서 SCAN보다 공평해. 끝부분 트랙이 늘 두 번씩 지나가는 SCAN의 비대칭을 없애 주거든.

6. SPTF — 회전까지 고려하기

seek 만 보지 말고 회전 지연까지 함께 고려해서 가장 빨리 끝낼 수 있는 요청을 고르는 게 SPTF(Shortest Positioning Time First)야. 정확히 계산하려면 디스크 내부의 헤드 위치, 회전 각도, 트랙 매핑을 다 알아야 해서 보통은 디스크 펌웨어 안에서 처리해. OS는 큰 그림만 정렬해서 던지고, 디스크 컨트롤러가 마지막 미세 조정을 맡는 분업이 자리 잡았어.

1. RAID가 등장한 이유

1980년대 후반, 비싼 단일 대형 디스크 대신 저렴한 디스크 여러 개를 묶어 쓰자는 발상이 나와. 이게 RAID의 시작이야. 사용자가 보기엔 그냥 하나의 거대한 블록 장치인데, 안에서는 여러 디스크가 협업하지. RAID의 매력은 세 가지로 정리할 수 있어: 용량, 성능, 신뢰성.

운영체제 입장에서 RAID는 보이지 않는 마법 상자야. 파일 시스템은 평소처럼 블록 단위로 read/write를 보내고, RAID 컨트롤러(또는 소프트웨어 RAID)가 그걸 여러 디스크에 어떻게 흩뿌릴지 결정해.

2. 평가 기준 세 가지

RAID 레벨을 비교할 땐 보통 세 잣대로 봐.

• 용량(capacity): N개의 디스크 중 실제 사용자 데이터로 쓰는 비율.
• 신뢰성(reliability): 몇 개의 디스크가 동시에 망가져도 데이터를 살릴 수 있는지.
• 성능(performance): 순차/임의 읽기·쓰기에서 단일 디스크 대비 얼마나 빠른지.

3. RAID 0 — 줄세우기(Striping)

가장 단순한 게 RAID 0이야. 데이터를 청크 단위로 잘라 N개의 디스크에 라운드 로빈으로 흩뿌려. 한 번에 여러 디스크가 동시에 일하니까 큰 시퀀셜 읽기/쓰기 성능이 거의 N배에 가깝게 나와.

블록 0 → 디스크 A
블록 1 → 디스크 B
블록 2 → 디스크 C
블록 3 → 디스크 D
블록 4 → 디스크 A   ...

대신 신뢰성은 오히려 떨어져. 디스크 한 개라도 망가지면 끝. 영상 편집의 임시 캐시처럼 "성능이 전부, 데이터 잃어도 됨" 같은 시나리오가 어울려.

4. RAID 1 — 거울 두 장(Mirroring)

RAID 1은 같은 데이터를 두 디스크에 똑같이 복제해 둬. 한쪽이 망가져도 다른 쪽이 살아 있으니 데이터는 안전해. 읽기는 어느 쪽에서나 할 수 있어 어느 정도 빨라지지만, 쓰기는 두 디스크에 모두 써야 하니 단일 디스크 수준이고 용량도 절반만 쓰는 셈.

RAID 0과 1을 함께 쓰는 RAID 10도 흔해. 미러로 묶은 짝을 다시 스트라이핑하는 구조라 빠르면서도 안전해. 데이터베이스 서버에서 단골이지.

5. RAID 4 — 패리티를 한 디스크에 몰기

거울은 안전하지만 디스크 절반을 깎아 먹는 게 아깝잖아. 그래서 패리티(parity)라는 트릭이 등장해. N개의 데이터 디스크에 더해 패리티 디스크 하나를 따로 둬서, 같은 줄(stripe)에 있는 데이터들의 XOR을 패리티 디스크에 저장해.

stripe k:
  D_a ⊕ D_b ⊕ D_c ⊕ D_d  =  P_k

만약 디스크 c가 죽으면:
  D_c = D_a ⊕ D_b ⊕ D_d ⊕ P_k

한 디스크가 죽어도 남은 디스크들의 XOR로 사라진 비트를 복원할 수 있어. 용량 효율이 (N-1)/N이라 미러보다 훨씬 알뜰해. 다만 작은 임의 쓰기를 할 때마다 패리티 디스크가 매번 갱신돼야 해서 패리티 디스크가 병목이 돼. 이게 RAID 4의 약점.

6. RAID 5 — 패리티를 골고루 흩뿌리기

RAID 5는 RAID 4의 약점을 똑똑하게 풀어. 패리티를 한 디스크에 몰지 않고 모든 디스크에 돌아가며 분산해서 저장해. 그래서 임의 쓰기가 와도 어느 한 디스크에 부담이 쏠리지 않아.

stripe 0:  D D D P
stripe 1:  D D P D
stripe 2:  D P D D
stripe 3:  P D D D
stripe 4:  D D D P  ...

다만 작은 쓰기 한 번에도 "옛 데이터 읽기 → 옛 패리티 읽기 → 새 패리티 계산 → 새 데이터/패리티 쓰기" 네 번의 I/O가 필요해. 이걸 작은 쓰기 패널티(small write penalty)라고 해. 큰 시퀀셜 쓰기는 한 번에 한 stripe 전체를 새로 만들 수 있어서 이 비용을 피할 수 있지.

1. 파일이라는 추상

파일은 OS가 사용자에게 주는 가장 오래된 약속이야. 디스크의 어떤 위치에 어떤 모양으로 데이터가 흩어져 있든, OS는 그걸 "이름이 붙은 바이트 배열" 한 덩어리로 보여줘. 각 파일에는 사람이 읽기 쉬운 이름과 함께 OS가 내부적으로 쓰는 숫자 식별자(inode 번호)가 붙어 있어.

파일 안의 데이터에 대해 OS는 보통 별 의미를 두지 않아. 그냥 바이트가 죽 늘어선 시퀀스. 의미를 부여하는 건 응용 프로그램의 몫이지. 같은 바이트 시퀀스라도 누가 읽느냐에 따라 JPEG 이미지가 되기도 하고, 소스 코드가 되기도 해.

2. 디렉토리 — 이름의 지도

디렉토리는 파일을 모으는 폴더 같은 존재인데, 더 정확히 보면 "이름 → inode 번호" 매핑을 담은 특수한 파일이야. 디렉토리도 결국 파일이라는 게 핵심이야. 다만 그 안에 든 내용이 일반 데이터가 아니라 디렉토리 엔트리들(name, inode#)일 뿐.

/                  → inode 2
├── home           → inode 5
│   └── brian     → inode 17
│       └── notes.txt  → inode 42
└── etc            → inode 6
    └── hosts     → inode 91

그래서 절대 경로를 따라가는 것(lookup)은 사실 inode를 한 단계씩 따라가며 디렉토리 엔트리에서 다음 inode 번호를 찾는 과정이야. /home/brian/notes.txt를 열려면 루트 inode부터 시작해서 home, brian, notes.txt를 차례로 따라가야 해.

3. 파일 시스템 인터페이스 — open, read, write, close

유닉스 계열에서 파일 다루는 시스템 콜은 의외로 단출해.

int  fd = open("/tmp/log.txt", O_WRONLY | O_CREAT, 0644);
ssize_t n = write(fd, buf, len);
off_t  p = lseek(fd, 0, SEEK_END);
int  rc = close(fd);

여기서 fd는 파일 디스크립터(file descriptor)라는 작은 정수야. 프로세스마다 고유한 테이블 인덱스지. 커널은 이 fd를 키로 해서 그 파일의 inode와 현재 오프셋, 권한 등을 추적해. 사용자 입장에선 그냥 정수 한 개 들고 다니면서 read/write를 부르면 돼서 깔끔해.

4. 하드 링크 — 같은 inode를 두 이름으로

리눅스의 link(혹은 ln) 시스템 콜은 같은 inode를 가리키는 새로운 디렉토리 엔트리를 만들어. 즉 한 파일에 두 개 이상의 이름이 붙는 거야.

$ ln /home/brian/notes.txt /home/brian/diary.txt
$ stat -c '%i %n' notes.txt diary.txt
42 notes.txt
42 diary.txt   # 같은 inode!

이때 inode 안에는 자신을 가리키는 이름의 개수, 즉 링크 카운트가 들어 있어. 사용자가 unlink로 이름 하나를 지우면 링크 카운트가 줄고, 0이 되는 순간(그리고 그 inode를 열고 있는 프로세스도 없을 때) 그제야 데이터 블록이 정말로 회수돼. 그래서 리눅스에서 "파일을 지운다"는 표현은 살짝 부정확해. 더 정확히는 "이름을 떼어 낸다"야.

5. 심볼릭 링크 — 경로를 담은 메모지

하드 링크와 다르게 심볼릭 링크(symlink)는 그 자체가 별도의 파일이고, 안에는 다른 파일의 경로 문자열이 적혀 있어. 그래서 원본 파일이 사라지면 심볼릭 링크는 갈 길을 잃은 끊어진 링크가 돼. 반면 하드 링크는 inode를 직접 가리키므로 다른 이름이 다 사라져도 데이터는 끄떡없어.

심볼릭 링크는 다른 파일 시스템 너머나 디렉토리도 가리킬 수 있다는 장점이 있어서 실무에서 폭넓게 쓰여. 하드 링크는 같은 파일 시스템 안에서만, 보통 디렉토리에는 못 걸어.

6. 권한과 마운트

유닉스 권한 모델은 소유자/그룹/그 외 사용자 각각에 대한 read/write/execute 비트로 단순하게 표현돼. 9비트 안에 거의 모든 게 들어 있는 셈. 더 정교한 제어가 필요하면 ACL을 쓰지만, 기본 9비트는 여전히 강력하고 빠르게 검사할 수 있어.

마운트(mount)는 또 다른 추상이야. 별개의 파일 시스템(이미지, USB 드라이브, 네트워크 공유 등)을 어떤 디렉토리 위에 끼워 넣어, 그 디렉토리 아래로 들어가면 다른 파일 시스템이 펼쳐지게 만들어. 사용자는 한 그루의 통합된 트리만 보면 되고, 어디서부터 다른 디스크인지 신경 쓸 필요가 없어.

1. vsfs — 아주 단순한 가상 파일 시스템

여기서는 학습용으로 만든 작은 파일 시스템을 vsfs(very simple file system)라 부를게. 이 친구는 실제로 쓰기엔 너무 단순하지만, 진짜 파일 시스템들이 공통으로 갖는 핵심 부품을 모두 담고 있어. 디스크 한 장이 있고, 그걸 4KB짜리 블록 64개로 나눴다고 해 보자.

+---+---+----+----+-----------------------------+
| S | i | dB | iB |   D D D D D D D D D D D D   |
+---+---+----+----+-----------------------------+
 0   1   2    3    4 ──────────────────────── 63

S  : 슈퍼블록
i  : inode 영역
dB : data bitmap
iB : inode bitmap
D  : 데이터 블록

2. 슈퍼블록 — 파일 시스템의 명함

가장 앞에 있는 블록 한두 개는 슈퍼블록 영역이야. 여기에는 파일 시스템 전체에 대한 메타데이터가 들어 있어. 블록 크기, 전체 블록 수, inode 영역의 시작 위치와 개수, 데이터 영역의 시작 위치, 매직 넘버(어느 파일 시스템인지 식별) 같은 값들이지. 부팅 시 OS가 이 슈퍼블록을 먼저 읽고, 거기 적힌 좌표를 기준으로 다른 영역에 접근해.

3. 비트맵 두 장 — 누가 비어 있나

새 파일을 만들거나 새 데이터 블록이 필요할 때, 어디가 비어 있는지 빠르게 알아야겠지. 그래서 vsfs는 두 개의 비트맵을 둬.

• inode 비트맵: 각 inode 슬롯이 사용 중인지(1) 비어 있는지(0)를 표시.
• 데이터 비트맵: 각 데이터 블록이 사용 중인지를 표시.

비트 하나가 슬롯/블록 하나에 대응하니 공간 효율도 좋아. 새 파일 생성은 결국 "inode 비트맵에서 0인 비트를 찾아 1로 바꾸기"로 시작해.

4. inode — 파일을 정의하는 작은 구조체

inode는 파일 한 개에 대한 모든 메타데이터와 데이터 블록 위치를 담은 구조체야. 보통 128바이트나 256바이트짜리. 안에는 파일 타입, 크기, 권한, 소유자, 시각 정보, 그리고 결정적으로 데이터 블록의 주소 목록이 들어 있어.

struct inode {
    uint16_t mode;           // 권한 + 파일 타입
    uint32_t uid;            // 소유자
    uint64_t size;           // 파일 크기 (바이트)
    uint32_t direct[12];     // 직접 포인터
    uint32_t single_indirect;// 간접 포인터
    uint32_t double_indirect;// 이중 간접 포인터
    // ... 시각 정보 등
};

주소를 저장하는 방식이 재미있는데, 보통 직접/간접/이중 간접 포인터로 트리 구조를 만들어. 작은 파일은 직접 포인터 몇 개로 끝나니 빠르고, 큰 파일은 간접 포인터를 통해 데이터 블록 주소가 들어 있는 블록을 가리키는 식으로 확장돼. 이 트리가 파일 크기와 접근 효율의 비대칭을 만드는 핵심이야.

5. 디렉토리도 그냥 파일이다

디렉토리는 inode가 디렉토리 타입으로 표시된 특별한 파일이야. 그 안에 든 데이터 블록을 들여다보면 (이름, inode 번호) 쌍의 목록이 죽 들어 있어. 보통 가변 길이 레코드로 저장되며, 삭제된 엔트리는 빈 슬롯으로 표시해 두고 다음에 재사용해.

+---------------+--------+-----------+
| inode#  | len | name              |
+---------------+--------+-----------+
| 17      | 12  | "notes.txt"       |
| 22      | 8   | "todo"            |
| 0       | 16  | "(deleted)"       |  ← 빈 자리
| 31      | 9   | "src.c"           |
+---------------+--------+-----------+

6. open과 read — 시스템 콜이 디스크를 얼마나 흔드는지

"단순해 보이는 open 한 번이 디스크에 몇 번 접근할까?"가 의외로 좋은 질문이야. /a/b/foo.txt를 열려면 루트 inode를 읽고, 그 데이터 블록에서 'a'의 inode 번호를 찾고, a inode를 읽고, a의 데이터에서 'b'를 찾고, b inode를 읽고, b의 데이터에서 'foo.txt'를 찾고, 마지막에 foo.txt의 inode를 읽어. 이미 디스크 접근만 7번이지. read 한 번도 inode 갱신(시간 정보)과 데이터 블록 읽기가 더해져.

그래서 파일 시스템은 이 모든 메타데이터를 메모리 안에 캐시하고, 자주 쓰는 디렉토리/inode를 살짝 살짝 붙잡아 두는 게 굉장히 중요해. 안 그러면 디스크가 정말 시끄러워질 거야.

7. write — 더 분주하다

새 데이터 블록이 필요한 write는 더 시끄러워. 데이터 비트맵을 읽고, 빈 블록을 찾아 비트맵에 1 표시한 뒤 다시 쓰고, 데이터 블록에 실제 내용을 쓰고, inode를 읽어 새 블록 주소를 추가한 뒤 inode를 다시 써. 한 번의 write에 디스크 접근이 여러 번 일어나는 셈이야. 이래서 OS가 다양한 캐싱·버퍼링·지연 쓰기 기법으로 무장한 거고.

1. 옛 파일 시스템의 비극

초기 유닉스 파일 시스템(흔히 "오래된 FS"라 부르는)은 디스크를 그저 평평한 블록 배열로 봤어. inode 영역과 데이터 영역이 분리돼 있고, 둘은 디스크의 다른 자리에 있었지. 그래서 파일 하나를 읽을 때마다 헤드가 inode 영역과 데이터 영역 사이를 한참 이동해야 했어. 게다가 사용 패턴이 누적되면 빈 블록은 디스크 곳곳에 점점이 흩어지고, 새 파일은 그 점들을 따라 분열돼 저장돼. 결과는 끔찍한 단편화. 디스크 성능이 시간이 갈수록 빠르게 망가졌지.

2. FFS의 큰 그림 — 실린더 그룹

1980년대 초, 버클리에서 등장한 FFS(Fast File System)는 이 문제를 디스크 지오메트리를 의식한 배치로 풀어. 핵심 아이디어는 디스크를 여러 개의 실린더 그룹(cylinder group)으로 나누는 거야. 각 실린더 그룹은 인접한 실린더 묶음이라 그룹 안에서는 헤드 이동이 짧고 빨라.

┌─── disk ──────────────────────────────┐
│ [CG0][CG1][CG2][CG3] ... [CGn]        │
└───────────────────────────────────────┘

각 실린더 그룹 (CG):
┌────────────────────────────────────────┐
│ SB | inode bitmap | data bitmap |      │
│ inodes ...        | data blocks ...    │
└────────────────────────────────────────┘

중요한 건 각 실린더 그룹이 자체적으로 슈퍼블록 사본, inode 비트맵, 데이터 비트맵, inode 영역, 데이터 블록 영역을 다 갖는다는 점이야. 즉 한 그룹 안에서 어지간한 일이 다 끝나니, 헤드가 그룹 밖으로 멀리 갈 일이 줄어들어.

3. 배치 정책 — 가까이, 그러나 덩어리지지 않게

FFS의 두 번째 핵심은 정책(policy)이야. 어떤 파일·디렉토리를 어느 실린더 그룹에 둘지 결정하는 규칙들이지. 대표적인 두 정책이 있어.

• 관련된 것은 가까이: 같은 디렉토리에 있는 파일들은 서로 가까이 있는 게 좋아. 그래서 새 파일의 inode는 부모 디렉토리의 inode가 있는 실린더 그룹에 배치하려고 해. 또 한 파일의 데이터 블록도 그 inode와 같은 그룹 안에 두려고 해.
• 새 디렉토리는 한가한 곳에: 모든 디렉토리가 한 그룹에 몰리면 그 그룹은 곧 가득 차. 그래서 새 디렉토리는 비어 있는 그룹, 즉 inode 사용량이 적고 데이터 블록 여유가 있는 그룹을 골라서 만들어.

두 정책이 약간 모순돼 보이지? 의도된 거야. 가까이 두려는 욕심과 골고루 흩뿌리려는 욕심을 균형 잡는 게 핵심이야. 그래야 시간이 가도 디스크가 골고루 차고, 한 디렉토리 안의 데이터는 응집해서 빠르게 읽히지.

4. 큰 파일은 예외

큰 파일을 한 실린더 그룹에 다 우겨 넣으면 그 그룹이 빠르게 가득 차 버려. 그러면 그 그룹의 다른 작은 파일들이 들어올 자리가 없어져. 그래서 FFS는 어떤 임계치를 넘어가는 큰 파일은 일정 크기마다 잘라서 다른 실린더 그룹으로 분산해 저장해. 약간의 시퀀셜 성능 손해를 감수하더라도 디스크 전체의 균형을 지키려는 거야.

5. 작은 파일을 위한 프래그먼트

FFS는 4KB나 8KB 같은 큰 블록을 표준으로 잡아 시퀀셜 처리량을 끌어올렸어. 그런데 큰 블록은 작은 파일에게는 낭비야. 1KB짜리 텍스트 파일이 8KB 블록 하나를 차지하면 7KB가 그냥 빈 자리가 되니까.

그래서 FFS는 블록을 더 잘게 나눈 프래그먼트(fragment)라는 단위를 도입해. 작은 파일이나 파일의 마지막 토막은 프래그먼트 단위로 저장하고, 파일이 자라면 프래그먼트들을 모아 결국 한 블록으로 다시 묶는 식. 공간 낭비를 줄이고 큰 블록의 성능 이득은 그대로 누리는 영리한 트릭이야.

6. 파일 시스템이 사람 친화적으로

FFS는 성능 외에도 사용성에서 여러 진보를 가져왔어. 긴 파일 이름을 허용하고, 심볼릭 링크를 도입하고, 파일 잠금(locking)도 제공했어. 이 자체는 OS 추상의 진화지만, 디스크 친화적 배치 정책이라는 거대한 토대 위에서 가능했던 변화이기도 해.

1. 한 번의 쓰기, 여러 번의 디스크 갱신

파일 하나에 4KB를 추가하는 단순한 동작도, 디스크 입장에서 보면 보통 세 군데 이상의 블록을 건드린다. 데이터 블록 자체, 그 데이터의 소유자인 inode, 그리고 새 블록이 사용 중임을 표시하는 비트맵. 이 셋 중 하나라도 빠지거나, 순서가 꼬이면 파일 시스템은 일관성 없는 상태로 굳는다.

여기서 정말 골치 아픈 문제가 생기는데, 디스크는 한 번에 한 섹터만 원자적으로 쓰는 게 보장될 뿐, 여러 블록을 한꺼번에 "동시에" 반영해주지 않는다는 점이다. 우리가 원하는 것은 "셋 다 갱신" 또는 "셋 다 그대로", 둘 중 하나뿐인데 현실은 그 사이의 어중간한 상태를 자주 만든다.

2. 부분 쓰기가 만들어내는 어색한 상태들

비트맵만 갱신되고 inode와 데이터는 안 바뀐 채로 멈춘다고 해보자. 이 블록은 "사용 중"이지만 누구도 자기 것이라고 주장하지 못하는 유령 블록이 된다. 반대로 inode만 새 블록을 가리키도록 바뀌고 비트맵이 갱신되지 않으면, 같은 블록을 두 파일이 동시에 자기 것이라 우길 수도 있다. 가장 무서운 시나리오는 비트맵과 inode는 "썼다"고 주장하는데 데이터 블록에는 옛날 쓰레기 값이 남아 있는 경우다. 디렉토리 정보가 그 자리에 있었다면 보안 사고로 번질 수도 있다.

3. fsck — 부팅할 때마다 디스크를 훑어 보기

초창기 유닉스의 답은 단순했다. 부팅 시 fsck(file system check)를 돌려 전체 메타데이터를 훑고 비일관성을 찾아 고치자는 발상이다. 비트맵과 inode가 어긋나면 어느 한쪽을 기준으로 맞추고, 아무도 가리키지 않는 inode는 lost+found로 보낸다.

발상은 명쾌하지만 디스크가 커질수록 비용이 살벌해진다. 1TB 디스크의 모든 inode와 디렉토리 트리를 매 부팅마다 검사한다고 상상해 보자. 게다가 fsck는 "메타데이터의 모순"만 잡을 뿐, 데이터 자체가 옛날 값인지 새 값인지는 알 길이 없다.

4. 저널링 — "할 일을 먼저 쓰고, 나중에 실제로 한다"

현대 파일 시스템(ext3/4, NTFS, XFS)은 데이터베이스의 write-ahead logging 아이디어를 빌려 왔다. 본 디스크 영역을 건드리기 전에, "내가 지금 이런 변경을 할 거야"라는 의도를 별도의 저널 영역에 먼저 기록한다. 저널 기록이 무사히 끝났다는 커밋 표시가 디스크에 박힌 시점부터, 이 트랜잭션은 "꼭 일어날 일"이 된다.

// 저널링 트랜잭션의 기본 흐름
TxBegin   -> 저널에 변경 의도 기록
TxJournal -> 데이터/메타데이터 블록 사본을 저널에 씀
TxCommit  -> 커밋 레코드 기록 (이 시점부터 "확정")
Checkpoint-> 본 영역으로 실제 반영
TxFree    -> 저널 슬롯 회수

도중에 크래시가 나도 부팅 시 저널을 다시 훑어 본다. 커밋까지 도달한 트랜잭션은 본 영역에 다시 적용(redo)하고, 커밋 전에 끊긴 트랜잭션은 그냥 버린다. fsck처럼 디스크 전체를 뒤지지 않고, 저널의 길이만큼만 보면 된다.

5. 데이터 저널링 vs. 메타데이터 저널링

모든 쓰기를 저널에 한 번, 본 영역에 또 한 번 기록하면 데이터까지 안전하지만 디스크에 같은 데이터를 두 번 쓰는 셈이라 느리다. 그래서 대부분 "메타데이터 저널링"을 기본으로 쓴다. inode, 비트맵, 디렉토리 같은 구조 정보만 저널에 적고, 실제 사용자 데이터는 본 영역에 한 번만 쓴다.

다만 이때 한 가지 주의가 필요한데, 새 데이터 블록의 본 영역 쓰기가 메타데이터 커밋보다 늦어지면, 옛날 값이 새 inode 안에 노출될 위험이 있다. ext3의 ordered 모드는 "데이터 블록 본 영역 쓰기 -> 메타데이터 저널 커밋" 순서를 강제해서 이 함정을 막는다.

1. "그 자리에 덮어쓰기"를 버린다

전통 파일 시스템은 inode 번호가 정해지면 그 inode가 사는 위치도 디스크상에서 고정이다. 데이터 블록 위치도 마찬가지여서, 같은 파일을 고치면 늘 같은 자리를 다시 쓴다. 디스크 헤드가 이리저리 점프하느라 시간을 버리는 게 이 모델의 약점이다.

LFS의 발상은 단순하면서도 과격하다. "모든 쓰기는 디스크의 빈 끝부분에 순차적으로". 데이터든 inode든 디렉토리든, 새로 쓸 일이 있으면 무조건 큰 segment에 모았다가 한 번에 길게 쓴다. 같은 블록을 두 번 고친다고 같은 위치를 덮어쓰지 않는다. 그냥 새 위치에 새 버전을 쓰고 옛 버전은 "낡은 흔적"으로 남긴다.

2. write buffer와 segment

작은 쓰기를 매번 디스크로 보내면 순차 쓰기의 장점이 사라진다. LFS는 메모리에 큰 write buffer(보통 수 MB)를 두고, 채워질 때까지 모았다가 한 번에 segment 단위로 디스크에 던진다. segment 하나가 수 메가라서, 디스크 입장에선 "긴 한 줄을 쓰는" 가장 효율적인 작업이 된다.

3. inode가 떠다닌다 — inode map의 등장

그런데 inode 위치가 매번 바뀌면, "inode 번호 47번을 어디서 찾지?"라는 문제가 생긴다. LFS는 inode map(imap)이라는 작은 자료구조를 두어 "inode N은 지금 디스크 어느 위치에 있는가"를 매핑한다. 이 imap도 갱신될 때마다 segment의 일부로 함께 기록된다.

imap 자체의 위치는 어떻게 찾느냐 하면, 디스크의 정해진 자리(checkpoint region)에 imap의 최신 위치 포인터를 주기적으로 적어 둔다. 부팅 시 그 포인터부터 시작해 imap을 복원하고, imap을 통해 모든 inode를 찾는다.

// LFS의 주소 변환
파일명 -> 디렉토리에서 inode 번호 N 획득
inode N -> imap[N] 조회로 디스크상의 inode 위치 P 획득
inode 읽기 -> 데이터 블록 포인터 따라가기

4. 옛 버전이 쌓인다 — garbage collection

덮어쓰기를 안 하니까 디스크에는 자연스레 "더 이상 누구도 가리키지 않는 옛 버전"이 쌓여 간다. 이걸 그대로 두면 디스크가 결국 가득 찬다. 그래서 LFS는 백그라운드에서 garbage collector를 돌린다. 군데군데 죽은 블록이 섞인 segment 몇 개를 골라, 살아 있는 블록만 모아 새 segment에 쓰고, 원래 segment들을 통째로 비워 버린다.

"이 블록이 살아 있는가"는 segment 헤더에 적힌 (inode 번호, 블록 오프셋) 정보를 imap의 현재 상태와 대조해 판단한다. 일치하면 살아 있는 것, 어긋나면 옛 버전이라 버려도 된다.

5. 크래시 일관성과 LFS

흥미롭게도 LFS는 구조 자체가 거대한 저널과 닮았다. 모든 변경이 시간 순서대로 segment에 적혀 있으니, 마지막 checkpoint 이후의 segment를 따라 재생하면 가장 최근 일관성 있는 상태를 복원할 수 있다. 별도의 저널 영역이 필요 없다는 건 깔끔한 이점이다.

1. NAND 플래시 셀 — 전자를 가둬 비트로 쓴다

SSD의 기본 단위는 플래시 셀이다. 셀 하나에 전자를 가두어 그 양으로 0/1을 표현한다. 한 셀에 1비트만 저장하면 SLC, 2비트면 MLC, 3비트면 TLC, 4비트면 QLC로 부르는데, 비트를 많이 욱여넣을수록 용량은 커지지만 읽기/쓰기 속도와 수명은 떨어진다.

2. page와 block — 비대칭 단위

SSD가 까다로운 진짜 이유는 읽기와 쓰기와 지우기의 단위가 모두 다르다는 점이다. 읽기와 쓰기(프로그램)는 page 단위(보통 4~16KB)이지만, 지우기(erase)는 그보다 훨씬 큰 block 단위(수 MB)다. 더 결정적인 제약은 "한 번 0으로 쓴 비트는 1로 되돌리려면 block 전체를 지워야 한다"는 점이다. 즉, 같은 자리에 새 값으로 덮어쓰는 일이 불가능에 가깝다.

// SSD의 비대칭
read   : page  단위, 빠름
program: page  단위, 깨끗한 page에만 가능
erase  : block 단위, 느림, 쓰기 가능 상태로 초기화

3. FTL — 디스크인 척 연기하기

OS는 여전히 LBA(논리 블록 주소)로 SSD에게 명령한다. "LBA 1234에 이 데이터를 써 줘." SSD 내부의 컨트롤러가 돌리는 펌웨어인 FTL(Flash Translation Layer)은 이 LBA를 실제 NAND의 어떤 page에 매핑할지를 관리한다.

FTL의 흔한 전략은 LFS와 흡사하다. 새 쓰기를 받으면, 깨끗한 새 page에 적고, 옛 page는 "이젠 무효"라고 표시한다. 매핑 테이블은 LBA를 항상 가장 최신의 물리 page로 가리키도록 갱신한다. 무효 page가 충분히 쌓이면 GC가 그 block을 통째로 지워서 다시 쓰기 가능 상태로 돌려놓는다.

4. wear leveling — 닳는 셀을 골고루 닳게

각 block은 지우기 횟수에 한계가 있다(SLC는 수만~수십만, QLC는 수천 정도). 같은 block만 계속 지우면 그 부분만 빨리 망가져서 SSD 전체 수명이 짧아진다. FTL은 어느 block이 얼마나 지워졌는지 카운트해 두고, 덜 닳은 block 위주로 새 쓰기를 분산시킨다. 심지어 "거의 안 변하는 정적 데이터"가 늙지 않은 block을 점유하고 있으면, 일부러 다른 곳으로 옮겨서 그 block도 풀에 합류시킨다.

5. write amplification과 over-provisioning

호스트가 보낸 1MB의 쓰기가 내부적으로는 GC와 wear leveling 때문에 그 이상 NAND에 쓰일 수 있는데, 이 비율이 write amplification이다. SSD 제조사는 사용자에게 노출하지 않는 여유 공간(over-provisioning)을 둠으로써 GC의 효율을 높이고 amplification을 낮춘다. 빈 자리가 많을수록 GC가 한꺼번에 비워낼 무효 page를 모으기 쉽기 때문이다.

6. TRIM — "이 블록 더는 안 쓴다"고 알려주기

OS가 파일을 지웠다고 SSD가 그걸 알 도리는 없다. SSD 입장에선 LBA가 아직 유효해 보이니, GC가 그 page를 "살아 있는 데이터"로 알고 살뜰히 옮겨 다닌다. TRIM 명령은 이 간극을 메운다. 파일이 삭제될 때 OS가 SSD에게 "이 LBA들은 이제 의미 없다"고 알리고, FTL은 해당 매핑을 무효로 표시해 GC 비용을 줄인다.

1. 디스크는 거짓말을 한다

옛날에는 디스크 고장이라 하면 헤드 충돌이나 모터 고장 같은 "전체 사망"을 떠올렸다. 현대 저장 장치의 실패 양상은 훨씬 미묘하다. 단일 섹터만 못 읽게 되는 latent sector error, 잘못된 블록을 정상이라며 돌려주는 misdirected write, 일부 데이터가 사라진 줄도 모르는 lost write, 그리고 가장 음흉한 silent corruption — 비트가 뒤집혔는데 ECC도 통과해서 OS에 그대로 흘러들어오는 경우.

2. 체크섬 — 데이터에 자기 자신을 증언시킨다

방어선은 체크섬이다. 데이터 블록에 함께 작은 해시 값을 붙여서, 읽을 때마다 "이 데이터가 정말 그때 쓴 데이터가 맞는지"를 검증한다. CRC32, Fletcher, xxHash 같은 가벼운 해시도 자주 쓰이지만, 보안까지 고려할 때는 더 강한 SHA 계열을 쓰기도 한다.

체크섬을 어디 두느냐도 핵심이다. 같은 섹터 안에 함께 두면 그 섹터 자체가 손상될 때 같이 망가질 위험이 있어, 체크섬은 별도 영역에 모아 두는 설계가 흔하다.

3. misdirected/lost write를 잡는 추가 정보

체크섬만으로는 "내용은 정상이지만 잘못된 자리"인 데이터를 잡지 못한다. 그래서 ZFS 같은 파일 시스템은 체크섬에 더해 "이 블록이 어느 위치에 있어야 하는가"를 함께 기록한다. 읽었을 때 위치 정보가 안 맞으면 misdirected write를 의심한다. lost write는 체크섬을 부모 블록에 보관하는 트리 구조로 잡아낸다 — 부모가 가지고 있는 체크섬과 실제 자식 데이터가 어긋나면 자식 쪽이 옛 데이터라는 신호다.

4. disk scrubbing — 의심병 있는 점검

체크섬은 "읽을 때" 검증해 준다. 그런데 자주 안 읽는 데이터는 손상이 있어도 모르고 지나간다. scrubbing은 백그라운드에서 주기적으로 디스크 전체를 훑으며 모든 블록을 읽고 체크섬을 확인한다. 손상이 발견되면, RAID 같은 이중화에서 정상 사본을 가져와 그 자리에 다시 써 넣는다.

// 데이터 보호의 층층이
[애플리케이션 체크섬]
  └ [파일 시스템 체크섬 + 트리]
      └ [RAID/이중화]
          └ [디스크 ECC, 매체 자체의 보호]

5. 어디까지 보호할지 — 비용과 신뢰의 균형

모든 층에 강한 체크섬을 두면 안전하지만 CPU 비용과 공간 비용이 누적된다. 핵심은 위협 모델이다. 매체 손상까지만 막으면 충분한지, 아니면 "메모리 비트 뒤집힘", "버스 손상", 혹은 "악의적 변조"까지 막아야 하는지에 따라 어느 층에 무엇을 둘지가 달라진다. 일반적으로 가장 위층(애플리케이션) 체크섬이 가장 넓은 범위를 보호하지만 가장 비싸다.

1. 무대 설정 — 클라이언트, 서버, RPC

NFS는 1980년대 Sun에서 만든 분산 파일 시스템으로, 서버가 디스크를 가지고 있고 여러 클라이언트가 네트워크로 그 파일들에 접근한다. 클라이언트의 시스템 콜은 평소처럼 가상 파일 시스템(VFS) 계층을 거치는데, NFS 마운트 포인트 아래로 들어가는 호출은 RPC 메시지로 변환되어 서버로 날아간다.

2. 무상태 서버 — 가장 결정적인 설계 결단

NFS의 가장 유명한 설계 선택은 "서버가 클라이언트의 상태를 기억하지 않는다"는 것이다. 어느 파일이 누구한테 열려 있는지, 어디까지 읽었는지 같은 정보를 서버가 보관하지 않는다. 모든 요청은 그 자체로 완전해야 한다 — "파일 핸들 X의 오프셋 4096부터 8KB 읽어 줘"처럼.

왜 이렇게 만들었느냐. 서버가 죽었다 깨어났을 때, 클라이언트들의 상태를 잃어버리고도 아무 일 없던 것처럼 처리하기 위해서다. 클라이언트는 그냥 같은 요청을 다시 보내면 된다. 서버는 갓 부팅한 직후라도 그 요청을 처음 보는 것처럼 처리할 수 있다.

3. 멱등 연산 — "같은 요청 또 와도 결과는 같다"

네트워크가 패킷을 잃어버리면 클라이언트는 같은 RPC를 또 보낸다. 서버는 그 요청이 처음인지 재시도인지 모른다. 그래서 NFS의 핵심 연산은 모두 멱등하게 설계되어 있다. READ와 WRITE는 오프셋과 길이를 명시하니 두 번 적용해도 결과가 같다. LOOKUP, GETATTR도 그냥 조회라 멱등이다.

// NFS 클라이언트의 재시도 루프
loop:
  send RPC to server
  wait with timeout
  if 응답 있음 -> 끝
  if 타임아웃 -> 다시 send (멱등하니까 안전)

다만 정말 멱등하지 않은 연산도 있다 — 예컨대 "이 디렉토리에서 mkdir foo". 두 번째 호출은 "이미 존재함"으로 실패할 수 있다. 이런 부분은 클라이언트가 결과를 적당히 해석해서 평탄하게 만든다.

4. 캐시 일관성 — 골치 아픈 그 문제

성능을 위해 클라이언트도 메모리 캐시를 쓴다. 그런데 클라이언트 A가 캐시한 파일을 클라이언트 B가 서버에서 갱신해 버리면, A는 옛날 값을 한참 동안 본다. NFS는 이 문제를 우아하게 풀기보다, 실용적인 절충안으로 처리한다.

대표적인 규칙이 close-to-open consistency다. 파일을 close할 때 클라이언트는 자기 변경을 서버로 flush하고, 다른 클라이언트가 open할 때 서버에서 attribute(특히 수정 시각)를 조회해 자기 캐시가 오래되었는지 확인한다. 즉 "파일을 닫고 다시 여는 시점"에는 어느 정도 일관성이 보장되지만, 이미 열려 있는 동안의 동시 수정은 보호되지 않는다.

여기서 정말 골치 아픈 문제가 생기는데, 캐시된 attribute 자체도 너무 자주 검증하면 RPC가 폭증한다. 그래서 attribute에 짧은 timeout을 걸어 일정 시간만 신뢰하는 식으로 타협한다. 분산 시스템에서 "강한 일관성"과 "현실적인 성능"은 늘 이런 식으로 줄다리기를 한다.

5. 서버 크래시와 마치 안 일어난 듯한 복구

서버가 갑자기 재부팅했다고 하자. 클라이언트의 RPC는 응답을 못 받고 타임아웃이 난다. 서버가 다시 살아나면 클라이언트는 같은 요청을 다시 보낸다. 무상태 + 멱등 덕분에 서버는 재부팅 직후라도 그 요청을 처리한다. 클라이언트의 사용자 입장에서는 "조금 멈췄다가 다시 됐다" 정도의 경험으로 그치는 것이 이상적이다.

1. 카네기멜런의 야심 — 한 캠퍼스를 한 파일 시스템으로

AFS(Andrew File System)는 1980년대 카네기멜런대에서 시작됐다. 캠퍼스 전체의 워크스테이션 수천 대가 같은 이름공간을 공유하게 하자는 큰 그림에서 출발했다. 이 규모에서 서버가 살아남으려면, 클라이언트가 가능한 한 서버를 안 부르고도 일하도록 만들어야 했다.

2. whole-file caching — 통째로 가져와서 통째로 쓴다

NFS가 블록 단위로 캐시를 한다면, 초기 AFS는 파일 전체를 클라이언트의 로컬 디스크에 통째로 복사해 와서 거기서 작업한다. 사용자가 읽기/쓰기를 하면 그 사본만 만지작거리고, close할 때 변경분이 있으면 한 번에 서버로 다시 올린다.

이 모델은 두 가지 큰 이점을 준다. 첫째, 같은 파일을 반복해 읽거나 쓰는 동안에는 네트워크가 전혀 끼어들지 않아서 성능이 매우 좋다. 둘째, 서버 부하가 "파일을 처음 가져올 때"와 "마지막에 올릴 때"로 한정되어, 같은 서버가 훨씬 많은 클라이언트를 감당할 수 있다.

3. callback — 서버가 "변했다"고 알려준다

그럼 캐시가 오래되었는지 어떻게 알까. NFS처럼 시간마다 서버에 묻는 대신, AFS는 callback이라는 우아한 약속을 쓴다. 클라이언트가 파일을 가져갈 때 서버는 "이 파일이 누군가에 의해 바뀌면 너한테 알려줄게"라는 약속을 등록해 둔다. 이후 다른 클라이언트가 그 파일을 새로 올리면, 서버는 callback을 가진 모든 클라이언트에게 "캐시 무효화" 통지를 쏜다.

// AFS의 일반적인 흐름
client open  -> 서버에서 파일 fetch + callback 등록
client read/write -> 로컬 사본만 사용 (서버 호출 0)
다른 client write+close -> 서버가 callback 통지 발사
client open(다시) -> callback 깨졌으면 새 사본 fetch

4. session semantics — close가 합쳐지는 시점

AFS는 close-on-write 의미론을 쓴다. 클라이언트가 파일을 close하기 전에는 변경이 다른 클라이언트에게 전혀 보이지 않다가, close 순간 그 변경이 서버에 반영되며 callback으로 다른 클라이언트들에게 통지가 간다. "내가 다 적은 다음에야 남이 본다"는 직관에 잘 맞고, 동시에 두 클라이언트가 같은 파일을 쓰는 일은 "마지막 close가 이긴다"는 단순한 규칙으로 처리된다.

5. 버전 비교와 callback 유실

네트워크가 끊겼다 살아나거나, 서버가 재부팅돼서 callback을 잃을 수 있다. 이런 경우 클라이언트는 다시 연결됐을 때 자기 캐시 항목들의 버전을 서버 쪽 버전과 비교한다. 일치하면 캐시는 여전히 유효하니 그대로 쓰고, 불일치하면 새 사본을 받는다. callback이라는 약속이 깨졌어도, 버전 비교가 마지막 안전망 역할을 한다.

6. NFS vs. AFS — 쓰임새가 가른 두 길

NFS는 "쉽게 마운트해서 쓰는 만능 네트워크 디스크"의 관점에서 발전했고, AFS는 "넓은 캠퍼스/조직의 글로벌 파일 공간"이라는 관점에서 발전했다. 큰 파일을 가끔 통째로 쓰는 워크로드에서 AFS가 빛나고, 작고 잦은 메타데이터 변경 워크로드에서는 NFS의 블록 단위 캐시가 유리할 때가 많다. 두 시스템은 라이벌이라기보다, 분산 파일 시스템 설계 공간의 두 극을 보여주는 사례에 가깝다.