1. 구현 목표이전 포스팅을 통해 RB-Tree의 생성과 트리 삭제, 탐색을 다뤘다면 이번 글에서는 RB-Tree의 핵심인 삽입과 삭제를 다루기 전에 추가적으로 필요한 기능들을 구현하고 넘어가려고 한다.2025.04.20 - [크래프톤 정글] - RB-Tree 구현하기 (C언어) - Part.1 설명 및 뼈대 구현 RB-Tree 구현하기 (C언어) - Part.1 설명 및 뼈대 구현RB-Tree(Red Black Tree)란?컴퓨터 과학에서 이진 탐색 트리(BST: binary search tree)는 다음과 같은 속성이 있는 이진트리 자료 구조이다.각 노드에 값이 있다.값들은 전순서가 있다.노드의 왼쪽 서브트리에www.gowoong.com우리가 이번에 구현할 기능은 RB-Tree에서 최소 값과 최댓값을..

RB-Tree(Red Black Tree)란?컴퓨터 과학에서 이진 탐색 트리(BST: binary search tree)는 다음과 같은 속성이 있는 이진트리 자료 구조이다.각 노드에 값이 있다.값들은 전순서가 있다.노드의 왼쪽 서브트리에는 그 노드의 값보다 작은 값들을 지닌 노드들로 이루어져 있다.노드의 오른쪽 서브트리에는 그 노드의 값보다 큰 값들을 지닌 노드들로 이루어져 있다.좌우 하위 트리는 각각이 다시 이진 탐색 트리여야 한다.높이가 h인 이진 탐색 트리에서 동적 집합 연산이 O(h) 될 수 있다는 것이다. 즉 이진 탐색 트리의 경우 치우친 편향 트리 (skewed tree)가 발생할 수 있다.위의 이미지가 치우친 편향 트리의 예시인데 만약 이러한 트리에 100개의 자식이 전부 위와 같은 모양이고..

9.8 메모리 매핑 (Memory Mapping)리눅스는 가상 메모리 영역의 초기 내용을 디스크 상의 객체에 연결(mapping)함으로써 초기화한다. 이를 메모리 매핑(memory mapping)이라고 한다. 가상 메모리 영역은 다음 두 종류의 객체 중 하나에 매핑될 수 있다:일반 파일예: 실행 파일, 객체 파일 등.파일의 일부분을 페이지 단위로 나누어 가상 페이지에 대응시킨다.요구 페이징(demand paging)을 사용하므로, 해당 페이지에 실제 접근하기 전까지는 메모리에 로드되지 않는다.영역 크기가 파일보다 크면, 나머지 공간은 0으로 패딩 된다.익명 파일(anonymous file)커널이 생성한, 내용이 모두 0으로 채워진 임시 객체.이 영역의 페이지에 처음 접근할 때, 커널이 물리 메모리에서 희..

9.7 Intel Core i7/Linux 메모리 시스템 사례 연구지금까지 설명한 가상 메모리 개념들을 실제 시스템에 적용한 사례로, Intel Core i7에서 Linux가 사용하는 메모리 시스템을 다룬다.Core i7 아키텍처 개요하스웰(Haswell) 마이크로아키텍처는 64비트 가상 및 물리 주소 공간을 지원한다.현재 Core i7 구현은 다음을 지원한다:48비트 가상 주소 공간 (256TB)52비트 물리 주소 공간 (4PB)**32비트 호환 모드 (4GB 주소 공간)**도 존재한다.Core i7 메모리 구성4개의 코어, 공유 L3 캐시, DDR3 메모리 컨트롤러 포함각 코어는 다음을 포함함:L1 i-TLB (128 entries), L1 d-TLB (64 entries), L2 TLB (512 e..

9.6 주소 변환 (Address Translation)주소 변환은 가상 메모리 시스템에서 가상 주소 공간(VAS)의 각 주소를 물리 주소 공간(PAS)의 주소로 변환하는 과정을 뜻한다. 이 절의 목표는 하드웨어(MMU)의 동작 방식을 이해하고, 직접 주소 변환 과정을 계산해 볼 수 있을 정도로 개념을 익히는 것이다.주소 변환의 수학적 정의주소 변환은 다음과 같은 함수로 정의된다:MAP: VAS → PAS ∪ ∅MAP(A) = A′ : 가상 주소 A에 해당하는 데이터가 메모리에 있을 경우, 물리 주소 A′에 위치함.MAP(A) = ∅ : 해당 데이터가 현재 물리 메모리에 존재하지 않음 (즉, 페이지 폴트 발생 가능).변환 구성 요소가상 주소(VA)는 두 부분으로 나뉜다:VPN: 가상 페이지 번호 (상위 ..

9.4 가상 메모리를 메모리 관리 도구로 활용하기앞선 절에서는 가상 메모리가 DRAM을 디스크 기반 가상 주소 공간의 캐시로 활용하는 방식을 살펴봤다. 이번 절에서는 가상 메모리가 어떻게 메모리 관리를 단순화하고 개선하는지를 설명한다.독립적인 주소 공간현대 운영체제는 각 프로세스마다 독립적인 페이지 테이블을 제공한다.즉, 각 프로세스는 자신만의 가상 주소 공간을 갖는다.예를 들어, 프로세스 i는 VP1을 PP2에, VP2를 PP7에 매핑할 수 있고, 프로세스 j는 VP1을 PP7에, VP2를 PP10에 매핑할 수 있다.같은 물리 페이지를 서로 다른 가상 페이지가 공유하는 것도 가능하다. 이는 코드 공유 등에 유용하다​.장점링킹 단순화각 프로세스가 고정된 형식의 메모리 이미지(코드, 데이터, 스택 위치)를..

9.3 가상 메모리를 캐시로 사용하는 방법 (VM as a Tool for Caching)가상 메모리는 개념적으로 디스크에 저장된 N개의 연속적인 바이트 셀 배열로 구성되어 있다. 각각의 바이트는 고유한 가상 주소를 가지며, 이 주소는 배열의 인덱스 역할을 한다. 디스크에 있는 이 데이터는 메인 메모리에 캐시 된다. 이 구조는 메모리 계층의 다른 캐시들과 유사하게 작동한다.가상 메모리 시스템은 디스크와 메모리 간의 전송 단위로 고정 크기 블록을 사용한다. 이를 가상 페이지(Virtual Page, VP)라고 부르며, 보통 P = 2^p 바이트 크기를 갖는다. 물리 메모리 역시 같은 크기의 물리 페이지(Physical Page, PP)로 나뉜다.어떤 시점에서, 가상 페이지는 다음 세 가지 집합 중 하나에 ..

Chapter 9: Virtual Memory (가상 메모리)가상 메모리는 현대 시스템에서 매우 중요한 메모리 추상화 개념이다. 이 추상화는 각 프로세스에게 독립적이고 균일한 메모리 주소 공간을 제공하며, 다음 세 가지 주요 기능을 제공한다:캐싱 도구로서의 VM메모리에 전부 올려놓기에는 프로그램이 너무 크거나, 메모리가 부족할 수 있다. 가상 메모리는 주기억장치를 디스크 기반의 큰 주소 공간에 대한 캐시로 사용함으로써 효율적인 메모리 사용을 가능하게 한다.메모리 관리 도구로서의 VM사용자 수준의 메모리 할당자 (예: malloc) 구현에 도움을 준다. 가상 메모리를 사용하면 프로그램은 큰 연속적인 주소 공간을 가지고 있는 것처럼 보이므로, 다양한 할당 전략이 가능하다.메모리 보호 도구로서의 VM하나의 프..

8.6 Nonlocal Jumps (비지역 점프)C 언어에서 제공하는 비지역 점프(nonlocal jump)라는 고급 제어 흐름 기능을 설명한다.이는 함수 호출과 반환의 일반적인 흐름을 무시하고, 한 함수에서 다른 함수의 실행 지점으로 직접 점프하는 기능이다.핵심 함수: setjmp와 longjmp#include int setjmp(jmp_buf env);void longjmp(jmp_buf env, int val); setjmp는 현재 호출 환경(PC, SP, 레지스터 등)을 저장하고 0을 반환longjmp는 setjmp로 저장된 위치로 되돌아감. 이때 setjmp는 val 값을 반환하게 됨즉, setjmp는 한 번 호출되지만 여러 번 반환될 수 있음주요 활용: 에러 복구함수 호출이 깊이 중첩된 상황에..

8.5.5 Writing Signal Handlers (시그널 핸들러 작성)시그널 핸들러를 올바르게 작성하는 방법에 대해 설명한다. 시그널 핸들러는 예외적으로 실행되며, 메인 프로그램과 동시에 실행될 수 있기 때문에 작성이 까다롭다.시그널 핸들러 작성의 어려움시그널 핸들러는 메인 프로그램과 동시에 실행되며, 전역 변수를 공유함.언제 시그널이 수신되는지는 예측이 어려움 → 비순차적 실행시스템마다 동작 방식이 다를 수 있어 이식성 문제도 있음​.안전한 시그널 핸들러 작성 지침G0. 핸들러를 최대한 단순하게 유지가능한 한 간단한 동작만 수행해야 함예: 전역 변수에 플래그를 설정하고 바로 반환 → 메인 루프가 주기적으로 플래그를 검사하여 처리G1. async-signal-safe 함수만 호출시그널 핸들러 내에서..