명시적 가용 리스트 Explicit Free List
요소를 저장하기 위해 명시적으로 메모리 공간(Array, Linked List) 할당
장점 : 검색 속도가 빠르고 메모리 할당, 해제 쉬움
단점 : 내부 단편화 발생
free_list를 가리키는 2중 포인터 설정
free block들의 정보를 모아둔 리스트 헤더 : free_listp
📄 mm_init
/*
* mm_init - initialize the malloc package.
*/
int mm_init(void)
{
/* Create the initial empty heap */
if ((heap_listp = mem_sbrk(6 * WSIZE)) == (void *)-1) /* 메모리 할당 오류가 발생했으면 */
return -1;
PUT(heap_listp, 0); /* Alignment padding */
PUT(heap_listp + (1 * WSIZE), PACK(2 * DSIZE, 1)); /* Prologue, heap의 정렬 & heap의 sential역할(경계태그) */
/* 왜 NEXT를 앞으로? payload 자리를 찾아가는 코드로 구성되어 있기 때문에 해당 자리에서 바로 찾을 수 있는 곳에 NEXT를 둬서 최대한의 동작을 줄임 */
PUT(heap_listp + (2 * WSIZE), PACK(0, 0)); /* 프롤로그 NEXT NULL로 초기화. */
PUT(heap_listp + (3 * WSIZE), PACK(0, 0)); /* 프롤로그 PREV NULL로 초기화 */
PUT(heap_listp + (4 * WSIZE), PACK(2 * DSIZE, 1)); /* Prologue footer */
PUT(heap_listp + (5 * WSIZE), PACK(0, 1)); /* Epilogue header */
free_listp = heap_listp + DSIZE; /* 첫 가용블록의 payload */
// free_listp = heap_listp + 2 * DSIZE;
/* Extend the empty heap with a free block of CHUNKSIZE bytes */
if (extend_heap(CHUNKSIZE / WSIZE) == NULL)
return -1;
return 0;
}🔎 prologue header & footer에 2 * DSIZE를 할당한 이유
연결을 위한 여분의 공간이 필요.
🔎 next_free를 prev_free보다 header에 가깝게 배치한 이유
보통 다음 가용 블록을 탐색하는 일이 이전 가용 블록을 탐색하는 일보다 많기때문에 next(succ)를 prev보다 먼저 배치한 코드가 많다.
연결 리스트에 blcok 추가
/* LIFO - 반환되거나 분할로 생긴 가용 블록을 가용리스트 가장 앞에 추가 */
static void splice_in(void *bp)
{
PREV_FREE(bp) = NULL; // 이전 블록은 없으니 NULL 할당
NEXT_FREE(bp) = free_listp; // 현재 블록의 다음 가용 블록의 free_listp가 가리키는 포인터 할당
PREV_FREE(free_listp) = bp; // 가용 블록의 이전 가용 블록을 현재 블록을 가리키는 포인터 할당
free_listp = bp; // free_listp가 가리키는 블록으로 현재 블록을 가리키는 포인터 할당
}root : free_listp로 가용 연결리스트의 맨 앞을 가리킨다. 링크드 리스트의 head같은 역할.
null : 가용 연결 리스트에 맨 마지막을 의미한다. 링크드 리스트의 tail같은 역할.
LIFO 방식으로 가용 연결 리스트 맨앞에 새로운 가용블록 추가
연결 리스트에 block 제거
/* 가용 블록을 free list에서 삭제 */
void splice_out(void *bp)
{
if (bp) {
// 이전 가용블록 없음
if (PREV_FREE(bp)) {
NEXT_FREE(PREV_FREE(bp)) = NEXT_FREE(bp);
}
else {
free_listp = NEXT_FREE(bp);
}
if (NEXT_FREE(bp) != NULL) {
// 이후 가용 블록 없음
PREV_FREE(NEXT_FREE(bp)) = PREV_FREE(bp);
}
}
}만약, bp 이후 가용 블록이 없으면, NEXT_FREE(bp)가 NULL값이 되므로 오류가 발생할 수 있다.
따라서 전후로 가용블록이 있냐 없냐 조건에 따라 혹시 모를 예외처리를 해줘야 한다.
가용 블록 연결리스트 업데이트
📄 coalesce 함수
static void *coalesce(void *bp)
{
...
// Case 1
// 가용 블록 연결리스트 처리해 줄 작업 없음.
// Case 2
if (prev_alloc && !next_alloc) {
// 이전 블록 할당, 다음 블록 free
// 다음 블록 header에 접근
splice_out(NEXT_BLKP(bp)); // 미리 제거해 혹시 모를 포인터로 인한 오류 방지
...
}
// Case 3
else if(!prev_alloc && next_alloc) {
// 이전 블록 free, 다음 블록 할당
// 이전 블록 footer에 접근
splice_out(PREV_BLKP(bp));
...
}
// Case 4
else if(!prev_alloc && !next_alloc) {
// 이전 블록 free, 다음 블록 free
// 이전 블록 footer와 다음 블록 header에 접근
splice_out(NEXT_BLKP(bp));
splice_out(PREV_BLKP(bp));
...
}
splice_in(bp);
return bp;
}
📄 place 함수
static void place(void *bp, size_t asize)
{
...
splice_out(bp); /* 사용할 가용블록을 가용리스트에서 없애기 */
if ((csize - asize) >= (2 * DSIZE)) /* 분할의 가치가 있음 */
{
...
splice_in(bp); /* 분할하고 남은 가용블록 가용리스트에 추가 */
...
}
else /* 남은 가용 블록의 크기가 2*DSIZE보다 작으면 */
...
}
🔎 가용블록 제거 후, 가용블록 추가하는 이유
가용 블록 연결리스트에서 임의의 가용블록을 제거한 뒤, 추가 시키는 업데이트 작업을 진행할때는 예기치 못한 오류를 방지해야 한다.
가용 블록 연결리스트에서 정보를 업데이트 할 때는 반드시 splice_out(노드 제거)을 먼저 수행하고 splice_in(노드 추가)을 수행하는 것이 안전하다. 만약, 이 과정을 반대로 진행한다면, splice_out한 노드가 아직 가용블록 연결 리스트에 남아있지 않은 상태에서 splice_in을 시도하게 되어 노드가 중복되어 추가될 가능성이 있다.
first fit : 가용 블록 연결 리스트를 header부터 탐색해 메모리 할당 가능한 가용블록 발견시 메모리 할당.
공부 자료 : 컴퓨터 시스템 Computer Systems: A Programmer's Perspective by Randal E. Bryant David R. O'Hallaron 9장 가상 메모리
'CS(ComputerScience)' 카테고리의 다른 글
| tiny 웹서버 구현 (0) | 2023.04.19 |
|---|---|
| Network, 통신 Model (0) | 2023.04.19 |
| 묵시적 가용 리스트 Implicit Free List (1) | 2023.04.12 |
| 가상 메모리 (0) | 2023.04.12 |
| Memory allocation using explicit free block tracking and first-fit method (0) | 2023.04.11 |
