C Academy · บทเรียน

malloc ทำงานอย่างไร

ฮีปและรายการหน่วยความจำว่าง

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

สิ่งที่ malloc ทำจริง ๆ

เมื่อคุณเรียก malloc(n) ไลบรารี C จะส่งพอยน์เตอร์ไปยังไบต์ที่ใช้งานได้อย่างน้อย n ไบต์ให้คุณ แต่ฮีปเป็นเพียงบริเวณหนึ่งของหน่วยความจำโพรเซสที่ตัวจัดสรรดูแลแทนคุณ

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

ฮีปมาจาก OS

ตัวจัดสรรไม่ได้สร้างหน่วยความจำขึ้นจากความว่างเปล่า แต่จะขอชิ้นหน่วยความจำขนาดใหญ่จากระบบปฏิบัติการผ่านการเรียกระบบ เช่น brk/sbrk หรือ mmap

จากนั้นจะแบ่งชิ้นหน่วยความจำเหล่านั้นเป็นบล็อกขนาดเล็กสำหรับการเรียก malloc ของคุณ การขอหน่วยความจำจากระบบปฏิบัติการมีต้นทุนสูง ตัวจัดสรรจึงขอหน่วยความจำครั้งละมาก ๆ และนำกลับมาใช้ใหม่

/* Conceptual: grow the heap by 4096 bytes */
void *base = sbrk(4096);
if (base == (void *)-1) {
    /* out of memory */
}

sbrk และจุดแบ่งโปรแกรม

sbrk(n) จะเลื่อน "จุดแบ่งโปรแกรม" ขึ้นไป n ไบต์ และส่งคืนจุดแบ่งเดิม บริเวณใหม่ที่ถูกเปิดเผยจะกลายเป็นพื้นที่ฮีปที่พร้อมใช้งาน

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

void *prev_break = sbrk(0);   /* current break */
sbrk(1024);                   /* grow by 1 KB */
/* prev_break now points to fresh memory */

ข้อมูลกำกับของบล็อก

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

พอยน์เตอร์ที่คุณได้รับจาก malloc จะชี้ไปยังตำแหน่ง หลัง ส่วนหัว ดังนั้นข้อมูลกำกับจึงถูกซ่อนไว้จากคุณ

typedef struct block {
    size_t size;
    int free;
    struct block *next;
} block_t;

พอยน์เตอร์ถัดจากส่วนหัว

เทคนิคที่ใช้กันทั่วไปคือการคำนวณทางเลขคณิตของพอยน์เตอร์ โดยพอยน์เตอร์ของผู้ใช้คือ header + 1 เมื่อมีพอยน์เตอร์ของผู้ใช้ ส่วนหัวจะอยู่ก่อนหน้านั้นหนึ่ง block_t

นี่คือวิธีที่ free(p) กู้คืนขนาดของบล็อกที่คุณจัดสรรไว้ได้ โดยไม่ต้องให้คุณส่งขนาดเข้าไป

block_t *hdr = (block_t *)user_ptr - 1;
printf("block size = %zu\n", hdr->size);

สาธิตโครงสร้างส่วนหัวขนาดเล็ก

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

ไม่มีการเรียก OS จึงสามารถทำงานได้ทุกที่

#include <stdio.h>
#include <stddef.h>

typedef struct { size_t size; int free; } block_t;
static char buffer[256];

int main(void) {
    block_t *h = (block_t *)buffer;
    h->size = 64;
    h->free = 0;
    void *payload = (char *)buffer + sizeof(block_t);
    printf("header bytes = %zu\n", sizeof(block_t));
    printf("payload offset = %ld\n", (long)((char *)payload - buffer));
    printf("size field = %zu\n", h->size);
    return 0;
}

แนวคิดรายการหน่วยความจำว่าง

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

เมื่อคุณเรียก free บล็อกจะถูกทำเครื่องหมายว่าว่างและส่งกลับไปยังรายการเพื่อใช้ใหม่ในภายหลัง ซึ่งช่วยหลีกเลี่ยงการขอหน่วยความจำจาก OS อีกครั้ง

block_t *find_free(block_t *head, size_t size) {
    block_t *b = head;
    while (b && !(b->free && b->size >= size))
        b = b->next;
    return b;
}

สิ่งที่ free ต้องทำ

free(p) จะค้นหาส่วนหัวของ p ทำเครื่องหมายว่าว่าง และในกรณีที่เหมาะสมจะรวมเข้ากับบล็อกว่างที่อยู่ติดกัน (การรวมบล็อก) เพื่อลดการกระจัดกระจาย

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

void my_free(void *p) {
    if (!p) return;
    block_t *hdr = (block_t *)p - 1;
    hdr->free = 1;
    /* real allocators coalesce neighbors here */
}

การกระจัดกระจาย

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

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

ข้อกำหนดด้านการจัดแนว

malloc ต้องส่งคืนหน่วยความจำที่จัดแนวได้เหมาะสมกับชนิดข้อมูลทุกชนิด ในระบบส่วนใหญ่ที่เป็น 64 บิต หมายถึงการจัดแนว 16 ไบต์ ซึ่งเป็นไปตาม max_align_t

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

#include <stdalign.h>
/* alignof(max_align_t) is the strictest required alignment */
size_t a = alignof(max_align_t);

นำทุกอย่างมาประกอบกัน

ดังนั้นตัวจัดสรรขั้นต่ำจึงต้องมี แหล่งหน่วยความจำ (บัฟเฟอร์แบบคงที่ sbrk หรือ mmap) ส่วนหัวประจำบล็อก กลยุทธ์สำหรับค้นหาพื้นที่ว่าง และการจัดการการจัดแนว

ในบทเรียนถัดไป เราจะสร้างส่วนประกอบเหล่านี้ ได้แก่ bump allocator ก่อน จากนั้นรายการหน่วยความจำว่าง แล้วจึงการจัดแนวและการแบ่งบล็อก

/* The four pillars of a custom allocator */
/* 1. memory source   2. block headers */
/* 3. free-block search   4. alignment */

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

ทดสอบความเข้าใจเกี่ยวกับการทำงานภายในของตัวจัดสรร

สรุปทบทวน

malloc จัดการฮีปที่ได้จาก OS ผ่าน sbrk หรือ mmap โดยแบ่งฮีปออกเป็นบล็อกที่มีส่วนหัวซ่อนอยู่ ซึ่งติดตามขนาดและสถานะว่าง

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

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

บทเรียน “malloc ทำงานอย่างไร” ฟรีหรือไม่

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

คุณจะเรียนรู้อะไรในบทเรียน “malloc ทำงานอย่างไร”

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

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

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

บทเรียน “malloc ทำงานอย่างไร” ใช้เวลานานแค่ไหน

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

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

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

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

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