พอยน์เตอร์ตรวจสอบอันตรายและปัญหา ABA

ในโค้ดไร้ล็อกที่ใช้ตัวชี้ ค่าอาจเป็น A เปลี่ยนเป็น B แล้วกลับมาเป็น A ได้ การเปรียบเทียบด้วย CAS ที่ดูเฉพาะค่าไม่อาจทราบได้ว่ามีการเปลี่ยนแปลงเกิดขึ้นระหว่างนั้น

เธรดที่ 1 อ่านตัวชี้ A และเตรียมทำ CAS ระหว่างนั้นเธรดที่ 2 ลบ A แล้วจัดสรรโหนดใหม่ที่บังเอิญนำที่อยู่ของ A กลับมาใช้ ทำให้ CAS ของเธรดที่ 1 สำเร็จอย่างไม่ถูกต้อง

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

แท็กจำเป็นต้องใช้ตัวแปรอะตอมิกที่มีความกว้างสองเท่า เช่น CMPXCHG16B บน x86 ซึ่งใช้พื้นที่มากขึ้นและอาจไม่มีให้ใช้บนทุกแพลตฟอร์ม

ปัญหาพื้นฐานคือ จะลบโหนดที่เธรดอื่นอาจกำลังเข้าถึงอยู่ได้อย่างไร โค้ดไร้ล็อกไม่สามารถใช้ delete แบบง่าย ๆ ได้

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

สำหรับการเข้าถึงแต่ละครั้ง:

1. อ่านตัวชี้แบบอะตอมิก
2. เผยแพร่ตัวชี้นั้นเป็นตัวชี้อันตราย
3. อ่านซ้ำเพื่อยืนยันว่าตัวชี้ไม่เปลี่ยนแปลง (หลีกเลี่ยงภาวะแข่งขัน)
4. ใช้งานตัวชี้
5. ล้างตัวชี้อันตราย

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

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

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

ABA จะเป็นปัญหาเฉพาะเมื่อมีรายการหน่วยความจำว่างหรือมีการนำที่อยู่หน่วยความจำกลับมาใช้ หากมีการเรียกคืนหน่วยความจำอย่างปลอดภัยด้วยตัวชี้อันตรายหรือยุค ปัญหานี้มักหมดไป

โครงสร้างข้อมูลไร้ล็อกเต็มไปด้วยกับดัก โปรดใช้การทำงานที่ผ่านการพิสูจน์แล้วจาก Folly, Boost หรือ Crossbeam (Rust) เขียนขึ้นเองเฉพาะเพื่อการศึกษา หรือเส้นทางการทำงานที่ต้องการประสิทธิภาพเป็นพิเศษ หลังจากวัดประสิทธิภาพอย่างรอบคอบแล้วเท่านั้น

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

ปัญหา ABA ในการเขียนโปรแกรมไร้ล็อกหมายถึงอะไร?

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