Malloc Lab
을 Implicit List
로 구현한 후 받은 첫 점수는 53점! 더 높은 점수를 위해서는 만든 동적 메모리 할당기의 성능을 다양한 방법으로 끌어올려야 했다. Malloc Lab
에서의 동적 메모리 할당기의 성능은 두 가지로 평가된다. Space Utilization과 Throughput. 영어 의미대로 `공간을 얼마나 잘 활용하는가'와 '할당 속도가 얼마나 빠른가'로 평가한다. 내가 선택한 더 높은 점수를 위한 첫 단추는 first-fit
을 next-fit
으로 바꿔 Throughput
을 개선하는 것!
first-fit
: 매 할당마다 처음부터 메모리를 쭉~ 보다가, 알맞은 자리가 있다면 할당!
next-fit
: first-fit과 동일하지만, 시작 위치를 처음부터가 아닌 이전 할당 위치부터!
first-fit
을 next-fit
으로 바꾸려고 마음먹은 후, 처음 든 생각은 '별거 아닐거 같은데?' 였다. 기존의 first-fit
을 활용한 find_fit
함수는 다음과 같다.
static void *find_fit(size_t asize){
void *bp;
for (bp = heap_listp; GET_SIZE(HDRP(bp)) > 0; bp = NEXT_BLKP(bp)) {
if (!GET_ALLOC(HDRP(bp)) && (asize <= GET_SIZE(HDRP(bp)))) {return bp;}
}
return NULL;
}
사전에 정의된 변수들과 상수들을 떼놓고 보면, 정말 로직이 간단하다고 느껴졌고, for
문의 초기값을 정해주는 부분인 bp = heap_listp
를 bp = recently_allocated
와 같이 최근 할당한 블록의 위치를 기억하는 전역 포인터로 바꿔준다면 간단하게 탐색 위치를 바꿀 수 있을거라 생각했다. 신나게 코드를 바꾸고,
static void *find_fit(size_t asize){
void *bp;
if (recently_allocated == NULL) {
recently_allocated = heap_listp;
}
for (bp = recently_allocated; GET_SIZE(HDRP(bp)) > 0; bp = NEXT_BLKP(bp)){
if (!GET_ALLOC(HDRP(bp)) && (asize <= GET_SIZE(HDRP(bp)))) {
recently_allocated = bp;
return bp;
}
}
return NULL;
}
overlaps...? ran out of memory...? 이 무슨.... 😨
간단한 로직 수정이었기에 저 코드에서의 문제는 없다고 생각이 들었다. 그렇다면 혹시 C언어 숙련도 문제로 포인터 recently_alloacated
를 잘못 처리했나? 싶어 문제점을 찾아봤는데 눈 씻고 찾아봐도 문제가 없어 보였다.. 대체 뭘까? 🤔
다양한 상황을 고려하기 위해 다양한 경우의 수를 생각해 보던 중, 할당 이전에 free
과정을 하고, 그로 인해 할당 가능한 블록들을 합쳐주는 coalesce
과정을 거친 후라면 내가 원하는 곳을 가리키지 않을수도 있겠다는 것을 알게 되었다. 그도 그럴게 단순무식하게 한 블록을 할당하면, 다음 블록이 할당되기까지 그 위치만을 계~속 기억하고 있으니까.. 그림을 그려 정리해보았다.
coalesce
과정이 문제가 된다면, 해당 부분을 거친 후에도 recently_allocated
포인터를 갱신해주면 될 것!
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));
// Case 1
...
// Case 4
recently_allocated = bp;
return bp; // 블록의 포인터를 리턴
}
coalesce
함수의 결과(병합 과정을 거친 블록의 주소)를 리턴하기 전, recently_allocated
포인터를 결과값으로 갱신해주었다. 이렇게 되면 최근 free
해준 블록이 있다면, 그곳에서 탐색을 시작하게 되기에, 완벽한 next-fit
은 아니지만 위의 버그는 확실하게 해결해줄 수 있을것!
Throughput
점수! 속도면에서 많은 개선을 이뤄냈다.현재 코드에서는 이전에 블록을 할당했던 위치 or 할당을 해제해준 블록의 위치부터 힙의 끝까지 탐색해보고, 넣을 수 없다면 힙의 사이즈를 늘려서 할당한다.
하지만 recently_allocated
이전에 수많은 할당 가능한 빈 공간이 있을 수 있는데, 이를 확인하지 않고 그냥 힙을 늘려서 할당해주는 것은 아쉽다고 느껴졌고, 그렇다면 recently_allocated
부터 쭉~ 탐색하고, 할당할 곳을 못 찾았다면 처음부터 한번 더 탐색해 보면 어떨까? 하는 생각이 들었다. 이렇게 하면 물론 앞에 빈 공간 없이 꽉꽉 알차게 할당되어있을 경우에는 동작 시간 저하를 유발하겠지만, 조금이라도 빈 공간이 있다면 훨씬 효율적으로 동작할 수 있겠다는 생각이 들었다.
static void *find_fit(size_t asize){
void *bp;
if (recently_allocated == NULL) {
recently_allocated = heap_listp;
}
for (bp = recently_allocated; GET_SIZE(HDRP(bp)) > 0; bp = NEXT_BLKP(bp)){
if (!GET_ALLOC(HDRP(bp)) && (asize <= GET_SIZE(HDRP(bp)))) {
recently_allocated = bp;
return bp;
}
}
// 저장된 위치부터 보고 나서 할당할 곳을 못찾았다면, 처음부터 재탐색 한번 더!
for (bp = heap_listp; GET_SIZE(HDRP(bp)) > 0; bp = NEXT_BLKP(bp)){
if (!GET_ALLOC(HDRP(bp)) && (asize <= GET_SIZE(HDRP(bp)))) {
recently_allocated = bp;
return bp;
}
}
return NULL;
}
Throughput
점수는 그대로, Space Utilization
점수는 소폭 상향되었다.이 이상의 점수를 얻기 위해서는 Implicit List
로는 한계가 보인다. Explicit List
를 이용해야 할 듯? 여기에 추가적으로 Buddy System
도 공부하여 적용할 수 있다면 더욱 더 좋은 성능을 이끌어 낼 수 있겠지 😎