C Academy · บทเรียน

การจัดแนวและการแบ่ง

ทำให้บล็อกใช้งานได้และเป็นระเบียบ

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

เหตุผลที่การจัดแนวสำคัญ

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

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

#include <stdalign.h>
/* the strictest fundamental alignment */
size_t strict = alignof(max_align_t);   /* often 16 */

เทคนิค align_up

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

วิธีนี้ใช้ได้ก็ต่อเมื่อ a เป็นเลขยกกำลังสอง ซึ่งการจัดแนวจริงทุกแบบเป็นเช่นนั้น

static size_t align_up(size_t n, size_t a) {
    return (n + a - 1) & ~(a - 1);
}
/* align_up(13, 8) == 16, align_up(16, 8) == 16 */

พิสูจน์ว่าคณิตศาสตร์ทำงานได้

มาทดสอบ align_up ด้วยโปรแกรมที่เรียกใช้ได้ โปรแกรมจะปัดขนาดหลายค่าขึ้นไปยังขอบเขต 8 และ 16 ไบต์ แล้วแสดงผลลัพธ์

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

static size_t align_up(size_t n, size_t a) {
    return (n + a - 1) & ~(a - 1);
}

int main(void) {
    printf("%zu\n", align_up(13, 8));   /* 16 */
    printf("%zu\n", align_up(16, 8));   /* 16 */
    printf("%zu\n", align_up(1, 16));   /* 16 */
    printf("%zu\n", align_up(33, 16));  /* 48 */
    return 0;
}

การจัดแนวขนาดที่ร้องขอ

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

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

#define ALIGN 16
void *my_alloc(size_t size) {
    size = align_up(size, ALIGN);
    /* now find a block of this aligned size */
    /* ... */
    return NULL;
}

ปัญหาของการนำทั้งบล็อกกลับมาใช้ใหม่

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

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

การแยกบล็อก

หากบล็อกที่เลือกมีขนาดใหญ่กว่าที่ต้องการมาก เราจะวางส่วนหัวใหม่ไว้ที่ท้ายบริเวณที่ร้องขอ ส่วนที่เหลือจะกลายเป็นบล็อกว่างขนาดเล็กลงในรายการ

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

void split(block_t *b, size_t size) {
    size_t rem = b->size - size;
    if (rem < sizeof(block_t) + ALIGN) return; /* too small */
    block_t *nb = (block_t *)((char *)(b + 1) + size);
    nb->size = rem - sizeof(block_t);
    nb->free = 1;
    nb->next = b->next;
    b->size = size;
    b->next = nb;
}

จัดสรร จัดแนว และแยกบล็อก

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

วิธีนี้ทำให้บล็อกมีขนาดพอดีและเหลือพื้นที่ว่างที่ใช้งานได้ไว้ด้านหลัง

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

รักษาการจัดแนวของพูลเอง

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

การใช้ alignas กับบัฟเฟอร์แบบ static รับประกันว่าโครงสร้างทั้งหมดจะเริ่มต้นอย่างถูกต้องตามแนว

#include <stdalign.h>
alignas(16) static unsigned char pool[4096];
/* pool now begins on a 16-byte boundary */

การจัดสรรที่จัดแนวแล้วซึ่งเรียกใช้ได้

โปรแกรมนี้จัดสรรจากพูลที่จัดแนวแล้ว และแสดงค่าที่อยู่ที่คืนมาเมื่อหารด้วย 16 โดยแสดงให้เห็นว่าผลลัพธ์เป็นศูนย์เสมอ หรือก็คือจัดแนวอย่างถูกต้อง

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

static size_t align_up(size_t n, size_t a){ return (n+a-1)&~(a-1); }
alignas(16) static unsigned char pool[1024];
static size_t off = 0;

void *alloc16(size_t s){ off=align_up(off,16); if(off+s>sizeof(pool)) return NULL; void*p=&pool[off]; off+=s; return p; }

int main(void){
    void *a = alloc16(1);
    void *b = alloc16(20);
    printf("a %% 16 = %lu\n", (unsigned long)((size_t)a % 16));
    printf("b %% 16 = %lu\n", (unsigned long)((size_t)b % 16));
    return 0;
}

การแยกบล็อกเทียบกับการรวมบล็อก

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

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

จากตัวอย่างจำลองสู่ตัวจัดสรรจริง

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

แต่แนวคิดหลักที่คุณสร้างที่นี่เป็นพื้นฐานของการใช้งาน malloc ทุกแบบ

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

ลองพิจารณาว่าเหตุใดจึงต้องแยกบล็อกระหว่างการจัดสรร

สรุปทบทวน

การจัดแนวจะปัดขนาดขึ้นด้วยเทคนิคบิต (n + a - 1) & ~(a - 1) เพื่อให้ส่วนข้อมูลทุกส่วนเหมาะกับชนิดข้อมูลทุกชนิด การแยกบล็อกจะแบ่งบล็อกว่างที่ใหญ่เกินไปออกเป็นส่วนที่ใช้งานและส่วนที่เหลือซึ่งว่างอยู่ ขณะที่การรวมบล็อกจะย้อนกระบวนการนี้เมื่อคืนพื้นที่

องค์ประกอบหลักทั้งสี่ประการนี้รวมกันเป็นตัวจัดสรรหน่วยความจำที่สมบูรณ์และถูกต้อง

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

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

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

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

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

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

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

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

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

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

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

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

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