B-3: 메모리 관리와 가상 메모리

안녕하세요, 홍순구 튜터입니다. CS 기초 다섯 번째 시간이에요.

지난 시간(B-2)에 컨텍스트 스위칭을 이야기하면서 제가 같은 말을 여러 번 했어요. "프로세스를 바꾸면 메모리 주소공간을 통째로 바꾼다", 그래서 캐시와 TLB가 식어 무겁다고요. 그런데 곰곰이 생각하면 이상하지 않나요? 실제 RAM은 컴퓨터에 한 덩어리뿐인데, 프로세스마다 "자기만의 메모리 주소공간"을 통째로 가진다는 게 어떻게 가능할까요? 게다가 B-1에서 그린 프로세스 메모리 구조 — 코드·데이터·힙·스택 — 그 스택과 힙의 주소는 대체 어디서 온 걸까요?

오늘 그 비밀을 풉니다. 답은 가상 메모리(virtual memory, 운영체제가 프로세스마다 만들어주는 가짜 주소공간)예요. 프로세스가 보는 주소는 사실 진짜 RAM 주소가 아니라, 운영체제가 프로세스마다 따로 만들어준 가짜 주소였습니다. 그래서 프로세스 A의 0번지와 프로세스 B의 0번지가 충돌 없이 공존할 수 있고, RAM보다 큰 프로그램도 돌아갑니다. B-1에서 본 스택과 힙도, 알고 보면 이 가상 주소 위에 놓여 있었어요.

메모리 영역은 기술 면접에서 빠지지 않는 단골이에요. "스택과 힙의 차이가 뭔가요"·"가상 메모리가 뭔가요"·"페이징이 뭔가요"·"LRU가 뭔가요" — 이 넷은 거의 반드시 나옵니다. 오늘 다 잡고 갑니다.

오늘 우리가 걸을 길은 이렇습니다.

   오늘의 여정 — 메모리 관리와 가상 메모리

   ① 스택과 힙 — 변수와 객체는 메모리 어디에 사는가 (면접 최단골)
   ② 단편화 — 메모리를 쓰다 보면 생기는 구멍 (내부·외부)
   ③ 가상 메모리 — 모두에게 "혼자 다 쓴다"는 환상을 주기
   ④ 페이징 — 주소를 고정 크기로 쪼개 흩어 담기
   ⑤ TLB와 세그멘테이션 — 변환을 빠르게, 그리고 다르게 나누기
   ⑥ 페이지 폴트 — 없으면 디스크에서 가져온다 (요구 페이징)
   ⑦ 페이지 교체 — 꽉 차면 누구를 내보낼까 (FIFO·LRU·LFU)
   ⑧ 스래싱과 GC — 교체가 일을 잡아먹을 때, 그리고 힙 청소

①~②는 메모리 그 자체의 이야기, ③~⑥은 그 메모리를 똑똑하게 쓰는 가상 메모리 이야기, ⑦~⑧은 메모리가 부족할 때 벌어지는 일이에요. 길목마다 면접 단골 질문이 숨어 있습니다.

💡 오늘 수업의 핵심 — "가상 메모리는 프로세스마다 '나 혼자 메모리를 다 쓴다'는 환상을 주고, 페이징으로 그 가짜 주소를 진짜 주소로 바꿔, 부족하면 디스크와 주고받으며 메모리를 관리하는 기술이다" 🎯

🎯 학습 목표

• 스택과 힙을 구분해 면접 최단골 질문에 답하고, 메모리를 쓰다 생기는 단편화(내부·외부)가 왜 생기는지 설명합니다.
• 가상 메모리가 왜 필요한지 이해하고, 페이징·페이지 테이블·TLB로 가상 주소가 어떻게 물리 주소로 바뀌는지 그립니다.
• 페이지 폴트와 요구 페이징, 페이지 교체 알고리즘(FIFO·LRU·LFU·Optimal)과 스래싱을 설명하고, 가비지 컬렉션 개념을 압니다.

Step 1: "스택과 힙 — 변수는 메모리 어디에 사는가"

B-1에서 프로세스의 메모리가 네 영역(코드·데이터·힙·스택)으로 나뉜다고 그렸어요. 오늘은 그중 면접에서 가장 자주 비교되는 둘, 스택(stack)과 힙(heap)을 깊이 들여다봅니다. "스택과 힙의 차이를 설명해보세요"는 운영체제·언어 면접의 1순위 단골이에요.

먼저 스택입니다. 스택은 함수가 호출될 때마다 쌓이는 메모리예요. 함수 하나가 호출되면 그 함수의 지역 변수, 매개변수, 돌아갈 주소(복귀 주소)를 묶은 덩어리(스택 프레임)가 스택 위에 얹히고, 함수가 끝나면 그 덩어리가 통째로 사라집니다. 쌓은 순서의 반대로 치워지는 후입선출(LIFO, Last-In First-Out) 구조죠. 누가 시키지 않아도 함수의 시작·끝에 맞춰 자동으로 할당되고 해제됩니다. 크기는 보통 컴파일 시점에 정해지고, 단순히 꼭대기를 가리키는 표시(스택 포인터)를 위아래로 옮기기만 하면 돼서 아주 빠릅니다. 대신 크기가 제한적이에요(그래서 함수가 끝없이 자기를 부르면 스택이 넘쳐 스택 오버플로가 났죠 — B-1에서 본 그 사고예요).

다음은 힙입니다. 힙은 프로그램이 실행 중에(런타임) 직접 요청해서 쓰는 메모리예요. "이만큼 메모리 주세요"라고 요청하면(new·malloc 같은 명령) 힙에서 공간을 떼어주고, 다 쓰면 돌려줘야 합니다. 누가 돌려주냐가 언어마다 갈려요. C·C++는 프로그래머가 손수 반납하고(free), 자바·파이썬 같은 언어는 가비지 컬렉터가 알아서 치웁니다(Step 8에서 다뤄요). 힙은 크기가 크고 수명이 자유롭지만(함수가 끝나도 남길 수 있음), 빈 공간을 찾아 떼어주고 관리하는 비용이 들어 스택보다 느립니다.

말로만 들으면 헷갈리니, 짧은 의사코드로 무엇이 어디에 잡히는지 봅시다. 특정 언어가 아니라, 여러분이 아는 어떤 언어로 읽어도 됩니다.

   function compute(a):            // a (매개변수)      → 스택
       sum = a + 1                 // sum (지역 변수)   → 스택
       data = new Array(1000)      // Array 객체(1000칸) → 힙
                                   // data (참조 변수)   → 스택,
                                   //                      가리키는 실체 → 힙
       return data                 // 함수 끝: 스택칸(a·sum·data)은 사라지고
                                   //          힙의 배열은 남음 (참조를 돌려줬으니)

여기서 핵심 한 가지. data라는 이름표(참조)는 스택에 있고, 그 이름표가 가리키는 실제 1000칸짜리 배열은 힙에 있어요. 함수가 끝나면 스택의 이름표는 사라지지만, 힙의 배열은 누군가 그 참조를 들고 있는 한 살아남습니다. 이게 "스택은 자동으로 사라지고, 힙은 따로 관리한다"의 실제 모습이에요.

그림으로 보면 프로세스의 메모리 한쪽 끝엔 스택이, 반대쪽엔 힙이 있고, 둘은 서로를 향해 자랍니다.

   높은 주소 (high address)
   ┌──────────────┐
   │ Stack        │──── 함수 호출마다 쌓임: 지역변수·매개변수·복귀주소
   │     ↓        │      자동 할당·해제(함수 끝나면 사라짐), 아래로 자람
   │              │
   │     ↑        │      직접 할당·해제(또는 GC), 위로 자람
   │ Heap         │──── new/malloc 으로 런타임에 요청한 객체
   ├──────────────┤
   │ Data         │──── 전역·정적 변수
   ├──────────────┤
   │ Code (Text)  │──── 실행할 기계어 명령
   └──────────────┘
   낮은 주소 (low address)

비유하면 스택은 구내식당의 식판 더미예요. 위에 차곡차곡 쌓고, 쓸 땐 맨 위 것부터 꺼내죠(후입선출). 규칙이 단순하니 빠르고, 누가 정리 안 해도 알아서 정돈됩니다. 힙은 거대한 물품 창고고요. "선반 좀 빌릴게요" 하고 원하는 만큼 받아 쓰지만, 다 쓰면 직접 반납해야 하고, 빈 선반을 찾아주는 관리인이 있어야 해서 식판 더미보다 굼뜹니다.

🎯 면접에서는 이렇게 답하세요

"스택은 함수 호출마다 지역 변수·매개변수·복귀 주소가 쌓이는 영역으로, 후입선출 구조이고 함수의 시작·끝에 맞춰 자동으로 할당·해제됩니다. 스택 포인터만 옮기면 돼서 빠르지만 크기가 작죠. 힙은 실행 중에 직접 요청해 쓰는 영역으로, 크기가 크고 수명이 자유롭지만 빈 공간을 찾아 관리해야 해 느립니다. 해제는 C 계열은 수동, 자바·파이썬은 가비지 컬렉터가 자동으로 합니다. 한마디로 작고 함수와 수명을 같이하는 값은 스택에, 크거나 함수보다 오래 살아야 하는 객체는 힙에 둡니다. 그리고 객체를 가리키는 참조는 스택에, 객체 본체는 힙에 있는 경우가 많습니다."

💡 스택은 알아서 정리되니 단편이 안 생기는데, 힙은 다릅니다. 원하는 만큼 떼어 쓰고 아무 때나 반납하다 보면 메모리에 구멍이 숭숭 뚫려요. 이 "구멍" 문제가 가상 메모리가 나온 동기 중 하나입니다. 다음 Step에서 단편화를 봅니다.

Step 2: "단편화 — 메모리를 쓰다 보면 생기는 구멍"

힙처럼 메모리를 원하는 만큼 떼어 쓰고 아무 때나 반납하면, 시간이 지날수록 메모리가 깔끔한 한 덩어리가 아니라 여기저기 빈틈이 뚫린 누더기가 됩니다. 이 빈틈 때문에 메모리가 충분한데도 못 쓰는 현상을 단편화(fragmentation)라고 해요. 단편화에는 두 종류가 있습니다.

먼저 외부 단편화(external fragmentation)예요. 빈 공간의 총량은 충분한데, 그게 작은 조각으로 흩어져 있어서 큰 요청을 못 받는 상황입니다. 메모리를 한 줄로 그려보면 이렇게 됩니다.

   메모리 한 줄:  [ P1 ][ free 20 ][ P2 ][ free 30 ][ P3 ][ free 25 ]

   빈 공간 합 = 20 + 30 + 25 = 75
   그런데 "연속된 60칸"을 요청하면? → 못 받습니다 (빈칸이 흩어져 있어서)

빈칸을 다 합치면 75칸이라 60칸 요청을 받고도 남는데, 한 군데도 60칸이 연속으로 비어 있질 않아 거절당해요. 주차장을 떠올리면 쉽습니다. 빈자리가 띄엄띄엄 10칸 있어도, 버스(연속 5칸이 필요한)는 댈 곳이 없는 것과 같아요. 이걸 해결하려고 흩어진 빈칸을 한쪽으로 몰아 큰 덩어리로 만드는 압축(compaction)을 하기도 하지만, 메모리에 있는 내용을 다 옮겨야 해서 비용이 큽니다.

다음은 내부 단편화(internal fragmentation)예요. 메모리를 정해진 크기 블록 단위로 나눠주다 보니, 요청보다 큰 블록을 줘서 블록 안에 남는 공간입니다. 예를 들어 메모리를 16칸 단위로만 떼어준다면, 10칸이 필요한 요청에도 16칸짜리 블록을 줘야 해서 6칸이 그 안에서 놀게 돼요. 쓰지도 못하고 비어 있죠. 택배 상자에 비유하면, 작은 물건 하나를 큰 규격 상자에 담아 보내서 상자 안이 텅 비는 것과 같습니다.

정리하면 외부 단편화는 "할당된 블록들 사이에 흩어진 빈틈", 내부 단편화는 "할당된 블록 안에 남는 빈틈"이에요. 둘 다 메모리를 낭비한다는 점은 같지만, 생기는 위치가 다릅니다.

🎯 면접에서는 이렇게 답하세요

"단편화는 메모리가 충분한데도 빈틈 때문에 못 쓰는 현상입니다. 외부 단편화는 할당된 블록들 사이에 빈 공간이 작게 흩어져, 총량은 충분해도 연속된 큰 공간 요청을 못 받는 것이고, 내부 단편화는 정해진 크기 블록으로 할당하다 보니 요청보다 큰 블록을 줘서 블록 안에 남는 공간입니다. 외부 단편화는 빈칸을 몰아주는 압축으로 줄일 수 있지만 비용이 커서, 메모리를 고정 크기 조각으로 잘라 흩어 담는 페이징으로 외부 단편화를 근본적으로 없애는 방향으로 발전했습니다."

💡 단편화의 골칫거리, 그리고 "프로세스마다 자기만의 주소공간"이라는 지난 시간의 수수께끼 — 이 둘을 한 번에 푸는 큰 발상이 있습니다. 프로세스가 보는 주소를 진짜 주소와 분리하는 것, 바로 가상 메모리예요. 다음 Step에서 만납니다.

Step 3: "가상 메모리 — 모두에게 '혼자 다 쓴다'는 환상을 주기"

이제 지난 시간에 남긴 수수께끼를 풉니다. 실제 RAM은 한 덩어리뿐인데, 어떻게 프로세스마다 "자기만의 주소공간"을 통째로 가질까요?

만약 프로그램이 물리 메모리 주소를 직접 쓴다고 상상해봅시다. 문제가 한가득이에요. 프로세스 A가 0x1000번지를 쓰고 싶은데 프로세스 B도 같은 0x1000번지를 쓰려 하면 충돌합니다. A가 실수로(혹은 악의로) B의 주소를 건드리면 남의 메모리를 침범하고요. 게다가 프로그램이 RAM 용량보다 크면 아예 올릴 수가 없습니다. 메모리를 직접 쓰게 두면 이런 사고가 끊이질 않아요.

그래서 운영체제는 영리한 거짓말을 합니다. 각 프로세스에게 "너는 0번지부터 시작하는 거대한 메모리를 혼자 다 쓴다"는 환상을 줘요. 프로세스가 보는 이 가짜 주소가 가상 주소(virtual address)이고, 프로세스마다 따로 갖는 이 환상의 공간이 가상 주소공간입니다. 실제 RAM의 진짜 주소는 물리 주소(physical address)고요. 프로세스와 CPU는 가상 주소만 보고, 그 가상 주소를 실제 물리 주소로 바꿔주는 전담 하드웨어가 있습니다. 이게 MMU(Memory Management Unit, 메모리 관리 장치)예요.

   프로세스 A: 가상주소 0 ~ MAX  (나만의 공간이라 믿음)
   프로세스 B: 가상주소 0 ~ MAX  (나만의 공간이라 믿음)
            │
            │   MMU 가 가상 → 물리로 변환
            ▼
   ┌────────────────────────┐
   │  Physical Memory (RAM) │──── 실제로는 하나뿐. A와 B의 조각이 섞여 올라감
   └────────────────────────┘

이 환상 덕에 모든 문제가 한 번에 풀립니다. A의 가상 0번지와 B의 가상 0번지는 MMU가 서로 다른 물리 주소로 바꿔주니 충돌하지 않아요. A의 가상 주소는 A에게 허락된 물리 주소로만 변환되니, B의 메모리를 넘볼 수도 없습니다(보호). 그리고 가상 주소공간 전부를 RAM에 올릴 필요가 없어, RAM보다 큰 프로그램도 돌릴 수 있죠(이건 Step 6에서 자세히).

여기서 지난 시간 이야기가 이어집니다. B-2에서 "프로세스를 바꾸면 주소공간을 통째로 바꾼다"고 했죠? 그 정체가 바로 이거예요. 프로세스마다 "가상 → 물리" 변환표가 다르니, 컨텍스트 스위칭 때 그 변환표를 통째로 갈아 끼우는 겁니다. 그래서 캐시와 TLB가 식는 거고요. 또 B-1에서 그린 스택과 힙도, 사실은 이 가상 주소 위에 놓여 있었습니다. 프로세스가 "내 스택은 높은 주소에 있어"라고 믿는 그 주소가 가상 주소였던 거예요.

비유하면 아파트 동·호수예요. 모든 입주민은 "101동 5층"처럼 자기 기준의 주소를 쓰지만, 우편물을 배달하는 집배원(MMU)은 그걸 실제 지번·좌표로 바꿔 정확한 집에 꽂아줍니다. 입주민끼리 같은 "5층"이어도 실제 위치는 다 다르니 충돌이 없죠.

🎯 면접에서는 이렇게 답하세요

"가상 메모리는 각 프로세스에게 '0번지부터 시작하는 메모리를 혼자 다 쓴다'는 독립된 주소공간의 환상을 주는 기법입니다. 프로세스가 보는 건 가짜 주소인 가상 주소이고, 실제 RAM의 물리 주소로는 MMU라는 하드웨어가 변환해줍니다. 덕분에 프로세스끼리 주소가 충돌하지 않고(같은 가상 0번지도 다른 물리 주소로 변환), 서로의 메모리를 침범하지 못하며(보호), 가상 주소공간 전부를 RAM에 올릴 필요가 없어 물리 메모리보다 큰 프로그램도 돌릴 수 있습니다. 컨텍스트 스위칭 때 무거운 이유도, 프로세스마다 이 가상-물리 변환 정보가 달라 통째로 교체되기 때문입니다."

💡 그럼 MMU는 가상 주소를 물리 주소로 어떻게 바꿀까요? 그 변환의 실제 방법이 바로 페이징입니다. 외부 단편화까지 한 방에 없애는, 가상 메모리의 핵심 구현이에요. 다음 Step에서 봅니다.

Step 4: "페이징 — 주소를 고정 크기로 쪼개 흩어 담기"

가상 주소를 물리 주소로 바꾸는 가장 널리 쓰는 방법이 페이징(paging)이에요. 핵심 발상은 단순합니다. 메모리를 똑같은 크기의 조각으로 잘라두자.

가상 주소공간을 고정 크기 조각으로 자른 것을 페이지(page), 물리 메모리를 같은 크기로 자른 것을 프레임(frame)이라고 해요. 둘은 크기가 같습니다(보통 4KB). 페이지 하나는 비어 있는 프레임 아무 곳에나 들어갈 수 있어요. 어느 프레임에 담겼는지를 기록해두는 표가 페이지 테이블(page table)입니다. 프로세스마다 하나씩 갖고, "가상 페이지 번호 → 물리 프레임 번호" 짝을 담고 있어요.

   [가상 주소공간]            [페이지 테이블]              [물리 메모리]
     Page 0  ──────────▶   0 │ Frame 3   ──────────▶   Frame 1: Page 2
     Page 1  ──────────▶   1 │ Frame 7   ──────────▶   Frame 3: Page 0
     Page 2  ──────────▶   2 │ Frame 1   ──────────▶   Frame 7: Page 1

   가상 페이지가 물리 프레임에 흩어져 담겨도, 페이지 테이블만 보면 찾아간다

MMU가 주소를 바꾸는 과정은 이래요. 가상 주소는 "페이지 번호 + 페이지 안에서의 위치(오프셋)"로 쪼개집니다. MMU는 페이지 번호로 페이지 테이블을 찾아 물리 프레임 번호를 얻고, 거기에 오프셋을 붙여 최종 물리 주소를 만들어요. 예를 들어 가상 주소가 "페이지 2번의 100번째 칸"이면, 페이지 테이블에서 "페이지 2 → 프레임 1"을 읽어 "프레임 1의 100번째 칸"으로 바꾸는 식입니다.

페이징의 진짜 강점은 외부 단편화가 사라진다는 거예요. 페이지와 프레임이 다 똑같은 크기라, 비어 있는 프레임이면 어디든 페이지를 넣을 수 있습니다. 빈칸이 흩어져 있어도 상관없어요. 어차피 한 조각씩 들어가니까요. Step 2에서 본 "연속 60칸이 없어 거절" 같은 일이 안 생깁니다. 대신 작은 대가가 있어요. 프로그램 크기가 페이지 크기의 딱 떨어지는 배수가 아니면, 마지막 페이지에 빈 공간이 조금 남습니다(내부 단편화). 하지만 페이지 하나 크기(4KB) 안쪽의 낭비라 외부 단편화에 비하면 사소해요.

비유하면 이삿짐을 똑같은 규격의 상자에 나눠 담는 거예요. 짐을 규격 상자들에 쪼개 담으면, 트럭 짐칸 어디가 비었든 상자를 척척 끼워 넣을 수 있죠(빈칸이 흩어져 있어도 OK). 어느 상자가 어디 실렸는지는 송장(페이지 테이블)에 적어두면 됩니다. 큰 가구를 통째로 실으려 낑낑대는 대신, 규격 상자로 쪼개니 짐 싣기가 유연해지는 거예요.

🎯 면접에서는 이렇게 답하세요

"페이징은 가상 주소공간을 고정 크기 페이지로, 물리 메모리를 같은 크기 프레임으로 나눠, 페이지를 빈 프레임 아무 곳에나 담는 기법입니다. 어느 페이지가 어느 프레임에 있는지는 페이지 테이블에 기록하고, MMU가 가상 주소의 페이지 번호로 테이블을 찾아 프레임 번호로 변환합니다. 페이지와 프레임 크기가 같아 빈 프레임이면 어디든 넣을 수 있어서 외부 단편화가 사라지는 게 핵심 장점입니다. 대신 마지막 페이지에 약간의 내부 단편화가 생기고, 페이지 테이블을 위한 메모리가 추가로 듭니다."

💡 그런데 변환할 때마다 메모리에 있는 페이지 테이블을 한 번씩 들춰봐야 한다면, 메모리 접근이 두 배가 되어 느려지겠죠. 이걸 해결하는 작은 캐시가 TLB예요. 그리고 페이징과는 다른 방식으로 메모리를 나누는 세그멘테이션도 함께 봅니다. 다음 Step.

Step 5: "TLB와 세그멘테이션 — 변환을 빠르게, 그리고 다르게 나누기"

페이징에는 숨은 비용이 하나 있어요. 가상 주소를 물리 주소로 바꾸려면 페이지 테이블을 봐야 하는데, 이 테이블이 메모리에 있습니다. 그러면 데이터 한 번 읽는 데 메모리 접근이 두 번 필요해져요. 페이지 테이블 읽기(어느 프레임?) 한 번, 실제 데이터 읽기 한 번. 메모리 접근이 두 배가 되니 느립니다.

그래서 TLB(Translation Lookaside Buffer, 변환 색인 버퍼)를 둡니다. TLB는 최근에 변환한 "페이지 → 프레임" 결과를 담아두는 아주 작고 빠른 캐시예요. A-2에서 배운 캐시가 자주 쓰는 데이터를 CPU 가까이 두어 빠르게 했듯, TLB는 자주 쓰는 주소 변환을 담아두어 빠르게 합니다. 주소를 변환할 때 MMU는 먼저 TLB부터 봐요. 거기 있으면(TLB 히트) 페이지 테이블을 안 거치고 바로 물리 주소를 얻습니다. 없으면(TLB 미스) 페이지 테이블까지 가서 찾고, 그 결과를 TLB에 채워둬요. 프로그램은 비슷한 주소를 연달아 쓰는 경향(지역성)이 있어서, TLB 적중률은 보통 매우 높습니다.

지난 시간 이야기와 여기서 만나요. B-2에서 "컨텍스트 스위칭 때 TLB가 비워져 무겁다"고 했죠? 프로세스마다 페이지 테이블이 다르니, 프로세스를 바꾸면 이전 프로세스의 변환 정보가 든 TLB는 새 프로세스에게 쓸모가 없어 비워야 하는 거예요. 그래서 전환 직후 한동안 TLB 미스가 잦아 느려집니다.

이제 페이징과 다른 방식으로 메모리를 나누는 세그멘테이션(segmentation)을 짧게 봅시다. 페이징이 의미를 따지지 않고 똑같은 크기로 쪼갠다면, 세그멘테이션은 프로그램을 논리적 의미 단위로 나눠요. 코드 세그먼트, 데이터 세그먼트, 스택 세그먼트처럼요. 크기는 단위마다 제각각(가변)입니다. 장점은 의미 단위라 보호와 공유가 자연스럽다는 것(예: 코드 세그먼트는 읽기 전용으로, 여러 프로세스가 공유). 단점은 크기가 제각각이라 외부 단편화가 다시 생긴다는 거예요. 그래서 오늘날 대부분의 시스템은 페이징을 주로 쓰고, 필요하면 둘을 결합해 씁니다.

🎯 면접에서는 이렇게 답하세요

"TLB는 최근의 '페이지 → 프레임' 변환 결과를 담는 작고 빠른 캐시입니다. 페이징은 변환을 위해 메모리의 페이지 테이블을 봐야 해 접근이 두 배가 되는데, TLB에 있으면(히트) 테이블을 건너뛰고 바로 변환해 이 비용을 줄입니다. 지역성 덕에 적중률이 높죠. 컨텍스트 스위칭 때 TLB를 비우는 건 프로세스마다 변환 정보가 다르기 때문입니다. 한편 세그멘테이션은 메모리를 코드·데이터·스택 같은 논리적 의미 단위(가변 크기)로 나누는 방식으로, 보호·공유가 자연스럽지만 가변 크기라 외부 단편화가 생깁니다. 그래서 오늘날은 외부 단편화가 없는 페이징을 주로 씁니다."

💡 지금까지는 필요한 페이지가 모두 물리 메모리에 있다고 가정했어요. 그런데 가상 주소공간이 물리 메모리보다 클 수 있다고 했죠. 그럼 RAM에 없는 페이지를 건드리면 무슨 일이 벌어질까요? 여기서 페이지 폴트와 디스크가 등장합니다. 다음 Step.

Step 6: "페이지 폴트 — 없으면 디스크에서 가져온다"

가상 주소공간이 물리 메모리보다 클 수 있다고 했는데, 비결이 여기 있어요. 운영체제는 프로그램의 모든 페이지를 RAM에 올려두지 않습니다. 지금 당장 필요한 페이지만 올려두고, 나머지는 디스크에 둬요. 페이지가 실제로 필요해지는 순간(접근될 때)에야 비로소 디스크에서 RAM으로 가져오는 이 방식을 요구 페이징(demand paging)이라고 합니다.

그럼 CPU가 RAM에 아직 없는 페이지를 건드리면 어떻게 될까요? 이때 발생하는 게 페이지 폴트(page fault, 페이지 부재)예요. 이름은 "결함(fault)"이지만 오류가 아니라, "그 페이지 지금 RAM에 없어요"라는 신호입니다. 페이지 폴트가 나면 운영체제가 끼어들어 이렇게 처리해요. ① 그 페이지를 디스크에서 찾아 ② 비어 있는 프레임에 올리고 ③ 페이지 테이블을 갱신한 뒤 ④ 멈췄던 명령을 다시 실행합니다. 이 과정이 끝나면 프로그램은 아무 일 없었다는 듯 계속 돌아가요.

이때 디스크의 한 영역을 메모리의 연장처럼 씁니다. 메모리가 부족하면 당장 안 쓰는 페이지를 디스크로 내보내고(swap out), 필요해지면 다시 가져오는(swap in) 거예요. 이 영역을 스왑 영역(swap)이라고 합니다. 덕분에 RAM이 8GB라도, 디스크를 빌려 그보다 큰 프로그램을 돌릴 수 있는 거예요.

여기서 A-2의 메모리 계층이 다시 등장합니다. 빠른 RAM과 느린 디스크 사이를 페이지가 오가는 거죠.

   ┌────────────┐
   │ RAM        │──── 지금 쓰는 페이지들 (빠름)
   └────────────┘
        ▲   │   page fault → 없는 페이지를 디스크에서 가져옴 (swap in)
        │   ▼   메모리가 부족하면 안 쓰는 페이지를 내보냄 (swap out)
   ┌────────────┐
   │ Disk (Swap)│──── 당장 안 쓰는 페이지 보관 (느림)
   └────────────┘

다만 페이지 폴트는 비쌉니다. A-2에서 봤듯 디스크는 RAM보다 수만 배 느려요. 페이지 폴트 한 번은 느린 디스크를 다녀와야 하니, RAM에서 바로 찾는 것과는 비교가 안 되게 오래 걸립니다. 그래서 페이지 폴트가 가끔 나는 건 가상 메모리의 정상 작동이지만, 너무 자주 나면 프로그램이 느려져요(이게 Step 8의 스래싱으로 이어집니다).

비유하면 책상과 책장이에요. 자주 보는 책 몇 권만 책상(RAM)에 두고, 나머지는 책장(디스크)에 꽂아둡니다. 책상에 없는 책이 필요하면(페이지 폴트) 일어나서 책장까지 다녀와야 하니 시간이 걸리죠(느린 디스크). 그래도 책상이 작아도 책장 전체를 활용할 수 있으니, 작은 책상으로 많은 책을 보는 셈입니다. A-2에서 본 캐시·지역성 이야기가 메모리와 디스크 사이로 한 층 더 확장된 거예요.

🎯 면접에서는 이렇게 답하세요

"운영체제는 프로그램의 모든 페이지를 RAM에 올리지 않고, 필요해질 때 디스크에서 가져오는 요구 페이징을 씁니다. CPU가 RAM에 없는 페이지를 접근하면 페이지 폴트가 발생하고, 운영체제가 그 페이지를 디스크에서 빈 프레임으로 올린 뒤 멈췄던 명령을 다시 실행합니다. 메모리가 부족하면 안 쓰는 페이지를 디스크의 스왑 영역으로 내보내고(swap out) 필요하면 다시 가져와(swap in), 물리 메모리보다 큰 프로그램도 돌릴 수 있습니다. 다만 페이지 폴트는 느린 디스크를 다녀와야 해서 비싸기 때문에, 자주 쓰는 페이지는 RAM에 머물러야 하고 폴트가 너무 잦으면 성능이 급락합니다."

💡 그런데 디스크에서 페이지를 가져오려는데 RAM의 프레임이 꽉 차 있으면 어떡할까요? 기존 페이지 하나를 내보내고 그 자리를 비워야 합니다. 그럼 누구를 내보낼까요? 이 선택이 성능을 좌우하는 페이지 교체 알고리즘이에요. 면접 단골 LRU가 여기서 나옵니다. 다음 Step.

Step 7: "페이지 교체 — 꽉 차면 누구를 내보낼까"

페이지 폴트가 나서 디스크에서 페이지를 가져오려는데, 물리 메모리의 프레임이 전부 차 있다면? 기존 페이지 하나를 골라 내보내고(victim, 희생 페이지) 그 자리에 새 페이지를 올려야 합니다. 이 "누구를 내보낼까"를 정하는 게 페이지 교체 알고리즘(page replacement)이에요. 목표는 분명합니다. 앞으로 페이지 폴트가 가장 적게 나도록 victim을 고르는 것. 대표 넷을 봅시다.

FIFO(First-In First-Out, 선입선출)는 가장 먼저 들어온 페이지를 내보내요. 단순하지만 함정이 있습니다. 오래전에 올라왔어도 지금 자주 쓰는 페이지를 "오래됐다"는 이유로 내쫓을 수 있어요. 게다가 프레임을 늘렸는데 오히려 폴트가 더 느는 기현상(벨라디의 모순, Belady's anomaly)도 FIFO에서 나타납니다.

Optimal(최적)은 앞으로 가장 오랫동안 안 쓸 페이지를 내보냅니다. 폴트가 이론상 가장 적지만, 미래에 무엇을 쓸지 미리 알아야 해서 현실에선 구현 불가예요. 다른 알고리즘이 얼마나 좋은지 재는 이론적 기준선으로만 씁니다.

LRU(Least Recently Used, 가장 오래 안 쓴)는 과거에 가장 오랫동안 안 쓰인 페이지를 내보내요. "최근에 안 썼으면 앞으로도 안 쓸 것"이라는 지역성 가정에 기댄 거죠. 미래를 못 보는 대신 과거로 미래를 추측하는 셈인데, 이게 Optimal에 꽤 근접해서 실무의 주력입니다(면접에서 묻는 그 LRU예요). 다만 페이지를 쓸 때마다 "방금 썼다"고 시간을 기록해야 해 비용이 있어, 실제로는 이를 단순화한 근사 방식(클럭 알고리즘 등)을 많이 씁니다.

LFU(Least Frequently Used, 가장 적게 쓴)는 사용 횟수가 가장 적은 페이지를 내보냅니다. 자주 쓰는 걸 남긴다는 발상은 좋지만, 과거에 잠깐 엄청 자주 썼다가 이제 안 쓰는 페이지를 "횟수가 많다"는 이유로 못 버리는 약점이 있어요.

가장 중요한 LRU가 실제로 어떻게 도는지, 작은 예로 따라가 봅시다. 프레임이 3칸이고, 페이지를 이 순서로 참조한다고 할게요.

   참조 순서:  A  B  C  A  D  B     (프레임 3칸, LRU 기준)

   A → [ A  ·  · ]   폴트 — 빈 프레임에 적재
   B → [ A  B  · ]   폴트
   C → [ A  B  C ]   폴트 (이제 꽉 참)
   A → [ A  B  C ]   히트! A를 방금 다시 썼으니 A가 '가장 최근'
   D → [ A  D  C ]   폴트 — 가장 오래 안 쓴 B를 내보내고 D 적재
   B → [ A  D  B ]   폴트 — 가장 오래 안 쓴 C를 내보내고 B 적재

   결과: 폴트 5번 · 히트 1번

여기서 D를 올릴 때(네 번째 줄 다음)를 눈여겨보세요. 그 직전에 A를 다시 썼기 때문에, "가장 오래 안 쓴" 페이지는 A가 아니라 B입니다. 그래서 LRU는 B를 내보내고 A를 남겨요. 만약 FIFO였다면 "가장 먼저 들어온" A를 내보냈을 텐데, A는 방금 막 다시 쓴 페이지죠. LRU는 "방금 썼으니 또 쓸 것"이라 보고 A를 지키는 겁니다. 이 한 끗 차이가 폴트 수를 가르고, LRU가 FIFO보다 대체로 나은 이유예요.

비유하면 책상에 책 세 권만 둘 수 있을 때 어떤 책을 책장으로 돌려보낼지 고르는 거예요. FIFO는 "산 지 가장 오래된 책"을, LRU는 "가장 오래 안 펼친 책"을 치웁니다. 지금 한창 보는 책이라면, 산 지 오래됐어도 안 치우는 LRU가 합리적이죠.

🎯 면접에서는 이렇게 답하세요

"물리 메모리가 꽉 찼을 때 어떤 페이지를 내보낼지 정하는 게 페이지 교체 알고리즘이고, 목표는 페이지 폴트 최소화입니다. FIFO는 가장 먼저 들어온 페이지를 내보내 단순하지만, 자주 쓰는 페이지도 내쫓을 수 있고 벨라디의 모순이 있습니다. Optimal은 앞으로 가장 늦게 쓸 페이지를 내보내 폴트가 최소지만 미래를 알아야 해 구현 불가능한 이론적 기준입니다. LRU는 가장 오래 안 쓰인 페이지를 내보내는데, '최근에 안 썼으면 앞으로도 안 쓸 것'이라는 지역성에 기대 Optimal에 근접해 실무에서 가장 많이 씁니다. LFU는 사용 횟수가 가장 적은 페이지를 내보내지만, 예전에 자주 쓴 페이지를 못 버리는 약점이 있습니다."

💡 페이지 교체로 메모리 부족을 그럭저럭 버틴다지만, 부족이 너무 심하면 어떻게 될까요? 페이지를 넣자마자 또 내보내고, 그게 또 필요해 가져오는 일이 끝없이 반복되면 — 컴퓨터가 일은 안 하고 디스크만 들락거립니다. 이 사고가 스래싱이에요. 마지막 Step에서 스래싱과, 힙을 자동으로 청소하는 GC를 한 입 보고 마무리합니다.

Step 8: "스래싱과 GC — 교체가 일을 잡아먹을 때, 그리고 힙 청소"

페이지 교체가 메모리 부족을 버티게 해준다지만, 부족이 도를 넘으면 교체 자체가 재앙이 됩니다. 동시에 도는 프로세스가 너무 많아 각자에게 돌아갈 프레임이 턱없이 부족하면, 페이지를 하나 가져오자마자 다른 페이지를 내보내야 하고, 내보낸 그 페이지가 곧바로 또 필요해져 다시 가져오는 일이 끝없이 반복돼요. CPU는 정작 일은 못 하고 디스크에서 페이지를 들이고 내보내는 데만 시간을 다 씁니다. 이 현상이 스래싱(thrashing)이에요.

스래싱이 무서운 건, 어느 선을 넘으면 성능이 갑자기 무너진다는 점입니다. 동시 프로세스 수를 늘릴수록 CPU 이용률이 오르다가, 임계점을 넘는 순간 페이지 폴트가 폭증하며 이용률이 곤두박질쳐요.

   CPU 이용률(%)
     ▲
     │         ___
     │       /     \____        ← 어느 선을 넘으면 급락 = 스래싱
     │     /             \___
     │   /                   \___
     │ /
     └──────────────────────────▶  동시에 도는 프로세스 수
       프로세스를 늘릴수록 이용률이 오르다가, 임계점을 넘으면 떨어진다

원인은 각 프로세스가 "지금 자주 쓰는 페이지 묶음"을 RAM에 못 올려서예요. 이 묶음을 워킹셋(working set, 한 프로세스가 일정 기간 실제로 쓰는 페이지 집합)이라고 합니다. 워킹셋만큼은 RAM에 들어가 있어야 폴트가 적은데, 프로세스가 너무 많아 그조차 안 되면 스래싱이 터지죠. 그래서 해법은 동시 프로세스 수를 줄이거나(일부를 잠시 통째로 swap out), 워킹셋이 들어갈 만큼 메모리를 확보하는 것입니다. 가장 현실적인 답은 물론 RAM을 늘리는 거고요.

비유하면 너무 작은 책상에서 공부하는 거예요. 펼쳐야 할 책이 다섯 권인데 책상엔 한 권만 올라가면, 책을 폈다 덮었다 책장을 들락거리느라 정작 공부는 한 줄도 못 합니다. 책상(RAM)이 워킹셋(펼쳐야 할 책들)을 못 받쳐주면, 일은 안 되고 책 나르기만 반복되는 거죠.

마지막으로 가비지 컬렉션(garbage collection, GC)을 한 입만 봅니다. Step 1에서 힙에 객체를 동적 할당한다고 했죠. 그 객체를 다 쓰고 나면 메모리를 돌려줘야 하는데, 누가 돌려줄까요? C·C++는 프로그래머가 손수 반납하지만(free), 깜빡하면 안 쓰는 객체가 힙에 계속 쌓이는 메모리 누수(memory leak)가 납니다. 자바·파이썬·자바스크립트 같은 언어는 가비지 컬렉터가 이 일을 자동으로 해요. "이제 아무도 가리키지 않는(참조가 끊긴) 객체"를 찾아 알아서 회수합니다. 덕분에 프로그래머가 메모리 해제를 신경 안 써도 되죠. 대신 GC가 도는 동안 잠깐 프로그램이 멈출 수 있다는 대가가 있어요. GC가 구체적으로 어떻게 안 쓰는 객체를 찾아 치우는지(마크-스위프, 세대별 GC 등)는 메모리를 직접 다루는 언어 과목에서 깊이 배웁니다. 여기서는 "힙의 청소를 자동으로 해주는 장치"라는 개념까지면 충분해요.

🎯 면접에서는 이렇게 답하세요

"스래싱은 물리 메모리가 부족해 페이지 교체가 끝없이 반복되며, CPU가 일은 못 하고 디스크 입출력에만 시간을 쓰는 현상입니다. 동시에 도는 프로세스가 너무 많아 각 프로세스의 워킹셋(지금 자주 쓰는 페이지 묶음)조차 RAM에 못 올릴 때 발생하죠. 어느 임계점을 넘으면 CPU 이용률이 급락하는 게 특징입니다. 해법은 동시 프로세스 수를 줄이거나 메모리를 늘려 워킹셋을 보장하는 것입니다. 한편 가비지 컬렉션은 힙에서 더 이상 참조되지 않는 객체를 자동으로 회수해 메모리 누수를 막는 기법으로, 자바·파이썬 등이 씁니다. 편리하지만 GC가 도는 동안 잠깐 멈출 수 있는 대가가 있습니다."

💡 스택과 힙부터 가상 메모리, 페이징, 페이지 교체, 스래싱까지 — 메모리가 어떻게 관리되는지 한 바퀴 돌았어요. 컴퓨터가 한정된 RAM으로 어떻게 여러 프로그램에게 "넉넉한 자기만의 메모리"라는 환상을 주는지 보이시죠? 정리하고 다음 시간 다리를 놓을게요.

마무리

오늘 배운 핵심 세 가지

🎯 하나, 스택은 함수 호출마다 자동으로 쌓이고 치워지는 빠르고 작은 영역(후입선출), 힙은 실행 중에 직접 요청해 쓰는 크고 자유롭지만 느린 영역입니다. 작고 함수와 수명을 같이하는 값은 스택에, 크거나 오래 살아야 하는 객체는 힙에 두죠. 그리고 힙처럼 자유롭게 쓰다 보면 메모리에 빈틈이 생기는데, 블록들 사이의 빈틈이 외부 단편화, 블록 안의 빈틈이 내부 단편화입니다.

🎯 둘, 가상 메모리는 프로세스마다 "나 혼자 메모리를 다 쓴다"는 독립 주소공간의 환상을 줘, 주소 충돌을 막고(보호) RAM보다 큰 프로그램도 돌립니다. 가짜 가상 주소를 진짜 물리 주소로 바꾸는 게 MMU이고, 그 방법이 메모리를 고정 크기 페이지/프레임으로 쪼개 흩어 담는 페이징이에요(외부 단편화 제거). 변환을 빠르게 하는 캐시가 TLB고요. 모든 페이지를 RAM에 안 올리고 필요할 때 디스크에서 가져오는 요구 페이징 덕에, RAM에 없는 페이지를 건드리면 페이지 폴트가 나 디스크에서 가져옵니다.

🎯 셋, 프레임이 꽉 차면 어떤 페이지를 내보낼지 정하는 페이지 교체가 필요한데, FIFO(단순·벨라디 모순)·Optimal(이론적 최선·구현 불가)·LRU(가장 오래 안 쓴·실무 주력)·LFU(가장 적게 쓴)가 있어요. 그중 LRU가 지역성에 기대 Optimal에 가장 가깝습니다. 메모리가 너무 부족해 교체만 반복되며 성능이 급락하는 게 스래싱이고, 힙의 안 쓰는 객체를 자동 회수하는 게 가비지 컬렉션입니다.

다음 시간 예고

지난 시간과 오늘, 멀티스레드를 이야기하며 경쟁 상태(race condition)가 두어 번 나왔죠. 여러 스레드가 공유 데이터를 동시에 건드리면 값이 꼬인다는 그 문제요. 은행 잔액을 두 스레드가 동시에 빼는데 한 번만 빠지는 사고, 기억하시죠?

다음 시간(B-4)에는 그 사고를 제대로 막는 법을 배웁니다. 한 번에 하나만 들어가게 줄을 세우는 임계 구역과 상호 배제, 그걸 구현하는 도구인 뮤텍스와 세마포어, 그리고 둘의 차이까지요. 그런데 이 잠금장치를 잘못 얽으면 서로가 서로를 기다리며 영영 멈춰버리는 새로운 사고가 생겨요. 좁은 사거리에서 차들이 서로 막혀 옴짝달싹 못 하는 것 같은 상황 — 데드락(교착 상태)과 그것이 생기는 네 가지 조건, 그리고 유명한 식사하는 철학자 문제를 다음 시간에 만납니다.

과제

[기초] 스택과 힙, 무엇이 어디에 잡히나

연필과 종이만 있으면 됩니다. 아래 의사코드를 보고, 각 변수와 객체가 스택에 잡히는지 힙에 잡히는지 표시해보세요(언어는 여러분이 아는 것 무엇으로 상상해도 됩니다).

   function buildList(n):
       count = n
       items = new List()       // 빈 목록 객체 생성
       total = count + 10
       return items

1. count·total·items·new List()로 만든 목록 객체 — 각각 스택인지 힙인지 적고, 한 줄씩 이유를 쓰세요.
2. 함수 buildList가 끝나는 순간, 위 넷 중 사라지는 것과 남는 것을 구분해보세요. return items가 그 결과에 어떤 영향을 주는지 한 줄로 설명하세요.
3. 스택이 힙보다 빠른 이유와, 그럼에도 힙이 필요한 이유(크기·수명)를 각각 한 줄로 정리해보세요.

[응용] LRU와 FIFO를 손으로 돌려 폴트 수 비교하기

페이지 교체를 직접 시뮬레이션하는 과제입니다. 프레임은 3칸, 페이지 참조 순서는 1 → 2 → 3 → 1 → 4 → 5 → 2 → 1이라고 합시다.

1. FIFO로 한 칸씩 따라가며, 매 참조가 폴트인지 히트인지 적고 총 페이지 폴트 수를 세어보세요. (꽉 찼을 때는 가장 먼저 들어온 페이지를 내보냅니다.)
2. LRU로 같은 순서를 다시 돌려, 총 페이지 폴트 수를 세고 FIFO와 비교해보세요. (꽉 찼을 때는 가장 오래 안 쓴 페이지를 내보냅니다.)
3. 두 결과가 다르다면 왜 다른지, "가장 먼저 들어온"과 "가장 오래 안 쓴"이 어떤 페이지에서 갈렸는지 한 문단으로 설명해보세요.

[심화] "가상 메모리란" 면접 답변과 꼬리 질문 대비하기

조사하고 정리하는 과제입니다.

1. "가상 메모리가 뭔가요?"에 대한 자기만의 답변을, "왜 필요한가(충돌·보호·RAM보다 큰 프로그램) → 어떻게 동작하나(가상/물리 주소·MMU·페이징)" 흐름으로 정리해 적어보세요.
2. 이어질 법한 꼬리 질문 세 개 — "페이징이 외부 단편화를 어떻게 없애나요?", "TLB는 왜 필요한가요?", "페이지 폴트가 왜 비싼가요?" — 에 대한 답을 각각 두세 문장으로 준비해보세요.
3. (선택) "스택과 힙의 주소도 사실 가상 주소"라는 오늘의 이야기를, B-1의 프로세스 메모리 구조와 연결해 한 문단으로 정리해보세요.

생각해볼 주제

1. 가상 메모리는 공짜로 좋기만 할까?

가상 메모리는 프로세스에게 독립 주소공간을 주고, RAM보다 큰 프로그램도 돌리게 해줍니다. 그런데 이 환상은 공짜가 아니에요. 주소를 쓸 때마다 가상에서 물리로 변환하는 비용이 들고, 필요한 페이지가 RAM에 없으면 느린 디스크를 다녀오는 페이지 폴트가 나며, 심하면 스래싱까지 터집니다. 그렇다면 가상 메모리가 주는 이득과 그 대가를 어떻게 저울질해야 할까요? 만약 디스크가 옛날 하드디스크에서 아주 빠른 SSD로 바뀌면 이 저울이 어느 쪽으로 기우는지, 페이지 폴트 비용과 연결해 생각해보세요.

2. 왜 스택은 빠르고 힙은 느릴까?

스택은 단순히 꼭대기를 가리키는 표시 하나를 위아래로 옮기는 것만으로 할당·해제가 끝나고, 함수가 끝나면 알아서 정리됩니다. 반면 힙은 빈 공간을 찾아 떼어주고, 다 쓰면 반납받아 다시 빈 공간으로 관리해야 하죠. 이 구조의 차이가 속도 차이를 만듭니다. 그렇다면 "빠르니까 다 스택에 두면 되지 않나"라는 생각은 어디서 막힐까요? 스택만으로 해결되지 않는 상황(실행 중에 크기가 정해지는 데이터, 함수보다 오래 살아야 하는 객체)을 떠올리며, 속도와 유연함 사이의 트레이드오프를 생각해보세요.

3. 가비지 컬렉션은 축복일까, 짐일까?

C·C++ 같은 언어는 프로그래머가 힙 메모리를 손수 반납하고, 자바·파이썬 같은 언어는 가비지 컬렉터가 자동으로 치웁니다. 자동이면 깜빡하고 메모리를 안 돌려줘서 생기는 누수를 막아주니 편하죠. 그런데 GC는 도는 동안 잠깐 프로그램을 멈출 수 있고, 언제 멈출지 예측하기 어렵습니다. 빠른 응답이 생명인 시스템(게임, 실시간 거래)에서는 이 멈춤이 문제가 되기도 해요. 그렇다면 "메모리를 자동으로 관리해주는 편리함"과 "직접 관리해 예측 가능성을 얻는 통제력" 중 무엇이 더 중요한지, 어떤 상황에서 어느 쪽을 택할지 생각해보세요.