[WEEK06] Malloc Lab 설명서 번역 (CS:APP)

http://csapp.cs.cmu.edu/3e/malloclab.pdf

이 글은 CSAPP (Computer Systems : A Programmer's Perspective) 교재의 참고자료 중 하나인 Malloc Lab 설명서를 번역한 글입니다.

오역이 있을 수 있으며, 특정 부분은 이해를 쉽게 하기 위해 의역하였음을 밝힙니다.

번역이 잘못된 부분은 댓글로 지적해주시면 감사하겠습니다.

 

수정1. 2022.10.28 - 전체적으로 문장을 매끄럽게 하고, 틀린 부분을 수정했으며 빠진 부분을 보충했습니다. (thanks to YJ)

 

 

Malloc Lab : Dynamic Storage Allocator(동적 메모리 할당기) 만들기

 

1. 소개

이번 실습에서는 C언어로 동적 메모리 할당기(dynamic storage allocator)를 만들게 됩니다. 즉, malloc, free, realloc을 여러분 버전으로 만드는거죠.

디자인 스페이스를 창의적으로 설계해서, 정확하고 효율적이며 속도도 빠른 할당기를 구현해보세요.

 

2. 로지스틱스

최대 두 명 정도까지 그룹지어서 작업하세요.

과제 내용에 대한 모든 정확한 설명, 수정사항 등은 코스 웹 페이지에 게시됩니다.

 

3. 배포 파일 설명

…(생략)…

당신이 다뤄야 할 파일은 mm.c입니다.

mdriver.c 프로그램은 여러분이 만든 솔루션의 성능을 평가하는 드라이버 프로그램입니다.

make 커맨드를 사용해서 드라이버 코드를 생성하고 ./mdriver -V 커맨드로 실행해보세요.

mm.c 파일을 보면, 여러분의 프로그래밍 팀 구성원 한 명(또는 두 명)의 개인 식별 정보를 삽입해야 하는 C 구조체 team 을 보게 될 겁니다. 나중에 까먹지 말고 지금 바로 정보를 넣어 보세요. (*역자 주 : 이 내용은 과제로 제출해야 되는 사람들에게만 해당되는 내용인 것 같습니다)

추후 랩을 완료하면, 솔루션이 들어 있는 파일(mm.c) 하나만 제출하게 됩니다.

 

4. 랩에서 어떻게 작업하면 될까요?

여러분의 동적 메모리 할당기(dynamic storage allocator)는 다음 네 개의 기능을 포함하게 될 것입니다. 아래 코드는 mm.h에 선언되어 있고mm.c에 정의되어 있어요.

int mm_init(void);
void *mm_malloc(size_t size);
void mm_free(void *ptr);
void *mm_realloc(void *ptr, size_t size);

여러분에게 제공된 파일 mm.c 는 저희 생각에 가장 간단하면서도 정확하게 작동하는 malloc 패키지를 구현합니다.

이 파일로 시작해서, 아래 시멘틱스를 준수하도록 기능을 수정하세요. (구현 과정에서 다른 private static function을 정의해도 됩니다)

• mm_init : mm_malloc, mm_realloc, mm_free를 호출하기 전에, 응용 프로그램(예를 들면 구현 평가에 쓰일 Trace-driven 드라이버 프로그램)은 초기 힙 영역 할당과 같은 필수적인 초기화를 수행하기 위해 mm_init을 호출할 겁니다. mm_init은 초기화에 문제가 있으면 -1을 리턴하고, 그렇지 않으면 0을 리턴해야 합니다.
• mm_malloc : mm_malloc 루틴은 최소 size 바이트로 할당된 블록 페이로드를 가리키는 포인터를 리턴합니다. 모든 할당된 블록은 heap 영역에 있어야 하며, 다른 할당된 덩어리들과 겹치지 않아야 합니다.
  저희는 표준 C 라이브러리(libc)에 지원되는 malloc 과 당신이 구현한 mm_malloc을 비교할 겁니다. libc malloc이 항상 8바이트에 정렬된 페이로드 포인터를 리턴하기 때문에, 당신이 구현한 malloc도 항상 8바이트에 정렬된 포인터를 리턴해야 합니다.
• mm_free : mm_free 루틴은 ptr가 가리키는 블록을 free 해주고, 아무것도 리턴하지 않습니다. 이 루틴은 전달받은 ptr가 이전에 호출한 mm_malloc 또는 mm_realloc에 의해 리턴된 것이면서 아직 free되지 않았을 때만 작동을 보장합니다.
• mm_realloc : mm_realloc 은 최소 size 바이트로 할당된 구역을 가리키는 포인터를 아래의 조건에 따라 리턴합니다.
  • 만약 ptr가 NULL이면, 이 호출은 mm_malloc(size); 와 동일합니다.
  • 만약 size 가 0이면, 이 호출은 mm_free(ptr); 와 동일합니다.
  • 만약 ptr가 NULL이 아닐 경우, 이 ptr는 이전에 실행된 mm_malloc 이나 mm_realloc 에 의해 리턴된 것이어야만 합니다.
    mm_realloc 은 ptr가 가리키는 메모리 블록의 사이즈를 size 바이트에 맞게 바꾸고, 새로운 블록의 주소를 리턴합니다. 새로운 블록의 주소는 — 당신의 구현 방식이나 이전 블록의 내부 단편화(fragmentation) 정도, 그리고 realloc 요청의 size에 따라서 — 예전 블록의 주소와 같을 수도 있고 다를 수도 있다는 사실을 알아두세요.
    구(old) 블록과 새(new) 블록의 size 중 작은 크기까지는, 새 메모리 블록의 내용이 구 ptr 블록의 내용과 같게 됩니다. 다른 모든 것은 초기화되지 않습니다(uninitialized). 예를 들어, 구 블록이 8바이트 크기고 새 블록이 12바이트 크기면, 새 블록의 8바이트 까지는 구 블록의 첫 8바이트와 같을 것이고 뒤의 4바이트는 초기화되지 않은 상태일 겁니다. 동일하게, 구 블록이 8바이트 크기이고 새 블록이 4바이트 크기이면 새 블록의 내용은 구 블록의 첫 4바이트와 같을 겁니다.

위의 조건들은 C언어 기본 libc의 malloc, realloc, free 조건과 동일합니다. 완전한 문서를 더 보고 싶다면, shell에 man malloc을 입력하세요.

 

5. 힙 일관성 검사기 (Heap Consistency Checker)

동적 메모리 할당기(Dynamic memory allocators)는 정확하고 효율적으로 프로그래밍 하기가 어렵기로 악명 높습니다. 타입이 선언되지 않은 포인터의 조작이 엄청나게 많이 이루어지기 때문이죠. 여러분은 heap checker를 써서 heap을 스캔하고 일관성을 체크하는 것이 굉장히 도움된다는 사실을 알게 될 겁니다.

 

heap checker는 뭘 체크할까요? 몇 가지 예를 들어봅시다 :

• 가용 리스트(free list)에 있는 모든 블록에 대해 '가용'하다는 표시가 되어 있는가?
• 연결되지 못한 연속된 가용 블록이 있는가?
• 모든 가용 블록이 실제로 가용 리스트에 있는가?
• 가용 리스트에 있는 포인터가 유효한 가용 블록을 가리키고 있는가?
• 할당된 블록들 중 겹치는 게 있는가?
• heap 블록에 있는 포인터들이 유효한 heap 주소를 가리키고 있는가?

여러분의 heap checker는 mm.c 에 있는 int mm_check(void) 함수로 구성될 겁니다. 여러분이 중요하다고 생각하는 모든 불변성, 일관성 조건을 체크하죠. heap checker는 여러분의 heap이 일관적일 경우에만 0이 아닌 값을 리턴할 것입니다. 위에 열거된 내용들을 모두 체크하려고 너무 묶여있을 필요는 없습니다. 그저 mm_check가 fail할 때 에러 메시지를 출력하기만 하면 됩니다.

 

6. 지원되는 루틴들

memlib.c 패키지는 여러분의 동적 메모리 할당기를 위한 메모리 시스템을 시뮬레이션 해줍니다. 여러분은 아래의 memlib.c함수들을 사용할 수 있습니다 :

• void *mem_sbrk(int incr) : 0이 아닌 양의 정수인 incr의 바이트 크기에 맞게 heap을 증가시킵니다. 그리고 새로 할당된 heap 영역의 첫 번째 바이트를 가리키는 generic 포인터를 리턴합니다. 이 함수는 오직 0이 아닌 양의 정수만을 인자로 갖는다는 점을 제외하면 Unix의 sbrk 함수와 동일합니다.
• void *mem_heap_lo(void) : heap의 첫번째 바이트를 가리키는 generic 포인터를 리턴합니다.
• void *mem_heap_hi(void) : heap의 마지막 바이트를 가리키는 generic 포인터를 리턴합니다.
• size_t mem_heapsize(void) : heap이 현재 몇 바이트 크기인지를 리턴합니다.
• size_t mem_pagesize(void) : system의 page가 몇 바이트 크기인지 리턴합니다. (Linux 시스템에서는 4K)

 

7. 추적 기반(Trace-driven) 드라이버 프로그램

드라이버 프로그램인 mdriver.c는 여러분의 mm.c 패키지의 정확성, 공간 활용도, 처리량을 테스트합니다. 드라이버 프로그램은 trace file들에 의해 컨트롤됩니다. 각 trace file들은 드라이버가 mm_malloc, mm_realloc, mm_free 를 호출하도록 지시하는 일련의 할당(allocate), 재할당(reallocate), 해방(free) 명령을 포함하고 있습니다. 드라이버와 trace file 둘 다 나중에 여러분들의 mm.c 파일에 점수를 매길 때 사용할 도구들입니다.

 

mdriver.c 드라이버는 아래의 커맨드라인 인자들을 받을 수 있습니다 :

• -t <tracedir> : config.h에 정의된 기본값 디렉토리 대신에 <tracedir> 디렉토리에서 기본값 trace file을 찾게 합니다.
• -f <tracefile> : 기본 trace file들 대신에 하나의 특정한 tracefile을 사용합니다.
• -h : 커맨드라인 인자들에 대한 요약을 출력합니다. (*역자 주 : -h는 help 명령어입니다.)
• -l : 여러분의 malloc 패키지에 추가로 libc malloc도 실행하여 측정합니다.
• -v : 상세(verbose) 출력. compact table에 있는 각 trace file에 대한 성능 분석을 출력합니다.
• -V : (대문자 V) 더욱 상세한 출력. 각 trace file이 처리될 때마다 추가 진단 정보를 출력합니다. 이는 malloc 패키지의 실패 원인인 trace file이 어떤 건지 알아내기 위해서 디버깅할 때 유용합니다.

 

8. 프로그래밍 규칙

• mm.c 안에 있는 어떤 인터페이스도 수정해서는 안됩니다.
• 메모리 관리와 관련된 그 어떤 라이브러리 콜이나 시스템 콜도 불러와서는 안됩니다. 이 말은 malloc, calloc, free, realloc, sbrk, brk 또는 이러한 콜과 관련된 어떠한 변수도 여러분의 코드에 사용해서는 안 된다는 것을 의미합니다.
• 여러분의 mm.c 파일에 배열, 구조체, 트리, 리스트 같은 전역이거나 정적인(static) 복합 데이터 구조를 정의하는 것이 허용되지 않습니다. 하지만 integer, float, pointer 같은 전역 확장성 변수는 허용됩니다.
• 8바이트 경계에 정렬된 블록을 리턴하는 libc malloc 패키지와의 일관성을 위해서, 여러분의 할당기는 항상 8바이트에 정렬된 포인터를 리턴해야 합니다. 드라이버는 여러분에게 이 요구사항을 강요할 겁니다.

 

9. 채점

여러분의 코드가 버그를 일으키거나, 드라이버와 충돌하거나, 위의 규칙들을 어긴다면 0점을 받을 것입니다. 그렇지 않다면 다음 조건들로 점수를 매길 것입니다 :

• 정확성 (20점) : 당신의 솔루션이 드라이버 프로그램의 정확성 테스트를 통과한다면 만점을 받을 수 있습니다. 각 trace가 맞을때마다 부분 점수가 주어집니다.
• 성능 (35점) : 솔루션을 평가하기 위해 두 가지 성능 메트릭스가 사용됩니다.
  • 공간 활용도 : 드라이버가 사용한 총 메모리 사용량 (mm_malloc, mm_realloc 에 의해 할당되었으나 mm_free로 free되지 않은 것들)과 당신의 할당기가 사용한 heap 공간의 크기 사이의 피크 비율을 봅니다. 이상적인 비율은 1입니다. 비율을 최대한 1과 가깝게 만들기 위해 단편화를 최소화하는 방법을 찾으세요.
  • 처리량 : 초당 실행된 평균 작업 수를 말합니다.

드라이버 프로그램은 당신의 할당기의 성능을 성능 지수 P로 계산해서 보여줍니다.

성능 지수 P는 가중치가 있는 공간 활용도와 처리량의 합계입니다 :

$$
P=wU+(1-w)min(1,{T \over T_{libc}})
$$

$U$는 공간 활용도이고, $T$는 처리량, $T_{libc}$는 여러분 시스템의 기본 trace에 있는 libc malloc의 예상 처리량을 말합니다. 이 성능 지수는 처리량보다 공간 활용도에 가중치가 있으며, 기본값은 $w$ = 0.6입니다.

메모리와 CPU 사이클이 값비싼 시스템 리소스라는 사실을 고려하여, 우리는 메모리 활용도와 처리량 모두의 균형잡힌 최적화를 위해서 위와 같은 공식을 채택했습니다. 이상적으로는, 성능 지수는 $P = w + (1-w) = 1$ 또는 100%에 도달할 것입니다. 각 메트릭은 성능 지수에 최대 $w$와 $1 - w$만큼 기여하므로, 당신은 메모리 활용도와 처리량 중 하나만 극단적으로 최적화해서는 안 됩니다. 좋은 점수를 받기 위해서는 메모리 활용도와 처리량 사이의 밸런스를 맞춰야 할 겁니다.

• 스타일 (10점)
  • 당신의 코드는 함수로 잘 나눠져야 하며, 전역변수는 가능한 최소로 사용하여야 합니다.
  • 당신의 코드는 설명이 적힌 header 코멘트로 시작해야 합니다. header 코멘트는 가용하거나 할당된 블록들의 구조, 가용 리스트의 조직, 그리고 할당기가 어떻게 가용 리스트를 조작하는지에 대한 설명을 담으면 됩니다. 각 함수가 어떤 기능을 하는지 함수 앞쪽에 header 코멘트를 달아 놓으세요.
  • 각 서브루틴은 무엇을 하고 어떻게 동작하는지에 대한 설명을 담은 header 코멘트를 포함해야 합니다.
  • 당신의 heap 일관성 검사기인 mm_check는 철저하게 잘 문서화되어 있어야 합니다.

좋은 heap 일관성 검사기에 5점, 좋은 프로그램 구조와 코멘트에 5점이 부여됩니다.

 

10. 제출 지침 (생략)

 

 

11. 힌트

• mdriver -f 옵션을 사용하세요. 초기 개발 단계에서, 작은 trace file을 사용하는 것은 디버깅과 테스팅을 단순하게 만들 것입니다. 이와 같은 작은 trace files 두 개를 (short1,2-bal.rep) 포함해두었으니 초기 디버깅 단계에 사용하세요.
• mdriver -v 와 -V 옵션을 사용하세요. -v 옵션은 각 trace file에 대한 자세한 요약을 제공합니다. -V 옵션도 각 trace file이 읽힐 때마다 상세한 요약을 표시해주므로, 에러를 분리해내는데에 도움이 될 겁니다.
• gcc -g로 컴파일하고 디버거를 사용하세요. 디버거는 당신이 범위를 벗어난 메모리 참조(out of bounds memory references)를 분리해서 찾아내는 데 도움이 됩니다.
• 교재의 모든 malloc 구현에 관한 내용을 읽고 이해하세요. 교재는 묵시적(implicit) 가용 리스트에 기반한 간단한 할당기에 대한 상세한 예시를 제공합니다. 교재를 읽고 이해하는 것을 시작점으로 잡으세요. 이 간단한 '묵시적 리스트 할당기'에 대해 완벽하게 이해하기 전까지는 할당기 작업을 시작하지 마세요.
• 포인터 연산을 C 전처리 매크로로 캡슐화하세요. 필요한 모든 캐스팅들 때문에 메모리 관리자에서의 포인터 연산은 복잡하고 에러가 발생하기 쉽습니다. 포인터 작업에 매크로를 쓰면 복잡도를 크게 줄일 수 있습니다. 예시는 교재를 참고하세요.
• 단계적으로 구현하세요. 9개의 첫 trace들은 malloc과 free 구현을 요구합니다. 마지막 2개의 trace들은 realloc, malloc, free를 요구합니다. 먼저 첫 9개 trace들에서 정확하고 효율적인 malloc, free 루틴이 동작하게끔 하는 걸 추천합니다. 그 이후에 realloc 구현을 신경쓰세요. 초심자들은 malloc과 free 구현을 완료하고 그 위에 realloc을 빌드하세요. 하지만 나중에 정말 좋은 성능을 위해서는 realloc을 단독으로 빌드해야 할 겁니다.
• profiler를 사용하세요. 성능을 최적화하는데에 gprof 도구가 도움이 될 것입니다.
• 최대한 빨리 시작하세요! 당신은 몇 페이지의 코드만으로도 효율적인 malloc 패키지를 작성할 수 있을 겁니다. 하지만 동시에 이 코드는 여러분이 지금까지 작성한 코드들 중에 가장 어렵고 복잡한 코드 중 하나일 거에요. 그러니까 얼른 시작하시고, 행운을 빕니다!