malloc() 및 free() 구현에 대한 이 시리즈의 이전 포스트에서 우리는 메모리 블록을 재사용하고 새로운 블록을 해제하여 힙을 줄이는 방법을 보여주었습니다. 그러나 현재 기능에는 미묘한 문제가 있습니다. 즉, 새로운 블록을 재사용하는 데 우선순위를 두므로 시간이 지남에 따라 메모리 소비가 증가할 수 있습니다. 왜 이런 일이 발생합니까? 분석해 보겠습니다.

최근 블록을 재사용하여 힙 감소

다음 시나리오를 고려해보세요. 먼저 4개의 메모리 블록을 할당합니다:

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

메모리 구조는 다음과 같이 시각화할 수 있습니다:

이제 첫 번째와 세 번째 블록을 공개합니다…

abfree(ptr1);
abfree(ptr3);

...다음과 같은 구조가 생성됩니다.

그런 다음 동일한 크기의 다른 블록을 할당합니다.

void *ptr5 = abmalloc(8);

abmalloc() 함수는 가장 최근의 사용 가능한 블록 검색을 시작하면서 맨 위에 있는 블록을 재사용합니다. 이제 마지막 블록을 해제하면:

이제 마지막 블록을 해제하면...

abfree(ptr4);

...이전 블록이 더 이상 사용 가능하지 않기 때문에 8바이트 블록 하나만으로 힙 크기를 줄일 수 있습니다.

오래된 블록의 재사용

이제 동일한 시나리오를 상상해 보십시오. 단, 한 가지만 수정하면 됩니다. 함수는 가장 오래된 것부터 사용 가능한 블록을 검색하기 시작합니다. 초기 구조는 동일할 것입니다...

...그리고 다시 첫 번째와 세 번째 메모리 블록을 해제합니다.

이번에는 첫 번째 블록이 재사용됩니다.

이제 마지막 블록을 해제하면 상단에 두 개의 사용 가능한 블록이 생기므로 힙을 두 개의 8바이트 블록으로 줄일 수 있습니다.

이 예는 새로운 블록에 우선권을 부여함으로써 사용되지 않은 오래된 블록을 축적하고 메모리를 낭비하며 불필요한 힙 증가로 이어지는 방법을 보여줍니다. 해결책은 검색 전략을 수정하여 오래된 블록의 재사용을 우선시하는 것입니다.

오래된 블록에 대한 우선권 구현

이 문제를 해결하기 위해 헤더의 다음 블록에 포인터를 추가하는 것부터 시작하겠습니다. 또한 첫 번째 블록에 대한 전역 포인터를 생성하여 해당 블록에서 검색을 시작할 수 있습니다.

typedef struct Header {
  struct Header *previous, *next;
  size_t size;
  bool available;
} Header;
Header *first = NULL;
Header *last = NULL;

두 가지 다른 상황에서 헤더가 있는 메모리 블록을 생성하므로 작은 리팩토링을 만들어 보겠습니다. 이 논리를 헤더를 할당하고 초기화하는 도우미 함수로 추출합니다(next 필드를 NULL로 설정하는 것을 포함):

Header *header_new(Header *previous, size_t size, bool available) {
  Header *header = sbrk(sizeof(Header)   size);
  header->previous = previous;
  header->next = NULL;
  header->size = size;
  header->available = false;
  return header;
}

이 새로운 함수를 사용하면 abmalloc() 내의 논리를 단순화할 수 있습니다.

void *abmalloc(size_t size) { 
  if (size == 0) { 
    return NULL; 
  } 
  Header *header = last; 
  while (header != NULL) { 
    if (header->available && (header->size >= size)) { 
      header->available = false; 
      return header   1; 
    } 
    header = header->previous; 
  } 
  last = header_new(last, size, false); 
  return last   1; 
}

이제 첫 번째 블록과 마지막 블록에 액세스할 수 있으며 블록이 주어지면 이전 블록과 다음 블록을 찾을 수 있습니다. 또한 첫 번째 블록에 대한 포인터가 null이면 아직 블록이 할당되지 않은 것입니다. 따라서 이 경우 블록을 즉시 할당하고 첫 번째와 마지막을 모두 초기화합니다.

void *abmalloc(size_t size) { 
  if (size == 0) { 
    return NULL; 
  } 
  if (first == NULL) { 
    first = last = header_new(NULL, size, false); 
    return first   1; 
  }

먼저 더 이상 NULL이 아니면 이미 할당된 블록이 있으므로 재사용 가능한 블록 검색을 시작합니다. 변수 header를 반복자로 계속 사용할 것이지만 가장 최근 블록부터 시작하는 대신 가장 오래된 블록부터 검색이 시작됩니다:

  Header *header = first;

반복할 때마다 이전 블록으로 돌아가는 대신 시퀀스의 다음 블록으로 진행합니다.

  while (header != NULL) { 
    if (header->available && (header->size >= size)) { 
      header->available = false; 
      return header   1; 
    } 
    header = header->next; 
  }

논리는 동일하게 유지됩니다. 충분한 크기의 사용 가능한 블록을 찾으면 반환됩니다. 그렇지 않고 목록을 탐색한 후 재사용 가능한 블록이 발견되지 않으면 새 블록이 할당됩니다:

  last = header_new(last, size, false);

이제 마지막 블록(할당 후 두 번째부터 마지막 ​​블록)을 조정해야 합니다. NULL을 가리켰지만 이제는 새 블록을 가리켜야 합니다. 이를 위해 이전 블록의 다음 필드를 새로운 마지막 블록으로 설정합니다:

  last->previous->next = last; 
  return last   1; 
}

abfree()의 조정

abfree() 함수는 기본적으로 동일한 구조를 유지하지만 이제 일부 극단적인 경우를 처리해야 합니다. 힙 상단의 블록을 해제하면 이 스니펫에서 이미 수행한 것처럼 새 블록이 마지막 블록이 됩니다.

    last = header->previous;
    brk(header)

여기서 포인터 헤더는 스택에서 사용할 수 있는 null이 아닌 마지막 블록을 참조합니다. 두 가지 가능한 시나리오가 있습니다:

1. 현재 블록에는 이전 블록이 있으며, 이는 새로운 마지막 블록이 됩니다. 이 경우 이 블록의 다음 포인터를 NULL로 설정해야 합니다.
2. 현재 블록에는 이전 블록이 없습니다(즉, 첫 번째이자 가장 오래된 블록입니다). 해제되면 스택은 비어 있습니다. 이 경우 존재하지 않는 블록의 필드를 업데이트하려고 시도하는 대신 먼저 NULL로 설정하여 더 이상 할당된 블록이 없음을 나타냅니다.

구현 방법은 다음과 같습니다.

  last = header->previous; 
  if (last != NULL) { 
    last->next = NULL; 
  } else { 
    first = NULL; 
  } 
  brk(header);

결론

abmalloc() 및 abfree() 함수는 이제 다음과 같습니다.

typedef struct Header {
  struct Header *previous, *next;
  size_t size;
  bool available;
} Header;

Header *first = NULL;
Header *last = NULL;

Header *header_new(Header *previous, size_t size, bool available) {
  Header *header = sbrk(sizeof(Header)   size);
  header->previous = previous;
  header->next = NULL;
  header->size = size;
  header->available = false;
  return header;
}

void *abmalloc(size_t size) {
  if (size == 0) {
    return NULL;
  }
  if (first == NULL) {
    first = last = header_new(NULL, size, false);
    return first   1;
  }
  Header *header = first;
  while (header != NULL) {
    if (header->available && (header->size >= size)) {
      header->available = false;
      return header   1;
    }
    header = header->next;
  }
  last = header_new(last, size, false);
  last->previous->next = last;
  return last   1;
}

void abfree(void *ptr) {
  if (ptr == NULL) {
   return;
  }
  Header *header = (Header*) ptr - 1;
  if (header == last) {
    while ((header->previous != NULL) && header->previous->available) {
      header = header->previous;
    }
    last = header->previous;
    if (last != NULL) {
      last->next = NULL;
    } else {
      first = NULL;
    }
    brk(header);
  } else {
   header->available = true;
  }
 }

이 변경을 통해 훨씬 더 많은 메모리를 절약할 수 있습니다. 그러나 아직 해결해야 할 문제가 있습니다. 예를 들어, 다음 시나리오를 고려해 보십시오. 8바이트의 메모리 블록 할당을 요청하고 abmalloc()은 1024바이트의 블록을 재사용합니다. 분명히 낭비가 있습니다.

다음 게시물에서 이 문제를 해결하는 방법을 살펴보겠습니다.