크래프톤 정글 6주차 과제로 C 프로그램을 위한 동적할당을 구현하도록 하는 과제가 주어졌다.
메모리 할당 기법에는 First-Fit, Next-Fit, Best-Fit, Worst-fit 등이 있고,
free list 할당 기법에는 Implicit Free List, Explicit Free List, Segregate Free List 이렇게 세 가지로 분류할 수 있다.
그 중에서 나는 Explicit Free List방법으로 Free List를 관리해 주었고, Worst-Fit으로 메모리 공간을 찾아주는 방식으로 구현을 진행했다.
Explicit Free List
Explicit Free List에서는 사용 가능한 메모리 블록들의 목록을 연결시켜 할당 요청이 들어올 때마다 이 목록에서 적절한 크기의 메모리 블록을 찾아 할당한다. 또, 메모리 해제 작업이 수행될 때 해당 메모리 블록을 다시 사용 가능한 목록에 추가한다.
Worst-Fit
Worst-fit은 메모리 할당 기법 중 하나로, 가장 큰 적재 가능한 메모리 공간을 찾아서 그 공간에 프로세스를 할당하는 방법이다.
Explicit Free List과 Worst-Fit을 사용한 이유
Explicit Free List는 메모리의 heap공간 전체를 탐색할 필요 없이 free공간만 확인하여 시간적으로 이득을 볼 수 있겠다고 생각을 했고, Worst-fit을 사용한다면 free공간들을 내림차순으로 정렬해준다면 삭제할 때 free list의 맨 처음부분만 보면 되기 때문에 O(1). 즉, 상수시간안에 삭제를 할 수 있다는 장점이 있다.
매크로 상수
상수 매크로는 코드 안에서 여러번 일어나는 연산의 가독성을 높여주기 위해 선언하였다.
#define WSIZE 4 // word size #define DSIZE 8 // double word size #define CHUNKSIZE (1 << 12) // 힙 확장을 위한 기본 크기 (= 초기 빈 블록의 크기) #define MAX(x, y) (x > y ? x : y) // /* 가용 리스트를 접근/순회하는 데 사용할 매크로 */ #define PACK(size, alloc) (size | alloc) // size와 할당 비트를 결합, header와 footer에 저장할 값 #define GET(p) (*(unsigned int *)(p)) // p가 참조하는 워드 반환 #define PUT(p, val) (*(unsigned int *)(p) = (unsigned int)(val)) // p에 val 저장 #define GET_SIZE(p) (GET(p) & ~0x7) // 사이즈 #define GET_ALLOC(p) (GET(p) & 0x1) // 할당 상태 #define HDRP(bp) ((char *)(bp)-WSIZE) // Header 포인터 #define FTRP(bp) ((char *)(bp) + GET_SIZE(HDRP(bp)) - DSIZE) // Footer 포인터 #define NEXT_BLKP(bp) ((char *)(bp) + GET_SIZE(((char *)(bp)-WSIZE))) // 다음 블록의 포인터 #define PREV_BLKP(bp) ((char *)(bp)-GET_SIZE(((char *)(bp)-DSIZE))) // 이전 블록의 포인터 // #define GET_SUCC(bp) (*(void **)((char *)(bp) + WSIZE)) // 다음 가용 블록의 주소 #define GET_PRED(bp) (*(void **)(bp)) // 이전 가용 블록의 주소
힙 초기화 함수
explicit free list를 구현하기위해 각 블록에 필수로 들어가야하는 헤더, 푸터, 다음 가용블록 주소, 이전 가용블록 주소를 넣어주었고 힙의 시작을 알리는 프롤로그와 힙의 끝을 알려주는 에필로그를 초기화 함수에서 넣어주었다.
int mm_init(void) { // 초기 힙 생성 if ((free_listp = mem_sbrk(8 * WSIZE)) == (void *)-1) // 8워드 크기의 힙 생성, free_listp에 힙의 시작 주소값 할당(가용 블록만 추적) return -1; PUT(free_listp, 0); // 정렬 패딩 PUT(free_listp + (1 * WSIZE), PACK(2 * WSIZE, 1)); // 프롤로그 Header PUT(free_listp + (2 * WSIZE), PACK(2 * WSIZE, 1)); // 프롤로그 Footer PUT(free_listp + (3 * WSIZE), PACK(4 * WSIZE, 0)); // 첫 가용 블록의 헤더 PUT(free_listp + (4 * WSIZE), NULL); // 이전 가용 블록의 주소 PUT(free_listp + (5 * WSIZE), NULL); // 다음 가용 블록의 주소 PUT(free_listp + (6 * WSIZE), PACK(4 * WSIZE, 0)); // 첫 가용 블록의 푸터 PUT(free_listp + (7 * WSIZE), PACK(0, 1)); // 에필로그 Header: 프로그램이 할당한 마지막 블록의 뒤에 위치하며, 블록이 할당되지 않은 상태를 나타냄 // free_listp += (4 * WSIZE); // 첫번째 가용 블록의 bp // // 힙을 CHUNKSIZE bytes로 확장 if (extend_heap(CHUNKSIZE / WSIZE) == NULL) return -1; // return 0; }
힙 크기 늘리기 함수
힙의 크기를 매개변수만큼 늘려주는 함수이다. 매개변수의 2의 배수로 늘려주고 mem_sbrk()함수로 늘려준 뒤에는 늘려주기 전에 힙 마지막 부분이 free상태라면 그 블록과 병합해주고 리턴해 주었다.
static void *extend_heap(size_t words) { char *bp; // 더블 워드 정렬 유지 // size: 확장할 크기 size_t size = (words % 2) ? (words + 1) * WSIZE : words * WSIZE; // 2워드의 가장 가까운 배수로 반올림 (홀수면 1 더해서 곱함) // if ((long)(bp = mem_sbrk(size)) == -1) // 힙 확장 return NULL; // PUT(HDRP(bp), PACK(size, 0)); // 새 빈 블록 헤더 초기화 PUT(FTRP(bp), PACK(size, 0)); // 새 빈 블록 푸터 초기화 PUT(HDRP(NEXT_BLKP(bp)), PACK(0, 1)); // 에필로그 블록 헤더 초기화 // return coalesce(bp); // 병합한뒤 리턴 블록 포인터 반환 }
free공간 합치는 함수
전에 블록이 free상태라면 블록포인터를 전 블럭으로 이동시켜주고 다음블록과 크기를 합쳐준다.
다음 블록이 free상태라면 다음블록과 크기를 합쳐준다.
이렇게 두 가지 조건문으로 다음 네 가지 경우를 모두 충족시켜줄 수 있다.
1. 이전블록과 다음블록이 모두 할당된 경우
2. 다음블록만 할당된 경우
3. 이전블록만 할당된 경우
4. 이전블록과 다음블록이 모두 free공간인 경우
static void *coalesce(void *bp) { size_t prev_alloc = GET_ALLOC(FTRP(PREV_BLKP(bp))); // 이전 블록 할당 상태 size_t next_alloc = GET_ALLOC(HDRP(NEXT_BLKP(bp))); // 다음 블록 할당 상태 size_t size = GET_SIZE(HDRP(bp)); // 현재 블록 사이즈 // //모두 할당된 경우 마지막에 bp를 free list에 추가해주고 리턴만 해주면 됨 if (!prev_alloc) { // 이전 블록이 빈 경우 splice_free_block(PREV_BLKP(bp)); // 이전 가용 블록을 free_list에서 제거 bp = PREV_BLKP(bp); size += GET_SIZE(HDRP(bp)); PUT(HDRP(bp), PACK(size, 0)); PUT(FTRP(bp), PACK(size, 0)); } // if (!next_alloc) { // 다음 블록이 빈 경우 splice_free_block(NEXT_BLKP(bp)); // 다음 가용 블록을 free_list에서 제거 size += GET_SIZE(HDRP(NEXT_BLKP(bp))); PUT(HDRP(bp), PACK(size, 0)); PUT(FTRP(bp), PACK(size, 0)); } // add_free_block(bp); return bp; }
free list에서 해당 블록을 제거하는 함수
해제하려는 블록의 이전 블록의 다음블록을 / 해제하려는 블록의 다음 블록으로 / 설정해 주고
해제하려는 블록의 다음 블록의 이전블록을 / 해제하려는 블록의 이전 블록으로 / 설정해 주는 함수이다.static void splice_free_block(void *bp) { if (bp == free_listp) // 분리하려는 블록이 free_list 맨 앞에 있는 블록이면 (이전 블록이 없음) { free_listp = GET_SUCC(free_listp); // 다음 블록을 루트로 변경 return; } // 이전 블록의 SUCC을 다음 가용 블록으로 연결 GET_SUCC(GET_PRED(bp)) = GET_SUCC(bp); // 다음 블록의 PRED를 이전 블록으로 변경 if (GET_SUCC(bp) != NULL) // 다음 가용 블록이 있을 경우만 GET_PRED(GET_SUCC(bp)) = GET_PRED(bp); }
free list에 메모리해제된 공간을 추가하는 함수
내림차순으로 free list를 관리해 주기 위해 반복문으로 자신보다 작은 크기의 free공간을 만나면 해당 위치에 free블록을 삽입해 주는 함수이다.
시간복잡도 : O(n)static void add_free_block(void *bp) { // 가용 리스트가 비어있는 경우 if (free_listp == NULL) { GET_SUCC(bp) = NULL; GET_PRED(bp) = NULL; free_listp = bp; return; } // void *temp = free_listp; void *prev = NULL; // // 적절한 위치를 찾아서 블록을 추가 while (temp != NULL && GET_SIZE(HDRP(temp)) > GET_SIZE(HDRP(bp))) { prev = temp; temp = GET_SUCC(temp); } // // 새로운 블록을 적절한 위치에 추가 if (prev == NULL) { // 첫 번째 위치에 추가하는 경우 GET_PRED(bp) = NULL; GET_SUCC(bp) = free_listp; GET_PRED(free_listp) = bp; free_listp = bp; } else { // 중간이나 마지막 위치에 추가하는 경우 GET_SUCC(bp) = temp; GET_PRED(bp) = prev; GET_SUCC(prev) = bp; if (temp != NULL) // 마지막 위치에 추가하는 경우가 아닌 경우에만 GET_PRED(temp) = bp; } }
메모리 할당 함수
이 코드에서는 더블워드 규칙을 사용한다. 더블워드 규칙을 사용하는 이유는 메모리상에서 8바이트가 정렬되어 있기 때문에 캐시 메모리에 접근할 때 보다 더 효율적으로 접근하기 때문에 더블워드 규칙을 사용하였다.
따라서 mm_malloc()함수에서 할당할 때 8바이트의 배수만큼 할당할 크기를 정해준다.
그리고 find_fit()함수로 free list에서 알맞은 공간을 찾아주고 해당 공간은 Worst-Fit으로 찾았기 때문에 찾은 메모리 공간이 클 확률이 높다. 따라서 필수적으로 place함수로 메모리를 가공해줘야한다.void *mm_malloc(size_t size) { size_t asize; // 조정된 블록 사이즈 size_t extendsize; // 확장할 사이즈 char *bp; // 잘못된 요청 분기 if (size == 0) return NULL; // if (size <= DSIZE) // 8바이트 이하이면 asize = 2 * DSIZE; // 최소 블록 크기 16바이트 할당 (헤더 4 + 푸터 4 + 저장공간 8) else asize = DSIZE * ((size + DSIZE + DSIZE - 1) / DSIZE); // 8배수로 올림 처리 // if ((bp = find_fit(asize)) != NULL) // 가용 블록 검색 { place(bp, asize); // 할당 return bp; // 새로 할당된 블록의 포인터 리턴 } // 적합한 블록이 없을 경우 힙확장 extendsize = MAX(asize, CHUNKSIZE); if ((bp = extend_heap(extendsize / WSIZE)) == NULL) return NULL; place(bp, asize); return bp; }
메모리 할당 공간 찾는 함수
Worst-fit 방식이기 때문에 가용리스트의 맨 앞에는 제일 큰 메모리공간이 오게된다. 따라서 가용리스트 헤더부분만 봐주고 그곳에 없다면 뒤에도 없기때문에 NULL을 리턴해주면 된다.
static void *find_fit(size_t asize) { void *bp = free_listp; if(bp == NULL)// 다음 가용 블럭이 없으면 NULL반환 return NULL; // if ((asize <= GET_SIZE(HDRP(bp)))) // 적합한 사이즈의 블록을 찾으면 반환 return bp; // return NULL; //적합한 사이즈 없으면 NULL반환 }
할당 할 블록을 가공해주는 함수
일단 free블록을 리스트에서 제거해준 뒤 빈공간이 16보다 크다면 빈공간과 할당된 부분을 나눠준다.
16으로 설정한 이유는 빈블록에 헤더, 푸터, 가용리스트 앞 부분 가리키는 포인터, 뒷부분을 가리키는 포인터, 이렇게 네 개의 공간이 있어야 하기때문에 최소 16으로 설정해 주었다.
만약 공간이 16보다 작다면 네 개의 공간을 할당할 수 없으므로 공간을 전부 할당해주면 된다.static void place(void *bp, size_t asize) { splice_free_block(bp); // free_list에서 해당 블록 제거 // size_t csize = GET_SIZE(HDRP(bp)); // 현재 블록의 크기 // if ((csize - asize) >= (2 * DSIZE)) { // 차이가 최소 블록 크기 16보다 같거나 크면 분할 PUT(HDRP(bp), PACK(asize, 1)); // 현재 블록에는 필요한 만큼만 할당 PUT(FTRP(bp), PACK(asize, 1)); // PUT(HDRP(NEXT_BLKP(bp)), PACK((csize - asize), 0)); // 남은 크기를 다음 블록에 할당(가용 블록) PUT(FTRP(NEXT_BLKP(bp)), PACK((csize - asize), 0)); add_free_block(NEXT_BLKP(bp)); // 남은 블록을 free_list에 추가 }else { PUT(HDRP(bp), PACK(csize, 1)); // 해당 블록 전부 사용 PUT(FTRP(bp), PACK(csize, 1)); } }
메모리 해제 함수
헤더와 푸터에 해제되었다고 알려준 뒤 앞 또는 뒷공간과 합쳐주고 가용리스트에 추가해준다.
( 가용리스트에 넣어주는 부분은 coalesce()함수 안에 정의되어있음 )void mm_free(void *bp) { size_t size = GET_SIZE(HDRP(bp)); PUT(HDRP(bp), PACK(size, 0)); PUT(FTRP(bp), PACK(size, 0)); //해제 coalesce(bp); //해제후 합침 }
메모리 재할당 함수
기존에 할당된 메모리 블록의 크기 변경해주고 매개변수는
기존 메모리 블록의 포인터,새로운 크기를 받으면 된다.
만약 첫번째 매개변수가 NULL이라면 메모리를 할당해주고, 두 번째 매개변수가 0일 경우 해당 메모리를 free()해준다.void *mm_realloc(void *ptr, size_t size) { if (ptr == NULL) // 포인터가 NULL인 경우 할당만 수행 { return mm_malloc(size); } if (size <= 0) // size가 0인 경우 메모리 반환만 수행 { mm_free(ptr); return 0; } // void *newptr = mm_malloc(size); // 새로 할당한 블록의 포인터 if (newptr == NULL) return NULL; // 할당 실패 // size_t copySize = GET_SIZE(HDRP(ptr)) - DSIZE; // payload만큼 복사 if (size < copySize) // 기존 사이즈가 새 크기보다 더 크면 copySize = size; // size로 크기 변경 (기존 메모리 블록보다 작은 크기에 할당하면, 일부 데이터만 복사) // memcpy(newptr, ptr, copySize); // 새 블록으로 데이터 복사 mm_free(ptr); // 기존 블록 해제 return newptr; }
점수
기술적 챌린지 (구현못함)
Worst-Fit에서 삽입할 때는 내림차순으로 정렬해줘야 하기 때문에 자기 자리를 찾는시간. 즉, O(n)만큼 걸린다는 단점이 있다. 이 단점을 최대힙을 사용하여 보완하려했다. 왜냐하면 내림차순으로 정렬할 필요 없이 제일 큰 free공간이 free list의 맨 처음에만 와주면 되기 때문이다.
free list에 13크기의 메모리 삽입 예시
편의상 각 메모리 블록을 트리식으로 표현하겠다.
삽입 할 때 먼저 루트와 비교를 하고 삽입하려는 메모리공간의 크기가 더 작다면 루트의 자식중에 메모리 크기가 큰 기준으로 큰 노드로 가준다.
마찬가지로 더 큰자식노드로 이동해 준다.
자신보다 작은 노드를 만났다면, 두 자리를 swap해준다.
자식이 한명이거나 리프노드까지 내려갔다면 NULL 자리에 블록을 추가해준다.
swap하는 과정에서 원래 연결되어있는 노드의 자식을 가리키게 해주는것 까지 문제가 없지만 넣을 위치의 부모가 새로 넣을 노드를 가리키게 해야한다. 그러므로 부모노드를 가리키는 포인터 한 개, 왼쪽 자식을 가리키는 포인터 한 개, 오른쪽 자식을 가리키는 포인터 한 개, 총 세 개의 포인터를 저장할 공간이 필요하지만 위 코드에선 앞 free공간, 뒤쪽 free공간으로 두 개의 포인터를 저장할 수 있는 공간만 주어졌다.
부모에서 자식으로 이어줄 수 있는 방법은 두 가지로 볼 수 있다.
1. 부모노드를 가리키는 포인터를 구조에 추가를 해 준다.
2. 부모노드에서 미리 아래 노드를 비교해 준다.
이 문제는 삭제에서도 마찬가지일 것이다.
지금으로써는 시간부족으로 구현하지 못했지만 정글 과정이 끝나고 꼭 해보고싶다.
