나만의 동적 메모리 할당기의 성능을 더더욱 높이기 위해, Explicit Free List
를 이용한 구현에 대해 공부했다. Implicit Free List
를 사용한 할당기는 간단하게 구현할 수 있지만 블록의 할당에 소모되는 시간이 힙의 모든 블록 수
에 비례한다는 단점이 있었다. 반면에 Explicit Free List
를 이용한다면, 블록의 할당에 소모되는 시간을 힙의 가용 블록 수
로 줄일 수 있다.
Explicit Free List
의 개념은 생각보다 간단했다. 가용 가능한 블록의 내부에 다음 가용 블록의 주소를 가리키는 포인터 Next
와 이전 가용 블록의 주소를 가리키는 포인터 Prev
를 포함하는 것! 이렇게 해주면 블록을 할당하려 할 때, 가용 블록들의 Next
포인터를 읽어나가며 가용 블록들만 탐색할 수 있게 된다.
Ok! 생각보다 별로 어려울 게 없어보였다. 가용 블록을 만들어 줄 때, 포인터들만 잘 포함해 주면 될 것 같은 느낌? 바로 작업에 착수했다.
Place
함수를 이렇게 변환하면 되겠다! 싶어 정리해본 그림처음 생각했던 대로 가용 블록에 Next
와 Prev
포인터를 물리적으로 포함시키려 했었다. 최소 블록 사이즈는 2*DSIZE
였고, 기존의 Header
와 Footer
를 제외하고도 DSIZE
만큼이 남게 된다. 그럼 포인터를 담을 공간이 딱 확보가 되어있네?
신나게 Prev
와 Next
의 주소를 계산하는 매크로 함수를 선언하고, 함수들의 로직을 변경해나갔다. 행복했던 시간도 잠시, Free
함수를 수정하던 중 의문점이 생겼다. 할당됬던 블록은 Next와 Prev 포인터를 가지고 있지 않는데... 그럼 매번 Free해줄 때 마다 블록 앞 뒤로 가용 블록을 찾아야 해? 말이 안되는 소리였다. 저렇게 설계한다면 Explicit Free List
의 장점들을 다 내다가 버리는 꼴이였다.
결국 다른 방안을 모색하기 위해 CSAPP를 더 읽어보고, 다른 사람들의 코드를 보고 공부했다. 대부분의 사람들이 택한 방법은 가용 블록들을 관리하는 free_listp
를 따로 두는 것. 실제로 배열은 아니고, Linked List
와 같은 형태로 가용 블록들을 관리하는 것!
힙을 초기화 할 때, free_listp
를 위한 공간을 따로 할당해주고, 함수들을 수정하고, 또 새로 만들었다.
PUT(heap_listp, 0); // 미사용 패딩 워드
PUT(heap_listp + (1*WSIZE), PACK(2*DSIZE, 1)); // Prologue Block Header
PUT(heap_listp + (2*WSIZE), NULL); // predecessor for free_listp
PUT(heap_listp + (3*WSIZE), NULL); // successor for free_listp
PUT(heap_listp + (4*WSIZE), PACK(2*DSIZE, 1)); // Prologue Block Footer
PUT(heap_listp + (5*WSIZE), PACK(0, 1)); // Epilogue Block Head
free_listp = heap_listp + (2*WSIZE);
free_listp
를 관리하는 주요 함수 add_freelist
, remove_freelist
// Free List의 맨 앞에 삽입
void add_freelist(void *bp){
FREE_NEXT(bp) = free_listp;
FREE_PREV(bp) = NULL;
FREE_PREV(free_listp) = bp;
free_listp = bp;
}
// Free List에서 삭제
void remove_freelist(void *bp){
// Free List의 첫번째 블록인 경우
if (bp == free_listp) {
FREE_PREV(FREE_NEXT(bp)) = NULL;
free_listp = FREE_NEXT(bp);
}
else {
FREE_NEXT(FREE_PREV(bp)) = FREE_NEXT(bp);
FREE_PREV(FREE_NEXT(bp)) = FREE_PREV(bp);
}
}
find_fit
함수. free_listp
를 탐색하게 바뀌었다.static void *find_fit(size_t asize){
void *bp;
for (bp = free_listp; GET_ALLOC(HDRP(bp))!= 1; bp = FREE_NEXT(bp)){
if (asize <= GET_SIZE(HDRP(bp))) {
return bp;
}
}
return NULL;
}
비록 작은 수치이지만 점수가 올랐다! 하지만 Malloc Lab: first-fit 을 next-fit 로 바꾸며 만났던 문제들에서 내가 최종적으로 개선했던 코드보단 오히려 점수가 떨어졌다. 하지만 여기에 Segregated Storage
와 같은 기법을 이용한다면 좀 더 높은 점수를 기대할 수 있겠지? 😎