1. 소개

   이 실습에서는 C 프로그램을 위한 동적 저장소 할당기를 작성하게 됩니다. 즉, malloc, free,

   그리고 realloc 루틴의 자신의 버전을 구현할 것입니다. 창의적으로 설계 공간을 탐색하고,

   정확하고 효율적이며 빠른 할당기를 구현해 보십시오.

2. 물류

   최대 두 명이 한 팀으로 작업할 수 있습니다. 과제에 대한 명확한 설명과 수정 사항은 강의 웹 페이지에 게시됩니다.

3. 자료 배포 지침

   사이트 별로: 여기에서 학생들이 malloclab-handout.tar 파일을 다운로드하는 방법을 설명하는 단락을 삽입하십시오.

   먼저 malloclab-handout.tar 파일을 작업하려는 보호된 디렉터리로 복사하십시오. 그런 다음 명령어 tar xvf malloclab-handout.tar를 입력합니다. 그러면 여러 파일이 디렉터리로 압축 해제됩니다. 수정하고 제출할 유일한 파일은 mm.c입니다. mdriver.c 프로그램은 솔루션 성능을 평가할 수 있게 해주는 드라이버 프로그램입니다. 명령어 make를 사용하여 드라이버 코드를 생성하고, ./mdriver -V 명령어로 실행하십시오. (-V 플래그는 유용한 요약 정보를 표시합니다.)

   mm.c 파일을 보면 프로그래밍 팀의 1 인 또는 2 인에 대한 식별 정보를 삽입해야 하는 C 구조체 team이 있습니다. 잊지 않도록 바로 이 작업을 수행하십시오.

   실습을 완료한 후에는 솔루션이 포함된 단일 파일(mm.c)만 제출하면 됩니다.

4. 실습 작업 방법

   동적 저장소 할당기는 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` 패키지를 구현합니다. 이를 시작점으로 사용하여 이러한 함수들을 수정하고 (필요하다면 다른 비공개 정적 함수를 정의하여) 다음 의미론을 준수하도록 하십시오.

   • mm_init:

     응용 프로그램(즉, 여러분이 구현을 평가하는 데 사용할 트레이스 기반 드라이버 프로그램)이 mm_malloc, mm_realloc 또는 mm_free를 호출하기 전에 필요한 초기화 작업을 수행하려고 mm_init을 호출합니다. 초기 힙 영역을 할당하는 등의 초기화 작업을 수행합니다. 초기화에 문제가 있으면 -1 을 반환하고, 그렇지 않으면 0 을 반환해야 합니다.

   • mm_malloc:

     mm_malloc 루틴은 최소한 size 바이트의 할당된 블록 페이로드에 대한 포인터를 반환합니다. 전체 할당된 블록은 힙 영역 내에 있어야 하며, 다른 할당된 청크와 겹치지 않아야 합니다. 구현을 표준 C 라이브러리의 malloc 버전과 비교할 것입니다. 표준 라이브러리의 malloc은 항상 8 바이트로 정렬된 페이로드 포인터를 반환하므로, 여러분의 malloc 구현도 8 바이트로 정렬된 포인터를 항상 반환해야 합니다.

   • mm_free:

     mm_free 루틴은 ptr이 가리키는 블록을 해제합니다. 아무것도 반환하지 않습니다. 이 루틴은 전달된 포인터(ptr)가 이전에 mm_malloc 또는 mm_realloc 호출에 의해 반환되었고 아직 해제되지 않은 경우에만 작동이 보장됩니다.

   • mm_realloc: mm_realloc 루틴은 최소한 size 바이트의 할당된 영역에 대한 포인터를반환합니다. 다음 제약 사항이 있습니다:

     • ptr이 NULL 이면, 호출은 mm_malloc(size)와 동일합니다.
     • size가 0 이면, 호출은 mm_free(ptr)와 동일합니다.
     • ptr이 NULL 이 아니면, 이는 이전에 mm_malloc 또는 mm_realloc 호출에 의해 반환된 것임이 보장되어야 합니다. mm_realloc 호출은 ptr이 가리키는 메모리 블록(이전 블록)의 크기를 size 바이트로 변경하고 새 블록의 주소를 반환합니다. 새 블록의 주소는 이전 블록과 동일할 수도 있고, 다를 수도 있습니다. 이는 구현, 이전 블록의 내부 단편화 양, 그리고 realloc 요청의 크기에 따라 달라집니다.
     • 새 블록의 내용은 이전 ptr 블록의 내용과 동일하며, 최소한 이전 크기와 새 크기 중 작은 크기만큼 동일합니다. 그 외의 부분은 초기화되지 않습니다. 예를 들어, 이전 블록이 8 바이트이고 새 블록이 12 바이트라면 새 블록의 처음 8 바이트는 이전 블록의 처음 8 바이트와 동일하고, 나머지 4 바이트는 초기화되지 않습니다. 비슷하게, 이전 블록이 8 바이트이고 새 블록이 4바이트라면 새 블록의 내용은 이전 블록의 처음 4 바이트와 동일합니다.이 의미론은 대응하는 libc의 malloc, realloc, free 루틴의 의미론과 일치합니다. 쉘에서 man malloc을 입력하여 완전한 문서를 확인하십시오

5. 힙 일관성 검사기

   동적 메모리 할당기는 정확하고 효율적으로 프로그래밍하기 매우 까다롭습니다. 특히, 많은 비정형 포인터 조작을 포함하기 때문에 올바르게 프로그래밍하기 어렵습니다. 힙을 스캔하고 일관성을 검사하는 힙 체크 프로그램을 작성하는 것이 매우 도움이 될 것입니다.

   힙 체크 프로그램이 확인할 수 있는 예는 다음과 같습니다:

   • 모든 블록이 자유 목록에서 'free'로 표시되어 있는가?
   • 병합이 되지 않은 인접한 자유 블록이 존재하는가?
   • 모든 자유 블록이 실제로 자유 목록에 있는가?
   • 자유 목록의 포인터가 유효한 자유 블록을 가리키고 있는가?
   • 할당된 블록이 겹치는가?
   • 힙 블록의 포인터가 유효한 힙 주소를 가리키고 있는가?

   힙 체크 프로그램은 mm.c의 int mm_check(void) 함수로 구성됩니다. 이 함수는 합리적이라고 생각되는 불변 조건이나 일관성 조건을 확인할 것입니다. 힙이 일관성이 있을 때만 0이 아닌 값을 반환합니다. 위에 나열된 제안 사항에만 한정되지 않으며, 모든 것을 확인할 필요는 없습니다. mm_check가 실패할 때 오류 메시지를 출력하는 것도 좋습니다.

   이 일관성 검사기는 개발 중 디버깅을 위한 것입니다. mm.c를 제출할 때는 mm_check 호출을 제거해야 합니다. 이는 처리량을 느리게 할 수 있기 때문입니다. mm_check 함수에 스타일 점수가 부여되므로 주석을 추가하고 무엇을 검사하고 있는지 문서화하십시오.

6. 지원 루틴

   memlib.c 패키지는 동적 메모리 할당기를 위한 메모리 시스템을 시뮬레이션합니다. memlib.c에서 다음 함수를 호출할 수 있습니다:

   • void *mem_sbrk(int incr): 힙을 incr 바이트만큼 확장합니다. 여기서 incr은 양의 정수이며, 새로 할당된 힙 영역의 첫 번째 바이트에 대한 제네릭 포인터를 반환합니다. 이 함수는 유닉스 sbrk 함수와 동일한 의미를 가지며, 단 mem_sbrk는 양의 정수 인수만 허용합니다.
   • void *mem_heap_lo(void): 힙의 첫 번째 바이트에 대한 제네릭 포인터를 반환합니다.
   • void *mem_heap_hi(void): 힙의 마지막 바이트에 대한 제네릭 포인터를 반환합니다.
   • size_t mem_heapsize(void): 힙의 현재 크기를 바이트 단위로 반환합니다.
   • size_t mem_pagesize(void): 시스템의 페이지 크기를 바이트 단위로 반환합니다(리눅스 시스템에서는 4K).

7. 트레이스 기반 드라이버 프로그램

   malloclab-handout.tar 배포판의 mdriver.c 드라이버 프로그램은 mm.c 패키지의 올바름, 공간 활용, 처리량을 테스트합니다. 드라이버 프로그램은 malloclab-handout.tar 배포판에 포함된 트레이스 파일 집합으로 제어됩니다. 각 트레이스 파일에는 드라이버가 mm_malloc, mm_realloc, mm_free 루틴을 순서대로 호출하도록 지시하는 할당, 재할당 및 해제 지침이 포함되어 있습니다. 드라이버와 트레이스 파일은 mm.c 파일을 평가할 때 사용할 것과 동일한 것입니다.

   mdriver.c 드라이버는 다음 명령줄 인수를 받습니다:

   • -t <tracedir>: 기본 디렉토리 대신 config.h에 정의된 디렉토리에서 기본 트레이스 파일을 찾습니다.
   • -f <tracefile>: 기본 트레이스 파일 집합 대신 특정 트레이스 파일 하나를 사용하여 테스트합니다.
   • -h: 명령줄 인수에 대한 요약을 출력합니다.
   • -l: 학생의 malloc 패키지 외에 libc malloc도 실행하고 측정합니다.
   • -v: 상세 출력. 각 트레이스 파일에 대한 성능 분석을 간단한 테이블 형식으로 출력합니다.
   • -V: 더욱 상세한 출력. 각 트레이스 파일이 처리될 때 추가 진단 정보를 출력합니다. malloc 패키지가 실패하는 원인을 디버깅할 때 유용합니다.
   1. 프로그래밍 규칙
   • mm.c의 인터페이스는 변경해서는 안 됩니다.
   • 메모리 관리 관련 라이브러리 호출이나 시스템 호출을 사용해서는 안 됩니다. 여기에는 malloc, calloc, free, realloc, sbrk, brk 또는 이들의 변형 호출을 사용하는 것이 포함됩니다.
   • mm.c 프로그램에서 배열, 구조체, 트리, 리스트와 같은 복합 전역 또는 정적 데이터를 정의할 수 없습니다. 그러나 mm.c에서 전역 스칼라 변수(정수, 실수, 포인터)는 선언할 수 있습니다.
   • libc malloc 패키지와 일관성을 유지하기 위해, 여러분의 할당기는 항상 8 바이트 경계로 정렬된 포인터를 반환해야 합니다. 드라이버가 이 요구 사항을 확인할 것입니다.

8. 평가

다음 규칙을 어기거나 코드에 버그가 있어 드라이버가 충돌하면 0 점을 받습니다. 그렇지 않은 경우 점수는 다음과 같이 계산됩니다:

• 정확성 (20 점): 드라이버 프로그램에서 실행되는 정확성 테스트를 통과하면 모든 점수를 받습니다. 각 올바른 트레이스마다 부분 점수를 받습니다.

• 성능 (35 점): 두 가지 성능 지표를 사용하여 솔루션을 평가합니다.

• 메모리 활용률: 드라이버가 사용한 총 메모리 양(즉, mm_malloc 또는 mm_realloc을 통해 할당되었지만 아직 mm_free를 통해 해제되지 않은 메모리)과 할당기가 사용한 힙 크기 사이의 최대 비율. 최적의 비율은 1 입니다. 이 비율을 최적에 가깝게 만들기 위해 단편화를 최소화할 수 있는 좋은 정책을 찾아야 합니다.

• 처리량: 초당 완료된 평균 작업 수.

드라이버 프로그램은 성능 지표 P를 계산하여 할당기의 성능을 요약합니다. P는 메모리활용률과 처리량의 가중 합으로 계산됩니다.

\[

P = wU + (1 − w) \min \left(1, \frac{T}{T_{\text{libc}}}\right)

\]

여기서 U는 메모리 활용률, T는 처리량, **T_{\text{libc}}**는 시스템에서 기본 트레이스에 대한 libc malloc의 예상 처리량입니다. 성능 지수는 메모리 활용률을 처리량보다 더 중시하며, 기본 가중치 w = 0.6입니다.

메모리와 CPU 주기가 모두 비용이 많이 드는 시스템 자원이므로, 우리는 메모리 활용과 처리량 모두의 균형 잡힌 최적화를 장려하기 위해 이 공식을 채택했습니다. 이상적으로는 성능 지수 P가 1 또는 100%에 도달해야 합니다. 각 지표는 성능 지수에 최대 w 및 1 − w 까지 기여하므로, 메모리 활용률이나 처리량 중 어느 하나에만 치중해서 최적화하지 말아야 합니다. 좋은 점수를 받으려면 활용률과 처리량 사이의 균형을 맞춰야 합니다.

• 스타일 (10 점):

• 코드는 함수로 분해되어야 하며, 전역 변수는 최소화해야 합니다.

• 코드에는 할당된 블록과 자유 블록의 구조, 자유 목록의 구성, 할당기가 자유 목록을 어떻게 조작하는지 설명하는 헤더 주석이 있어야 합니다. 각 함수 앞에도 그 함수가 하는 일을 설명하는 헤더 주석이 있어야 합니다.

• 서브루틴에는 그 동작과 방법을 설명하는 헤더 주석이 있어야 합니다.

• 힙 일관성 검사기 mm_check는 철저하고 잘 문서화되어야 합니다. 좋은 힙 일관성 검사기에는 5 점, 프로그램 구조와 주석에 5 점을 부여합니다.

1. 제출 지침

   사이트별로: 학생들이 mm.c 파일을 제출하는 방법을 설명하는 단락을 삽입하십시오.

2. 힌트

• mdriver -f 옵션을 사용하십시오. 초기 개발 단계에서는 작은 트레이스 파일을 사용하면

디버깅과 테스트가 단순해집니다. 초기에 디버깅할 수 있도록 두 개의 작은 트레이스 파일

(short1, 2-bal.rep)이 포함되어 있습니다.

• mdriver -v 및 -V 옵션을 사용하십시오. -v 옵션은 각 트레이스 파일에 대한 자세한

요약을 제공합니다. -V 옵션은 각 트레이스 파일이 읽힐 때도 표시되므로, malloc 패키지가

실패하는 원인을 고립시키는 데 도움이 됩니다.

• gcc -g 로 컴파일하고 디버거를 사용하십시오. 디버거는 메모리 경계 밖 참조를 식별하고

고립시키는 데 도움이 됩니다.

• 교재의 malloc 구현의 모든 줄을 이해하십시오. 교재에는 암묵적인 자유 목록을 기반으로

한 간단한 할당기의 자세한 예제가 있습니다. 이를 출발점으로 삼으십시오. 간단한 암묵적 목록

할당기에 대해 완벽하게 이해하기 전까지는 작업을 시작하지 마십시오.

• 포인터 연산을 C 전처리기 매크로로 캡슐화하십시오. 메모리 관리자에서 포인터 연산은

캐스팅 때문에 혼란스럽고 오류가 발생하기 쉽습니다. 포인터 연산에 대한 매크로를 작성하면

복잡성을 크게 줄일 수 있습니다. 예제는 교재에서 확인하십시오.

• 단계별로 구현하십시오. 첫 번째 9 개의 트레이스는 malloc과 free 요청을 포함하고,

마지막 2 개의 트레이스는 realloc, malloc, free 요청을 포함합니다. 먼저 첫 번째 9 개의

트레이스에서 malloc과 free 루틴을 올바르고 효율적으로 작동하도록 만든 후, realloc

구현에 집중하는 것이 좋습니다. 우선, realloc을 기존 malloc과 free 구현에 기반하여

구축하십시오. 하지만 정말 좋은 성능을 얻으려면 독립적인 realloc을 만들어야 합니다.

• 프로파일러를 사용하십시오. 성능 최적화를 위해 gprof 도구가 유용할 수 있습니다.
• 일찍 시작하십시오! 효율적인 malloc 패키지는 몇 페이지의 코드로 작성할 수 있지만,

지금까지 여러분이 작성한 코드 중 가장 어렵고 복잡할 것입니다. 일찍 시작하고, 행운을 빕니다!