소프트웨어학과 k군

[CSAPP] 9장 가상 메모리(Virtual Memory) - 9.9(9.9.11 ~ 9.9.14)

9.9.11 경계 태그 병합(Boundary-Tag Coalescing)해제된 블록과 인접한 빈 블록을 헤더·풋터(boundary tags) 정보를 이용해 즉시 합치는 방식입니다.풋터에 크기 정보를 복사해 두면, 해제 시 이전 블록의 크기를 O(1)로 알 수 있습니다​.free(ptr) 호출 시 왼쪽·오른쪽 이웃 블록의 할당 비트를 검사하고, 모두 자유 상태라면 세 블록을 하나로 합칩니다​. 즉시 병합(immediate coalescing)을 쓰면 외부 단편화를 효과적으로 줄이지만, 매 free마다 검사 비용이 추가될 수 있습니다​. Header/​Footer 모두에 블록 크기와 할당 비트(a/f)를 저장합니다.free 시 Footer로 이전 블록 크기를 즉시 알아낼 수 있어 빠른 병합이 가능합니다.병합..

[CSAPP] 9장 가상 메모리(Virtual Memory) - 9.9(9.9.6 ~ 9.9.10)

9.9.6 암시적 가용 리스트(Implicit Free List)힙의 모든 블록(할당·자유)을 헤더(header)·풋터(footer) 만으로 관리하고, 빈 블록을 찾을 때마다 힙을 처음부터 끝까지 순차 탐색합니다.헤더·풋터 구조크기(size) 필드: 블록 전체 크기(헤더+페이로드+패딩 포함)할당 비트(a): LSB로 “1=할당됨, 0=자유”를 표시동작 원리현재 블록의 헤더에서 크기와 할당 여부를 읽는다.다음 블록 주소로 포인터를 옮긴다.할당 비트가 0인 블록을 발견하면 그곳을 사용.힙 전체를 탐색하는 구조이므로 구현은 간단하지만, 블록 수 * n 에 비례한 O(n) 탐색 시간이 소요됩니다.9.9.7 할당 위치 선택(Placement)빈 블록 탐색 후 어떤 블록을 사용할지 결정하는 전략기법설명장,단점Fir..

[CSAPP] 9장 가상 메모리(Virtual Memory) - 9.9(9.9.1 ~ 9.9.5)

동적 메모리 할당은 C 프로그램이 실행 중에 힙(heap) 영역에서 메모리 블록을 확보·반환하는 기법입니다.힙은 초기화되지 않은 데이터 세그먼트(.bss) 바로 뒤에서 시작해, 커널이 brk/sbrk 호출로 demand-zero 페이지를 위로 확장하는 영역입니다.할당자는 힙을 크기가 다양한 블록들의 집합으로 유지하며, 각 블록은 할당됨(allocated) 또는 비어 있음(free) 상태로 표시됩니다.이때 메모리를 직접 malloc/free로 관리하는 방식을 명시적 할당자(explicit allocator), 가비지 콜렉터가 자동으로 해제하는 방식을 암시적 할당자(implicit allocator)라고 한다​구분명시적(explicit) 할당자암시적(implicit) 할당자관리 주체프로그래머가 직접 mall..

[CSAPP] 7.9 실행 가능 목적 파일(Executable Object Files)

들어가며리눅스에서 프로그램을 실행한다는 것은 단순히 저장장치에 있는 바이너리 파일을 읽어 들이는 것만을 의미하지 않습니다. 커널은 ELF 포맷의 실행 파일을 해석해, 필요한 부분만 골라 메모리에 올리고, 프로그램이 안전하게 돌아갈 수 있도록 다양한 초기화 작업을 수행하죠. 이번 글에서는 “실행 가능(executable) 상태”가 되기 위해 반드시 충족해야 하는 세 가지 핵심 조건을 짚어 보고, 링킹과 실행의 전체 흐름을 함께 살펴보겠습니다.링킹과 실행: 전체 흐름 요약아래 흐름도는 소스코드 작성 → 컴파일·어셈블 → 링킹 → ELF 파일 구조 정리 → 실행 시 로딩의 전 과정을 한눈에 보여줍니다.1. 소스코드 작성 (e.g. main.c, sum.c) • C 언어로 프로그램을 작성 • 고급 언어 ..

9.5 가상 메모리를 통한 메모리 보호가상 메모리 시스템은 프로세스마다 독립된 주소 공간을 제공할 뿐 아니라, 페이지 단위로 접근 권한을 통제할 수 있는 메커니즘을 갖추고 있습니다.페이지 테이블 엔트리(PTE)의 권한 비트각 PTE에 SUP(kernel vs user), READ, WRITE 비트를 두어 접근을 제어합니다.사용자 모드가 SUP=1인 페이지 접근 시 Segmentation Fault 발생 읽기/쓰기 비트가 맞지 않으면 Protection Fault 발생메모리 보호 다이어그램┌─────────────┐ PTE: SUP=0, R=1, W=0│ Virtual VP0 │ ──▶│ Physical PP2 │ (읽기만 가능)└─────────────┘ Permissions: r/o ┌..

1. 레드 - 블랙 트리 개요1.1 기원과 정의레드‑블랙 트리는 Leonidas J. Guibas와 Robert Sedgewick이 1978년에 제안한 self‑balancing 이진 탐색 트리 자료구조입니다.각 노드는 추가로 한 비트(“색상(color)”) 정보를 가지며, 이 색상은 red 또는 black 중 하나입니다.이 색상 비트는 삽입/삭제 시 균형을 유지하기 위한 제약 조건을 정의하는 데 사용됩니다.이론적으로 RBT는 삽입·삭제·탐색 모든 연산에서 최악 O(log n)의 시간 복잡도를 보장합니다.또한 2‑3‑4 트리(B‑트리의 특수형)와 구조적으로 대응 관계가 있어, 2‑3‑4 트리의 각 노드를 하나의 black 노드와 그에 연결된 red 자식 그룹으로 매핑할 수 있습니다.1.2 주요 제약조건(..

9.3 가상 메모리를 캐시로 사용하기가상 메모리 시스템은 디스크(보조 저장장치)에 있는 데이터를 메인 메모리(RAM)로 필요할 때 불러오는 캐시 역할을 합니다.즉, 메모리 그 자체가 디스크의 캐시로 동작하는 구조입니다.9.3.1 DRAM 캐시의 구조가상 주소 공간은 일정한 크기 단위인 페이지(Page)로 나뉩니다.운영체제는 이 가상 페이지를 메인 메모리의 프레임(Frame)에 매핑하여 사용합니다.페이지(Page): 가상 메모리의 기본 단위 (보통 4KB)프레임(Frame): 물리 메모리의 기본 단위 (페이지와 크기 동일)👉 디스크 → 페이지 단위👉 메인 메모리 → 프레임 단위하나의 프로세스는 수천~수만 개의 페이지를 가질 수 있고, 이 중 일부만이 실제 메모리에 올라와 있습니다.9.3.2 페이지 테이..

왜 가상 메모리를 배워야 할까?가상 메모리는 단순한 메모리 관리 기술이 아닙니다. 현대 운영체제, 컴파일러, 하드웨어의 핵심 연결고리이자, 다음과 같은 강력한 기능을 제공합니다.(1) 효율적인 메모리 사용→ 실제 메모리보다 큰 프로그램도 실행 가능하게 해줍니다. 디스크에 있는 데이터를 필요할 때만 메모리에 불러오는 캐시 구조로 동작합니다.(2) 프로세스 간 메모리 보호→ 각 프로세스는 자기만의 가상 주소 공간을 갖습니다. 다른 프로세스 메모리에 접근할 수 없어 안정성이 보장됩니다.(3) 메모리 관리 단순화→ 개발자는 '주소'를 직접 신경 쓰지 않고도 동적으로 메모리를 할당하고 해제할 수 있습니다.9.1 물리 및 가상 주소 방식물리 주소 (Physical Address)실제 DRAM(메인 메모리) 상의 주..

8.4 프로세스의 제어(Process Control)운영체제와 프로그램이 프로세스를 생성·종료·관리하는 메커니즘을 설명합니다.8.4.1 프로세스 ID 얻기각 프로세스는 고유한 PID(Process ID)를 가지며, 이를 통해 부모·자식 관계를 파악하거나 프로세스 제어를 수행할 수 있습니다.getpid() : 호출 프로세스의 PID를 반환하며, 항상 성공합니다. getppid(): 부모 프로세스의 PID를 반환하며, 부모가 이미 종료된 경우에는 1(init)의 PID를 반환합니다.#include #include int main() { printf("PID = %d\n", getpid()); // 호출 프로세스의 PID 반환 :contentReference[oaicite:0]{index=0} p..

이번 포스팅에서는 예외적인 제어 흐름(ECF, Exceptional Control Flow)에 대해 다룹니다. 이를 이해하기 위해 먼저 일반적인 제어 흐름에 대해 간단히 알아보겠습니다.일반적인 제어 흐름컴퓨터 프로그램은 보통 메모리에 연속적으로 저장된 명령어들을 순차적으로 실행합니다. 이러한 흐름은 다음과 같은 방식으로 이루어집니다:순차 실행: 명령어들이 메모리에 저장된 순서대로 실행됩니다.분기 및 반복: 조건문과 반복문을 통해 특정 조건에 따라 흐름이 변경됩니다.함수 호출과 반환: 함수를 호출하면 해당 함수의 명령어들이 실행되고, 완료되면 원래 위치로 돌아옵니다.하지만, 프로그램 실행 중 예기치 않은 상황이나 외부 이벤트로 인해 이러한 흐름이 갑자기 변경되는 경우가 있습니다. 이를 예외적인 제어 흐름(..