malloc() 및 free() 구현 — 큰 블록 분할

이 시리즈의 이전 게시물에서 재사용할 메모리 블록을 선택하는 순서에 따라 메모리 소비가 어떻게 늘어나거나 줄어들 수 있는지 알아보았고, 이를 방지하기 위해 기능을 변경했습니다. 쓰레기. 그러나 우리는 훨씬 더 심각한 또 다른 문제를 해결해야 합니다. 때로는 매우 큰 메모리 블록이 여러 개의 작은 블록이 사용할 수 있는 공간을 차지할 수 있습니다. 큰 메모리 덩어리를 할당하고 할당을 취소한 다음 훨씬 작은 블록 두 개를 할당하는 아래 사례를 고려해보세요.

void *ptr1 = abmalloc(128);
void *ptr2 = abmalloc(8);
abfree(ptr1);
void *ptr3 = abmalloc(8);
void *ptr4 = abmalloc(8);

여기에는 사용 가능한 128바이트 메모리 블록이 있는데, 8바이트 블록만 할당하면 128바이트를 모두 사용할 수 없게 됩니다. 또 다른 8바이트 블록을 할당하면 힙이 다시 커져야 합니다. 이는 메모리를 효율적으로 사용하는 것이 아닙니다.

이 경우에는 두 가지 인기 있는 솔루션이 있습니다. 한 가지 더 효율적인 방법은 bins를 사용하는 것입니다: 블록을 크기별로 그룹화하는 목록입니다. 이는 더 정교하고 효율적인 접근 방식이지만 더 복잡합니다. 더 간단한 또 ​​다른 옵션은 큰 블록을 찾아서 더 작은 블록으로 분할하는 것입니다. 우리는 이 접근 방식을 따를 것입니다.

하지만 기억하세요. 단순하다고 해서 단순하다는 뜻은 아닙니다 ;-)

초기 리팩토링

시작하기 전에 간단한 리팩토링을 해보겠습니다. 현재 header_new() 함수는 두 가지 작업을 수행합니다. 새 블록에 더 많은 메모리를 할당하고 헤더를 초기화하여 이전 블록에 대한 메타데이터와 포인터를 설정합니다. 헤더를 초기화하는 부분이 유용할 것 같으니 추출해보겠습니다. 가독성을 높이기 위해 두 가지 새로운 기능을 만들겠습니다.

• 초기화된 블록을 이전 및 다음 블록에 "플러그"하는 header_plug() 함수
• 블록 메타데이터의 초기 값(크기 및 가용성)을 설정하는 header_init() 함수.

모습은 다음과 같습니다.

void header_init(Header *header, size_t size, bool available) {
    header->size = size;
    header->available = available;
}

void header_plug(Header *header, Header *previous, Header *next) {
    header->previous = previous;
    if (previous != NULL) {
        previous->next = header;
    }
    header->next = next;
    if (next != NULL) {
        next->previous = header;
    }
}

이제 새로운 기능을 사용하려면 header_new()를 수정하면 됩니다.

Header *header_new(Header *previous, size_t size, bool available) {
    Header *header = sbrk(sizeof(Header) + size);
    header_init(header, size, available);
    header_plug(header, previous, NULL);
    return header;
}

(또한 abmalloc() 함수에서 last->previous->next = last; 행을 제거할 수 있습니다. 이제 header_plug()가 이를 처리하기 때문입니다.)

블록 분할

이러한 도구를 사용하여 header_split() 함수를 만들어 보겠습니다. 헤더와 필요한 최소 크기가 주어지면 이 함수는 원본 블록이 다음을 포함할 만큼 충분히 큰 경우 메모리 블록을 두 개로 분할합니다

• 필요한 사이즈
• 새 블록의 새 헤더
• 약간의 추가 메모리.

먼저 블록이 충분히 큰지 확인합니다.

Header *header_split(Header *header, size_t size) {
    size_t original_size = header->size;
    if (original_size >= size + sizeof(Header)) {

이 조건이 충족되면 블록을 분할합니다. 먼저 abmalloc에서 요청한 헤더 크기와 공간을 빼서 현재 블록의 크기를 줄입니다.

void *ptr1 = abmalloc(128);
void *ptr2 = abmalloc(8);
abfree(ptr1);
void *ptr3 = abmalloc(8);
void *ptr4 = abmalloc(8);

이렇게 하면 현재 블록 뒤에 메모리 공간이 남게 되며, 이를 사용하여 새 블록을 생성하게 됩니다. 우리는 이 새로운 블록에 대한 포인터를 계산합니다:

void header_init(Header *header, size_t size, bool available) {
    header->size = size;
    header->available = available;
}

void header_plug(Header *header, Header *previous, Header *next) {
    header->previous = previous;
    if (previous != NULL) {
        previous->next = header;
    }
    header->next = next;
    if (next != NULL) {
        next->previous = header;
    }
}

이제 새 블록에 대한 포인터가 있으므로 header_init()를 사용하여 헤더를 초기화합니다.

Header *header_new(Header *previous, size_t size, bool available) {
    Header *header = sbrk(sizeof(Header) + size);
    header_init(header, size, available);
    header_plug(header, previous, NULL);
    return header;
}

그리고 header_plug()를 사용하여 새 블록을 이전 및 다음 블록에 연결합니다.

Header *header_split(Header *header, size_t size) {
    size_t original_size = header->size;
    if (original_size >= size + sizeof(Header)) {

원래 블록이 마지막 블록이었다면 이제 새 블록이 마지막 블록이 되므로 마지막 포인터를 업데이트합니다.

header->size = original_size - size - sizeof(Header);

마지막으로 새 블록을 반환합니다.

Header *new_header = header + sizeof(Header) + header->size;

원래 블록이 충분히 크지 않으면 단순히 원래 블록을 반환합니다.

header_init(new_header, size, true);

abmalloc() 업데이트 중

이제 abmalloc() 함수로 돌아가서 사용 가능한 블록을 찾은 위치에서 header_split()을 호출하여 분할을 시도하면 됩니다.

header_plug(new_header, header, header->next);

블록을 분할할 수 있으면 새 블록이 반환됩니다. 그렇지 않으면 원래 블록이 유지되고 이전과 같이 반환됩니다.

블록 분할에 대한 참고 사항

원래 블록의 끝 부분에 새 블록을 생성했다는 점에 유의하세요. 처음에 생성할 수도 있었지만 마지막에 새로운 사용 블록을 생성함으로써 새로운 무료 블록은 이전 블록과 더 가깝게 유지됩니다. 이렇게 하면 다음에 abmalloc()이 호출될 때 먼저 발견됩니다.

큰 메모리 블록을 분할하는 것은 한 단계 발전된 것이지만 반대의 문제도 있습니다. 작은 메모리 블록으로 인해 조각화가 발생할 수 있고, 더 큰 요청으로 인해 힙이 커질 수 있습니다. 다음 게시물에서 이 문제를 해결하는 방법을 살펴보겠습니다.

위 내용은 malloc() 및 free() 구현 — 큰 블록 분할의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!