malloc() 및 free() 구현 - 오래된 메모리가 먼저 재사용됨

malloc() と free() の実装に関するこのシリーズの前回の 投稿 では、新しいブロックを解放することでメモリ ブロックを再利用し、ヒープを削減する方法を示しました。ただし、現在の関数には微妙な問題があります。新しいブロックの再利用が優先されるため、時間の経過とともにメモリ消費量が増加する可能性があります。なぜこのようなことが起こるのでしょうか?分解してみましょう。

最近のブロックを再利用してヒープを削減

次のシナリオを考えてみましょう。まず、4 つのメモリ ブロックを割り当てます。

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

メモリ構造は次のように視覚化できます:

さて、最初と 3 番目のブロックを解放します…

abfree(ptr1);
abfree(ptr3);

…次の構造になります:

次に、同じサイズの別のブロックを割り当てます。

void *ptr5 = abmalloc(8);

関数 abmalloc() が最新の空きブロックの検索を開始すると、先頭のブロックが再利用されます。ここで最後のブロックを解放するとします:

ここで最後のブロックを解放すると…

abfree(ptr4);

…前のブロックはもう空いていないため、ヒープ サイズを 8 バイト ブロック 1 つだけ減らすことができます。

古いブロックの再利用

ここで、同じシナリオを想像してください。ただし、変更が 1 つあります。関数は、最も古いブロックから空きブロックの検索を開始します。初期構造は同じになります…

…そして再び最初と 3 番目のメモリ ブロックを解放します:

今回は、最初のブロックが再利用されます:

最後のブロックを解放すると、先頭に 2 つの空きブロックができ、ヒープを 8 バイト ブロック 2 つ減らすことができます。

この例は、新しいブロックを優先することで、古い未使用のブロックが蓄積され、メモリが浪費され、不必要なヒープの増加につながることを示しています。解決策は、古いブロックの再利用を優先して検索戦略を変更することです。

古いブロックの優先の実装

この問題を解決するには、ヘッダー内の次のブロックへのポインターを追加することから始めます。また、最初のブロックへのグローバル ポインターも作成します。これにより、そこから検索を開始できます。

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

2 つの異なる状況でヘッダーを持つメモリ ブロックを作成するので、小さなリファクタリングを行いましょう。ヘッダーを割り当てて初期化するヘルパー関数にこのロジックを抽出します (フィールド nextwith 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 = 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);

ここで、最後のブロック (割り当て後、最後から 2 番目) を調整する必要があります。 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.

위 내용은 malloc() 및 free() 구현 - 오래된 메모리가 먼저 재사용됨의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!