[malloc] segregated free list 방식 - 구현

segregated free list

---

• seg-list 방법은 free 블록들을 사이즈 에 대해 리스트를 각각 마련하는 방식이다. 서로다른 size 값이 n개라면, n개의 가용 리스트를 두어 각 가용 블럭들을 분류해서 기억하는 것이다.
• 사이즈 별로 연결리스트를 만들어야 하기 때문에 여러개의 연결리스트가 필요하며 여러개의 연결리스트 포인터가 존재한다.(힙에저장)
• 예를들어 37만큼의 메모리를 할당하고자 하면 위 그림에서 32~64 사이즈 연결리스트를 선택하게 되고 연결리스트에서 적절한 free블록을 찾게 된다. 위와 같이 대부분의 seg-list에서 연결리스트 사이즈는 2의 제곱수를 기준으로 한다.
• 해당 연결리스트에서 적절한 사이즈의 블록을 찾지 못하면, 다음 크기의 연결리스트로 넘어서 찾게된다. 이렇게 연결리스트 간의 탐색을 제외하고는 , 연결리스트를 사용하는 개념은 explicit과 동작이 유사하다.

 

 

📌code

 

💡관련 매크로 정의

#define SEGREGATED_SIZE (12) // 가용리스트의 크기를 나타냄

#define GET_ROOT(class) (*(void **)((char *)(heap_listp) + (WSIZE * class)))//class를 받아서 해당 가용 리스트의 루트 주소를 반환.

• ((char *)(heap_listp) + (WSIZE * class)) : 는 class에 해당하는 가용리스트의 루트 주소를 계산, class를 곱한 값에 heap_listp를 더함으로써 해당 클래스의 가용리스트의 시작 주소를 계산
• *(void**)는 포인터로 캐스트하여 해당 주소 값을 읽어온다.

 

💡힙, 분리가용리스트 생성

int mm_init(void) {
    // 초기 힙 생성,8워드
    if ((heap_listp = mem_sbrk((SEGREGATED_SIZE + 4) * WSIZE)) == (void *)-1)
        return -1;
    // 힙 시작 지점에 블록 크기(0)를 저장, 정렬패딩
    PUT(heap_listp, 0);
    // 프롤로그 헤더 블록 설정 (힙 크기와 할당 여부)
    PUT(heap_listp + (1 * WSIZE), PACK((SEGREGATED_SIZE + 2) * WSIZE, 1));

    // 가용 리스트 초기화
    for (int i = 0; i < SEGREGATED_SIZE; i++)
        PUT(heap_listp + ((2 + i) * WSIZE), NULL);

    // 프롤로그 푸터 블록 설정 (힙 크기와 할당 여부)
    PUT(heap_listp + ((SEGREGATED_SIZE + 2) * WSIZE), PACK((SEGREGATED_SIZE + 2) * WSIZE, 1));
    // 에필로그 끝 지점에 표시
    PUT(heap_listp + ((SEGREGATED_SIZE + 3) * WSIZE), PACK(0, 1));

    // heap_listp를 초기 힙 블록 뒤로 이동
    heap_listp += (2 * WSIZE);

    // 초기 확장 블록 생성
    if (extend_heap(4) == NULL)
        return -1;
    if (extend_heap(CHUNKSIZE / WSIZE) == NULL)
        return -1;

    return 0;
}

• 프롤로그 header와 footer 사이에 세그리게이트 리스트 들이 각 root블록의 주소를 담을 워드를 배정한다.
• 초기에는 가용리스트들이 존재하지 않으므로 null

 

💡가용블록에 할당하기

• mm_malloc과 extend_heap, place 함수는 explicit list와 동일하다.

 

💡가용블록 검색

• 가용블록을 탐색할 가용 리스트를 찾는다. ->get_class 함수 호출
• 위에서 찾은 가용 리스트의 루트블록 부터 탐색을 시작한다.
• 현재 필요한 크기인 asize 를 담을 수 있는  블록을 찾을 때까지 탐색을 이어간다.
• 가용 리스트에 적합한 블록이 존재하지 않으면 다음 가용리스트로 이동해서 탐색을 이어 나간다.

static void *find_fit(size_t asize) {
    int class = get_class(asize); // asize에 기반하여 할당할 클래스(class)를 결정
    void *bp = GET_ROOT(class);   // 현재 클래스의 가용 리스트 루트 포인터 가져옴

    while (class < SEGREGATED_SIZE) {
        // 현재 탐색하는 클래스가 범위 안에 있는 동안 반복
        bp = GET_ROOT(class); // 현재 클래스의 가용 리스트 루트 포인터 가져옴

        while (bp != NULL) {
            // 현재 클래스의 가용 블록들을 반복해서 탐색
            if ((asize <= GET_SIZE(HDRP(bp)))) {
                // 요청한 크기(asize)보다 크거나 같은 블록을 찾으면 반환
                return bp;
            }
            bp = GET_SUCC(bp); // 다음 가용 블록으로 이동
        }
        class += 1; // 다음 클래스로 이동
    }
    return NULL; // 적합한 블록을 찾지 못한 경우 NULL 반환
}

 

💡가용 리스트에서 제거

•  get_calss 함수 호출해서 제거할 블록이 있는 가용 리스트를 찾고 해당 가용 리스트에서 제거한다.

// 가용 리스트에서 bp에 해당하는 블록을 제거하는 함수
static void splice_free_block(void *bp)
{
    int class = get_class(GET_SIZE(HDRP(bp))); // 블록의 크기를 기반으로 클래스(class)를 결정

    if (bp == GET_ROOT(class)) {
        // 분리하려는 블록이 free_list 맨 앞에 있는 블록이면 (이전 블록이 없음)
        GET_ROOT(class) = GET_SUCC(GET_ROOT(class)); // 다음 블록을 가용 리스트의 루트로 변경
        return;
    }

    // 이전 블록의 SUCC을 다음 가용 블록으로 연결
    GET_SUCC(GET_PRED(bp)) = GET_SUCC(bp);

    // 다음 블록의 PRED를 이전 블록으로 변경
    if (GET_SUCC(bp) != NULL) {
        // 다음 가용 블록이 있는 경우에만
        GET_PRED(GET_SUCC(bp)) = GET_PRED(bp);
    }
}

 

💡가용 리스트에 추가

• 새로운 가용 블록을 적합한 가용 리스트에 추가한다.

// 적합한 가용 리스트를 찾아서 맨 앞에 현재 블록을 추가하는 함수
static void add_free_block(void *bp)
{
    int class = get_class(GET_SIZE(HDRP(bp))); // 블록의 크기를 기반으로 클래스(class)를 결정

    GET_SUCC(bp) = GET_ROOT(class); // 현재 블록의 다음 가용 블록을 현재 클래스의 가용 리스트 루트로 설정

    if (GET_ROOT(class) != NULL) {
        // 가용 리스트에 블록이 이미 존재하는 경우에만 아래 코드를 실행
        GET_PRED(GET_ROOT(class)) = bp; // 가용 리스트의 루트였던 블록의 이전 블록을 현재 추가한 블록으로 연결
    }

    GET_ROOT(class) = bp; // 현재 블록을 가용 리스트의 새로운 루트로 설정
}

 

💡적합한 가용리스트 탐색

• 첫번쨰 가용 리스트의 최소 크기는 블록의 최소 크기인 16byte로 설정하고, 다음 단계로 넘어갈수록 최소 크기가 이전 가용 리스트의 2배가 될 때 현재 size에 적합한 가용 리스트를 찾는다.

// 주어진 크기에 적합한 클래스를 찾는 함수
int get_class(size_t size)
{
    if (size < 16) // 최소 블록 크기는 16바이트
        return -1; // 잘못된 크기, 오류 반환

    // 클래스별 최소 크기를 저장하는 배열
    size_t class_sizes[SEGREGATED_SIZE];
    class_sizes[0] = 16;

    // 주어진 크기에 적합한 클래스 검색
    for (int i = 0; i < SEGREGATED_SIZE; i++)
    {
        // 클래스별 최소 크기를 2배씩 증가시켜 배열에 저장
        if (i != 0)
            class_sizes[i] = class_sizes[i - 1] << 1;

        // 주어진 크기가 현재 클래스의 최소 크기 이하인 경우, 해당 클래스 반환
        if (size <= class_sizes[i])
            return i;
    }

    // 주어진 크기가 마지막 클래스의 범위를 넘어갈 경우, 마지막 클래스로 처리
    return SEGREGATED_SIZE - 1;
}

 

💡반환하기와 재할당하기는 explit list와 동일하다.