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

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

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

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

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

さて、1ブロック目と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; 
}

abfree() での調整

関数 abfree() は基本的に同じ構造を維持しますが、いくつかの特殊なケースを処理する必要があります。このスニペットですでに行っているように、ヒープの先頭にあるブロックを解放すると、新しいブロックが最後のブロックになります。

最後 = ヘッダー->前; brk(ヘッダー)

    last = header->previous;
    brk(header)

ここで、ポインター ヘッダーは、スタック上で使用可能な最後の非 null ブロッ​​クを参照します。考えられるシナリオは 2 つあります:

現在のブロックには前のブロックがあり、それが新しい最後のブロックになります。この場合、このブロックの次のポインタを NULL に設定する必要があります。
現在のブロックには前のブロックがありません (つまり、最初で最も古いブロックです)。解放されると、スタックは空になります。この場合、存在しないブロックのフィールドを更新しようとする代わりに、最初にそのフィールドを NULL に設定し、これ以上割り当てられたブロックがないことを示します。

実装方法は次のとおりです:

最後 = ヘッダー->前; if (最後の != NULL) { 最後->次 = NULL; } それ以外 { 最初 = NULL; } brk(ヘッダー);

    last = header->previous;
    brk(header)

結論

関数 abmalloc() と abfree() は次のようになります:

typedef 構造体のヘッダー { 構造体ヘッダー *前、*次; size_t サイズ; ブール値が利用可能です。 ヘッダー。 ヘッダー *first = NULL; ヘッダー *last = NULL; Header *header_new(Header *previous、size_t サイズ、bool が利用可能) { ヘッダー *header = sbrk(sizeof(ヘッダー) サイズ); ヘッダー->前 = 前; ヘッダー->次 = NULL; ヘッダー->サイズ = サイズ; ヘッダー->利用可能 = false; ヘッダーを返します。 } void *abmalloc(size_t サイズ) { if (サイズ == 0) { NULL を返します。 } if (最初 == NULL) { 最初 = 最後 = header_new(NULL, サイズ, false); 最初の 1 を返します。 } ヘッダー *header = 最初; while (ヘッダー != NULL) { if (ヘッダー->利用可能 && (ヘッダー->サイズ >= サイズ)) { ヘッダー->利用可能 = false; ヘッダー 1 を返します。 } ヘッダー = ヘッダー->次; } last = header_new(last, size, false); 最後->前->次 = 最後; 最後の 1 を返します。 } void abfree(void *ptr) { if (ptr == NULL) { 戻る; } ヘッダー *header = (ヘッダー *) ptr - 1; if (ヘッダー == 最後) { while ((header->previous != NULL) && header->previous->available) { ヘッダー = ヘッダー->前; } 最後 = ヘッダー->前; if (最後の != NULL) { 最後->次 = NULL; } それ以外 { 最初 = NULL; } brk(ヘッダー); } それ以外 { ヘッダー->利用可能 = true; } }

    last = header->previous;
    brk(header)

この変更により、メモリを大幅に節約できます。しかし、解決すべき問題はまだ残っています。たとえば、次のシナリオを考えてみましょう。8 バイトのメモリ ブロックの割り当てを要求し、abmalloc() がたとえば 1024 バイトのブロックを再利用します。明らかに無駄があります。

次の投稿でこれを解決する方法を見ていきます。