Implémentation de malloc() et free() — ancienne mémoire réutilisée en premier

이 시리즈의 이전 포스트에서는 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; 
}

Adjustments in abfree()

The function abfree() basically maintains the same structure, but now we must handle some edge cases. When we free blocks at the top of the heap, a new block becomes the last one, as we already do in this snippet:

    last = header->previous;
    brk(header)

Here, the pointer header references the last non-null block available on the stack. We have two possible scenarios:

1. the current block has a previous block, which will become the new last block. In this case, we should set the pointer nextof this block to NULL.
2. the current block does not have a previous block (i.e., it is the first and oldest block). When it is freed, the stack is empty. In this case, instead of trying to update a field of a non-existent block, we simply set it first to NULL, indicating that there are no more allocated blocks.

Here is how we implement it:

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

Conclusion

Our functions abmalloc() and abfree() now look like this:

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;
  }
 }

This change allows us to save considerably more memory. There are, however, still problems to solve. For example, consider the following scenario: we request the allocation of a memory block of 8 bytes, and abmalloc() reuse a block of, say, 1024 bytes. There is clearly a waste.

We will see how to solve this in the next post.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!