[Week6] malloc lab explicit 전용 영역

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

크기별 전용 영역 테스트 케이스 7, 8번은 아래 이미지와 같다. 작은 크기(64)와 큰 크기(448)을 반복적으로 할당한 뒤, 큰 크기를 모두 free한다. 그리고 큰 크기(448)에 할당되지 않는 조금 더 큰 크기(512)를 요청한다. 이렇게 하면 작은 크기(64)때문에 모든 큰 크기(448)을 사용할 수가 없게 되어 단편화가 매우 심하게 일어난다. 이것을 개선하기위해 전용 영역을 구현하였다. 핵심 아이디어는 같은 크기의 작은 free블록들을 한 곳에 몰아넣는 것이다. 그리고 그 크기를 변경하지 않고 오직 그 크기만을 위한 블록으로 사용한다. 설계 확장 malloc 요청 크기가 1024 이하인 경우 크기(ex. 64)를 small bin에서 검색한다. 검색한 head가 null 이면 힙을 요청크기 * n개만큼 확장해서 첫 번째 블록을 할당한다. 전용영역은 헤더와 푸터를 가지고 있다. 전용블록인지 아닌지를 저장한다. 하위 2번째 비트로 판단한다. 사용하고 남는 n - 1개는 classify 로 분류한다. static void *extend_heap(size_t words) { char *block_pointer; // 새 free 블록의 첫 주소를 가리키는 포인터 size_t size; // 블록의 사이즈 size = (words % 2) ? (words + 1) * WSIZE : words * WSIZE; // size를 짝수로 → 8바이트 정렬 size_t small_size = size; // small 전용 영역 만들기 if (size <= MAX_SMALL_BIN) { size = size * EXCLUSIVE; } // mem_sbrk는 확장하기 전 힙의 끝 주소를 반환한다. if ((long)(block_pointer = mem_sbrk(size)) == -1) return NULL; // 힙 확장 실패시 NULL write_end_of_heap_block(block_pointer, size); // 포인터 초기화 PUT_PTR(PREV_FREE_PTR(block_pointer), NULL); PUT_PTR(NEXT_FREE_PTR(block_pointer), NULL); if (small_size <= MAX_SMALL_BIN) { PUT(HDRP(block_pointer), EX_PACK(small_size, 1, 1)); // 전용 블록의 헤더 작성 PUT(FTRP(block_pointer), EX_PACK(small_size, 1, 1)); // 전용 블록의 푸터 작성 char *cur = block_pointer + small_size; for (int i = 2; i <= EXCLUSIVE; i++) { PUT(HDRP(cur), EX_PACK(small_size, 1, 0)); // 전용 블록의 헤더 작성 PUT(FTRP(cur), EX_PACK(small_size, 1, 0)); // 전용 블록의 푸터 작성 classify_block(cur, small_size); cur += small_size; } return block_pointer; // small 전용 } return coalesce(block_pointer); } 분할 하지 않는다. 병합 하지 않는다. free 일단 small bin에 넣어둔다. void mm_free(void *bp) { size_t size = GET_SIZE(HDRP(bp)); size_t is_exclusive = IS_EX(HDRP(bp)); if(is_exclusive) is_exclusive = 1; else is_exclusive = 0; PUT(HDRP(bp), EX_PACK(size, is_exclusive, 0)); PUT(FTRP(bp), EX_PACK(size, is_exclusive, 0)); // unsoretd bin에 넣기 if(!IS_EX(HDRP(bp))) { char *merged = coalesce(bp); char *unsorted_head = arena.unsorted_bin; insert_head(unsorted_head, merged); arena.unsorted_bin = merged; } else { classify_block(bp, GET_SIZE(HDRP(bp))); } } --- ### realloc 1. 전용 공간에 따라 병합 여부를 결정한다. (조건만 변경) 1. 전용 공간이면 합치지 않고 분할하지도 않는다. ```c void *mm_realloc(void *ptr, size_t size) { ... // 블록을 병합해야할 경우 size_t prev_alloc = GET_ALLOC(FTRP(PREV_BLKP(ptr))); // 이전 빈 블록 할당 플래그 size_t next_alloc = GET_ALLOC(HDRP(NEXT_BLKP(ptr))); // 다음 빈 블록 할당 플래그 size_t is_exclusive = IS_EX(HDRP(ptr)); size_t is_prev_exclusive = IS_EX(FTRP(PREV_BLKP(ptr))); size_t is_next_exclusive = IS_EX(HDRP(NEXT_BLKP(ptr))); size_t prev_block_size = GET_SIZE(HDRP(PREV_BLKP(ptr))); size_t next_block_size = GET_SIZE(HDRP(NEXT_BLKP(ptr))); if (!is_exclusive) // 현재블록이 전용블록이 아니어야함. { if (prev_alloc && next_alloc) { } else if ((prev_alloc || is_prev_exclusive) && !next_alloc && !is_next_exclusive) { // 1. 제자리, 오른쪽 블록 병합 ... } else if (!prev_alloc && !is_prev_exclusive && (next_alloc || is_next_exclusive)) { // 2. 블록을 왼쪽으로 옮겨야 할 경우 // 2 - 1. 왼쪽이 비어있는데 병합하면 공간이 충분한 경우 } } else if (!prev_alloc && !next_alloc && !is_prev_exclusive && !is_next_exclusive) { // 2 - 1 - 3. 왼쪽과 오른쪽이 비어있는데 병합하면 공간이 충분한 경우 } } } // asize 이상 크기의 free block을 찾고 할당해야하는 경우 if ((newptr = find_fit(asize)) != NULL) { // 완전히 다른곳으로 이동 // 3 - 1. 적절한 블록이 있는지 탐색후 위치 옮기기 // 3 - 2. 적절한 블록이 없으면 확장 후 할당(malloc) } // 블록을 확장해야할 경우 // 1. 왼쪽은 할당, 요청받은 블록이 힙 끝이면 그대로 확장만 if ((prev_alloc || is_prev_exclusive) && next_alloc && next_block_size == 0) { } // 2. 왼쪽 병합했는데 공간이 부족, 그런데 힙의 끝이어서 제자리 확장이 가능한 경우 if (!prev_alloc && !is_prev_exclusive && (old_size + prev_block_size < asize) && next_alloc && next_block_size == 0) { // mem_sbrk는 확장하기 전 힙의 끝 주소를 반환한다. // 필요한 payload만큼 요청 } // 3. 제자리, 오른쪽 블록 병합 해도 부족한데, 힙 끝인 경우 확장 if ((prev_alloc || is_prev_exclusive) && (!next_alloc || !is_next_exclusive) && old_size + next_block_size < asize && GET_SIZE(HDRP(NEXT_BLKP(NEXT_BLKP(oldptr)))) == 0) { // mem_sbrk는 확장하기 전 힙의 끝 주소를 반환한다. // 필요한 payload만큼 요청 } // 적절한 블록이 없어서 힙을 확장해야하는 경우 } 결과 Results for mm malloc: trace valid util ops secs Kops 0 yes 99% 5694 0.002349 2424 1 yes 99% 5848 0.002057 2843 2 yes 99% 6648 0.003098 2146 3 yes 99% 5380 0.002304 2335 4 yes 100% 14400 0.005293 2720 5 yes 96% 4800 0.004807 999 6 yes 94% 4800 0.002095 2292 7 yes 55% 12000 0.024931 481 8 yes 51% 24000 0.076473 314 9 yes 96% 14401 0.002309 6238 10 yes 87% 14401 0.000382 37669 Total 89% 112372 0.126099 891 Perf index = 53 (util) + 40 (thru) = 93/100 캬 4점 신기록 추가 free 전용 영역 내부가 전부 free일 경우 small bin에서 내부를 전부 해제하고 large bin으로 분류한다. 이를위해 하위 3비트중 세번째 비트를 가장 처음인지의 여부로 본다. void mm_free(void *bp) { size_t size = GET_SIZE(HDRP(bp)); size_t is_exclusive = IS_EX(HDRP(bp)); if(is_exclusive) is_exclusive = 1; else is_exclusive = 0; size_t is_first = IS_FIRST(HDRP(bp)); if(is_first) is_first = 1; else is_first = 0; PUT(HDRP(bp), EX_PACK(size, is_first, is_exclusive, 0)); PUT(FTRP(bp), EX_PACK(size, is_first, is_exclusive, 0)); // 전용 블록이 아니면 unsoretd bin에 넣기 if(!is_exclusive) { char *merged = coalesce(bp); char *unsorted_head = arena.unsorted_bin; insert_head(unsorted_head, merged); arena.unsorted_bin = merged; return; } // 전용 블록이라면 첫번째 전용 블록까지 탐색 char *first_ex = bp; while(!IS_FIRST(HDRP(first_ex))) { first_ex = PREV_BLKP(first_ex); } char *cur = first_ex; size_t small_size = GET_SIZE(HDRP(bp)); for (int i = 0; i < EXCLUSIVE; i++) { // 중간에 하나라도 할당되어있으면 그냥 분류시킴 if (GET_ALLOC(HDRP(cur))) { classify_block(bp, small_size); return; } cur = NEXT_BLKP(cur); } // 한 영역이 전부 free 상태이므로 일반 블록으로 병합하고 분류한다. cur = first_ex; for (int i = 0; i < EXCLUSIVE; i++) { if(bp != cur) del_from_bin(cur, small_size); cur = NEXT_BLKP(cur); } // 일반 블록으로 만들고 분류 size_t large_size = small_size * EXCLUSIVE; // 포인터 초기화 PUT_PTR(PREV_FREE_PTR(first_ex), NULL); PUT_PTR(NEXT_FREE_PTR(first_ex), NULL); // 일반 블록 PUT(HDRP(first_ex), EX_PACK(large_size, 0, 0, 0)); PUT(FTRP(first_ex), EX_PACK(large_size, 0, 0, 0)); classify_block(first_ex, large_size); } 여기에 exclusive 개수를 5로 낮췄다. 결과 Results for mm malloc: trace valid util ops secs Kops 0 yes 99% 5694 0.002531 2249 1 yes 99% 5848 0.003479 1681 2 yes 99% 6648 0.002110 3151 3 yes 100% 5380 0.002296 2343 4 yes 100% 14400 0.005215 2761 5 yes 96% 4800 0.004710 1019 6 yes 94% 4800 0.003256 1474 7 yes 91% 12000 0.003394 3535 8 yes 84% 24000 0.006025 3984 9 yes 56% 14401 0.006282 2292 10 yes 87% 14401 0.000398 36147 Total 91% 112372 0.039696 2831 Perf index = 55 (util) + 40 (thru) = 95/100 +2!!!! 개선 그런데 이 전용 영역을 합쳐서 바로 free해버리면 오히려 realloc 효율이 떨어져버린다. 아마도 작은 영역들을 원래 사용하고 있었는데 큰 블록으로 합쳐버리면서 나중에 잘라 사용하고 단편화가 생기는 것으로 보인다. 그래서 한 영역이 전부 free되더라도 합치는건 그 전용 크기가 몇개 있는지 탐색하고 충분하다면 큰 블록으로 합치고, 충분하지 않으면 그대로 전용 블록으로 사용하도록한다. void mm_free(void *bp) { // 전용 블록이 아니면 unsoretd bin에 넣기 // 전용 블록이라면 첫번째 전용 블록까지 탐색 // 중간에 하나라도 할당되어있으면 그냥 분류시킴 // 전용 블록의 개수가 별로 없으면 합치지 말고 분류 if (small_block_count(small_size) < MAX_SMALL_BLOCK) { classify_block(bp, small_size); return; } // 한 영역이 전부 free 상태이므로 일반 블록으로 병합하고 분류한다. // 일반 블록으로 만들고 분류 //classify_block(first_ex, large_size); char *merged = coalesce(first_ex); classify_block(merged, GET_SIZE(HDRP(merged))); } static size_t small_block_count(size_t asize) { // small bin에서 블록 개수 size_t s_i = (size_t)(asize / SMALL_BIN_UNIT); if (arena.small_bin[s_i] == NULL) return 0; size_t count = 0; char *cur = arena.small_bin[s_i]; while (cur != NULL) { cur = GET_PTR(NEXT_FREE_PTR(cur)); count++; } return count; } 이렇게 하고 분류하기전 병합까지 시킨다. 결과 Results for mm malloc: trace valid util ops secs Kops 0 yes 99% 5694 0.003507 1624 1 yes 99% 5848 0.001488 3931 2 yes 99% 6648 0.001315 5057 3 yes 100% 5380 0.001785 3013 4 yes 100% 14400 0.005394 2669 5 yes 96% 4800 0.004860 988 6 yes 94% 4800 0.004648 1033 7 yes 91% 12000 0.003064 3917 8 yes 84% 24000 0.005492 4370 9 yes 98% 14401 0.002685 5363 10 yes 87% 14401 0.000498 28918 Total 95% 112372 0.034735 3235 Perf index = 57 (util) + 40 (thru) = 97/100 2점!! 더 올릴게 있을까여기서 realloc 전용 영역 옮기기 void *mm_realloc(void *ptr, size_t size) { ... // 요청한 크기보다 이미 가지고 있는 크기가 더 크면 분할 후 리턴 if (old_size >= asize) { // 전용 영역인 경우 크기에 맞는 전용 영역 찾기 if (IS_EX(HDRP(oldptr))) { // asize 이상 크기의 free block을 찾고 할당 if ((newptr = find_fit(asize)) != NULL) { place(newptr, asize); return newptr; } // free block을 못찾았을 때 힙을 늘림 //extendsize = MAX(asize, CHUNKSIZE); size_t extendsize = asize; if ((newptr = extend_heap(extendsize / WSIZE)) == NULL) return NULL; place(newptr, asize); return newptr; } // 일반영역인경우 분할 후 리턴 place(oldptr, asize); return oldptr; } ... 결과 Results for mm malloc: trace valid util ops secs Kops 0 yes 99% 5694 0.001880 3028 1 yes 99% 5848 0.002285 2559 2 yes 99% 6648 0.002234 2976 3 yes 100% 5380 0.002316 2323 4 yes 100% 14400 0.003104 4640 5 yes 96% 4800 0.003880 1237 6 yes 94% 4800 0.004627 1037 7 yes 91% 12000 0.003455 3474 8 yes 84% 24000 0.005192 4623 9 yes 98% 14401 0.002605 5528 10 yes 87% 14401 0.000438 32902 Total 95% 112372 0.032014 3510 Perf index = 57 (util) + 40 (thru) = 97/100 시간 줄어듬 (?)