Senarai Bebas dan Guna Semula
Jejak dan guna semula blok.
Senarai Bebas dan Guna Semula ialah pelajaran C Academy percuma di CoddyKit. Ini ialah pelajaran 3 daripada 4. Anda boleh membaca keseluruhan pelajaran di bawah secara percuma — kemudian berlatih secara praktikal dalam pelayar menggunakan penyunting kod terbina dalam dan tutor kecerdasan buatan 24/7. Pelajaran ini merupakan sebahagian daripada laluan pembelajaran C Academy, dan kemajuan anda disegerakkan merentas web serta aplikasi CoddyKit. Kursus C Academy merangkumi sejumlah 4 pelajaran.
Melangkaui Pengagih Memori Bump
Untuk membebaskan block secara individu dan menggunakannya semula, kita memerlukan rekod pengurusan. Senarai bebas ialah senarai terpaut bagi block yang tersedia, yang dicari oleh pengagih sebelum mendapatkan memori baharu.
Setiap block membawa pengepala supaya pengagih dapat mencari saiznya dan memautkannya kepada block seterusnya dalam rantaian.
Pengepala block dengan Pautan
Kami melanjutkan pengepala dengan penuding next dan bendera free. Bersama-sama, kedua-duanya menukarkan kumpulan memori kita menjadi senarai block yang boleh dinavigasi.
Muatan mengikuti pengepala dengan serta-merta dalam memori.
typedef struct block {
size_t size; /* payload bytes */
int free; /* 1 if reusable */
struct block *next; /* next block in pool */
} block_t;Memulakan Satu block Bebas yang Besar
Semasa permulaan, seluruh kumpulan memori ialah satu block bebas yang besar. Apabila peruntukan berlaku, kami membahagikannya; apabila pembebasan berlaku, kami menandakan block sebagai boleh digunakan semula.
Kepala senarai ialah block awal ini yang meliputi 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;
}Carian first-fit
Strategi penggunaan semula yang paling mudah ialah first-fit: telusuri senarai dan kembalikan block bebas pertama yang cukup besar. Kaedah ini pantas dan cenderung mengekalkan block kecil berhampiran bahagian hadapan.
Alternatifnya ialah best-fit (block paling kecil yang mencukupi) dan worst-fit, yang menukar kelajuan dengan corak pemecahan.
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;
}Memperuntukkan daripada block Bebas
Setelah menemui padanan, kami menandakannya sebagai digunakan dan mengembalikan penuding tepat selepas pengepalanya. Buat masa ini kami menyerahkan seluruh block; pembahagian akan dibincangkan dalam pelajaran seterusnya.
Penuding yang dikembalikan ialah block + 1, lalu menyembunyikan pengepala daripada 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 block
Untuk membebaskan, undur daripada penuding pengguna ke pengepalanya dan tukar bendera bebas. Kini block itu layak digunakan semula dalam carian seterusnya.
Mendapatkan semula pengepala daripada muatan menggunakan helah penuding satu langkah yang sama seperti sebelum ini.
void my_free(void *p) {
if (!p) return;
block_t *b = (block_t *)p - 1;
b->free = 1;
}Menggabungkan block Bebas Bersebelahan
Pembebasan sahaja meninggalkan kumpulan memori yang dipenuhi block bebas kecil. Penggabungan mencantumkan block yang dibebaskan dengan block seterusnya jika block itu juga bebas, lalu membina semula kawasan bersebelahan yang lebih besar.
Ini mengurangkan pemecahan luaran supaya permintaan besar pada masa hadapan masih 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 Senarai Bebas yang Boleh Dijalankan
Program lengkap ini memulakan kumpulan memori, memperuntukkan dua block, membebaskan block pertama, kemudian menggunakannya semula untuk permintaan yang lebih kecil, membuktikan bahawa senarai 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;
}Kos Mencari
Satu senarai bebas terpaut bermakna peruntukan mengambil masa O(n) berdasarkan bilangan block. Dengan banyak peruntukan, proses ini menjadi perlahan.
Pengagih sebenar menggunakan senarai bebas terasing (bekas mengikut saiz) atau pepohon supaya carian menghampiri O(1). Prinsip penggunaan semula kekal sama.
/* Segregated lists: one bucket per size class */
static block_t *bins[NUM_SIZE_CLASSES];
/* lookup goes straight to the right bucket */Pembebasan Berganda dan Kerosakan
Menandakan sesuatu block sebagai bebas dua kali, atau menulis melepasi saiz block, merosakkan pengepala bersebelahan. Carian seterusnya kemudian mengikuti penuding next yang mengandungi data sampah lalu mengalami ranap.
Inilah sebabnya pepijat memori dalam C sangat berbahaya: metadata pengagih itu sendiri berada betul-betul di sebelah data anda.
Menyatukan Penggunaan Semula
Pengagih senarai bebas yang berfungsi memerlukan pemulaan, strategi padanan, peruntukan, pembebasan dan penggabungan. Dengan semua ini, memori berulang-alik melalui kumpulan memori dan bukannya berkembang tanpa henti.
Penambahbaikan yang masih diperlukan ialah membahagikan block yang terlebih besar dan mematuhi penjajaran, yang menjadi subjek pelajaran terakhir.
Semakan Pantas
Fikirkan perkara yang menghalang senarai bebas daripada mengalami pemecahan teruk.
Imbas Kembali
Senarai bebas memautkan block melalui pengepala supaya peruntukan individu boleh dibebaskan dan digunakan semula. Carian first-fit mencari block, pembebasan menukar bendera, dan penggabungan mencantumkan block bersebelahan untuk memerangi pemecahan.
Carian linear ialah O(n); pengagih pengeluaran mengasingkan block mengikut saiz demi kelajuan. Seterusnya kami menambah pembahagian dan penjajaran.
Pelajari C dengan tutor kecerdasan buatan — percuma
Tulis dan jalankan kod sebenar dalam pelayar anda, dapatkan bantuan segera daripada tutor kecerdasan buatan yang tersedia 24/7, dan sambung semula dari tempat anda berhenti di web atau dalam aplikasi.
- Kursus
- 39
- Pelajaran
- 144
Soalan Lazim
Adakah pelajaran “Senarai Bebas dan Guna Semula” percuma?
Ya — teks penuh “Senarai Bebas dan Guna Semula” boleh dibaca secara percuma di web ini. Untuk berlatih secara interaktif menggunakan penyunting kod terbina dalam dan tutor kecerdasan buatan 24/7, serta membuka kunci baki kursus C Academy, tingkat taraf kepada CoddyKit PRO. Kursus C Academy merangkumi sejumlah 4 pelajaran.
Apakah yang akan saya pelajari dalam “Senarai Bebas dan Guna Semula”?
Jejak dan guna semula blok. Anda berlatih C Academy menggunakan kod praktikal yang dijalankan terus dalam pelayar, manakala tutor kecerdasan buatan 24/7 menjawab soalan anda semasa anda mengikuti pelajaran.
Adakah saya memerlukan pengalaman untuk memulakan C Academy?
Tiada pengalaman terdahulu diperlukan. Pembelajaran C Academy di CoddyKit disusun untuk pelajar daripada peringkat pemula hingga lanjutan, jadi anda boleh bermula di sini atau dari awal dan belajar mengikut kadar anda sendiri. Ini ialah pelajaran 3 daripada 4.
Berapa lamakah pelajaran “Senarai Bebas dan Guna Semula” diambil?
Kebanyakan pelajaran CoddyKit mengambil masa kira-kira 5–10 minit. Setiap pelajaran ringkas dan interaktif, jadi anda boleh membuat kemajuan secara berterusan dan menyambung tepat dari tempat anda berhenti di web atau aplikasi.
Bolehkah saya menulis dan menjalankan kod dalam pelajaran C Academy ini?
Ya. Setiap pelajaran C Academy menyertakan penyunting kod terbina dalam, jadi anda boleh menulis dan menjalankan kod sebenar terus dalam pelayar serta menerima maklum balas kecerdasan buatan serta-merta — tanpa memerlukan persediaan setempat.
Semua pelajaran dalam kursus ini
- Cara malloc Berfungsi
- Peruntuk Bump Ringkas
- Senarai Bebas dan Guna Semula
- Penjajaran dan Pemisahan