[JUNGLE] TIL_38. CSAPP 9.1 ~ 9.5, RB Tree 삭제 끝!

모깅·2025년 10월 20일

JUNGLE

목록 보기

39/56

가상 메모리 (Virtual Memory, VM)

현대 시스템은 메인 메모리를 더 효율적이고 안전하게 관리하기 위해 가상 메모리(VM)라는 추상화 개념을 제공합니다. 가상 메모리는 하드웨어와 커널 소프트웨어의 상호작용을 통해 각 프로세스에게 크고, 균일하며, 독립적인 전용 주소 공간을 제공하는 메커니즘입니다.

1. 가상 메모리의 필요성

메인 메모리를 여러 프로세스가 직접 공유하면 다음과 같은 문제가 발생합니다.

공간 부족: 너무 많은 프로세스가 메모리를 요구하면 일부 프로세스는 아예 실행조차 할 수 없습니다.
메모리 손상: 한 프로세스가 실수로 다른 프로세스의 메모리 영역에 데이터를 쓰면, 해당 프로세스는 논리와 상관없는 방식으로 오작동하거나 멈출 수 있습니다.

2. 가상 메모리의 3가지 핵심 기능

가상 메모리는 하나의 메커니즘을 통해 다음 세 가지 중요한 기능을 제공합니다.

효율적인 메모리 사용: 메인 메모리를 디스크에 저장된 주소 공간을 위한 캐시(cache)처럼 사용합니다. 활성화된 영역만 메인 메모리에 유지하고, 필요에 따라 디스크와 데이터를 교환합니다.
메모리 관리 단순화: 각 프로세스에게 균일한(uniform) 주소 공간을 제공하여 메모리 관리를 단순화합니다.
메모리 보호: 각 프로세스의 주소 공간을 다른 프로세스로부터 완벽하게 보호하여 메모리 손상을 방지합니다.

3. 프로그래머가 가상 메모리를 이해해야 하는 이유

가상 메모리는 자동으로 동작하지만, 프로그래머가 이를 이해해야 하는 이유는 다음과 같습니다.

가상 메모리는 핵심 개념이다 (Central): 가상 메모리는 하드웨어 예외, 링커, 로더, 프로세스 등 컴퓨터 시스템의 모든 수준에 깊이 관여합니다. 이를 이해하면 시스템 전반의 동작 방식을 더 잘 이해할 수 있습니다.
가상 메모리는 강력하다 (Powerful): 메모리 매핑(memory mapping)과 같은 강력한 기능을 제공합니다. 예를 들어, 명시적인 복사 없이 파일의 내용을 메모리에 올리거나, 메모리 주소를 읽고 쓰는 것만으로 파일 내용을 수정할 수 있습니다.
가상 메모리는 위험하다 (Dangerous): 포인터를 잘못 사용하면 "Segmentation fault"와 같은 오류로 프로그램이 즉시 멈추거나, 오랫동안 조용히 실행되다가 멈추거나, 심지어 틀린 결과를 내고도 정상 종료되는 등 잡기 어려운 버그가 발생할 수 있습니다. 가상 메모리를 이해하면 이러한 메모리 관련 오류를 피하는 데 도움이 됩니다.

9.1 물리 주소와 가상 주소 (Physical and Virtual Addressing)

1. 물리 주소 지정 (Physical Addressing)

컴퓨터의 메인 메모리는 연속된 바이트 크기의 셀 배열로 구성되며, 각 바이트는 고유한 물리 주소(Physical Address, PA)를 가집니다.

동작 방식: CPU는 메모리에 접근할 때 물리 주소를 직접 생성하여 메모리 버스를 통해 메인 메모리에 전달합니다. 메인 메모리는 해당 주소의 데이터를 가져와 CPU에 반환합니다.
사용: 초기 PC나 디지털 신호 처리기(DSP), 임베디드 마이크로컨트롤러 등에서 여전히 사용됩니다.

2. 가상 주소 지정 (Virtual Addressing)

현대 프로세서는 가상 주소 지정 방식을 사용합니다.

동작 방식: CPU는 가상 주소(Virtual Address, VA)를 생성합니다. 이 가상 주소는 메인 메모리로 전송되기 전에, 적절한 물리 주소로 변환(translation)되어야 합니다.
주소 변환 (Address Translation):
- 가상 주소를 물리 주소로 변환하는 작업을 의미합니다.
- 이 작업은 CPU 하드웨어와 운영체제의 긴밀한 협력을 통해 이루어집니다.
- MMU (Memory Management Unit): CPU 칩 내부에 있는 이 전용 하드웨어가 주소 변환을 실시간으로 수행합니다.
- MMU는 메인 메모리에 저장된 조회 테이블(lookup table)을 사용하며, 이 테이블의 내용은 운영체제가 관리합니다.

9.2 주소 공간 (Address Spaces)

주소 공간은 음이 아닌 정수 주소들의 순서 있는 집합 {0, 1, 2, ...} 입니다. 이 정수들이 연속적일 때, 이를 선형 주소 공간(linear address space)이라고 부릅니다.

1. 가상 주소 공간 (Virtual Address Space)

CPU가 생성하는 주소들이 속한 공간으로, 크기는 $N = 2^n$ 입니다.
- {0, 1, 2, ..., N-1}
$N = 2^n$ 개의 주소를 갖는 공간을 n비트 주소 공간이라고 부릅니다. 현대 시스템은 주로 32비트 또는 64비트 가상 주소 공간을 지원합니다.

2. 물리 주소 공간 (Physical Address Space)

시스템에 있는 M바이트의 물리 메모리에 해당하는 주소 공간입니다.
- {0, 1, 2, ..., M-1}
설명의 편의를 위해, M의 크기는 $M = 2^m$ 이라고 가정합니다.

3. 주소 공간의 핵심 개념

주소 공간이라는 개념은 데이터 객체(바이트)와 그 속성(주소)을 명확하게 분리합니다.

이러한 분리를 통해, 각 데이터 객체가 서로 다른 주소 공간에 속한 여러 개의 독립적인 주소를 가질 수 있게 됩니다. 이것이 바로 가상 메모리의 기본 아이디어입니다. 메인 메모리의 각 바이트는 가상 주소 공간에 속한 가상 주소와, 물리 주소 공간에 속한 물리 주소를 모두 가지게 됩니다.

9.3 캐싱 도구로서의 가상 메모리(VM)

개념적으로 가상 메모리는 디스크에 저장된 N개의 연속적인 바이트 배열로 볼 수 있습니다. 디스크에 있는 이 배열의 내용은 메인 메모리에 캐시(cache)됩니다.

1. 페이지: 데이터 전송 단위

메모리 계층의 다른 캐시와 마찬가지로, 하위 계층(디스크)의 데이터는 상위 계층(메인 메모리)으로 전송될 때 블록(block) 단위로 움직입니다.

가상 페이지 (Virtual Pages, VPs)
- 가상 메모리를 고정된 크기로 나눈 블록입니다.
- 크기는 $P = 2^p$ 바이트입니다.
물리 페이지 (Physical Pages, PPs)
- 물리 메모리를 가상 페이지와 동일한 크기로 나눈 블록입니다.
- 페이지 프레임(Page Frames)이라고도 부릅니다.

2. 가상 페이지의 3가지 상태

어떤 시점에서든, 가상 페이지의 집합은 다음 세 가지의 서로 다른 부분 집합으로 나뉩니다.

할당되지 않음 (Unallocated)
- VM 시스템에 의해 아직 생성되지 않은 페이지입니다.
- 이 페이지들은 데이터와 연결되어 있지 않으며, 디스크 공간도 차지하지 않습니다.
캐시됨 (Cached)
- 할당되었고, 현재 물리 메모리에 캐시되어 있는 페이지입니다.
캐시되지 않음 (Uncached)
- 할당은 되었지만, 현재 물리 메모리에 없고 디스크에만 있는 페이지입니다.

↓ 추가 내용

1. 프로그램 실행 전 (Unallocated 상태)

Unallocated는 운영체제(OS)가 해당 프로세스를 위해 아직 어떠한 가상 메모리 관련 자료구조도 만들지 않은 상태를 의미합니다.

이 단계에서는 디스크에 컴파일된 실행 파일(a.out 또는 .exe)만 존재할 뿐입니다.
OS 커널은 이 프로그램을 위한 프로세스 컨텍스트(Process Context)나 페이지 테이블(Page Table)을 메모리에 생성하지 않았습니다.
따라서 가상 주소 공간은 아직 실체 없이 개념적으로만 존재하며, 어떤 가상 페이지도 디스크나 메모리에 물리적인 공간을 할당받지 않은 상태입니다.

2. 프로세스 생성 시 (Allocated & Uncached 상태)

사용자가 ./a.out을 실행하여 프로세스가 생성되는 순간, OS 로더(loader)가 동작하며 가상 메모리 공간을 초기화합니다. 이 과정이 바로 할당(Allocation)입니다.

커널은 프로세스를 위한 페이지 테이블을 생성합니다.
그 후, 실행 파일의 세그먼트 정보를 읽어 페이지 테이블의 각 항목(PTE, Page Table Entry)을 초기화합니다.
- Code(.text), Initialized Data(.data) 세그먼트: 이 세그먼트에 해당하는 가상 페이지들은 스왑(swap) 영역으로 복사되지 않습니다. 대신, 커널은 각 PTE에 "이 가상 페이지의 내용은 디스크에 있는 실행 파일의 몇 번째 오프셋에 있다"라고 매핑 정보만 기록합니다. 이를 메모리 매핑(Memory Mapping)이라고 합니다.
- Uninitialized Data(.bss), 스택(Stack), 힙(Heap) 세그먼트: 이 세그먼트들은 실행 파일에 내용이 없으므로, 커널은 이 가상 페이지들이 스왑 공간을 사용하도록 PTE에 표시합니다. 혹은 당장 필요할 때 0으로 채워진 물리 페이지를 주기로 약속하는 요구-제로 페이지(demand-zero page)로 설정합니다.
이 단계가 끝나면, 프로세스의 가상 주소 공간에 있는 페이지들은 모두 존재하는 것(Allocated)으로 간주됩니다. 하지만 아직 어떤 페이지의 내용도 물리 메모리(RAM)에 올라오지 않았기 때문에, 모든 페이지는 캐시되지 않음(Uncached) 상태입니다.

Q. .text, .data는 스왑 영역으로 복사되지 않고 .bss, stack, heap은 스왑 공간을 사용하도록 PTE에 표시하는 이유가 뭘까?

.bss, 스택, 힙 세그먼트가 스왑 공간을 사용하는 이유는, 이 페이지들이 특정 파일에 기반하지 않는 익명 페이지(Anonymous Pages)이기 때문입니다.

모든 가상 페이지는 물리 메모리(RAM)에서 쫓겨날 경우 돌아갈 수 있는 뒷받침 저장소(Backing Store)가 반드시 필요합니다. 이 저장소의 종류에 따라 페이지는 두 가지로 나뉩니다.

파일 기반 페이지 (File-backed Pages)
- 대상: .text (코드), .data (초기화된 데이터) 세그먼트
- 뒷받침 저장소: 실행 파일 그 자체
- 동작: 이 페이지들이 RAM에서 쫓겨나더라도, 원본 데이터가 실행 파일에 그대로 있기 때문에 필요하면 거기서 다시 읽어오면 됩니다. 만약 페이지 내용이 변경되었다면(거의 없음) 그때는 스왑 공간에 저장합니다.
익명 페이지 (Anonymous Pages)
- 대상: .bss, 스택, 힙 세그먼트
- 뒷받침 저장소: 스왑 공간 (Swap Space)
- 동작: 이 페이지들은 처음부터 특정 파일과 연결된 적이 없습니다. 프로그램이 실행되면서 동적으로 생성되고 데이터가 쓰이는 공간입니다. 따라서 RAM에서 쫓겨날 때, 그 내용을 임시로 저장해 둘 장소가 필요한데, 그 장소가 바로 스왑 공간입니다.

간단히 말해, .text 페이지는 RAM에서 쫓겨나도 돌아갈 "본가"(실행 파일)가 있지만, .bss, 스택, 힙 페이지는 그런 "본가"가 없기 때문에 임시 거처인 "스왑 공간"을 뒷받침 저장소로 지정하는 것입니다.

Q. 요구-제로 페이지(demand-zero page)란?

핵심 아이디어는 "프로세스가 실제로 해당 메모리에 쓰기 전까지는, 물리 메모리(RAM)는 물론 디스크(스왑)에도 아무런 공간을 할당하지 않고 약속만 해두는 것"입니다.

동작 과정

프로세스 생성 시 (약속 단계)
- 프로세스가 시작되고 .bss나 스택을 위한 가상 메모리 공간이 예약됩니다.
- 이때 커널은 스왑 공간에 0으로 채워진 페이지를 미리 만들어두지 않습니다.
- 대신, 해당 가상 페이지들에 대한 PTE(페이지 테이블 항목)에 "이 페이지는 요구-제로 페이지다"라고 특별한 표시만 해둡니다. 이 PTE의 유효 비트(valid bit)는 0입니다. → 요구-제로 페이지 표시 : valid bit = 0 + 특별한 패턴 (Linux의 경우, 보통 모든 비트가 0)
첫 쓰기 접근 시 (페이지 폴트 발생)
- 프로세스가 이 영역의 특정 주소에 처음으로 쓰기(write)를 시도합니다.
- MMU는 PTE의 유효 비트가 0인 것을 보고 페이지 폴트를 발생시켜 커널을 호출합니다.
커널의 처리 (실제 할당)
- 페이지 폴트 핸들러(커널)는 PTE의 특별 표시를 보고 이것이 요구-제로 페이지에 대한 폴트임을 인지합니다.
- 커널은 "제로 페이지(zero page)"라고 불리는, 모든 내용이 0으로 채워진 깨끗한 물리 페이지 프레임을 하나 가져옵니다.
- 이 제로 페이지를 해당 가상 주소에 매핑하고, PTE를 새로운 물리 페이지 번호로 업데이트한 뒤 유효 비트를 1로 설정합니다.
- 이제 프로세스는 물리 메모리에 정상적으로 쓰기 작업을 완료할 수 있습니다.

요구-제로 페이지의 장점

빠른 프로세스 생성: 프로세스를 시작할 때 스왑 공간에 수많은 0을 쓰는 디스크 I/O 작업이 전혀 필요 없으므로 프로세스 로딩이 매우 빨라집니다.
효율적인 자원 사용: 프로그램이 할당만 받아놓고 실제로 사용하지 않는 메모리(예: 거대한 .bss 배열)에 대해서는 물리 메모리나 디스크 공간을 전혀 낭비하지 않습니다. "요구(Demand)"가 있을 때만 자원을 할당하므로 매우 효율적입니다.

Q. 가상 메모리 공간이 예약된다는 말은 어떤 의미일까?

"가상 메모리 공간이 예약된다"는 말은, 실제 물리 메모리(RAM)나 디스크를 사용하는 것이 아니라, 커널이 관리 장부에 "이 주소 범위는 앞으로 이런 용도로 사용할 것이다"라고 논리적으로 기록만 해두는 것을 의미합니다.

이는 실제 공간을 할당하는 행위가 아니라, 주소 범위를 특정 목적(예: 스택, 힙)으로 선점해두는 개념적인 약속입니다.

커널의 실제 동작

프로세스가 시작될 때, 커널은 해당 프로세스를 관리하기 위한 자료구조를 자신의 메모리 공간에 만듭니다. 리눅스의 경우, VMA(vm_area_struct)라는 구조체를 사용합니다.

"스택을 위한 가상 메모리 공간이 예약된다"는 것은 커널이 다음과 같은 내용을 담은 VMA를 생성한다는 의미입니다.

스택 VMA:

주소 범위: 0x7ffffffde000 부터 0x7ffffffff000 까지

접근 권한: 읽기/쓰기 가능

특징: 아래 방향으로 자라나는(grows down) 영역

이 VMA가 생성되는 순간이 바로 "예약"이 완료된 시점입니다. 이 단계에서는:

이 주소 범위를 위한 페이지 테이블 항목(PTE)은 아직 생성되지 않았습니다.
물리 메모리(RAM)는 당연히 할당되지 않았습니다.
디스크의 스왑 공간도 전혀 사용되지 않았습니다.

이것은 커널이 프로세스에게 "네가 이 주소 범위를 사용하면, 내가 알아서 처리해 줄게"라고 약속하는 것과 같습니다. 실제로 프로세스가 이 주소 범위 내의 특정 주소에 처음 접근하여 페이지 폴트를 일으키기 전까지는 어떠한 물리적 자원도 소모되지 않습니다.

Q. 요구 제로 페이지를 달라고 하는 시점은 전역변수를 접근했을 때일까?

네, 정확히 그 시점이 맞습니다. 하지만 조금 더 포괄적으로 말하면, .bss 세그먼트에 속한 전역/정적 변수나, 힙(heap), 스택(stack) 영역에 있는 특정 가상 주소에 처음으로 접근(read 또는 write)하는 바로 그 순간에 요구-제로 페이지를 달라고 요청하게 됩니다.

"요청"의 진짜 의미: 페이지 폴트

요구-제로 페이지를 "요청"하는 행위는 프로그램이 getPage() 같은 함수를 호출하는 것이 아닙니다. 이 요청은 하드웨어 수준에서 발생하는 페이지 폴트(Page Fault)를 통해 이루어집니다.

단계별 동작 과정

프로그램 시작 (약속만 있는 상태)
- 프로그램이 시작되면, .bss에 있는 int global_var;는 가상 주소 공간에 논리적으로만 존재합니다.
- 이 변수가 속한 가상 페이지에 대한 PTE(페이지 테이블 항목)는 "유효하지 않음(valid bit = 0)"으로 설정되어 있으며, "이것은 요구-제로 페이지다"라는 특별 표시가 되어 있습니다.
- 이 시점에는 RAM이든 디스크든, global_var를 위한 어떤 물리적 공간도 존재하지 않습니다.
첫 접근 (페이지 폴트 발생)
- 이제 CPU가 global_var를 처음으로 읽거나 쓰려는 명령(mov global_var, %eax 등)을 실행합니다.
- MMU(메모리 관리 장치)는 global_var의 가상 주소를 물리 주소로 변환하려고 PTE를 확인합니다.
- PTE의 유효 비트가 0이므로, MMU는 주소 변환에 실패하고 페이지 폴트라는 하드웨어 예외를 발생시켜 커널을 호출합니다.
커널의 응답 (요구-제로 페이지 제공)
- 페이지 폴트 핸들러(커널)는 이 폴트가 "요구-제로 페이지"에 대한 요청임을 확인합니다.
- 커널은 비어있는 물리 페이지(RAM)를 하나 할당하고, 그 내용을 전부 0으로 채웁니다.
- 커널은 PTE를 이 새로운 물리 페이지의 주소로 업데이트하고, 유효 비트를 1로 설정합니다.
- 이제 global_var는 실제 물리 메모리에 자신의 공간을 갖게 됩니다.
명령어 재실행
- 커널은 원래 실패했던 메모리 접근 명령어를 다시 실행시킵니다.
- 이번에는 PTE가 유효하므로, MMU는 주소 변환에 성공하고 프로그램은 아무 일도 없었다는 듯이 실행을 계속합니다.

.bss 뿐만 아니라 스택과 힙도 마찬가지

이 "필요할 때만 할당하는" 원리는 .bss뿐만 아니라 다른 메모리 영역에도 동일하게 적용됩니다.

스택 (Stack): 함수가 깊게 호출되어 기존에 할당된 스택 페이지를 넘어서는 새로운 주소에 접근할 때, 페이지 폴트가 발생하고 새로운 "0으로 채워진" 스택 페이지가 할당됩니다.
힙 (Heap): malloc을 호출하여 새로운 메모리를 요청했을 때, 커널은 VMA를 통해 가상 주소 공간만 예약해주고, 프로그램이 그 영역에 처음 접근할 때 페이지 폴트를 통해 실제 물리 페이지를 할당해 줍니다.

Q. 요구 페이지라면 특정 페이지를 요청 했는데 물리 메모리에 없다면 스왑영역에 있는 페이지를 메모리로 올리는건가?

페이지를 항상 스왑 영역에서 가져오는 것은 아닙니다. 페이지의 종류에 따라 가져오는 위치, 즉 뒷받침 저장소(Backing Store)가 다릅니다.

페이지 폴트가 발생했을 때, 커널은 해당 페이지가 어떤 종류인지에 따라 다음 세 가지 중 하나의 동작을 수행합니다.

1. 스왑 영역에서 가져오는 경우

대상: 힙(Heap), 스택(Stack), 수정된 데이터 페이지 등 특정 파일과 연결되지 않은 익명 페이지(Anonymous Pages)
설명: 이 페이지들은 프로그램이 실행되면서 동적으로 생성되거나 내용이 바뀐 데이터들입니다. RAM 공간이 부족해서 이 페이지들을 잠시 쫓아낼 때, 그 내용을 임시로 저장해두는 장소가 바로 스왑 영역입니다. 따라서 다시 필요해지면 당연히 스왑 영역에서 해당 내용을 읽어와 물리 메모리로 올립니다. 사용자님이 질문하신 경우가 바로 이것입니다.

2. 실행 파일에서 가져오는 경우

대상: 코드(.text)나 초기화된 전역 변수(.data)처럼, 원본 내용이 실행 파일에 그대로 있는 페이지.
설명: 이 페이지들은 내용이 바뀌지 않는(read-only) 경우가 대부분입니다. 따라서 RAM에서 쫓겨나더라도 그 내용을 굳이 스왑 영역에 복사해 둘 필요가 없습니다. 그냥 RAM에서 지워버리고, 나중에 다시 필요해지면 원본 실행 파일의 해당 위치에서 직접 다시 읽어오는 것이 훨씬 효율적입니다.

3. 새로 만드는 경우 (요구-제로 페이지)

대상: 초기화되지 않은 전역 변수(.bss)나, 이제 막 할당된 힙/스택 공간.
설명: 이 페이지들은 아직 아무 데이터도 쓰인 적이 없는 "빈 페이지"입니다. 따라서 디스크에서 어떤 내용을 읽어올 필요가 전혀 없습니다. 대신, 커널은 그냥 비어있는 물리 페이지를 하나 가져와 모든 내용을 0으로 깨끗하게 채운 뒤, 프로세스에게 할당해 줍니다.

페이지 폴트 처리 과정 요약

CPU가 특정 가상 주소를 요청합니다.
MMU가 페이지 테이블을 확인했으나, 해당 페이지가 물리 메모리에 없음을 확인합니다 (유효 비트 = 0).
MMU가 페이지 폴트 예외를 발생시켜 커널을 호출합니다.
커널의 페이지 폴트 핸들러가 실행됩니다.
핸들러는 PTE의 내용을 분석하여 이 페이지의 뒷받침 저장소가 어디인지 판단합니다.
- "이 페이지는 스왑 영역에 있는가?"
- "이 페이지는 실행 파일에 매핑되어 있는가?"
- "이 페이지는 새로 만들어야 하는 요구-제로 페이지인가?"
판단에 따라, 커널은 해당 뒷받침 저장소에서 물리 메모리의 빈 프레임으로 데이터를 가져오거나(I/O), 0으로 채운 새 페이지를 만듭니다.
커널은 PTE를 새로운 물리 주소로 업데이트하고 유효 비트를 1로 설정합니다.
원래 실패했던 명령어를 다시 실행하면, 이번에는 주소 변환에 성공합니다.

3. CPU의 첫 메모리 접근 시 (Allocated & Cached 상태)

프로세스가 실제로 명령어를 실행하며 특정 가상 주소에 접근하는 순간, 다음과 같은 과정이 발생합니다.

CPU가 특정 가상 주소를 MMU(Memory Management Unit)에 전달하여 물리 주소로 변환을 요청합니다.
MMU는 해당 가상 주소에 대한 PTE를 페이지 테이블에서 확인합니다. PTE에는 해당 페이지가 물리 메모리에 없다고 표시되어 있습니다(valid bit = 0).
MMU는 페이지 폴트(Page Fault)라는 하드웨어 예외를 발생시켜 CPU를 멈추고 커널을 호출합니다.
커널의 페이지 폴트 핸들러가 실행됩니다. 핸들러는 PTE를 다시 확인하여 이 페이지의 내용이 디스크의 어디에(실행 파일 또는 스왑 공간) 저장되어 있는지 파악합니다.
커널은 물리 메모리에서 비어있는 물리 페이지 프레임(Physical Page Frame)을 찾습니다.
커널은 디스크 I/O를 통해 디스크에 있던 페이지 내용을 해당 물리 페이지 프레임으로 복사합니다.
커널은 PTE를 업데이트하여 이제 해당 가상 페이지가 어떤 물리 주소에 매핑되었는지 기록하고, 유효 비트(valid bit)를 1로 설정합니다.
이제 페이지의 상태는 캐시됨(Cached)이 됩니다.
페이지 폴트를 유발했던 원래 명령어가 다시 실행되고, 이번에는 MMU가 주소 변환에 성공하여 물리 메모리에 정상적으로 접근합니다. 이 과정을 요구 페이징(Demand Paging)이라고 합니다.

9.3.1 DRAM 캐시의 구성

1. SRAM 캐시 vs. DRAM 캐시

메모리 계층의 여러 캐시를 명확히 구분하기 위해 다음과 같이 용어를 정의합니다.

SRAM 캐시: CPU와 메인 메모리 사이에 있는 L1, L2, L3 캐시를 의미합니다.
DRAM 캐시: 가상 페이지를 메인 메모리에 캐시하는 가상 메모리(VM) 시스템의 캐시를 의미합니다.

2. 미스 비용(Miss Cost)의 막대한 영향

DRAM 캐시의 구성 방식은 전적으로 막대한 미스 비용(enormous cost of misses)에 의해 결정됩니다.

DRAM은 SRAM보다 최소 10배 느립니다.
디스크는 DRAM보다 약 100,000배 느립니다.

이러한 성능 차이 때문에, SRAM 캐시 미스는 DRAM에서 데이터를 가져오지만, DRAM 캐시 미스는 디스크에서 데이터를 가져와야 하므로 비교할 수 없을 정도로 큰 성능 저하를 유발합니다.

3. DRAM 캐시 구성의 특징

이러한 막대한 미스 비용 때문에 DRAM 캐시는 다음과 같은 특징을 갖도록 설계되었습니다.

큰 페이지 크기 (Large Page Size)
- 디스크 접근은 첫 바이트를 읽는 비용이 매우 크기 때문에, 한 번 접근할 때 많은 양의 데이터를 가져오는 것이 효율적입니다.
- 따라서 가상 페이지의 크기는 일반적으로 4KB에서 2MB로 매우 큽니다.
완전 연관 캐시 (Fully Associative)
- 미스 패널티가 매우 크기 때문에, 캐시의 유연성을 극대화해야 합니다.
- 따라서 어떤 가상 페이지든 어떤 물리 페이지에도 저장될 수 있는 완전 연관 방식으로 구성됩니다.
정교한 교체 정책 (Sophisticated Replacement Policy)
- 잘못된 페이지를 교체했을 때의 비용이 매우 높으므로, 운영체제는 하드웨어가 SRAM 캐시에 사용하는 단순한 정책보다 훨씬 정교한 교체 알고리즘을 사용합니다.
쓰기-후기 정책 (Write-Back)
- 디스크 접근 시간이 매우 길기 때문에, DRAM 캐시는 항상 쓰기-후기(Write-Back) 방식을 사용합니다.
- 쓰기-관통(Write-Through) 방식처럼 매번 디스크에 기록하는 것은 시스템 성능을 심각하게 저하시키기 때문입니다.

페이지 테이블

VM 시스템은 페이지 테이블을 사용하여 가상 페이지(VP)가 DRAM에 캐시되었는지, 만약 그렇다면 어느 물리 페이지(PP)에 있는지 판단합니다. 페이지 폴트가 발생하면, 페이지 테이블을 참조하여 디스크 상의 페이지 위치를 찾아 물리 메모리로 가져옵니다.

이 과정은 운영체제(OS), MMU(메모리 관리 장치), 그리고 물리 메모리에 저장된 페이지 테이블의 협력으로 이루어집니다.

MMU (하드웨어): 가상 주소를 물리 주소로 변환할 때마다 페이지 테이블을 읽습니다.
운영체제 (소프트웨어): 페이지 테이블의 내용을 유지하고, 디스크와 DRAM 간의 페이지 전송을 담당합니다.

페이지 테이블 항목 (PTE)

페이지 테이블은 페이지 테이블 항목(PTE, Page Table Entry)들의 배열입니다. 각 가상 페이지는 페이지 테이블의 고정된 위치에 자신만의 PTE를 가집니다.

각 PTE는 최소한 두 가지 정보를 포함합니다.

유효 비트 (Valid bit): 해당 가상 페이지가 현재 DRAM에 캐시되어 있는지 여부를 나타냅니다.
주소 필드 (Address field):
- 유효 비트가 1일 때: 가상 페이지가 캐시된 물리 페이지의 시작 주소(PPN)를 가리킵니다.
- 유효 비트가 0일 때:
  - 주소가 NULL이면, 해당 가상 페이지는 아직 할당되지 않았음(Unallocated)을 의미합니다.
  - 주소가 NULL이 아니면, 디스크에 있는 가상 페이지의 시작 주소를 가리킵니다.

제공된 텍스트의 예시(Figure 9.4)는 8개의 가상 페이지와 4개의 물리 페이지가 있는 시스템을 보여줍니다. DRAM 캐시는 완전 연관 방식이므로, 어떤 물리 페이지든 어떤 가상 페이지든 담을 수 있습니다.

9.3.3 페이지 히트 (Page Hit)

CPU가 요청한 가상 주소의 페이지가 이미 DRAM에 캐시되어 있는 경우를 페이지 히트라고 합니다.

주소 변환 하드웨어(MMU)는 가상 주소를 인덱스로 사용하여 PTE(페이지 테이블 항목)를 읽습니다.
PTE의 유효 비트(valid bit)가 1인 것을 확인합니다. 이는 해당 페이지가 DRAM에 캐시되어 있음을 의미합니다.
MMU는 PTE에 저장된 물리 페이지 주소(PPN)를 사용하여 최종 물리 주소를 생성하고, 이 주소로 메인 메모리에 접근하여 데이터를 가져옵니다.

9.3.4 페이지 폴트 (Page Fault)

가상 메모리에서 DRAM 캐시 미스가 발생한 경우를 페이지 폴트라고 합니다.

발생: CPU가 DRAM에 캐시되지 않은 가상 페이지(예: VP 3)에 접근합니다.
감지: MMU가 PTE 3을 읽고, 유효 비트가 0인 것을 확인합니다. MMU는 주소 변환을 중단하고 페이지 폴트 예외를 발생시켜 커널을 호출합니다.
핸들러 실행: 커널의 페이지 폴트 핸들러가 실행됩니다.
희생 페이지 선택: 핸들러는 물리 메모리에서 쫓아낼 희생 페이지(victim page)를 선택합니다. (예: PP 3에 있는 VP 4)
희생 페이지 스왑 아웃: 만약 희생 페이지(VP 4)의 내용이 변경되었다면(dirty), 커널은 이를 디스크에 다시 기록합니다(write-back).
PTE 업데이트 (희생 페이지): 커널은 희생 페이지(VP 4)의 PTE를 수정하여, 더 이상 DRAM에 캐시되어 있지 않음(유효 비트=0)을 표시합니다.
필요한 페이지 스왑 인: 커널은 원래 필요했던 페이지(VP 3)를 디스크에서 물리 메모리(PP 3)로 복사합니다.
PTE 업데이트 (새로운 페이지): 커널은 VP 3의 PTE를 업데이트하여 새로운 물리 페이지 위치를 기록하고, 유효 비트를 1로 설정합니다.
복귀 및 재시작: 핸들러는 원래 실패했던 명령어로 복귀하여 해당 명령어를 재시작합니다. 이제 필요한 페이지가 메모리에 있으므로, 주소 변환은 페이지 히트로 정상 처리됩니다.

주요 용어 정리

가상 메모리 시스템은 SRAM 캐시와 용어가 약간 다릅니다.

페이지 (Pages): 가상 메모리에서의 블록(block)을 의미합니다.
스와핑/페이징 (Swapping/Paging): 디스크와 메모리 간에 페이지를 전송하는 행위를 의미합니다.
- 스왑 인 (Swap in) / 페이지 인 (Paged in): 디스크에서 DRAM으로 페이지를 가져오는 것.
- 스왑 아웃 (Swap out) / 페이지 아웃 (Paged out): DRAM에서 디스크로 페이지를 내보내는 것.
요구 페이징 (Demand Paging): 미스가 발생했을 때, 하나의 페이지로 스와핑되어 들어오는 마지막 순간까지 기다리는 전략. 현대 시스템은 모두 요구 페이징 방식 사용.

9.3.5 페이지 할당 (Allocating Pages)

malloc 호출과 같이 새로운 가상 메모리 페이지가 필요할 때, 운영체제는 다음과 같이 페이지를 할당합니다.

디스크 공간 확보: 디스크(스왑 공간)에 새로운 페이지를 위한 공간을 만듭니다.
PTE 업데이트: 해당 가상 페이지(예: VP 5)의 PTE(페이지 테이블 항목)를 수정하여, 방금 디스크에 생성된 페이지를 가리키도록 설정합니다.

이때 할당된 페이지는 아직 물리 메모리에 없으므로, "캐시되지 않음(Uncached)" 상태로 시작합니다.

9.3.6 지역성 다시 보기 (Locality to the Rescue Again)

가상 메모리는 막대한 미스 비용 때문에 매우 비효율적일 것이라는 첫인상을 주기 쉽습니다. 하지만 실제로는 지역성(locality) 원리 덕분에 매우 잘 동작합니다.

워킹셋 (Working Set)
- 프로그램은 전체 실행 시간 동안 물리 메모리보다 더 많은 페이지를 참조할 수 있지만, 어떤 특정 시점에는 워킹셋(working set) 또는 상주 집합(resident set)이라고 불리는 소수의 활성 페이지 집합에만 집중적으로 접근하는 경향이 있습니다.
지역성의 효과
- 초기에 이 워킹셋이 메모리로 로드(page-in)되고 나면, 그 이후의 대부분 접근은 페이지 히트가 되어 추가적인 디스크 트래픽 없이 빠르게 처리됩니다.
쓰레싱 (Thrashing)
- 프로그램의 시간적 지역성이 좋지 않아 워킹셋의 크기가 실제 물리 메모리의 크기를 초과하면, 쓰레싱이라는 최악의 상황이 발생할 수 있습니다.
- 쓰레싱이란, 페이지들이 지속적으로 메모리와 디스크 사이에서 교체(swap-in, swap-out)되면서, 실제 작업은 거의 하지 못하고 페이징에만 모든 시간을 소모하는 현상을 말합니다.
- 만약 프로그램의 성능이 급격히 저하된다면, 현명한 프로그래머는 쓰레싱이 발생하고 있는지 의심해 봐야 합니다.

9.4 메모리 관리 도구로서의 VM

가상 메모리(VM)는 단순히 DRAM을 디스크의 캐시로 사용하는 것을 넘어, 메모리 관리를 대폭 단순화하고 메모리를 보호하는 강력한 도구입니다.

이 기능의 핵심은 운영체제가 각 프로세스마다 별도의 페이지 테이블(page table)을 제공한다는 점입니다. 결과적으로, 모든 프로세스는 자신만의 독립적인 가상 주소 공간(virtual address space)을 갖게 됩니다. 이를 통해 링킹, 로딩, 공유, 메모리 할당이 매우 단순해집니다.

1. 링킹 단순화 (Simplifying Linking)

독립적인 주소 공간 덕분에, 모든 프로세스는 코드와 데이터가 실제 물리 메모리 어디에 위치하는지와 상관없이 동일하고 표준적인 메모리 레이아웃을 사용할 수 있습니다.

예시: 64비트 Linux 시스템에서 모든 프로세스의 코드 세그먼트는 가상 주소 0x400000에서 시작하고, 스택은 최상위 주소에서 아래로 자랍니다.
장점: 링커는 물리 메모리 상의 최종 위치를 전혀 고려할 필요 없이, 이 표준 가상 주소에 기반하여 실행 파일을 만들 수 있습니다. 이로 인해 링커의 설계와 구현이 매우 단순해집니다.

2. 로딩 단순화 (Simplifying Loading)

가상 메모리는 실행 파일을 메모리로 가져오는 로딩 과정을 매우 효율적으로 만듭니다.

동작 방식: Linux 로더는 프로그램을 실행할 때, 디스크에 있는 코드와 데이터를 메모리로 미리 복사하지 않습니다. 대신, 해당 영역을 위한 가상 페이지만 할당하고, 이 페이지들에 대한 페이지 테이블 항목(PTE)이 디스크의 실행 파일을 가리키도록 설정합니다. (이때 유효 비트는 0입니다.)
장점: 실제 데이터는 CPU가 해당 페이지에 처음 접근할 때 페이지 폴트를 통해 필요할 때만(on demand) 메모리로 올라옵니다. 이를 요구 페이징(Demand Paging)이라고 하며, 프로그램 시작 속도를 매우 빠르게 만듭니다. 이 개념을 일반화한 것이 메모리 매핑(Memory Mapping)입니다.

독립적인 주소 공간은 프로세스 간 코드 및 데이터 공유를 위한 일관된 메커니즘을 제공합니다.

예시: C 표준 라이브러리(printf 등)나 커널 코드는 모든 프로세스가 공통으로 사용합니다. 각 프로세스마다 이 코드를 메모리에 따로 올리는 대신, 운영체제는 여러 프로세스의 서로 다른 가상 페이지들이 동일한 물리 페이지를 가리키도록 매핑합니다.
장점: 단 하나의 코드 복사본만 물리 메모리에 올려두고 모든 프로세스가 공유하므로, 메모리를 매우 효율적으로 사용할 수 있습니다.

4. 메모리 할당 단순화 (Simplifying Memory Allocation)

가상 메모리는 프로그램이 malloc을 호출하여 추가 메모리를 요청할 때 할당 과정을 단순화합니다.

문제점: 가상 메모리가 없다면, malloc(16MB) 요청을 처리하기 위해 16MB 크기의 연속된 빈 물리 메모리 공간을 찾아야 합니다. 메모리 단편화(fragmentation) 때문에 이는 매우 어렵습니다.
VM의 해결책: 운영체제는 16MB 크기의 연속된 가상 페이지를 할당합니다. 그리고 이 연속된 가상 페이지들을 물리 메모리 여기저기 흩어져 있는(scattered) 물리 페이지들에 매핑합니다.
장점: 프로그램은 연속적인 메모리 공간을 얻은 것처럼 동작하지만, 운영체제는 물리 메모리를 조각난 상태 그대로 효율적으로 사용할 수 있습니다.

Q. malloc의 동작 방식

1단계: 논리적 할당 (가상 주소 공간 예약)

프로그램이 malloc(16MB)를 호출하면, C 라이브러리는 커널에게 더 많은 힙 공간을 요청합니다 (sbrk 또는 mmap 시스템 콜 사용).

이때 커널이 하는 일은 다음과 같습니다.

연속된 가상 주소 공간 예약: 커널은 해당 프로세스의 가상 주소 공간에서 16MB 크기의 연속된 빈 주소 범위를 찾습니다.
VMA 생성: 이 주소 범위를 관리하기 위한 VMA(vm_area_struct)를 생성하여 "이 영역은 힙을 위한 공간이다"라고 논리적으로 기록합니다.
물리 자원 미사용: 이 단계에서는 어떤 물리 메모리(RAM)나 디스크 스왑 공간도 실제로 할당되지 않습니다. 단지 주소만 예약된 상태입니다.

이것이 바로 "16MB 크기의 연속된 가상 페이지를 할당한다"는 설명의 의미입니다.

2단계: 물리적 할당 (첫 접근 시 페이지 폴트)

이제 프로그램이 malloc으로 받은 16MB 공간 내의 특정 주소에 처음으로 접근하려고 시도합니다.

페이지 폴트 발생: 해당 가상 주소에 대한 PTE(페이지 테이블 항목)는 아직 어떤 물리 페이지와도 매핑되지 않았으므로(유효 비트=0), 페이지 폴트가 발생합니다.
요구-제로 페이지 제공: 커널은 이 폴트가 요구-제로 페이지에 대한 요청임을 인지하고, 비어있는 물리 페이지(RAM)를 하나 할당하여 0으로 채운 뒤, 요청된 가상 페이지에 매핑합니다.
"뒷받침 저장소"로서의 디스크: 이 단계에서 커널은 PTE를 업데이트하며, 새로 할당된 이 페이지의 뒷받침 저장소(backing store)가 디스크의 스왑 공간임을 표시합니다. 나중에 RAM이 부족해져 이 페이지를 쫓아내야 할 때, 그 내용을 저장할 장소로 스왑 공간을 지정하는 것입니다.

이것이 바로 "malloc할 때 디스크(스왑 공간)에 공간을 만들어 놓는다"는 설명의 진짜 의미입니다. 정확히는, "만든다"기보다는 "필요할 때 저장할 장소로 지정한다"는 것이 더 정확한 표현입니다.

정리: 두 설명의 관계

두 설명을 malloc(16MB)의 전체 과정에 맞춰 정리하면 다음과 같습니다.

연속된 가상 공간 확보: 커널은 먼저 16MB 크기의 연속된 가상 주소 공간을 예약(VMA 생성)합니다. (→ VM의 해결책)
물리 공간은 흩어져서 할당: 프로그램이 이 16MB 공간을 실제로 사용하기 시작하면, 페이지 폴트가 발생할 때마다 커널은 RAM 여기저기에 흩어져 있는 빈 물리 페이지를 하나씩 찾아서 할당해 줍니다. (→ VM의 장점)
디스크는 보험: 이렇게 할당된 각 물리 페이지는, 나중에 RAM에서 쫓겨날 때를 대비하여 디스크의 스왑 공간을 자신의 뒷받침 저장소로 지정받습니다. (→ malloc과 디스크의 관계)

결론적으로, malloc은 가상적으로는 연속적인 공간을 얻지만, 물리적으로는 흩어져 있는 RAM 페이지를 할당받으며, 이 페이지들은 디스크의 스왑 공간을 보험으로 가지고 있는 것입니다.

Q. 가상 주소의 연속된 공간을 어떻게 찾을까?

널은 malloc 요청에 대한 연속된 빈 가상 주소 공간을 찾기 위해, 전체 주소 공간을 처음부터 끝까지 스캔하는 비효율적인 방식을 사용하지 않습니다. 대신, 이미 할당된 메모리 영역(VMA)들만 효율적으로 관리하는 자료구조를 사용하여 빈 공간을 매우 빠르게 찾아냅니다.

1. "단순 스캔" 방식의 문제점

만약 커널이 for 루프처럼 주소를 하나씩 스캔한다면, 다음과 같은 문제가 발생합니다.

엄청난 시간 소모: 64비트 주소 공간( $2^{64}$ )은 거의 무한대에 가까울 정도로 크기 때문에, 선형 탐색은 사실상 불가능합니다.
비효율적인 관리: 가상 주소 공간의 대부분은 텅 비어있습니다. 이 텅 빈 공간을 일일이 확인하는 것은 엄청난 낭비입니다.

2. 실제 방식: VMA 리스트/트리

커널은 "어디가 비어있는가?"를 찾는 대신, "어디가 사용 중인가?"를 기록하고 그 사이의 빈틈(gap)을 찾아냅니다.

VMA(vm_area_struct): 커널은 각 프로세스의 메모리 영역(코드, 데이터, 힙, 스택, 공유 라이브러리 등)을 VMA라는 구조체로 관리합니다. 각 VMA는 시작 주소, 끝 주소, 권한 등의 정보를 담고 있습니다.
자료구조: 커널은 이 VMA들을 시작 주소 순으로 정렬된 연결 리스트(Linked List)나, 더 효율적인 레드-블랙 트리(Red-Black Tree) 같은 균형 잡힌 이진 탐색 트리로 유지합니다.
빈 공간을 찾는 과정은 다음과 같습니다.
1. 프로세스가 malloc 등으로 메모리를 요청합니다.
2. 커널은 VMA 리스트(또는 트리)를 순회하며 이미 할당된 VMA들 사이의 간격을 확인합니다.
3. "VMA 1의 끝 주소"와 "VMA 2의 시작 주소" 사이의 공간이 요청한 크기보다 큰지 계산합니다.
4. 충분한 크기의 첫 번째 빈 공간을 찾으면, 그 위치에 새로운 VMA를 생성하여 할당하고 탐색을 마칩니다.

9.5 메모리 보호 도구로서의 VM

현대 운영체제는 가상 메모리(VM) 메커니즘을 확장하여 메모리 시스템에 대한 접근을 정교하게 제어하고 보호합니다.

1. 메모리 보호의 필요성

운영체제는 다음과 같은 상황을 막아야 합니다.

사용자 프로세스가 자신의 읽기 전용(read-only) 코드 영역을 수정하는 행위.
사용자 프로세스가 커널의 코드나 자료구조를 읽거나 수정하는 행위.
사용자 프로세스가 다른 프로세스의 사적인 메모리를 읽거나 쓰는 행위.
명시적인 허가 없이 공유된 가상 페이지를 수정하는 행위.

2. PTE를 이용한 접근 제어

각 프로세스에 독립적인 가상 주소 공간을 제공하는 것만으로도 프로세스 간의 메모리 분리가 어느 정도 이루어집니다. 하지만 가상 메모리는 페이지 테이블 항목(PTE)에 접근 권한 비트(permission bits)를 추가함으로써 훨씬 더 세밀한 접근 제어를 제공합니다.

MMU(주소 변환 하드웨어)는 모든 메모리 접근 시마다 PTE를 읽기 때문에, 이 권한 비트를 확인하는 것은 자연스럽고 효율적입니다.

SUP (Supervisor) 비트: 페이지에 접근하기 위해 커널 모드여야 하는지를 나타냅니다.
- 커널 모드에서는 모든 페이지에 접근할 수 있습니다.
- 사용자 모드에서는 SUP 비트가 0인 페이지만 접근할 수 있습니다.
READ 비트: 페이지에 대한 읽기 권한을 제어합니다.
WRITE 비트: 페이지에 대한 쓰기 권한을 제어합니다.

3. 권한 위반 시 동작

만약 어떤 명령어가 PTE에 설정된 권한을 위반하면, 다음과 같은 과정이 발생합니다.

CPU는 일반 보호 폴트(general protection fault)라는 예외를 발생시킵니다.
제어권이 커널의 예외 핸들러로 넘어갑니다.
커널은 위반한 프로세스에게 SIGSEGV 시그널을 보냅니다.
Linux 쉘은 이 예외를 일반적으로 "세그멘테이션 폴트(Segmentation fault)"라고 보고하고, 프로세스는 종료됩니다.

RB Tree 삭제

int rbtree_erase(rbtree *t, node_t *p) {
    if (t == NULL || p == NULL || t->root == NULL) {
        return 0;
    }

    node_t *find_node = rbtree_find(t, p->key);
    if (find_node == NULL) {
        return 0;
    }

    node_t *removed_node = NULL;
    node_t *replacement_node = NULL;
    node_t *parent_of_replacement = NULL;
    color_t removed_color;

    int is_root_deleted = find_node == t->root;

    // Case 1: 자녀가 하나 혹은 없을 경우
    if (find_node->left == NULL || find_node->right == NULL) {
        removed_color = find_node->color;
        parent_of_replacement = find_node->parent;
        replacement_node = (find_node->left != NULL) ? find_node->left : find_node->right;

        removed_node = remove_node_with_one_or_zero(&find_node);

        if (is_root_deleted) {
            t->root = find_node;
        }
    }
    // Case 2: 자녀가 두 개일 경우
    else {
        node_t *successor = find_successor(find_node);

        removed_color = successor->color;

        replacement_node = successor->right;
        parent_of_replacement = successor->parent;

        if (parent_of_replacement == find_node) {
             parent_of_replacement = successor;
        }

        removed_node = remove_node_with_one_or_zero(&successor);

        find_node->key = successor->key;
    }

    if (removed_color == RBTREE_BLACK) {
        rebalanceAfterDeletion(t, replacement_node, parent_of_replacement);
    }

    if (removed_node != NULL) {
        free(removed_node);
    }

    return 1;
}

node_t* remove_node_with_one_or_zero(node_t ** node) {
    if (node == NULL || *node == NULL) {
        return NULL;
    }

    node_t *original_node_to_free = *node;
    node_t *parent = original_node_to_free->parent;
    node_t *child = (original_node_to_free->left != NULL) ? original_node_to_free->left : original_node_to_free->right;

    if (child != NULL) {
        child->parent = parent;
    }

    if (parent == NULL) {
        *node = child;
    } else {
        if (parent->left == original_node_to_free) {
            parent->left = child;
        } else {
            parent->right = child;
        }
    }

    return original_node_to_free;
}

node_t * find_successor(node_t * node) {
    if (node == NULL || node->right == NULL) {
        return NULL;
    }

    node_t *cur = node->right;
    while (cur->left != NULL) {
        cur = cur->left;
    }
    return cur;
}

void rebalanceAfterDeletion(rbtree *t, node_t *node, node_t *parent) {
    node_t *sibling;

    // node가 루트가 아니고, "doubly black" 속성을 가질 동안 반복
    while (node != t->root && (node == NULL || node->color == RBTREE_BLACK)) {
        // node가 NULL이거나 parent가 없으면 더 이상 진행할 수 없습니다.
        if (parent == NULL) break;

        // Case: node가 왼쪽 자식인 경우
        if (node == parent->left) {
            sibling = parent->right;

            // Case 1: 형제 sibling가 RED
            if (sibling != NULL && sibling->color == RBTREE_RED) {
                sibling->color = RBTREE_BLACK;
                parent->color = RBTREE_RED;

                node_t **ptr_to_parent = (parent->parent == NULL) ? &(t->root)
                                             : (parent == parent->parent->left ? &(parent->parent->left) : &(parent->parent->right));
                left_rotate(ptr_to_parent);
                sibling = parent->right; // 회전 후 형제가 바뀌었으므로 갱신
            }

            // Case 2: 형제 sibling가 BLACK이고, sibling의 두 자식이 모두 BLACK
            if (sibling == NULL || ((sibling->left == NULL || sibling->left->color == RBTREE_BLACK) &&
                              (sibling->right == NULL || sibling->right->color == RBTREE_BLACK))) {
                if (sibling != NULL) sibling->color = RBTREE_RED;
                node = parent; // 문제를 부모로 전가
                parent = node->parent;
                continue; // 다음 루프에서 처리
            }

            // Case 3: 형제 sibling이 BLACK, sibling의 왼쪽 자식이 RED, 오른쪽 자식이 BLACK
            if (sibling->right == NULL || sibling->right->color == RBTREE_BLACK) {
                if (sibling->left != NULL) sibling->left->color = RBTREE_BLACK;
                sibling->color = RBTREE_RED;
                right_rotate(&(parent->right)); // sibling는 parent의 오른쪽 자식이므로 &(parent->right)를 전달
                sibling = parent->right; // 회전 후 형제가 바뀌었으므로 갱신
            }

            // Case 4: 형제 node가 BLACK, node의 오른쪽 자식이 RED
            sibling->color = parent->color;
            parent->color = RBTREE_BLACK;
            if (sibling->right != NULL) sibling->right->color = RBTREE_BLACK;

            node_t **ptr_to_parent = (parent->parent == NULL) ? &(t->root)
                                    : (parent == parent->parent->left ? &(parent->parent->left) : &(parent->parent->right));
            left_rotate(ptr_to_parent);

            node = t->root; // 모든 문제가 해결되었으므로 루프 종료

        } else { // Case: node가 오른쪽 자식인 경우
            sibling = parent->left;

            // Case 1: 형제 sibling가 RED
            if (sibling != NULL && sibling->color == RBTREE_RED) {
                sibling->color = RBTREE_BLACK;
                parent->color = RBTREE_RED;

                node_t **ptr_to_parent = (parent->parent == NULL) ? &(t->root)
                                             : (parent == parent->parent->left ? &(parent->parent->left) : &(parent->parent->right));
                right_rotate(ptr_to_parent);
                sibling = parent->left;
            }

            // Case 2: 형제 sibling가 BLACK이고, sibling의 두 자식이 모두 BLACK
            if (sibling == NULL || ((sibling->left == NULL || sibling->left->color == RBTREE_BLACK) &&
                              (sibling->right == NULL || sibling->right->color == RBTREE_BLACK))) {
                if (sibling != NULL) sibling->color = RBTREE_RED;
                node = parent;
                parent = node->parent;
                continue;
            }

            // Case 3: 형제 sibling가 BLACK, sibling의 오른쪽 자식이 RED, 왼쪽 자식이 BLACK
            if (sibling->left == NULL || sibling->left->color == RBTREE_BLACK) {
                if (sibling->right != NULL) sibling->right->color = RBTREE_BLACK;
                sibling->color = RBTREE_RED;
                left_rotate(&(parent->left));
                sibling = parent->left;
            }

            // Case 4: 형제 sibling가 BLACK, sibling의 왼쪽 자식이 RED
            sibling->color = parent->color;
            parent->color = RBTREE_BLACK;
            if (sibling->left != NULL) sibling->left->color = RBTREE_BLACK;

            node_t **ptr_to_parent = (parent->parent == NULL) ? &(t->root)
                                    : (parent == parent->parent->left ? &(parent->parent->left) : &(parent->parent->right));
            right_rotate(ptr_to_parent);
            node = t->root;
        }
    }

    if (node != NULL) {
        node->color = RBTREE_BLACK;
    }
}

void in_order(node_t *node, key_t *arr, int *index, size_t size) {
    if (node == NULL || *index >= size) return;

    in_order(node->left, arr, index, size);

    if (*index >= size) return;
    arr[*index] = node->key;
    (*index)++;

    in_order(node->right, arr, index, size);
}

void right_rotate(node_t **node) {
    node_t *cur = *node;
    node_t *child = cur->left;

    cur->left = child->right;
    if (child->right != NULL)
        child->right->parent = cur;

    child->parent = cur->parent;
    child->right = cur;
    cur->parent = child;
    *node = child;
}

void left_rotate(node_t **node) {
    node_t *cur = *node;
    node_t *child = cur->right;

    cur->right = child->left;
    if (child->left != NULL)
        child->left->parent = cur;

    child->parent = cur->parent;
    child->left = cur;
    cur->parent = child;
    *node = child;
}

모깅

멈추지 않기

이전 포스트

[JUNGLE] TIL_37. RB Tree 삭제 일부 구현

다음 포스트