implicit free list
이번 글은 CS:APP책 9장에 적혀있는 코드를 참고하여 작성한 implicit free list코드와 공부한 내용을 정리해 볼 생각이다.
implicit free list는 메모리공간을 관리하기 위한 방법 중 제일 기본적이고, 간단한 방법이다. 블록의 할당 여부를 명시적으로 표시하지 않고, 메모리 블록의 크기를 확인하여 다음 블록의 시작 위치를 추적함으로써 할당 가능한 블록을 찾아낸다.
데이터가 들어있는 블록과 들어있지 않은 블록을 구분하여 관리하지 않고, 일정 포인터 위치부터 선형 탐색하여 알맞는 크기의 데이터가 들어 있지 않아 사용할 수 있는 블럭(이제부터 free block이라고 하겠다.)을 찾아 데이터를 삽입하는 방식이다.
구현이 간결하고 적은 오버헤드로 메모리 할당 및 해제를 수행할 수 있다는 장점이 있다. 하지만, coalescing 과정에서 메모리 접근이 많아져 성능이 저하될 수 있으며, 블록의 크기를 고정하여 내부 단편화를 방지하기 때문에 메모리 사용률이 낮을 수 있다는 단점이 있다.
채점된 점수를 보더라도, 해당 코드가 채점된 점수는 52점으로, util은 44점이지만, thru가 8점인 것으로 보아, 연산속도가 느린 것을 알 수 있다.
Implicit free list에서 블록은 header, data, footer로 구성된다. header에는 할당 블록의 크기와 할당여부를 저장하고, footer는 블록의 끝을 나타내며, header와 같은 값을 가진다. 블록 내부의 데이터 영역은 실제로 할당된 데이터를 저장한다. 이러한 구성으로 인해 내부 단편화가 발생하지 않도록 블록 크기를 최소 4워드로 제한하며, 필요한 경우 패딩을 추가하여 메모리 단편화를 최소화한다.
header로 32bit=8byte=2word 단위로 이루어 지는데, 앞부터 29자리 수는 사이즈 값을 나타내며, 뒤의 3자리수는 할당여부를 나타낸다. 이렇게 쓸 수 있는 이유는 블록의 크기를 8의 배수로 맞추기 때문에 하위 3자리는 000이므로 이 자리수에 할당여부를 0,1로 표현할 수 있기 때문이다. 해당 값을 사이즈|할당여부로 구현하는 방법은 아래에 설명해 놓았다.
기본 설정
자료구조의 연결리스트 같은 방식.
워드: 4byte
더블워드: 8byte
최소 블록 크기는 16byte (책 823p)
한블록에는 1워드의 헤더, 데이터, 추가적인 패딩으로 구성됨.
설정변수 및 매크로
/* single word (4) or double word (8) alignment */
#define ALIGNMENT 8
ALIGNMENT이 8, 1word가 4byte이므로, 가상메모리 한 칸당 32bit(0~31)의 값이 저장된다.
/* rounds up to the nearest multiple of ALIGNMENT */
#define ALIGN(size) (((size) + (ALIGNMENT - 1)) & ~0x7)입력받은 size에 대해 ALIGNMENT에 정의된 값(8)으로 정렬된 크기를 반환하는 매크로 함수이다.
- 이진 비트 연산자 &: [1, 1] =1 그외는 전부 0
- 논리 부정 연산자 ~: ~1 ==0, ~0 == 1
-> ~0x7 == hex: 0xFFFFFFF8
아래 계산기 이미지를 보면, 16진수 값 0xFFFFFFF8은 다음과 같이 32자리숫자중에 하위비트 3자리를 빼고 0인 값임을 알 수 있다.
하위 비트 3자리는 1,2,4의 자리이며, 해당 값이 0이면, 8,16,32..등의 자리값만 있게되어 8의 배수가된다.
예를들어, size=1인 경우, (1 +7) & 0xFFFFFFF8이 되며, 이진수로 표현하면
0000 0000 0000 0000 0000 0000 0000 1000 & 1111 1111 1111 1111 1111 1111 1111 1000
= 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 1000 = DEX: 8
10진수의 8 값이 가상메모리에 저장된다.
size=15인 경우, (15+7) & 0xFFFFFFF8
= 0000 0000 0000 0000 0000 0000 0010 00010 & 1111 1111 1111 1111 1111 1111 1111 1000
= 0000 0000 0000 0000 0000 0000 0010 00000 = DEX:32
10진수의 32값이 가상메모리에 저장된다.
따라서 해당 매크로는 32자리수의 8의 배수(하위 3비트값=0)로 연산해준다.
#define GET(p) (*(unsigned int *)(p))p는 포인터 값이며, 연산을 위해 unsigned int형으로 캐스팅을 해준뒤, 포인터 속성을 유지하도록 '*' 를 붙여준다.
#define PUT(p, val) (*(unsigned int *)(p) = (val))p는 포인터 값이며, 해당 포인터가 가르키는 값이 val이 되도록 한다.
#define GET_SIZE(p) (GET(p) & ~0x7)ALIGN(size) 매크로와 비슷한 원리로, 하위 3비트를 0으로 만들고, 나머지 29자리 수를 가져옴으로써 사이즈값만을 get하는 매크로이다.
#define GET_ALLOC(p) (GET(p) & 0x1)위 코드와 반대로, 하위 3비트만 가져옴으로써 할당여부의 값만 가져온다. (0은 free된 상태, 1은 데이터 할당된 상태)
#define HDRP(bp) ((char *)(bp)-WSIZE)
#define FTRP(bp) ((char *)(bp) + GET_SIZE(HDRP(bp)) - DSIZE)
#define NEXT_BLKP(bp) ((char *)(bp) + GET_SIZE(((char *)(bp)-WSIZE)))
#define PREV_BLKP(bp) ((char *)(bp)-GET_SIZE(((char *)(bp)-DSIZE)))우리는 사회적 약속을 하기로 한다. bp는 내가 탐색하고 싶고, 알고싶은 블럭을 가리킬 때, 그 블럭의 header 뒤에 bp포인터가 위치하도록 하자.
포인터의 위치를 바꿔주는 매크로는 그림으로 이해하면 더 쉽다.
처음 bp의 위치는 검은 화살표로 나타냈으며, 그 뒤의 연산은 해당 색깔 화살표로 표시했다. 그리고 최종 위치의 포인터 화살표는 보라색 화살표로 나타냈다.
int mm_init(), extend_heap()
코드1
int mm_init(void)
{
/* Create the initial empty heap */
if ((heap_listp = mem_sbrk(4 * WSIZE)) == (void *)-1)
return -1;
PUT(heap_listp, 0); /* Alignment padding */
PUT(heap_listp + (1 * WSIZE), PACK(DSIZE, 1)); /* Prologue header */
PUT(heap_listp + (2 * WSIZE), PACK(DSIZE, 1)); /* Prologue footer */
PUT(heap_listp + (3 * WSIZE), PACK(0, 1)); /* Epilogue header */
heap_listp += (2 * WSIZE);
/* Extend the empty heap with a free block of CHUNKSIZE bytes */
if (extend_heap(CHUNKSIZE / WSIZE) == NULL)
return -1;
return 0;
}코드2
static void *extend_heap(size_t words)
{
char *bp;
size_t size;
/* Allocate an even number of words to maintain alignment */
size = (words % 2) ? (words + 1) * WSIZE : words * WSIZE;
if ((long)(bp = mem_sbrk(size)) == -1)
return NULL;
/* Initialize free block header/footer and the epilogue header */
PUT(HDRP(bp), PACK(size, 0)); /* Free block header */
PUT(FTRP(bp), PACK(size, 0)); /* Free block footer */
PUT(HDRP(NEXT_BLKP(bp)), PACK(0, 1)); /* New epilogue header */
/* Coalesce if the previous block was free */
return coalesce(bp);
}함수 실행후 VM 그림
mm_init()함수가 끝난 뒤 가상메모리 공간을 그림으로 그려봤다. 여기서 mem_sbrk(size)함수는 2번 실행되는데 4번째 줄에서 1번, 13번째줄의 extend_heap()함수에서 1번. 총 2번이 일어난다. 해당 함수는 size만큼 가상 메모리의 heap공간을 늘리고, 이전 break point를 반환한다. 따라서 최종 bp의 위치는 free_block_header의 위치가 되는 점을 주의하자.
또한, extend_heap()함수 전에는 epil.header였던 block이 extend_heap()함수의 12번줄 코드를 통해 free_block_header가 되면서 초기화가 된다.
mm_malloc()
- size가 0인 경우, NULL을 반환하는 예외처리를 한다.
- 사이즈가 너무 작은 블럭들이 생기면, payload보다 header,footer가 더 많은 내부 단편화가 생길 수 있어서 다음 로직을 적용한다. 일정 크기(여기서는 dsize) 보다 작으면 Dsize로 맞추고, 그 이상이면, asize = {...}문을 통해 8의 배수로 맞춰준다.
3.find_fit 함수를 호출하여, 적절한 크기의 빈 블록을 찾는다. find_fit 함수는 적절한 크기의 빈 블록을 검색하는 함수다. find_fit 함수가 반환한 블록이 존재하는 경우, place 함수를 호출하여 블록을 할당하고, 할당된 블록의 주소를 반환한다. find_fit 함수가 반환한 블록이 존재하지 않는 경우, extend_heap 함수를 호출하여 힙을 확장한다. 확장된 힙에서 asize만큼의 빈 블록을 찾아 place 함수를 호출하여 블록을 할당하고, 할당된 블록의 주소를 반환한다.
코드
void *mm_malloc(size_t size)
{
size_t asize; /* adjusted block size */
size_t extendsize; /* amount to extend heap if no fit */
char *bp;
if (size == 0)
{
return NULL;
}
/* Adjust block size to include overhead and alignment reqs. */
if (size <= DSIZE)
{
asize = 2 * DSIZE;
}
else
{
asize = DSIZE * ((size + (DSIZE) + (DSIZE - 1)) / DSIZE);
}
/* Search the free list for a fit */
if ((bp = find_fit(asize)) != NULL)
{
place(bp, asize);
return bp;
}
/* No fit found. Get more memory and place the block */
extendsize = MAX(asize, CHUNKSIZE);
if ((bp = extend_heap(extendsize / WSIZE)) == NULL)
{
return NULL;
}
place(bp, asize);
return bp;
}mm_free(void *bp)
주어진 블록을 해제하고, coalesce()함수를 통해 인접한 빈 블록을 병합하여 하나의 큰 블록으로 만드는 함수다. 이를 통해 외부단편화를 방지한다.
- bp의 블록 크기를 얻어온다. 이를 size 변수에 저장한다.
- bp의 헤더와 푸터를 각각 size와 0으로 설정한다. 이를 통해 블록이 사용 중이지 않음을 표시한다.
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);
}coalesce(void *ptr)
코드
static void *coalesce(void *ptr)
{
size_t prev_alloc = GET_ALLOC(FTRP(PREV_BLKP(ptr)));
size_t next_alloc = GET_ALLOC(HDRP(NEXT_BLKP(ptr)));
size_t size = GET_SIZE(HDRP(ptr));
if (prev_alloc && next_alloc) /* Case 1 */
{
return ptr;
}
else if (prev_alloc && !next_alloc) /* Case 2 */
{
size += GET_SIZE(HDRP(NEXT_BLKP(ptr)));
PUT(HDRP(ptr), PACK(size, 0));
PUT(FTRP(ptr), PACK(size, 0));
}
else if (!prev_alloc && next_alloc) /* Case 3 */
{
size += GET_SIZE(HDRP(PREV_BLKP(ptr)));
PUT(FTRP(ptr), PACK(size, 0));
PUT(HDRP(PREV_BLKP(ptr)), PACK(size, 0));
ptr = PREV_BLKP(ptr);
}
else /* Case 4 */
{
size += GET_SIZE(HDRP(PREV_BLKP(ptr))) + GET_SIZE(FTRP(NEXT_BLKP(ptr)));
PUT(HDRP(PREV_BLKP(ptr)), PACK(size, 0));
PUT(FTRP(NEXT_BLKP(ptr)), PACK(size, 0));
ptr = PREV_BLKP(ptr);
}
return ptr;
}블록 병합 함수인 coalesce 함수다. 이 함수는 현재 블록과 인접한 빈 블록을 병합하여 하나의 큰 블록으로 만드는 역할을 한다. 따라서 현재 블록과 양옆의 블록의 포인터를 잘 지정해야한다. 이 때 앞서 설명한 매크로를 이용하는데, 아래 공부할 때 그렷던 그림들을 참고하면 이해하는데 도움이 될것이다.
coalesce 함수는 먼저 현재 블록의 이전 블록과 다음 블록의 할당 여부를 확인한다.
이전 블록과 다음 블록이 모두 할당된 경우(케이스 1), 블록을 그대로 반환한다.
이전 블록이 할당되어 있고, 다음 블록이 비어 있는 경우(케이스 2), 현재 블록과 다음 블록을 병합한다.
이전 블록이 비어 있고, 다음 블록이 할당되어 있는 경우(케이스 3), 이전 블록과 현재 블록을 병합한다.
이전 블록과 다음 블록이 모두 비어 있는 경우(케이스 4), 이전 블록, 현재 블록, 다음 블록을 모두 병합한다.
블록을 병합할 때는 블록 헤더와 푸터의 값을 업데이트하여 하나의 큰 블록으로 만든다. 이 때, 블록을 반환할 때는 병합된 블록 중 가장 앞쪽의 블록 주소를 반환한다.
coalesce 함수는 메모리 공간을 최적화하기 위해 사용되며, 인접한 빈 블록을 병합하여 더 큰 블록으로 만든다. 이러한 과정을 통해 빈 공간을 최대한 활용하고, 메모리 효율성을 높인다.
mm_realloc(void *ptr, size_t size)
메모리를 재할당 하는 코드다.
-
ptr이 NULL인 경우, mm_malloc 함수를 호출하여 새로운 메모리 블록을 할당하고, 그 주소를 반환합니다. 이는 새로운 메모리 블록을 할당하는 경우다.
-
size가 0인 경우, mm_free 함수를 호출하여 이전에 할당된 메모리 블록을 해제하고, NULL을 반환한다. 이는 메모리 블록을 해제하는 경우다.
-
mm_malloc 함수를 호출하여 새로운 메모리 블록을 할당한다. 만약 메모리 블록 할당에 실패한 경우, NULL을 반환한다.
-
이전 메모리 블록의 크기에서 8바이트(헤더와 푸터의 크기)를 뺀 크기를 copySize에 저장한다.
size가 copySize보다 작은 경우, copySize를 size로 설정한다. -
memcpy 함수를 호출하여 이전 메모리 블록의 데이터를 새로운 메모리 블록으로 복사한다.
이전 메모리 블록을 mm_free 함수를 호출하여 해제한다. -
새로운 메모리 블록의 주소를 반환한다.
mm_realloc 함수는 이전에 할당된 메모리 블록을 새로운 크기로 조정하여 새로운 메모리 블록을 할당하고, 기존 데이터를 새 메모리 블록으로 복사한다. 이를 통해 메모리 사용을 최적화하고, 메모리 할당과 해제의 성능을 향상시킨다.
코드
void mm_realloc(void ptr, size_t size)
{
void oldptr = ptr;
void newptr;
size_t copySize;
/* case 1 */
if (ptr == NULL)
return mm_malloc(size);
/* case 2 */
if (size == 0)
{
mm_free(ptr);
return NULL;
}
newptr = mm_malloc(size);
if (newptr == NULL)
return NULL;
copySize = GET_SIZE(HDRP(oldptr)) - DSIZE;
if (size < copySize)
copySize = size;
memcpy(newptr, oldptr, copySize);
mm_free(oldptr);
return newptr;}
find_fit(size_t asize)
이 함수는 요청한 크기에 맞는 빈 블록을 검색하고, 해당 블록의 주소를 반환한다.
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;
}place(void *bp, size_t asize)
이 함수는 빈 블록을 요청한 크기에 맞게 분할하여 할당하는 역할을 한다. 를 통해 메모리 사용을 최적화하고, 메모리 할당과 해제의 성능을 향상시킨다.
place 함수는 메모리 블록의 크기를 csize로 저장한다. 만약, 분할 후 남는 공간이 충분하다면, 요청한 크기에 맞는 블록과 남은 빈 블록을 만든다. 이 때, 남은 블록은 최소 블록 크기보다 작으면 안된다. 남은 블록이 최소 블록 크기보다 작을 경우, 빈 블록을 만들지 않고 전체 블록을 할당한다. 이 때, 블록 헤더와 푸터에 할당 표시를 추가하여 할당된 상태로 만든다.
이 코드 또한 간단하므로, 앞에 매크로 그림을 참고하면 이해에 도움이 될것이다.
코드
static void place(void *bp, size_t asize)
{
size_t csize = GET_SIZE(HDRP(bp));
if ((csize - asize) >= (2 * DSIZE))
{
PUT(HDRP(bp), PACK(asize, 1));
PUT(FTRP(bp), PACK(asize, 1));
bp = NEXT_BLKP(bp);
PUT(HDRP(bp), PACK(csize - asize, 0));
PUT(FTRP(bp), PACK(csize - asize, 0));
}
else
{
PUT(HDRP(bp), PACK(csize, 1));
PUT(FTRP(bp), PACK(csize, 1));
}
}