Week 05 ~ 07 : 전산학 프로젝트/SW정글 Week 06 : Malloc Lab 8

[Malloc Lab] 7. 성능 개선을 위한 몇가지 최적화 (3) (Best fit)

3. Explicit free list chain 내림차순 정렬 / 그에 맞는 Best fit find_fit함수 구현 (+2점) 명시적 가용 리스트 chain은 가장 나중에 추가된 원소가 start점에 위치하는, 우선순위 없는 선입후출인 스택의 구조를 갖고 있었다. 속도는 빠르지만 공간 효율에는 그닥 도움을 주지 못해서 속도점수는 높고 메모리 점수는 낮아 한쪽으로 점수가 치우친 상태인데, 빈 블록을 크기순 내림차순으로 정렬함으로써 이 부분을 개선했다. 빈 블록을 보관하는 가용리스트 chain이 크기 내림차순이라면, 가장 큰 블록은 chain의 start에 있을 것이다. 그렇다면 만약 fit을 요구하는 asize가 start보다 크다면 나머지 원소와는 비교하지 않아도 fit이 불가능함을 빠르게 알 수 있..

[Malloc Lab] 6. 성능 개선을 위한 몇가지 최적화 (2)

3. realloc 커스텀 (+5점) 기존의 realloc 함수는 bp의 위치와 기존, 새 size에 관계없이 새로 malloc을 실행 후 데이터를 복사하는 방식이었다. 하지만 realloc하려는 bp의 컨디션에 따라 무의미한 복사를 하지 않고도 재할당이 가능한 경우가 있어 이 경우 예외적으로 malloc을 재실행하지 않는다면, 새로 free되어 생기는 공간활용의 구멍도, malloc 실행에 쓰이는 연산력도 절약할 수 있다. newsize가 oldsize보다 크지만 bp의 다음 블록이 그 차이를 채울만큼 큰 빈 블록인 경우, newsize가 oldsize보다 작아서 제자리에서 재할당이 가능한 경우의 두 케이스에 대해 각각의 상황에 맞는 예외적인 절차를 밟도록 구현했다. Explicit 방식에 위의 몇가지..

[Malloc Lab] 5. 성능 개선을 위한 몇가지 최적화

1. CHUNKsize 축소 (+2점) malloc lab에서 다루는 heap의 사이즈는 20MB로 작고, 테스트케이스에서 할당과 free를 요구하는 용량도 작다. 이런 상황에서 extend_heap의 최소용량인 CHUNKsize가 4kB인건 비효율적인 공간 사용이 될 수 있다. CHUNKsize를 줄여가며 점수를 확인한 결과 2^8 이하일때 최대 점수가 나왔다. 2^7, 2^6 혹은 그 이하를 해도 점수가 더 오르진 않는걸 보면 너무 작은 용량은 테스트케이스에 없는 것 같다. 2. place 함수 커스텀 (+2점) place함수는 find_fit으로 선택된 빈 블록의 크기과 실제 할당을 요구한 크기의 차 surplus가 Dsize*2 이상이라면 그 나머지를 다시 빈 블록으로 분할하여 재활용한다. 기존의..

[Malloc Lab] 4. Explicit, pointer 기록을 이용한 malloc 구현

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 12..

[Malloc Lab] 3. Explicit, vector 기록을 이용한 malloc 구현

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 12..

[Malloc Lab] 2. Implicit, Next fit을 이용한 malloc 구현

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 // Implicit과 공통되는 선언부 생략 static char *lastplacedP; static size_t lastplacedsize; int mm_init(void) // Implicit과 동일 static char *extend_heap(size_t words) // Implicit과 동일 static char ..

[Malloc Lab] 1. Implicit, first fit을 이용한 malloc 구현

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 12..