9.9.12 종합 설계 : 간단한 할당기의 구현 (수정중)

이제 본격적인 할당기의 구현이다.

우선 전제 조건은 최대 블록은 2^32 = 4GB이고, 64비트를 전제로 하여 설계를 해보겠다.

- 할당기 기본 설계

우선 memlib.c 메모리 시스템 모델을 보고 가자. (memlib.c 패키지게엇 기본적으로 제공되므로 실제로 코드로 구현하지 않아도 된다.)

// --------------------- Declaration --------------- //
extern int mm_init(void);
extern void *mm_malloc (size_t size);
extern void mm_free (void *ptr);


/* Private global variables */
static char *mem_heap;  /* Points to first byte of heap */
static char *mem_brk; /* Points to last byte of heap plus 1 */
static char *mem_max_addr; /* Max legal heap addr plus 1 */

/* *mem_init - Initilaize the memory system model */

void mem_init(void)
{
    mem_heap = (char *)Malloc(MAX_HEAP);
    mem_brk = (char *)mem_heap;
    mem_max_addr = (char *)(mem_heap + MAX_HEAP);
}

/*
 * mem_sbrk - Simple model of the sbrk function. Extends the heap
 * by incr bytes and returns the start address of the new area.
 * In this model, the heap cannot be shrunk
 */

void *mem_sbrk(int incr)
{
    char *old_brk = mem_brk;
    
    if ( (incr < 0) || ((mem_brk + incr) > mem_max_addr)){
        errno = ENOMEM;
        fprintf(stderr, "ERROR: mem_sbrk failed. Ran out of memory...\n")
        return (void *) -1;
    }
    mem_brk += incr;
    return (void *)old_brk;
}

전역변수부터 보자. 아래 세 개는 문자열 포인터이다. 할당기가 시작하면서 다음과 같이 설정된다.

mem_heap : 힙의 처음을 가리키는 포인터

mem_brk : 배당 받은 힙 공간의 마지막 자리를 가리킨다.

mem_max_addr : MAX_HEAP의 끝 자리를 나타낸다. 이 이상으로는 할당할 수 없다.

여기서 주목해야할 것은 mem_brk이다.

현재 내가 할당받은 heap 공간 중에서 가장 마지막 공간 + 1칸을 나타내는 곳이다. ( 그림의 한 칸은 1word를 가리킨다. 해당 칸의 주소는 칸의 왼쪽 모서리이다. 즉, old_brk는 늘린 heap의 첫번째 칸을 가리킨다. )

그 다음 두 함수를 보자.

mem_init : 할당기를 초기화하고, 성공하면 0을, 아니면 -1를 반환한다.

mem_sbrk : incr (할당 요청이 들어왔을 때, 요청된 용량) 가 들어왔을 때, 이것이 MAX_HEAP을 초과하지 않으면 추가로 mem_brk를 할당 요청 용량만큼 옮긴다. (그림 1에서 할당 요청이 들어오기 전에 mem_brk의 위치는 old_brk였다.) 만약 용량의 크기가 음수이거나, MAX_HEAP을 초과하면 error 메세지를 반환한다.

그렇다면 이제 할당키 코드로 들어가보자. (여기서부터 우리가 구현해야할 코드다.)

1 /* Basic constants and macros */
2 #define WSIZE 4 /* Word and header/footer size (bytes) */
3 #define DSIZE 8 /* Double word size (bytes) */
4 #define CHUNKSIZE (1<<12) /* Extend heap by this amount (bytes) */
5
6 #define MAX(x, y) ((x) > (y)? (x) : (y))
7
8 /* Pack a size and allocated bit into a word */
9 #define PACK(size, alloc) ((size) | (alloc))
10
11 /* Read and write a word at address p */
12 #define GET(p) (*(unsigned int *)(p))
13 #define PUT(p, val) (*(unsigned int *)(p) = (val))
14
15 /* Read the size and allocated fields from address p */
16 #define GET_SIZE(p) (GET(p) & ~0x7)
17 #define GET_ALLOC(p) (GET(p) & 0x1)
18
19 /* Given block ptr bp, compute address of its header and footer */
20 #define HDRP(bp) ((char *)(bp) - WSIZE)
21 #define FTRP(bp) ((char *)(bp) + GET_SIZE(HDRP(bp)) - DSIZE)
22
23 /* Given block ptr bp, compute address of next and previous blocks */
24 #define NEXT_BLKP(bp) ((char *)(bp) + GET_SIZE(((char *)(bp) - WSIZE)))
25 #define PREV_BLKP(bp) ((char *)(bp) - GET_SIZE(((char *)(bp) - DSIZE)))

위의 코드는 할당기 코드 전체에서 사용하게 될 상수와 매크로를 보여준다.

2~4번 줄은 기본 size의 상수를 정하고 있다.

WSIZE;4byte : 1 Words이며, 헤더/풋터의 크기. 그림에서 네모 한 칸을 의미한다.

DSIZE;8byte : 2 Words이며, 블록들은 DSIZE 단위로 크기가 결정된다.

CHUNKSIZE;2^12byte : 초기 가용 블록과 힙 확장 시 추가되는 블록 크기

그리고 9~25번 줄은 자주 사용하게 될 기능들을 매크로로 저장한 것이다.

PACK(size, alloc) ((size) | (alloc)) : 비트연산자를 통해 size와 alloc을 표시하는 상수값을 반환한다.

GET(p) : p(포인터) 가 가리키는 블록의 데이터를 반환한다.

PUT(p, value) : p(포인터) 가 가리키는 블록에 value(데이터)를 입력한다.

GET_SIZE(p) : 비트연산자를 통해 헤더/풋터에 적혀있는 사이즈를 반환한다.

GET_ALLOC(p) : 비트연산자를 통해 헤더/픗터에 현재 블록의 가용 여부를 판단한다.

bp는 현재 블록의 포인터 (그림 1의 pointer)를 나타낸다.

HDRP(bp) : 현재 블록의 헤더의 위치를 반환한다. ( bp - 1words )

FTRP(bp) : 현재 블록의 풋터의 위치를 반환한다. ( bp + 현 블록의 크기 - 2words; bp + 현 블록의 크기하면 다음 블록의 BP를 나타낸다. 그래서 그 자리에서 -2words를 하면 현 블록의 풋터를 나타내게 된다.)

NEXT_BLKP(bp) : 다음 블록의 bp의 위치를 가리킨다. ( BP + 현재 블록의 크기;BP - 1words로 현 블록의 헤더를 읽는다. )

PREV_BLKP(bp) : 이전 블록의 bp의 위치를 가리킨다. ( BP - 이전 블록의 크기;BP - 2words로 전 블록의 풋터를 읽는다. )

1 int mm_init(void)
2 {
3 /* Create the initial empty heap */
4 if ((heap_listp = mem_sbrk(4*WSIZE)) == (void *)-1)
5 return -1;
6 PUT(heap_listp, 0); /* Alignment padding */
7 PUT(heap_listp + (1*WSIZE), PACK(DSIZE, 1)); /* Prologue header */
8 PUT(heap_listp + (2*WSIZE), PACK(DSIZE, 1)); /* Prologue footer */
9 PUT(heap_listp + (3*WSIZE), PACK(0, 1)); /* Epilogue header */
10 heap_listp += (2*WSIZE);
11
12 /* Extend the empty heap with a free block of CHUNKSIZE bytes */
13 if (extend_heap(CHUNKSIZE/WSIZE) == NULL)
14     return -1;
15 return 0;
16 }

이제 init 함수를 살펴보자.

우선 초기 할당을 위해 4워드 (16 byte; 이전 글의 그림에서 한 칸으로 표시되던 것들) 의 가용 리스트를 만든다. (상기의) mem_sbrk의 함수에서 할당할 수 없는 경우 void * -1를 반환했던 것을 기억하자.

그리고 mm_init 함수에서 할당받은 4번째칸의 구조는 다음과 같다.

1번째 칸 : 0을 적어넣는다.

2번째 칸 : 용량:2워드, 할당:1(할당됨) 이라는 헤더를 적어 넣는다.

3번째 칸 : 용량:2워드, 할당:1 이라는 풋터를 적어 넣는다. ( 2번째, 3번째 칸은 prologue block이라고 칭한다. )

4번째 칸 : 용량:0워드, 할당:1 이라는 헤더를 적어 넣는다. (이 칸은 앞으로 epilogue block header 라고 칭한다. )

10번째 줄은 heap_listp (현재 위치를 나타내는 포인터가 될 것이다.)를 2워드 뒤로 옮긴다. 그러면 heap_listp는 3번째 칸을 가리키게 될 것이다. 그리고 extend_heap 함수를 호출한다. (아래 코드)

1 static void *extend_heap(size_t words)
2 {
3 char *bp;
4 size_t size;
5
6 /* Allocate an even number of words to maintain alignment */
7 size = (words % 2) ? (words+1) * WSIZE : words * WSIZE;
8 if ((long)(bp = mem_sbrk(size)) == -1)
9 return NULL;
10
11 /* Initialize free block header/footer and the epilogue header */
12 PUT(HDRP(bp), PACK(size, 0)); /* Free block header */
13 PUT(FTRP(bp), PACK(size, 0)); /* Free block footer */
14 PUT(HDRP(NEXT_BLKP(bp)), PACK(0, 1)); /* New epilogue header */
15
16 /* Coalesce if the previous block was free */
17 return coalesce(bp);
18 }

우리는 2워드;8바이트씩 할당받을 수 있다. words가 홀수면 +1을 해줘서 공간을 할당받는다.

그리고 size를 mem_sbrk의 인자로 넘겨줘서 -1을 반환받으면 (즉, mem_sbrk 함수에서 이 size가 할당 가능한 heap의 범위를 초과했다고 판단하면) 할당하지 않는다.

배정받은 가용 블록의 앞뒤에 이 블록이 가용상태라는 정보를 담은 헤더와 풋터를 배치한다. (12, 13줄)

그리고 14번줄에서 다음 블록의 헤더로 가서 epilogue block header 를 입력한다. 여기서 주의해야 할 점은 다음 블록이라고는 했지만 실제로는 존재하지 않는 블록이다. 단지, extend_heap으로 배치한 블록 너머에 오지 않도록 배치한 블록 다음 공간을 블록이라고 가정하고 epilogue block header 를 배치하는 것이다.

그리고 새로 확장한 블록의 앞이 가용 블록이라면 통합시킨다. (colaesce(bp))

반환 함수와 연결 함수는 아래와 같다.

1 void mm_free(void *bp)
2 {
3 size_t size = GET_SIZE(HDRP(bp));
4
5 PUT(HDRP(bp), PACK(size, 0));
6 PUT(FTRP(bp), PACK(size, 0));
7 coalesce(bp);
8 }
9
10 static void *coalesce(void *bp)
11 {
12 size_t prev_alloc = GET_ALLOC(FTRP(PREV_BLKP(bp)));
13 size_t next_alloc = GET_ALLOC(HDRP(NEXT_BLKP(bp)));
14 size_t size = GET_SIZE(HDRP(bp));
15
16 if (prev_alloc && next_alloc) { /* Case 1 */
17 return bp;
18 }
19
20 else if (prev_alloc && !next_alloc) { /* Case 2 */
21 size += GET_SIZE(HDRP(NEXT_BLKP(bp)));
22 PUT(HDRP(bp), PACK(size, 0));
23 PUT(FTRP(bp), PACK(size,0));
24 }
25
26 else if (!prev_alloc && next_alloc) { /* Case 3 */
27 size += GET_SIZE(HDRP(PREV_BLKP(bp)));
28 PUT(FTRP(bp), PACK(size, 0));
29 PUT(HDRP(PREV_BLKP(bp)), PACK(size, 0));
30 bp = PREV_BLKP(bp);
31 }
32
33 else { /* Case 4 */
34 size += GET_SIZE(HDRP(PREV_BLKP(bp))) +
35 GET_SIZE(FTRP(NEXT_BLKP(bp)));
36 PUT(HDRP(PREV_BLKP(bp)), PACK(size, 0));
37 PUT(FTRP(NEXT_BLKP(bp)), PACK(size, 0));
38 bp = PREV_BLKP(bp);
39 }
40 return bp;
41 }

free 함수는 아주 간단하다.

반환하려는 블록의 헤더와 풋터로 가서 0만 입력해주면 된다.

그럼 연결함수를 보자. 앞 블록의 풋터와 뒷 블록의 헤더에서 정보를 읽어 앞 블록과 뒷 블록이 가용 상태인지 본다. (12~13 줄)

그리고 연결을 위해 현재 블록의 사이즈를 읽어온다. (14 줄)

이제 세 가지로 나뉜다. 1. 앞 블록이 가용이고 뒷 블록이 가용이 아닐 때, 2. 앞 블록은 불가용이고 뒷 블록이 가용일 때, 3. 양 쪽 모두 가용일 때.

각각의 경우에서 상황에 맞게 병합한 뒤, 사이즈와 bp(블록 포인터)를 기록하고, 블록 포인터를 반환한다.

이제 주인공인 할당 함수를 보도록 하자.

1 void *mm_malloc(size_t size)
2 {
3 size_t asize; /* Adjusted block size */
4 size_t extendsize; /* Amount to extend heap if no fit */
5 char *bp;
6
7 /* Ignore spurious requests */
8 if (size == 0)
9 return NULL;
10
11 /* Adjust block size to include overhead and alignment reqs. */
12 if (size <= DSIZE)
13 asize = 2*DSIZE;
14 else
15 asize = DSIZE * ((size + (DSIZE) + (DSIZE-1)) / DSIZE);
16
17 /* Search the free list for a fit */
18 if ((bp = find_fit(asize)) != NULL) {
19 place(bp, asize);
20 return bp;
21 }
22
23 /* No fit found. Get more memory and place the block */
24 extendsize = MAX(asize,CHUNKSIZE);
25 if ((bp = extend_heap(extendsize/WSIZE)) == NULL)
26 return NULL;
27 place(bp, asize);
28 return bp;
29 }

8~9 줄 : 만약 할당 요청받은 용량이 0이면 그냥 반환한다.

12~13 줄 : 2워드 (8바이트) 이하의 사이즈는 4워드로 할당요청한다. (앞의 1워드는 헤더에, 뒤의 1워드는 풋터를 넣어야한다.)

14~15 줄 : 할당 요청의 용량이 2워드 초과일 때인데, 8byte의 배수에 안맞게 나왔을 때, 충분한 8byte의 배수의 용량을 할당할 수 있도록 하는 것이다.

예를 들어 31byte를 필요로 한다고 하자. 그러면 (31;size + 8;DSIZE + 7;DSIZE-1 ) / 8;DSIZE = 5.75 가 된다. 그런데 DSIZE는 정수형이므로 소수가 있으면 내림해서 받는다. 그래서 5가 되고, 40byte를 필요로한다. 여기에 헤더가 더해지면 35byte가 되고, 35byte보다 큰 8의 배수는 40byte가 됨으로 8;DSIZE * (31;size + 8;DSIZE + 7;DSIZE-1 ) / 8;DSIZE 가 40byte가 되고, 40byte를 배정받는다.

(간단하게 말하면 (요청된 용량+헤더의 크기) 보다 큰 8의 배수를 찾는 과정이다.)

18~19 줄 : find_fit함수로 적당한 크기의 가용 블록을 검색한다. 그리고 place함수로 초과 부분을 분할하고 새롭게 할당한 블록의 블록 포인터를 반환한다. (find_fit과 place는 뒤에서 서술하겠다.)

24~28 줄 : 만약 적당한 가용 블록을 찾지 못한다면 extend_heap함수로 heap을 확장하여 추가 확장 블록을 배정한다. (extendsize/WSIZE는 칸의 갯수를 말한다.) 만약 heap을 확장하는 것에 성공하면 블록을 배치하고 bp를 반환한다. (extend_heap에서 힙을 확장하는 데 실패하면 NULL을 반환하게 된다. 그래서 bp == NULL이되면 배치를 하지않고 NULL을 반환한다.)

1 static void *find_fit(size_t asize)
2 {
3 /* First-fit search */
4 void *bp;
5
6 for (bp = heap_listp; GET_SIZE(HDRP(bp)) > 0; bp = NEXT_BLKP(bp)) {
7 if (!GET_ALLOC(HDRP(bp)) && (asize <= GET_SIZE(HDRP(bp)))) {
8 return bp;
9 }
10 }
11 return NULL; /* No fit */
12 #endif
13 }

적절한 가용 블록이 있는지 찾는 find_fit 함수이다. (여기선 first-fit 탐색을 적용하였다.)

우선 for문으로 탐색한다. bp는 heap의 시작점을 가리키는 heap_listp에서 시작하여, 헤더를 읽는다. 만약 (해당 헤더의) 블록이 할당되어있지 않고(GET_ALLOC 함수로 판단한다.) 사이즈도 원하는 크기(asize)보다 크다면 (GET_SIZE로 판단한다.) bp를 반환한다. 그러면 위의 mm_malloc에서 해당 bp에 데이터를 배치할 것이다.

만약 적절한 헤더가 아니라면 다음 블록의 헤더로 이동해서 같은 판단 작업을 수행하고, 움직일 수 없게 되면(GET_SIZE(HDRP(bp)) > 0 이 아닐 때; 우리는 이 힙의 끝점에 0/1 로 표시한 epilogue header 가 있는 것을 기억해야한다.) NULL을 반환한다. (NULL을 반환하면, mm_malloc함수에서 extend_heap으로 힙을 확장할 것이다.)

그러면 이제 데이터를 배치하는 place함수를 살펴보자.

1 static void place(void *bp, size_t asize)
2 {
3 size_t csize = GET_SIZE(HDRP(bp));
4
5 if ((csize - asize) >= (2*DSIZE)) {
6 PUT(HDRP(bp), PACK(asize, 1));
7 PUT(FTRP(bp), PACK(asize, 1));
8 bp = NEXT_BLKP(bp);
9 PUT(HDRP(bp), PACK(csize-asize, 0));
10 PUT(FTRP(bp), PACK(csize-asize, 0));
11 }
12 else {
13 PUT(HDRP(bp), PACK(csize, 1));
14 PUT(FTRP(bp), PACK(csize, 1));
15 }
16 }

place 함수는 데이터를 할당할 가용 블록의 bp와 배치 용량을 할당받는다.

그리고 해당 가용 블록의 전체 크기는 csize로 저장한다.

만약 csize와 asize의 차이가 16byte (네 칸) 보다 작다면 해당 블록을 통째로 사용해서, 해당 블록의 첫 자리에는 헤더를, 끝 자리에는 풋터를 놓는다. (else문)

if문에 들어가기 앞서 왜 4칸인가?

우리는 기본 단위가 2칸인 것을 기억해야한다. 그런데 헤더와 풋터만 놔도 2칸을 다 사용해버리기 때문에 실제로 데이터를 배치할 수 있는 공간은 2칸보다 큰 2의 배수인 4칸이 된다. (헤더 + 데이터 2칸 + 풋터)

그래서 만약 가용 블록과 요구되는 용량 (데이터 + 헤더 + 풋터) 의 차이가 4칸이상이라면, 통째로 쓰기에는 아까우므로 분리를 해줘야한다. 그럼 if문을 하나씩 뜯어보도록 하자.

6~7 줄 : 요청 용량만큼 블록을 배치하고 헤더와 풋터를 배치한다.

8~10 줄 : 남은 블록에 헤더와 풋터를 배치한다.

'프로그래밍 공부 > CSPP' 카테고리의 다른 글

11.3 글로벌 IP 인터넷 (0)	2021.01.22
11.1 클라이언트-서버, 11.2 네트워크 (0)	2021.01.22
9.9.11 경계 태그로 연결하기 (0)	2021.01.16
9.9.7~11 할당한 블록의 배치/분할/연결 등 (0)	2021.01.16
9.9.4 단편화 / 9.9.5 구현 이슈 / 9.9.6 묵시적 가용 리스트 (0)	2021.01.15

불냥이의 작은 도서관

9.9.12 종합 설계 : 간단한 할당기의 구현 (수정중)

'프로그래밍 공부 > CSPP' 카테고리의 다른 글

댓글

티스토리툴바

9.9.12 종합 설계 : 간단한 할당기의 구현 (수정중)

'프로그래밍 공부 > CSPP' 카테고리의 다른 글

관련글

댓글

티스토리툴바