[시스템 프로그래밍] Malloc Lab Explicit (1)

 

 

 

explicit 방식은 implicit 방식의 단점을 보완한다.

 

 

 

 

 

가용블록을 위와 같이 디자인한다.

 

header 4바이트 / pred + succ 16바이트 / footer 4바이트로 총 24바이트의 크기를 가진다.

 

pred와 succ 포인터를 통해 힙 공간 중 가용 가능한 공간들만 linked list 형태로 관리하는 방식을 사용한다.

 

 

 

 

 

할당된 블록은 위와 같이 디자인한다. (implicit과 동일)

 

가용 가능 블록들에 대해서는 prev와 succ포인터를 추가해야 해서 메모리를 조금 더 사용해야 하지만 그만큼의 이점이 있다.

 

implicit 방식으로 first fit을 구현할 때는 최악의 경우 전체 블록을 모두 조사해야 가용 블록을 찾을 수 있지만, explicit 방식을 사용하면 조사 대상을 전체 블록 중 가용 블록으로 좁힐 수 있어 implicit 방식을 사용 할 때 보다 빠르다.

 

free 블록을 추가하는 알고리즘으로는 LIFO를 채택한다.

반환하는 블록을 리스트의 맨 앞에 끼워넣는 방식이다.

 

 

 

 

 

 

explicit 구현에서 사용할 매크로이다. implicit에서 사용한 매크로와 유사하니 새로운 매크로들만 살펴보자.

 

NEXT_FREEP : bp를 기준으로 다음 가용 블록의 위치를 계산한다. (lvalue)

PREV_FREEP: bp를 기준으로 이전 가용 블록의 위치를 계산한다. (lvalue)

 

NEXT_FREE_BLKP : bp를 기준으로 다음 가용 블록의 위치를 계산한다.

PREV_FREE_BLKP : bp를 기준으로 이전 가용 블록의 위치를 계산한다.

 

 

 

1. extend_heap 함수 구현

 

 

 

 

 

extend_heap 함수는 implicit에서 작성한 코드와 유사하다.

 

정렬을 위해 확장하는 크기를 8의 배수로 설정한다.

이 때 블록의 최소 크기인 24바이트보다 작다면 24로 설정해준다. (오류 방지)

 

이후 mem_sbrk 함수로 힙의 크기를 size만큼 늘리고 bp를 새로 만들어진 공간의 끝부분에 위치시킨다.

 

PUT 매크로를 사용해 free 블록의 header와 footer를 설정하고 에필로그의 위치를 다시 설정한다. (bp 다음 블록이 에필로그 블록이다)

 

반환하기 전에 coalesce 함수를 호출해 가용 리스트를 관리 해 준다.

 

 

 

coalesce 함수를 구현하자.

 

 

 

 

 

 

 

 

implicit에서 작성한 함수와 비슷하지만, 현재 블록의 양옆에 가용 블록이 있다면 해당 블록을 가용 리스트에서 제거한 후 블록을 결합하는 부분에서 차이가 있다.

 

총 4가지 경우에 대해 각각 살펴보자.

 

다음 블록만 가용 블록인 경우 다음 블록을 현재 블록과 합치고 다음 블록을 리스트에서 제거한다.

 

이전 블록만 가용 블록인 경우 이전 블록을 현재 블록과 합치고 이전 블록을 리스트에서 제거한다.

 

두 블록 모두 가용 블록인 경우 둘 다 합치고 둘 다 제거한다.

 

두 블록 모두 할당된 블록인 경우 LIFO 방식으로 현재 블록을 가용 리스트의 맨 앞에 넣어준다.

 

가용 리스트에서 블록을 제거하는 함수도 따로 구현해서 사용하자.

 

 

 

 

 

 

remove_block 함수는 가용 블록을 가용 리스트에서 제거하는 작업을 수행한다.

 

리스트에서 제거하려는 블록의 이전 부분에 블록이 있으면 그 블록의 next 포인터가 제거하려는 블록의 다음 블록을 가리키도록 설정하고 제거하려는 블록의 다음 블록이 가지는 prev 포인터는 제거하려는 블록의 이전 블록을 가리키도록 설정한다.

 

제거하려는 블록의 이전 블록이 없으면 제거하려는 블록이 가용 리스트의 시작 부분이다.

가용 리스트의 시작 부분을 가리키는 포인터인 free_listp를 제거하려는 블록의 다음 블록을 가리키도록 설정하자.

 

이미 place 함수에서 할당된 블록으로 바꿔 놨기 때문에 블록을 수정할 필요는 없다.

 

 

 

2. mm_init 함수 구현

 

 

implicit으로 구현 할 때와는 다르게 next와 prev 포인터를 블록에 할당해 줘야 한다.

 

 

 

 

 

첫 부분은 패딩 부분이다. 0으로 채워준다.

 

다음은 블록의 header 부분이다. 블록의 최소 사이즈를 넣어주는데, LIFO 방식을 사용하기 때문에 이 블록이 가용 리스트의 끝 부분이 된다.

 

header를 설정한 후 prev / next 포인터와 footer를 넣어준 뒤 에필로그 블록을 초기화한다.

 

free_listp 포인터는 가용 리스트 포인터이다. 가용 리스트의 앞 부분을 가리키도록 설정하자.

 

 

 

3. find_fit 함수 구현

 

 

 

 

 

explicit 방식을 사용하면 가용 블록들만 검사 할 수 있어 전체를 검사해야 하는 implicit 방식보다 효과적이다.

 

가용 리스트의 처음 부분부터 탐색을 시작해 적당한 크기의 가용 블록을 찾으면 바로 반환한다.

 

가용 리스트의 끝에는 할당 비트 값이 0인 블록이 있다. 이 블록을 사용해 마지막 탐색을 감지하고 마지막까지 탐색했는데 찾지 못했다면 NULL을 반환한다.

 

 

 

4. place 함수 구현

 

 

할당할 위치와 할당할 크기를 인자로 받는다.

GET_SIZE 매크로로 현재 블록의 크기를 계산하고 계산한 위치를 할당된 영역으로 바꾼 후 가용 블록을 가용 리스트에서 제거한다.

 

 

 

 

5. malloc 함수 구현

 

 

 

 

 

malloc 함수는 implicit에서 구현한 함수와 비슷하다.

 

할당할 크기가 0 이하인 경우 무시하고 할당 크기가 적어도 최소 블록의 크기는 넘기도록 설정한다.

 

이 다음은 똑같다. find_fit함수로 적당한 블록을 찾고 찾은 경우 place 함수를 사용해 할당한다.

찾지 못한 경우 extend_heap 함수를 호출해 힙 공간의 크기를 늘린 후 place 함수로 공간을 할당한다.

 

 

 

6. realloc 함수 구현

 

 

 

 

 

realloc 함수는 implicit 함수에서 작성한 함수를 바탕으로 기능을 추가해서 구현한다.

 

크기가 음수이면 free 후 반환한다.

위치가 비어있으면 malloc으로 새로 할당한다.

 

realloc이 실패할 경우 0을 반환하고, 원래 크기와 동일하게 할당할 경우 원래 블록의 포인터를 그대로 반환한다.

 

크기가 줄여야 하는 경우 블록의 크기를 줄이고 동일한 크기의 블록을 만들어서 반환한다. (최소 블록의 크기보다 작은 경우 그대로 반환한다)

 

이 다음은 implicit과 동일하다. memcpy로 기존 내용을 옮기고 free를 호출한 후 새로운 블록을 반환한다.

 

 

이제 테스트를 돌릴 준비가 됐다. 바로 테스트 해 보자.

 

 

 

 

 

 

속도는 확실히 빠르지만 공간을 효과적으로 사용하지 않고 있다.