[CS:APP 9.9] 비전공자가 이해한 malloc — 동적 메모리 할당 부터 구현 이슈 까지(malloc-lab 대비)

Об этом предложении

[CS:APP] 9.9 동적 메모리 할당 정리 (9.9 ~ 9.9.5) malloc-lab대비 할당기(malloc)는 힙이라는 메모리 영역을 블록 단위로 쪼개서 빌려주고(malloc) 돌려받는(free) 관리자다. 말록랩은 이 관리자를 직접 만드는 과제다. 말록랩의 mm.c 에서 채워야 하는 함수는 4개다. int mm_init(void); // 힙을 처음 세팅 void *mm_malloc(size_t size); // 블록 빌려주기 void mm_free(void *ptr); // 블록 돌려받기 void *mm_realloc(void *ptr, size_t size); // 크기 바꾸기 9.9 ~ 9.9.5는 이 4개 함수가 지켜야 할 규칙과 채점 기준, 설계 결정 목록을 담고 있다. 그래서 각 개념마다 "말록랩에서는?"을 같이 정리했다. 9.9 동적 메모리 할당: 힙이라는 영역 힙은 프로그램이 실행 중에 필요한 만큼 빌려 쓰는 가상 메모리 영역이다. 크기가 미리 정해지지 않으므로 필요하면 높은 주소 방향으로 늘린다. 힙은 초기화되지 않은 데이터 영역( .bss ) 바로 위에서 시작한다. 힙은 요구 0(demand-zero) 메모리 영역이다. 처음 접근할 때 0으로 채워진 페이지를 받는다. 커널은 프로세스마다 힙의 꼭대기를 가리키는 brk (break) 값을 관리한다. 할당기는 힙을 블록들의 모음 으로 관리한다. 블록은 연속된 가상 메모리 묶음이다. 높은 주소 ┌──────────────────────────┐ ← brk (힙 꼭대기) │ [할당][가용][할당][가용] │ ← 힙 = 블록들의 줄 ├──────────────────────────┤ │ .bss / .data / .text │ 낮은 주소 블록의 상태는 둘 중 하나다. 할당(allocated) : 프로그램이 쓰고 있다. 반환될 때까지 그대로 남는다. 가용(free) : 비어 있어서 다음 할당 요청에 줄 수 있다. 명시적 할당기 vs 묵시적 할당기 두 종류 모두 할당은 프로그램이 명시적으로 요청한다. 차이는 반환을 누가 하느냐다. 명시적 할당기 묵시적 할당기 반환은 누가 프로그래머가 free 호출 할당기가 안 쓰는 블록을 찾아서 반환 예 C의 malloc 패키지 Java, Python의 가비지 컬렉터 말록랩 해당 (직접 만드는 것) 해당 없음 명시적 할당기에서 free 를 하지 않으면 블록은 계속 할당된 채로 남는다. 단, 프로세스가 끝나면 OS가 주소공간 전체를 회수한다. 9.9.1 malloc과 free: 지켜야 할 규칙 malloc 규칙 1: 최소 size 바이트, 정렬된 주소 책 기준으로 malloc은 32비트에서 8의 배수, 64비트에서 16의 배수 주소를 리턴한다. 말록랩 mm.c 에는 #define ALIGNMENT 8 이 정의되어 있어서(자기 파일에서 확인) 요청 크기를 8의 배수로 올림한다. #define ALIGN(size) (((size) + (ALIGNMENT-1)) & ~0x7) size = 13 을 넣으면 이렇게 계산된다. 13 + 7 = 20 20은 2진수로 10100 & ~0x7 로 아래 3비트를 지우면 10000 = 16 13바이트를 요청해도 16바이트를 준다. "최소 size 바이트"라는 말의 뜻이 이것이다. malloc 규칙 2: 실패하면 NULL 가용한 가상 메모리보다 큰 블록을 요청하면 malloc은 NULL 을 리턴하고 errno 를 설정한다. 말록랩에서도 힙을 늘리다 실패하면 mm_malloc 은 NULL 을 리턴해야 한다. malloc 규칙 3: 리턴하는 메모리를 초기화하지 않음 힙은 demand-zero라서 처음엔 0인데, malloc이 0을 보장하지 않는 이유는 재사용 때문이다. free된 블록을 다시 빌려주면 이전에 쓰던 값이 그대로 남아 있다. calloc과 realloc calloc : malloc을 감싼 얇은 래퍼 함수다. malloc으로 받은 메모리를 0으로 초기화한다. realloc : 이미 할당된 블록의 크기를 바꾼다. 말록랩의 mm_realloc 이 이것이다. 힙을 늘리는 함수: sbrk malloc 같은 할당기는 mmap / munmap 으로 힙 메모리를 할당·반환하거나 sbrk 를 쓴다. 말록랩에서는 memlib.c 의 mem_sbrk 만 쓴다. sbrk(incr) 은 brk 에 incr 바이트를 더해 힙을 늘리거나 줄인다. 성공: 이전 brk 값을 리턴한다. 즉 새로 생긴 공간의 시작 주소다. 실패: (void *)-1 을 리턴하고 errno 를 ENOMEM 으로 설정한다. incr 이 0이면 현재 brk 를 리턴한다. brk = 0x2000 일 때 mem_sbrk(32) 를 호출하는 경우를 계산해 보면, 32는 10진수라서 16진수로 먼저 바꾼다. 32 ÷ 16 = 2, 나머지 0이므로 32 = 0x20 이다. 0x2020 ┌───────────────────┐ ← 호출 후 brk (0x2000 + 0x20) │ 새로 생긴 32바이트 │ 0x2000 └───────────────────┘ ← 이전 brk = 리턴값 │ 기존 힙 │ 호출 (brk = 0x2000 ) 리턴값 호출 후 brk mem_sbrk(32) 0x2000 0x2020 mem_sbrk(16) 0x2000 0x2010 free 규칙 ptr 은 malloc, calloc, realloc이 돌려준 블록의 시작 주소 여야 한다. 아니면 동작이 정의되지 않는다. free는 리턴값이 없어서, 잘못 호출해도 프로그램은 실패를 알 수 없다. 말록랩의 채점 trace는 올바른 포인터만 넘기므로, mm_free 에서 포인터 유효성 검사는 하지 않아도 된다. 9.9.2 왜 동적 할당이 필요한가 필요한 메모리 크기를 실행해 봐야 알 수 있는 경우가 많기 때문이다. int n; scanf("%d", &n); // 실행해 봐야 n을 앎 int *arr = malloc(n * sizeof(int)); n이 5일지 100만일지 컴파일 시점에는 모른다. 배열 크기를 미리 100만으로 고정하면 n이 5일 때 낭비가 크고, 100만을 넘으면 프로그램이 터진다. 그래서 실행 중에 필요한 만큼 힙에서 받는다. 9.9.3 할당기의 요구사항과 목표 요구사항은 반드시 지켜야 하는 규칙이고, 목표는 잘할수록 점수가 높아지는 기준이다. 요구사항 요구사항 뜻 말록랩에서 임의의 요청 순서 처리 malloc/free가 어떤 순서로 와도 처리 (free는 할당된 블록에만 옴) trace 파일이 무작위 순서로 호출 즉시 응답 요청을 모았다가 처리하거나 순서를 바꾸면 안 됨 호출 하나에 바로 결과 리턴 힙만 사용 할당기의 자료구조도 힙 안에 둠 큰 전역 배열을 잡아 쓰는 방식 금지 블록 정렬 어떤 타입이든 담을 수 있게 정렬 ALIGN() 매크로 할당된 블록 수정 금지 빌려준 블록을 옮기거나 압축하면 안 됨 압축(compaction) 불가 마지막 규칙의 이유: 사용자가 이미 그 주소를 포인터로 들고 있다. 할당기가 블록을 옮기면 사용자 포인터가 엉뚱한 곳을 가리키게 된다. 그래서 한 번 빌려준 블록은 free될 때까지 그 자리에 고정이다. 목표 1: 처리량(throughput) 최대화 단위 시간당 처리하는 요청 수다. 즉 빠를수록 좋다. 목표 2: 메모리 이용도(utilization) 최대화 힙을 얼마나 알뜰하게 쓰는지다. 책은 **최고 이용도(peak utilization)**로 측정한다. U = \frac{\text{동시에 살아 있던 payload 합의 최댓값}}{\text{힙의 최종 크기}} payload는 사용자가 실제로 요청한 바이트다. 예시로 계산해 보면 다음과 같다. 요청 살아 있는 payload 합 힙 크기 p1 = malloc(16) 16 24 p2 = malloc(32) 16 + 32 = 48 (최대) 64 free(p1) 32 64 U = 48 ÷ 64 = 0.75 (75%). 같은 요청을 힙 56바이트로 처리했다면 48 ÷ 56 ≈ 0.86으로 더 좋은 할당기다. 두 목표는 서로 충돌한다 전략 처리량 이용도 판정 free된 블록은 무시하고 매번 mem_sbrk 로 새로 늘림 매우 빠름 최악 (힙이 계속 커짐) 나쁨 요청마다 모든 가용 블록을 뒤져서 딱 맞는 것을 찾음 느림 좋음 한쪽으로 치우침 적당히 찾되, 빨리 찾을 수 있게 가용 블록을 정리해 둠 균형 균형 말록랩이 원하는 방향 판단 기준: 한쪽만 극단적으로 올리는 설계는 점수가 나오지 않는다. 원래 CS:APP 랩의 점수식은 다음과 같다. 가중치는 과정마다 다를 수 있으니 핸드아웃에서 확인한다. P = 0.6U + 0.4\min\left(1, \frac{T}{T_{libc}}\right) 실행하면 mdriver 가 util (이용도)과 thru (처리량)를 따로 보여준다. 9.9.4 단편화: 이용도를 떨어뜨리는 원인 단편화는 메모리가 남아 있는데도 요청에 쓸 수 없는 상태다. 내부 단편화와 외부 단편화 두 종류가 있다. 내부 단편화: 블록 안의 낭비 빌려준 블록이 요청한 payload보다 커서 생기는 낭비다. malloc(13) 요청 → ALIGN(13) = 16바이트 블록 ┌─────────────────┬───┐ │ payload 13 │ 3 │ ← 이 3바이트는 아무도 못 씀 └─────────────────┴───┘ 원인은 정렬, 그리고 헤더/풋터 같은 관리용 정보(9.9.6에서 다룸)다. 현재 블록만 보면 바로 계산할 수 있어서 측정이 쉽다. 외부 단편화: 블록 사이의 낭비 가용 메모리를 모두 합치면 충분한데, 한 덩어리로 연속된 공간이 없어서 요청을 처리하지 못하는 상태다. [가용 16][할당 16][가용 16] malloc(32) 요청 → 가용 합계는 32지만 연속된 32가 없음 → mem_sbrk로 힙을 늘려야 함 → 이용도 하락 외부 단편화는 미래의 요청에 따라 문제가 되기도 하고 안 되기도 해서 측정하기 어렵다. 위 상황에서 다음 요청이 malloc(8) 뿐이라면 아무 문제가 없다. 내부 단편화 외부 단편화 위치 블록 안 블록 사이 원인 정렬, 헤더/풋터, 최소 블록 크기 가용 블록이 흩어져 있음 측정 쉬움 (현재 블록만 보면 됨) 어려움 (미래 요청에 달림) 9.9.5 구현 이슈: 말록랩에서 결정할 4가지 할당기를 만들려면 아래 네 질문에 답해야 한다. 이 표가 9.9.6 이후 내용의 목차다. 질문 이름 다루는 절 가용 블록들을 어떻게 기록하고 추적하나? 가용 블록 구성 9.9.6 묵시적 가용 리스트, 9.9.13 명시적 가용 리스트 요청이 오면 어느 가용 블록을 고르나? 배치(placement) 9.9.7 (first fit, next fit, best fit) 고른 블록이 요청보다 크면 남는 부분은? 분할(splitting) 9.9.8 free된 블록 옆에 또 가용 블록이 있으면? 연결(coalescing) 9.9.10 9.9.4의 외부 단편화 예시가 연결이 필요한 이유다. [가용 16][가용 16] 이 붙어 있는데 따로 관리하면 32바이트 요청을 받지 못한다. 둘을 합쳐 [가용 32] 로 만들어야 한다. 정리: 말록랩 연결표 말록랩 연결표 책 개념 말록랩에서 힙, brk mem_heap_lo() ~ mem_heap_hi() , 내부의 mem_brk sbrk mem_sbrk(incr) 정렬 규칙 ALIGNMENT , ALIGN() 매크로 malloc 실패 시 NULL mem_sbrk 실패 시 mm_malloc 이 NULL 리턴 realloc mm_realloc 처리량, 최고 이용도 mdriver 의 thru , util 4가지 구현 이슈 9.9.6부터 배울 mm.c 의 본체