C Academy · บทเรียน

รายการหน่วยความจำว่างและการนำกลับมาใช้

ติดตามและนำบล็อกกลับมาใช้ใหม่

รายการหน่วยความจำว่างและการนำกลับมาใช้ เป็นบทเรียน C Academy ฟรีบน CoddyKit นี่คือบทเรียนที่ 3 จากทั้งหมด 4 บทเรียน คุณสามารถอ่านบทเรียนทั้งหมดด้านล่างฟรี — จากนั้นลองปฏิบัติด้วยตัวคุณเองในเบราว์เซอร์พร้อมตัวแก้ไขโค้ดในตัวและติวเตอร์ AI ตลอด 24/7 บทเรียนนี้เป็นส่วนหนึ่งของเส้นทางการเรียน C Academy และความก้าวหน้าของคุณจะซิงค์ข้ามเว็บและแอป CoddyKit คอร์ส C Academy มีบทเรียนทั้งหมด 4 บทเรียน

ก้าวข้ามตัวจัดสรรแบบ Bump

หากต้องการคืนบล็อกแต่ละบล็อกและนำกลับมาใช้ใหม่ เราต้องมีข้อมูลกำกับรายการพื้นที่ว่างคือรายการเชื่อมโยงของบล็อกที่พร้อมใช้งาน ซึ่งตัวจัดสรรจะค้นหาก่อนขอหน่วยความจำใหม่

แต่ละบล็อกมีส่วนหัว เพื่อให้ตัวจัดสรรทราบขนาดและลิงก์ไปยังบล็อกถัดไปในสายโซ่

ส่วนหัวบล็อกพร้อมลิงก์

เราขยายส่วนหัวด้วยพอยน์เตอร์ next และแฟล็ก free เมื่อรวมกันแล้ว ส่วนเหล่านี้จะเปลี่ยนพูลของเราให้เป็นรายการบล็อกที่ไล่ดูได้

ส่วนข้อมูลจะอยู่ต่อจากส่วนหัวทันทีในหน่วยความจำ

typedef struct block {
    size_t size;          /* payload bytes */
    int free;             /* 1 if reusable */
    struct block *next;   /* next block in pool */
} block_t;

เริ่มต้นด้วยบล็อกว่างขนาดใหญ่หนึ่งบล็อก

เมื่อเริ่มต้น พูลทั้งหมดจะเป็นบล็อกว่างขนาดใหญ่เพียงบล็อกเดียว เมื่อมีการจัดสรร เราจะแยกบล็อกนี้ออก และเมื่อมีการคืนพื้นที่ เราจะทำเครื่องหมายบล็อกให้สามารถนำกลับมาใช้ใหม่

ส่วนหัวของรายการคือบล็อกเริ่มต้นนี้ ซึ่งครอบคลุมพื้นที่ทั้งหมดของอารีนา

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;
}

การค้นหาแบบ First-Fit

กลยุทธ์การนำกลับมาใช้ใหม่ที่ง่ายที่สุดคือแบบ first-fit โดยไล่ดูรายการแล้วคืนบล็อกว่างบล็อกแรกที่มีขนาดใหญ่พอ วิธีนี้รวดเร็วและมักเก็บบล็อกขนาดเล็กไว้ใกล้ต้นรายการ

ทางเลือกอื่นคือ best-fit ซึ่งเลือกบล็อกที่เล็กที่สุดที่พอใช้ และ worst-fit โดยแลกความเร็วกับลักษณะการเกิดพื้นที่แตกกระจาย

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;
}

การจัดสรรจากบล็อกว่าง

เมื่อพบบล็อกที่เหมาะสมแล้ว เราจะทำเครื่องหมายว่าถูกใช้งานและคืนพอยน์เตอร์ที่อยู่ถัดจากส่วนหัวทันที ในตอนนี้เราส่งมอบทั้งบล็อก โดยการแยกบล็อกจะกล่าวถึงในบทเรียนถัดไป

พอยน์เตอร์ที่คืนมาคือ block + 1 ซึ่งซ่อนส่วนหัวจากผู้เรียกใช้

void *my_alloc(size_t size) {
    block_t *b = first_fit(size);
    if (!b) return NULL;
    b->free = 0;
    return (void *)(b + 1);
}

การคืนบล็อก

เมื่อต้องการคืนพื้นที่ ให้ถอยจากพอยน์เตอร์ของผู้ใช้กลับไปยังส่วนหัว แล้วสลับแฟล็กว่าง บล็อกนั้นก็พร้อมให้ค้นหาเพื่อนำกลับมาใช้ใหม่ในครั้งถัดไป

การกู้คืนส่วนหัวจากส่วนข้อมูลใช้เทคนิคพอยน์เตอร์แบบเลื่อนหนึ่งตำแหน่งเดียวกับที่เราเห็นก่อนหน้านี้

void my_free(void *p) {
    if (!p) return;
    block_t *b = (block_t *)p - 1;
    b->free = 1;
}

การรวมบล็อกว่างที่อยู่ติดกัน

การคืนพื้นที่เพียงอย่างเดียวทำให้พูลเต็มไปด้วยบล็อกว่างขนาดเล็ก Coalescing จะรวมบล็อกที่คืนแล้วเข้ากับบล็อกถัดไปหากบล็อกนั้นก็ว่างเช่นกัน เพื่อสร้างบริเวณต่อเนื่องขนาดใหญ่ขึ้น

วิธีนี้ช่วยลดพื้นที่แตกกระจายภายนอก ทำให้คำขอขนาดใหญ่ในอนาคตยังได้รับการจัดสรรได้

void coalesce(block_t *b) {
    if (b->next && b->next->free) {
        b->size += sizeof(block_t) + b->next->size;
        b->next = b->next->next;
    }
}

ตัวอย่างรายการพื้นที่ว่างที่เรียกใช้ได้

โปรแกรมฉบับสมบูรณ์นี้เริ่มต้นพูล จัดสรรสองบล็อก คืนบล็อกแรก แล้วนำบล็อกนั้นกลับมาใช้กับคำขอที่เล็กลง เพื่อพิสูจน์ว่ารายการพื้นที่ว่างทำงานได้

#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;
}

ต้นทุนของการค้นหา

รายการพื้นที่ว่างแบบเชื่อมโยงรายการเดียวทำให้การจัดสรรมีความซับซ้อน O(n) ตามจำนวนบล็อก เมื่อมีการจัดสรรจำนวนมาก วิธีนี้จะช้าลง

ตัวจัดสรรจริงใช้รายการพื้นที่ว่างแยกตามกลุ่มขนาด หรือใช้ต้นไม้ เพื่อให้การค้นหาใกล้เคียง O(1) หลักการนำกลับมาใช้ใหม่ยังคงเหมือนเดิม

/* Segregated lists: one bucket per size class */
static block_t *bins[NUM_SIZE_CLASSES];
/* lookup goes straight to the right bucket */

การคืนพื้นที่ซ้ำและข้อมูลเสียหาย

การทำเครื่องหมายว่าบล็อกว่างซ้ำสองครั้ง หรือการเขียนเลยขนาดของบล็อก จะทำให้ส่วนหัวของบล็อกข้างเคียงเสียหาย จากนั้นการค้นหาครั้งถัดไปจะเดินตามพอยน์เตอร์ next ที่เป็นขยะและทำให้โปรแกรมหยุดทำงาน

นี่คือเหตุผลที่ข้อผิดพลาดเกี่ยวกับหน่วยความจำในภาษา C อันตรายมาก เพราะข้อมูลกำกับของตัวจัดสรรเองอยู่ติดกับข้อมูลของคุณ

ประกอบการนำกลับมาใช้ใหม่

ตัวจัดสรรแบบรายการพื้นที่ว่างที่ใช้งานได้ต้องมีการเริ่มต้น กลยุทธ์การค้นหาบล็อกที่เหมาะสม การจัดสรร การคืนพื้นที่ และการรวมบล็อก เมื่อมีส่วนเหล่านี้ หน่วยความจำจะหมุนเวียนอยู่ในพูลแทนที่จะขยายไปเรื่อย ๆ

การปรับปรุงที่เหลือคือการแยกบล็อกที่ใหญ่เกินไปและการจัดแนว ซึ่งเป็นหัวข้อของบทเรียนสุดท้าย

ตรวจสอบอย่างรวดเร็ว

ลองคิดดูว่าอะไรช่วยป้องกันไม่ให้รายการพื้นที่ว่างเกิดการแตกกระจายมากเกินไป

สรุปทบทวน

รายการพื้นที่ว่างเชื่อมโยงบล็อกผ่านส่วนหัว ทำให้สามารถคืนและนำการจัดสรรแต่ละรายการกลับมาใช้ใหม่ได้ การค้นหาแบบ first-fit จะค้นหาบล็อก การคืนพื้นที่จะสลับแฟล็ก และการรวมบล็อกจะรวมบล็อกข้างเคียงเพื่อลดการแตกกระจาย

การค้นหาเชิงเส้นมีความซับซ้อน O(n) ส่วนตัวจัดสรรสำหรับใช้งานจริงจะแบ่งกลุ่มตามขนาดเพื่อเพิ่มความเร็ว ต่อไปเราจะเพิ่มการแยกบล็อกและการจัดแนว

คำถามที่พบบ่อย

บทเรียน “รายการหน่วยความจำว่างและการนำกลับมาใช้” ฟรีหรือไม่

ใช่ — ข้อความเต็มของ “รายการหน่วยความจำว่างและการนำกลับมาใช้” ฟรีให้อ่านที่นี่บนเว็บ เพื่อปฏิบัติแบบโต้ตอบ (ตัวแก้ไขโค้ดในตัวและติวเตอร์ AI ตลอด 24/7) และปลดล็อคส่วนที่เหลือของคอร์ส C Academy ให้อัปเกรดเป็น CoddyKit PRO คอร์ส C Academy มีบทเรียนทั้งหมด 4 บทเรียน

คุณจะเรียนรู้อะไรในบทเรียน “รายการหน่วยความจำว่างและการนำกลับมาใช้”

ติดตามและนำบล็อกกลับมาใช้ใหม่ คุณปฏิบัติ C Academy ด้วยโค้ดที่ใช้งานได้จริงที่คุณเรียกใช้โดยตรงในเบราว์เซอร์ และติวเตอร์ AI ตลอด 24/7 ตอบคำถามของคุณขณะที่คุณไปผ่านบทเรียน

คุณต้องมีประสบการณ์ก่อนที่จะเริ่มเรียน C Academy หรือไม่

ไม่จำเป็นต้องมีประสบการณ์มาก่อน C Academy บน CoddyKit ออกแบบมาสำหรับผู้เริ่มต้นไปจนถึงผู้เรียนขั้นสูง คุณสามารถเริ่มต้นที่นี่หรือเริ่มจากตัวแรกและเรียนด้วยความเร็วของคุณเอง นี่คือบทเรียนที่ 3 จากทั้งหมด 4 บทเรียน

บทเรียน “รายการหน่วยความจำว่างและการนำกลับมาใช้” ใช้เวลานานแค่ไหน

บทเรียน CoddyKit ส่วนใหญ่ใช้เวลาประมาณ 5–10 นาที แต่ละบทเรียนจึงสั้นและเป็นแบบโต้ตอบ คุณสามารถก้าวหน้าอย่างต่อเนื่องและกลับมาเรียนต่อจากตรงที่เพิ่งหยุดบนเว็บและแอปได้เลย

ฉันเขียนและรันโค้ดในบทเรียน C Academy นี้ได้ไหม

ได้ บทเรียน C Academy ทุกบทมีตัวแก้ไขโค้ดในตัว คุณจึงเขียนและรันโค้ดจริงได้เลยในเบราว์เซอร์ และได้รับข้อเสนอแนะจาก AI ในทันที — ไม่ต้องติดตั้งในเครื่องของคุณ

บทเรียนทั้งหมดในหลักสูตรนี้

← กลับไปที่ C Academy