Daftar Memori Bebas dan Penggunaan Ulang
Lacak dan gunakan kembali blok.
Daftar Memori Bebas dan Penggunaan Ulang adalah pelajaran C Academy gratis di CoddyKit. Ini adalah pelajaran 3 dari 4. Kamu bisa membaca pelajaran lengkapnya di bawah secara gratis — lalu praktikkan langsung di browser dengan editor kode bawaan dan tutor AI 24/7. Ini adalah bagian dari jalur belajar C Academy, dan progresmu tersinkronisasi di web dan aplikasi CoddyKit. Kursus C Academy mencakup 4 pelajaran total.
Melampaui Pengalokasi Bump
Untuk membebaskan blok individual dan menggunakannya kembali, kita memerlukan pencatatan. Daftar bebas adalah daftar tertaut berisi blok-blok yang tersedia, yang dicari oleh pengalokasi sebelum mengambil memori baru.
Setiap blok memiliki header agar pengalokasi dapat menemukan ukurannya dan tautan ke blok berikutnya dalam rantai.
Header Blok dengan Tautan
Kita memperluas header dengan pointer next dan penanda free. Keduanya mengubah kumpulan memori kita menjadi daftar blok yang dapat ditelusuri.
Payload berada tepat setelah header di dalam memori.
typedef struct block {
size_t size; /* payload bytes */
int free; /* 1 if reusable */
struct block *next; /* next block in pool */
} block_t;Menginisialisasi Satu Blok Bebas Besar
Saat dimulai, seluruh kumpulan memori merupakan satu blok bebas yang sangat besar. Saat alokasi berlangsung, kita membaginya; saat pembebasan berlangsung, kita menandai blok agar dapat digunakan kembali.
Kepala daftar adalah blok awal ini, yang mencakup seluruh arena.
static unsigned char pool[4096];
static block_t *head;
void heap_init(void) {
head = (block_t *)pool;
head->size = sizeof(pool) - sizeof(block_t);
head->free = 1;
head->next = NULL;
}Pencarian First-Fit
Strategi penggunaan kembali yang paling sederhana adalah first-fit: telusuri daftar dan kembalikan blok bebas pertama yang ukurannya cukup. Strategi ini cepat dan cenderung menempatkan blok-blok kecil di bagian depan.
Alternatifnya adalah best-fit (blok terkecil yang mencukupi) dan worst-fit, yang menukar kecepatan dengan perilaku fragmentasi.
block_t *first_fit(size_t size) {
for (block_t *b = head; b; b = b->next)
if (b->free && b->size >= size)
return b;
return NULL;
}Mengalokasikan dari Blok Bebas
Setelah menemukan kecocokan, kita menandainya sebagai digunakan dan mengembalikan pointer tepat setelah header. Untuk saat ini kita menyerahkan seluruh blok; pembagian akan dibahas pada pelajaran berikutnya.
Pointer yang dikembalikan adalah block + 1, sehingga header tersembunyi dari pemanggil.
void *my_alloc(size_t size) {
block_t *b = first_fit(size);
if (!b) return NULL;
b->free = 0;
return (void *)(b + 1);
}Membebaskan Blok
Untuk membebaskan blok, mundur dari pointer pengguna ke header-nya lalu ubah penanda free. Blok tersebut kini dapat digunakan kembali pada pencarian berikutnya.
Mendapatkan kembali header dari payload menggunakan trik pointer satu langkah yang sama seperti sebelumnya.
void my_free(void *p) {
if (!p) return;
block_t *b = (block_t *)p - 1;
b->free = 1;
}Menggabungkan Blok Bebas yang Berdampingan
Pembebasan saja membuat kumpulan memori dipenuhi blok-blok bebas kecil. Coalescing menggabungkan blok yang dibebaskan dengan blok berikutnya jika blok tersebut juga bebas, sehingga membentuk kembali wilayah yang lebih besar dan berurutan.
Hal ini mengatasi fragmentasi eksternal agar permintaan besar di masa mendatang tetap dapat dipenuhi.
void coalesce(block_t *b) {
if (b->next && b->next->free) {
b->size += sizeof(block_t) + b->next->size;
b->next = b->next->next;
}
}Demo Daftar Bebas yang Dapat Dijalankan
Program lengkap ini menginisialisasi kumpulan memori, mengalokasikan dua blok, membebaskan blok pertama, lalu menggunakannya kembali untuk permintaan yang lebih kecil, membuktikan bahwa daftar bebas berfungsi.
#include <stdio.h>
#include <stddef.h>
typedef struct block { size_t size; int free; struct block *next; } block_t;
static unsigned char pool[1024];
static block_t *head;
void heap_init(void){ head=(block_t*)pool; head->size=sizeof(pool)-sizeof(block_t); head->free=1; head->next=NULL; }
block_t *first_fit(size_t s){ for(block_t *b=head;b;b=b->next) if(b->free&&b->size>=s) return b; return NULL; }
void *my_alloc(size_t s){ block_t *b=first_fit(s); if(!b) return NULL; b->free=0; return (void*)(b+1); }
void my_free(void *p){ if(!p) return; ((block_t*)p-1)->free=1; }
int main(void){
heap_init();
int *a = my_alloc(sizeof(int));
*a = 7;
printf("a=%d free=%d\n", *a, head->free);
my_free(a);
printf("after free: free=%d\n", head->free);
return 0;
}Biaya Pencarian
Daftar bebas tertaut tunggal membuat alokasi memiliki kompleksitas O(n) terhadap jumlah blok. Dengan banyak alokasi, proses ini menjadi lambat.
Pengalokasi nyata menggunakan daftar bebas terpisah (bin berdasarkan ukuran) atau pohon agar pencarian mendekati O(1). Prinsip penggunaan kembali tetap sama.
/* Segregated lists: one bucket per size class */
static block_t *bins[NUM_SIZE_CLASSES];
/* lookup goes straight to the right bucket */Pembebasan Ganda dan Kerusakan Data
Menandai sebuah blok sebagai bebas dua kali, atau menulis melewati ukurannya, akan merusak header di sebelahnya. Pencarian berikutnya kemudian mengikuti pointer next yang berisi data sampah dan mengalami crash.
Inilah alasan bug memori di C sangat berbahaya: metadata milik pengalokasi berada tepat di samping data Anda.
Menyatukan Penggunaan Kembali
Pengalokasi daftar bebas yang berfungsi memerlukan inisialisasi, strategi pencocokan, alokasi, pembebasan, dan coalescing. Dengan semua ini, memori berputar melalui kumpulan memori, bukan terus bertambah tanpa batas.
Penyempurnaan yang tersisa adalah membagi blok yang terlalu besar dan memenuhi penyelarasan, yang menjadi topik pelajaran terakhir.
Pemeriksaan Singkat
Pikirkan apa yang mencegah daftar bebas terfragmentasi parah.
Ringkasan
Daftar bebas menautkan blok melalui header sehingga alokasi individual dapat dibebaskan dan digunakan kembali. Pencarian first-fit menemukan blok, pembebasan mengubah penanda, dan coalescing menggabungkan blok-blok tetangga untuk melawan fragmentasi.
Pencarian linear memiliki kompleksitas O(n); pengalokasi produksi mengelompokkan blok berdasarkan ukuran demi kecepatan. Selanjutnya kita menambahkan pembagian dan penyelarasan.
Belajar C dengan tutor AI — gratis
Tulis dan jalankan kode asli di browser kamu, dapatkan bantuan instan dari tutor AI 24/7, dan lanjutkan di mana kamu tinggalkan di web atau aplikasi.
- Kursus
- 39
- Pelajaran
- 144
Pertanyaan yang Sering Diajukan
Apakah pelajaran “Daftar Memori Bebas dan Penggunaan Ulang” gratis?
Ya — teks lengkap “Daftar Memori Bebas dan Penggunaan Ulang” gratis dibaca di sini di web. Untuk praktiknya secara interaktif (editor kode bawaan dan tutor AI 24/7) dan buka sisa kursus C Academy, upgrade ke CoddyKit PRO. Kursus C Academy mencakup 4 pelajaran total.
Apa yang akan aku pelajari di “Daftar Memori Bebas dan Penggunaan Ulang”?
Lacak dan gunakan kembali blok. Kamu berlatih C Academy dengan kode praktik yang langsung kamu jalankan di browser, dan tutor AI 24/7 menjawab pertanyaanmu saat kamu mengerjakan pelajaran ini.
Apakah aku perlu pengalaman untuk memulai C Academy?
Tidak diperlukan pengalaman sebelumnya. C Academy di CoddyKit dirancang untuk pemula hingga pelajar tingkat lanjut, jadi kamu bisa memulai di sini atau dari awal dan belajar sesuai kecepatan kamu sendiri. Ini adalah pelajaran 3 dari 4.
Berapa lama pelajaran “Daftar Memori Bebas dan Penggunaan Ulang” memakan waktu?
Sebagian besar pelajaran CoddyKit memakan waktu sekitar 5–10 menit. Setiap pelajaran ringkas dan interaktif, jadi kamu membuat kemajuan stabil dan melanjutkan dari tempat kamu tinggalkan di web dan aplikasi.
Bisakah aku menulis dan menjalankan kode dalam pelajaran C Academy ini?
Ya. Setiap pelajaran C Academy menyertakan editor kode bawaan, jadi kamu menulis dan menjalankan kode nyata langsung di browser dan mendapatkan umpan balik AI instan — tidak diperlukan penyiapan lokal.
Semua pelajaran dalam kursus ini
- Cara Kerja malloc
- Alokator Bump Sederhana
- Daftar Memori Bebas dan Penggunaan Ulang
- Penyelarasan dan Pemisahan