Melaksanakan malloc() dan free() — memori lama digunakan semula dahulu

Dalam siaran sebelumnya dalam siri ini tentang melaksanakan malloc() dan free(), kami menunjukkan cara mungkin untuk menggunakan semula blok memori dan mengurangkan timbunan dengan membebaskan blok yang lebih baharu. Walau bagaimanapun, fungsi semasa memperkenalkan isu halus: ia mengutamakan penggunaan semula blok yang lebih baharu, yang boleh membawa kepada peningkatan penggunaan memori dari semasa ke semasa. Mengapa ini berlaku? Mari pecahkannya.

Pengurangan timbunan dengan menggunakan semula blok terbaru

Pertimbangkan senario berikut. Pertama, kami memperuntukkan empat blok memori:

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

Struktur memori boleh digambarkan seperti ini:

Sekarang, kami mengeluarkan blok pertama dan ketiga…

abfree(ptr1);
abfree(ptr3);

…menghasilkan struktur berikut:

Kemudian kami memperuntukkan blok lain yang sama saiz:

void *ptr5 = abmalloc(8);

Apabila fungsi abmalloc() mula mencari blok percuma terbaharu, ia menggunakan semula blok di bahagian atas. Jika kami kini membebaskan blok terakhir:

Jika sekarang kami mengeluarkan blok terakhir…

abfree(ptr4);

…kita boleh mengurangkan saiz timbunan dengan hanya satu blok 8-bait, kerana blok sebelumnya tidak lagi percuma:

Guna semula blok lama

Sekarang, bayangkan senario yang sama, tetapi dengan satu pengubahsuaian: fungsi kami mula mencari blok percuma daripada blok tertua. Struktur awal adalah sama…

…dan sekali lagi kami membebaskan blok memori pertama dan ketiga:

Kali ini, blok pertama akan digunakan semula:

Kini, apabila kita membebaskan blok terakhir, kita akan mempunyai dua blok percuma di bahagian atas, membolehkan kita mengurangkan timbunan sebanyak dua blok 8 bait:

Contoh ini menggambarkan bagaimana, dengan memberi keutamaan kepada blok yang lebih baharu, kami akhirnya mengumpul blok lama yang tidak digunakan, membazirkan ingatan dan membawa kepada pertumbuhan timbunan yang tidak perlu. Penyelesaiannya ialah mengubah suai strategi carian, mengutamakan penggunaan semula blok lama.

Melaksanakan keutamaan untuk blok lama

Untuk menyelesaikan masalah ini, kita akan mulakan dengan menambahkan penunjuk ke blok seterusnya dalam pengepala. Kami juga akan membuat penunjuk global ke blok pertama, supaya kami boleh memulakan carian daripadanya:

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

Kami akan mencipta blok memori dengan pengepala dalam dua situasi berbeza, jadi mari buat pemfaktoran semula kecil: kami akan mengekstrak logik ini kepada fungsi pembantu yang memperuntukkan dan memulakan pengepala (termasuk menetapkan medan di sebelah 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;
}

Dengan fungsi baharu ini, kami boleh memudahkan logik dalam 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; 
}

Kini kami mempunyai akses kepada blok pertama dan terakhir, dan diberi satu blok, kami boleh mengetahui blok sebelumnya dan seterusnya. Kami juga tahu bahawa apabila penunjuk ke blok pertama adalah batal, tiada blok telah diperuntukkan lagi. Jadi dalam kes ini, kami akan memperuntukkan blok dengan serta-merta, dan memulakan kedua-dua yang pertama dan terakhir:

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

Jika pertama ia tidak lagi NULL, sudah ada blok yang diperuntukkan, jadi kami akan mula mencari blok boleh guna semula. Kami akan terus menggunakan pengepala pembolehubah sebagai iterator, tetapi bukannya bermula dengan blok terbaharu, carian akan bermula dari yang tertua:

  Header *header = first;

Pada setiap lelaran, kami akan mara ke blok seterusnya dalam turutan, bukannya pergi ke belakang ke blok sebelumnya:

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

Logiknya tetap sama: jika kita menemui blok yang tersedia dengan saiz yang mencukupi, ia dikembalikan. Jika tidak, jika tiada blok boleh guna semula ditemui selepas kami merentasi senarai, blok baharu akan diperuntukkan:

  last = header_new(last, size, false);

Sekarang, kita perlu melaraskan blok yang terakhir (selepas peruntukan, yang kedua kepada yang terakhir). Ia menunjuk ke NULL, tetapi kini ia harus menunjuk ke blok baharu. Untuk melakukan ini, kami menetapkan medan seterusnya blok sebelumnya kepada blok terakhir baharu:

  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.

Atas ialah kandungan terperinci Melaksanakan malloc() dan free() — memori lama digunakan semula dahulu. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!