lockfree

ล็อคฟรี

lockfree คือชุดของโครงสร้างข้อมูลที่ไม่มีการล็อคซึ่งเขียนด้วยมาตรฐาน C++ 11 และเหมาะสำหรับทุกแพลตฟอร์ม ตั้งแต่การฝังลึกไปจนถึง HPC

โครงสร้างข้อมูลที่ไม่มีการล็อคคืออะไร?

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

ทำไมต้องใช้ lockfree

• เขียนด้วยมาตรฐาน C++11 เข้ากันได้กับทุกแพลตฟอร์มที่รองรับ
• โครงสร้างข้อมูลทั้งหมดเป็นแบบเธรดและการขัดจังหวะที่ปลอดภัยในกรณีการใช้งานที่เกี่ยวข้อง
• ไม่มีการจัดสรรแบบไดนามิก
• ปรับให้เหมาะสมเพื่อประสิทธิภาพสูง
• เอ็มไอทีได้รับใบอนุญาต
• API เพิ่มเติมสำหรับเวอร์ชัน C++ ที่ใหม่กว่า

มีโครงสร้างข้อมูลอะไรบ้าง?

โครงสร้างข้อมูลผู้บริโภครายเดียวจากผู้ผลิตรายเดียว

• คิว - ดีที่สุดสำหรับการดำเนินการองค์ประกอบเดียว API ที่รวดเร็วและเรียบง่ายซึ่งประกอบด้วย 2 วิธีเท่านั้น
• Ring Buffer - โครงสร้างข้อมูลทั่วไปที่มีความสามารถในการจัดการองค์ประกอบหลายรายการในแต่ละครั้ง ใช้สำเนาไลบรารีมาตรฐานทำให้การดำเนินการจำนวนมากรวดเร็วมาก
• Bipartite Buffer - รูปแบบของบัฟเฟอร์วงแหวนที่มีความสามารถในการจัดเตรียมพื้นที่เชิงเส้นในบัฟเฟอร์เสมอ ช่วยให้สามารถประมวลผลในบัฟเฟอร์ได้
• คิวลำดับความสำคัญ - การเปลี่ยนแปลงของคิวที่มีความสามารถในการจัดลำดับความสำคัญที่แตกต่างกันสำหรับองค์ประกอบ ซึ่งมีประโยชน์มากสำหรับสิ่งต่างๆ เช่น สัญญาณ เหตุการณ์ และแพ็กเก็ตการสื่อสาร

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

โครงสร้างข้อมูลผู้บริโภคหลายราย

• คิว - ดีที่สุดสำหรับการดำเนินการองค์ประกอบเดียว API ที่รวดเร็วและเรียบง่ายซึ่งประกอบด้วย 2 วิธีเท่านั้น
• คิวลำดับความสำคัญ - การเปลี่ยนแปลงของคิวที่มีความสามารถในการจัดลำดับความสำคัญที่แตกต่างกันสำหรับองค์ประกอบ ซึ่งมีประโยชน์มากสำหรับสิ่งต่างๆ เช่น สัญญาณ เหตุการณ์ และแพ็กเก็ตการสื่อสาร

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

วิธีการรับ

มีสามวิธีหลักในการรับห้องสมุด:

• การใช้ CMake FetchContent()
• เป็นโมดูลย่อย git
• โดยการดาวน์โหลดรุ่นจาก GitHub

การกำหนดค่า

lockfree ใช้การจัดตำแหน่ง cacheline สำหรับดัชนีเพื่อหลีกเลี่ยงปรากฏการณ์การแบ่งปันที่ผิดพลาดตามค่าเริ่มต้น หลีกเลี่ยงการสูญเสียประสิทธิภาพของการทำให้ cacheline ใช้งานไม่ได้บนระบบที่เชื่อมโยงกันของแคช สิ่งนี้จะจัดดัชนีเป็น LOCKFREE_CACHELINE_LENGTH , 64 โดยค่าเริ่มต้น

ในระบบฝังตัว LOCKFREE_CACHE_COHERENT ควรตั้งค่าเป็น false เกือบทุกครั้งเพื่อหลีกเลี่ยงการสิ้นเปลืองหน่วยความจำ

นอกจากนี้ บางระบบมีความยาวแคชไลน์ที่ไม่ปกติ (เช่น Apple M1/M2 CPU มีความยาวแคชไลน์ 128 ไบต์) และควรตั้งค่า LOCKFREE_CACHELINE_LENGTH ตามนั้นในกรณีเหล่านั้น

ข้อจำกัดที่ทราบ

โครงสร้างข้อมูลทั้งหมดใน lockfree มีไว้เพื่อใช้สำหรับประเภทที่ไม่สำคัญเท่านั้น

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

เหตุใดฉันจึงใช้สิ่งนี้ในการล็อกโครงสร้างข้อมูลบนเครื่องที่โฮสต์

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

นอกจากนี้ lockfree ยังมีวิธีสร้างแอปพลิเคชันและไลบรารีที่สามารถคอมไพล์เพื่อทำงานทั้งในสภาพแวดล้อม POSIX และที่ไม่ใช่ POSIX โดยไม่ต้องใช้ #ifdef s หรือ polymorphism

เหตุใดจึงใช้สิ่งนี้ผ่านกลไก IPC ของ RTOS บนระบบฝังตัว

แม้ว่าการล็อคมักจะไม่แพงในระบบฝังตัว เช่น ไมโครคอนโทรลเลอร์ แต่ก็มี RTOS-es ที่หลากหลาย และไม่มี API มาตรฐานสำหรับการล็อค ความจริงที่ว่ามีสถาปัตยกรรมหลายตัวตั้งแต่ 8051 ถึง RISC-V หมายความว่าวิธีการจัดการการขัดจังหวะไม่ได้มาตรฐานเช่นกัน

lockfree มอบวิธีสร้างโค้ดแบบฝังแบบพกพาโดยมีค่าใช้จ่ายด้านประสิทธิภาพเล็กน้อย เมื่อเทียบกับการล็อค โค้ดที่ใช้ lockfree สามารถคอมไพล์เพื่อทำงานบนแพลตฟอร์มแบบฝังตัวที่รองรับ C ++ 11 นอกจากนี้ โค้ดยังสามารถทดสอบบนเครื่องโฮสต์ได้อย่างง่ายดายโดยไม่จำเป็นต้องจำลอง

การใช้ C++ บน C มีข้อดีอะไรบ้างสำหรับไลบรารี

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

การจำแนกประเภทอย่างเป็นทางการของโครงสร้างข้อมูลใน lockfree คืออะไร?

โครงสร้างทั้งหมดใน lockfree มี ขอบเขต อิงอาเรย์ และ ไม่มีการล็อก โครงสร้างข้อมูล spsc ก็ ไม่ต้องรอ และ มีความปลอดภัยในการยกเลิก

ทฤษฎีและการอ้างอิง

สำหรับข้อมูลเชิงลึกเพิ่มเติมเกี่ยวกับการเขียนโปรแกรมแบบไร้ล็อค โปรดดูที่:

• ซีรีส์พูดคุยอันยอดเยี่ยมจาก Herb Sutter
• ซีรีส์พูดคุยสดแบบ Lock-Free หรือ Deadlock จาก Fedor Pikus
• บล็อกที่ยอดเยี่ยมของ Dmitry Vyukov